Source-linked AI summary
Structure Discovery in Nonparametric Regression through Compositional Kernel Search
David Duvenaud, James Robert Lloyd, Roger Grosse, Joshua B. Tenenbaum, Zoubin Ghahramani
TL;DR
Choosing a kernel’s structural form requires expertise and trial and error in conventional nonparametric regression. The paper searches compositional sums and products of base kernels using a scientific-discovery-inspired procedure, finding interpretable structures that support time-series extrapolation and outperform varied kernel baselines on prediction tasks.
Problem
Users must specify the parametric kernel form, making kernel learning dependent on considerable expertise and trial and error.
Method
The method searches a space of Gaussian-process kernel structures composed from sums and products of a small number of base kernels, scoring structures with marginal likelihood.
Results
The method recovers known synthetic structures, finds plausible real-world structures, enables interpretable time-series extrapolation, and outperforms widely used kernel classes and combination methods.
Takeaways & Limitations
Learned kernels often decompose signals into diverse interpretable components, enabling human model-checking and accurate extrapolation on complex time series.
Takeaways & Limitations
The search space cannot parsimoniously represent some long-term lack of variation, although the learned kernel can retain periodic structure and express increasing long-term uncertainty.
Abstract
from arXiv · showhide
Despite its importance, choosing the structural form of the kernel in nonparametric regression remains a black art. We define a space of kernel structures which are built compositionally by adding and multiplying a small number of base kernels. We present a method for searching over this space of structures which mirrors the scientific discovery process. The learned structures can often decompose functions into interpretable components and enable long-range extrapolation on time-series datasets. Our structure search method outperforms many widely used kernels and kernel combination methods on a variety of prediction tasks.
1. Introduction
Kernel learning traditionally requires users to specify a parametric kernel form, often demanding expertise and trial and error. This paper reframes the task as automated structure discovery over compositional kernel forms and reports interpretable decompositions, extrapolation, and competitive prediction.
- Kernel functions define similarity between inputs, determining expected output correlations and the model’s inductive generalization pattern.
- Existing kernel-learning methods generally estimate parameters, combine fixed kernels, or learn embeddings after the kernel form is specified.
- The proposed method searches a compositional space formed by sums and products of a small set of base kernels, using Gaussian-process marginal likelihood.
- The algorithm recovers known synthetic structures, finds plausible real-world structures, and produces interpretable time-series decompositions supporting extrapolation beyond observations.
- Automatically discovered kernels outperform widely used kernel classes and kernel combination methods on supervised prediction tasks.
- The work focuses on Gaussian-process regression, while extension to classification, ordinal regression, and kernel SVMs remains prospective.
2. Expressing structure through kernels
The paper constructs expressive Gaussian-process priors by composing valid base kernels with addition and multiplication. These operations represent superposition and interaction, yielding interpretable structures for diverse functions and inputs.
- Gaussian-process kernels define covariance between function values and thereby specify which structures are likely under the prior.
- The kernel vocabulary includes squared exponential, periodic, linear, and rational quadratic families, with multidimensional kernels composed across input dimensions.
- Composing Kernels: Positive semidefinite kernels remain valid covariance functions under addition and multiplication, enabling richly structured and interpretable composite kernels.
- Summation: Summing kernels models superpositions of independent functions, including processes at different time scales and additive effects across dimensions.
- Multiplication: Multiplying kernels represents interactions between input dimensions or similarity notions; for example, Per × SE converts global periodicity into local periodicity.
- Composite kernels provide OR-like similarity through sums and AND-like similarity through products, allowing a few base kernels to capture complex relationships.
- Example expressions: The compositional language captures motifs including Bayesian linear regression, polynomial regression, generalized Fourier decompositions, generalized additive models, local deviations, and changing amplitude.
3. Searching over structures
The method searches algebraic kernel expressions by applying structure-motivated operators and selecting models with marginal likelihood. A greedy expansion strategy makes the search practical, but parameter optimization can encounter local optima.
- Kernel families are algebraic expressions combining SE, Per, Lin, and RQ base kernels through addition and multiplication.
- The search starts with every base kernel family on every input dimension and expands expressions using additive, multiplicative, and replacement operators.
- These operators can generate all algebraic expressions while allowing search paths more flexible than direct context-free-grammar derivations.
- At each stage, the greedy procedure expands the highest-scoring kernel using all possible operators.
- Search operators mirror scientific practice by adding residual structure, localizing globally assumed structure, and incrementally adding features.
- Scoring kernel families: Marginal likelihood balances model fit and complexity; kernel-family scores approximate parameter integration with BIC after maximum-likelihood optimization.
- Parameter optimization is nonconvex and may have local optima, including harmonic periods, so the procedure uses inherited initializations, conjugate gradients, and random restarts.
4. Related Work
Prior work addresses structured regression through additive, interaction-based, composite, embedding, and grammar-based models, while kernel learning often requires users to specify components or forms in advance.
- Nonparametric methods can struggle in high-dimensional spaces because they suffer from the curse of dimensionality and require additional model structure.
- Additive and interaction structures: Generalized additive models use sums of functions over individual dimensions, a structure mirrored by sums of base kernels across dimensions.
- Additive and interaction structures: Additive Gaussian processes and related spline-based models extend additive structure with products or higher-order interactions between dimensions.
- Composite models: Semiparametric regression combines an interpretable parametric component with a nonparametric component, represented here as SE + Lin.
- Kernel learning: Weighted-sum kernel methods are computationally efficient but require component kernels and hyperparameters to be specified in advance.
- Kernel learning: Embedding methods learn representations but may require costly generalization procedures or rely on structure in the input density rather than f(x).
- Structure discovery: Related grammar-based searches learn equations, graphs, or unsupervised structures, whereas this work searches covariance structures in supervised learning.
5. Structure discovery in time series
The method searches compositional kernel structures for time series and decomposes learned models into interpretable components. Across datasets, deeper searches improve extrapolation, while some unsupported patterns remain uncertain.
- The time-series experiments apply kernel search and visualize additive decompositions using base kernels searched to depth 10.
- Mauna Loa atmospheric CO2: The Mauna Loa model decomposes into a long-term trend, annual periodicity, and medium-term deviations, matching components selected by human experts.
- Mauna Loa atmospheric CO2: On Mauna Loa CO2 data, deeper searches improve extrapolation by adding structure beyond what a single base kernel can represent.
- Airline passenger data: The airline model captures a long-term trend, annual variation, short-term deviations, near-linearity, and linearly growing oscillation amplitude.
- Solar irradiance data: The solar irradiance analysis reports the learned kernel’s posterior and residuals, while the search space cannot parsimoniously represent a historical interval of little variation.
6. Validation on synthetic data
The method was tested on synthetic Gaussian-process data generated from known composite kernels across signal-to-noise ratios. It recovered nearly all relevant structure at the highest SNR and simplified models as noise increased.
- 300 noisy function samples were generated from Gaussian-process priors using several known composite kernel expressions and varying signal-to-noise ratios.The inputs were sampled uniformly, then independent Gaussian noise was added.
- Table 1 compares each true kernel with the structures selected by the search across input dimensionalities and signal-to-noise ratios.A dash denotes that modeling the data as i.i.d. Gaussian noise had the highest marginal likelihood.
- At the highest SNR, the method found all relevant structure in all but one test.An additional linear component was explainable by occasional near-linear trends in long-length-scale squared-exponential samples.
- As noise increased, the method generally selected simpler structures.
7. Quantitative evaluation
The quantitative evaluation measured extrapolation on airline time series and multidimensional prediction against fixed-kernel, additive, and kernel-search baselines. The discovered structures performed best across training-set sizes and narrowly outperformed the next-best method in every high-dimensional test.
- Extrapolation: On the airline dataset, extrapolation was evaluated with predictive MSE while training data increased from the first 10% to the first 90%.The training and test sets were contiguous.
- Extrapolation: SE-only and Per-only Gaussian-process models failed to capture long-term trends because marginal-likelihood-selected parameters captured only short-term structure.
- Extrapolation: The discovered full structures outperformed the other approaches for every evaluated training-set amount.Compared approaches included linear regression and Gaussian processes using fixed or richer kernel combinations.
- High-dimensional prediction: The high-dimensional comparison used 10-fold cross-validation on five datasets, reporting MSE and predictive likelihood for five methods.The datasets ranged from 4 to 13 dimensions and from 150 to 450 data points; structure search used depth 10 with SE and RQ bases.
- High-dimensional prediction: The comparison included Additive GPs, GAM, GP SE-ARD, HKL, and the proposed structure search.
- High-dimensional prediction: The proposed method outperformed the next-best method in every test, although the differences were not substantial.Table 2 marks results not significantly different from the best-performing method using a paired t-test with p-value 5%.
8. Discussion
The discussion frames kernel selection as structure discovery: compositional search mirrors scientific discovery and produces interpretable models. The authors report accurate extrapolation, competitive prediction, and possible extension beyond Gaussian-process regression.
- The paper introduces composite kernels formed by sums and products of a small number of base kernels, together with a scientific-discovery-style search procedure.The model space includes many standard regression models.
- Learned structures often extrapolate accurately on complex time series and remain competitive with widely used kernel classes and combination methods.
- The learned kernels often decompose signals into diverse, interpretable components, enabling human model-checking.
- The authors suggest that automated, data-driven kernel selection could make nonparametric regression and classification methods more accessible to non-experts.
Appendix
The appendix defines the base kernel families and gives an analytic identity for decomposing a Gaussian-process posterior into additive components.
- Kernel definitions: For scalar inputs, the appendix defines squared-exponential, periodic, linear, and rational-quadratic kernel families.
- Posterior decomposition: The posterior decomposition section gives an analytic conditional-Gaussian identity for decomposing a GP posterior over additive components.It considers f = f1 + f2 with Gaussian component distributions.