5
$\begingroup$

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?

$\endgroup$
8
+50
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – spurra Mar 30 '15 at 21:13
  • $\begingroup$ Yep, that was a mistake; fixed. $\endgroup$ – djs Mar 30 '15 at 21:15
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.