1
$\begingroup$

I have a problem understanding why, considering dual form, the Soft margin SVM (linear) is more general than Hard margin SVM. The dual form of the Hard Margin consists of the finding of tuple $\alpha$ maximizing $\psi(\alpha)=\ldots$ and with the constraint that $\forall i, 0\leq\alpha_i$ and $\sum_i \alpha_i y^{(i)}=0$. For Soft margin SVM it is the same thing but with the constraint that $0\leq\alpha_i\leq C$. What I understand is that there will be a (unique) solution to Hard margin (ie the data is linearly separated) if there are $\alpha$s such that $\forall i, 0\leq\alpha_i$ and $\sum_i \alpha_i y^{(i)}=0$ (so that we can after find what such $\alpha$s maximize $\psi(\alpha)$). But then, if there is some solution $\alpha$ for the soft margin SVM then it verifies $\forall i, 0\leq\alpha_i\leq C$ and $\sum_i\alpha_i y^{(i)}=0$ so it verifies the less restrictive condition $\forall i,0\leq\alpha_i$ and $\sum_i\alpha_i y^{(i)}=0$, so it will be a valid $\alpha$ for the Hard margin (not maximizing for Hard Margin I guess, so not the solution). So with this (faulty) reasoning Hard margin appears more general than Soft margin??? where is my mistake?

Maybe a simple example could show me my mistake but I get lost in the translation to the dual form...

$\endgroup$

1 Answer 1

1
$\begingroup$

Feasibility of the dual is not the same as feasibility of the primal.

You are correct that the set of feasible solutions for the soft margin problem is a subset of that of the hard margin problem. But that just makes it more likely that the hard margin dual problem is unbounded, and by weak duality that implies that the hard margin primal is infeasible.


Take a very simple example in 1 dimension: points at -1, 0, and 1, with labels +1, -1, +1 respectively. This is not linearly separable, clearly. What's the dual?

$$\max \sum \alpha_i - \frac12 \sum_{i,j} \alpha_i\alpha_j x_i x_j y_i y_j\\ \text{s.t. } \sum \alpha_i y_i = 0 \text{ & } \alpha\geq0$$

Let $\alpha=(a, 2a, a)$; for every $a\geq0$ this is a feasible solution; the second term of the objective function here has zero for every $(i,j)$ containing the point 0, so all that's left is the cross-term $(-1, 1)$ (and its reverse) and the terms $(-1,-1)$ and $(1,1)$:

$$4a - \frac12(-2a^2 + a^2 + a^2) = 4a$$

so taking $a\to\infty$ shows the program is unbounded.

$\endgroup$
1
  • $\begingroup$ But it seems to me that with gradient avoiding we have $w=\sum_i \alpha_i x^{(i)} y^{(i)}$ so that each solution in the dual formulation gives a solution in the primal. For example here it gives $w=0$ (and $b=0$ I guess): pb the data doesn't verify the constraint $y^{(i)}(\langle w,x^{(i)}\rangle+b)\geq 1$. I missed something... $\endgroup$ Feb 25 at 21:57

Your Answer

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

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