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

Would removing covariates correlated with model residuals (errors) from training improve prediction in machine-learning or deep-learning? [closed]

Would removing covariates correlated with model residuals (on training data) improve prediction in machine-learning or deep-learning or make the weights calculated more interpretable or useable to ...
1 vote
0 answers
21 views

Is it possible to apply the kernel trick to a "mahalnobis distance learner" such as GLS?

1.https://arxiv.org/pdf/0804.1441.pdf 2.https://www.sciencedirect.com/science/article/abs/pii/S0925231210001165 These papers describe kernelizing a mahalanobis distance learner. I am interested in ...
1 vote
0 answers
12 views

Is there a multilinear kernel principal components analysis?

PCA can be extended to kPCA using the kernel trick. MPCA is a multilinear extension of PCA that involves multiple matrices for the different modes of the data tensor. Can MCPA be similarly extended ...
  • 4,722
1 vote
0 answers
14 views

Is there a difference between kernel PCA with a non-linear kernel vs PCA with a non-linear change of variables?

I see that kernel PCA with a linear kernel is the same as PCA. On Wikipedia's introduction of the kernel to PCA they suggest that there exists a non-trivial arbitrary choice of map $\Phi$ that is ...
  • 4,722
0 votes
0 answers
9 views

Objective of maximal margin classifier with quadratic decision boundary

What is the objective for minimization for a maximal margin classifier with quadratic decision boundary of the form $ x^{T}Ax + b^Tx + c =0 $?
  • 223
3 votes
0 answers
45 views

Relation between generalization bounds of Kernel Ridge Regression and largest eigenvalue of the kernel Gram matrix

Consider a positive-definite, symmetric function $k(x_1, x_2)$ which is used, given the dataset $\{(x_i, y_i)\}_{i=1}^m$, to construct the Gram matrix $K = [k(x_i, x_j)]_{i,j \in 1, ..., m}$. What is ...
  • 31
1 vote
1 answer
43 views

How to derive the three matrices of SVD from eigenvalue decomposition in Kernel PCA?

Kernel PCA is usually done via eigenvalue decomposition of the Kernel Matrix $\mathbf{K}$ and standard PCA via SVD of the input $\mathbf{X}$. In standard PCA as far as I know we can derive $\mathbf{S}...
  • 23
0 votes
0 answers
15 views

How do we find a feature space where our data is linearly seperable and how do we find a kernel for this feature map?

I am dealing with Kernel SVM right now and there is one thing I don't fully understand. As I have understood the only thing we have to know to compute the hyperplane are the expressions of the form $...
  • 61
1 vote
0 answers
26 views

Is it possible to express a decision tree as a kernel machine?

This paper argues that models trained with gradient descent like neural networks can be expressed as kernel machines with an interesting kernel function. The kernel is $$ K(x, x') = \int_{c(t)} \...
3 votes
2 answers
71 views

How kernel functions are related to the similarity between two vectors?

I was reading about regression with Gaussian processes and I bumped into kernel functions. These functions can be expressed as inner products in a new feature space $\mathcal{M}$, that is: $$k(\mathbf{...
  • 131
1 vote
1 answer
37 views

Prove the Laplacian kernel is a valid kernel

By a valid kernel, we mean the Gram matrix induced by it is positive semi-definite (and symmetric). Let $K(x,y)=\exp(-\lambda \|x-y \|)$, where $\lambda >0.$ We say $K$ is a Laplacian kernel. I ...
  • 113
0 votes
0 answers
21 views

How is the value of dot product given by SVM kernel useful?

Take the polynomial kernel for example : $\begin{align} k(\mathbf x, \mathbf y) & = (1 + \mathbf x^T \mathbf y)^2 = (1 + x_1 \, y_1 + x_2 \, y_2)^2 = 1 + x_1^2 y_1^2 + x_2^2 y_2^2 + 2 x_1 y_1 + ...
  • 135
0 votes
1 answer
26 views

How to find a mapping to a higher dimension that separates the data, given a data set

We have the following dataset: $$ \begin{bmatrix} x_1 & x_2 & y\\ +1 & 0 & +1\\ -1 & 0 & +1\\ 0 & +2 & +1\\ 0 & +1 & -1 \end{bmatrix} $$ I was asked to find ...
0 votes
0 answers
20 views

On the choice of kernel in HSIC dependence measure

It is necessary to choose a kernel to use HSIC measure for dependence detection between two distributions, in a sensitivity analysis context for example. Among them, using universal kernel is ...
  • 1
1 vote
0 answers
28 views

Calculating output from kernel

Given the following task: You feed an image $I$ with the dimensions $200\text{x}200\text{x}3$ in the convolutional layer, which consists of $12323$ kernels $K$ each with the size $40\text{x}40\text{x}...
  • 11
0 votes
0 answers
15 views

Using a kenel function which is different from the common set of kernels

The function $f:\mathbb{R}\rightarrow\mathbb{R}$ is a neural network that depends on $\theta$ (model parameters) and $\lambda$ (hyperparameters). Therefore, the surrogate function can be written as ...
  • 101
1 vote
1 answer
53 views

Kernel trick implemented for Ridge Regression

I am trying to see the kernel trick implemented for Ridge Regression. As a first step, I want to rewrite the solution of Ridge regression. I know that: $ \hat{\beta} = (X^TX + \lambda I_n)^{-1} X^T Y $...
0 votes
0 answers
38 views

Reproducing kernel hilbert space norm as smoothness functional

Let $K:X \times X \rightarrow \mathbb{R}$ be a Mercer kernel with an associated RKHS $H$ then the norm $|f|_H^2$ can be used as a way to ensure that $f$ is smooth in $H$. If i understand correctly, ...
2 votes
0 answers
129 views

Pros and cons of Nadaraya–Watson estimator vs. RKHS method?

Recently I've been reading some materials about nonparametric methods. Two methods related to the word "kernel" rasied my interest-- Nadaraya–Watson estimator and RKHS method. What's the ...
  • 21
3 votes
2 answers
55 views

For every x, y ∈ IN = {1, . . . , N} define K(x, y) = min{x, y}. Prove that K is a valid kernel

I need to prove K is a valid Kernel. x and y are positive integers, and K is the minimum of x and y. I know I should prove K positive definite. But May I see how.
0 votes
0 answers
16 views

Finding the derivative of the kSVM classifier funcion with respect to the weight vector?

I would like to try a different approach for defining the kSVM. However to do that at some point I need a derivative of the clasifier function $y(\textbf{x})$ with respect to the weights vector ...
  • 259
9 votes
4 answers
274 views

Bias Variance tradeoff in neural networks

Large neural networks have low bias and high variance. Training on large datasets greatly reduces the variance allowing them to fit complicated functions. My question is why they seem to have much ...
  • 177
2 votes
1 answer
34 views

Is $\min(k_1(x, y), k_2(x, y))$ a positive definite kernel?

It is known that $(x,y)\in \mathbb{R}^2 \mapsto \min(x,y)$ is a positive definite kernel. Can we generalize this result in the following way : Let $k_1(x, y)$ and $k_2(x, y)$ be any two positive ...
  • 259
1 vote
0 answers
24 views

reproducing kernel hilbert space notation

I'm trying to understand reproducing kernel Hilbert spaces (RKHSs) from scientific papers, however I don't find any gentle introduction. However, my main problem, at the moment, seems to be to ...
3 votes
1 answer
51 views

Moore-Aronszajn Theorem and Mercer theorem for the kernel trick

I have been reading about the RKHS and the kernel trick in Machine Learning mainly from https://ngilshie.github.io/jekyll/update/2018/02/01/RKHS.html (1) and https://arxiv.org/pdf/2106.08443.pdf (2). ...
0 votes
0 answers
41 views

Implementing kernel alignment for SVM algorithms

I am trying to understand and re-implement the results from Table 2 in the first Kernel-Target Alignment paper. The task that is being done is a simple classification task using an SVM with RBF ...
0 votes
0 answers
31 views

Can a kernel be constructed from any arbitrary bivariate function?

For a kernel $\kappa(x_i, x_j)$ to be considered valid, it must be symmetric and have a positive semidefinite gram matrix for any set of points $\{x_1,...,x_n\}$ (ref: page 4 of http://www.cs.berkeley....
0 votes
0 answers
11 views

The derivation of the RBF kernel to the inner product form, and what does this notation $\sum _{n_{1}+n_{2}+\dots +n_{k}=j}$ mean?

I have two questions regarding the following derivation: What does this notation $\sum _{n_{1}+n_{2}+\dots +n_{k}=j}$ mean in the following equation? How is it derived from step 3 to step 4, and from ...
2 votes
2 answers
433 views

Universal approximation of Gaussians

Can gaussian kernels reproduce non continuous L2 integrable functions? ( Do non continuous L2 integrable functions lie in the RKHS constructed by a Gaussian Kernel?) Edit: I think my question is being ...
  • 65
1 vote
0 answers
15 views

A question about linear inference in random Fourier feature kernels

In Ali Rahimi's and Ben Recht's paper "Random Features for Large-Scale Kernel Machines," there is a line near the bottom of the introduction which I can not reason about... In addition to ...
  • 639
0 votes
0 answers
20 views

Estimating the Probability in a statistical analysis

I am carrying out a statistical analysis where I run the simulation (Matlab) 5000 times, to get 5000 results. The objective is to estimate the probability of having a result that is less than or equal ...
1 vote
0 answers
44 views

Information preserved in the kernel mean embedding

I have recently been introduced to the kernel mean embedding of distributions, that is the map $$\mu: \mathcal{M}^{1}_{+}(X) \rightarrow \mathcal{H} \\ \mu(P) := \int \phi(x) dP(x)$$ where $K$ is a ...
0 votes
0 answers
16 views

Would l-1 regularization with kernel trick induce sparsity on feature map's features?

Would l-1 regularization with kernel trick induce sparsity on the infinite dimensional feature map's features in the case of gaussian kernel?
0 votes
0 answers
16 views

Would logistic regression/support vector-machine with l-2 regularization and early stopping regularization cause underfitting?

Would early stopping regularization combined with l-2 regularization or in logistic regression/support vector machine cause underfitting? Does a kernel-trick affect what combination of regularization ...
0 votes
0 answers
25 views

Is the exponentiated sum of squared norms a valid kernel function?

Define $$k(x, y) = e^{-(||x||^2 + ||y||^2)}$$ Is this a valid kernel function? My guess is yes, with the feature map $\phi(x) := e^{-||x||^2} \in \mathbb{R}_{>0}$. Then $k(x,y) = \phi(x) \cdot \phi(...
0 votes
0 answers
65 views

Proof of polynomial kernel using positive semi-definiteness

I was asked to prove that $K$ is a valid kernel: $K(\vec{u}, \vec{v}) = \sum_{i=0}^M {a_i(G(\vec{u}, \vec{v}))^i}$ with $a_i \ge 0$, given that $G$ is a valid kernel. I tried to prove it using ...
  • 133
2 votes
1 answer
447 views

In machine learning, for a kernel function k, is sqrt(k) also a valid kernel function?

For some kernel function k which by definition has a symmetric and positive semidefinite kernel matrix K, is the new kernel function sqrt(k) also a valid kernel function? If we use Mercer's theorem, ...
0 votes
0 answers
60 views

Kernel Multinomial Logistic regression in R

I have a dataset of graphs/networks, and associated labels in R. I have read literature on graph kernels (e.g. Borgwardt et al), and can implement these with the ...
0 votes
0 answers
23 views

Kernelized Decision Trees

I came across a simple example that shows where decision trees may have difficulty solving a classification problem efficiently: "[...] For example, if we have a two-class problem and the ...
0 votes
0 answers
134 views

fitrgp: custom Kernel

I want to using Gaussian processes to dataset using a custom kernel. My kernel has one parameter 'beta' that I want to optimize. The problem is that the parameter 'beta' is not changing at all during ...
1 vote
0 answers
94 views

Square Root of kernel function validity [closed]

If k1(x,z) and k2(x,z) are valid kernels, then is k(x,z) a valid kernel, where k(x,z) = sqrt(k1(x,z)k2(x,z)) Prove using mercers theorem
  • 19
0 votes
0 answers
71 views

Proving validity of kernels

If k1(x,z) and k2(x,z) are valid kernels, then is k(x,z) a valid kernel, where k(x,z) = a1k1(x,z) - a2k2(x,z) (where a1, a2 > 0 are real numbers) I don't think this is true, but I am having trouble ...
  • 19
3 votes
1 answer
98 views

Kernel transformation in Machine Learning

I understand kernels allow us to linearly separate non-linearly separable data in a higher-dimensional space. Given a feature vector $\bar x = [x1,x2,..xn]^T$, we can apply the transformation $\phi(\...
  • 31
0 votes
0 answers
68 views

Why are radial basis functions so different from classic inner product?

I was studying SVM with kernel tricks and it seems that the kernel is a modified dot product. A simple kernel would be $K(x,y) = <x,y>^2$. I understand how this is a modification of the dot ...
  • 1
1 vote
0 answers
36 views

Prove that $k(u, v) = \tilde{k}(\phi(u), \phi(v))$ [closed]

Given that $\phi : \mathcal{X} → \mathcal{X}′$, prove that $k(u, v) = \tilde{k}(\phi(u), \phi(v))$. I've seen similar proofs where if $\phi : \mathcal{X} → \mathcal{X}$, the transformation is simply ...
  • 31
1 vote
0 answers
197 views

Prove that $k(x,y) = f(x)\tilde{k}(x,y)f(y)$ is a valid kernel

Given that $f: \chi \rightarrow \mathbb{R}$, prove that $k(x,y) = f(x)\tilde{k}(x,y)f(y)$ is a valid kernel, using only the fact that addition and multiplication yields valid kernels. My approach was ...
  • 31
4 votes
1 answer
219 views

Why Are Neural Networks Considered "Expensive" to Train?

Recently, I was looking at the optimization functions required in training Kernel Based Methods compared to Neural Networks. 1) Kernel Methods: For instance, I was looking at the optimization in ...
  • 6,068
0 votes
0 answers
12 views

How do you obtain extra-dimensional values using the kernel trick in SVMs?

To preface, I've been reading about SVMs and the kernel trick for the better part of an hour, and I think I understand what it is trying to accomplish fairly well, but what I don't understand is the ...
  • 1
1 vote
0 answers
45 views

Prove that the variance of a Gaussian Process is minimum on its train data points

I want to prove that the variance of a Gaussian Process (GP) is the lowest on any one of its $p$ training data points. The prior distribution for a zero-mean GP prior, with kernel function $k(x, x')$ ...
  • 155
1 vote
2 answers
226 views

Theoretical Speculations as to Why Neural Networks have Replaced Kernel-Based Methods

I have been reading about the history of statistical and machine learning algorithms, and am particularly interested in the reasons as to why neural networks have "replaced" kernel-based ...
  • 6,068

1
2 3 4 5
15