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
0
votes
0answers
7 views

Why do Support Vector Data Description and One Class Support Vector Machine produce the same results?

Quoating from Chapter 5 of Kernel Methods in Computer Vision by Christoph H. Lampert 'A quick geometric check shows that if all data points have the same feature space norm and can be separated ...
0
votes
1answer
94 views

Intuitive Understanding of the Effect of Correlation on Random Variables in Gaussian Process

So In general covariance matrix in GP provides us with proportionality relation between random variables, in other words $x_1$ and $x_2$ are perfectly correlated if off-diagonal entry has $\rho=\pm 1$:...
1
vote
0answers
15 views

Dimensions of feature transfrom $\phi(x)$ for a kernel Support Vector Machines

Given a kernel function $K(x, x') = \langle \phi(x), \phi(x') \rangle$, how can we figure out the dimensions of the feature transform $\phi(x)$? For example, for $K(x, x') = (1+x^Tx')^M$
0
votes
0answers
32 views

Recent advances in the use of the spectra of kernel integrals following Yoshua Bengio's 2004 paper that links kernel PCA and spectral clustering?

In Yoshua Belgio's 2003 technical report http://www.iro.umontreal.ca/~lisa/pointeurs/TR1232.pdf, and subsequent 2004 paper http://www.iro.umontreal.ca/~lisa/pointeurs/bengio_eigenfunctions_nc_2004.pdf,...
0
votes
1answer
17 views

Comparing margin width of SVM with different kernels as a performance metric

Assume we have applied SVM with different kernels to a problem, Alongside the performance metrics like accuracy, precision, etc, can we compare the margin size to decide which kernel is the best?
3
votes
1answer
23 views

Periodicity of random kitchen sink feature mappings

In various papers, e.g. Random Features for Large-Scale Kernel Machines, Rahimi and Recht introduce the now popular methodology wherein a "low rank" approximation to a stationary, PSD, kernel $K(x,y) =...
0
votes
0answers
20 views

$\Sigma_*$ in Gaussian Process Prediction Formula

So posterior predictive distribution of the Gaussian process is given by the following equation. $\mathbf{f}_*$ given new input $\mathbf{X}_*:$ $$p(\mathbf{f}_* \lvert \mathbf{X}_*,\mathbf{X},\...
1
vote
1answer
34 views

Expression for Derivative of Hyperparameter of Kernel with respect to New Data

I would like to determine how the hyperparameter will change when a new data is observed and the GP is updated with this new data. Considering the following predictive distribution of the GP: $$\mu(...
1
vote
0answers
15 views

Should Kernel Ridge Regression with linear kernel yield same results as Ridge regression?

I'm comparing the performance of different regressors from scikit-learn for fitting some data. I would have expected that Ridge regression and Kernel Ridge regression both yield the same model/...
1
vote
0answers
20 views

Effect of Gamma and C on distant points in SVM

(I am aware of the following, already answered questions: this,and this,as well as others, and IMHO they are not related) I am trying to precisely understand the behavior of SVM's with regards to the ...
0
votes
0answers
9 views

Why is the input feature space infinite-dimensional after applying the kernel transformation in Kernel-PCA?

Kernel-PCA is an unsupervised technique that can be used to compress data. It has some hyper-parameters, for example the choice of the type of kernel (radial, linear, sigmoid, etc.). According to the ...
0
votes
1answer
31 views

What is the expanded representation, $\phi(X)$, required to obtain the RBF kernel?

For the two-dimensional case, where $\boldsymbol X=[x_1, x_2]$ and its corresponding expanded represetation $\boldsymbol\phi(X)= [1, \sqrt2 x_1, \sqrt2 x_2, x_1^2, x_2^2, \sqrt2x_1x_2]$, we can ...
0
votes
0answers
16 views

Covariate Shift in the case of Kernel Regression

Kernel Regression, in its most simplistic form (Nadaraya-Watson kernel regression), can be viewed as a conditional density estimation problem. Let $\hat{p}(y, x) = N^{-1}\sum_i K(y, y_i)K(x, x_i)$ be ...
0
votes
0answers
10 views

Informative Vector Machine for multiple classes

Reading about the GPLVM -Gaussian Process Latent Variable Models- in the Neil D. Lawrence 2003 paper I understood how the dimensionality reduction is performed. From my understanding, the algorithm is ...
0
votes
0answers
27 views

Relation between choice of kernel for the affinity matrix in spectral clustering and embedding into a higher dimensional space, using feature maps

So I've been studying spectral clustering where they use some affinity function related to a pre-constructed graph of the sample points or data $\{x_1,...x_n\}$. If we call the affinity function $W$, ...
0
votes
1answer
25 views

Adaptive Gamma in RBF Kernel

The RBF Kernel is defined by $K(x,y)=\exp(-\gamma ||x-y||^2)$ Wouldnt it be better to find a suited gamma value for each dimension? $K(x,y)=\exp(-\sum_i \gamma_i * (x_i-y_i)^2 )$ This would add ...
1
vote
0answers
18 views

Is it good idea to generate features from data points similarity comparison?

I know about polynomial features in machine learning, which can introduce nonlinearity to original dataset. I also heard about binning, which also allows us to create new features from existing ones. ...
8
votes
1answer
204 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 ...
2
votes
1answer
26 views

Reference: Data-Dependent Early Stopping Criterion for Deep Learning?

In the context of non-parametric regression, this paper provides an data-dependent rule for optimal early stopping, when learning an unknown function $f^{\star}$ lying in some RKHS. Here, one stops ...
0
votes
0answers
14 views

Proof that the linear kernel is a kernel

I'm having trouble trying to show that the linear kernel is a kernel because its Gram matrix is symmetric and positive semi-definite. Can anyone help me?
0
votes
0answers
17 views

Implementing a Kernel Adaptive Filtering model explained in a paper

In this paper, Stock price prediction using kernel adaptive filtering within a stock market interdependence approach, the authors propose a method for predicting stock prices by combining the ...
2
votes
1answer
50 views

Is it always possible to find the feature map from a given kernel?

Each positive definite kernel $k(x, x')$ used in machine learning/statistics has an equivalent representation as a dot product of the feature map representation $\phi(x)$ of each input i.e. \begin{...
4
votes
0answers
79 views

Nystrom approximation with inexact/stochastic kernel evaluation

Suppose we have several data points $x_1,\ldots,x_m\in\mathbb R^n$ as well as a positive definite kernel $K(x,y):\mathbb R^n\times\mathbb R^n\to\mathbb R$ that can be written in the form $$K(x,y)=\...
2
votes
0answers
19 views

Difference between Kernel ridge regression and normal regression [duplicate]

I wanted to ask whether they're any difference between Kernel Ridge Regression and normal Ridge Regression. I've fitted a dataset with both models and obtained approximately the same root mean squared ...
0
votes
0answers
10 views

Does reducing dimensionality of data makes it less linearly separable?

I recently read about kernel trick in SVM that says that mapping data to higher dimensions makes it more linearly separable but can we conversely say that "mapping ...
0
votes
1answer
47 views

Is the kernel trick unnecessary for for non-linear SVM?

I am just learning about Mercer Kernels, and a question came up. Since using Mercer's theorem, we know that a positive definite kernel matrix can be represented by an inner production of the input ...
0
votes
0answers
36 views

Kernelized Perceptron, is it a more efficient algorithm?

I'm reading http://ciml.info/ chapter 11 Kernel Methods. For a feature vector x=x1,x2,x3,...,xD, feature combination expands O(x^2) features. We can rewrite linear models which only takes O(x) ...
0
votes
1answer
34 views

How to classify new data point for Kernel SVM?

I am working on implementing the kernel SVM using cvxopt quadratic programming, this is for a class so that why I'm not using something like SKLearn. Assume here no slack variable, only SMV but with ...
1
vote
1answer
125 views

On the properties of covariance and kernel matrices

I'm stumbling upon an example of a mixed model or a Gaussian Process, say: $Z \in\mathbb{R}^{n \times m}, m \ge n$ ie random effect $X \in\mathbb{R}^{n \times p}, p \ge 1$ ie fixed effects $K \in\...
2
votes
1answer
43 views

The inner product properties seem to clash with the RKHS property for RBF kernels. What is off?

By the reproducing kernel Hilbert space (RKHS) property, given a P.S.D. kernel function $\kappa:X\times X \rightarrow \mathbb R$, there exists a Hilbert space $H$ and a map $\phi:X\rightarrow H$ such ...
0
votes
0answers
29 views

Is a valid kernel function have to be positive definite?

Positive semi-definite(PSD) kernels confuse me a lot. Are PSD kernels valid kernels? I used to read some papers in which the authors define PSD kernels and use them for some tasks. However, I think a ...
0
votes
1answer
18 views

How does square of dot product can be compared to a similarity in terms of circle

When reading about SVM and Kernel Trick, a common similarity function which is often used is which is taken from this blog I am trying to understand how this is related to equation of circle. ...
0
votes
1answer
17 views

Determine dimension of mapping function Phi from form of Kernel

If I have a kernel of the form $k(x, y) = (x^Ty)^n$ where $x$ and $y$ are d-dimensional, how can I determine the dimension of the mapping function $\phi(x)$, in terms of n and d, without explicitly ...
1
vote
1answer
23 views

Kernel Confusion

Consider the function $K(\vec{x},\vec{y})$ where $\vec{x},\vec{y} \in \mathbb{R}^n$. I have been asked to check that this is a valid kernel. Question 1 My understanding is that I can prove this in ...
0
votes
0answers
10 views

Recursive formula for polynomial kernel

I'm reading Chapter 9 of Kernel Methods for Pattern Analysis by Shawe-Taylor and Cristianini. (Online here, p.296.) It defines $$ \kappa_s^m(\mathbf{x},\mathbf{z})=(\langle\mathbf{x}_{1:m},\mathbf{z}_{...
0
votes
1answer
17 views

(SVMs) Do the specific higher dimensional mappings of attributes not matter when calculating a kernel?

From what I know, one of the strategies employed by an SVM is to increase dimensionality of your data until they are linearly separable. (I guess there's some mathematical proof that your data will ...
0
votes
0answers
11 views

What is Kernel based approach in Machine Learning?

I came across several papers talking about kernel based approaches. I googled and found most of them discussing about kernel tricks using SVM. Anybody throw some light on this technique?
2
votes
1answer
158 views

Advantage & disadvantage of PCA vs kernel PCA

PCA is used for dimensional reduction. I learned today that PCA cannot be used for nonlinear data. When nonlinear, you have to use kernel PCA (KPCA). It seems that since KPCA is more applicable to ...
0
votes
1answer
35 views

What is the minimal feature space dimension for an input to be linearly saparable?

I would like to know what methods exists to determine for certain feature-space-mapping-functions and a related finite number of inputs the minimal dimension of the feature space to make the inputs ...
0
votes
0answers
24 views

Kernel trick and its inner-product kernel

I try to solve a task where a nonlinear transformation $\phi:\mathbb{R}\mapsto\mathbb{R}^{d+1}$ is given by $\phi(x)=(a_0\cdot 1,a_1\cdot x,a_2\cdot x^2,\ldots,a_d\cdot x^d)$ with $a_i\in\mathbb{R}$. ...
0
votes
0answers
44 views

Gaussian process with ARD kernel much more expensive to train

I'm fitting a Gaussian process regression model in MATLAB (using the quasi-Newton method) with 10 input parameters, using the Matérn 5/2 and Matérn 5/2 ARD kernels. I notice that, with increasing ...
0
votes
0answers
15 views

Does the kernel trick functions represents the Z value of a 2D point that are we going to display it into 3D space?

I am new to machine learning and the support vector machine is one of the hardest to understand in terms of math. Using one of the rbf kernel functions: $$k(xi,xj)...
2
votes
0answers
27 views

General approach to prove if the given function is NOT a valid kernel function

In general, for proving that the given kernel function is valid, I try one of the following two approaches: Check if the gram matrix is Symmetric Postive Semi Definite. Check if the kernel function ...
0
votes
0answers
32 views

Kernel:Why is the dot product a “measure of similarity” of instances? [duplicate]

Not a duplicate since the linked question does not answer this question: A measure of similarity should be maximal for instances which are the same (e.g. similarity between (1,1) and (1,1) should be ...
1
vote
2answers
61 views

For what values of $\beta \in \mathbb{R}$ is $t(x-x')=-||x-x'||^\beta$ a kernel?

For what values of $\beta \in \mathbb{R}$ is $t(x-x')=-||x-x'||^\beta$ a kernel? I know that kernels of type $t(x-x')$ where $t$ is function that inverts the dissimilarity $x-x'$ into a similarity ...
1
vote
0answers
130 views

Invertibility of Random Fourier Features

Is it possible to approximately reconstruct a point $ \mathbf{x} $ in a vector space (say $\mathbb{R}^n $) given it's randomized feature map $ z(\cdot) $ and respective projection $ z(\mathbf{x})$ (in ...
0
votes
0answers
51 views

I want to know the relationship between Discriminant functions and the kernel in SVM

The following articles are reprinte of #3338212 of math.stackexchange.com. It was recommended to ask this community at math.stackexchange.com. The following 【Quiz】 and 【Official Answer】are the ...
2
votes
1answer
56 views

Support Vector Machine: identifying support vectors and kernel linear separability

I went through the MIT Artificial Intelligence lecture on Support Vector Machines by Professor Patrick Winston: https://www.youtube.com/watch?v=_PwhiWxHK8o I've got a couple of questions. Would be ...
1
vote
1answer
100 views

Understanding the reproducing property of RKHS

I am currently trying to learn about Reproducing Kernel Hilbert spaces (RKHS) and would like to gain some intuition about its reproducing property. The RKHS is defined with kernel $k(x,x')$ which maps ...
0
votes
0answers
28 views

why the result of primal sim is not the same as linear kernel?

I have a data set with 36000 rows and 9 columns. so n<< m. this is multi classification SVM. I solved this by primal model in OSQP. then I used R package e710 and svm with linear kernel. the ...

1 2 3 4 5 12