Communications - October 2010

or misleading, these approximations will heavily distort the resulting estimates.

One advantage of Monte Carlo and particle filtering methods lies in the fact that their discretization of the state space is obtained stochastically, and thus has excellent theoretical properties. Examples include statistical consistency, and convergence rates that do not depend on the dimension. 10 While particle filters are typically restricted to “forward” sequential inference, the connection to discrete inference has been exploited to define smoothing (forward and backward) algorithms, 6 and to perform resampling to dynamically improve the approximation. 35 Monte Carlo approximations were also previously applied to other tree-structured graphs, including junction trees. 9, 29

Gaussian mixture models also have a long history of use in inference. In Markov chains, an algorithm for forward inference using Gaussian mixture approximations was first proposed by Alspach and Sorenson1; see also Anderson and Moore. 2 Regularized particle filters smooth each particle with a small, typically Gaussian kernel to produce a mixture model representation of forward messages. 11 For Bayesian networks, Gaussian mixture-based potentials and messages have been applied to junction tree-based inference. 12

NBP combines many of the best elements of these methods. By sampling, we obtain probabilistic approximation properties similar to particle filtering. Representing messages as Gaussian mixture models provides smooth estimates similar to regularized particle filters, and interfaces well with Gaussian mixture estimates of the potential functions. 12, 14, 17, 38 NBP extends these ideas to “loopy” message passing and approximate inference.

Since the original development of NBP, a number of algorithms have been developed that use alternative representations for inference on continuous, or hybrid, graphical models. Of these, the most closely related is particle BP, which uses a simplified importance sampling representation of messages, more closely resembling the representation of (unregularized) particle filters. This form enables the derivation of convergence rates similar to those available for particle filtering, 21 and also allows the algorithm to be extended to more general inference techniques such as reweighted message-passing algorithms. 24

Other forms of message representation have also been explored. Early approaches to deterministic discrete message approximation would often mistakenly discard states in the early stages of inference, due to misleading local evidence. More recently, dynamic discretization techniques have been developed to allow the inference process to recover from such mistakes by re-including states that were previously removed. 7, 27, 36 Other approaches substitute alternative, smoother message representations, such as Gaussian process-based density estimates. 40

Finally, several authors have developed additional ways of combining Monte Carlo sampling with the principles of exact inference. AND/OR importance sampling, 16 for example, uses the structure of the graph to improve the statistical

102 communicationS of the acm | OcTOber2010 | VOL. 53 | nO. 10

efficiency of Monte Carlo estimates given a set of samples. Another example, Hot Coupling, 18 uses a sequential ordering of the graph’s edges to define a sequence of importance sampling distributions.

The intersection of variational and Monte Carlo methods for approximate inference remains an extremely active research area. We anticipate many further advances in the coming years, driven by increasingly varied and ambitious real-world applications.

acknowledgments

The authors thank L. Sigal, S. Bhatia, S. Roth, and M. Black for providing the person tracking results in Figure 7. Work of WTF supported by NGA NEGI-1582-04-0004 and by MURI Grant N00014-06-1-0734. Work of ASW supported by AFOSR Grant FA9559-08-1-1080 and a MURI funded through AFOSR Grant FA9550-06-1-0324.

1. alspach, d.L. and sorenson, h.w. nonlinear bayesian estimation using gaussian sum approximations, Morgan Kaufmann. IEEE Trans. AC 17, 4 (aug. 1972), 439–448.

2. anderson, b.d.o., Moore, J.b. Optimal Filtering. Prentice hall, new Jersey, 1979.

3. andrieu, c., de Freitas, n., doucet, a., Jordan, M.i. an introduction to McMc for machine learning. Mach. Learn. 50 (2003), 5–43.

4. baron, d., sarvotham, s., baraniuk, r.g. bayesian compressive sensing via belief propagation. IEEE Trans. Sig. Proc. 58, 1 (2010), 269–280.

5. briers, M., doucet, a., singh, s.s. sequential auxiliary particle belief propagation. in ICIF (2005), 705–711.

6. cappé, o., godsill, s.J., Moulines, e. an overview of existing methods and recent advances in sequential Monte carlo. Proc. IEEE 95, 5 (May 2007), 899–924.

7. coughlan, J., shen, h. dynamic quantization for belief propagation in sparse spaces. Comput. Vis. Image underst. 106, 1 (2007), 47–58.

8. coughlan, J.M., Ferreira, s.J. Finding deformable shapes using loopy belief propagation. in ECCV, vol. 3, (2002), 453–468.

9. dawid, a.P., Kjaerulff, u., Lauritzen, s.L. hybrid propagation in junction trees. in Advances in Intelligent Computing (1995), 87–97.

10. del Moral, P. Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications. springer-Verlag, new york, 2004.

11. doucet, a., de Freitas, n., gordon, n., eds. Sequential Monte Carlo Methods in Practice. springer-Verlag, new york, 2001.

12. driver, e., Morrell, d. implementation of continuous bayesian networks using sums of weighted gaussians. in uAI (1995), 134–140.

13. Felzenszwalb, P. F., huttenlocher, d.P. Pictorial structures for object recognition. IJCV 61, 1 (2005), 55–79.

14. Freeman, w.t., Pasztor, e.c., carmichael, o.t. Learning low-level vision. IJCV 40, 1 (2000),

References

25–47.

15. Frey, b. J., MacKay, d. J.c. a revolution: belief propagation in graphs with cycles. in NIPS 10 (1998), Mit Press, 479–485.

16. gogate, V., dechter, r. and/or importance sampling. in uAI (2008), 212–219.

17. grimes, d.b., rashid, d.r., rao, r.P. Learning nonparametric models for probabilistic imitation. in NIPS (2007), Mit Press, 521–528.

18. hamze, F., de Freitas, n. hot coupling: a particle approach to inference and normalization on pairwise undirected graphs of arbitrary topology. in NIPS 18 (2006), Mit Press, 491–498.

19. han, t.X., ning, h., huang, t.s. efficient nonparametric belief propagation with application to articulated body tracking. in CVPR (2006), 214–221.

20. heskes, t. on the uniqueness of loopy belief propagation fixed points. Neural Comp. 16 (2004), 2379–2413.

21. ihler, a., Mcallester, d. Particle belief propagation. in AI Stat. 12 (2009).

22. ihler, a.t., Fisher, J.w., Moses, r. L., willsky, a.s. nonparametric belief propagation for self-localization of sensor networks. IEEE J. Sel. Areas Commun. 23, 4 (apr. 2005), 809–819.

23. ihler, a.t., Fisher, J.w., willsky, a.s. Loopy belief propagation: convergence and effects of message errors. JMLR 6 (2005), 905–936.

24. ihler, a.t., Frank, a.J., smyth, P. Particle-based variational inference for continuous systems. in NIPS 22 (2009), 826–834.

25. ihler, a.t., sudderth, e.b., Freeman, w.t., willsky, a.s. efficient multiscale sampling from products of gaussian mixtures. in NIPS 16 (2004), Mit Press.