# SVM Training: Working Set Selection

This is related to Joachims's 1998 paper on training SVMs (link to paper). In 11.3, I understand how the term $V(\mathbf d)$ arises as a result of a first order approximation, and why it needs to be minimized.

I do not understand how the method in 11.3.2 arises from the description in 11.3.

How does the quantity $\omega_i$ represent $V(\mathbf d)$?

And how does picking the top and bottom $q/2$ terms imply minimizing $V(\mathbf d)$?

## 1 Answer

Since no one answered this, I may as well put down what I found:

Our task was to minimize the first order term in the Taylor series expansion of the objective function, namely $d^T\nabla f(\alpha)$

We will call the gradient term $G$.

As explained in section 11.3, $d_i$ is bounded by $\pm 1$. Now of all $d_i$, only two are chosen to optimize over (recall, we only pick two $\alpha$ values) so the vector $d$ will look like $[0, 0..., d_a,0...,d_b,0...,0]$

The resulting term that needs to be minimized is therefore $d_a G_a+ d_bG_b$. We would like this term to be as negative as possible, so we must pick between the boundary values of $d_i$ based on the sign of $G_i$.

Now recall from the SMO algorithm the index sets and combine the constraints of $y$ and $d$ for the index $i$: $i\in I_{up} \implies d_iy_i>0$ and $i\in I_{low} \implies d_iy_i<0$

Since we're looking at boundary values, we can simplify this to $i\in I_{up} \implies d_i=y_i$ and $i\in I_{low} \implies d_i=-y_i$.

Therefore, the minimization described above can be brought to the form $min \ (\pm)y_aG_a + (\pm)y_bG_b$ which can be minimized over all indices if we evaluate the product $F=y_iG_i$ for all $i$ and pick:

$min \ F_i$ for $i$ in $I_{up}$ and $max \ F_i$ for $i$ in $I_{low}$ which will ensure both terms are as negative as possible.