Graphical model inference: Sequential Monte Carlo meets deterministic approximations
Approximate inference in probabilistic graphical models (PGMs) can be grouped into deterministic methods and Monte-Carlo-based methods. The former can often provide accurate and rapid inferences, but are typically associated with biases that are hard to quantify. The latter enjoy asymptotic consistency, but can suffer from high computational costs. In this paper we present a way of bridging the gap between deterministic and stochastic inference. Specifically, we suggest an efficient sequential Monte Carlo (SMC) algorithm for PGMs which can leverage the output from deterministic inference methods. While generally applicable, we show explicitly how this can be done with loopy belief propagation, expectation propagation, and Laplace approximations. The resulting algorithm can be viewed as a post-correction of the biases associated with these methods and, indeed, numerical results show clear improvements over the baseline deterministic methods as well as over "plain" SMC.
Summary and Assessment: ------------------------  This paper strives to improve Sequential Monte Carlo (SMC) sampling on probabilistic graphical models through the usage of twisted targets. More specifically, rather employ a "myopic" sequence of target distributions consisting of gradually introducing the factors and variables in the overall target (according to some ordering criteria) a method is devised by which the future can be conditionally approximated and taken into account. The idea is to devise a target that more closely approximates the true marginal distribution (\pi( x_1,...x_t) of \pi at step t rather than that resulting from dropping all future interactions. Proposition 1 presents the ideal but infeasible choice of twisting function. In effect, equation (6) defines a conditional partition function, and so approximating it with a deterministic method seems sensible. The authors present loopy BP, EP, and Laplace approximation approaches to achieve this. Improvements over myopic SMC are demonstrated in several regimes.   This is a good paper with nice ideas; I am encouraged to see ongoing research into improved sampling for PGMs. The paper is very well-written and clearly motivates the problem and contributions. Inference in PGMs remains an important problem today, and the authors present a natural and intuitively appealing enhancement to sampling techniques on these models. I believe this work should be accepted to NIPS.  The results and statements are technically correct to my knowledge.  Questions and Minor Issues: --------------------------  - Can more be said about the computational burden of the variational fitting? On line 232, the cost of BP is described as "quite small" which may well be true for 16x16 lattices, but the issue is how does such effort scale with problem size. Nonetheless I can readily believe that in many situations, the extra cost will be more than compensated for in the overall efficiency compared to myopic SMC.  - This is my most "serious" concern: is there any reason the authors did not include comparisons to SMC under traditional temperature-based annealing? In such a scheme, of course, the overall distribution is always considered, though at different "smoothness" due to the introduction of high-temperature target distributions. It is my experience that for "complex" energy landscapes, it is often quite difficult to do better than a temperature-based sequence. Quite likely, as the authors' results suggest, the cases presently considered are not such "rough" problems, as hinted at by the success of the variational approximations, but in those cases thermal annealing also tends to work quite well. I do suggest that in future work, the authors investigate this if they have not already done so.  - A suggestion regarding related work: a relatively early application of SMC to PGMs was Hamze and de Freitas (NIPS '05), where edges (potentials) were sequentially introduced to form the target sequence.  - A natural question one may ask, given that the method does something along the lines of a "lookahead", and that equation (6) specifies a conditional partition function, is how well a recursive application of the naive SMC method to approximate the optimal twisted target would fare. More specifically, (6) could be approximated with the myopic SMC (at step t, over variables t+1 to T), but with simulation parameters setting up a fast "pilot" run to get a rough estimate; it would be interesting to see how this does against the variational approximations. Have the authors considered such an approach?