A kernel is a function that computes the dot product of two vectors in a new, often higher-dimensional feature space without explicitly transforming the vectors into that space. This is known as the "kernel trick." A kernel function, commonly denoted by $$K(\vec{x}_1, \vec{x}_2)$$, acts as an implicit feature mapping and provides a measure of similarity or distance between inputs. In the dual formulation of Support Vector Machines (SVMs), replacing the standard dot product with $$K(\vec{x}^i, \vec{x}^j)$$ allows the model to efficiently learn non-linear decision boundaries in the original feature space. While closely related to the general notion of an inner product, a kernel need not strictly be an inner product.

Kernel Functions

Using the Dual formulation of SVM, we can define an implicit feature mapping with kernels. 

Lets talk about what a kernel is, then give a couple examples of popular kernels.

University of Michigan - Ann Arbor

An explicit feature mapping is a mathematical transformation of the form $$f : \mathbb{R}^n \to \mathbb{R}^m$$. When using explicit feature mappings, we compute $$f(\vec{x})$$ for each data point $$\vec{x}$$ in our feature space to project it into a new, typically higher-dimensional space where the data may become linearly separable. For example, if we are given the feature space $$\vec{x} = [x_1, x_2]^T \in \mathbb{R}^2$$, and we assume that our data is not linearly separable but is quadratically separable, we might define a feature mapping to be $$f: \mathbb{R}^2 \to \mathbb{R}^3$$ where $$f([x_1, x_2]^T) = [x_1^2, x_2^2, 1]^T$$.

Explicit Feature Mapping

When we beginning to kernelize the SVM, we have just got to do some calculus. When solving the soft-margin optimization problem we rely on something called a *Lagrangian*. Watch the despicably helpful khan academy video cited, take a look at the proof, convince yourself of it, then accept the new, *dual* formulation for the soft margin problem:

$$\max_{\alpha} - \frac{1}{2} 
\sum_{i,j=1}^n\alpha_i\alpha_jy^iy^j\vec{x}^i\cdot\vec{x}^j + \sum_{i=1}^n\alpha_i$$
$$\text{subject to } \alpha_i \geq 0 \ \ \forall i \\ \text{ and } \sum_{i=1}^n\alpha_iy^i = 0$$


Dual Formulation

James, G., Witten, D., Hastie, T., & Tibshirani, R. (2013). An introduction to statistical learning (Vol. 112, pp. 3-7). New York: springer.

An Introduction to Statistical Learning with Applications in R

Lagrangians are a tool for constrained optimization problems. Have a look at the video for an intuitive explanation: 

[www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/lagrange-multipliers-and-constrained-optimization/v/the-lagrangian](https://www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/lagrange-multipliers-and-constrained-optimization/v/the-lagrangian) 

Learn Before

Related

Learn After

Learn After

Related