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

Kernel and polynomial features transformation [duplicate]

How I can show that the running time of processing the data produced by polynomial features transformation through SVM classifier is better when we use kernel vs if we did not use kernel. PLEASE DO ...
1
vote
1answer
21 views

count Number of unique common substrings using kernel

We have two strings consist of characters. we define kernel of two strings as number of unique common substrings. how to proof number of unique common substrings is a valid function for kernel? for ...
0
votes
0answers
11 views

Approximating a predictor with a kernel

Assume that some predictor $f$ is a kernel machine, but the kernel function $K(\cdot, \cdot)$ is unknown. Is there a way to recover the kernel $K(\cdot, \cdot)$ that "best approximates" $f$? ...
-2
votes
0answers
22 views

Kernel procedure [closed]

I am reading a book now and currently in the SVM section and reading about the kernel. I just wanted to get some examples of situations when the use of kernel procedure is more efficient in terms of ...
0
votes
0answers
26 views

Implementing Hadamard Kernel [closed]

I want to use Hadamard Kernel for classification with SVM and trying to implement the following kernel function. Here is my implementation in Python using numpy: <...
2
votes
0answers
21 views

In the broadest sense, what is a “kernel”?

In MCMC sampling methods, a transition kernel, as found in Metropolis(/Hastings) algorithm, is the comparison of the likelihood of the current position and the likelihood of the proposed position. ...
0
votes
0answers
16 views

Cross validation for kernel regression

I've been reading about the Kernel trick, where we we can obtain a prediction by calculating: $\hat{y} = y(K(x,x)+\lambda I_n)^{−1} K(x,\hat{x})$, where $K(x,z) = (1+xz)^p$. If I want to tune the ...
1
vote
1answer
31 views

What is it called when you find the best fit in an RKHS to some training data?

Suppose I have a series of labelled training inputs $(x_i, y_i)$, and a kernel function $k$ on the input domain, with a corresponding RKHS $H$. Now form the Gram matrix $A$, where $A_{ij}=k(x_i, x_j)$....
2
votes
1answer
29 views

Prove that the following matrix is positive definite

We define $K_{\mathbf{a}, \mathbf{b}}$ as the $n \times m$ matrix whose $ij^{th}$ entry is $\kappa(a_{i}, b_{j})$ Where, $\kappa$ is a (positive definite) kernel function. Here, $\mathbf{a}_{i}, \...
0
votes
0answers
23 views

Is $k(x, x') = 1$ if $x = x' $ and $k(x, x') = 0$ otherwise a valid kernel function?

Is $k(x, x') = 1$ if $x = x' $ and $k(x, x') = 0$ otherwise a valid kernel function? I can't prove the Gram matrix is positive semi-definite. I was wondering if we can find a basis function $\phi: X \...
1
vote
1answer
25 views

Why is there a discrepancy between the eigenvalues of the covariance matrix (PCA) and the eigenvalues of the kernel matrix (kernel PCA)?

I've done PCA on my data matrix $ \mathbf{X} $ which gives me i.a. the eigenvalues $ \lambda $ and eigenvectors $ v $ of the data covariance matrix $ C=\mathbf{X}^T \mathbf{X} $. I'm now extending my ...
2
votes
1answer
30 views

Computing sample variance

Anyone could help with this question on my homework? I managed to substitute f into the expression, and express the denominator as a summation of kernels. However, I am not sure what should I do with ...
1
vote
1answer
32 views

the kernel trick and linear regression

This question is inspired by this and the answer by Hamed. Let us say the underlying data generation process is: y = 3x + sin(x) So pretty non linear. I ...
0
votes
0answers
10 views

Standardized inputs in KRR

Say we have N observations of a function f and that one wishes to obtain an approximation of f by using Kernel Ridge Regression. I read that it was recommended to standardize the inputs. So, when one ...
1
vote
0answers
37 views

How to use sklearn's Gaussian Process Regression parameters?

I have been trying to play around with Gaussian process Regression. I have constructed a fake 1D data for this. I am using a Squared exponential kernel. I solved the regression problem using inbuilt ...
1
vote
0answers
19 views

How to extend kernel-based classifier to non-euclidean space like SO3

What is the proper way to extend kernel-based classifier to non-euclidean space like SO3? This kind of situation happens a lot in robotics, where the data points all live in a specific manifold. (Note:...
0
votes
0answers
18 views

Squared Exponential Basis Function - Can you explain the dimensionality please?

So I am studying kernel functions and I am stuck on a problem. For a squared exponential kernel $\kappa(\mathbf{x}_i,\mathbf{x}_j) = \sigma_f^2 \exp\left(-\frac{1}{2l^2} (\mathbf{x}_i - \mathbf{x}_j)...
1
vote
0answers
19 views

Can someone improve my feeble understanding of feature maps and kernels?

I am taking the course and the extent in which we've discussed feature maps and kernels is as follows: Given Obviously we cannot use linear regression. Instead we map it to a space where it becomes ...
0
votes
0answers
25 views

Kernel PCA stopping rule / criterion

I have been comparing dimensionality reduction methods, while performing KPCA, I didn't know what number of PCs I should retain, how many to take and decide : "there it is, this is the new ...
0
votes
0answers
7 views

What is the Perceptron Kernel predictor function?

I am trying to implement a kernalised perceptron, and one thing that I can't understand is what at the end is the predictor function and how do we use it? I know that the update rule is $$\left (y_i \...
3
votes
1answer
66 views

In this example, which of these vectors are support vectors?

The hyperplane of hard margin SVM with $\phi$ kernel is calculated as following that input space using $\phi$ to map to higher dimension space. $$f(\phi(x))=4\phi_1(x)+9\phi_2(x)+4\phi_3(x)$$ $$ \phi(...
2
votes
1answer
35 views

intuition behind Cover's theorem?

I was going over https://en.wikipedia.org/wiki/Cover%27s_theorem And I am a bit lost with the intuition. I do understand that if it's not linearly separable, then projecting it into a higher-...
4
votes
2answers
187 views

Meaning of “Distribution over functions” in Gaussian Processes?

I'm reviewing PyMC3's Gaussian Process documents and it's illuminated that I might have a flawed understanding of what "distribution over functions" actually means. Consider the below code: <...
0
votes
0answers
11 views

Ambiguous kernel graph for Gaussian processes in Pattern Recognition and Machine Learning

In the book Pattern Recognition and Machine Learning, the author shows these graphs in the context of Gaussian processes for regression (section 6.4.2) and states, "One widely used kernel ...
2
votes
0answers
25 views

What is the difference between pairwise kernels and pairwise distances?

What is the difference between pairwise kernels and pairwise distances? I frequently came across terms like pairwise kernels and pairwise distances while learning about Pairwise metrics, Affinities, ...
1
vote
0answers
47 views

Prove that $K(x_{1},x_{2})=f(x_{1})K_{1}(x_{1},x_{2})f(x_{2})$ is symmetric positive definite if $K_{1}(x_{1},x_{2})$ is symmetric positive definite

I have been trying to prove this 5th proposition on the 25th slide We can prove that $ K(x_{1},x_{2}) $ will be a valid kernel as: \begin{align} K(x_{1},x_{2}) = & \; f(x_{1})K_{1}(x_{1},x_{2})f(...
1
vote
0answers
35 views

Convolution kernels

Below are two different convolution kernel formulas, h and H, written in Python which I think are both symmetric. What is the ...
2
votes
0answers
30 views

Interpretation of the alpha parameter in the Rational Quadratic Kernel

I've been working on Gaussian processes and a problem that keeps bugging me is the alpha parameter on the rational quadratic kernel I know that the rational quadratic is an infinite sum of squared ...
1
vote
1answer
111 views

Is it possible to find cluster centroids in kernel K means?

Suppose ${x_1, \ldots, x_N}$ are the data points and we have to find $K$ clusters using Kernel K Means. Let the kernel be $Ker$ (not to confuse with $K$ number of clusters) Let $\phi$ be the implicit ...
0
votes
0answers
13 views

In classical kernel regression, is there a specific task which responds almost exclusively to a single kernel choice?

I'm curious if there is any well-known kernel regression/classification task which can only be "solved" using a specific choice of kernel?
0
votes
0answers
15 views

Why minimize radius in support vector clustering

I have recently started studying machine learning on my own. I am reading support vector machines and then support vector clustering. https://papers.nips.cc/paper/2000/file/...
3
votes
1answer
37 views

difference between the “Kernel Convolution” and “Kernel PCA”

Can anybody explain the difference between the "Kernel Convolution" and "Kernel PCA" to me, please?
0
votes
0answers
21 views

Nonlinear regression with multiple outputs

I'm trying to learn a smooth, nonlinear mapping between regions of $\mathbb{R}^2$ by doing a regression. In the past, I've used Gaussian process regression to learn similar mappings where the output ...
6
votes
1answer
34 views

two times square in distance calculation on one example?

I read a book on Kernels, See the following example. Why the authors take square two times here? what is the logic?
1
vote
0answers
30 views

how to find a feature map

I have a dataset and it's 2 concentric circles centered at 0 of radius 1 and 2 corresponding to the two different classes. It's easy to seperate the data to get a classifier with 100% accuracy (I'm ...
0
votes
0answers
59 views

How to use the kernel trick on a XOR-like dataset

Let's say that I have the following data: I want to find a transformation of this dataset that will make it linearly separable. My thought was to bring the data around the origin and then multiply $...
1
vote
1answer
42 views

How do we come up with the SVM Kernel giving $n+d\choose d$ feature space?

I was going through the CS229 notes on SVM and Kernel tricks and I came across the following line. More generally the kernel $K(x,z)=(xTz+c)^d$ corresponds to a feature mapping to an $n+d\choose d$ ...
5
votes
1answer
113 views

Probability density from Hilbert-Schmidt integral operator

The Hilbert-Schmidt integral operator determines the underlying measure, if a universal kernel is used. Now, do eigenvalues of the Hilbert-Schmidt integral operator determine the underlying measure up ...
1
vote
2answers
92 views

Why is Dirac kernel positive semi-definite?

I read a paper Weisfeiler-Lehman Graph Kernel. In this paper, it says: Let the base kernel $k$ be a function counting pairs of matching node labels in two graphs: $k\left(G, G^{\prime}\right)=\sum_{v ...
0
votes
1answer
35 views

Why is the Dual Formulation a valid reparametrization of a regression model

In polynomial regression problems, in which an input vector $\underline{\phi}(\underline{x})$ is used to map a feature vector to a higher dimensional space (an example of this being $(x_{1}, x_{2}) \...
0
votes
2answers
46 views

Relationship between structural or statistical properties and hardness of classification

I am trying to understand the relationship between structural or statistical properties of training dataset and hardness of classification in the context of binary classification with SVM using RBF ...
1
vote
0answers
30 views

Kernel ridge regression and Gaussian Process Regression

One knows that through the both methods mentioned in the title, in regression setting, with the same kernel $K$, the result is the same. It may be a very naive question but why? To me, they are quite ...
1
vote
1answer
55 views

Proving that a function is not a kernel function

The function is defined as $k(x,x')=||x||$ Norm in Hilbert Spaces can be defined as $||x||= \sqrt{x^Tx} $. I am not sure about the feature map of this function that how will it be and I am positive ...
4
votes
1answer
47 views

Prove that a function is not a kernel

$k(x,x') = \alpha k_1(x,x) + \beta k_2(x',x')$ is a kernel if $k_1$ and $k_2$ are kernels Prove that this statement is false for all $\alpha,\beta \in \mathbb{R}$ How to check for symmetricity of $k(x,...
0
votes
0answers
62 views

Feature map of Polynomial Kernel

The polynomial kernel is defined as $k(x,x') = (\langle x,x' \rangle +c)^m $ The feature map for polynomial kernel as introduced by my lecturer is given as $\phi:x \mapsto c_i(x_1^{i_1}+x_2^{i_2}+x_3^{...
2
votes
0answers
31 views

How can I model interactions between two groups of features using kernel methods?

Basically I am looking to fit a linear regression model using two groups of features that are completely different in nature (genomic data and say... weather data). I'm looking to extract main effects ...
0
votes
0answers
17 views

Posterior Gaussian process covariance operator

In Gaussian processes, we often see updates for the posterior covariance matrix at a set of points. However, the posterior covariance is actually an infinite dimensional operator. We often see the ...
3
votes
0answers
142 views

Does training loss go to zero in kernel regression?

Edit Have left the original post in tact, scroll to bottom for updated thinking High Level Problem Statement While studying kernel regression, after playing around with some linear algebra, I appear ...
1
vote
1answer
41 views

What is a natural way to define RKHS over mixed spaces (discrete and continuous)?

It is well known that given a kernel $k$ over any space $\mathcal{X}$, there is a corresponding RKHS (Reproducing Kernel Hilbert Space) associated with the kernel $k$. For example, Radial basis ...
0
votes
0answers
20 views

Dimensionality problem in dual SVM regression formulation

Consider the Boston Housing dataset. If we denote the house price with $y$ and the vector of predicting variables with $x$, then the Kernel SVMs are solved by considering the following dual convex ...

1
2 3 4 5
13