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
1answer
10 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
15 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
6 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
14 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
7 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
26 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
31 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
19 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
22 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
8 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
16 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
26 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
55 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
120 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
42 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
29 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
53 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
21 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 ...
0
votes
3answers
94 views

What are kernels in support vector machine? [duplicate]

What are kernels in support vector machines? I have tried many contents but i am not familiar with Lagrange and Laplace concept in mathematics. So anyone can please elaborate concepts of kernels in ...
1
vote
1answer
33 views

Random fourier features and Bochner's Theorem

The paper, Random Fourier Features for Large-Scale Kernel Machines by Ali Rahimi and Ben Recht , makes use of Bochner's theorem which says that the Fourier transform $p(w) $ of shift-invariant ...
0
votes
0answers
20 views

How would phi of the gaussian rbf kernel map a 100-by-3 dimensional feature matrix?

Would a 100-by-3 dimensional feature matrix be mapped into a 100 dimensional or into a infinite dimensional feature space, if the mapping would not be bypassed by the Gaussian RBF Kernel? Following ...
0
votes
1answer
34 views

Kernel PCA: Find most important variables for each PC

To find the most important variable for each Principal Component is easy with PCA: With data->X and variables->variable_names ...
0
votes
1answer
36 views

How to Interpret output Coefficients of Linear Support Vector Regression?

I'm looking to interpret the output from my SVR model. I know that with SVM you can't directly interpret the coefficients of the model but that you first have to take a dot product With that said, ...
0
votes
0answers
28 views

How to show or prove a dataset is not linearly separable

I am looking to be pointed in the right direction. I am learning about kernels and I have a homework assignment to use the dual perceptron algorithm to classify datapoints from a spiral dataset, with ...
2
votes
1answer
55 views

Are there examples of covariance functions used in Gaussian processes with negative non-diagonal elements?

I've been searching through numerous kernels used in Gaussian processes, and one common feature is that the covariance matrices always have only positive elements. Yet the only requirement on the ...
1
vote
0answers
32 views

Maximum Mean Discrepancy Implementation

I am just beginning to learn about MMD as a way to measure the difference between two probability distributions using this tutorial. I want to implement it code-wise but I don't understand it ...
3
votes
1answer
55 views

Why isn't a gaussian kernel subject to the curse of dimensionality?

This has been bugging me for a while now. I understand from this answer why gaussian kernels are effective. But I can't wrap my head around the intuition of why the infinite dimensional feature map 𝜙(...
2
votes
0answers
41 views

Is kernalized linear regression parametric or nonparametric?

We know that for linear regression, we can predict: $$\hat{y} = w^Tx +b$$ Where $w$ is the parameter that minimizes the square loss. It is easy to prove that for the final solution using gradient ...
1
vote
1answer
17 views

A derivation regarding kernel regression for the support vector machine

THis is from the Elements of Statistical Learning book page 437 in the section of support vector machine. Can anyone give me some hint for the missing derivation steps for why 12.49 is true (as seen ...
0
votes
1answer
23 views

Expansion of inner product for polynomial kernel for SVMs

On page 424 in "The Elements of Statistical Learning" by Hastie et al (2013) (https://web.stanford.edu/~hastie/Papers/ESLII.pdf), we see the following expansion of a polynomial kernel with degree 2: ...
0
votes
1answer
29 views

Relevant Dimension Estimation: Showing that $\sum_{i=1}^N s_i^2 = ||y||^2$

In relevant dimension estimation, we are given a Kernel Matrix $K \in \mathbb{R}^{n \times n}$, where $K_{ij} = k(x_i, x_j)$. We then compute the kernel eigenvector from the multiple solutions of the ...
0
votes
0answers
11 views

The KL-divergence kernel based method

I have read some papers about applying KL-divergence on kernel method, but they don't give any details about why this KL-divergence kernel is positive definite, which confuses me a lot. So does anyone ...
0
votes
1answer
70 views

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

I thought functional analysis was long thought to be old fashioned and generally a dead research area. It seems that all of a sudden there is a huge fascination with so-called reproducing kernel ...
0
votes
1answer
27 views

Kernels and Features

I am studying about kernel ridge regression and please bear with me, I have a couple points that left me very startled. Here is the equation for Kernel ridge regression: $f^{ridge}(x) = \phi(x)^T\...
2
votes
1answer
23 views

Computational analysis kernel trick

I was reading through "kernel trick" since I wasn't familiar with it. It is my understanding that apart from a better classification boundary (literally the geometric boundary) there should be some ...
0
votes
0answers
41 views

Sum of two kernel is also a kernel, how can we prove that? [duplicate]

Suppose that k(·, ·) and k 0 (·, ·) are kernels. Prove that l(·, ·) where l(x, y) = k(x, y) + k0 (x, y) is also a kernel. I am having trouble proving this, can you help?
0
votes
0answers
38 views

What are other nonlinear transformation methods in machine learning except Neural Network activation functions?

One advantage of the MLP neural networks is the nonlinear transformation used on raw features. The popular ones used are the activation functions like Sigmoid, Tanh, ReLU, Leaky ReLU, etc. They are of ...
0
votes
0answers
33 views

Linear separation in higher dimension [duplicate]

I am having a problem comprehending with the relation of kernel, weight and linear separation. I have a case where I am given a kernel $k_1$. that has a corresponding mapping $\phi_1$. And we ...
1
vote
2answers
153 views

What kind of kernel is used by statsmodels.nonparametric.kernel_regression.KernelReg?

I am doing multivariate nonparametric kernel regression using the Python function as mentioned in the title. The documentation can be found here: https://www.statsmodels.org/stable/generated/...
0
votes
0answers
25 views

Reproducing kernels: how do I numerically compute the decomposition?

Suppose I'm given a kernel, $$ K(x,y) : \mathbb{R} \times \mathbb{R} \rightarrow \mathbb{R} $$ In order to describe/understand the (unique) associated RKHS, I seek its eigenfunctions, as per Mercer'...
0
votes
0answers
39 views

R - Gamma estimates in Kernel Ridge Regression

I am running a Kernel Ridge Regression in R. Mathematically, the minimization problem to be solved is the following: $$ \min_{\boldsymbol{\beta} \in \mathbb{R}^{d}} \ \sum_{i = 1}^{n} (y_{i} - \left \...
0
votes
2answers
67 views

Intuition behind the length-scale of the Rational Quadratic Kernel

What is the meaning of the length-scale in a rational quadratic? \begin{equation} k_{\textrm{RQ}}(t, t') = \sigma^2 \left( 1 + \frac{(t - t')^2}{2 \alpha \ell^2} \right)^{-\alpha} \label{eq:...
0
votes
1answer
25 views

When kernels are not useful in SVM?

In SVM using kernels we map the original features to the higher, transformer space (feature mapping) and then perform linear SVM in this higher space. But when kernels are not useful? I could not find ...
0
votes
1answer
90 views

RBF kernel mapping

I was reading that the Gaussian/RBF kernel maps its input onto the surface of normalized hypersphere. Our RBF kernel given by: $k(x,z) = exp(\frac{- ||x-z||^2}{2\sigma^2})$ Can anyone explain why ...
1
vote
0answers
9 views

Is there a representer theorem for unsupervised learning (to justify kernel density estimation)?

In supervised learning, we get a representer theorem by considering regularized losses of the following form: In Kernel Density Estimation, we simply directly assume densities of the form Could this ...
2
votes
1answer
30 views

Can SVM with Gaussian RBF kernel separate all kinds of data theoretically?

Gaussian is well known because its corresponding feature mapping is to infinite dimension. So with finite number of training data, is that the case that we can achieve zero training error with some ...
0
votes
0answers
36 views

The role of Fisher information matrix in Fisher kernel

I read the original paper proposed the Fisher kernel. The Fisher kernel is defined as $K(X_i,X_j) \propto U_{X_i}I^{-1}U_{X_j}$, where $U_X$ is the Fisher schore and $I$ is the Fisher information ...
1
vote
0answers
44 views

Kernlab, user-defined kernel on chosen variables [closed]

I want to make a user-defined kernel with different variables in the kernel and combine them. Does anyone know if this is possible with kernlab or what is wrong with my code? I use these packages: <...
0
votes
0answers
207 views

Gaussian process vs. Bayesian linear regression / computational cost in weight space

Gaussian process (GP) regression with the linear covariance function $$k(x_i, x_j) = \sigma_0^2 + \sigma_1^2 x_i x_j + \delta(i=j)$$ can be seen as a Bayesian linear regression (BLR) model $$ y_i = ...
0
votes
0answers
98 views

Earth Movers Distance and Maximum Mean Discrepency

By Kantorovich-Rubinstein duality the Earth Movers Distance (EMD)/Wasserstein Metric is equivalent to Maximum Mean Discrepancy (MMD) correct? See here for a more thorough explanation. Why then does ...