3
$\begingroup$

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.

reference to the paper

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

reference to the paper

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)$?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

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

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