Kernels are used as a computational “trick” to compute the dot product of two vectors in some new feature space. Kernels can be generally thought of as a measure of distance, and are denoted by $K(\vec{x}_1, \vec{x}_2)$. When we look at the dual formulation of the SVM problem, we see that our feature vectors are now isolated in a dot product. By switching out this dot product for the term $K(\vec{x}^i, \vec{x}^j)$, we can learn non-linear decision boundaries in our original feature space. 

For anyone studying math, notice how similar this is to the general notion of an inner-product, however be cautious because the kernel need-not be an inner product. 

We can also think of kernels as an *implicit* feature mapping. This is what is meant by a computational trick (see child node on "Proof of Quadratic Kernel" to see the relationship between one kernel and its *explicit* feature mapping). 


Kernels

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

When we kernelize our features, we are implicitly doing a feature mapping of the form $$f : \mathbb{R}^n \to \mathbb{R}^m$$. These mappings are similar to those used in GANs. When using feature mappings we explicitly compute $$f(\vec{x})$$ for each $$\vec{x}$$ in our feature space. 

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 feature space 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

Kernelization

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