19
$\begingroup$

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

$\endgroup$
  • $\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 Dec 2 '10 at 10:15
  • 2
    $\begingroup$ I cannot comment yet but I think in the accepted answer shouldn't the decision line and margins be: abline(b/w[2],-w[1]/w[2]) abline((b+1)/w[2],-w[1]/w[2],lty=2) abline((b-1)/w[2],-w[1]/w[2],lty=2) since abline takes input as intercept and slope respectively? w.x-b=0 which implies: w1.x1+w2.x2=b which implies(since x2 is the "y") abline(b/w[2], -w[1]/w[2]) Sorry this is an old post but I thought I'd ask. $\endgroup$ – Nepze Tyson Jan 30 '14 at 22:43
  • $\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$ – gung Jan 30 '14 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 Feb 1 '14 at 21:24
  • $\begingroup$ @dshin: see stats.stackexchange.com/questions/164935/… $\endgroup$ – user83346 Aug 15 '15 at 10:19
29
$\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$
  • 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 Dec 6 '10 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 Aug 15 '15 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$

protected by kjetil b halvorsen Nov 8 '17 at 12:21

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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