In machine learning, the kernel trick is a method for easily converting a linear classifier algorithm into a non-linear one, by mapping the original observations into a higher-dimensional non-linear space so that linear classification in the new space is equivalent to non-linear classification in the original space.

This is done using Mercer's condition, which states that any positive semi-definite kernel K(x, y) can be expressed as a dot product in a high-dimensional space.

More specifically, if the arguments to the kernel are in a measurable space X, and if the kernel is positive semi-definite — i.e.

$\backslash sum\_\{i,j\}\; K(x\_i,x\_j)\; c\_i\; c\_j\; \backslash ge\; 0$

for any finite subset {x₁, ..., x_n} of X and subset {c₁, ..., c_n} of real numbers — then there exists a function φ(x) whose range is in an inner product space of possibly high dimension, such that

$K(x,y)\; =\; \backslash varphi(x)\backslash cdot\backslash varphi(y).$

The kernel trick transforms any algorithm that solely depends on the dot product between two vectors. Wherever a dot product is used, it is replaced with the kernel function. Thus, a linear algorithm can easily be transformed into a non-linear algorithm. This non-linear algorithm is equivalent to the linear algorithm operating in the range space of φ. However, because kernels are used, the φ function is never explicitly computed. This is desirable, because the high-dimensional space may be infinite-dimensional (as is the case when the kernel is a Gaussian).

The kernel trick was first published in the 1964 paper Theoretical foundations of the potential function method in pattern recognition learning.

It has been applied to several algorithms in machine learning and statistics, including:

• Support vector machines
• Principal components analysis
• Fisher's linear discriminant analysis

The coiner of the term kernel trick is unknown.

References

• M. Aizerman, E. Braverman, and L. Rozonoer. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25:821--837, 1964.

See also

• Integral transforms
• Hilbert space

Machine learning

Kernel (Maschinelles Lernen)