Approximate Knowledge Compilation by Online Collapsed Importance
  Sampling
  We introduce collapsed compilation, a novel approximate inference algorithm
for discrete probabilistic graphical models. It is a collapsed sampling
algorithm that incrementally selects which variable to sample next based on the
partial sample obtained so far. This online collapsing, together with knowledge
compilation inference on the remaining variables, naturally exploits local
structure and context- specific independence in the distribution. These
properties are naturally exploited in exact inference, but are difficult to
harness for approximate inference. More- over, by having a partially compiled
circuit available during sampling, collapsed compilation has access to a highly
effective proposal distribution for importance sampling. Our experimental
evaluation shows that collapsed compilation performs well on standard
benchmarks. In particular, when the amount of exact inference is equally
limited, collapsed compilation is competitive with the state of the art, and
outperforms it on several benchmarks.
