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
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
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
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
1. alspach, d.L. and sorenson, h.w.
nonlinear bayesian estimation
using gaussian sum
approximations, Morgan Kaufmann.
IEEE Trans. AC 17, 4 (aug. 1972),
2. anderson, b.d.o., Moore, J.b. Optimal
Filtering. Prentice hall, new Jersey,
3. andrieu, c., de Freitas, n., doucet, a.,
Jordan, M.i. an introduction to McMc
for machine learning. Mach. Learn. 50
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),
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),
7. coughlan, J., shen, h. dynamic
quantization for belief propagation
in sparse spaces. Comput. Vis.
Image underst. 106, 1 (2007),
8. coughlan, J.M., Ferreira, s.J. Finding
deformable shapes using loopy belief
propagation. in ECCV, vol. 3, (2002),
9. dawid, a.P., Kjaerulff, u., Lauritzen, s.L.
hybrid propagation in junction trees.
in Advances in Intelligent Computing
10. del Moral, P. Feynman-Kac
Formulae: Genealogical and
Interacting Particle Systems with
new york, 2004.
11. doucet, a., de Freitas, n., gordon, n.,
eds. Sequential Monte Carlo Methods
in Practice. springer-Verlag, new york,
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),
14. Freeman, w.t., Pasztor, e.c.,
carmichael, o.t. Learning low-level vision. IJCV 40, 1 (2000),
15. Frey, b. J., MacKay, d. J.c. a revolution:
belief propagation in graphs with
cycles. in NIPS 10 (1998), Mit Press,
16. gogate, V., dechter, r. and/or
importance sampling. in uAI (2008),
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,
19. han, t.X., ning, h., huang, t.s.
efficient nonparametric belief
propagation with application to
articulated body tracking. in CVPR
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
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),
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
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
26. isard, M. PaMPas: real-valued
graphical models for computer
vision. in CVPR, vol. 1 (2003),
27. isard, M., Maccormick, J., achan, K.
for message-passing algorithms.
in NIPS (2009), Mit Press,