Questions tagged [kernel-trick]

Kernel methods are used in machine learning to generalize linear techniques to nonlinear situations, especially SVMs, PCA, and GPs. Not to be confused with [kernel-smoothing], for kernel density estimation (KDE) and kernel regression.

Filter by
Sorted by
Tagged with
127
votes
4answers
77k views

How to intuitively explain what a kernel is?

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 ...
100
votes
4answers
75k views

How to select kernel for SVM?

When using SVM, we need to select a kernel. I wonder how to select a kernel. Any criteria on kernel selection?
77
votes
2answers
21k views

What is a “kernel” in plain English?

There are several distinct usages: kernel density estimation kernel trick kernel smoothing Please explain what the "kernel" in them means, in plain English, in your own words.
71
votes
4answers
39k views

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

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 ...
49
votes
2answers
68k views

Linear kernel and non-linear kernel for support vector machine?

When using support vector machine, are there any guidelines on choosing linear kernel vs. nonlinear kernel, like RBF? I once heard that non-linear kernel tends not to perform well once the number of ...
38
votes
4answers
10k views

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

What is the intuition behind the fact that an SVM with a Gaussian Kernel has infinite dimensional feature space?
35
votes
3answers
18k views

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

How to prove that the radial basis function $k(x, y) = \exp(-\frac{||x-y||^2)}{2\sigma^2})$ is a kernel? As far as I understand, in order to prove this we have to prove either of the following: For ...
34
votes
3answers
4k views

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

I have seen people have put a lot of efforts on SVM and Kernels, and they look pretty interesting as a starter in Machine Learning. But if we expect that almost-always we could find outperforming ...
33
votes
2answers
44k views

Which search range for determining SVM optimal C and gamma parameters?

I am using SVM for classification and I am trying to determine the optimal parameters for linear and RBF kernels. For the linear kernel I use cross-validated parameter selection to determine C and for ...
31
votes
3answers
26k views

Difference between a SVM and a perceptron

I am a bit confused with the difference between an SVM and a perceptron. Let me try to summarize my understanding here, and please feel free to correct where I am wrong and fill in what I have missed. ...
29
votes
2answers
7k views

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

The Matérn covariance function is commonly used as kernel function in Gaussian Process. It is defined like this $$ {\displaystyle C_{\nu }(d)=\sigma ^{2}{\frac {2^{1-\nu }}{\Gamma (\nu )}}{\Bigg (}{\...
28
votes
4answers
17k views

Feature map for the Gaussian kernel

In SVM, the Gaussian kernel is defined as: $$K(x,y)=\exp\left({-\frac{\|x-y\|_2^2}{2\sigma^2}}\right)=\phi(x)^T\phi(y)$$ where $x, y\in \mathbb{R^n}$. I do not know the explicit equation of $\phi$. I ...
27
votes
4answers
57k views

The difference of kernels in SVM?

Can someone please tell me the difference between the kernels in SVM: Linear Polynomial Gaussian (RBF) Sigmoid Because as we know that kernel is used to mapped our input space into high ...
23
votes
1answer
21k views

What function could be a kernel?

In the context of machine learning and pattern recognition, there's a concept called Kernel Trick. Facing problems where I am asked to determine whether a function could be a kernel function or not, ...
23
votes
3answers
7k views

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

Why do people use Quadratic Programming techniques (such as SMO) when dealing with kernelized SVMs? What is wrong with Gradient Descent? Is it impossible to use with kernels or is it just too slow (...
21
votes
1answer
15k views

Difference between Primal, Dual and Kernel Ridge Regression

What is the difference between Primal, Dual and Kernel Ridge Regression? People are using all three, and because of the different notation that everyone uses at different sources is difficult for me ...
21
votes
3answers
9k views

Is Kernel PCA with linear kernel equivalent to standard PCA?

If in kernel PCA I choose a linear kernel $K(\mathbf{x},\mathbf{y}) = \mathbf x^\top \mathbf y$, is the result going to be different from the ordinary linear PCA? Are the solutions fundamentally ...
20
votes
1answer
18k views

What are the advantages of kernel PCA over standard PCA?

I want to implement an algorithm in a paper which uses kernel SVD to decompose a data matrix. So I have been reading materials about kernel methods and kernel PCA etc. But it still is very obscure to ...
20
votes
3answers
3k views

Applying the “kernel trick” to linear methods?

The kernel trick is used in several machine learning models (e.g. SVM). It was first introduced in the "Theoretical foundations of the potential function method in pattern recognition learning" paper ...
18
votes
1answer
33k views

How to understand effect of RBF SVM

How can I understand what the RBF Kernel in SVM does? I mean I understand the maths, but is there a way to get a feeling when this kernel will be useful? Would results from kNN be related to SVM/RBF ...
18
votes
1answer
11k views

Gaussian RBF vs. Gaussian kernel

What is the difference between doing linear regression with a Gaussian Radial Basis Function (RBF) and doing linear regression with a Gaussian kernel?
16
votes
6answers
21k views

Fastest SVM implementation

More of a general question. I'm running an rbf SVM for predictive modeling. I think my current program definitely needs a bit of a speed up. I use scikit learn with a coarse to fine grid search + ...
16
votes
5answers
13k views

Kernel SVM: I want an intuitive understanding of mapping to a higher-dimensional feature space, and how this makes linear separation possible

I am trying to understand the intuition behind kernel SVM's. Now, I understand how linear SVM's work, whereby a decision line is made which splits the data as best it can. I also understand the ...
14
votes
2answers
2k views

How to prove there is no finite-dimensional feature space for Gaussian RBF kernel?

How to prove that for the radial basis function $k(x, y) = \exp(-\frac{||x-y||^2)}{2\sigma^2})$ there is no finite-dimensional feature space $H$ such that for some $\Phi: \text{R}^n \to H$ we have $k(...
14
votes
1answer
2k views

Understanding Gaussian Process Regression via infinite dimensional basis function view

It is often said that gaussian process regression corresponds (GPR) to bayesian linear regression with a (possibly) infinite amount of basis functions. I am currently trying to understand this in ...
13
votes
1answer
11k views

Kernelised k Nearest Neighbour

I'm new to kernels and have hit a snag while trying to kernelise kNN. Preliminaries I'm using a polynomial kernel: $K(\mathbf{x},\mathbf{y}) = (1 + \langle \mathbf{x},\mathbf{y} \rangle)^d$ Your ...
13
votes
3answers
3k views

Should I use the Kernel Trick whenever possible for non-linear data?

I recently learned about the use of the Kernel trick, which maps data into higher dimensional spaces in an attempt to linearize the data in those dimensions. Are there any cases where I should avoid ...
13
votes
3answers
14k views

Proof of closeness of kernel functions under pointwise product

How can I prove that pointwise product of two kernel functions is a kernel function?
13
votes
3answers
4k views

What is a kernel and what sets it apart from other functions

There seem to be many machine learning algorithms that rely on kernel functions. SVMs and NNs to name but two. So what is the definition of a kernel function and what are the requirements for it to be ...
13
votes
1answer
5k views

How to choose a kernel for kernel PCA?

What are the ways to choose what kernel would result in good data separation in the final data output by kernel PCA (principal component analysis), and what are the ways to optimize parameters of the ...
12
votes
5answers
57k views

How to calculate a Gaussian kernel effectively in numpy [closed]

I have a numpy array with m columns and n rows, the columns being dimensions and the rows datapoints. I now need to calculate kernel values for each combination of data points. For a linear kernel $...
12
votes
1answer
3k views

Nystroem Method for Kernel Approximation

I have been reading about the Nyström method for low-rank kernel aproximation. This method is implemented in scikit-learn [1] as a method to project data samples to a low-rank approximation of the ...
12
votes
1answer
2k views

The relationship between the number of support vectors and the number of features

I ran an SVM against a given data set, and made the following observation: If I change the number of features for building the classifier, the number of resulting support vectors will also be changed. ...
12
votes
1answer
6k views

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

I would like to train an SVM to classify cases (TRUE/FALSE) based on 20 attributes. I know that some of those attributes are highly correlated. Therefore my question is: is SVM sensitive to the ...
11
votes
2answers
336 views

Does Mercer's theorem work in reverse?

A colleague has a function $s$ and for our purposes it is a black-box. The function measures the similarity $s(a,b)$ of two objects. We know for sure that $s$ has these properties: The similarity ...
11
votes
1answer
2k views

Kernel Ridge Regression Efficiency

Ridge Regression can be expressed as $$\hat{y} = (\mathbf{X'X} + a\mathbf{I}_d)^{-1}\mathbf{X}x$$ where $\hat{y}$ is the predicted label, $\mathbf{I}_d$ the $d \times d$ identify matrix, $\mathbf{x}$ ...
11
votes
1answer
3k views

How to kernelize a simple perceptron?

Classification problems with nonlinear boundaries cannot be solved by a simple perceptron. The following R code is for illustrative purposes and is based on this example in Python): ...
10
votes
1answer
9k views

What are the limitations of Kernel methods and when to use kernel methods?

Kernel methods are very effective in many supervised classification tasks. So what are the limitations of kernel methods and when to use kernel methods? Especially in the large scale data era, what ...
10
votes
1answer
219 views

Beyond Fisher kernels

For a while, it seemed like Fisher Kernels might become popular, as they seemed to be a way to construct kernels from probabilistic models. However, I've rarely seen them used in practice, and I have ...
10
votes
2answers
2k views

Which kernel method gives the best probability outputs?

Recently I have used Platt's scaling of SVM-outputs to estimate probabilities of default-events. More direct alternatives seem to be "Kernel logistic Regression" (KLR) and the related "Import Vector ...
10
votes
1answer
1k views

How are SVMs = Template Matching?

I read about SVMs and learnt that they are solving an optimization problem and max margin idea was very reasonable. Now, using kernels they can find even non-linear separation boundaries which was ...
10
votes
1answer
506 views

Why are random Fourier features efficient?

I am trying to understand Random Features for Large-Scale Kernel Machines. In particular, I don't follow the following logic: kernel methods can be viewed as optimizing the coefficients in a weighted ...
10
votes
1answer
254 views

What methods exist for tuning graph kernel SVM hyperparameters?

I have some data that exist on a graph $G=(V,E)$. The vertices belong to one of two classes $y_i\in\{-1,1\}$, and I'm interested in training an SVM to distinguish between the two classes. One ...
9
votes
2answers
13k views

Which SVM kernel to use for a binary classification problem?

I'm a beginner when it comes to support vector machines. Are there some guidelines that say which kernel (e.g. linear, polynomial) is best suited for a specific problem? In my case, I have to classify ...
9
votes
2answers
10k views

Use of the Gamma parameter with support vector machines

When using libsvm, the parameter $\gamma$ is a parameter for the kernel function. Its default value is setup as $$\gamma = \frac{1}{\text{number of features.}}$$ ...
9
votes
2answers
6k views

Is it possible to use kernel PCA for feature selection?

Is it possible to use kernel principal component analysis (kPCA) for Latent Semantic Indexing (LSI) in the same way as PCA is used? I perform LSI in R using the ...
9
votes
1answer
8k views

Log marginal likelihood for Gaussian Process

Log marginal likelihood for Gaussian Process as per Rasmussen's Gaussian Processes for Machine Learning equation 2.30 is: $$\log p(y|X) = -\frac{1}{2}y^T(K+\sigma^2_n I)^{-1}y - \frac{1}{2}\log|K+\...
9
votes
1answer
485 views

Regularized linear vs. RKHS-regression

I'm studying the difference between regularization in RKHS regression and linear regression, but I have a hard time grasping the crucial difference between the two. Given input-output pairs $(x_i,y_i)...
8
votes
1answer
16k views

Non-linear SVM classification with RBF kernel

I'm implementing a non-linear SVM classifier with RBF kernel. I was told that the only difference from a normal SVM was that I had to simply replace the dot product with a kernel function: $$ K(x_i,...
8
votes
1answer
6k views

What are the advantages of Multiple Kernel Learning (MKL) methods?

Multiple Kernel Learning methods aim to construct a kernel model where the kernel is a linear combination of fixed base kernels. Learning the kernel then consists of learning the weighting ...

1
2 3 4 5
13