Conditional Expectation Propagation

Zheng Wang, Shandian Zhe

Conditional Expectation Propagation: Accelerating Bayesian Inference via Taylor-Approximated Moments

In Bayesian machine learning, estimating posterior distributions is a fundamental challenge. Expectation Propagation (EP) has long been a favored algorithm for this task due to its balance of speed and accuracy. EP operates by approximating complex likelihood factors with simpler exponential family messages through iterative moment matching. However, for many modern, complex models—such as those involving tensor decompositions or logistic likelihoods—the required moment matching integrals are mathematically intractable. Practitioners are often forced to choose between slow numerical optimization (e.g., Laplace Propagation), expensive sampling methods, or labor-intensive manual approximations.

The CEP Framework

Conditional Expectation Propagation (CEP) addresses these limitations by introducing a "divide and conquer" strategy for moment matching. The method relies on three key innovations:

  1. Conditional Moment Matching: Instead of computing joint moments for all variables simultaneously, CEP calculates the conditional moments of a single variable while keeping others fixed. This reduction often allows for analytical solutions or efficient 1D numerical integration (quadrature).
  2. Taylor Approximations: To finalize message updates, CEP approximates the expectation of these conditional moments over the current beliefs of the remaining variables using first- or second-order Taylor expansions.
  3. Analytical Fixed-Point Iterations: By deriving analytical update formulas, CEP eliminates the need for internal optimization loops (such as L-BFGS used in Laplace Propagation), significantly reducing the per-iteration computational cost.

Experimental Evaluation

The authors evaluated CEP against standard EP, Variational Bayes (VB), Laplace Propagation (LP), and Importance Sampling (IS) across several domains, including classification tasks on UCI datasets, Bayesian tensor decomposition (Alog and Enron datasets), and large-scale streaming data using the DBLP bibliography dataset.

Key Results

CEP demonstrates a remarkable efficiency-accuracy trade-off. In Bayesian tensor decomposition tasks, CEP achieved over a 40x speedup compared to Laplace Propagation. On standard classification benchmarks, CEP-2 (using second-order expansions) matched the accuracy of standard EP and VB while being significantly faster to converge.

Convergence of KL divergence over time for various inference methods in Bayesian Logistic and Probit Regression.

As shown in the figure above, CEP variants (CEP-1 and CEP-2) reach low approximation error (measured by KL divergence) orders of magnitude faster than Laplace Propagation (LP) and Importance Sampling (IS). While standard EP is also fast, CEP provides a more general framework that is easier to apply to models where standard EP updates are unavailable.

In tensor decomposition, CEP not only improved speed but also enhanced robustness, outperforming state-of-the-art algorithms like CP-WOPT in terms of Root Mean Square Error (RMSE) and Area Under the Curve (AUC). For streaming applications, the CEP-based Assumed Density Filtering (ADF) approach scaled effectively with batch size, outperforming existing methods like POST.

Conclusion

Conditional Expectation Propagation offers a powerful alternative for Bayesian inference in complex models. By replacing intractable joint integrations with conditional moments and Taylor approximations, it provides a "plug-and-play" solution that is both faster and more flexible than traditional EP variants. Future work may extend this framework to even more complex architectures, such as Bayesian Neural Networks.

Summary updated

BibTeX
@inproceedings{wang2019conditional,
  author = {Zheng Wang and Shandian Zhe},
  title = {{Conditional Expectation Propagation}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=YMI986yLnq},
}
Figure