Unassigned classes in Multiclass SVM with One vs All Approach

Question

How do you handle unassigned classes in multiclass support vector machines (multiclass SVM) with the One vs All approach?

Lets say my training data has three classes A, B, and C. I use 3 SVM one-vs-all classifiers. For a particular test instance, all classifiers say 'Not A', 'Not B' and 'Not C' respectively. How do I assign this instance to one of the classes? I tried using an 'unassigned class' class, but the error rates are too high.

Another question:
When two or more classifiers assign a test instance as positive, which one should I go with. I read somewhere that you should use "output function of the SVM". Now what's that?

Matlab gives the following svmStruct:

1. SupportVectors
2. Alpha
3. Bias
4. KernelFunction
5. SupportVectorIndices
6. Others

How do I use these to generate the "output value"?

Also, I did not quite understand Platt's technique. How do I implement it using elements of svmStruct. This question is related but went unanswered.

Answer 1

Another question: When two or more classifiers assign a test instance as positive, which one should I go with. I read somewhere that you should use "output function of the SVM". Now what's that?

When used as a classifier, the label for instance $\mathbf{x}$ is decided based on the sign of the decision value $f(\mathbf{x})$. The decision value of an SVM for instance $\mathbf{x}$ is computed as follows:

$$ f(\mathbf{x}) = \sum_{i\in \mathcal{S}} \alpha_i y_i \kappa(\mathbf{x}_i,\mathbf{x}) + b . $$

The decision value itself can be used to rank decisions by confidence in the predicted label. A higher absolute value $|f(\mathbf{x})|$ indicates a larger distance from $\mathbf{x}$ to the separating hyperplane and as such signifies higher confidence in the predicted label.

Matlab gives the following svmStruct ... How do I use these to generate the "output value"?

Matlab's SVMStruct has all the ingredients for you to implement the decision function $f(\cdot)$ yourself:

• SupportVectors: the set of $\mathbf{x}_i$'s,
• Alpha: the $\alpha$ vector (probably even $\alpha.*y$),
• Bias: the $b$ term,
• KernelFunction: $\kappa(\cdot,\cdot)$.

Lets say my training data has three classes A, B, and C. I use 3 SVM one-vs-all classifiers. For a particular test instance, all classifiers say 'Not A', 'Not B' and 'Not C' respectively. How do I assign this instance to one of the classes?

Choose the class associated with the least confident (calibrated) not-this-class-prediction. Do not use decision values of different models directly since their distributions may differ (see below for simple instructions).

Calibrating decision values

You can compare decision values from one single model with eachother to perform ranking. You cannot, generally, compare decision values of different models with eachother directly as they are not calibrated.

In your case, unfortunately, you are in the latter situation. Therefore you would first need to perform some kind of calibration. A very rudimentary (but often sufficiently accurate) calibration approach would be dividing the decision values per model by the standard deviation of decision values you get for that model on an independent test set (not the training set!).

For example, assume you have two models which disagree on a label: $$ sign[f_1(\mathbf{x})] \neq sign[f_2(\mathbf{x})]. $$ You want to follow that model for which the confidence of the decision is highest, but you cannot directly compare the two (since the distribution of decision values may differ between both models). This is why we calibrate them first:

$$ \begin{align} f_1^{cal}(\mathbf{x}) &= f_1(\mathbf{x}) / \sigma_1 \\ f_2^{cal}(\mathbf{x}) &= f_2(\mathbf{x}) / \sigma_2 \end{align} $$

Now simply follow the label from the model with the highest calibrated confidence in its decision (e.g. highest absolute value of the calibrated decision value).