Abstract
Training Gaussian process-based models typically involves an $O(N^3)$ computational bottleneck due to inverting the covariance matrix. Popular methods for overcoming this matrix inversion problem cannot adequately model all types of latent functions, and are often not parallelizable. However, judicious choice of model structure can ameliorate this problem. A mixture-of-experts model that uses a mixture of $K$ Gaussian processes offers modeling flexibility and opportunities for scalable inference. Our embarrassingly parallel algorithm combines low-dimensional matrix inversions with importance sampling to yield a flexible, scalable mixture-of-experts model that offers comparable performance to Gaussian process regression at a much lower computational cost.
Introduction
Gaussian Processes (GPs) are powerful non-parametric tools for Bayesian regression, offering elegant uncertainty quantification. However, their practical application is severely limited by the $O(N^3)$ complexity of covariance matrix inversion. Existing solutions generally fall into two categories: sparse methods and local methods. Sparse methods use inducing points to approximate the global GP, often failing to capture fine-grained local variations. Local methods partition data into independent blocks, which is computationally efficient but introduces discontinuities at boundaries and ignores long-range dependencies.
In "Embarrassingly Parallel Inference for Gaussian Processes," Zhang and Williamson propose the Importance Sampled Mixture of Experts (IS-MOE) to bridge this gap, providing a scalable framework that maintains the expressiveness of global GPs while leveraging parallel computing.
The IS-MOE Framework
The core of the proposed approach is to treat the data partitioning as a latent variable and use importance sampling to aggregate results from multiple random partitions. This avoids the "edge effects" common in fixed local partitioning schemes.
The IS-MOE algorithm follows four primary steps:
- Partitioning: Sample $J$ independent partitions of the input space using a Dirichlet mixture of Gaussians.
- Parallel Training: For each partition $j$, fit $K$ independent GP experts to the local clusters. This step is "embarrassingly parallel," as each partition and expert can be processed independently.
- Weighting: Calculate importance weights $w_j$ for each partition based on the marginal likelihood of the data under that specific split.
- Aggregation: Combine predictions from all $J$ partitions using the normalized importance weights.
For extremely large datasets, the authors introduce SA IS-MOE (Stochastic Approximation), which utilizes minibatches to estimate weights and parameters, further reducing the computational overhead to $O(JB^3/K^2)$.
Experimental Evaluation
The authors evaluated IS-MOE across various synthetic and real-world datasets, including mid-tropospheric CO2 measurements (AIRS dataset) and the Higgs-Boson dataset, which contains 1.1 million observations.
Key Results
- Uncertainty Quantification: IS-MOE significantly outperformed the Robust Bayesian Committee Machine (RBCM) in uncertainty estimation. While RBCM often exhibited overconfidence, IS-MOE's log-likelihood scores remained closer to the ground truth.
- Scalability and Accuracy: On the Higgs-Boson dataset, IS-MOE achieved superior AUC and log-likelihood compared to Stochastic Variational Inference (SVI). The algorithm processed the million-point dataset in approximately six minutes on a standard cluster.
- Non-Stationarity: By allowing local experts to have independent hyperparameters, IS-MOE naturally models non-stationary data where behavior varies across the input space.
Conclusion
IS-MOE provides a robust framework for scaling Gaussian Processes to massive datasets without sacrificing the benefits of global modeling. By leveraging importance sampling over random partitions, the method smooths out local discontinuities and enables efficient parallelization. Future work includes extending this framework to Deep Gaussian Processes and further optimizing performance via GPU acceleration.
Summary updated