Kernel Belief Propagation

Le Song, Arthur Gretton, Danny Bickson, Yucheng Low, Carlos Guestrin

Abstract

Kernel Belief Propagation (KBP) introduces a nonparametric framework for inference in pairwise Markov random fields by representing messages as functions within a Reproducing Kernel Hilbert Space (RKHS). Traditional Belief Propagation (BP) often relies on restrictive assumptions, such as discrete domains or Gaussian distributions. KBP overcomes these by treating message updates as simple linear operations in the RKHS, learned directly from data. This approach allows for inference on complex, non-Euclidean domains while achieving significant improvements in both computational speed and predictive accuracy.

The Limitations of Classical Belief Propagation

Belief Propagation is a fundamental tool for probabilistic inference, yet its practical application is frequently constrained by the "Gaussian or Discrete" bottleneck. Real-world data is rarely so well-behaved; it is often continuous, multimodal, and high-dimensional. While existing nonparametric methods like Particle BP or Gaussian Mixture BP attempt to address these complexities, they are often computationally prohibitive and require manually specified potential functions. The authors sought a truly nonparametric solution that learns relations directly from data while remaining computationally efficient.

Kernel Belief Propagation (KBP)

RKHS Embeddings and Linear Updates

KBP's core innovation lies in its use of RKHS embeddings. Instead of passing probability densities, KBP passes embeddings of these distributions. By mapping variables into a high-dimensional feature space, the complex integrals typically required for message updates are transformed into simple linear operations. Specifically, KBP utilizes empirical conditional embedding operators learned from training data, effectively bypassing the need for explicit density estimation or pre-defined potentials.

Learning and Efficiency

Unlike traditional BP, KBP learns variable interactions directly from training examples. To ensure scalability, the authors employ a low-rank approximation using a small set of basis functions selected via Gram-Schmidt orthogonalization. This enables constant-time message updates regardless of the training set size, allowing the algorithm to scale to massive datasets and high-resolution continuous data.

Experimental Results

The effectiveness of KBP was demonstrated across several diverse domains, including synthetic image denoising, 3D depth prediction (Make3D dataset), and protein configuration modeling (Protein Data Bank).

Speed and Scalability

In synthetic image denoising tasks, KBP demonstrated remarkable efficiency. As shown in the runtime analysis, while the cost of discrete BP increases quadratically with the number of states (colors), KBP maintains a nearly constant runtime. It outperforms Particle BP and Gaussian Mixture BP by orders of magnitude, making it uniquely suited for high-resolution tasks.

Runtime comparison showing KBP's efficiency as the number of colors increases.

Accuracy across Domains

Beyond speed, KBP consistently provides more accurate results. In denoising experiments, KBP achieved the lowest Root Mean Square Error (RMSE) across all color levels. In real-world depth prediction, KBP achieved a Mean Absolute Error (MAE) of 0.145, significantly outperforming discrete BP (0.22) and Gaussian mixtures (0.16). Furthermore, KBP successfully handled protein folding angles on a sphere—a non-Euclidean domain where standard Gaussian methods are mathematically ill-suited.

RMSE comparison for image denoising, demonstrating KBP's superior accuracy.

Conclusion

KBP represents a significant advancement in graphical model inference. By leveraging the power of kernel methods to turn calculus problems into linear algebra, it provides a versatile, efficient, and accurate alternative to traditional BP. Its ability to learn nonparametrically from data and handle non-Euclidean domains opens new possibilities for inference in complex real-world systems.

Summary updated

Abstract

We propose a nonparametric generalization of belief propagation, Kernel Belief Propagation (KBP), for pairwise Markov random fields. Messages are represented as functions in a reproducing kernel Hilbert space (RKHS), and message updates are simple linear operations in the RKHS. KBP makes none of the assumptions commonly required in classical BP algorithms: the variables need not arise from a finite domain or a Gaussian distribution, nor must their relations take any particular parametric form. Rather, the relations between variables are represented implicitly, and are learned nonparametrically from training data. KBP has the advantage that it may be used on any domain where kernels are defined (Rd, strings, groups), even where explicit parametric models are not known, or closed form expressions for the BP updates do not exist. The computational cost of message updates in KBP is polynomial in the training data size. We also propose a constant time approximate message update procedure by representing messages using a small number of basis functions. In experiments, we apply KBP to image denoising, depth prediction from still images, and protein configuration prediction: KBP is faster than competing classical and nonparametric approaches (by orders of magnitude, in some cases), while providing significantly more accurate results.
BibTeX
@inproceedings{song2011kernel,
  author = {Le Song and Arthur Gretton and Danny Bickson and Yucheng Low and Carlos Guestrin},
  title = {{Kernel Belief Propagation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=TKNE2jP2ED},
}
Figure