Kernel Tricks

Kernel trick is a fundamental technique used in machine learning, especially in algorithms like Support Vector Machines (SVMs), to handle non-linear data by implicitly mapping it into a higher-dimensional space where linear classification or regression becomes possible. The key idea is to avoid the explicit computation of the mapping to higher dimension, by using kernel functions.

Feature Mapping

The general approach would be to mapp the input features into a higher-dimensional space using a mapping function. This transformation, however, can be computationally expensive, especially for large datasets or very high-dimensional spaces.

Kernel Trick

The kernel function computes the dot product between two data points $x_i$ and $x_j$, but rather than doing this in some explicit high-dimensional feature space, it computes it directly in the original input space. This avoids the computational complexity of transforming the data into the higher-dimensional space, making the algorithm much more efficient.

For many common transformations, there exists a kernel function that allows us to compute the dot product in the higher-dimensional space without every explicitly calculating the mapping.

Example of kernel function: Linear Kernel, Polynomial Kernel, RBF Kernel, etc.

Analogy

I would like to compare Linear kernel with neural network, where in the neural network the dot product between features and weights computes the linear combination of the input features where the weights transforms the input features.

The dot product between the input features and weights is similar to what happens with a linear kernel in SVM. In SVM, linear kernel computes the dot product between two input vectors. This computes a similarity measure between two data points, and the SVM learns a linear decision boundary based on this dot product. There are no additional transformations or layers in a basic linear SVM; it simply computes the dot product and creates a linear decision boundary.