Enumeration query doesn't work in a simple widget model

[juliusc]

The following code gives a stack overflow error:

(enumeration-query

  ;;this machine makes a widget -- which we'll just represent with a real number:
  (define (widget-maker)  (multinomial '(.2 .3 .4 .5 .6 .7 .8) '(.05 .1 .2 .3 .2 .1 .05)))

  ;;this machine tests widgets as they come out of the widget-maker, letting
  ;; through only those that pass threshold:
  (define (next-good-widget)
    (define widget (widget-maker))
    (if (> widget threshold)
        widget
        (next-good-widget)))

  ;;but we don't know what threshold the widget tester is set to:

  (define threshold  (multinomial '(.3 .4 .5 .6 .7) '(.1 .2 .4 .2 .1)))

  ;;what is the threshold?
  threshold

  ;;if we see this sequence of good widgets:
  (equal? (repeat 3 next-good-widget)
          '(0.6 0.7 0.8)))

This is a modification of one of the probmods code examples, with rejection changed to enumeration. I've yet to investigate why this happens.

[longouyang]

This is the correct behavior, as the hypothesis space here is not finite.

For instance, suppose that we are just sampling a single widget conditional on a threshold of 0.5. Inside next-good-widget, we can get arbitrarily long sequences of widget draws with value less than the threshold. enumeration-query searches in order and tries to exhaust these, but it obviously can't.

For better usability, we might want to detect when hypothesis spaces are infinite and complain. Even better (but harder) would be to accommodate some simple cases of infinite hypothesis spaces when the posterior support is finite (this likely requires constraint propagation, which no one has had the stomach to implement yet)

[juliusc]

Aha, I didn't look carefully enough at that, and had not thought about these recursive functions.

Isn't detecting an infinite hypothesis space solving the halting problem?

[longouyang]

There are broad classes where you can solve halting, though, (e.g., finite state machines, pushdown automata with finite resources)

[ngoodman]

There are indeed broad cases where detecting non-halting is possible (and where solving exact enumeration is still possible -- see cosh). But we aren't necessarily in those cases, so we can't detect in general. Detecting for specific cases is probably not worth it...