4
$\begingroup$

I'm trying to implement a Support Vector Machine classifier in R and I have to solve the optimization problem using the quadprog R package which solves problems of the form :

$$min_b \frac{1}{2} b^tDb-d^tb$$

such that : $A^tb \geq b_0$

In my case :

$$ A^t = \left(\begin{array} II\\ z^t \end{array}\right) $$

Where $z$ is a vector containing the label ($1$ or $-1$) for each training instance, $b_0$ a vector of $0$

and $D = ZY_xY_x^tZ$

where $Z$ is a diagonal matrix with the $z$ labels in its diagonal and $Y_x$ is a matrix that contains the training instances.

(here is the documentation of the quadprog solver : http://svitsrv25.epfl.ch/R-doc/library/quadprog/html/solve.QP.html)

In my case, I want to solve the soft margin problem, then I have to introduce the $\gamma$ constant and put it in

$A^tb \geq b_0$

in order to satisfy the following constraint :

$\gamma \geq A^tb \geq b_0$

So my first question is : How can I integrate $\gamma$ in $A^t$ to satisfy the previous constraint ? And what is the best way to do it in R (which function to use, ...)?

The solve.QP function of the quadprod package returns an $\alpha$ vector (in \$solution) where the $y_i$ for each $\alpha_i > 0$ is a support vector.

With this information, I can now find the $g(x)$ function :

$$g(x) = \sum_i \alpha_i z_i y_i^t x + b_0$$

Which gives the equation of the hyperplane separating the instances of the two classes (am I right ?).

My second question is : What does the argument x represent ? Am I missing something ?

You can find my code here : http://pastebin.com/t6xj5SXTdescription

$\endgroup$
  • $\begingroup$ the $x$ in your second question is one row of what you wrote $Y_x$ above. $\endgroup$ – user603 May 12 '13 at 23:03

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.