Particle Belief Propagation

Alexander Ihler, David A. McAllesterAISTATS 2009

Abstract

Particle Belief Propagation (PBP) provides a robust framework for inference in graphical models with continuous or large discrete state spaces. This paper introduces a formal theoretical analysis of PBP, proving its asymptotic consistency and establishing a finite-sample convergence rate of $O(1/\sqrt{n})$. Unlike Non-parametric Belief Propagation (NBP), which introduces statistical bias through kernel smoothing, PBP maintains a predictable accuracy improvement as the number of samples increases, regardless of the variable domain size.

Introduction

Belief Propagation (BP) is a fundamental algorithm for inference in graphical models. However, it faces a significant challenge when applied to continuous variables or massive discrete domains, such as 3D coordinates in robotics or pixel-level image analysis. Traditionally, BP requires variables to have a small number of discrete states or follow specific parametric forms like Gaussians. While particle filters address this for simple chains, generalizing them to complex graphs has historically relied on various heuristics. This paper provides a rigorous theoretical framework for Particle Belief Propagation (PBP), explaining its behavior as sample sizes grow.

Methodology: Particle Belief Propagation

The authors propose a generic PBP algorithm analyzed through importance sampling. Instead of passing full probability distributions, nodes pass messages represented by a finite set of $n$ weighted samples (particles).

A key distinction of this approach is how it avoids the "smoothing trap." Non-parametric Belief Propagation (NBP) typically uses kernel density estimation to smooth samples into continuous functions. While this makes the math appear cleaner, it introduces statistical bias and computational overhead. PBP defines messages directly on the particle locations of target nodes, sidestepping these issues.

The 'Sawtooth' image (a) and its corresponding disparity map (b) from the Middlebury Stereo Dataset, used to evaluate PBP's performance in continuous state-space inference.

Theoretical Analysis and Consistency

The core contribution is a proof of convergence using Bernstein’s inequality. The authors define a constant, $R_W$, representing the quality of the sampling distribution—how well the proposal distribution matches the true target. They prove that as the number of samples $n \to \infty$, the PBP estimate converges to the true BP message.

Crucially, the convergence rate is established as $O(1/\sqrt{n})$. This rate is independent of the size of the variable's domain, meaning PBP is equally effective for variables with a thousand states or a million, provided the sampling distribution is adequate.

Empirical Results

The approach was evaluated using the "Sawtooth" image from the Middlebury Stereo Dataset, a standard benchmark for depth reconstruction. The experiments confirmed the theoretical bounds: on a log-log plot, PBP's error followed the predicted $1/\sqrt{n}$ slope.

Comparison of L-1 error for PBP and NBP variants. PBP maintains the faster $1/\sqrt{n}$ convergence rate, while NBP's smoothing bias leads to slower convergence.

In direct comparison, PBP consistently achieved lower $L_1$ error than NBP. While NBP's error decreased at a rate of roughly $n^{-2/5}$ due to smoothing bias, PBP maintained the superior $n^{-1/2}$ ($1/\sqrt{n}$) rate. The results also highlighted the importance of the proposal distribution; sampling from the estimated marginal (the current "belief") yielded significantly better results than sampling from local potentials.

Conclusion and Future Directions

This work establishes PBP as a statistically superior method for inference in complex graphical models compared to smoothed alternatives. While the theory is robust for trees, extending these bounds to loopy graphs remains a challenge due to the exponential growth of the "unrolled" Bethe tree. Future work will also explore more efficient ways to calculate optimal sampling distributions and integrate Markov Chain Monte Carlo (MCMC) methods to improve particle selection.

Summary updated

BibTeX
@article{ihler2009particle,
  author = {Alexander Ihler and David A. McAllester},
  title = {{Particle Belief Propagation}},
  journal = {AISTATS},
  year = {2009},
}
Figure