I wonder if the SVM optimization problem
minimize $||w||^2$
with the contraints $y_i(w^\intercal x_i+b)\ge 1$
could be formulated as a typical quadratic programming problem:
$0.5\cdot z^\intercal Mz$
with $Az\leq d$ and setting z to the vector $\left (\begin{array}{l}w_1\\\ldots\\w_n\\b\end{array} \right )$.
The expression $||w||^2$ can be obtained by setting $M$ to $I$.
There is only one problem, $b$ doesnt show up in the objective function.
so i would have to introduce a zero line in $M$ but then it isn't invertible any more. Should I take the pseudo-inverse instead? Thanks for any hints.
Asked
Active
Viewed 396 times
0
-
SVM does reduce to a QP problem in the dual form. There are plenty of resources out there to explain it. To handle b you would add a 1 line, not a zero line. – Tpofofn Apr 03 '15 at 18:30
-
a thanks a lot for the answer, do you know some resource where this is stated maybe? Actually I am not 100% convinced of the solution. – Tim vor der Brück Apr 03 '15 at 20:28
-
Elements of Statistical Learning by Hastie et al is one. Pretty much any book that covers SVM's will have it though. – Batman Apr 03 '15 at 20:56
-
Adding a rows of 1 to matrix M, as @Tpofofn states doesn't seem to make sense. – mathse Apr 03 '15 at 20:59
1 Answers
0
My guess is to to let $z=(w_1,\ldots,w_n,b)^\intercal$, to set $M$ to
$$M = [I_{n\times n} 0_{n\times 1}; 0_{(n+1)\times (n+1)}].$$
and to stack a column of $1$'s in the last column of $A$.
Then solve via a QP solver.
mathse
- 2,438
- 12
- 18