10
$\begingroup$

I'm trying to understand the process for training a linear support vector machine. I realize that properties of SMVs allow them to be optimized much quicker than by using a quadratic programming solver, but for learning purposes I'd like to see how this works.

Training Data

set.seed(2015)
df <- data.frame(X1=c(rnorm(5), rnorm(5)+5), X2=c(rnorm(5), rnorm(5)+3), Y=c(rep(1,5), rep(-1, 5)))
df
           X1       X2  Y
1  -1.5454484  0.50127  1
2  -0.5283932 -0.80316  1
3  -1.0867588  0.63644  1
4  -0.0001115  1.14290  1
5   0.3889538  0.06119  1
6   5.5326313  3.68034 -1
7   3.1624283  2.71982 -1
8   5.6505985  3.18633 -1
9   4.3757546  1.78240 -1
10  5.8915550  1.66511 -1

library(ggplot2)
ggplot(df, aes(x=X1, y=X2, color=as.factor(Y)))+geom_point()

enter image description here

Finding the Maximum Margin Hyperplane

According to this Wikipedia article on SVMs, to find the maximum margin hyperplane I need to solve

$$ \arg\min_{(\mathbf{w},b)}\frac{1}{2}\|\mathbf{w}\|^2 $$ subject to (for any i = 1, ..., n) $$ y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1. $$

How do I 'plug' my sample data into a QP solver in R (for instance quadprog) to determine $\mathbf{w}$?

$\endgroup$
  • $\begingroup$ You have to solve the dual problem $\endgroup$ – user83346 Nov 3 '15 at 18:08
  • 2
    $\begingroup$ @fcop can you elaborate? What is the dual in this case? How do I solve using R? etc. $\endgroup$ – Ben Nov 3 '15 at 18:24
5
$\begingroup$

HINT:

Quadprog solves the following:

$$ \begin{align*} \min_x d^T x + 1/2 x^T D x\\ \text{such that }A^T x \geq x_0 \end{align*} $$

Consider $$ x = \begin{pmatrix} w\\ b \end{pmatrix} \text{and } D=\begin{pmatrix} I & 0\\ 0 & 0 \end{pmatrix} $$

where $I$ is the identity matrix.

If $w$ is $p \times 1$ and $y$ is $n \times 1$:

$$ \begin{align*} x &: (2p+1) \times 1 \\ D &: (2p+1) \times (2p+1) \end{align*} $$

On similar lines: $$ x_0 = \begin{pmatrix} 1\\ 1 \end{pmatrix}_{n \times 1} $$

Formulate $A$ using the hints above to represent your inequality constraint.

$\endgroup$
  • 1
    $\begingroup$ I'm lost. what is $d^T$? $\endgroup$ – Ben Nov 4 '15 at 4:17
  • 1
    $\begingroup$ What is the coefficient of $w$ in your objective function? Not $||w||^2_2$ but $w$? $\endgroup$ – rightskewed Nov 4 '15 at 4:19
  • 1
    $\begingroup$ Appreciate the help. I thought I figured this out but when I set D = the matrix you suggest quadprog returns the error "matrix D in quadratic function is not positive definite!" $\endgroup$ – Ben Nov 4 '15 at 4:53
  • 2
    $\begingroup$ HACK: Perturb $D$ by adding a small value say $1e-6$ on the diagonal $\endgroup$ – rightskewed Nov 4 '15 at 4:59
5
$\begingroup$

Following rightskewed's hints...

library(quadprog)

# min(−dvec^T b + 1/2 b^T Dmat b) with the constraints Amat^T b >= bvec)
Dmat       <- matrix(rep(0, 3*3), nrow=3, ncol=3)
diag(Dmat) <- 1
Dmat[nrow(Dmat), ncol(Dmat)] <- .0000001
dvec       <- rep(0, 3)
Amat       <- as.matrix(df[, c("X1", "X2")])
Amat <- cbind(Amat, b=rep(-1, 10))
Amat <- Amat * df$Y
bvec       <- rep(1, 10)
solve.QP(Dmat,dvec,t(Amat),bvec=bvec)

plotMargin <- function(w = 1*c(-1, 1), b = 1){
  x1 = seq(-20, 20, by = .01)
  x2 = (-w[1]*x1 + b)/w[2]
  l1 = (-w[1]*x1 + b + 1)/w[2]
  l2 = (-w[1]*x1 + b - 1)/w[2]
  dt <- data.table(X1=x1, X2=x2, L1=l1, L2=l2)
  ggplot(dt)+geom_line(aes(x=X1, y=X2))+geom_line(aes(x=X1, y=L1), color="blue")+geom_line(aes(x=X1, y=L2), color="green")+
    geom_hline(yintercept=0, color="red")+geom_vline(xintercept=0, color="red")+xlim(-5, 5)+ylim(-5, 5)+
    labs(title=paste0("w=(", w[1], ",", w[2], "), b=", b))
}

plotMargin(w=c(-0.5065, -0.2525), b=-1.2886)+geom_point(data=df, aes(x=X1, y=X2, color=as.factor(Y)))

enter image description here

$\endgroup$

Your Answer

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

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