Many machine learning classifiers (e.g. support vector machines) allow one to specify a kernel. What would be an intuitive way of explaining what a kernel is?

One aspect I have been thinking of is the distinction between linear and non-linear kernels. In simple terms, I could speak of 'linear decision functions' an 'non-linear decision functions'. However, I am not sure if calling a kernel a 'decision function' is a good idea.

Suggestions?

Kernel is a way of computing the dot product of two vectors $\mathbf x$ and $\mathbf y$ in some (possibly very high dimensional) feature space, which is why kernel functions are sometimes called "generalized dot product".

Suppose we have a mapping $\varphi \, : \, \mathbb R^n \to \mathbb R^m$ that brings our vectors in $\mathbb R^n$ to some feature space $\mathbb R^m$. Then the dot product of $\mathbf x$ and $\mathbf y$ in this space is $\varphi(\mathbf x)^T \varphi(\mathbf y)$. A kernel is a function $k$ that corresponds to this dot product, i.e. $k(\mathbf x, \mathbf y) = \varphi(\mathbf x)^T \varphi(\mathbf y)$.

Why is this useful? Kernels give a way to compute dot products in some feature space without even knowing what this space is and what is $\varphi$.

For example, consider a simple polynomial kernel $k(\mathbf x, \mathbf y) = (1 + \mathbf x^T \mathbf y)^2$ with $\mathbf x, \mathbf y \in \mathbb R^2$. This doesn't seem to correspond to any mapping function $\varphi$, it's just a function that returns a real number. Assuming that $\mathbf x = (x_1, x_2)$ and $\mathbf y = (y_1, y_2)$, let's expand this expression:

$\begin{align} k(\mathbf x, \mathbf y) & = (1 + \mathbf x^T \mathbf y)^2 = (1 + x_1 \, y_1 + x_2 \, y_2)^2 = \\ & = 1 + x_1^2 y_1^2 + x_2^2 y_2^2 + 2 x_1 y_1 + 2 x_2 y_2 + 2 x_1 x_2 y_1 y_2 \end{align}$

Note that this is nothing else but a dot product between two vectors $(1, x_1^2, x_2^2, \sqrt{2} x_1, \sqrt{2} x_2, \sqrt{2} x_1 x_2)$ and $(1, y_1^2, y_2^2, \sqrt{2} y_1, \sqrt{2} y_2, \sqrt{2} y_1 y_2)$, and $\varphi(\mathbf x) = \varphi(x_1, x_2) = (1, x_1^2, x_2^2, \sqrt{2} x_1, \sqrt{2} x_2, \sqrt{2} x_1 x_2)$. So the kernel $k(\mathbf x, \mathbf y) = (1 + \mathbf x^T \mathbf y)^2 = \varphi(\mathbf x)^T \varphi(\mathbf y)$ computes a dot product in 6-dimensional space without explicitly visiting this space.

Another example is Gaussian kernel $k(\mathbf x, \mathbf y) = \exp\big(- \gamma \, \|\mathbf x - \mathbf y\|^2 \big)$. If we Taylor-expand this function, we'll see that it corresponds to an infinite-dimensional codomain of $\varphi$.

Finally, I'd recommend an online course "Learning from Data" by Professor Yaser Abu-Mostafa as a good introduction to kernel-based methods. Specifically, lectures "Support Vector Machines", "Kernel Methods" and "Radial Basis Functions" are about kernels.

  • 8
    That's what I called intuitive... not! – user11081980 Sep 16 '17 at 21:59
  • +1. It's a matter of aesthetics. I've always found this angle more intuitive than the highfalutin gobbledygook visual explanation. – user603 Jul 8 at 10:34
  • Current tag definition: "Intuitive: questions that seek a conceptual or non-mathematical understanding of statistics." No clear indication whether conceptual is treated as a synonym of non-mathematical. – rolando2 Jul 8 at 15:58

A very simple and intuitive way of thinking about kernels (at least for SVMs) is a similarity function. Given two objects, the kernel outputs some similarity score. The objects can be anything starting from two integers, two real valued vectors, trees whatever provided that the kernel function knows how to compare them.

The arguably simplest example is the linear kernel, also called dot-product. Given two vectors, the similarity is the length of the projection of one vector on another.

Another interesting kernel examples is Gaussian kernel. Given two vectors, the similarity will diminish with the radius of $\sigma$. The distance between two objects is "reweighted" by this radius parameter.

The success of learning with kernels (again, at least for SVMs), very strongly depends on the choice of kernel. You can see a kernel as a compact representation of the knowledge about your classification problem. It is very often problem specific.

I would not call a kernel a decision function since the kernel is used inside the decision function. Given a data point to classify, the decision function makes use of the kernel by comparing that data point to a number of support vectors weighted by the learned parameters $\alpha$. The support vectors are in the domain of that data point and along the learned parameters $\alpha$ are found by the learning algorithm.

  • Dot product and projection are not quite identical. – ttnphns May 18 '15 at 21:18
  • In the case of SVM, I believe that kernels are distance measures in different spaces. This is in keeping with the idea that a SVM generalizes a support vector classifier. In general, kernels can be more complicated. – aginensky May 20 '15 at 2:56

A visual example to help intuition

Consider the following dataset where the yellow and blue points are clearly not linearly separable in two dimensions.

enter image description here

If we could find a higher dimensional space in which these points were linearly separable, then we could do the following:

  • Map the original features to the higher, transformer space (feature mapping)
  • Perform linear SVM in this higher space
  • Obtain a set of weights corresponding to the decision boundary hyperplane
  • Map this hyperplane back into the original 2D space to obtain a non linear decision boundary

There are many higher dimensional spaces in which these points are linearly separable. Here is one example

$$ x_1, x_2 : \rightarrow z_1, z_2, z_3$$ $$ z_1 = \sqrt{2}x_1x_2 \ \ z_2 = x_1^2 \ \ z_3 = x_2^2$$

This is where the Kernel trick comes into play. Quoting the above great answers

Suppose we have a mapping $\varphi \, : \, \mathbb R^n \to \mathbb > R^m$ that brings our vectors in $\mathbb R^n$ to some feature space $\mathbb R^m$. Then the dot product of $\mathbf x$ and $\mathbf y$ in this space is $\varphi(\mathbf x)^T \varphi(\mathbf y)$. A kernel is a function $k$ that corresponds to this dot product, i.e. $k(\mathbf x, > \mathbf y) = \varphi(\mathbf x)^T \varphi(\mathbf y)$

If we could find a kernel function that was equivalent to the above feature map, then we could plug the kernel function in the linear SVM and perform the calculations very efficiently.

Polynomial kernel

It turns out that the above feature map corresponds to the well known polynomial kernel : $K(\mathbf{x},\mathbf{x'}) = (\mathbf{x}^T\mathbf{x'})^d$. Let $d = 2$ and $\mathbf{x} = (x_1, x_2)^T$ we get

\begin{aligned} k(\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \begin{pmatrix} x_1' \\ x_2' \end{pmatrix} ) & = (x_1x_2' + x_2x_2')^2 \\ & = 2x_1x_1'x_2x_2' + (x_1x_1')^2 + (x_2x_2')^2 \\ & = (\sqrt{2}x_1x_2 \ x_1^2 \ x_2^2) \ \begin{pmatrix} \sqrt{2}x_1'x_2' \\ x_1'^2 \\ x_2'^2 \end{pmatrix} \end{aligned}

$$ k(\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \begin{pmatrix} x_1' \\ x_2' \end{pmatrix} ) = \phi(\mathbf{x})^T \phi(\mathbf{x'})$$

$$ \phi(\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}) =\begin{pmatrix} \sqrt{2}x_1x_2 \\ x_1^2 \\ x_2^2 \end{pmatrix}$$

Visualizing the feature map and the resulting boundary line

  • Left hand side plot shows the points plotted in the transformed space together with the SVM linear boundary hyper plane
  • Right hand side plot shows the result in the original 2-D space

enter image description here


Source

Very simply (but accurately) a kernel is a weighing factor between two sequences of data. This weighing factor can assign more weight to one "data point" at one "time point" than the other "data point", or assign equal weight or assign more weight to the other "data point" and so on.

This way the correlation (dot product) can assign more "importance" at some points than others and thus cope for non-linearities (e.g non-flat spaces), additional information, data smoothing and so on.

In still another way a kernel is a way to change the relative dimensions (or dimension units) of two data sequences in order to cope with the things mentioned above.

In a third way (related to the previous two), a kernal is a way to map or project one data sequence onto the other in 1-to-1 manner taking into account given information or criteria (e.g curved space, missing data, data re-ordering and so on). So for example a given kernel may stretch or shrink or crop or bend one data sequence in order to fit or map 1-to-1 onto the other.

A kernel can act like a Procrustes in order to "fit best"

  • I think you may be talking about kernels in the sense of kernel density estimation, not the positive-semidefinite Mercer kernels used in SVMs and related methods. – Dougal May 22 '15 at 5:30
  • @Dougal, in the sense of this answer the kernel is a weighing function or measure used to correlate data in a specific manner or to exploit certain data features, so SVM kernel methods are covered as well – Nikos M. May 22 '15 at 7:07

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.