Optimizing a Support Vector Machine with Quadratic Programming

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() 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}$?

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

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.

• I'm lost. what is $d^T$? – Ben Nov 4 '15 at 4:17
• What is the coefficient of $w$ in your objective function? Not $||w||^2_2$ but $w$? – rightskewed Nov 4 '15 at 4:19
• 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!" – Ben Nov 4 '15 at 4:53
• HACK: Perturb $D$ by adding a small value say $1e-6$ on the diagonal – rightskewed Nov 4 '15 at 4:59

Following rightskewed's hints...

# 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*x1 + b)/w
l1 = (-w*x1 + b + 1)/w
l2 = (-w*x1 + b - 1)/w
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, ",", w, "), 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))) 