0
$\begingroup$

I've seen other posts about using gradient descent for the primal form, but not the dual form.

In this book, the author discusses using (projected) gradient descent for the dual form: http://ciml.info/ (Chapter 11, Kernel Methods)

The problem is, it is unclear how to find the bias term, as it does not appear at all in the dual objective.

The objective is:

$L(\alpha)=\alpha^T 1 - \frac{1}{2}\alpha^TG\alpha $

Where:

$ G_{nm} = y_n y_m K(x_n, x_m) $

The constraint on $\alpha$ is:

$ C \ge \alpha_n \ge 0$

So, how can one find the bias term using this method?

$\endgroup$
1
$\begingroup$

Answering myself since I figured it out with help from http://disp.ee.ntu.edu.tw/~pujols/Support%20Vector%20Machine.pdf.

Using the KKT conditions, we have the 3 outcomes:

$ \alpha_i = 0 $, meaning $ x^{(i)} $ lies beyond the margin

$ 0 < \alpha_i < C $, implying $ x^{(i)} $ lies on the margin

$ \alpha_i = C $, meaning $ x^{(i)} $ violates the margin

We can find the data points which correspond to the second case, since if $ x^{(i)} $ lies on the margin, then:

$ y^{(i)}(w^Tx^{(i)}+b) = 1 $

Rearranging for b, we get:

$ b = y^{(i)} - w^Tx^{(i)} $

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