Inference for Belief Networks Using Coupling From the Past
This addresses the challenge of exact inference for researchers in probabilistic graphical models, though it is incremental as it focuses on a specific network type.
The paper tackles the problem of exact inference in belief networks by proposing a method based on coupling from the past for layered noisy-or networks, which samples from the correct distribution with about twice the time per step as ordinary Gibbs sampling but may require more simulation steps.
Inference for belief networks using Gibbs sampling produces a distribution for unobserved variables that differs from the correct distribution by a (usually) unknown error, since convergence to the right distribution occurs only asymptotically. The method of "coupling from the past" samples from exactly the correct distribution by (conceptually) running dependent Gibbs sampling simulations from every possible starting state from a time far enough in the past that all runs reach the same state at time t=0. Explicitly considering every possible state is intractable for large networks, however. We propose a method for layered noisy-or networks that uses a compact, but often imprecise, summary of a set of states. This method samples from exactly the correct distribution, and requires only about twice the time per step as ordinary Gibbs sampling, but it may require more simulation steps than would be needed if chains were tracked exactly.