1
$\begingroup$

I found this problem in a book. It supposedly minimizes the number of Support vectors rather than maximizing the margin:

$min_{\alpha,b} \frac{1}{2}\sum_{i=1}^{m}\alpha_{i}^{2}$
$s.t.\quad y_{i}(\sum_{j=1}^m\alpha_{j}y_{j}(x_{i}\cdot x_{j})+b)\ge1 \quad \forall i\in \{1,...m\}$

(for simplicity, I've omitted the slack variables - let's assume the problem is linearly sperable.)

I don't understand how this was derived. we get $w=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i}$ from the regular lagrangian for the SVM problem, in which $w$ is squared - thus, when we derive by $w$ and equate to 0, we get the formula for $w$. But here, $w$ is already replaced with the same expression. It makes sense - we still want to express the seperator as some combination of the input vectors. But how do you get this mathematically for this different problem?

Also, I understand that using l1 norm for $\alpha_{i}$ should make the number of support vectors even lower. how come?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.