Conditional Expectation Propagation

Zheng Wang, Shandian Zhe

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:

  1. 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).
  2. 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.

Comparison of running times across six UCI datasets. The cyan bars represent Laplace Propagation (LP), highlighting its significant computational overhead compared to the more efficient CEP variants.

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.

Convergence of KL divergence over time for simulated Probit (BPR) and Logistic Regression (BLR) tasks. CEP variants (black/red) converge to the same accuracy as standard EP (blue) but do so orders of magnitude faster than LP (cyan) or IS (yellow).

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

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.
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