Nonparametric belief propagation

By Erik B. Sudderth, A. Ihler, William T. Freeman, Alan S. Willsky. 2003

615 citations recorded by the source corpus.

In many applications of graphical models arising in computer vision, the hidden variables of interest are most naturally specified by continuous, non-Gaussian distributions. There exist inference algorithms for discrete approximations to these continuous distributions, but for the high-dimensional variables typically of interest, discrete inference becomes infeasible. Stochastic methods such as particle filters provide an appealing alternative. However, existing techniques fail to exploit the rich structure of the graphical models describing many vision problems. Drawing on ideas from regularized particle filters and belief propagation (BP), this paper develops a nonparametric belief propagation (NBP) algorithm applicable to general graphs. Each NBP iteration uses an efficient sampling procedure to update kernel-based approximations to the true, continuous likelihoods. The algorithm can accommodate an extremely broad class of potential functions, including nonparametric representations. Thus, NBP extends particle filtering methods to the more general vision problems that graphical models can describe. We apply the NBP algorithm to infer component interrelationships in a parts-based face model, allowing location and reconstruction of occluded features.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “(2007), Székely and Rizzo (2009) for an independence test as a weighted L2-distance between characteristic functions of the joint and product distributions.”
Kernel Belief Propagation (2011, methodology): “We describe two competing approaches for nonparametric belief propagation: Gaussian mixture BP, originally known as non-parametric BP (Sudderth et al., 2003), and particle BP (Ihler & McAllester, 2009).”
Unsupervised Learning of Object Deformation Models (2007, methodology): “Particle filtering methods for general graphical models like NBP/PAMPAS [21, 11, 20, 10] deal with this problem, using sampling-based approximations to the messages and posteriors, and focusing on a smaller region of the state space; we use the efficient implementation of NBP made available by [10].”
Harmony Potentials (2011, background): “For models with variables on very large domains, inference is usually made possible by discarding labels (Freeman et al, 2000; Cough-lan and Ferreira, 2002) or sampling the label space (Ih-ler and McAllester, 2009; Koller et al, 1999; Sudderth et al, 2002).”
Global stereo reconstruction under second order smoothness priors (2008, background): “While recent developments of BP have lead to continuous representations of the state space of variables [38], [39], and also linear3 increases in computational cost with clique size for certain classes of clique functional [40] (including those based on derivatives), the fact remains that BP perform”
Fault Identification Via Nonparametric Belief Propagation (2009, background): “cles, exact inference is often difficult; however, similar message-passing algorithms such as loopy BP perform approximate inference [33].”
Particle Belief Propagation (2009, methodology): “On the other hand, many implementations of NBP also use MCMC steps at each iteration to draw samples from the message product (e.g., Sudderth et al., 2003), and thus have similar cost and convergence assessment issues.”
Facial point detection using boosted regression and graph models (2010, methodology): “[21]), using for example a coordinate system based on the head position.”
Simplifying Mixture Models Through Function Approximation (2006, positive): “Other examples that involve mixture models include the particle filter [20] and nonparametric belief propagation [39], [38], where the mixture model has to be frequently used or updated during the learning process.”
Learning Visual Representations for Interactive Systems (2009, methodology): “We use nonparametric belief propagation [20] optimized to exploit the specific structure of this inference problem [6].”
Tracking People by Learning Their Appearance (2007, background): “An attractive strategy is to ignore the loops and pass local messages [37] and to represent those messages with a set of samples [38], [39].”
Nonparametric belief propagation for self-localization of sensor networks (2005, background): “However, a particle-based approximation to BP, called NBP, results in a more tractable algorithm.”
Tracking loose-limbed people (2004, methodology): “The two formulations [13, 25] have different strengths; we adopt the PAMPAS algorithm [13] because it maps better to our models where the potentials are small mixtures of Gaussians and the likelihoods are simple to evaluate up to an unknown normalization.”
Image Completion Using Efficient Belief Propagation Via Priority Scheduling and Dynamic Pruning (2007, neutral): “[31] and Isard [32] have independently proposed a nonparametric BP algorithm.”
Partitioned Variational Inference: A unified framework encompassing federated and continual learning (2018, background): “It is, however, unclear how flexible variational approximations such as mixtures of exponential family distributions [see e.g. Sudderth et al., 2010] or normalizing flows [Rezende and Mohamed, 2015] can be efficiently and tractably accommodated in the PVI framework.”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, neutral): “As a result, many generalizations of belief propagation have been proposed in the literature [57], [55], [45], [9], [5], [16].”