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
343 views

Prove sum of slacks in SVM is an upper bound on the number of misclassified examples

How can we Prove that the sum of slacks $\sum \xi_n$ from the objective function of the SVM formulation with soft margin is an upper bound on the number of misclassified training examples? Some ...
1
vote
1answer
751 views

What is the difference between explicit and implicit mapping in SVM?

1) What is the difference between explicit and implicit mapping 2) What is the difference between mapping and kernel trick?
4
votes
1answer
2k views

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

How can we prove that the normalized kernel is a kernel? That is how can we show $\frac{K(x,y)}{ \sqrt{( K(x,x) K(y,y) )}}$ is a valid kernel. Question: Also in real world, why do we normalize the ...
1
vote
1answer
50 views

Conceptual Understanding of Kernels

I'm currently reading up on Kernels specifically related to SVM. My understanding of Kernels is that the data points are projected to another dimension and an ...
-1
votes
1answer
48 views

How to decide an SVM kernel is linear or not?

I found the definition of SVM polynomial kernel is $$K (x, x′) = (1 + (x · x′))^p$$ I want to know why it add $1$? Does the kernel $K (x, x′ ) = (x · x′ )^2 $ a linear kernel or a polynomial kernel? ...
4
votes
1answer
831 views

SVM kernels and decision boundaries

I trying to figure out intuitively how the kernel trick gives rise to a decision boundary. I've always thought of SVMs as hyperdimensional spaces with a decision plane dividing them up and I'm trying ...
3
votes
2answers
103 views

Distribution Regression with Kernel Mean Embedding

I'm interested in doing distribution regression with Kernel Mean Embedding with a variety of kernel methods (SVM regression, Ridge Regression, Gaussian Process). Typically in distribution regression, ...
0
votes
1answer
232 views

Relationship between PCA and KPCA

The relation between PCA and KPCA seems somewhat confusing. Basically, the Kernel variant of PCA can be described as constructing the normalized kernel matrix of the data $n \times n$ (n is the number ...
2
votes
2answers
2k views

(SVM) Difference between linear kernel and polynomial kernel of degree 1?

I am new to machine learning. Could anyone tell me the difference between linear kernel vs. polynomial kernel of degree 1 wrt SVM (if there is any difference)? The reason I asked, I am getting ...
2
votes
0answers
233 views

Influence kernel function for Kernel Ridge Regression and Support Vector Regression

I am currently exploring two regression methods using kernels, namely Kernel Ridge Regression (KRR) and Support Vector Regression (SVR). I tune their parameters using a randomized grid search. Using ...
1
vote
1answer
144 views

Kernel Regression

In Kernel Regression with a linear kernel, we have $$\beta = X\alpha = X^T(XX^T+\lambda I)^{-1}Y$$ and the normal Ridge Regression solution is $$\beta = (X^TX+\lambda I)^{-1}X^TY.$$ How can you prove ...
0
votes
1answer
125 views

Number of coefficients in SVM solutions

We know that the SVM optimization problem with n data points has a solution in the form of $$f(x)=\sum_{i=1}^n a_i k(x_i,x)+b$$ which has n+1 coefficients. But as I understands it we don't ...
7
votes
0answers
794 views

What is the deep(er) math that makes the 'kernel trick' in SVMs work?

The kernel trick gets used very heavily in SVMs. And it is impressive: not only can you get the inner product in a larger-dimensional space (including an infinite-dimensional one) that comes from a ...
1
vote
1answer
814 views

Python - (SVM) Why is my Gram matrix not positive definite?

I am writing a support vector machine with 1-norm soft margins in Python, using the quadprog quadratic programming package. As far as I can tell, by using the Gaussian kernel I should be guaranteed a ...
1
vote
1answer
1k views

Formulation for kernel k-means

Given $n$ points ${\boldsymbol{x_1},...,\boldsymbol{x_n}}$ and a nonlinear feature map $\Phi$, the kernel k-means problem is formulated as follows, $\underset{\boldsymbol{t}, \; \boldsymbol{\mu}_k \; ...
0
votes
0answers
174 views

Why shouldn't we scale data before entering into KPCA?

In Kernel Principal Component Analysis (KPCA), data comes in as a $n\times d$ matrix $X$ where $n$ is the number of observations and $d$ is the number of features. The process has been explained in ...
0
votes
0answers
55 views

Kernelled Regression

I am trying to implement Protocol 3 mentioned in the paper On-line Prediction with Kernels and the Complexity Approximation Principle. I have written the following code in R using polynomial kernel: <...
3
votes
1answer
4k views

Feature scaling in svm: Does it depend on the Kernel?

It is often recommended to do feature scaling (e.g. by normalization) when using a Support Vector Machine. For example here: When using SVMs, why do I need to scale the features? or also on ...
1
vote
1answer
558 views

KernelPCA from sklearn doesn't return original data

If I do a transform and then an inverse_transform using PCA, I of course get the original data back. If I do the same for KernelPCA, I don't. Is this a property of kernelPCA or a shortcoming of the ...
0
votes
1answer
87 views

Are Gaussian Process learning problems well defined with only a covariance function?

Lets consider a simple derivation of GPs I've seen. Given a dataset $ ( X, \vec{y} ) = (\vec{x}_i, y_i)_{i=0}^N $, we wish to find a function $ f $ such that $ y_i = \vec{w} \cdot \vec{\phi}(\vec{x_i}...
0
votes
1answer
2k views

Conjugate prior for inverse Gamma with known scale parameter

Suppose $Y \sim \text{Inverse Gamma}(\alpha, \beta)$ with scale parameter $\beta$ known, and $\alpha$ unknown, and the pdf is given by $$f(y) = \frac{\exp(-1/\beta y)}{\Gamma(\alpha) \beta^\alpha y^...
3
votes
1answer
48 views

Do you need to store entire training set when using RBF kernel?

When you use a model that has been trained based on the RBF (Gaussian) kernel, do you need to store the entire training dataset to compute similarity features? If so, why doesn't this decrease the ...
1
vote
0answers
206 views

How to represent a non-trivial kernel as a Gram matrix? [closed]

Given a kernel, can we represent it as a Gram matrix? For example, a linear kernel can be presented (in Python/MATLAB code) in a ...
2
votes
2answers
368 views

Is alpha*RBF a valid kernel, where alpha >= 0 is a parameter?

I wonder if K = alpha*RBF can be a valid kernel satisfying Mercer's condition, where ...
2
votes
1answer
178 views

A bunch of questions about Kernels in Machine Learning

i've read many topics on this platform about this topic but i still have some questions, mainly theoretical. We are dealing with ML, so if we are here means that we have to classify with linear ...
5
votes
1answer
360 views

Negative values of hyperparameters in Gaussian Process

I am trying to optimize the hyperparameters for a Gaussian process. I am using a squared exponential kernel, where I am optimizing three parameters. $$k_y(x_p,x_q) = \sigma^2_f \exp\left(-\frac{1}{2l^...
2
votes
2answers
4k views

SVM: How to get predicted output from SVM with Gaussian / RBF Kernel? Andrew Ng's course svmPredict

I've been learning machine learning through Andrew Ng's Coursera. I've completed Andrew's homework on SVM, but it felt wishy washed and I'm having hard time taking it from 0 to finish. Say you ...
6
votes
1answer
3k views

Kernels in Gaussian Processes

I am trying to understand intuitively how a kernel works in a Gaussian process. I know that GP are distributions over functions, in short you have the model $y = f(x)+\epsilon$ and the $f(x)$ follows ...
2
votes
0answers
28 views

Is there a relationship between RKHS and mixtures?

Reproducing kernel Hilbert spaces (RKHS) (see here or here) seem to involve conic combinations of "kernel functions" (my understanding is very crude). (See pp. 34-35 of Behrends, unfortunately the ...
1
vote
1answer
110 views

Prediciting an output with (kernelized) ridge regression

The optimal weight w* for ridge regression is ($\lambda$ is a positive scalar): $$w^* = (XX^T+\lambda I_n)^{-1}Xy$$ I want to predict the output for a new datapoint $x_i$, whereby $w^*$ is already ...
1
vote
0answers
1k views

Proving that kernels are closed under addition and scalar multiplication

We have to show that given k_1 and k_2 are both kernels, the sum k_1 + 2*k_2 is a kernel as well. I am attempting to show this by using Mercer's theorem: $k(x,y) = <a(x),a(y)>$. Showing that $...
1
vote
1answer
391 views

Does SVM get biased towards majority class in case of imbalanced class proportion?

After reading many posts, I thought of asking: Why should a SVM be biased towards majority class like other classifiers, since an SVM never used the whole data of the training data set—it only uses ...
0
votes
1answer
470 views

If the linear kernel function is the same as RBF with sigma = inf, then what is happening when the kernel scale is changed with a linear SVM?

From another answer here, I was linked to a paper: Linear kernel and non-linear kernel for support vector machine? http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.141.880&rep=rep1&...
2
votes
1answer
2k views

Polynomial kernel feature space?

Given a kernel with the form: and x,z in R^n, how do you prove that the feature space is (n+d) choose n? Note: sorry the rest of the question is not in Latex as I do not yet have enough reputation to ...
2
votes
0answers
75 views

Kernel Alignment and Ideal Kernel

Why is $yy^T$ known as the ideal kernel? (Where $y$ is the vector of class labels and $y \epsilon \{-1,1\}$ ) Also, what does Kernel Alignment with the ideal kernel help find?
4
votes
3answers
615 views

A Kernel Two Sample Test and Curse of Dimensionality

Gretton et al describes the Kernel Maximum Mean Discrepancy, a measure of distance between distributions. In order to compare two distributions, it turns out you can do much better than, say, taking ...
3
votes
1answer
555 views

Principal Component Analysis on Graphs

How can somebody apply PCA on a set of graphs? Is it possible to define a meaningful graph kernel for my problem, and then follow the typical procedure on the derived matrix of pairwise distances (...
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+\...
1
vote
0answers
171 views

Kernels in SVM vs Kernels in Non Parametric Density Estimation (in Statistics)

Is there a relationship between the Kernels used in context of SVM(or kernel machines) and the Kernels in non-parametric density estimation in statistics? Are they conceptually very different but ...
1
vote
0answers
165 views

Proving a string kernel

Let $\mathcal{S}$ be the set of strings of length at most $100$, drawn from a finite alphabet $A$; for any $s \in \mathcal{S}$, $s = a_1 , . . . , a_{100}$ where each $a_j \in A$. Let $\mathcal{K} : \...
2
votes
1answer
53 views

Is there any common point between Deep Learning and Kernel based Strategies like SVM?

Let’s take for example a binary classification task To me it seems that both Deep Learning and Kernel based Methods seem to share the idea of not trying to learn a complex classification function ...
1
vote
1answer
221 views

How to understand the predicted **negative** values by Kernel Regularized Least Squares (KRLS)?

I am learning the prediction algorithm, Kernel Regularized Least Squares (KRLS). The predicted values are listed in the follows: $$\hat{y} = K((K + 1 \times I)^{-1}y)$$ For example, I have 100 ...
0
votes
1answer
513 views

Dimensionality of the Gaussian Kernel

I have read that the dimensionality of the feature map of the Gaussian Kernel is infinite. However I saw another post (Kernel SVM) stating that the feature map for a Kernel SVM maps to a ...
2
votes
1answer
1k views

Prove that this kernel is a valid kernel

How would you argument or prove that this is a valid kernel: $$ K_a(x, t) = \prod_{i=1}^{n} (1 + x_it_i + (1-x_i)(1-t_i)). $$ I know that there are two conditions that a kernel must satisfy to be a ...
0
votes
1answer
204 views

Extension of the Nearest Neighbor classifier within each class

Let's consider a classifier that for each new sample ($x_i$), finds the nearest neighbor ($x'^k_j$) for each class $k$ present in the training data computes the corresponding distances: $d(x_i, x'^...
0
votes
1answer
463 views

Validating Kernel Functions

I'd appreciate help in clarifying my understanding of how to valid kernel functions, using the following two examples: $K(x, t) = x^Tt - (x^Tt)^2$ $K(x, t) = e^{(x_1t_1)}$ where $x_1\ and\ t_1$ are ...
1
vote
0answers
225 views

General form of Epanechnikov kernel

This Wikipedia source states the Epanechnikov kernel to be of the form: \begin{equation} k_{n,d}=\left\{ \begin{array}{ll} \frac{1}{2d} \cdot \left(1 + \frac{1}{2n}\right) \cdot \left(1 - \left(\...
1
vote
0answers
32 views

Approximate arbitrary covariance matrix using kernel

I would like to approximate a arbitrary covariance matrix using a kernel. In hear kernel can only be summation or multiplication of each kernel (rbf, linear ,periodic, constant). I don't want to use ...
0
votes
1answer
111 views

Observations made if dataset performs better on Linear Kernel than Polynomial Kernel in SVM and vice versa?

When I run a dataset using Support Vector Machines(SVM) and I am use both Polynomial and Linear Kernels. The performance I obtain is different, so I was wondering if there is any information I can ...
1
vote
1answer
2k views

For a Gaussian kernel, what is the sigma value, and how is it calculated? [duplicate]

For a Gaussian kernel, what is the sigma value, and how is it calculated? $K(\mathbf{x}_i,\mathbf{x}_j) = \exp{-\frac{\|\mathbf{x}_i-\mathbf{x}_j\|^2}{\sigma^2}}$ ? Is it the covariance of the ...

1
3 4
5
6 7
13