Structure Discovery in Nonparametric Regression through Compositional Kernel Search

Introduction

Kernel-based nonparametric models, such as support vector machines and Gaussian processes (s), have been one of the dominant paradigms for supervised machine learning over the last 20 years. These methods depend on defining a kernel function, $k(x,x^{\prime})$, which specifies how similar or correlated outputs $y$ and $y^{\prime}$ are expected to be at two inputs $x$ and $x^{\prime}$. By defining the measure of similarity between inputs, the kernel determines the pattern of inductive generalization.

Most existing techniques pose kernel learning as a (possibly high-dimensional) parameter estimation problem. Examples include learning hyperparameters (rasmussen38gaussian), linear combinations of fixed kernels (Bach_HKL), and mappings from the input space to an embedding space (salakhutdinov2008using).

However, to apply existing kernel learning algorithms, the user must specify the parametric form of the kernel, and this can require considerable expertise, as well as trial and error.

To make kernel learning more generally applicable, we reframe the kernel learning problem as one of structure discovery, and automate the choice of kernel form. In particular, we formulate a space of kernel structures defined compositionally in terms of sums and products of a small number of base kernel structures. This provides an expressive modeling language which concisely captures many widely used techniques for constructing kernels. We focus on Gaussian process regression, where the kernel specifies a covariance function, because the Bayesian framework is a convenient way to formalize structure discovery. Borrowing discrete search techniques which have proved successful in equation discovery (todorovski1997declarative) and unsupervised learning (grosse2012exploiting), we automatically search over this space of kernel structures using marginal likelihood as the search criterion.

We found that our structure discovery algorithm is able to automatically recover known structures from synthetic data as well as plausible structures for a variety of real-world datasets. On a variety of time series datasets, the learned kernels yield decompositions of the unknown function into interpretable components that enable accurate extrapolation beyond the range of the observations. Furthermore, the automatically discovered kernels outperform a variety of widely used kernel classes and kernel combination methods on supervised prediction tasks.

While we focus on Gaussian process regression, we believe our kernel search method can be extended to other supervised learning frameworks such as classification or ordinal regression, or to other kinds of kernel architectures such as kernel SVMs. We hope that the algorithm developed in this paper will help replace the current and often opaque art of kernel engineering with a more transparent science of automated kernel construction.

Expressing structure through kernels

Gaussian process models use a kernel to define the covariance between any two function values: ${\textrm{Cov}(y,y^{\prime})=k(x,x^{\prime})}$. The kernel specifies which structures are likely under the prior, which in turn determines the generalization properties of the model. In this section, we review the ways in which kernel familiesWhen unclear from context, we use ‘kernel family’ to refer to the parametric forms of the functions given in the appendix. A kernel is a kernel family with all of the parameters specified.can be composed to express diverse priors over functions.

There has been significant work on constructing kernels and analyzing their properties, summarized in Chapter 4 of (rasmussen38gaussian). Commonly used kernels families include the squared exponential (), periodic (), linear (), and rational quadratic () (see Figure 1 and the appendix).

Positive semidefinite kernels (i.e. those which define valid covariance functions) are closed under addition and multiplication. This allows one to create richly structured and interpretable kernels from well understood base components.