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?


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.