4
$\begingroup$

I was reading a class note on SVM from Andrew Ng (pp 19~20 from http://cs229.stanford.edu/notes/cs229-notes3.pdf) and can't understand something in the lecture note. It says that the L1-regularzed soft-margin problem is the following:

$$\begin{array}{ll} \mbox{min.} & & \frac{1}{2} ||w||^2 + C \sum \xi_i \\ \mbox{s.t.} & & y_i (w^T x_i+b) \geq 1 - \xi_i, i = 1,...,m\\ & & \xi_i \geq 0, i=1,...,m \end{array}$$

It then says that the Lagrangian is

$L(w,b,\xi, \alpha, r) = \frac{1}{2}w^Tw + C\sum{\xi_i} - \sum \alpha_i [y_i (x^Tw+b)-1+\xi_i] - \sum r_i \xi_i$

Then, it says that the KKT dual-complementarity condition are: $$\begin{array}{ll} \alpha_i = 0 & \Rightarrow & y_i (w^Tx_i + b) \geq 1 \\ \alpha_i = C & \Rightarrow & y_i (w^Tx_i + b) \leq 1 \\ 0 < \alpha_i < C & \Rightarrow & y_i (w^Tx_i + b) = 1 \end{array}$$

I don't understand the last part. Isn't the KKT dual-complementarity condition $\alpha_i [y_i (x^Tw+b)-1+\xi_i]$ = 0 -- that is, either $\alpha_i = 0$ or $ y_i (x^Tw+b)-1+\xi_i = 0$. Can anybody explain to me how the above complementarity conditions are derived? I am troubled that $\xi_i$ doesn't appear in the complementary condition.

$\endgroup$
3
$\begingroup$

Unfortunately, I am late a couple of years, but after reading Ng's lecture notes, I was asking myself the same question. The complementarity conditions you have listed follow from the other KKT conditions, namely: $$ \begin{align} \alpha_i &\geq 0 \tag{1},\\ g_i(w) &\leq 0 \tag{2},\\ \alpha_i g_i(w) &= 0 \tag{3},\\ r_i &\geq 0 \tag{4},\\ \xi_i &\geq 0 \tag{5},\\ r_i \xi_i &= 0 \tag{6}, \end{align} $$ where $$ g_i(w) = - y^{(i)} \left(w^T x^{(i}) + b\right) +1 -\xi_i. $$ Furthermore, from $$ \begin{equation} \frac{\partial \mathcal{L}}{\partial \xi_i} \overset{!}{=} 0, \end{equation} $$ we obtain the relation $$ \alpha_i = C - r_i \tag{7}. $$

Now we can distinguish the following cases:

  • $\alpha_i = 0 \implies r_i = C \implies \xi_i = 0$ (from Eq. (7) and (6)), which together with Eq. (2) gives $$ \begin{equation} y^{(i)} \left(w^T x^{(i}) + b\right) \geq 1 \tag{8} \end{equation} $$
  • $0 < \alpha_i < C \implies r_i > 0 \implies \xi_i = 0$ via Eq. (3) gives $$ \begin{equation} y^{(i)} \left(w^T x^{(i}) + b\right) = 1 \tag{9} \end{equation} $$
  • And finally $\alpha_i = C \implies r_i = 0 \implies \xi_i \geq 0$ so that, again, from Eq. (2): $$ \begin{equation} \xi_i \geq 1 - y^{(i)} \left(w^T x^{(i}) + b\right), \end{equation} $$ which we note can only be fulfilled simultaneously with Eq. (5) if $$ \begin{equation} y^{(i)} \left(w^T x^{(i}) + b\right) \leq 1, \tag{10} \end{equation} $$

Note that Eq. (8) does not contribute to the SVM, as it is classified with sufficient confidence ($\alpha_i = 0$ as for the linearly separable case). For the case $0<\alpha_i<C$, $\xi_i=0$ the points are on the decision boundary, and for $\alpha_i = C$ the points are within the margin (where depending on the value of $\xi_i$ the points are either classified correctly or incorrectly).

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