SVM has relatively low classification rate for high-dimensional data even though 2-D projections show they are separable

Question

I have another problem with 14000 features and 500 training samples. It is a binary classification problem and approximately in the form of an ellipse. My classification accuracy using the 2nd degree polynomial Kernel and via CV is ~ 80%. However, I've randomly tried projecting the data onto 2-D, that is I just pick out two features and project them, and find that there are several combinations that give me 100% separation. I've also used the RB kernel and the classification accuracy is ~70% for that. Does anyone have a reason why this is happening?

This is the code I'm using for libsvm...

% train SVM model
model = svmtrain2(Y(train_vec,1),X(train_vec,:),['-t 1 ' '-d 2 ' '-g ' num2str(grid_data(i,1)) ' ' '-r ' num2str(grid_data(i,2)) ' ' '-c ' num2str(C)]);
% test model on test set 
[predict_label, accuracy, dec_values] = svmpredict(Y(test_vec,1),X(test_vec,:),model);

Could you share the code/commands you are using to train the SVM? — Stumpy Joe Pete, Jul 11 '13 at 16:51
Why don't you test the model on the training data, just to make sure it's 100%. — Stumpy Joe Pete, Jul 11 '13 at 17:06

score 7 · Answer 1 · answered Jul 11 '13 at 17:51

I didn't see anything wrong with the results you had. As others pointed out already, you are facing a typical $P \gg N$ situation, where the number of predictors, i.e., features, is much greater than the number of instances.

In this situation, SVM is generally a good choice, as its maximum margin property gives some guarantees on the generalization performance. But in this situation, I would go for a linear kernel instead of a polynomial or RBF kernel. Because a linear kernel with 14000 features is already very powerful. If you later find out that the representation power of linear kernel is not enough, you can then try some more powerful kernels instead.

As you mentioned that the data are well separable with fewer predictors, you might want to get rid of some predictors in the first place. In general, we try to avoid the $P \gg N$ situation. Maybe you want to use some Lasso methods to do some implicit feature selection for you.

score 6 · Answer 2 · answered Jul 11 '13 at 17:10

6

From Gaussian Processes for Machine Learning by Rasmussen:

In a feature space of dimension $N$, if $N > n$ then there will always be a separating hyperplane. However this hyperplane may not give rise to good generalization performance, especially if some of the labels are incorrect.

That is, if you have more dimensions than data points the data will be linearly separable, but it doesn't necessarily mean that the data can be classified perfectly.

answered Jul 11 '13 at 17:10

Max S.

1,666
8
7

Thank you so much for your help. Does this mean no matter how the data set looks like, if I have N > n, I can find the separating hyperplane right? – user27525 Jul 11 '13 at 17:15
@user27525 Yes, it does. You don't even need a kernel. You could just use the dotproduct and you'd always be able to separate them. – Stumpy Joe Pete Jul 11 '13 at 17:32

score 0 · Answer 3 · answered Jul 11 '13 at 20:45

When there are more features than patterns, a linear kernel is generally a good idea as the other answers suggest (+1), however the really important thing to do then is to set the regularisation parameter (C) carefully (using e.g. cross-validation). It is largely the regularisation of support vector machines that gives rise to their good generalisation performance (simply ridge regression with good choice of ridge parameter is often just as good in practice).

SVM has relatively low classification rate for high-dimensional data even though 2-D projections show they are separable

3 Answers3