# Struggling to understand threshold(b) update step in SMO

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:

$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

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$

...

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

• You will likely need to explain the meanings of all the symbols so that people can understand what these statements are trying to say. – whuber Aug 30 '16 at 15:21
• Your edit defines the overall SVM problem. You still need to define the SMO sub-problems and iteration. For example, what is $E_i$? – GeoMatt22 Aug 30 '16 at 16:43
• @GeoMatt22 I'm afraid it would be lengthy to define the whole SMO thing, however I will do it if necessary. – Cesc Aug 31 '16 at 1:07
• @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? – GeoMatt22 Aug 31 '16 at 1:23

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.

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!