Sparse-posterior Gaussian Processes for general likelihoods

Yuan (Alan) Qi, Ahmed H. Abdel-Gawad, Thomas P. MinkaUAI 2010

TL;DR

This paper introduces SASPA, a novel framework for sparse Gaussian Processes (GPs) that significantly reduces computational cost for large datasets. By approximating the posterior distribution with a smooth basis and using expectation propagation, SASPA effectively handles general likelihoods, outperforming previous sparse GP methods in both regression and classification tasks.

What Problem Does This Paper Address?

Gaussian Processes (GPs) are powerful tools for modeling unknown functions in various machine learning tasks like regression and classification. However, their primary drawback is computational intractability for large datasets. Exact GP training scales cubically ($O(N^3)$) with the number of data points ($N$), making them impractical for real-world applications with millions of data points. Existing sparse GP methods attempt to alleviate this by using a smaller set of "basis points" or "pseudo-inputs" to approximate the full GP posterior. While successful for regression, these methods have been limited in their ability to handle general likelihood functions, especially for classification. This paper aims to bridge this gap by proposing a unified framework that can efficiently approximate GPs with arbitrary likelihoods.

Methods

The core contribution of this paper is the Sparse And Smooth Posterior Approximation (SASPA) framework. SASPA tackles the problem from a "posterior-approximation perspective," aiming to find a compact representation (using $M$ basis points, where $M \ll N$) such that the resulting approximate posterior distribution minimizes the divergence to the true posterior distribution. This minimization is achieved using Expectation Propagation (EP), a powerful approximate inference technique.

Key methodological aspects include:

  • Smooth Basis: Unlike previous methods that might treat basis points as discrete entities, SASPA "blurs" each basis point with a Gaussian distribution. This distribution has a full covariance matrix, allowing it to capture local data manifold information more effectively. This is a significant departure from methods that use spherical covariances or no blurring at all.
  • General Likelihoods: SASPA is designed to work with arbitrary likelihood functions, not just the Gaussian likelihood used in regression. This is achieved by using EP to approximate the posterior for general likelihoods.
  • Unified Framework: SASPA encompasses previous state-of-the-art sparse GP methods like SPGP and VSGP as special cases, demonstrating its generality.
  • EP Inference: The paper details the EP inference procedure for SASPA, including message deletion, projection, and update steps, adapted for the smooth basis approximation.

Datasets

The paper evaluates SASPA on:

  • Synthetic Data:
    • A toy regression problem involving sampling 100 data points along a circle.
  • A synthetic classification task where classes are sampled from multivariate Gaussian distributions.
  • UCI Benchmark Datasets:
    • Spambase
    • Ionosphere

The authors note that for sparse GP algorithms, they used K-means clustering to select basis points (cluster means) and their covariances. This is presented as a practical heuristic, acknowledging that learning these hyper-parameters in a principled way remains an open problem.

Key Insights and Ideas

  • Local Manifold Information is Crucial: The paper strongly emphasizes that using a richer approximating family, specifically by blurring basis points with full covariance matrices, significantly improves the approximation quality. This allows the model to capture local data structure more effectively than simpler approximations.
  • EP as a Unifying Tool: Expectation Propagation proves to be a versatile inference engine, enabling SASPA to handle general likelihoods and unify various sparse GP approaches.
  • SASPA as a Generalization: By framing the problem as posterior divergence minimization, SASPA naturally incorporates and extends prior work like SPGP and VSGP, demonstrating a more principled approach to sparse GP approximation.
  • Trade-off Between Approximation and Complexity: The number of basis points ($M$) offers a direct knob to control model complexity and computational cost, allowing for a tunable trade-off between accuracy and efficiency.

Key Results

  • Improved Approximation Quality: Experiments show that SASPA, particularly with full local covariance matrices, significantly improves the approximation quality of the posterior mean compared to simpler sparse GP methods (e.g., SPGP, FITC-EP) on both synthetic and real-world datasets. Figure 1 visually demonstrates this improvement on a circle dataset.
  • Competitive Classification Performance: SASPA achieves competitive or superior classification error rates on UCI datasets (Spambase, Ionosphere) compared to other sparse GP methods and IVM. Figure 4 and 5 illustrate these results.
  • Reduced Computational Cost: SASPA reduces the computational cost for training GPs from $O(N^3)$ to $O(M^2N)$, making it feasible for much larger datasets.
  • Effective Basis Point Selection: Using K-means for selecting basis points and their local covariances yields competitive results, suggesting that simple clustering can be an effective heuristic for hyperparameter tuning in this context.

Limitations and Future Work

  • Hyperparameter Learning: While K-means is shown to be effective for selecting basis centers and covariances, the paper acknowledges that learning these hyper-parameters in a principled and tractable way for sparse GPs with general likelihoods remains an open problem.
  • Online Learning: The paper mentions that the stagewise design of some previous methods hinders online learning, but SASPA's EP framework is presented as being more amenable to online learning, though a detailed online algorithm is not presented.
  • Model Selection: The paper notes that SASPA works for any choice of pseudo-inputs but doesn't specify how they should be chosen optimally beyond K-means. Learning these optimally to minimize KL divergence is an open challenge.

Summary updated

BibTeX
@inproceedings{qi2010sparse,
  author = {Yuan (Alan) Qi and Ahmed H. Abdel-Gawad and Thomas P. Minka},
  title = {{Sparse-posterior Gaussian Processes for general likelihoods}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2010},
}
Figure