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 compilation obtained so far. This online collapsing, together with knowledge compilation inference on the remaining variables, naturally exploits local structure and contextspecific independence in the distribution. These properties are used implicitly in exact inference, but are difficult to harness for approximate inference. Moreover, 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.
This paper proposes an approximate inference algorithm that combines SDDs with importance sampling. Previously, SDDs have been used for exact inference, by compiling probabilistic graphical models into a tractable SDD representation for answering queries. However, this compilation may lead to an exponentially large representation. Instead, the authors of this paper propose to interleave the compilation process with sampling assignments for individual variables in order to reduce the SDD and keep its size small.  The partially compiled SDD itself serves as a proposal distribution for sampling.  The algorithm is similar to other importance sampling algorithms, but I thought the way that it used SDDs and sampled variables dynamically was clever. The experiments comparing different variable selection strategies and baseline proposal distributions were useful. It makes sense that the frontier method would work well, since variables that participate in many factors could have their probabilities greatly changed by each factor. In fact, you could design really bad cases where factors contradict the included ones, leading to a proposal distribution that's much worse than uniform. I'd be interested to see additional discussion of limitations and when these methods will work particularly well or poorly compared to other algorithms.  I do not follow the literature on approximate inference closely enough to know if the baselines used are still state-of-the-art and represent the best comparison. SampleSearch and EDBP have been around for a while... is there anything more recent that's worthy of discussion or empirical comparison? That said, both algorithms have performed well on these benchmarks in the past, and the benchmarks are from inference competitions designed specifically to test approximate inference algorithms. In my review, I will assume that the empirical comparison is as strong as reported. Additional discussion of related work (even if it's not compared empirically) would be welcome, as would more explanation of why these inference tasks are meaningful on these datasets and how to interpret the metrics. For example, collapsed inference means that probabilities of very unlikely events can still be estimated. Are there appropriate experiments that could test predictions of rare events?  One suggested piece of related work:    Gogate and Domingos, "Approximation by Quantization," UAI 2011  This work performs exact inference on a model where the parameters have been approximated to make reasoning tractable. I suspect this paper is less general-purpose and less accurate than what is proposed here, but there are some common themes of connecting exact and approximate inference and using representations that support rich structure (algebraic decision diagrams, in this case, instead of SDDs).  (This is not a serious problem -- just a suggestion for the authors which they are free to disregard.)  Overall summary: Clever combination of different inference methods with good empirical results. If a longer version of this paper is ever published, it would help to have even more analysis and context.  After the author response: I've read the author response and the other reviews, and I remain enthusiastic about this paper. The comments by Reviewer 1 and the author response increase my confidence that this paper is sound and state-of-the-art. The comments by Reviewer 3 do not convince me that anything is lacking or inadequate about this paper. I have changed my rating from 7 to 8.