3
$\begingroup$

Currently reading Platt's paper, Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines , I got stuck in section 2.3 Computing the Threshold:

SVM notation


objective function: \begin{array}{1} \max _{\alpha }\sum _{i=1}^{n}\alpha _{i}-{\frac {1}{2}}\sum _{i=1}^{n}\sum _{j=1}^{n}y_{i}y_{j}K_{ij}\alpha _{i}\alpha _{j}\\ 0\leqslant \alpha_i \leqslant C : Lagrange multipliers\\ \sum_{i=1}^Nyi\alpha_i=0\\ \end{array}

KKT condition:

\begin{array}{l} \quad {a_i} = 0 \quad \Leftrightarrow \quad {y_i}u_i \ge 1\\ 0 < {a_i} < C \quad \Leftrightarrow \quad {y_i}u_i = 1\\ \quad {a_i} = C \quad \Leftrightarrow \quad {y_i}u_i \le 1 \end{array}

$b$: threshold in SVM model $w^Tx-b$

$u_i=\sum_{j=1}^Ny_j\alpha_jK_{ij}-b$: predict value using SVM

$E_i=u_i-y_i$: difference between target and prediction

$K_{ij}=K(x_i, x_j)=K(x_j,x_i)$: the kernel matrix


Brief description about SMO


According to Platt, SMO optimize two Lagrange multipliers one time, for example:

$y_1\alpha_1+y_2\alpha_2=-\sum_{i=3}^Ny_i\alpha_i=Const$ SMO-SUB

...

Update $\alpha_i$

...

The question

  1. if $\alpha_i$ is not at bound, threshold $b$ can be computed by forcing the output to be $y_i$: $b_i=E_i+y_i(\alpha^{new}_1-\alpha_1)K_{11}+y_2(\alpha_2^{new,clipped}-\alpha_2)K_{12}+b^{old}$ (eq.1)

  2. if both $\alpha_1$ and $\alpha_2$ are at bound, then using eq.1 computing $b_1$ and $b_2$, all thresholds between $b_1$ and $b_2$ are consistent with KKT conditions.


I understand case 1 since $0<\alpha_i<C$,we get $y_iu_i=1$, prediction error must be 0, but I failed to understand case 2...

$\endgroup$
4
  • 1
    $\begingroup$ You will likely need to explain the meanings of all the symbols so that people can understand what these statements are trying to say. $\endgroup$ – whuber Aug 30 '16 at 15:21
  • $\begingroup$ Your edit defines the overall SVM problem. You still need to define the SMO sub-problems and iteration. For example, what is $E_i$? $\endgroup$ – GeoMatt22 Aug 30 '16 at 16:43
  • $\begingroup$ @GeoMatt22 I'm afraid it would be lengthy to define the whole SMO thing, however I will do it if necessary. $\endgroup$ – Cesc Aug 31 '16 at 1:07
  • $\begingroup$ @CescFangs thanks for the expansion. I skimmed the paper briefly. One thing your presentation does not include is the linear equality constraint on the $\alpha$'s, which is $\sum_iy_i\alpha_i=0$ I believe. For the sub-problem, this means there is only one degree of freedom, which he shows as a line in the $(\alpha_1,\alpha_2)$ plane. This seems relevant to your case 2, which is similarly talking about a "line segment" in $b$ space? $\endgroup$ – GeoMatt22 Aug 31 '16 at 1:23
0
$\begingroup$

I don't think the answer is obvious. Without figuring out their notation and possibly getting my pencil out, I can't get you all the way to an answer. But I think the following will get you pretty close:

In general in SVMs, if you can find at least one $\alpha_i$ "not at bound", then you can find $b$ in a straightforward way (which amounts to your Eqn 1 in this context). Otherwise, according to the paper "A Note On Support Vector Machine Degeneracy" by Rifkin et al., the problem is degenerate, which means it has a solution for which $w=0$. Moreover, according to their Lemma 6, the solution has $b=1$ if there are more training examples in the positive class, $b=-1$ if there are more training examples in the negative class, and $b \in [-1,1]$ if there are equally many examples in each class.

This must reduce to their claim in Eqn 2 for their special case.

$\endgroup$
0
$\begingroup$

I figured it out finally:

when both $\alpha_1$ and $\alpha_2$ are at bound, then using eq.1 computing $b_1$ and $b_2$, all thresholds between $b_1$ and $b_2$ are consistent with KKT conditions.

let $b^{new}=tb_1+(1-t)b_2,0\leqslant t\leqslant1$, i.e.,$b^{new}$ is between $b_1$and $b_2$, we have:

$$ \begin{split} b^{new}&=tb_1+(1-t)b_2\\ &=t(E_1+y_1(\alpha_1^{new}-\alpha_1)K_{11}+y_2(\alpha_2^{new}-\alpha_2)K_{12}+b)+(1-t)(E_2+y_2(\alpha_2^{new}-\alpha_2)K_{22}+y_1(\alpha_1^{new}-\alpha_1)K_{12}+b)\\ \end{split} $$

since both $\alpha_1$ and $\alpha_2$ are at bound, $\alpha_2$ probably have been clipped(see figure in the question), so we introduce $0\leqslant \lambda\leqslant1$ to update $\alpha_2$: $$ \alpha_2^{new}=\alpha_2+\lambda\frac{y_2(E_1-E_2)}{\eta}\quad(see \ eq.16\ in\ SMO\ paper ) $$


$$\begin{split} E_1^{new}&=E_1+y_2(\alpha_2^{new}-\alpha_2)K_{12}+(\alpha_1^{new}-\alpha_1)y_1K_{11}-\Delta b\\ E_2^{new}&=E_2+y_2(\alpha_2^{new}-\alpha_2)K_{22}+(\alpha_1^{new}-\alpha_1)y_1K_{12}-\Delta b\\ \Delta b&=b^{new}-b\\ &=E_2+y_1(\alpha_1^{new}-\alpha_1)K_{12}+y_2(\alpha_2^{new}-\alpha_2)K_{22}+t[E_1-E_2+y_1(\alpha_1^{new}-\alpha_1)(K_{11}-K_{12})+y_2(\alpha_2^{new}-\alpha_2)(K_{12}-K_{22})]\\ \end{split}$$

substitute $\Delta b$ into $E_1^{new}$ and $E_2^{new}$, we have: $$\begin{split} E_1^{new}&=(1-t)(1-\lambda)(E_1-E_2)\\ E_2^{new}&=-t(1-\lambda)(E_1-E_2)\\ \end{split} $$


take $\alpha_1=\alpha_2=C$ for example:

$$\begin{split} \alpha_2^{new}-\alpha_2&=\lambda\frac{y_2(E_1-E_2)}{\eta} \geqslant 0\\ &\Leftrightarrow y_2(E_1-E_2) \geqslant 0\\ &\Leftrightarrow -t(1-\lambda)y_2(E_1-E_2)\leqslant 0\\ &i.e., y_2E_2^{new}\leqslant 0 \end{split}$$

for $\alpha_1$: $$\begin{split} \alpha_1^{new}-\alpha_1&=s(\alpha_2-\alpha_2^{new})\geqslant 0\\ &\Leftrightarrow-s\lambda\frac{y_2(E_1-E_2)}{\eta}\geqslant 0\\ &\Leftrightarrow-\lambda\frac{y_1(E_1-E_2)}{\eta}\geqslant 0\\ &\Leftrightarrow y_1(E_1-E_2)\leqslant 0\\ &\Leftrightarrow (1-t)(1-\lambda)y_1(E_1-E_2)\leqslant 0\\ &i.e., y_1E_1^{new}\leqslant 0 \end{split}$$

KKT condition holds!

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