I was reading about kernel PCA (1, 2, 3) with Gaussian and polynomial kernels.
How does the Gaussian kernel separate seemingly any sort of nonlinear data exceptionally well? Please give an intuitive analysis, as well as a mathematically involved one if possible.
What is a property of the Gaussian kernel (with ideal $\sigma$) that other kernels don't have? Neural networks, SVMs, and RBF networks come to mind.
I think the key to the magic is smoothness. My long answer which follows is simply to explain about this smoothness. It may or may not be an answer you expect.
Short answer:
Given a positive definite kernel $k$, there exists its corresponding space of functions $\mathcal{H}$. Properties of functions are determined by the kernel. It turns out that if $k$ is a Gaussian kernel, the functions in $\mathcal{H}$ are very smooth. So, a learned function (e.g, a regression function, principal components in RKHS as in kernel PCA) is very smooth. Usually smoothness assumption is sensible for most datasets we want to tackle. This explains why a Gaussian kernel is magical.
Long answer for why a Gaussian kernel gives smooth functions:
A positive definite kernel $k(x,y)$ defines (implicitly) an inner product $k(x,y)=\left\langle \phi(x),\phi(y)\right\rangle _{\mathcal{H}}$ for feature vector $\phi(x)$ constructed from your input $x$, and $\mathcal{H}$ is a Hilbert space. The notation $\left\langle \phi(x),\phi(y)\right\rangle $ means an inner product between $\phi(x)$ and $\phi(y)$. For our purpose, you can imagine $\mathcal{H}$ to be the usual Euclidean space but possibly with inifinite number of dimensions. Imagine the usual vector that is infinitely long like $\phi(x)=\left(\phi_{1}(x),\phi_{2}(x),\ldots\right)$. In kernel methods, $\mathcal{H}$ is a space of functions called reproducing kernel Hilbert space (RKHS). This space has a special property called ``reproducing property'' which is that $f(x)=\left\langle f,\phi(x)\right\rangle $. This says that to evaluate $f(x)$, first you construct a feature vector (infinitely long as mentioned) for $f$. Then you construct your feature vector for $x$ denoted by $\phi(x)$ (infinitely long). The evaluation of $f(x)$ is given by taking an inner product of the two. Obviously, in practice, no one will construct an infinitely long vector. Since we only care about its inner product, we just directly evaluate the kernel $k$. Bypassing the computation of explicit features and directly computing its inner product is known as the "kernel trick".
What are the features ?
I kept saying features $\phi_{1}(x),\phi_{2}(x),\ldots$ without specifying what they are. Given a kernel $k$, the features are not unique. But $\left\langle \phi(x),\phi(y)\right\rangle $ is uniquely determined. To explain smoothness of the functions, let us consider Fourier features. Assume a translation invariant kernel $k$, meaning $k(x,y)=k(x-y)$ i.e., the kernel only depends on the difference of the two arguments. Gaussian kernel has this property. Let $\hat{k}$ denote the Fourier transform of $k$.
In this Fourier viewpoint, the features of $f$ are given by $f:=\left(\cdots,\hat{f}_{l}/\sqrt{\hat{k}_{l}},\cdots\right)$. This is saying that the feature representation of your function $f$ is given by its Fourier transform divided by the Fourer transform of the kernel $k$. The feature representation of $x$, which is $\phi(x)$ is $\left(\cdots,\sqrt{\hat{k}_{l}}\exp\left(-ilx\right),\cdots\right)$ where $i=\sqrt{-1}$. One can show that the reproducing property holds (an exercise to readers).
As in any Hilbert space, all elements belonging to the space must have a finite norm. Let us consider the squared norm of an $f\in\mathcal{H}$:
$ \|f\|_{\mathcal{H}}^{2}=\left\langle f,f\right\rangle _{\mathcal{H}}=\sum_{l=-\infty}^{\infty}\frac{\hat{f}_{l}^{2}}{\hat{k}_{l}}. $
So when is this norm finite i.e., $f$ belongs to the space ? It is when $\hat{f}_{l}^{2}$ drops faster than $\hat{k}_{l}$ so that the sum converges. Now, the Fourier transform of a Gaussian kernel $k(x,y)=\exp\left(-\frac{\|x-y\|^{2}}{\sigma^{2}}\right)$
is another Gaussian where $\hat{k}_{l}$ decreases exponentially fast with $l$. So if $f$ is to be in this space, its Fourier transform must drop even faster than that of $k$. This means the function will have effectively only a few low frequency components with high weights. A signal with only low frequency components does not ``wiggle'' much. This explains why a Gaussian kernel gives you a smooth function.
Extra: What about a Laplace kernel ?
If you consider a Laplace kernel $k(x,y)=\exp\left(-\frac{\|x-y\|}{\sigma}\right)$, its Fourier transform is a Cauchy distribution which drops much slower than the exponential function in the Fourier transform of a Gaussian kernel. This means a function $f$ will have more high-frequency components. As a result, the function given by a Laplace kernel is ``rougher'' than that given by a Gaussian kernel.
What is a property of the Gaussian kernel that other kernels do not have ?
Regardless of the Gaussian width, one property is that Gaussian kernel is ``universal''. Intuitively, this means, given a bounded continuous function $g$ (arbitrary), there exists a function $f\in\mathcal{H}$ such that $f$ and $g$ are close (in the sense of $\|\cdot\|_{\infty})$ up to arbitrary precision needed. Basically, this means Gaussian kernel gives functions which can approximate "nice" (bounded, continuous) functions arbitrarily well. Gaussian and Laplace kernels are universal. A polynomial kernel, for example, is not.
Why don't we put the norm through, say, a Cauchy PDF and expect the same results?
In general, you can do anything you like as long as the resulting $k$ is positive definite. Positive definiteness is defined as $\sum_{i=1}^{N}\sum_{j=1}^{N}k(x_{i},x_{j})\alpha_{i}\alpha_{j}>0$ for all $\alpha_{i}\in\mathbb{R}$, $\{x_{i}\}_{i=1}^{N}$ and all $N\in\mathbb{N}$ (set of natural numbers). If $k$ is not positive definite, then it does not correspond to an inner product space. All the analysis breaks because you do not even have a space of functions $\mathcal{H}$ as mentioned. Nonetheless, it may work empirically. For example, the hyperbolic tangent kernel (see number 7 on this page)
$k(x,y) = tanh(\alpha x^\top y + c)$
which is intended to imitate sigmoid activation units in neural networks, is only positive definite for some settings of $\alpha$ and $c$. Still it was reported that it works in practice.
What about other kinds of features ?
I said features are not unique. For Gaussian kernel, another set of features is given by Mercer expansion. See Section 4.3.1 of the famous Gaussian process book. In this case, the features $\phi(x)$ are Hermite polynomials evaluated at $x$.
I will do my best to answer this question not because I'm an expert on the topic (quite the opposite), but because I'm curious about the field and the topic, combined with an idea that it could be a good educational experience. Anyway, here's the result of my brief amateur research on the subject.
TL;DR: I would consider the following passage from the research paper "The connection between regularization operators and support vector kernels" as the short answer to this question:
Gaussian kernels tend to yield good performance under general smoothness assumptions and should be considered especially if no additional knowledge of the data is available.
Now, a detailed answer (to the best of my understanding; for math details, please use references).
As we know, principal component analysis (PCA) is a highly popular approach to dimensionality reduction, alone and for subsequent classification of data: http://www.visiondummy.com/2014/05/feature-extraction-using-pca. However, in situations, when data carries non-linear dependencies (in other words, linearly inseparable), traditional PCA is not applicable (does not perform well). For those cases, other approaches can be used, and non-linear PCA is one of them.
Approaches, where PCA is based on using kernel function is usually referred to, using an umbrella term "kernel PCA" (kPCA). Using Gaussian radial-basis function (RBF) kernel is probably the most popular variation. This approach is described in detail in multiple sources, but I very much like an excellent explanation by Sebastian Raschka in this blog post. However, while mentioning the possibility of using kernel functions, other than Gaussian RBF, the post focuses on the latter due to its popularity. This nice blog post, introducing kernel approximations and kernel trick, mentions one more possible reason for Gaussian kernel popularity for PCA: infinite dimensionality.
Additional insights can be found in several answers on Quora. In particular, reading this excellent discussion reveals several points on potential reasons of Gaussian kernel's popularity, as follows.
Gaussian kernels are universal kernels i.e. their use with appropriate regularization guarantees a globally optimal predictor which minimizes both the estimation and approximation errors of a classifier.
The Gaussian RBF kernel is very popular and makes a good default kernel especially in absence of expert knowledge about data and domain because it kind of subsumes polynomial and linear kernel as well. Linear Kernels and Polynomial Kernels are a special case of Gaussian RBF kernel. Gaussian RBF kernels are non-parametric model which essentially means that the complexity of the model is potentially infinite because the number of analytic functions are infinite.
A Gaussian Kernel is just a band pass filter; it selects the most smooth solution. [...] A Gaussian Kernel works best when the infinite sum of high order derivatives converges fastest--and that happens for the smoothest solutions.
Finally, additional points from this nice answer:
NOTES:
The above-referenced point about Gaussian kernel being optimal choice, especially when there is no prior knowledge about the data, is supported by the following sentence from this CV answer:
In the absence of expert knowledge, the Radial Basis Function kernel makes a good default kernel (once you have established it is a problem requiring a non-linear model).
For those curious about non-essential differences between Gaussian RBF kernel and standard Gaussian kernel, this answer might be of interest: https://stats.stackexchange.com/a/79193/31372.
For those, interested in implementing kPCA for pleasure or business, this nice blog post might be helpful. It is written by one of the authors (creators?) of Accord.NET - a very interesting .NET open source framework for statistical analysis, machine learning, signal processing and much more.
Let me put in my two cents.
The way I think about Gaussian kernels are as nearest-neighbor classifiers in some sense. What a Gaussian kernel does is that it represents each point with the distance to all the other points in the dataset. Now think of classifiers with linear or polynomial boundaries, the boundaries are limited to certain shapes. However, when you look at nearest neighbor, the boundary can practically take any shape. That is I think why we think of Gaussian kernel also as non-parametric, i.e., adjusting the boundary depending on the data. Another way to think of that is the Gaussian kernel adjusts to the local shape in a region, similar to how a nearest neighbor locally adjusts the boundary by looking at the distance to other points in the local region.
I don't have a mathematical argument for this, but I think the fact that the Gaussian kernel in fact maps to an infinite dimensional space has something to do with its success. For the linear and polynomial kernels, the dot products are taken in finite dimensional spaces; hence it seems more powerful to do things in a larger space. I hope someone has a better grasp of these things. That also means that if we can find other kernels with infinite dimensional spaces, they should also be quite powerful. Unfortunately, I'm not familiar with any such kernel.
For your last point, I think Cauchy pdf or any other pdf that in some way measures the distance to other points should work equally well. Again, I don't have a good mathematical argument for it, but the connection to nearest neighbor makes this plausible.
Edit:
Here are some ideas on how to think of a classifier using Gaussian kernels as nearest-neighbor classifiers. First, let us think about what a nearest-neighbor classifier does. Essentially, a nearest neighbor classifier is a standard classifier that uses the distances between points as inputs. More formally, imagine we create a feature representation $\phi_i$ for each point $x_i$ in the dataset by calculating its distance to all the other points. $$\phi_i = (d(x_i,x_1), d(x_i, x_2), \ldots, d(x_i, x_n))$$ Above, $d$ is a distance function. Then what a nearest neighbor classifier does is to predict the class label for a point based on this feature representation and class labels for the data. $$ p_i = f(\phi_i, y) $$ where $p_i$ is the prediction for data point $x_i$ and $y$ is a vector of class labels for $x_1, x_2, \ldots, x_n$.
The way I think about kernels is that they do a similar thing; they create a feature representation of each point using its kernel values with other points in the dataset. Similar to the nearest neighbor case, more formally this would be $$ \phi_i = (k(x_i, x_1), k(x_i, x_2), \ldots, k(x_i, x_n)) $$ Now the connection with nearest neighbor is quite obvious; if our kernel function is some measure that is related to the distance measures we use in nearest neighbor classifiers, our kernel based classifier will be similar to a nearest neighbor model.
Note: The classifiers we train using kernels do not work directly with these $\phi_i$ representations, but I think that is what they do implicitly.
The reason is that the VC dimension for Gaussian kernels is infinite, and thus, given the correct values for the parameters (sigma), they can classify an arbitrarily large number of samples correctly.
RBFs work well because they ensure that the matrix $K(x_{i},x_{j})$ is full rank. The idea is that $K(x_{i},x_{i}) > 0$, and off-diagonal terms can be made arbitrarily small by decreasing the value of $\sigma$. Notice that the kernel corresponds to a dot product in the feature space. In this feature space, the dimension is infinite (by considering the series expansion of the exponential). One could thus see this as projecting those points in different dimensions so that you can separate them.
Consider by contrast, the case of linear kernels, which can only shatter four points on the plane.
You may take a look at this paper, though it's very technical. One of the standard books on SVMs should make this concept more accessible.
