Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It only takes a minute to sign up.
Sign up to join this community
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)?
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).
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.
Dimensionality Reduction: this is a way of reducing the features of your dataset which may not really contribute much to the model development. Putting it in another way, dimensionality reduction helps to remove "noice" from our dataset thus avoiding overfitting of our model.
However, Kernel Trick helps us to make a linearly inseparable dataset to become linearly separable by projecting it into higher dimensionality which may otherwise improve the precision of our model. With Kernel Trick, you can make a nonlinear dataset linear.
