Skip to main content
87 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 ...
Xavier Bourret Sicotte's user avatar
38 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 ...
MachineEpsilon's user avatar
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 ...
Matt Krause's user avatar
  • 21.1k
31 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 that ...
Danica's user avatar
  • 24.8k
28 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 ...
Ben Ogorek's user avatar
  • 5,387
27 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 ...
Dahn's user avatar
  • 618
19 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) = \...
Ashok Davas's user avatar
16 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(\...
Firebug's user avatar
  • 19.1k
16 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,...
Danica's user avatar
  • 24.8k
15 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 ...
SmallChess's user avatar
  • 7,231
12 votes
Accepted

What's the physical meaning of the eigenvectors of the Gram/Kernel matrix?

The eigenvalues are actually the same as those of the covariance matrix. Let $X = U \Sigma V^T$ be the singular value decomposition; then $$X X^T = U \Sigma \underbrace{V^T V}_{I} \Sigma U^T = U \...
Danica's user avatar
  • 24.8k
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 ...
Juho Kokkala's user avatar
  • 7,923
11 votes
Accepted

Why does a Gaussian Process need to have a PSD kernel? Can I use a non-PSD kernel?

Say that $X \sim \mathcal{GP}(m(\cdot), k(\cdot, \cdot))$. If $k$ is not a PSD kernel, then there is some set of $n$ points $\{ t_i \}_{i=1}^n$ and corresponding weights $\alpha_i \in \mathbb R$ such ...
Danica's user avatar
  • 24.8k
10 votes
Accepted

Log marginal likelihood for Gaussian Process

The more general formulation for the log marginal likelihood (not marginal log likelihood, as you originally wrote - I edited it in your post) of a GP is $$\log p(y|X) = -\frac{1}{2}(y - m(X))^T(K+\...
lacerbi's user avatar
  • 5,186
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$
Jakub Bartczuk's user avatar
10 votes
Accepted

Can someone provide a brief explanation as to why reproducing kernel Hilbert space is so popular in machine learning?

The typical way to give some intuition for reproducing kernel spaces (and, in particular, the kernel trick), is the application area of support vector machines. The aim is to linearly separate two ...
IljaKlebanov's user avatar
10 votes
Accepted

Advantage & disadvantage of PCA vs kernel PCA

Kernel PCA (kPCA) actually includes regular PCA as a special case--they're equivalent if the linear kernel is used. But, they have different properties in general. Here are some points of comparison: ...
user20160's user avatar
  • 32.6k
10 votes
Accepted

Why use RBF kernel if less is needed?

One way of looking at it is to say that the RBF kernel dynamically scales the feature space with the number of points. As we know from geometry, for $p$ points you can always draw an at most $(p-1)$-...
Igor F.'s user avatar
  • 9,169
10 votes

In machine learning, for a kernel function k, is sqrt(k) also a valid kernel function?

Counterexample An example of a positive definite kernel is $K = \mathbf{x} \cdot \mathbf{y}$. But when we consider the following $x_i$ $$x_1 = \begin{bmatrix} 17 \\ 9 \\ 7 \\0 \end{bmatrix} \qquad x_2 ...
Sextus Empiricus's user avatar
9 votes
Accepted

RBF kernel algorithm Python

Say that mat1 is $n \times d$ and mat2 is $m \times d$. Recall that the Gaussian RBF kernel is defined as $k(x, y) = \exp\left( ...
Danica's user avatar
  • 24.8k
9 votes
Accepted

Covariance in Gaussian Process

Noise parameter, $\sigma^2$, is the parameter of the likelihood function a.k.a noise function. The one with $+\sigma^2$ is the variance of $y$ (observation). The one without is the variance of $f$ (...
Leila's user avatar
  • 965
9 votes
Accepted

How can we prove that a normalized kernel is also a kernel?

\begin{align*} K'(x,y)&:=\frac{K(x,y)}{\sqrt{K(x,x)K(y,y)}}\\ &=\frac{\Phi(x)\cdot\Phi(y)}{\|\Phi(x)\|\|\Phi(y)\|}. \end{align*} The denominator is always non-negative, hence this is a kernel ...
Alex R.'s user avatar
  • 13.9k
9 votes
Accepted

Gaussian Process instability with more datapoints

A very useful project to grow intuition around Gaussian processes! [I'll try to write this as intuitive rather than mathematical] The two problems are very much related. The kernel you are using is ...
j__'s user avatar
  • 2,352
8 votes

In Convolutional Neural Networks (CNN), how we can decide number of kernels between input and hidden layer?

It's important not to confuse kernels with feature maps. The kernels are the masks used to perform convolution on your input image. The feature maps are the result of the convolution, your new ...
Julep's user avatar
  • 497
8 votes
Accepted

What happens if you square an RBF kernel function?

To start with, you're slightly off on the representer theorem; it means that $h$ is a linear combination of kernel functions. That is, if your input data points are $\{z_i\}_{i=1}^n$, then $$ h(x) = \...
Danica's user avatar
  • 24.8k
8 votes
Accepted

How to prove a Hamming distance as a Kernel?

Step 1. For an arbitrary set of strings $\{x_i\}$, first sort them by their length. Then the kernel matrix is block-diagonal, since the kernel value between any two strings of different lengths is ...
Danica's user avatar
  • 24.8k
8 votes
Accepted

Is non-integer power of a kernel still a kernel?

You have exactly defined the class of infinitely divisible kernels, i.e., a kernel $k(x, y)$ such that $k(x, y)^p$ is a kernel for any $p > 0$. Not all kernels are infinitely divisible. Many of ...
Mark L. Stone's user avatar
8 votes

Does Mercer's theorem work in reverse?

Does Mercer's theorem work in reverse? Not in all cases. Wikipedia: "In mathematics, specifically functional analysis, Mercer's theorem is a representation of a symmetric positive-definite function ...
Rob's user avatar
  • 2,100
8 votes
Accepted

Is a kernel function basically just a mapping?

My initial understanding is that a kernel is essentially just a mapping into a higher dimension. No. Kernel is a function that calculates dot product in the image of this mapping. It can be ...
Jakub Bartczuk's user avatar
8 votes

Why are random Fourier features efficient?

So this kind of looks like a case of notational abuse to me. Quick Review of Dual Formulation of SVMs and Kernel Trick For standard, basic vanilla support vector machines, we deal only with binary ...
Don Walpola's user avatar
  • 1,328

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