Block enumeration on dependent principal nodes may generate wrong stationary distribution

[axch]

Block enumeration proceeds thus:

• Query each principal node's operator for the set of possible values (before detaching)
• Form the Cartesian product
• Evaluate the posterior at every combination
• Then, for enumerative Gibbs, sample from that This amounts to computing an independent product of the possibility set.

This is problematic if the set of options available at node B can depend on the value chosen for node A. Example situations where that might happen:

• B is a categorical whose objects argument depends on the value of A.
• A and B are both the same CRP that also has other applications (in this case, if A is assigned to a unique table, B needs to possibly be assigned to the same unique table as A, or to a different unique table).

The fact that enumerateValues is called pre-detach is also problematic. Consider three CRP applications being jointly enumerated. Up to renumbering the tables (but not reordering the applications), there are five possible partitions: (1, 1, 1), (1, 1, 2), (1, 2, 1), (1, 2, 2), (1, 2, 3). However, the size of the set of combinations that the above enumeration algorithm will consider will be some perfect cube. In fact, the cube in question will actually depend on the initial state -- 2^3 from (1, 1, 1), 3^3 from any of the middle configurations, or 4^3 from (1, 2, 3). This means that enumeration will consider some equivalent combinations more than once; and, since none of the cubes are 5^3, will necessarily consider some combinations different numbers of times from others. I conjecture that it will overweight the configurations it overcounts.

[axch]

From conversation with @luac, the following looks like a solution. It essentially amounts to making LKernels that use amb, but with what amounts to an ad-hoc delimited continuation structure instead of trying to mess with the actual Python interpreter's actual continuations.

To wit, define a new kind of LKernel, called, say, SearchNodeLKernel, and attach a bunch of them, sharing a common (mutable) search tree state. After a proposal, the state of the tree indicates the values that have been proposed, and, at each node, the remaining agenda for the consequences of all the previous nodes being given the values currently in the tree. Before a proposal, the state indicates the values to propose. The special value None means "when you get here, query the operator's enumerateValues method, store that as the agenda, and propose the first element." Stepping from completed proposal to next proposal can be done in the enumeration loop.

Issues:

• This loses the parallelism currently available to enumerative Gibbs.
  • However, can at least evaluate the agenda of the last node in parallel.
• This leaves #470 (sensitivity to unreachable table ids) unresolved.
• I don't particularly relish the required implementation effort.
• Does this plan work if the value proposed can affect the regeneration order of the nodes? The answer might be "yes".
• This plan doesn't work if the set of nodes that exists can be affected by the values chosen, but I am under the impression that we explicitly ban those anyway.

[axch]

Another use case: Block enumerating a discrete choice together with an exactly guarding one of its consequences. If asked first, the exactly will report one possible output, namely the one it currently has -- defeating the purpose of including it in the block.

My revision to @pgmoren 's HDP-HMM model has this problem.