Kernel trick refers to kernel methods in machine learning, such as kernel support vector machine (SVM) or kernel principal components analysis (PCA). It allows to generalize linear techniques to non-linear situations. DO NOT USE this tag for [kernel] which is reserved for non-parametric estimation ...

learn more… | top users | synonyms

1
vote
1answer
22 views

Margin bound for binary classification and Rademacher complexity

In the slides (slide 29) of Mohri a margin bound for binary classification is derived: $$R(h) \leq \hat{R}_\rho(h) + \frac{2}{\rho} \hat{R}_S(H) + 3\sqrt{\frac{\log \frac{2}{\delta}}{2m}}$$ Here ...
2
votes
1answer
33 views

Chi Squared Kernel and Faster implementation

There is a good implementation of Chi-Squared Kernel in http://www.vlfeat.org/matlab/vl_alldist2.html But this implementation is very slow when input data is huge. This implementation doesn't accept ...
1
vote
0answers
10 views

Fisher kernel or KL divergence?

I am currently reading about pLSA and LDA and how can I apply these methods on calculating document similarity. I got a feeling that common similarity measure used in pLSA is Fisher kernel, but for ...
4
votes
1answer
23 views

How to prove that text is linearly separable?

I sentiment analisys task, for this I used SVM with an rbf kernel and a linear one. The results for the linear kernel were better than the rbf, from this I know that text is linearly separable, but ...
1
vote
1answer
18 views

Combining text and non-text features

I am working on a binary classification problem using SVM. I am currently using ksvm in R (kernlab package). The input is a combination of text and scores. I would like to be able to use substring ...
13
votes
3answers
383 views

How to intuitively explain what a kernel is?

Many machine learning classifiers (e.g. support vector machines) allow one to specify a kernel. What would be an intuitive way of explaining what a kernel is? One aspect I have been thinking of is ...
1
vote
1answer
24 views

Kernels for Categorical or Mixed Data

It appears that when data sets have a combination of categorical and continuous attributes, the common way to apply kernel algorithms to such data sets is to use a one hot encoding scheme for each ...
1
vote
1answer
80 views

Combination of two SVM Kernels

According to the book "Support Vector Machines" from Cristianini and Shawe-Taylor, it is feasible to make kernels from kernels. My question is now more in application of this methods with tools like ...
0
votes
1answer
29 views

Prove that a kernel is conditionally positive definite

A kernel is called positive definite (p.d) if its Gram matrix is p.d., i.e. all eigenvalues of the Gram matrix are positive for all possible input vectors in the feature space. My understanding of ...
4
votes
1answer
62 views

Is Support Vector Machine sensitive to the correlation between the attributes?

I would like to train an SVM to classify cases (TRUE/FALSE) based on 20 attributes. I know that some of those attributes are highly correlated. Therefore my question is: is SVM sensitive to the ...
0
votes
0answers
19 views

Neural networks kernel for high error rate in training set.

I will be working with a huge training set (around 10^6 examples, with around 400 features). Which has labels (around 100) accurate to around 90%. It would be possible to generate a smaller subset of ...
1
vote
0answers
40 views

Generalization error of PCA and kernel PCA

I've been recently reading Shawe-Taylor et al. 2005, On the Eigenspectrum of the Gram Matrix and the Generalization Error of Kernel PCA, where the authors analyze the squared residual of kernel ...
4
votes
1answer
72 views

Using kernels with Fisher's linear discriminant analysis

I am a bit stuck implementing the Kernel Fisher Discriminant. $$ J(\mathbf{w}) = \frac{\mathbf{w}^{\text{T}}\mathbf{S}_B^{\phi}\mathbf{w}}{\mathbf{w}^{\text{T}}\mathbf{S}_W^{\phi}\mathbf{w}} $$ $$ ...
1
vote
2answers
83 views

SVM kernel parameters value [duplicate]

I need a kernel for the following situation: 100 dimensions, 10 classes For every feature(in the features order) the maximum distance between any different pair of points is ...
2
votes
1answer
44 views

Turn a distance measure into a kernel function

I have read here that an easy way to turn a distance function $d$ into a similarity function $s$ is to compute: $s = e^{-\gamma * d}$. I believe that this is also what is done with the RBF kernel. ...
2
votes
0answers
43 views

What is the nonlinear transformation assumed by the gaussian (rbf) kernel? [duplicate]

A common kernel choice is the gaussian kernel: $ k(x,x^{'}) = \exp \big( -\frac{1}{2\sigma^2}\| x - x^{'} \|^2 \big)$ This implies a transformation on $x$, and equally on $x^{'}$. What is it?
0
votes
1answer
15 views

Kernel SVM overfitting after training set extension

I am training Kernel SVM from sklearn package for binary classification problem. I perform a gridsearch for parameters optimization. Parameters are taken from following ranges: 'C':[1., 10., 100.], ...
0
votes
1answer
52 views

Does the kernel trick really map 2d data to 3d data?

I want to learn something about kernel trick in svm, so I'm using this code: ...
0
votes
0answers
7 views

What are “parts” in Haussler's definition of R-convolution kernels?

I have been reading about R-convolution kernels: http://citeseerx.ist.psu.edu/viewdoc/download?rep=rep1&type=pdf&doi=10.1.1.110.638. These important types of kernels are generalization of ...
3
votes
1answer
137 views

Confused about transposes in kernel notation

I am studying machine learning and I ran into a challenge that does not make sense to me. Maybe it is a crazy or a simple question. If we have kernel $ \phi_1(x)=[x, x^2]^T $ and $ \phi_2(x)=[2x, ...
1
vote
0answers
27 views

Probabilistic degree of confidence for the kernel SVM with RBF

Let $f\colon\Bbb{R}^n\to\Bbb{R}$ be the decision function of an SVM using the radial basis function (RBF), $$ k(\mathbf{x},\mathbf{x}')=\exp\Big(-\gamma\|\mathbf{x}-\mathbf{x}'\|^2\Big). $$ That is, ...
0
votes
1answer
99 views

Locally weighted regression VS kernel linear regression?

I am trying to make it clear the relationship of the listed three methods. According to my understanding kernel regression means : the weight vector W lies in the space spanned by training data. $$ ...
1
vote
1answer
76 views

Kernel methods in machine learning?

I am beginning to tackle geostatistics problems where I tried to apply kriging(gaussian processes) to interpolate demographical water drop. According to my understanding, kernel methods are something ...
3
votes
1answer
77 views

How to use the kernel trick on data that can't be visualized

I'm reviewing the kernel trick and there are a lot of toy examples of how a 2D classification which can't usually be separated by a linear SVM can be separated in 3 space. This is fine, but how is ...
1
vote
2answers
118 views

Kernel PCA and classification

I need to perform kernel PCA on the colon-­‐cancer dataset and then I need to plot number of principal components vs classification accuracy with PCA data. For the first part I am ...
0
votes
2answers
39 views

Data normalization for RBF kernel

I have a matrix of values where rows are individuals and columns are attributes. I want to extract a similarity value for every pair of individuals, and I use an rbf kernel: $$k(x_i,x_j) = ...
3
votes
1answer
78 views

How do you transform a decision boundary in the angle kernel to the original space?

Say I have training data $S_n$ and each point is of the form $x = \langle x_1 , x_2 \rangle$ in the original space (i.e. $x^{(i)} \in \mathbb{R}^2$). I was considering the following kernel: $$ ...
2
votes
0answers
41 views

How to prove that Radial Basis Function can be derived by mapping function?

How to prove the radial basis function $k(u,v) = \int_{\mathbb{R}^d} \phi_t(u)\phi_t(v)dt $ can be integrated out by mapping function? $$\phi_{t}(u) = \frac{1}{(2\pi\Sigma)^{d/2}} ...
1
vote
1answer
35 views

Relationship between kernel function for distance (locally weighted regression) and kernel function for SVMs?

I am reading Tom Mitchell's Machine Learning. In section 8.2.3, he defines: Kernel function is the function of distance that is used to determine the weight of each training example. In other words, ...
0
votes
0answers
45 views

SVM for an unbalanced textual dataset?

I have a text classification task, currently I can classify the data with very poor precision. This are the scores: ...
1
vote
1answer
38 views

Regularizing the dual variables in SVM

Consider the the optimization program of the kernelized SVM: $$\text{maximize}_{\alpha} ~~ \alpha^T1-\alpha^TQ\alpha$$ $$\text{subject to:} \sum_{i=1}^N \alpha_iy_i=0,~0\leq \alpha_i\leq c$$ where ...
0
votes
0answers
56 views

What are the potential disadvantages of doing kernel PCA?

I was trying to learn more of the motivation around kernel PCA. Its clear to me that one might need to change the representation of the data if it lies in a non-linear space, hence, the projection ...
0
votes
1answer
42 views

Regression with a kernel

I have a fixed kernel and a set of points. I do SVC with the flavor of SVM classification i'm working on (assume it's just a regular SVM) and i obtain a classifier represented by an explicit vector of ...
5
votes
1answer
53 views

Does a polynomial kernel with degree less than 1 satisfy Mercer's condition

Consider the polynomial kernel: $$K(\boldsymbol{x}, \boldsymbol{x}') = (\boldsymbol{x}^{T} \boldsymbol{x}'+c)^{d}$$ This kernel satisfies the Mercer's theorem/condition. Since I never saw any ...
0
votes
1answer
135 views

Which hyperplane separates these two classes?

I have a dataset of 3 dimensional points in two classes, I want to separate between the two. As the plot suggests, these two are completely separable but I don't know the formula to form the ...
4
votes
1answer
224 views

How to choose a kernel for kernel PCA?

What are the ways to choose what kernel would result in good data separation in the final data output by kernel PCA (principal component analysis), and what are the ways to optimize parameters of the ...
3
votes
1answer
100 views

What exactly is the procedure to compute principal components in kernel PCA?

In kernel PCA (principal component analysis) you first choose a desired kernel, use it to find your $K$ matrix, center the feature space via the $K$ matrix, find its eigenvalues and eigenvectors, then ...
1
vote
1answer
51 views

Integrating length for input-space feature PC projections in kernel PCA

I read a paper detailing the algebraic process of kernel PCA. I have question though: the paper details the projection of new points onto the new eigenvectors in the feature space, but what if I want ...
20
votes
4answers
701 views

What makes the Gaussian kernel so magical for PCA, and also in general?

I was reading about kernel PCA (1, 2, 3) with Gaussian and polynomial kernels. How does the Gaussian kernel separate seemingly any sort of nonlinear data exceptionally well? Please give an intuitive ...
1
vote
1answer
61 views

Does the method of computing feature weights for linear kernel SVM also works for radial Kernel SVM?

I searched for how to find feature weights and found this stackoverflow answer. It gives the following equation to get the weights: ...
0
votes
0answers
104 views

Combining multiple feature subsets through ensemble classification methods?

I have a set of $N$ samples to be classifies in a binary classification problem. I have extracted features from these samples from 4 different perspectives (views) of every samples. Hence I have 4 ...
1
vote
1answer
59 views

What are the various basic kernels available?

I am currently following the book Gaussian Processes for Machine Learning by C.E. Rasmussen and C.K.I. Williams and I have come across various kernels in their Chapter 4 I have also gone through the ...
1
vote
0answers
29 views

How to Mine Tree Structures?

To learn similarities/differences between different instances (that are in the form of tree), what are the suitable methods/approaches? I know kernel methods and particularly tree kernels, but would ...
1
vote
1answer
61 views

How to fit a single quadratic term to a regression

I have a high dimensional multivariate model and am fitting linear weights to each of the $N$ free variables using a classic stable SVD matrix solver. This works. I want to improve the fit by using a ...
1
vote
0answers
15 views

U statistics and RKHS

Is there a relation between the kernel function in U-statistics and RKHS theory? Namely, can the kernel trick be seen as an order-2 U-statistic?
3
votes
1answer
42 views

Inner Product Kernel $k(x,y) = (1+\epsilon)^{\langle x, y \rangle}$

Where in the literature is the inner product kernel $k(x,y) = (1+\epsilon)^{\langle x, y \rangle}$ mentioned? Does it have a name?
0
votes
2answers
148 views

Kernel SVM on sparse data

I have a sparse dataset where a lot of the columns (features) contain mostly zero values. Class labels are multiple discrete categories (10 classes to be precise). I'm wondering if this should trouble ...
1
vote
1answer
88 views

Is it possible to project a new vector onto the PC space using kernel PCA?

Let $X_{N \times d}$ be the data matrix, where $N$ is the number of samples and $d$ the size of the features space. Using kernel PCA (kPCA), one first computes a kernel matrix $K_{N \times N}$, and ...
1
vote
1answer
59 views

Intuition behind RKHS

Why has RKHS become such an important concept in machine learning in recent times. Is it because it allows us to represent a function of combination of linear functions? What areas of mathematic does ...
1
vote
1answer
78 views

What kernel function can be used to project data into a feature space that is a “circle”?

I am working with cyclical data (Days 1-7, hours 1-24). I want to project it into a feature space that can understand that 1 and 7 are close days and 1 and 24 are closer than 22 and 24, etc, and then ...