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