2
$\begingroup$

I have encountered an ambiguity in SVM equations. As is stated in Chris Bishop's machine learning book, the optimization goal in SVM is to maximize this function:

$$C\sum\limits_{n = 1}^N {{\xi _n}} + {1 \over 2}{\left\| w \right\|^2}$$

Subject to this constraints(*):

$${\xi _n} \ge 0$$ $${t_n}y({x_n}) \ge 1 - {\xi _n}$$

where:

$$y({x_n}) = {w^T}{x_n} + b$$

so the corresponding Lagrangian function for this problem is:

$$L(w,b,a) = C\sum\limits_{n = 1}^N {{\xi _n}} + {1 \over 2}{\left\| w \right\|^2} - \sum\limits_{n = 1}^N {{a_n}\{ {t_n}y({x_n}) - 1 + {\xi _n}\} - } \sum\limits_{n = 1}^N {{\mu _n}{\xi _n}} $$

and the corresponding KKT conditions are given by (**):

$${a _n} \ge 0$$

$${{t_n}y({x_n}) - 1 + {\xi _n}} \ge 0$$

$${a_n}({t_n}y({x_n}) - 1 + {\xi _n}) = 0$$

$${\xi _n} \ge 0$$

$${\mu _n} \ge 0$$

$${\mu _n}{\xi _n} = 0$$

And if we set

$${{\partial L} \over {\partial {\xi _n}}} = 0$$

we get (***)

$${a_n} = C - {\mu _n}$$

As we know, that subset of data points that have

$${a_n} = 0$$

are not support vectors. But for this data points we have (from ***):

$${\mu_n} = C$$

and therefore (from **)

$${\xi _n} = 0$$

So here lies the problem. If a data point from this subset is in the wrong side of the decision boundary, then

$${t_n}y({x_n}) \le 0$$

and we will have (from *) $${\xi _n} \ge 1$$

which is in an obvious conflict with

$${\xi _n} = 0$$

$\endgroup$
1
$\begingroup$

Good point! Interesting consequence!

Problem is the $a_n=0$ assumption, i.e. assuming misclassified points are not support vectors.

Here is the flow. Slack variable $\xi_n$ is defined as $$\xi_n := |t_n - y(\boldsymbol{x}_n)|$$ where $t_n \in \{+1, -1\}$ is the true label, and $y(\boldsymbol{x}_n)$ is the prediction. Therefore, for a misclassified point (on the wrong side) we have $$\xi_n > 1$$ by definition. Given $\mu_n \xi_n = 0$, therefore$$\mu_n=0$$ and given $a_n=C - \mu_n$, therefore $$a_n = C > 0$$ which means (given $a_n > 0$ only for support vectors)

Every misclassified point is a support vector.

This is a nice consequence and should have been stated in the book.

Although, a remotely! related point has been stated in the book:

Points with $a_n = C$ can lie inside the margin and can either be correctly classified if $\xi_n \leq 1$ or misclassified if $\xi_n > 1$.

| 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.