Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
I am rather new to the field of Gaussian processes and how they are being applied in machine learning. I keep reading and hearing about the covariance functions being the main attraction of these methods. So could anyone explain in an intuitive manner what is happening in these covariance functions?
Otherwise, if you could point out to a specific tutorial or document explaining them.
In loose terms, a kernel or covariance function $k(x, x^\prime)$ specifies the statistical relationship between two points $x, x^\prime$ in your input space; that is, how markedly a change in the value of the Gaussian Process (GP) at $x$ correlates with a change in the GP at $x^\prime$. In some sense, you can think of $k(\cdot, \cdot)$ as defining a similarity between inputs (*).
Typical kernels might simply depend on the Euclidean distance (or linear transformations thereof) between points, but the fun starts when you realize that you can do much, much more.
As David Duvenaud puts it:
Kernels can be defined over all types of data structures: Text, images, matrices, and even kernels. Coming up with a kernel on a new type of data used to be an easy way to get a NIPS paper.
For an easy overview of kernels for GPs, I warmly recommend his Kernel Cookbook and references therein.
(*) As @Dikran Marsupial notes, beware that the converse is not true; not all similarity metrics are valid kernels (see his answer).
As @lacerbi suggests a kernel function (or covariance function in a Gaussian Process setting) is essentially a similarity metric, so that the value of the kernel is high if the two input vectors are considered "similar" according to the needs of the application and lower if they are dissimilar. However not all similarity metrics are valid kernel functions. To be a valid kernel, the function must be interpretable as computing an inner product in some transformed feature space, i.e. $K(x, x') = \phi(x)\cdot\phi(x')$ where $\phi(\cdot)$ is a function that maps the input vectors into the feature space.
So why must the kernel be interpretable as an inner product in some feature space? The reason is that it is much easier to devise theoretical bounds on generalisation performance for linear models (such as logistic regression) than it is for non-linear models (such as a neural network). Most linear models can be written so that the input vectors only appear in the form of inner products. This means that we can build a non-linear model by constructing a linear model in the kernel feature space. This is a fixed transformation of the data, so all of the theoretical performance bounds for the linear model automatically apply to the new kernel non-linear model*.
An important point that is difficult to grasp at first is that we tend not to think of a feature space that would be good for our particular application and then design a kernel giving rise to that feature space. In general we come up with a good similarity metric and then see if it is a kernel (the test is straightforward, if any matrix of pairwise evaluations of the kernel function at points in general position is positive definite, then it is a valid kernel).
$^*$ Of course if you tune the kernel parameters to optimise generalisation performance, e.g. by minimising the cross-validation error, then it is no longer a fixed transformation, but one that has been learned from the data and much of the beautiful theory has just been invalidated. So in practice, while the the design of kernel methods has a lot of reassuring theory behind them, the bounds themselves generally don't apply to practical applications - but it is still reassuring as there are sound principles underpinning the model.
