# Why do one-versus-all multi class SVMs need to be calibrated?

On the wiki page for multi-class support vector machines (https://en.wikipedia.org/wiki/Support_vector_machine#Multiclass_SVM) it states that "it is important that the output functions be calibrated to produce comparable scores."

Why is that so? Why are the scores not directly comparable with each other?

### Setup

Recall that an SVM can be viewed as a weight vector $w$ and an intercept $b$, and that the output function for a test input $x$ is is $\langle w, x \rangle + b$. To get a binary prediction, we take $f(x) = \mathrm{sign}(\langle w, x \rangle + b)$.

(I'm going to use some primal notations here, but use $\langle \cdot, \cdot \rangle$ to denote that inner products are happening in some Hilbert space rather than necessarily in $\mathbb R^n$. This won't be important to the answer; feel free to think of everything as a traditional vector if you like.)

### Importance of $\lVert w \rVert$

If we want to compare output functions from different models, say $(w, b)$ and $(w', b')$, we would need some kind of assurance that the values of $\langle w, x \rangle + b$ and $\langle w', x \rangle + b'$ are of similar size.

Otherwise, for example, suppose that $\lVert w \rVert \gg \lVert w' \rVert$, so that for most values of $x$, $\lvert \langle w, x \rangle \rvert \gg \lvert \langle w', x \rangle \rvert$. $\lvert b \rvert$ will probably also be larger, but this will just make the mean value 0 (in a balanced classification problem); we'll still typically have $\lvert \langle w, x \rangle + b \rvert \gg \lvert \langle w', x \rangle + b' \rvert$. Then, when we pick the model with the highest-valued output function, we'll usually just pick $(w, b)$.

This is not great because, for any $\alpha > 0$, the model defined by $(w, b)$ gives the same predictions as that defined by $(\alpha w, \alpha b)$: $\langle w, x \rangle + b > 0$ iff $\langle \alpha w, x \rangle + \alpha b = \alpha \left( \langle w, x \rangle + b \right) > 0$.

### What determines $\lVert w \rVert$?

The question, then, is how do we end up with large $w$s as a result of the SVM optimization problem?

For a hard-margin SVM, the margin is $2 / \lVert w \rVert$. So a high value of $\lVert w \rVert$ actually corresponds to a small-margin model, which makes it (in the underlying assumption of SVMs) a worse model. So if we don't scale the output scores, we actually trust the worst models the most!

For soft-margin SVMs, the margin is still $2 / \lVert w \rVert$, but how "hard" the margin is depends on the total slack. This tradeoff is done by the $C$ hyperparameter in the objective $\tfrac12 \lVert w \rVert^2 + C \sum_i \xi_i$, where $\xi_i$ is the amount you'd need to move the $i$th training example to put it on the right side of the margin. A higher $C$ corresponds to a harder margin, thus a smaller margin, and a larger $\lVert w \rVert$. If you're tuning the hyperparameters of your multiclass ensemble individually for each problem, the unscaled version of the ensemble will additionally be biased towards those with higher values of $C$, without any really good reason for doing so.

### Moral of the story

"It is important that the output functions be calibrated to produce comparable scores." Otherwise, you're doing almost exactly the wrong thing.

• Thanks for your thorough explanation. You assume that |(w,x) + b| >> |(w',x) + b'| and then you state that if we pick the model with the highest-valued output function, we'll pick (w',b'). Don't you mean (w,b)? – spurra Mar 30 '15 at 21:13
• Yep, that was a mistake; fixed. – Danica Mar 30 '15 at 21:15

This is because each individual one-vs-all classifier corresponds to different support vectors and their respective alphas in the decomposition. The score output for a test data point is in no way bounded and should be normalized (e.g. using Platt's scheme from scores to probabilities) in order to be comparable.