Kernel Belief Propagation

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.

References in corpus (2)

• Loopy Belief Propagation for Approximate Inference: An Empirical Study
• Multi-Label Prediction via Compressed Sensing

Cited by in corpus (22)

• Discriminative Embeddings of Latent Variable Models for Structured Data
• Kernel Mean Embedding of Distributions: A Review and Beyond
• Learning Decentralized Controllers for Robot Swarms with Graph Neural Networks
• A Survey on The Expressive Power of Graph Neural Networks
• Modelling transition dynamics in MDPs with RKHS embeddings
• Kernel Mean Shrinkage Estimators
• Belief Propagation for Continuous State Spaces: Stochastic Message-Passing with Quantitative Guarantees
• Finite sample properties of parametric MMD estimation: robustness to misspecification and dependence
• Hilbert Space Embeddings of POMDPs
• Path Integral Control by Reproducing Kernel Hilbert Space Embedding
• Rethink Maximum Mean Discrepancy for Domain Adaptation
• Nonparametric Detection of Geometric Structures over Networks
• MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means
• A Unified Joint Maximum Mean Discrepancy for Domain Adaptation
• Characteristic Kernels and Infinitely Divisible Distributions
• Modeling transition dynamics in MDPs with RKHS embeddings of conditional distributions
• NF-iSAM: Incremental Smoothing and Mapping via Normalizing Flows
• Pull Message Passing for Nonparametric Belief Propagation
• A Kernel-Based Nonparametric Test for Anomaly Detection over Line Networks
• Stochastic Belief Propagation: A Low-Complexity Alternative to the Sum-Product Algorithm
• Model-based Kernel Sum Rule: Kernel Bayesian Inference with Probabilistic Models
• Learning General Latent-Variable Graphical Models with Predictive Belief Propagation