What is a kernel and what sets it apart from other functions

There seem to be many machine learning algorithms that rely on kernel functions. SVMs and NNs to name but two. So what is the definition of a kernel function and what are the requirements for it to be valid?

• I wouldn't say that NNs rely on kernel functions - they rely on a transfer function to achieve nonlinearity, but this is not the same thing as a kernel function – tdc Feb 16 '12 at 16:33

For x,y on S, certain functions K(x,y) can be expressed as an inner product (in usually a different space). K is often referred to as a kernel or a kernel function. The word kernel is used in different ways throughout mathematics, but this is the most common usage in machine learning.

The kernel trick is a way of mapping observations from a general set S into an inner product space V (equipped with its natural norm), without ever having to compute the mapping explicitly, in the hope that the observations will gain meaningful linear structure in V. This is important in terms of efficiency (computing dot products in a very high dimensional space very quicky) and practicality (we can convert linear ML algorithms to non-linear ML algorithms).

For a function K to be considered a valid kernel it has to satisfy Mercer's conditions. This in practical terms means that we need to ensure the kernel matrix (computing the kernel product of every datapoint you have) will always positive semi-definite. This will ensure that the training objective function is convex, a very important property.

• Thanks @carlosdc, but I am afraid that you're trying to teach this old dog, new tricks. A lot of that is way over my head. I read Mercer's conditions, but their meaning in the real world is lost on me. I assume from the above that the integral of a kernel must be constrained to a finite value. Is that assumption correct? – Oswy Feb 18 '12 at 11:44
• The part that the objective is convex if the kernel matrix is PSD depends on the objective. This is true for SVMs, but with Gaussian processes the point is that the Kernel matrix is a valid covariance matrix and thus invertible. – bayerj Sep 4 '12 at 7:45

From Williams, Christopher KI, and Carl Edward Rasmussen. "Gaussian processes for machine learning." the MIT Press 2, no. 3 (2006). Page 80.

kernel = a function of two arguments mapping a pair of inputs $x \in X$, $x' \in X$ into $\mathbb{R}$.

Also, kernel = kernel function.

Kernels used in machine learning algorithms typically satisfied more properties, such as being positive semidefinite.

Going to try for a less technical explanation.

First, start with the dot product between two vectors. This tells you how "similar" the vectors are. If the vectors represent points in your data set, the dot product tells you if they are similar or not.

But, in some (many) cases, the dot product is not the best metric of similarity. For example:

• Maybe points that have low dot products are similar for some other reasons.
• You may have data items that are not well represented as points.

So, instead of using the dot product, you use a "kernel" which is just a function that takes two points and gives you a measure of their similarity. I'm not 100% sure of what technical conditions a function must meet to technically be a kernel, but this is the idea.

One very nice thing is that the kernel can help you put your domain knowledge into the problem in the sense that you can say two points are the same because of xyz reason which comes form you knowing about the domain.