198 votes

How to intuitively explain what a kernel is?

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 "...
77 votes

How to intuitively explain what a kernel is?

A visual example to help intuition 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 ...
63 votes

What makes the Gaussian kernel so magical for PCA, and also in general?

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 ...
  • 2,043
48 votes

How to intuitively explain what a kernel is?

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 ...
46 votes
Accepted

Difference between Primal, Dual and Kernel Ridge Regression

Short answer: no difference between Primal and Dual - it's only about the way of arriving to the solution. Kernel ridge regression is essentially the same as usual ridge regression, but uses the ...
46 votes
Accepted

What are the advantages of kernel PCA over standard PCA?

PCA (as a dimensionality reduction technique) tries to find a low-dimensional linear subspace that the data are confined to. But it might be that the data are confined to low-dimensional nonlinear ...
  • 96.4k
45 votes

How can SVM 'find' an infinite feature space where linear separation is always possible?

This answer explains the following: Why perfect separation is always possible with distinct points and a Gaussian kernel (of sufficiently small bandwidth) How this separation may be interpreted as ...
  • 10.2k
34 votes
Accepted

Is there any supervised-learning problem that (deep) neural networks obviously couldn't outperform any other methods?

Here is one theoretical and two practical reasons why someone might rationally prefer a non-DNN approach. The No Free Lunch Theorem from Wolpert and Macready says We have dubbed the associated ...
  • 19.6k
30 votes

How to prove that the radial basis function is a kernel?

I'll add a third method, just for variety: building up the kernel from a sequence of general steps known to create pd kernels. Let $\mathcal X$ denote the domain of the kernels below and $\varphi$ the ...
  • 22.6k
30 votes
Accepted

What is the rationale of the Matérn covariance function?

In addition to @Dahn's nice answer, I thought I would try to say a little bit more about where the Bessel and Gamma functions come from. One starting point for arriving at the covariance function is ...
29 votes
Accepted

Nystroem Method for Kernel Approximation

Let's derive the Nyström approximation in a way that should make the answers to your questions clearer. The key assumption in Nyström is that the kernel function is of rank $m$. (Really we assume ...
  • 22.6k
27 votes

Is there any supervised-learning problem that (deep) neural networks obviously couldn't outperform any other methods?

Somewhere on this playlist of lectures by Geoff Hinton (from his Coursera course on neural networks), there's a segment where he talks about two classes of problems: Problems where noise is the key ...
  • 4,737
20 votes

What is the rationale of the Matérn covariance function?

I do not know, but I found this question very interesting and here's what I got after a bit of reading on it. For certain values of $\nu$, the Matérn covariance function can be expressed as a product ...
  • 518
18 votes

What makes the Gaussian kernel so magical for PCA, and also in general?

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 ...
15 votes

The difference of kernels in SVM?

Relying on basic knowledge of reader about kernels. Linear Kernel: $K(X, Y) = X^T Y$ Polynomial kernel: $K(X, Y) = (γ\cdot X^T Y + r)^d , γ > 0$ Radial basis function (RBF) Kernel: $K(X, Y) = \...
15 votes
Accepted

Is the Gaussian Kernel still a valid Kernel when taking the negative of the inner function?

This reasoning is essentially that of Sycorax's answer, but no need to resort to that theorem: Consider two distinct points $x$ and $y$. For $\theta<0$, their Gram matrix is $$ \begin{bmatrix} k(x,...
  • 22.6k
14 votes
Accepted

Intuition behind RKHS (Reproducing Kernel Hilbert Space}?

As the name says, reproducing kernel Hilbert spaces is a Hilbert space, so some knowledge of Hilbert space/functional analysis comes in handy ... But you might as well start with RKHS, and then see ...
14 votes
Accepted

What exactly is the procedure to compute principal components in kernel PCA?

To find PCs in classical PCA, one can perform singular value decomposition of the centred data matrix (with variables in columns) $\mathbf X = \mathbf U \mathbf S \mathbf V^\top$; columns of $\mathbf ...
  • 96.4k
14 votes
Accepted

Is Support Vector Machine sensitive to the correlation between the attributes?

Linear kernel: The effect here is similar to that of multicollinearity in linear regression. Your learned model may not be particularly stable against small variations in the training set, because ...
  • 22.6k
14 votes
Accepted

Is Gradient Descent possible for kernelized SVMs (if so, why do people use Quadratic Programming)?

Set $\mathbf w = \phi(\mathbf x)\cdot \mathbf u$ so that $\mathbf w^t \phi(\mathbf x)=\mathbf u^t \cdot \mathbf K$ and $\mathbf w^t\mathbf w = \mathbf u^t\mathbf K\mathbf u$, with $\mathbf K = \phi(\...
  • 16.1k
14 votes

Is there any supervised-learning problem that (deep) neural networks obviously couldn't outperform any other methods?

Two linearly perfected correlated variables. Can deep-network with 1 million hidden layers and 2 trillion neutrons beat a simple linear regression? EDITED In my experience, sample collection is more ...
  • 6,937
13 votes
Accepted

How to project a new vector onto the PC space using kernel PCA?

Let's consider the training dataset first. Principal components (sometimes called PC "scores") are the centered data projected onto the principal axes. In kPCA, eigenvectors of the kernel matrix ...
  • 96.4k
12 votes

Feature map for the Gaussian kernel

For any valid psd kernel $k : \mathcal X \times \mathcal X \to \mathbb R$, there exists a feature map $\varphi : \mathcal X \to \mathcal H$ such that $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_{...
  • 22.6k
11 votes
Accepted

How to use "kernel trick" in Stochastic gradient descent?

AFAIK the kernel trick has pretty much nothing to do with SGD. Are you thinking SVM instead of SGD perhaps? The kernel trick is an optimization used mainly to compute SVM models. The "Kernel Trick" ...
11 votes
Accepted

Kernels in Gaussian Processes

Notation / setting We are considering a GP regression model: \begin{equation} y_i = f(x_i) + \epsilon_i \end{equation} where $y_i\in \mathbb{R}$,$x_i \in \mathbb{R}^d$, $f$ a Gaussian process (whose ...
  • 7,683
10 votes

What makes the Gaussian kernel so magical for PCA, and also in general?

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 ...
  • 1,399
10 votes
Accepted

Linear combination of two kernel functions

A necessary and sufficient condition for a function $\kappa(\cdot,\cdot)$ to be expressible as an inner product in some feature space $\mathcal{F}$ is a weak form of Mercer's condition, namely that: $...
  • 17.6k
10 votes
Accepted

Proof that the linear kernel is a kernel, understanding the math

First, your definition should be corrected as $$k(x, x') = \langle x, x\color{red}{'}\rangle = \sum_{a = 1}^N x_a x_a'. $$ The problem of your derivation is that you didn't distinguish $x_i = (x_{i,1},...
  • 5,112
10 votes
Accepted

Proof that $K(x,y) = f(x)f(y)$ is a kernel

$\sum_{i=1}^n\sum_{j=1}^nK(x_i, x_j)c_ic_j=\sum_{i=1}^n\sum_{j=1}^nf(x_i)f(x_j)c_ic_j = (\sum_{i=1}^nf(x_i)c_i)^2 \geq 0$
9 votes

How to choose a kernel for kernel PCA?

The general approach to select an optimal kernel (either the type of kernel, or kernel parameters) in any kernel-based method is cross-validation. See here for the discussion of kernel selection for ...
  • 96.4k

Only top scored, non community-wiki answers of a minimum length are eligible