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

2 Answers 2

8
$\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 margin, 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$
2
$\begingroup$

Considering a general primal problem: $$\min_w f(w)$$ subject to $$g_i(w)\leq 0 \forall i, h_j(w)=0 \forall j$$ This gives us the Lagrangian: $$ \mathcal{L}(w,\alpha,\beta) = f(w) +\sum_i\alpha_i g_i(w) + \sum_j\beta_j h_j(w) $$

KKT condition says that $\alpha_i^*g_i(w^*) = 0 \forall i$

Now let us state the soft margin SVM: $$\min_w \frac 12 w^Tw + C\sum_{i=1}^m \xi_i$$ subject to $$y_i(w^Tx_i+b)\geq 1-\xi_i \forall i \in \{1,2,..,m\}$$ $$\xi_i\geq 0 \forall i \in \{1,2,..,m\}$$

It is importatnt to notice that both of these constraints are inequalities. This means both of these will appear in the KKT conditions. This solves your trouble:

I am troubled that $\xi_i$ doesn't appear in the complementary condition.

(It does).

The Lagrangian can then be written as: $$\mathcal{L}(w,b,\xi,\alpha,r) = \frac{1}{2}w^Tw + C\sum_{i=1}^m{\xi_i} - \sum_{i=1}^m \alpha_i [y_i (w^Tx_i+b)-1+\xi_i] - \sum_{i=1}^m r_i \xi_i$$

We have by setting derivative wrt $\xi_i$ to 0: $$\alpha_i+r_i=C \forall i \in \{1,2,..,m\}$$

Applying the KKT condition at optimal point: $$\alpha_i[y_i(w^Tx_i+b)-1+\xi_i] = 0 \forall i \in \{1,2,..,m\}$$ $$r_i\xi_i = 0 \forall i \in \{1,2,..,m\}$$ Case 1: $$\alpha_i=0\implies r_i=C\implies \xi_i = 0 \implies y_i(w^Tx_i+b)-1+0\geq 0 $$ $$ \implies y_i(w^Tx_i+b)\geq1$$ Case 2: $$0<\alpha_i<C\implies 0<r_i<C\implies \xi_i = 0 \implies y_i(w^Tx_i+b)-1+0=0 $$ $$ \implies y_i(w^Tx_i+b)=1$$ Case 3: $$\alpha_i=C\implies r_i=0\implies \xi_i \geq 0 \implies y_i(w^Tx_i+b)-1+\xi_i=0, \xi_i\geq 0$$ $$\implies y_i(w^Tx_i+b)\leq1$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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