Abstract
Expectation propagation (EP) is a powerful approximate inference algorithm. However, a critical barrier in applying EP is that the moment matching in message updates can be intractable. Handcrafting approximations is usually tricky, and lacks generalizability. Importance sampling is very expensive. While Laplace propagation offers an excellent solution, it has to run numerical optimizations to find Laplace approximations in every update, which is still quite inefficient. To overcome these practical barriers, we propose conditional expectation propagation (CEP) that performs conditional moment matching given the variables outside each message fixed, and then takes expectation w.r.t their approximate posterior. The conditional moments are often analytical and much easier to derive. In the most general case, we can use (fully) factorized messages so that the conditional moments can be represented by quadrature formulas. We then compute the expectation of the conditional moments via Taylor approximations when necessary. In this way, our algorithm can always conduct efficient, analytical fixed point iterations. Experiments on several popular models for which standard EP is available or unavailable demonstrate the advantages of CEP in both inference quality and computational efficiency.
The Challenge of Moment Matching
Expectation Propagation (EP) is a cornerstone of Bayesian inference, prized for its balance of speed and accuracy. However, its reliance on moment matching—calculating the mean and variance of a "tilted distribution"—presents a significant computational hurdle. In many complex models, such as those involving logic functions or product terms, these moments are mathematically intractable.
Practitioners typically face three suboptimal choices: handcrafting model-specific approximations, using computationally grueling Importance Sampling (IS), or employing Laplace Propagation (LP). While LP is effective, it requires running numerical optimizations (like L-BFGS) for every single update, which becomes prohibitively slow for large-scale problems.
The CEP Framework
Conditional Expectation Propagation (CEP) addresses this bottleneck by decomposing the joint moment-matching problem into two manageable steps:
- Conditional Moment Matching: While joint moments may be intractable, conditional moments (fixing all but one variable) are often analytical or can be accurately approximated via simple one-dimensional quadrature (e.g., Gauss-Hermite).
- Expected Conditional Moments: CEP estimates the expectation of these conditional moments with respect to the other variables using first or second-order Taylor expansions around the current approximate posterior.
This approach transforms the projection step into a series of efficient, analytical fixed-point iterations. Unlike LP, which "hunts" for a mode using optimization, CEP leverages local geometric information to update beliefs directly, making it as general as sampling but as fast as standard EP.
Experimental Evaluation
The authors evaluated CEP against standard EP, LP, and IS across several domains, including Bayesian Probit and Logistic Regression on six real-world UCI datasets (australian, breast, crab, ionos, pima, sonar) and large-scale tensor decomposition tasks.
As illustrated in the runtime comparison, LP is consistently the slowest method across all datasets. CEP variants provide a much faster alternative, achieving over a 40x speedup in complex tasks like Bayesian tensor decomposition.
Key Results: Speed and Accuracy
The experimental results underscore CEP's dual advantages. In regression tasks, CEP's inference quality remained nearly identical to standard EP (where available) and proved much more stable than kernel-based predictors or Importance Sampling.
The convergence plots demonstrate that CEP-1 and CEP-2 reach the optimal KL divergence significantly faster than Laplace Propagation or Importance Sampling. This efficiency is particularly pronounced in high-dimensional settings where the overhead of numerical optimization in LP becomes a major bottleneck.
Conclusion
CEP provides a general-purpose framework for approximate inference that bypasses the primary weakness of standard EP. By substituting numerical optimization with analytical Taylor expansions of conditional moments, it offers a scalable solution for complex Bayesian models. Future work may explore its application to even more complex structures, such as Bayesian Neural Networks, where moment matching remains notoriously difficult.
Summary updated