Trjtdtk

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:

$$Csumlimits_n = 1^N xi _n + 1 over 2left$$

Subject to this constraints(*):

$$xi _n ge 0$$
$$t_ny(x_n) ge 1 - xi _n$$

where:

$$y(x_n) = w^Tx_n + b$$

so the corresponding Lagrangian function for this problem is:

$$L(w,b,a) = Csumlimits_n = 1^N xi _n + 1 over 2left - sumlimits_n = 1^N a_n t_ny(x_n) - 1 + xi _n - sumlimits_n = 1^N mu _nxi _n $$

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

$$a _n ge 0$$

$$t_ny(x_n) - 1 + xi _n ge 0$$

$$a_n(t_ny(x_n) - 1 + xi _n) = 0$$

$$xi _n ge 0$$

$$mu _n ge 0$$

$$mu _nxi _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_ny(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(boldsymbolx_n)|$$
where $t_n in +1, -1$ is the true label, and $y(boldsymbolx_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$.