What to do when every SVM returns "not a member"?

Question

We have trained about 200 Linear Support Vector Machines (hand-coded in C#) belonging to our 200 categories and we use them in text categorization. Due to the shortness of the text in our training samples and other uncontrollable factors, very often every machine returns a negative number for (classifies as negative) a given document. Returning "None" as an answer is not feasible because it happens maybe about 40% of the time, and not classifying 40% of the documents is unacceptable from a business point of view.

What we do is, we don't bother about the sign of the results and return the category with the maximum value anyway. However, I feel this makes our error rate larger than need to be.

So here is my question: Is there a principled middle-of-the-road way? That is it will sometimes (but not too often, maybe about 5% of the time) return "None" and it will sometimes return the maximum of the negative numbers, so that |misclassified documents| + k.|unclassified documents| will be minimum (for some k<=1)? For example, is there a way to translate the distance given by an SVM to a probability value? Or, relatedly, is there a principled way to compare the output of two Support Vector Machines, i.e. +0.2 denotes a higher probability of membership in one of them? Any suggestion, source, paper is welcome. Thank you.

Answer 1

The correct way to approach this problem is to assign costs to false positive and false negative errors, and set the regularisation parameter C to different values for each class in order to minimise the expected loss. I wrote a paper on this some years ago, there is probably something more up to date available now.

The fact that "not classifying 40% of the documents is unacceptable from a business point of view" strongly suggests that false-positive and false-negative costs are not equal.

This problem can crop up frequently in multi-class problems with a large number of classes, which means that individual two-class SVMs end up with a dataset with hardly any positive examples. Again the best you can do with SVMs is probably to tune the ratio of C for positive and negative patterns via cross-validation to minimise the expected loss.

For converting the output of an SVM to a probability, there are many methods, but Platt's method is the most commonly used. However, if you want probabilities, then why not just use regularised logistic regression? In practice there generally isn't much to choose performance-wise between linear SVMs and RLR, provided the regularsation parameters are properly tuned. If you want probabilities, then RLR seems closer to Vapnik's maxim of always solving the problem directly, rather than using a more general method and simplifying (or on this case, a less general method and post-processing it to get a probability).

HTH