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.
Consider the following dataset where the yellow and blue points are clearly not linearly separable in two dimensions.
If we could find a higher dimensional space in which these points were linearly separable, then we could do the following:
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.
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_1' + 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}$$
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.
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"
In the top answer to this question, there's a link to the lecture of Pr. Yaser Abu-Mostafa from CalTech and it gives a very nice intuition of it... so I'll try to explain what i understood, without equation:
Here's some words from the lecture:
Think of it this way. I am a guardian of the Z space. I'm closing the door. Nobody has access to the Z space.
You come to me with requests... If you give me an x and ask me, what is the transformation, that's a big demand. I have to hand you a big z. And I may not allow that.
But let's say that all I'm willing to give you are inner products. You give me x and x dash, I close the door, do my thing, and come back with a number, which is the inner product between z and z dash, without actually telling you what z and z dash were. That would be a simple operation.
And if you can get away with it, then that's a pretty good thing.
Selected parts of the lecture:
The kernel is a function that quantifies similarity between a pair of data points. And mathematically speaking this similarity can be computed using inner product, which has been explained beautifully in above answers. In RBF kernel it calculates this similarity between a landmark point and all other data points. How this landmark point is chosen is a different optimization problem all together. In support vector machines we find the decision boundary in higher dimension space without visiting it, with the help of a kernel. This decision boundary is linear is higher dimension space but when projected back on feature space it is curvy.
as was said in comments @ttnphns: "Dot product and projection are not quite identical." – kernel trick is utilized in computations involving the dot products (x, y). kernel itself programmically is just a core of a computer's OS, that controls & distributes "time" & "power" between CPU, RAM, Devices & etc. projection is builded Feature Map, as I understand.
In ML (SVM) Kernel replaces Euclidean Inner Product, that is the measure of similarity/dissimilarity. SVM maximizes the distance between closiest points while learning the Decision Boundary - the distance that is Euclidean distance here in Euclidean space. As so as space can be multidimensional => linear models don't always help (Lnear Regression & PCA), non-linearity (e.g. with cos in geometrical space) is added in calculations to add Geometrically-Weighted-Transformations. e.g. compare Linear Kernel vs. Cosine Kernel Inner_Product:
This is called cosine similarity, because Euclidean (L2) normalization projects the vectors onto the unit sphere, and their dot product is then the cosine of the angle between the points denoted by the vectors.
(or mathematically & ststistically - here - for the Cosine kernel defined by the pdf f(x)=(π/4)cos(xπ/2))
Important: see here
Types of SVM kernels Think of kernels as definned filters each for their own specific usecases.
1) Polynomial Kernels (used for image processing) 2) Gaussian Kernel (When there is no prior knowledge for data) 3) Gaussian Radial Basis Function(same as 2) 4) Laplace RBF Kernel ( recommend for higher training set more than million) 5) Hyperbolic Tangent Kernel (neural network based kernel) 6) Sigmoid Kernel(proxy for Neural network) 7) Anova Radial Basis Kernel (for Regression Problems)
be carefull: space can be non-Euclidean or pseudo-Euclidean or etc... your choice depends on the objectives of your research task, I think
P.S. So, defining either kernel (more precise here - certain kernel-trick) to use it in algorithm - you simply define certain type of decomposition to matrices & approximation-type for the learning, But as so as this essentially leads to certain working load for CPU & RAM (as so as the learning process is rather hardware resources consuming) - they called the parameter simply "kernel". (I think, it really is as simple as just the name meaning the direction of pc-resources distribution for certain type of derivation/approximation) - some answers here are helpful to distinguish OS-kernel & ML-kernel -- terms from different fields, but I think, are meaningfull in understanding how to calculate huge matrices rapidly (async), not waiting in the queue in iterating process (don't know how operational_system cope with recursion to improve memory/speed balance)
P.P.S. can see here a number of approaches where kernels are useful.
P.P.P.S. by the way, analysing data in time - Weighted Geometric Mean is often used
P.P.P.P.S. What function could be a kernel
