TL;DR
This paper introduces Expectation Propagation (EP), a novel deterministic algorithm for approximate Bayesian inference in complex probabilistic models. EP unifies and extends existing methods like assumed-density filtering and loopy belief propagation, offering higher accuracy and broader applicability, especially for hybrid networks with both discrete and continuous variables.
What Problem Does This Paper Address?
Bayesian inference, while powerful, often involves computationally intractable integrals and sums, especially in models with many variables or complex dependencies (like loops in belief networks). This computational expense limits its practical application. Existing approximation methods, such as assumed-density filtering (ADF) and loopy belief propagation (LBP), have limitations: ADF is sequential and sensitive to data order, while LBP is restricted to discrete networks and can be slow to converge. The paper aims to bridge this gap by developing a more robust, accurate, and general approximation technique.
Methods
The core contribution is Expectation Propagation (EP). EP builds upon the idea of Assumed-Density Filtering (ADF), which approximates complex distributions with simpler ones (e.g., Gaussians) at each step. However, ADF's sequential nature discards information that might be crucial later. EP addresses this by introducing iterative refinement.
Here's how it works:
- Term Approximations: Instead of directly approximating the entire posterior distribution, EP approximates individual "terms" (e.g., factors in a graphical model, or conditional probability tables) within the model.
- Iterative Refinement: EP iteratively updates these term approximations. In each iteration, it removes one term's approximation from the current overall approximation, recomputes the posterior based on the remaining terms, and then re-approximates the removed term to match this new posterior. This process is repeated until the approximations stabilize.
- Unification: EP is shown to unify ADF (when no refinement is done) and loopy belief propagation (when the approximation is a completely disconnected network).
- Applicability: EP is particularly well-suited for hybrid networks (containing both discrete and continuous variables) because it can maintain expectations (like mean and variance) for continuous variables and can impose functional form constraints (like Gaussian distributions).
Datasets
The paper evaluates EP on two main problem types:
- Gaussian Mixture Model (Clutter Problem): This is a synthetic benchmark problem designed to test inference in a hybrid network with discrete (clutter vs. signal) and continuous (observation location) variables. The paper uses this to compare EP against Laplace's method, variational Bayes, importance sampling, and Gibbs sampling.
- Bayes Point Machine (BPM): This is a real-world application for linear classification. The paper uses standard datasets from the UCI repository (Heart, Thyroid, Ionosphere, Sonar) for evaluation, comparing EP against SVM, Billiard, TAP, and Mean-Field algorithms.
Key Insights and Ideas
- Iterative Refinement is Key: The core insight is that by iteratively refining term approximations, EP can overcome the sequential limitations of ADF and achieve higher accuracy. This allows information to propagate and be re-evaluated throughout the network.
- EP as a General Framework: EP provides a unifying perspective on several existing approximate inference techniques, showing how they can be seen as special cases of a more general iterative refinement process.
- Hybrid Network Power: EP's ability to handle hybrid networks by maintaining expectations (mean, variance) is a significant advantage over methods that are restricted to purely discrete or purely continuous domains.
- Fixed Points and Convergence: The paper proves that EP iterations always have a fixed point, which can be found by minimizing an energy function. This provides theoretical grounding for its convergence properties, although it notes that sometimes the approximating family might be a poor match, leading to convergence to an erroneous result (as seen in Figure 2).
Key Results
- Clutter Problem: EP significantly outperforms Laplace's method, variational Bayes, and Monte Carlo methods in terms of accuracy for a similar computational cost. It is shown to be more accurate than ADF by a constant factor (number of refinement passes).
- Bayes Point Machine: EP achieves comparable or better accuracy than other methods like Billiard and TAP, often with faster convergence or lower computational cost. For example, on the Sonar dataset, EP had lower average error than SVM.
- Convergence: EP iterations are shown to always have a fixed point. While convergence is generally good, the paper notes that in cases with complex posteriors (like Figure 2), EP might converge to a single mode when the true posterior is multimodal, a limitation shared by other deterministic methods.
Limitations and Future Work
- Approximating Family Choice: The performance of EP can depend on the choice of the approximating family. In cases where the approximating family is a poor match to the true posterior (e.g., multimodal posteriors), EP might converge to an erroneous result. The paper suggests that before considering alternate ways to carry out EP, one should reconsider the approximating family.
- Convergence to Suboptimal Fixed Points: While EP always converges to a fixed point, this fixed point might not always be the "best" one, especially if multiple fixed points exist. The paper mentions that minimizing an energy function can help select the best fixed point, or gradient descent can be used if canonical EP doesn't converge.
- Future Work: The paper suggests that EP can be extended to arbitrary inner product functions for applications like Gaussian process classifiers and Support Vector Machines, changing the running time complexity. It also notes that the algorithm can be extended to handle more complex networks.
Summary updated