63
$\begingroup$

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.

  • Why don't we put the norm through, say, a Cauchy PDF and expect the same results?
$\endgroup$

migrated from math.stackexchange.com Jan 4 '15 at 4:06

This question came from our site for people studying math at any level and professionals in related fields.

  • 1
    $\begingroup$ +1. Excellent question which I almost overlooked, because it did not have a [pca] tag! Edited now. $\endgroup$ – amoeba Jan 6 '15 at 22:47
  • 4
    $\begingroup$ Good question. I'm wondering if the answer might be "oh yeah, many other kernels would work fine too but gaussian is well known/easy" $\endgroup$ – Stumpy Joe Pete Jan 6 '15 at 22:59
  • $\begingroup$ @StumpyJoePete I don't think that's such a trivial answer. What other distribution's location parameter is also its mean? What other distributions' scale parameter is also its variance? What other distribution is so universally intuitive? Surely not the Cauchy distribution -- it doesn't even have a mean! $\endgroup$ – shadowtalker Jan 7 '15 at 1:49
  • 3
    $\begingroup$ @ssdecontrol I'm happy to be proven wrong; I've upvoted both the question and one of the answers--I just think my boring, ho-hum, deflationary answer makes a good default that a real answer ought to disprove. $\endgroup$ – Stumpy Joe Pete Jan 7 '15 at 19:01
  • $\begingroup$ I think this may help: stats.stackexchange.com/questions/168051/… $\endgroup$ – user83346 Aug 22 '15 at 7:33
53
+50
$\begingroup$

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$.

$\endgroup$
  • 2
    $\begingroup$ I'm not about to award the bounty just yet but I'm tempted to award it to this answer, because it's very targeted to the question and makes explicit comparisons to other kernels $\endgroup$ – shadowtalker Jan 11 '15 at 20:19
  • $\begingroup$ Finally this question got one great answer! (+1) I was briefly confused by the notation you used here: $f(x)=\left\langle f,\phi(x)\right\rangle$ -- and in the following paragraphs. Wouldn't a more explicit notation $f(x)=\left\langle \Psi(f),\phi(x)\right\rangle$ be clearer by separating a function $f(\cdot)$ acting on the original space and a vector $\Psi(f) \in \mathcal H$, where $\Psi(\cdot)$ is a functional? By the way, which functions are guaranteed to be "reproduced" by the "reproducing property"? All? Continuous? Smooth? $\endgroup$ – amoeba Jan 11 '15 at 20:28
  • $\begingroup$ @amoeba In the literature, people do not distinguish a representation of $f$ and the function itself. If needed, sometimes they use $f$ for representation and $f(\cdot)$ for a function. All functions in the space $\mathcal{H}$ have the reproducing property. Smooth or not, that is specified by the kernel. :) $\endgroup$ – wij Jan 11 '15 at 20:29
  • $\begingroup$ Updated the post. Added a bit more on tanh kernel. $\endgroup$ – wij Jan 11 '15 at 20:30
  • $\begingroup$ Hmmm, I think I am confused here. We start with a vector space $\mathcal X$, where data points $x$ live. Then we choose a positive definite kernel $k(\cdot, \cdot): \mathcal X \times \mathcal X \to \mathbb R$. Then we claim that Theorem 1 holds: $k$ can be realized as a dot product on some Hilbert space $\mathcal H$, such that $k(x,y) = \langle \phi(x), \phi(y)\rangle$, where $\phi:\mathcal X \to \mathcal H$. Okay. And now you say that any function $f(x)$ acting on $\mathcal X$ can be realized as a scalar product of its representation $f\in \mathcal H$ with $\phi(x)$? Is this right? $\endgroup$ – amoeba Jan 11 '15 at 21:32
16
$\begingroup$

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:

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.

  • Gaussian kernels are circular (which leads to the above-mentioned infinite dimensionality?)
  • Gaussian kernels can represent "highly varying terrains"
  • The following point, supporting the main conclusion above, is better delivered by citing the author:

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.

  • Gaussian kernels are optimal (on smoothness, read more here - same author):

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:

  • Gaussian kernels support infinitely complex models
  • Gaussian kernels are more flexible

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.

$\endgroup$
  • 5
    $\begingroup$ I appreciate and applaud the effort put in composing this answer, but at the same time must say that it quotes from a lot of sources that are not very authoritative and that provide only this sort of general hand-wavy explanations that might be correct but might also be completely false. So the RBF kernel is an isotropic stationary kernel with an infinite-dimensional reproducing Hilbert space. Good! Are there are other kernels with these properties? If so, why would RBF be better than all of them? In fact, is there any empirical support to the claim that RBF outperforms such competitors? $\endgroup$ – amoeba Jan 7 '15 at 10:53
  • $\begingroup$ @amoeba: Thank you for kind words. In regard to the sources that I've used, you're partially right - it's a mix and some sources are just opinions. However, some sources (i.e., the blog posts) themselves cite solid papers. At this point, I was more attracted by quality of an explanation rather than its rigor. As far as your questions go, I'm preparing to address them later. I need to read a bit more theory. I've already compiled sources with empirical support, but need more time for their systematization (and some sleep, :). $\endgroup$ – Aleksandr Blekh Jan 7 '15 at 12:12
  • 1
    $\begingroup$ I have a feeling the fact that the Gaussian has maximum entropy among real symmetric distributions plays a role in your first point about good performance under general assumption $\endgroup$ – shadowtalker Jan 11 '15 at 20:24
  • 2
    $\begingroup$ Also @AleksandrBlekh this is a fantastic compilation. People rag on Quora but it's no less authoritative than linking to another answer here $\endgroup$ – shadowtalker Jan 11 '15 at 20:27
  • $\begingroup$ @ssdecontrol: Thank you for kind words. Glad that we are on the same page about the topic. I have some additional info to address amoeba's comment, so watch this space, if you're interested. $\endgroup$ – Aleksandr Blekh Jan 11 '15 at 22:39
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The nearest-neighbors interpretation is interesting. Do you think you could expand on that a little bit? I think I get it but I'm not sure I do. $\endgroup$ – shadowtalker Jan 14 '15 at 1:27
  • $\begingroup$ @ssdecontrol I added some comments; I hope they are helpful. $\endgroup$ – goker Jan 15 '15 at 20:17
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 'RBFs work well because they ensure that the matrix $K(x_i,x_j)$ is full rank': this is true of every valid (Mercer) kernel function (including the linear one) so I'm not sure how it explains the alleged out-performance of the RBF. $\endgroup$ – user603 Jan 7 '15 at 10:11
  • 2
    $\begingroup$ In addition to what @user603 has just written: are there other popular kernels with infinite VC dimension (dimension of the target space)? If so, are they then as good as RBF? $\endgroup$ – amoeba Jan 7 '15 at 10:13
  • 2
    $\begingroup$ Isn't VC dimension a property of a set of classifiers, not the property of a kernel ? $\endgroup$ – wij Jan 11 '15 at 18:41
  • 2
    $\begingroup$ @user603: this isn't true. Mercer kernels only require that the kernel matrix be positive semidefinite; they can be singular. For example, the linear kernel in fact gives singular kernel matrices if $x_i = 0$ is in your set of points. (Of course, most kernels are strictly positive definite and so this isn't a particularly distinctive property of the Gaussian RBF.) $\endgroup$ – Dougal Jan 15 '15 at 22:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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