11
$\begingroup$

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 kernel?

Layman's terms if possible would be greatly appreciated, and links to papers that explain such methods would also be nice.

$\endgroup$
  • 1
    $\begingroup$ When you say "good data separation", what exactly are you referring to? What application of kernel PCA do you have in mind? If it has anything to do with "data separation", then should you maybe be using some classification technique (like kernel support vector machine) instead of kPCA? Apart from all that, good question, +1. I don't have experience with kernel choice, so cannot help you here. $\endgroup$ – amoeba says Reinstate Monica Jan 5 '15 at 18:45
  • $\begingroup$ @amoeba It's to be used for Nonlinear Dimensionality Reduction. My knowledge on support vectors is a bit limited because I've never taken any CS courses; I'm a undergrad and have been learning through online papers. By "good data separation" I mean what is shown by the plotted examples in this paper. I'm working with Matlab and my kernel PCA code is up and running for simple, poly, radial basis, and sigmoid kernels, but It'd be helpful to know when to use which for best results. $\endgroup$ – Chives Jan 6 '15 at 2:00
  • $\begingroup$ I think the best (only?) way to select a kernel is to use cross-validation, see here: How to select kernel for SVM? You only need to have a performance measure for your kPCA in order to use cross-validation. Class separation can be a decent measure if that is what you are after, but note that PCA/kPCA is not designed at all to result in a good class separation; it is simply maximizing the captured variance. $\endgroup$ – amoeba says Reinstate Monica Jan 6 '15 at 11:14
  • $\begingroup$ I did some reading and might be able to answer your question after all. But it might take me some time (days). $\endgroup$ – amoeba says Reinstate Monica Jan 6 '15 at 13:54
  • $\begingroup$ @amoeba Maximizing variance does make sense to me now that you mention it. I'll look into cross validation myself, but it'd be great if you could look into it a little too if you can find the time! Thank you. $\endgroup$ – Chives Jan 6 '15 at 21:25
7
$\begingroup$

The general approach to select an optimal kernel (either the type of kernel, or kernel parameters) in any kernel-based method is cross-validation. See here for the discussion of kernel selection for support vector machines: How to select kernel for SVM?

The idea behind cross-validation is that we leave out some "test" data, run our algorithm to fit the model on the remaining "training" data, and then check how well the resulting model describes the test data (and how big the error is). This is repeated for different left-out data, errors are averaged to form an average cross-validated error, and then different algorithms can be compared in order to choose one yielding the lowest error. In SVM one can use e.g. classification accuracy (or related measures) as the measure of model performance. Then one would select a kernel that yields the best classification of the test data.

The question then becomes: what measure of model performance can one use in kPCA? If you want to achieve "good data separation" (presumably good class separation), then you can somehow measure it on the training data and use that to find the best kernel. Note, however, that PCA/kPCA are not designed to yield good data separation (they do not take class labels into account at all). So generally speaking, one would want another, class-unrelated, measure of model performance.

In standard PCA one can use reconstruction error as the performance measure on the test set. In kernel PCA one can also compute reconstruction error, but the problem is that it is not comparable between different kernels: reconstruction error is the distance measured in the target feature space; and different kernels correspond to different target spaces... So we have a problem.

One way to tackle this problem is to somehow compute the reconstruction error in the original space, not in the target space. Obviously the left-out test data point lives in the original space. But its kPCA reconstruction lives in the [low-dimensional subspace of] the target space. What one can do, though, is to find a point ("pre-image") in the original space that would be mapped as close as possible to this reconstruction point, and then measure the distance between the test point and this pre-image as reconstruction error.

I will not give all the formulas here, but instead refer you to some papers and only insert here several figures.

The idea of "pre-image" in kPCA was apparently introduced in this paper:

Mika et al. are not doing cross-validation, but they need pre-images for de-noising purposes, see this figure:

kPCA de-noising from Mika et al.

Denoised (thick) points are pre-images of kPCA projections (there is no test and training here). It is not a trivial task to find these pre-images: one needs to use gradient descent, and the loss function will depend on the kernel.

And here is a very recent paper that used pre-images for cross-validation purposes and kernel/hyperparameter selection:

This is their algorithm:

Alam and Fukumizu

And here are some results (that I think are pretty much self-explanatory):

Alam and Fukumizu

$\endgroup$
  • 1
    $\begingroup$ (+1) It may be useful to note that this pre-image is the set of Fréchet/Karcher means of the points assigned to a given cluster, not that that necessarily helps with anything. $\endgroup$ – Dougal Jan 7 '15 at 18:10
  • $\begingroup$ @Dougal: wow, thanks, I was not aware of this term at all. But I am not sure I understand. Consider the first Figure I posted here (from Mika et al.): each 2d point $x$ is mapped to the 1-dimensional kernel PC space $x \mapsto y$ which is then mapped back to the 2d pre-image $y \mapsto z$. When you say that pre-image $z$ is the "set of Frechet/Karcher means of the points assigned to a given cluster", what do you mean by cluster, and why is there a set? $\endgroup$ – amoeba says Reinstate Monica Jan 7 '15 at 22:10
  • $\begingroup$ On second thought, I guess I didn't pay enough attention before; my comment applies to kernel k-means, not kPCA. The preimage is definitely related to that concept, but not the same thing at all. Sorry for the noise. :) $\endgroup$ – Dougal Jan 8 '15 at 0:59

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.