assume each hidden variable xi takes one of K discrete values
(|Xi| = K), so that messages and marginals can be represented
by K-dimensional vectors. The message update integral then
becomes a matrix–vector product, which in general requires
O(K2) operations. This variant of BP is sometimes called the
sum–product algorithm. 30
For graphical models with continuous hidden variables, closed-form evaluation of the BP update integral
is only possible when the posterior is jointly Gaussian.
The resulting Gaussian BP algorithm, which uses linear
algebra to update estimates of posterior mean vectors
and covariance matrices, generalizes Kalman smoothing
algorithms for linear dynamical systems. 2 More generally, a fixed K-point discretization sometimes leads to an
effective histogram approximation of the true continuous
beliefs. 13, 14 However, as K must in general grow exponentially with the dimension of Xi, computation of the discrete messages underlying such approximations can be
extremely demanding.
2. 3. monte carlo methods
By using random samples to simulate probabilistic models,
Monte Carlo methods3 provide flexible alternatives to variational methods like BP. Given a target distribution p(x | y),
many inference tasks can be expressed via the expected
value Ep[ f (x)] of an appropriately chosen function. Given L
independent samples from p(x | y), the desired statistic can be approximated as follows:
This estimate is unbiased, and converges to Ep[ f (x)] almost
surely as L → ∞. For the graphical models of interest here,
however, exact sampling from p(x | y) is intractable.
2. 4. Particle filters
Our approach is inspired by particle filters, an approximate
inference algorithm specialized for hidden Markov models
(HMMs). As depicted graphically in Figure 1, an HMM models a sequence of T observations y = {y1, …, y T} via a corresponding set of hidden states x:
Recognizing this factorization as a special case of the pairwise MRF of Equation 1, the “forward” BP messages passed
to subsequent time steps are defined via the recursion
For continuous Xt where this update lacks a closed form,
particle filters6, 11 approximate the forward BP messages
mt− 1, t(xt) via a collection of L weighted samples, or particles,
update the particle locations and weights via a single,
forward pass through the observations. A variety of proposal
distributions q(xt+ 1|xt, yt+ 1), which aim to approximate
p(xt+ 1|xt, yt+ 1), have been suggested. 6 For example, the
“bootstrap filter” samples , and incorporates
evidence via weights .
. Importance sampling is used to recursively
3. nonPaRametRic BP
Although particle filters can be adapted to an extremely wide
range of dynamical models and observation types, they are
specialized to the structure of temporal filtering problems.
Conversely, loopy BP can in principle be applied to graphs of
any structure, but is only analytically tractable when all hidden
variables are discrete or jointly Gaussian. In this section, we
describe an NBP algorithm26, 44 that generalizes sequential
Monte Carlo methods to arbitrary graphs. As in regularized
particle filters, 11 we approximate the true BP messages and
beliefs by nonparametric density estimates. Importance
sampling and MCMC approximations then update these
sample-based messages, propagating information from local
observations throughout the graph.
3. 1. nonparametric representations