Abstract: The Gaussian process (GP) is a simple yet powerful probabilistic framework for various machine learning tasks. However, exact algorithms for learning and prediction are prohibitive to be applied to large datasets due to inherent computational complexity. To overcome this main limitation, various techniques have been proposed, and in particular, local GP algorithms that scale “truly linearly” with respect to the dataset size. In this paper, we introduce a hierarchical model based on local GP for large-scale datasets, which stacks inducing points over inducing points in layers. By using different kernels in each layer, the overall model becomes multi-scale and is able to capture both long- and short-range dependencies. We demonstrate the effectiveness of our model by speed-accuracy performance on challenging real-world datasets.
Introduction: The Scalability Challenge
Gaussian Processes (GPs) are widely regarded as the "gold standard" for Bayesian non-parametric regression due to their high-quality predictions and integrated uncertainty estimates. However, their computational complexity is a significant bottleneck: exact GP inference scales at $O(N^3)$, where $N$ is the number of data points. This cubic scaling effectively limits exact GPs to datasets of a few thousand points.
Existing approximations generally fall into two categories:
- Global Inducing-Point Methods: These use a small set of $M$ "pseudo-data" points to summarize the entire dataset. While faster ($O(NM^2)$), they often produce "blurry" models that fail to capture sharp local variations.
- Local GP Methods: These partition the data into independent blocks. While they achieve linear scaling, they suffer from "seams" or discontinuities at block boundaries and cannot capture long-range dependencies because each block is isolated.
This paper introduces Hierarchically-partitioned Gaussian Process Approximation (HPGPA), a model designed to combine the speed of local methods with the global awareness of inducing-point methods.
Methods: A Hierarchy of Summaries
HPGPA utilizes a "hierarchy of summaries" to bridge the gap between local and global scales. The core architecture is a tree-based partition of the input space.
The Tree Structure and Inducing Points
As shown in the figure above, the input space is partitioned into a tree. Leaf nodes contain the raw data and a set of local inducing points. Each parent node then contains its own set of inducing points that summarize the inducing points of its children. This "inducing points over inducing points" structure allows information to propagate efficiently: data communicates upward to a root node that maintains a coarse global view, then back down to other branches.
Multi-scale Kernels
A critical innovation in HPGPA is the use of multi-scale kernels. Standard GPs use a single length-scale, which determines the range of a point's influence. HPGPA employs short length-scales at the bottom of the tree to capture fine-grained local noise and wiggles, and progressively longer length-scales toward the top to capture broad global trends. To maintain mathematical consistency across these scales, the authors utilize a convolution-based technique.
Efficient Inference
Inference is performed via an upward-downward message-passing algorithm, conceptually similar to Kalman filtering on trees. This ensures that the total computational cost remains linear, roughly $O(NL^2)$, where $L$ is the number of points per block.
Experimental Evaluation
The model was evaluated on two large-scale real-world datasets:
- Household Electric Power Consumption (UCI): A time-series dataset with >184,000 points. HPGPA achieved significantly lower standardized mean squared error (SMSE) than standard inducing-point methods (FITC) and previous tree-based methods (Tree-GP) while maintaining competitive computation times.
- UK Terrain Data (OS Terrain-50): A spatial dataset with 531,000 points. HPGPA successfully recovered sharp edges and broad slopes in missing regions. In contrast, global methods produced blurry results, and local methods created "sinkholes" in missing patches due to a lack of global context.
Key Insights and Conclusion
HPGPA demonstrates that hierarchical modeling is essential for scaling GPs to "Big Data" without sacrificing local detail or global consistency. By tying inducing points at boundaries, the model minimizes the discontinuities common in local GP methods. While some small jumps remain due to the mathematical complexity of multi-scale kernel integration, HPGPA represents a significant step forward in making high-fidelity Bayesian regression viable for datasets with hundreds of thousands of points. Future work may involve adapting the tree topology to the underlying data manifold or exploring deeper connections with Deep Gaussian Processes.
Summary updated