Source-linked AI summary
Kernel Interpolation for Scalable Structured Gaussian Processes (KISS-GP)
Andrew Gordon Wilson, Hannes Nickisch
TL;DR
Gaussian processes are expressive but computationally expensive at scale, while existing scalable approaches trade generality, inducing-point capacity, or grid requirements. The paper introduces SKI and KISS-GP, using local interpolation to combine inducing points with Toeplitz and Kronecker structure. KISS-GP improves accuracy and runtimes over popular alternatives, supports expressive kernel learning, and handles arbitrarily located inputs.
Problem
Gaussian processes have O(n^3) computation and O(n^2) storage costs, while existing inducing-point and grid-structured methods impose scalability, accuracy, or input-grid limitations.
Method
The paper introduces SKI, which forms scalable kernel approximations through interpolation, and KISS-GP, which uses local cubic or inverse-distance-weighting interpolation for sparse cross-covariances.
Results
KISS-GP combines with Toeplitz and Kronecker algebra, supports arbitrarily located inputs without grid data, and is orders of magnitude more accurate than alternatives at a given runtime.
Takeaways & Limitations
SKI provides a simple, general framework for scalable Gaussian-process methods with high accuracy and low computational costs, including expressive kernel learning.
Takeaways & Limitations
Interpolation approaches rely on smooth underlying kernels, and more expressive quasi-periodic kernels require more inducing points for good approximation.
Abstract
from arXiv · showhide
We introduce a new structured kernel interpolation (SKI) framework, which generalises and unifies inducing point methods for scalable Gaussian processes (GPs). SKI methods produce kernel approximations for fast computations through kernel interpolation. The SKI framework clarifies how the quality of an inducing point approach depends on the number of inducing (aka interpolation) points, interpolation strategy, and GP covariance kernel. SKI also provides a mechanism to create new scalable kernel methods, through choosing different kernel interpolation strategies. Using SKI, with local cubic kernel interpolation, we introduce KISS-GP, which is 1) more scalable than inducing point alternatives, 2) naturally enables Kronecker and Toeplitz algebra for substantial additional gains in scalability, without requiring any grid data, and 3) can be used for fast and expressive kernel learning. KISS-GP costs O(n) time and storage for GP inference. We evaluate KISS-GP for kernel matrix approximation, kernel learning, and natural sound modelling.
1 Introduction
GPs offer expressive, interpretable models but their O(n^3) computation and O(n^2) storage limit application to large datasets. SKI unifies inducing-point methods and, through KISS-GP, combines scalable interpolation with structure-exploiting algebra without requiring grid data.
- O(n^3) computation and O(n^2) storage restrict Gaussian processes to datasets containing at most a few thousand training points.
- Inducing-point methods reduce scaling costs but typically require m ≪ n inducing inputs, which can reduce predictive performance and limit expressive kernel learning.Their costs are O(m^2n + m^3) computations and O(mn + m^2) storage.
- Grid-based Kronecker methods support scalable inference and flexible kernel learning but require inputs on a multidimensional lattice, limiting general applicability.
- A naive grid placement of inducing points reduces only the m^3 term, not the more critical O(m^2n) cross-covariance cost.
- SKI interprets inducing-point methods as kernel interpolation and explains how inducing-point count, kernel choice, and interpolation strategy affect accuracy and efficiency.It also provides a framework for creating new inducing-point methods through alternative interpolation strategies.
- KISS-GP uses local cubic and inverse-distance-weighting interpolation to sparsify cross-covariances, while supporting Toeplitz and Kronecker algebra for further scalability.With Toeplitz structure, it requires O(n + m log m) computations and O(n + m) storage.
- KISS-GP lifts grid restrictions so arbitrarily located inputs can use Toeplitz or Kronecker structure, enabling expressive kernel learning and orders-of-magnitude gains over alternatives such as FITC.The paper reports improved accuracy and efficiency, and provides an implementation as a GPML toolbox extension.
2 Background
Gaussian processes offer expressive, interpretable covariance modeling but standard inference scales poorly, motivating inducing-point and structure-exploiting approximations. These approaches trade general applicability, grid requirements, accuracy, and computational cost in different ways.
- Inducing-point approximations: Inducing-point methods replace the exact kernel with an approximation, costing O(m^2n + m^3) computation and O(mn + m^2) storage.Practical efficiency generally requires m ≪ n, which can reduce predictive performance and limit expressive kernel learning.
- Inducing-point approximations: SoR produces a rank-at-most-m covariance matrix, whereas FITC adds a diagonal correction that yields a full-rank and more faithful approximation.Both approximate kernels are generated from the exact user-specified kernel and can be optimized for kernel learning.
- Kronecker methods: Kronecker methods exploit product kernels on Cartesian grids to accelerate eigendecompositions and matrix-vector products for scalable exact inference and learning.Their grid requirement makes them inapplicable to many datasets, although partial-grid extensions support some missing-data settings.
- Structure-exploiting methods: Kronecker inference and learning cost O(Pm^(1+1/P)) operations and O(Pm^(2/P)) storage, while Toeplitz methods use FFT-based products in O(m log m) operations and O(m) storage.Toeplitz structure applies to stationary kernels on regularly spaced one-dimensional grids.
- Kronecker methods: Partial-grid Kronecker extensions approximate the log-determinant term while retaining efficient matrix-vector products and inference through iterative methods.The eigenvalue approximation is asymptotically consistent when observed inputs are bounded by the complete grid.
3 Structured Kernel Interpolation
SKI approximates training–inducing cross covariances by interpolating on the inducing-point covariance matrix, making the interpolation weights sparse and enabling scalable kernel computations. With suitable inducing-point structure, SKI combines sparse interpolation with Kronecker or Toeplitz algebra while retaining arbitrary training inputs.
- Structured Kernel Interpolation: SKI approximates the n × m cross-covariance matrix by interpolating kernel values on the m × m inducing-point covariance matrix.For linear interpolation, each training point is bracketed by nearby inducing points and its covariance is formed from their weighted values.
- Structured Kernel Interpolation: Local cubic interpolation uses c = 4 non-zero weights per row, while inverse distance weighting uses c = 2 on general rectilinear grids.The sparse weight matrix W reduces the cost of multiplying by the interpolated cross-covariance matrix.
- Computational Structure: Kronecker structure reduces SKI matrix-vector products to O(Pm^(1+1/P)) computations and O(n + Pm^2) storage.This structure is created in the inducing-point covariance matrix, not assumed for the training inputs.
- Computational Structure: O(n + m log m) computations and O(n + m) storage are required for SKI matrix-vector products with Toeplitz structure.Without Toeplitz or Kronecker structure, the corresponding cost is O(n + m^2) computations and storage.
- Computational Structure: SKI inference and learning are accelerated over standard inducing-point approaches even without exploiting Toeplitz or Kronecker structure.Fast matrix-vector products support conjugate-gradient inference, while kernel-learning complexity is no greater than inference complexity.
- Accuracy and Scope: Interpolation quality depends on kernel smoothness, inducing-point count, and interpolation strategy; more expressive quasi-periodic kernels require more inducing points.KISS-GP combines GPs, sparse cubic interpolation, and Kronecker or Toeplitz algebra.
4 Experiments
The experiments evaluate SKI for covariance approximation and kernel learning, comparing interpolation strategies and scalable GP alternatives. Across these tests, local cubic interpolation supports accurate approximations and efficient learning with many inducing points.
- Experimental scope: The experiments cover kernel matrix approximation, kernel learning, and comparisons with FITC, SoR, and SSGPR.The study focuses on lower-dimensional problems to relax Kronecker and Toeplitz grid restrictions, using FITC as the primary inducing-point comparison.
- Covariance matrix reconstruction: A 1000 × 1000 RBF covariance matrix with unstructured inputs was almost indistinguishable from its SKI reconstruction using local cubic interpolation and m = 40 points.The approximation was generally accurate, with greatest precision near the matrix diagonal and outer edges.
- Covariance matrix reconstruction: Cubic interpolation is significantly more accurate than linear interpolation for small m, while k-means placement improves regular-grid linear interpolation but becomes less important as m increases.Except for small m, regular-grid cubic interpolation generally outperforms inverse-distance weighting with k-means.
- Covariance matrix reconstruction: For very small m ≪n, global GP interpolation is more accurate, but local cubic interpolation is more efficient and its accuracy gap quickly shrinks as m increases.At m = 150, SKI with cubic interpolation and SoR have similarly small reconstruction errors, with qualitatively different error concentration.
- Covariance matrix reconstruction: KISS-GP compares approximations at matched runtime, where local cubic interpolation is evaluated against SoR and FITC for m ∈[500, 2000].This experiment measures covariance construction rather than inference and does not yet exploit Kronecker or Toeplitz structure.
5 Discussion
The discussion presents SKI as a unifying framework that turns interpolation choices into scalable GP methods. KISS-GP combines local cubic interpolation with Kronecker and Toeplitz algebra while supporting arbitrarily located inputs.
- Framework: SKI generalises and unifies inducing point methods by interpreting them as kernel approximations formed through global GP interpolation.Changing the interpolation strategy yields new inducing-point methods, including KISS-GP with local cubic interpolation.
- Scalability: KISS-GP naturally combines with Kronecker and Toeplitz algebra, relaxing their grid assumptions to arbitrarily located inputs.This combination provides additional scalability while retaining the applicability of inducing-point methods.
- Empirical consequences: KISS-GP handles many inducing points efficiently, enabling expressive kernel learning and improved predictive accuracy and runtimes over popular alternatives.The discussion reports that, for any given runtime, KISS-GP is orders of magnitude more accurate than the alternatives.
- Future directions: The framework opens research directions involving new interpolation-based GP models, stochastic variational inference, and unified Kronecker-Toeplitz methods.The authors state that they have only begun exploring the possibilities of SKI.