Kernel Belief Propagation

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

Abstract

Kernel Belief Propagation (KBP) is a nonparametric approach to inference in graphical models that represents messages as functions in a Reproducing Kernel Hilbert Space (RKHS). By learning the relationships between variables directly from data, KBP bypasses the restrictive assumptions of classical Belief Propagation (BP) and outperforms existing nonparametric methods in both speed and accuracy. This paper details the mathematical foundation of KBP, its constant-time update mechanism, and its superior performance across image denoising, depth prediction, and protein structure tasks.

Introduction

Belief Propagation (BP) is a fundamental algorithm for inference in graphical models, yet it faces a significant trade-off between flexibility and efficiency. Discrete BP is effective for finite states but scales poorly with continuous variables. Conversely, Gaussian BP handles continuous variables but relies on rigid parametric assumptions that fail in the presence of skewed or multimodal data. Existing nonparametric alternatives, such as Particle BP or Gaussian Mixture BP, are often computationally prohibitive due to slow sampling steps and the need for manually specified potential functions.

Kernel Belief Propagation (KBP) addresses these challenges by treating BP through the lens of kernel methods, allowing for a model-free approach that learns complex dependencies directly from training data.

Methodology

KBP represents messages as functions within an RKHS rather than probability densities or histograms. The core innovation lies in interpreting the standard BP integral update as a conditional expectation. In an RKHS, these expectations can be computed as simple linear operations using conditional embedding operators.

To ensure scalability, KBP avoids the polynomial complexity typically associated with kernel methods. The authors employ a low-rank approximation via a greedy Gram-Schmidt process, representing messages using a small set of basis functions. This optimization reduces message update costs to constant time relative to the training set size, enabling the algorithm to handle millions of data points efficiently.

Experimental Evaluation

The efficacy of KBP was evaluated across three diverse domains:

  1. Image Denoising: Synthetic "sunset" images were used to test performance across varying color levels (up to 250).
  2. Depth Prediction: Using the Make3D dataset, KBP predicted 3D depth maps from 2D images, a task characterized by multimodal depth possibilities.
  3. Protein Structure Prediction: KBP was applied to Protein Data Bank (PDB) data to predict angle pairs defining protein folds, demonstrating its ability to handle non-Euclidean domains like the unit sphere.

Key Results

KBP demonstrates significant advantages in both computational speed and predictive accuracy. In image denoising tasks, KBP's runtime remains nearly constant as the number of color levels increases, whereas Discrete BP's runtime grows exponentially.

Performance of KBP on sunset image denoising. (a) Original image, (b) Noisy input, (c) RMSE comparison, and (d) Runtime comparison showing KBP's scalability.

In depth prediction, KBP achieved a Mean Absolute Error (MAE) of 0.145, outperforming both discrete and other nonparametric methods. Its ability to capture multimodal distributions was crucial for accurately mapping 2D features to 3D depths. Furthermore, KBP proved robust in protein folding applications, where traditional methods struggle with non-Euclidean variable spaces.

Discussion and Future Work

While KBP shows empirical success on loopy graphs, theoretical convergence remains an open question. Future research may explore extending KBP to tree-reweighted BP to improve performance on highly cyclic graphs. Additionally, while the low-rank approximation ensures speed, performance remains sensitive to kernel selection and hyperparameter tuning. Despite these areas for growth, KBP represents a major step forward in flexible, scalable inference for complex graphical models.

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