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

0
votes
0answers
13 views

Storing a kernel matrix

I'm reading a paper on feature hashing and the authors state in the introduction that "limited memory makes storing a kernel matrix infeasible." I'm confused as to why the kernel matrix needs to be ...
0
votes
1answer
32 views

Is Representer theorem valid with constraints on coefficients?

By the representer theorem, we have that in a Reproducing Kernel Hilbert Space the function being learnt in a regularizer + loss function problem under some conditions, can be represented as $\sum_i ...
1
vote
0answers
25 views

Kernel PCA wrong output

Linear PCA and kPCA with linear kernel should produce exactly the same results ( good explanation is in this post ). As I am learning to use PCA family methods I try to write my own functions ...
2
votes
0answers
23 views

Estimating the prediction variance in kernel ridge regression

I'm trying to estimate the variance of predictions for a kernel ridge regression model. The model is simply kernel ridge regression: $$\hat{y} = K(K+\lambda I)^{-1}y = A y$$ $K$ is the $n \times n$ ...
0
votes
1answer
21 views

whats a difference between multiple kernel learning and ensemble learning?

From wiki: Ensemble methods use multiple learning algorithms to obtain better predictive performance than could be obtained from any of the constituent learning algorithms Multiple kernel learning ...
2
votes
0answers
25 views

Assuming normality in RKHS

There are some authors who assume data in a Reproducing Kernel Hilbert Space is following a normal distribution. For example, in this article, the authors use this assumption to be able to derive ...
0
votes
0answers
34 views

Kernel K nearest neighbours with sparse data

I have a big sparse matrix (around 5 million of lines, 20 000 predictors), and I would like to run a kernelized k-NN on it. However, I don't know how to scale the data properly. So far, I have scaled ...
0
votes
0answers
10 views

Does it ever make sense to use a feature-local (e.g. polynomial) kernel for binary data?

As I understand, for a sample $s$, a polynomial kernel produces a vector consisting of $x_{s,i},x_{s,i}^2,..., x_{s,i}^n$ for every feature $i$, allowing SVM (or ANN) to effectively find a nonlinear ...
1
vote
1answer
27 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
36 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
16 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
27 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
29 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
410 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
29 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
94 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
36 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
63 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
27 views

set SVM parameter range values for tuning [duplicate]

I am newbie to using svm for classification. I want to tune svm parameters by .TrainAutofunction in EmguCV. But I don't know what are the range(min-max value) of below parameters that I should give to ...
0
votes
0answers
26 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
45 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
86 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
47 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
18 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
62 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
8 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
142 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
28 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
37 views

Valid result when adding two kernels with negative coefficient?

If $k_1$ and $k_2$ be a kernel in $ \mathbb{R}^n \times \mathbb{R}^n $. we know $k(x,z)=ak_1(x,z) + bk_2(x,z)$ (kernel addition) is still a valid kernel if $\: a,b \geq 0\,$ ($a,b$ is real numbers, ...
0
votes
1answer
168 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
98 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
79 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 ...
0
votes
0answers
46 views

What is the time complexity of binary classification of SVM?

One of the earliest solutions to the SVM problem is SMO applied to dual form. What is the time complexity of SMO algorithm? What is the best known time complexity to solve SVM algorithm (non linear)? ...
1
vote
2answers
135 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
51 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) = ...
1
vote
0answers
17 views

Good implementation of SVM with operator valued kernel

I've already come across the question Vector Valued SVM but the replies doesn't point to SVM with any operator-valued kernel. I understand that svm-struct can solve the same by solving an inference ...
1
vote
2answers
50 views

Recommended/estimated number of radial basis functions in RBFN

I am attempting to make a Radial Basis Function Network to see if a relationship exists between input/output data that I have been collecting. I have hit a bit of a brick wall with a few issues, and ...
3
votes
2answers
88 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: $$ ...
0
votes
1answer
42 views

Covariance function to draw an inverse function

In a Gaussian Process (GP), we know that choice of the covariance function determines the shape of function that can be drawn from the GP. eg. Constant : $\sigma _{o}^{2}$ Draws constant function ...
2
votes
0answers
42 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}} ...
0
votes
1answer
56 views

Correct arguments for svm() function in R

I'm looking to implement a linear and non-linear SVM in R but having some confusion over which argument to use in svm(). For the linear SVM I want to add in the ...
1
vote
1answer
36 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
47 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
39 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
44 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
57 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
138 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 ...