20
$\begingroup$

Given the support vectors of a linear SVM, how can I compute the equation of the decision boundary?

$\endgroup$
4
  • $\begingroup$ w = sum over i (ai ti xi). you will have to minimize the lagrangian to find the values of the multipliers, ai. i wonder how u got the support vectors ? the same process should also give u the value of ai's. $\endgroup$
    – euphoria83
    Commented Dec 2, 2010 at 10:15
  • $\begingroup$ Welcome to the site, @Nepze Tyson. This isn't an answer to the OP's question. Please only use the "Your Answer" field to provide answers. If you have your own question, click the [ASK QUESTION] at the top of the page & ask it there, then we can help you properly. Since you are new here, you may want to read our tour page, which contains information for new users. $\endgroup$ Commented Jan 30, 2014 at 23:30
  • $\begingroup$ @Nepze Thank you for your perceptive comment and for the time and attention you took in order to make it. I expect it will lead to an improved answer here. I would also like to join gung in welcoming you to our site. $\endgroup$
    – whuber
    Commented Feb 1, 2014 at 21:24
  • $\begingroup$ @dshin: see stats.stackexchange.com/questions/164935/… $\endgroup$
    – user83346
    Commented Aug 15, 2015 at 10:19

2 Answers 2

30
$\begingroup$

The Elements of Statistical Learning, from Hastie et al., has a complete chapter on support vector classifiers and SVMs (in your case, start page 418 on the 2nd edition). Another good tutorial is Support Vector Machines in R, by David Meyer.

Unless I misunderstood your question, the decision boundary (or hyperplane) is defined by $x^T\beta + \beta_0=0$ (with $\|\beta\|=1$, and $\beta_0$ the intercept term), or as @ebony said a linear combination of the support vectors. The margin is then $2/\|\beta\|$, following Hastie et al. notations.

From the on-line help of ksvm() in the kernlab R package, but see also kernlab – An S4 Package for Kernel Methods in R, here is a toy example:

set.seed(101)
x <- rbind(matrix(rnorm(120),,2),matrix(rnorm(120,mean=3),,2))
y <- matrix(c(rep(1,60),rep(-1,60)))
svp <- ksvm(x,y,type="C-svc")
plot(svp,data=x)

Note that for the sake of clarity, we don't consider train and test samples. Results are shown below, where color shading helps visualizing the fitted decision values; values around 0 are on the decision boundary.

alt text

Calling attributes(svp) gives you attributes that you can access, e.g.

alpha(svp)  # support vectors whose indices may be 
            # found with alphaindex(svp)
b(svp)      # (negative) intercept 

So, to display the decision boundary, with its corresponding margin, let's try the following (in the rescaled space), which is largely inspired from a tutorial on SVM made some time ago by Jean-Philippe Vert:

plot(scale(x), col=y+2, pch=y+2, xlab="", ylab="")
w <- colSums(coef(svp)[[1]] * x[unlist(alphaindex(svp)),])
b <- b(svp)
abline(b/w[1],-w[2]/w[1])
abline((b+1)/w[1],-w[2]/w[1],lty=2)
abline((b-1)/w[1],-w[2]/w[1],lty=2)

And here it is:

alt text

$\endgroup$
2
  • 4
    $\begingroup$ Beautiful, exactly what I was looking for. The two lines: w <- colSums(coef(svp)[[1]] * x[unlist(alphaindex(svp)),]) b <- b(svp) were a godsend. Thank you! $\endgroup$
    – dshin
    Commented Dec 6, 2010 at 21:54
  • $\begingroup$ @chi: it may be interesting to take a look at my answer to "how to compute the decision boundary of an SVM": stats.stackexchange.com/questions/164935/… $\endgroup$
    – user83346
    Commented Aug 15, 2015 at 15:44
4
$\begingroup$

It's a linear combination of the support vectors where the coefficients are given by the Lagrange multipliers corresponding to these support vectors.

$\endgroup$

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