15
$\begingroup$

I want to implement an algorithm in a paper which uses kernel SVD to decompose a data matrix. So I have been reading materials about kernel methods and kernel PCA etc. But it still is very obscure to me especially when it comes to mathematical details, and I have a few questions.

  1. Why kernel methods? Or, what are the benefits of kernel methods? What is the intuitive purpose?

    Is it assuming a much higher dimensional space is more realistic in real world problems and able reveal the nonlinear relations in the data, compared to non-kernel methods? According to the materials, kernel methods project the data onto a high-dimensional feature space, but they need not to compute the new feature space explicitly. Instead, it is enough to compute only the inner products between the images of all pairs of data points in the feature space. So why projecting onto a higher dimensional space?

  2. On the contrary, SVD reduces the feature space. Why do they do it in different directions? Kernel methods seek higher dimension, while SVD seeks lower dimension. To me it sounds weird to combine them. According to the paper I am reading (Symeonidis et al. 2010), introducing Kernel SVD instead of SVD can address the sparsity problem in the data, improving results.

enter image description here

From the comparison in the figure we can see that KPCA gets an eigenvector with higher variance (eigenvalue) than PCA, I suppose? Because for the the largest difference of the projections of the points onto the eigenvector (new coordinates), KPCA is a circle and PCA is a straight line, so KPCA gets higher variance than PCA. So does it mean KPCA gets higher principal components than PCA?

$\endgroup$
  • 3
    $\begingroup$ More a comment than an answer: KPCA is very similar to Spectral Clustering -- in some settings it is even the same. (see e.g. cirano.qc.ca/pdf/publication/2003s-19.pdf). $\endgroup$ – user44306 Apr 23 '14 at 9:24
  • $\begingroup$ Sorry for late reply. Yes, your answer is very enlightening. $\endgroup$ – Tyler 十三将士归玉门 Oct 24 '14 at 9:56
21
$\begingroup$

PCA (as a dimensionality reduction technique) tries to find a low-dimensional linear subspace that the data are confined to. But it might be that the data are confined to low-dimensional nonlinear subspace. What will happen then?

Take a look at this Figure, taken from Bishop's "Pattern recognition and Machine Learning" textbook (Figure 12.16):

kernel PCA from Bishop's ML book

The data points here (on the left) are located mostly along a curve in 2D. PCA cannot reduce the dimensionality from two to one, because the points are not located along a straight line. But still, the data are "obviously" located around a one-dimensional non-linear curve. So while PCA fails, there must be another way! And indeed, kernel PCA can find this non-linear manifold and discover that the data are in fact nearly one-dimensional.

It does so by mapping the data into a higher-dimensional space. This can indeed look like a contradiction (your question #2), but it is not. The data are mapped into a higher-dimensional space, but then turn out to lie on a lower dimensional subspace of it. So you increase the dimensionality in order to be able to decrease it.

The essence of the "kernel trick" is that one does not actually need to explicitly consider the higher-dimensional space, so this potentially confusing leap in dimensionality is performed entirely undercover. The idea, however, stays the same.

$\endgroup$
  • $\begingroup$ Nice answer. Just a follow up question though. You said if the data points are non-linear as shown in figure above then PCA won't work and kernel PCA is required. But how do we know in the first place if the data points are non linear for data set which has more than 4 features (the real world case). To visualize such data we need to reduce dimensionality which means we end up using PCA to reduce dimensionality which would be wrong as data might be non linear and we use normal PCA to visualize. Then how does one know whether data is non linear to use kernel PCA rather than PCA $\endgroup$ – Baktaawar Oct 23 '15 at 23:28
  • $\begingroup$ Thanks, @user. I guess this depends on the application of PCA/kPCA. For example, if it is applied as a preprocessing step for some classification, regression, or clustering algorithm, then one can judge how well PCA vs. kPCA performed from how well this subsequent algorithm performs. $\endgroup$ – amoeba Oct 24 '15 at 14:04
  • 1
    $\begingroup$ Thanks @amoeba. But I guess what I wanted to ask was that like you mentioned above we need to use kPCA when the data is non linear then how does one know if the data has non -linearlity if no. of features is more than 3?. We can't visualize that without reaching dimensions and then it's like a chicken and egg problem $\endgroup$ – Baktaawar Oct 26 '15 at 17:43
  • 2
    $\begingroup$ @Baktaawar If you are doing machine learning, don't visualize, let your model learn it itself. Basically include a KPCA step in your inner resampling loop and test the kernels as parameters, including the linear kernel and any others you want/can afford to test. $\endgroup$ – Firebug Jun 13 '16 at 20:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.