Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

1 Answer

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.