Kernel Belief Propagation

By Le Song, Arthur Gretton, Danny Bickson, Yucheng Low, Carlos Guestrin. 2011

86 citations recorded by the source corpus.

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 (R d , 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.

Subfields: Artificial Intelligence, Probabilistic & Bayesian Methods

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

In Probabilistic & Bayesian Methods

Citations in the corpus

Discriminative Embeddings of Latent Variable Models for Structured Data (2016, neutral): “Similar to kernel BP (Song et al., 2010, 2011) and kernel EP (Jitkrittum et al., 2015), our current work exploits feature space embedding to reformulate graphical model inference procedures.”
Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “Conditional mean embedding has enjoyed successful applications in graphical models and probabilistic inference (Song et al. 2009; 2010a; 2011a;b; 2010b).”
Kernel-Based Just-In-Time Learning for Passing Expectation Propagation Messages (2015, background): “We note that Song et al. (2010, 2011) propose a related regression approach for predicting outgoing messages from incoming messages, for the purpose of belief propagation.”
Computing functions of random variables via reproducing kernel Hilbert space representations (2015, neutral): “h is that it allows us to apply RKHS methods to probability distributions, often with strong theoretical guarantees [44, 45]. It has been applied successfully in many domains such as graphical models [38, 39], two-sample testing [11], domain adaptation [16, 13, 23], and supervised learning on probab”
Kernel Mean Shrinkage Estimators (2014, methodology): “Second, basic operations on the distribution can be carried out by means of inner products in RKHS, e.g., EP[f(x)] = 〈f, µP〉H for all f ∈ H, which is an essential step in probabilistic inference (see, e.g., Song et al. (2011)).”
Characteristic Kernels and Infinitely Divisible Distributions (2014, methodology): “An important application will be the development of the semi-parametric kernel mean Bayesian inference, based on the currently developed full-nonparametric kernel mean Bayesian inference (Song et al., 2009, 2010, 2011; Fukumizu et al., 2013), by incorporating probabilistic models into them.”
Hilbert Space Embeddings of POMDPs (2012, methodology): “Recently, inference methods which make use of the embeddings have been proposed, including for Hidden Markov Models [Song et al., 2009, Song et al., 2010], and belief propagation [Song et al., 2010, Song et al., 2011].”
Modelling transition dynamics in MDPs with RKHS embeddings (2012, methodology): “These approaches have been particularly successful in performing inference in graphical models, where the model parameters are learned nonparametrically from data (Song et al., 2010b; 2009; 2011).”
Kernel Bayes' Rule (2010, methodology): “More recently, a method for belief propagation using kernel means was proposed [18, 19]: unlike the present work, this directly estimates conditional densities assuming the prior to be uniform.”
Provable Bayesian Inference via Particle Mirror Descent (2015, methodology): “[37] and [21, 25] extend the belief propagation algorithm with nonparametric models by kernel embedding and particle approximation, respectively.”
Kernel Embeddings of Conditional Distributions: A Unified Kernel Framework for Nonparametric Inference in Graphical Models (2013, methodology): “In this paper, we will review the recent development of nonparametric inference with kernel embeddings of conditional distributions [4, 5, 6, 7, 8, 9, 10, 11, 12], and provide a novel, unified kernel framework for addressing a broad class of challenging problems in graphical models.”
The Nonparametric Kernel Bayes Smoother (2016, methodology): “By applying the nonparametric kernel sum rule12 (Section 2 or Song et al. [25]) to m̂Xt|z1:T , we have m̂X̄t+1|z1:T = ÛX̄t+1|Xtm̂Xt|z1:T = l ∑ i=1 η (t+1) i kX (·, X̃ ′ i), where ÛX̄t+1|Xt is the nKSR operator to obtain the estimator m̂X̄t+1|z1:T .”
Recovering Distributions from Gaussian RKHS Embeddings (2014, background): “, 2011), belief propagation (Song et al., 2010; Song et al., 2011), predictive state representations (Boots et al.”
Monte Carlo Filtering Using Kernel Embedding of Distributions (2014, background): “…such as statistical testing (Gretton et al. 2012; 2008), time series analysis (Song et al. 2009; 2010; Fukumizu, Song, and Gretton 2011), belief propagation (Song, Gretton, and Guestrin 2010; Song et al. 2011), and reinforcement learning (Grünewälder et al. 2012b; Nishiyama et al. 2012).”
Robust Low Rank Kernel Embeddings of Multivariate Distributions (2013, methodology): “This new framework has led to many recent advances in machine learning such as kernel independence test [3] and kernel belief propagation [4].”
Path Integral Control by Reproducing Kernel Hilbert Space Embedding (2012, background): “However, these problems can be addressed with alternative estimators for U based on low rank approximations [Song et al., 2011] or importance sampling [Rawlik et al.”