Product Trees for Gaussian Process Covariance in Sublinear Time

David A. Moore, Stuart RussellWorkshops @ UAI 2013 · OpenReview

TL;DR

This paper introduces a novel "product tree" data structure that dramatically speeds up the computation of Gaussian Process (GP) predictive variances, a critical bottleneck in complex Bayesian models. By efficiently approximating the covariance calculations, this method enables GPs to be used in larger, more complex models and for datasets with longer-scale variations, which was previously computationally prohibitive.

What Problem Does This Paper Address?

Gaussian Processes (GPs) are powerful tools for probabilistic modeling, offering a flexible way to capture uncertainty in predictions. However, a major hurdle to their widespread adoption in large-scale Bayesian models is their computational cost. Specifically, calculating the predictive variance for a standard GP model requires O(n²) time, where 'n' is the number of training data points. This quadratic complexity makes it infeasible to use GPs within the inner loops of computationally intensive inference procedures like Markov Chain Monte Carlo (MCMC), especially when dealing with large datasets or models that need to capture both short- and long-range dependencies in the data. Existing methods often focus on speeding up the predictive mean or are restricted to GPs with short lengthscales, limiting their applicability to data with longer-scale variations.

Methods

The core innovation of this paper is the development of a "product tree" data structure. This tree is built not on individual data points, but on pairs of training points. The key idea is to efficiently compute a weighted sum that represents the predictive covariance. Instead of calculating this sum naively (which takes O(n²) time), the product tree allows for an approximation.

Here's a breakdown of the approach:

  • Product Space and Metric: The method operates on a "product space" of pairs of training points (M x M). A specific "product metric" is defined for this space, which, for certain common kernels like the Squared Exponential (SE) kernel, has a fortunate property: the product of two kernel evaluations on individual points is equal to the kernel evaluation on the product metric of their pairs. For kernels where this exact property doesn't hold, the paper proposes using upper and lower bounds on the kernel product.
  • Tree Construction: A metric tree (specifically, a cover tree is used in their implementation) is built on this product space. Each node in the tree represents a cluster of pairs of training points. The tree is augmented with cached sums of the inverse kernel matrix entries (K⁻¹) within each node's subtree.
  • Recursive Computation: A recursive algorithm, WEIGHTEDMETRICSUM, traverses the product tree. At each node, it uses bounds on the weights and cached sums to decide whether to descend further or to approximate the contribution of that subtree. This allows for adaptive computation, focusing computational effort on pairs of points that are most relevant to the query.
  • Primal/Dual Models: The authors extend their product tree approach to "mixed primal/dual" GP models. These models combine a parametric component (e.g., a polynomial) for capturing long-scale structure with a nonparametric GP component for local variations. This allows for efficient modeling of global trends while retaining the flexibility of GPs for local details.

Datasets

  • Synthetic Dataset: A simple two-dimensional synthetic dataset was used for evaluation, with points sampled uniformly from the unit square. This dataset allowed for systematic comparison of different approaches to calculating GP variance.
  • Seismic Event Data: Amplitude data from 3105 seismic events detected at Fitzroy Crossing, Australia, was used. The task involved predicting event amplitude based on latitude, longitude, and depth, using great-circle distance as the metric. This dataset is noted for potentially containing both global trends and local structure.

Key Insights and Ideas

  • Pairs, Not Points: The most significant insight is shifting the focus from individual data points to pairs of points for covariance approximation. This directly addresses the O(n²) complexity of covariance calculations.
  • Product Tree for Efficiency: Building a tree structure on the product space of point pairs is a clever way to exploit geometric relationships and enable sublinear time complexity for covariance computations.
  • Adaptive Cutoff Rule: The proposed cutoff rule for the recursive algorithm, which considers both the running weighted sum and the magnitude of the inverse kernel entries, is crucial for balancing accuracy and speed.
  • Bridging Long and Short Scales: The extension to mixed primal/dual models is a powerful idea, demonstrating how to combine the efficiency of parametric models for global structure with the flexibility of GPs for local details, a common challenge in real-world data.
  • Kernel Properties Matter: The paper highlights how specific kernel properties (like the SE kernel's behavior with the product metric) simplify the approach, while also providing strategies (bounds) for more general kernels.

Key Results

  • Sublinear Time Complexity: The product tree method achieves predictive variance computation in sublinear time with respect to the number of training points (n), a significant improvement over the standard O(n²) complexity.
  • Significant Speedups: Empirical results on both synthetic and real-world seismic data demonstrate substantial speedups compared to dense and sparse matrix-based methods. For instance, on a large sparse dataset, runtimes grew from 0.08ms to 0.13ms as 'n' increased from 1000 to 200,000.
  • Accuracy Maintained: The product tree approach achieves this speedup with minimal loss in accuracy, often less than 0.1% error compared to exact calculations.
  • Effective Mixed Models: The mixed primal/dual GP models, when combined with the product tree, showed accuracy comparable to more complex models but with significantly faster variance calculations, particularly on the seismic dataset.

Limitations and Future Work

  • Kernel Matrix Inversion: A limitation acknowledged is the need to explicitly invert the kernel matrix (K) during training. This can still be computationally expensive for very large datasets.
  • Cutoff Rule Optimization: The authors suggest further investigation into the cutoff rules for the weighted sum recursion, including theoretical analysis and empirical studies of different rules.
  • Extension to Higher Dimensions: While the use of cover trees (instead of k-d trees) theoretically allows for extension to higher dimensions, the authors note that for very high-dimensional data where manifolds are not present, other nearest-neighbor techniques might be superior. Adapting these to GP regression is presented as an interesting open problem.
  • Iterative Factorization: Future work could explore iterative factorization of the kernel matrix as an alternative to direct inversion, potentially alleviating the training bottleneck.

Summary updated

BibTeX
@inproceedings{moore2013product,
  author = {David A. Moore and Stuart Russell},
  title = {{Product Trees for Gaussian Process Covariance in Sublinear Time}},
  booktitle = {Workshops @ UAI},
  year = {2013},
  url = {https://openreview.net/forum?id=aO6aqvRF2YV},
}
Figure