# An ambiguity in SVM equations about misclassified data

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

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