4
$\begingroup$

Whilst learning about classification, I have seen two different arguments. One is that projecting the data to a lower-dimensional space, such as with PCA, makes the data more easily separable. The other is that projecting to a higher-dimensional space, such as with kernel SVM, makes the separation easier.

Which is correct? Or does it depend on the data? What about projecting down with PCA, and afterwards projecting that space up with kernel SVM (or vica versa)?

$\endgroup$
3
$\begingroup$

This answer also adds points from pAt84's answer

Dimensionality reduction. I don't think reducing dimension can make your data more separable actually but it has some other benefits. First, as the dimension of your space grows, you often need more samples to be able to catch patterns, this is just a question of volume. Of course this all depends on how corrolated your data is (if you add a duplicate column it won't change). So reducing your dimension can be a necessity when you have feature vectors that has too many components, e.g. if you work with text and have a sort of TF-IDF, it would create one dimension per word (or lemma). Moreover, it prevents you from the curse of dimensionnality (e.g. if you need to perform some sort of KNN afterwards). And obviously it also fastens a lot the algorithm you run in the reduced space - though the cost of reducing dimension can be higher than the gain of running algorithms in reduced dimension. One thing is sure: dimensionnality reduction decreases information. Most of the time it does so by discarding correlations in the input data.

Kernel trick. That being said, the kernel trick is an entirely different idea. Some data that are not separable in the original space can become in a higher one: imagine two circles of radius $.5$ and $1$ sampled, those points are not separable, but if you add the distance to $0$ they become. So the idea is that the way we use a dot-product in the original space is not sufficient enough, we ought to use the dot-product in that mapped space with distance to the origine, and that's the core idea to kernels: find functions that can "scatter" our data as we want into a hilbert space. But the way I prefer to see it is that using a kernel is using a prior information on your data: how they can be compared. Roughly, a kernel is more or less a similarity matrix, and a kernel-based method is a method where you've switch the naive way of comparison (regular dot-product in the original space) to one that fits your data best (your kernel). Then, indeed, it can correspond in a mathematical way, to increasing the dimension of the space comparison happens in. Precisely: your data still lives on the same-dimensional space, but the kernel you provided acts as if you mapped your data in a higher dimensional space (RKHS), that can have an infinite dimension (e.g. with an RBF), and you used a dot-product in that space. The main trick of kernel-based method is that you actualy never explicitly map your data into the RKHS - that's why it can work! All the work is done by applying your kernel on two samples. Eventually, you haven't gained any information, meaning that it helps give a mathematical frame to explain how it works, but intuitively the idea is just that you've provided a better way to compare your data: no dimension were really explicitly added to your data (computationaly), you simply found a more suitable way to compare them.

Now nothing prevents you from doing both: you could try to categorize texts by doing a TF-IDF, then a PCA and then an RBF-SVM (though a linear one is most of the time OK with texts but nonetheless that would make perfect sense).

$\endgroup$
1
$\begingroup$

I won't have enough space in the comments to give my thoughts on Vinces answer, which is certainly very good but lacking some additional insight. Can answers be merged?

Dimensionality reduction would not make the data more separable during training: you are giving away information. However, this information drain might be useful for the generalization of the learned model, i.e. its performance on unseen data will increase.

You do not always need more samples to catch patterns in a high(er)-dimensional space although in general this might actually be the case. It also depends on the correlation of the features. If you just double a feature vector, i.e. two feature vectors will be the same, the increase in dimensionality will obviously not have significant consequences other than probably upsetting your regularization scheme of the learner. It is quite important to see how much the data correlates, the rank of the feature matrix can be a very good inside.

Vince makes a very good point when he says that dimensionality reduction can fasten your algorithm during training and testing. However, keep in mind that the reduction itself also has a computational complexity, so performing PCA and adding an SVM might not give you much of a speedup (and can be absorbed into one weight vector I think). However, if you keep the dimensionality reduction simple enough, then this will really work in your favor. A good example of that are HOG features in object detection (http://cs.brown.edu/~pff/papers/lsvm-pami.pdf). In the paper PCA is performed on the HOG feature vector. A closer look at the eigenvectors reveals that a simple dimensionlity reduction, which just sums up different groups of features, will be enough and it indeed is. This gave a 2 to 3 times speedup.

As for the kernel trick: the function that `lifts' your data into a higher dimensional space does not necessarily have to map into euclidean space but into a Reproducing Kernel Hilbert Space (RKHS). This gives you a bit more freedom in designing such functions. The Gram matrix of the kernel function, i.e. the dot-product in higher-dimensional space for all combinations of training examples can vaguely be seen as a similarity/dissimilarity matrix. However, I would not really push this thought too far. For an RBF kernel this is certainly true but a polynomial kernel is very hard to interpret in this way.

Actually additional components are added to your feature vector when using kernels, i.e. the dimensionality increases. It does so implicitly in the RKHS. For many kernels, e.g. polynomial kernels, the dimensionality increases massively. For the RBF kernel it is even infinite under some conditions.

Doing both (PCA + kernel-based learning) is called kernel pca and essentially fuses both methods.

Keep in mind though: just as a dimensionlity reduction may speed up your algorithms, kernel functions will almost always slow them down due to its increased computational complexity at test time c.f. a linear classifier. This can partially be circumvented by explicit feature mapping, i.e. actually executing the mapping function from original to high-dimensional space and keeping an eye on the dimensionality. See, for example, this paper: http://www.robots.ox.ac.uk/~vedaldi/assets/pubs/vedaldi11efficient.pdf This trick is quite nice as it gives you an intuition of the higher dimensional space while not making it too large in the sense of having too many components. Once your feature vectors are explicitely mapped into the higher-dimensional space, you may apply a linear classifier.

There is certainly more out there (e.g. low-rank expansion) but I think these two answers should give you a good and somewhat detailed overview. Vinces answer should be upvoted and chosen as best answer if you are happy with the information we gave you.

$\endgroup$
  • $\begingroup$ Some good points up there, I'll add them to my answer (that I wanted concise but those subjects are too broad to be kept narrow, you're right). As for the speed up, as you said it depends on the process you need to do afterwards. I don't think I said a RKHS is euclidean though, but if I did my bad, I may have meant hilbertian. $\endgroup$ – Vince.Bdn Mar 6 '16 at 15:42
  • $\begingroup$ As for the "actually" added components, I don't agree =) the whole magic of using kernels is that you don't explicitly use the dot-product in the RKHS, it's kept under the hood by the kernel! Otherwise, you wouldn't even be able to compute the rbf of two vectors (as its RKHS is of infinite dimension). It's very important computationnaly to get that RKHS work thanks to this trick. $\endgroup$ – Vince.Bdn Mar 6 '16 at 15:43
  • $\begingroup$ Found where I did said "euclidean", shame on me!! Glitch corrected. I tried to summarize the main ideas of your answer down there. Tell me if something's bothering you! $\endgroup$ – Vince.Bdn Mar 6 '16 at 15:55
  • $\begingroup$ Yes, indeed, I formulated that quite vaguely. The trick is actually to compute the dot-product using the kernel function in the lower dimensional space. Thanks for the clearup. $\endgroup$ – pAt84 Mar 8 '16 at 10:48

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.