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
1
vote
0answers
27 views

Kernel ridge regression with matrix-vector data set $S := \{ X_i, y_i \}_{i=1}^{N}$? [duplicate]

Background: For Kernel ridge regression, I have normally come across the data-set given in vector and scalar form, i.e., $\overline{S}:= \{x_i, \overline{y}_i \}$, where $x_i \in M_{n,1}(\mathbb{R})$ ...
3
votes
0answers
87 views

Kernel function for use in Kernel-PCA given a known piecewise linear true data generating process

If I know that a multivariate dataset has a piecewise-linear data generating process with known knots (or breakpoints), then what is the appropriate kernel function to use in Kernel-PCA? For example, ...
1
vote
0answers
80 views

How to combine multiple kernels of large sample datasets?

I have multiple large sample datasets in matrix format (each has 15000 rows and 5-50 columns) corresponding to different experiments. Each matrix contains the same number of samples(rows) but the ...
1
vote
1answer
64 views

Kernel functions with vector output

Kernel functions are used commonly with SVMs to make classification of non linearly separable data possible - i.e. the Kernel function provides the linear separability. But from looking at Kernel ...
1
vote
1answer
3k views

How to use the squared exponential kernel with multidimensional vector inputs?

I'm constructing an optimization (Bayesian optimization) algorithm using Java code. I have created the program, but the similarity values between inputted vectors in the kernel equation does not ...
4
votes
0answers
811 views

Fourier transform of a Gaussian process

I would like to discuss and ask a question regarding the Fourier transform of a Gaussian process, if it makes sense. For that purpose, let me describe the following situation. Let $z(s)$ be a ...
3
votes
0answers
131 views

Understanding kernel PCA when the target space is infinite-dimensional

The PCA optimization problem is known as $$ \max_{U \in \mathbb{R}^{d\times r}, U^TU = I} tr(U^T\Sigma U), $$ where $\Sigma$ is a covariance matrix of a dataset $\{x_1,\dots,x_n\} \subset \mathbb{R}^d$...
4
votes
0answers
149 views

Are null space of matrix and kernel function same?

I have recently started learning about machine learning and have come across kernels and null spaces. I understand that null space is the set of all vectors that satisfy the equation A.v = 0 (Where A ...
1
vote
0answers
24 views

kernel publications

What are some contemporary papers that provide the reader with a complex overview of kernel functions used nowadays in machine learning?
1
vote
0answers
37 views

eigenvalue perturbation theory for kernel function

Let $S=\{x_i\}_{i=1}^n$ be a set of training examples, and let $K\in \mathbb{S}^n_+$ be the kernel matrix induced by $S$ and some kernel function $k$ (i.e., $K_{ij}=k(x_i,x_j)$). I was wondering how ...
2
votes
1answer
371 views

How to calculate RKHS norm of a function under given kernel transformation

This was a question asked before in mathoverflow but not yet got answered. I have the same problem when reading Srinivas et al (2010) [appendix B]'s paper. Here are my problems: Definitions: ...
1
vote
0answers
211 views

Kernel function from polynomial basis functions

In chapter 3 & 6 of Bishop's Pattern Recognition and Machine Learning, he showed that the equivalent kernel based on eqn (3.62) $$ k(x,x') = \beta \phi(x)^T (\alpha I + \beta \Phi^T \Phi )^{-1}\...
3
votes
1answer
308 views

Are Matérn class kernels universal kernels or not?

This is a question that I can't find the solution. I don't know it is a open question or it is a well-known result that can be attained from several lemmas. Here are the definition of Matérn class ...
2
votes
1answer
279 views

What is the motivation or objective for adopting Kernel methods? Is kernel trick a feature engineering method?

I come to know that kernel methods can be used in not only SVM but also many machine learning algorithms. I understanding that in SVM, the reason for using kernel trick is that some data are linearly ...
0
votes
0answers
103 views

What does it mean to have Covariance > 1 in Gaussian Processes? (Or Cov(x, x) != 1?)

The sum of two kernels is a kernel. [. . .] The product of of two kernels is a kernel. - Gaussian Processes for Machine Learning, Section 4.2.4 I can quite easily see how the product would work: ...
1
vote
1answer
1k views

Gaussian Process instability with more datapoints

I'm working my way through Rasmussen and Williams' classical work Gaussian Process for Machine Learning, and attempting to implement a lot of their theory in Python. I've attempted to fit a sin(x) ...
1
vote
0answers
95 views

Kernels property: integral of kernel product $\propto k(x,y)$

Let $k$ be a kernel function (symmetric and semi-positive definite function). Does the following relationship hold: $\int_{-\infty}^{+\infty}k(x,u)k(y,u) du \propto k(x,y)$ ? Or for what type of ...
4
votes
2answers
380 views

RKHS for polynomial kernel

Say we have a polynomial kernel of degree two: $k(x,x')=\langle x,x' \rangle^2$ for $X=\mathbb{R}^2$. I know that a feature map $\phi(x)=(x_1^2,\sqrt{2}x_1x_2,x_2^2)$ exist. What I want to know is ...
0
votes
1answer
264 views

SVM: Maximal number of components kernel PCA versus linear PCA

I'm comparing the Support Vector Machines (SVM) formulation of linear PCA with kernel PCA. I know that in linear PCA, the maximum number of principal components is equal to the dimension of the input ...
0
votes
1answer
369 views

How to tune bandwidth in machine learning kernel model?

Gaussian kernel $k(x,y) = \exp(-\lVert x-y \rVert^2/\sigma^2)$ has a hyperparameter $\sigma$. I know grid search cross validation, but this would require a lot of computation since computational ...
1
vote
0answers
123 views

Sum of two Poly Kernels

I have a questions from assignment about sum polynomial Kernels : If I have Poly Kernel $k_1$ =$(α_1 x\cdot y+β_1)^d$ and mapping $\varphi_1$ and kernel $k_2$ =$(α_2 x\cdot y+β_2)^d$ with mapping $\...
2
votes
0answers
133 views

A kernel $K_1$ maps from $R^n$ to $R^m (m>n)$ and is linearly separable. Given a different kernel $K=K_1+K_2$ will we still find a linear classifier?

Just started learning about SVM, kernels and all those things. Got stuck on this question (homework question): Consider a kernel $K_1$ and its corresponding mapping $φ_1$ that maps from the lower ...
0
votes
1answer
704 views

How does the shape of a decision boundary in relate between the original and kernel feature space?

I'm trying to get my head around the mathematics and implementation of SVM and hopefully gain some intuition into how kernels work and perhaps being able to, with a bit more confidence, define my own ...
1
vote
0answers
151 views

why kernel method is not overfitting?

A question comes to my mind and confuses me: Simply consider kernel method for regression. If kernel method is equivalently solving a infinite dimensional linear regression problem, then there should ...
11
votes
2answers
335 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 ...
0
votes
1answer
56 views

Dropping the exponent of the Gaussian Kernel

I am wondering, for the Gaussian kernel $$k(x_n,x_m) = \exp(- \frac{\theta}{2} \lVert x_n-x_m\rVert^2)$$ whether we really need the exponent. What are the consequences of just using $$k(x_n,x_m) = ...
0
votes
1answer
24 views

Does there exist a vector α st the equality holds?

A training set $(x_1,y_1),...,(x_m,y_m)$ is generic iff $x_i=x_j$ then $y_i=y_j$ and let's consider the following kernel $K_a(x,t)=\prod_{i=1}^n(1+(x_it_i)+(1-x_i)(1-t_i))$ Given a generic training ...
3
votes
1answer
55 views

The trace term in 2 Wassersteins metric for Gaussians

I was looking at the formula for 2 Wassersteins distance for Gaussian distribution on Wikipedia. https://en.wikipedia.org/wiki/Wasserstein_metric#Normal_distributions It satisfies all properties of a ...
2
votes
2answers
197 views

addition of a kernel and a function

I have this problem. My approach would be to take a Kernel matrix of $ \ k(x,y) $ as it is positive semidefinitive. And if I am able to make $ \ k'(x,y) $ a kernel matrix, then I can prove that it ...
1
vote
1answer
554 views

How to understand effect of RBF kernel for kernel PCA

I understand the math in kernel PCA and with RBF kernel, and I also understand that the RBF kernel map the data into a infinite dimensional space. I know that for SVM, mapping the data into a higher ...
1
vote
0answers
57 views

How to kernalize a logistic loss based regularized ERM optimization problem?

Given $\{\mathbf{x}_i,y_i\}, i=1,\ldots,m$, consider the following optimization problem: $\min\limits_{\mathbf{w},b} \sum\limits_{i=1}^{m}\log(1+\exp(-y_i(\mathbf{w^Tx_i} + b)))$ $+\lambda|| \mathbf{...
2
votes
1answer
638 views

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

Is there an absolute need to use a PSD kernel for Gaussian processes (and maybe SVMs?) For example, If I used a Minkowski distance with 0 < p < 1, the function would is not convex, and thus I ...
1
vote
0answers
183 views

The gamma parameter (or kernel width) for RBF Gaussian kernel in kernel PCA

Is there any general way or rule of thumb of how to determine the kernel width for KPCA?
4
votes
1answer
963 views

Intuition of regular SVM vs kernel SVM

I have been trying to understand the difference between a regular Support Vector Machine, and a kernel Support Vector Machine. I have my own intuition, but I'm not sure if it is quite right. Below is ...
9
votes
1answer
480 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)...
5
votes
0answers
137 views

Equivalent Gradients in Kernelized SVM

Let $\varphi: \mathcal{X} \to \mathcal{H}$ a mapping with corresponding kernel $K:\mathcal{X}\times\mathcal{X}\to \mathbb{R}$ (that is, $K\left(x,x'\right) = \left<\varphi\left(x\right), \varphi\...
0
votes
1answer
282 views

Can a kernel be used to define the cardinality of the union of 2 sets?

Given a space $\Omega $ with 2 sets $X\subseteq \Omega $ and $Y\subseteq \Omega $, how can I define a kernel $k(X,Y)=|X\cup Y|$? I know that I can define a kernel $k_1(X,Y)=|X\cap Y|$ by setting $k_1(...
0
votes
0answers
139 views

Prove strictly positive-definite kernel

It can be shown that the Hamming distance defines a positive semi-definite kernel (see e.g., here). However, is the kernel $$ K(\mathbf{x}, \mathbf{y}) = 1 - \frac{1}{n} \sum_{i=1}^n \mathbb{I}\{x_i = ...
3
votes
1answer
461 views

Variance of kernel ridge regression vs Gaussian process

Consider the model $ \mathbf{y} = f(\mathrm{X}) + \epsilon $. Here $\mathrm{X}$ is a fixed $n \times d$ data matrix, and $\epsilon \sim \mathcal{N}(0, \sigma^2 I)$ is iid Gaussian noise. Assume that ...
1
vote
0answers
60 views

Choosing a robust kernel based on dataset properties (theoretical arguments)

Consider a non-linear least squares estimation problem, where we use a kernel (i.e. M-estimator) to reduce sensitivity to outliers,e.g. $argmin_x \sum\limits_{k=1}^n\rho_k(||r_k(x)||_2)$, where $...
3
votes
0answers
548 views

What is the difference between spectral clustering and kernel spectral clustering?

I have been reading about spectral clustering (SC) technique. So far I understood that it is based on computing the similarity between datapoints (using some function like the gausian kernel function) ...
3
votes
2answers
376 views

Kernel functions for vectors in discrete spaces

There are lots of choices for kernel functions $k(\textbf{x}, \textbf{y})$ in continuous spaces (e.g., $\textbf{x}, \textbf{y}\in \mathbb{R}^d$), such as the RBF kernel, etc. However, what are some ...
3
votes
1answer
87 views

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

When fitting a Gaussian process, we use a kernel function to define the covariance matrix. It is well known that if $k(x, y)$ is a kernel function, then $k_1(x, y) = k(x, y)^p$ is also a kernel ...
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 (}{\...
6
votes
1answer
1k views

Proof that $K(x,y) = f(x)f(y)$ is a kernel

I cannot find a proof that $K(x,y)=f(x)f(y)$ is a Kernel for any real valued function $f$ and $x,y\in \mathbb{R}^n$. Obviously it is symmetric but can someone prove that it is positive semidefinite? ...
3
votes
1answer
3k views

Proof that exponential of a kernel is a kernel

How can I prove that the exponential $\exp(K)$ of a kernel function $K$ is again a kernel? I think it can be proved using Taylor expansion but I am not sure how.
3
votes
1answer
1k views

Sample from Gaussian Process across 2D

This seems like a straightforward questions; my apologies if it is already answered (I have looked). Problem: I would like to sample from a Gaussian Process (GP) prior over X and Y coordinates (e.g. ...
2
votes
0answers
576 views

Calculation of nu and gamma in one-class SVM with rbf kernel

I am using python sklearn's one-class svm classifier for anomaly detection. I would like to know can I accurately calculate the required value for nu and gamma for rbf kernel. Is there any equation or ...
1
vote
2answers
4k views

How do I prove such a kernel is positive semi definite? K(x, y) = min(x, y) - xy over [0, 1]

For such a kernel: K(x, y) = min(x, y) - xy over [0, 1] X [0, 1] How can I prove that it's positive semi definite? I know how to prove ...
1
vote
1answer
549 views

Relation of kernels and Cholesky decomposition

I am trying to find an intuition on why we require that kernels are positive semi definite and I have found this: We are given a dataset $X$ of size $n \times d$ where $n$ is the number of samples ...

1 2 3
4
5
13