Support Vector Machines and the Maximum Margin
You have already met classifiers that draw a straight line between two groups, like logistic regression and LDA. A support vector machine draws a straight boundary too, but it chooses that boundary by one strikingly simple and powerful principle: leave the widest possible empty street between the classes.
Below is a support vector machine at work. The circled points, its support vectors, are the only ones that shape the boundary, and switching the kernel bends that boundary to fit. This course is about that machine. This first lesson builds its beating heart on one concrete job a straight line can handle: sorting ripe tomatoes from unripe ones off two cheap sensor readings. Given many lines that all split the two groups, what makes one of them the best?
By the end of this lesson you will be able to:
- Explain what the margin is and why the widest-margin boundary is the most reliable one
- Read the boundary equation, the margin, and the max-margin problem, with every symbol defined
- Find the support vectors, and predict how the boundary moves when a point changes
- Fit a linear SVM in R, count its support vectors, and tune its cost
Prerequisites: you can fit and read a basic classifier and know what a training set and a decision boundary are; you have seen at least one straight-boundary classifier such as logistic regression or LDA. A scatter plot and a straight-line equation are all the geometry you need.
Many lines separate them; which do we trust?
A tomato packing line needs to sort fruit into ripe (ship today) and unripe (back to the shelf), automatically, from two cheap sensor readings: redness, a 0 to 10 colour score, and give, how many millimetres the skin dents under a standard press. Ripe tomatoes are redder and softer (high give); unripe ones are greener and firmer (low give). Plotted, they form two clean clouds with an empty strip between them.
Each lesson runs in a fresh R session, so we build a small labelled batch right here: 20 ripe and 20 unripe tomatoes. The three dashed lines below all separate the batch perfectly, every ripe tomato on one side, every unripe one on the other.
All three lines score 100% on this training batch, yet they are clearly different rules. A tomato that lands in the gap tomorrow could be graded ripe by one line and unripe by another. So "separates the training data" cannot be the whole story. We need a reason to prefer one line over all the others.
The best line has the widest street
Picture each candidate line as the centre of a road, with the road widened outward on both sides until it just touches the nearest tomato. That road is the margin: the empty band around the boundary. A line squeezed right up against the points has a thin margin; a line running down the middle of the gap has a fat one.
The support vector machine picks the boundary with the widest street. The intuition is about safety. A new tomato measured tomorrow will land somewhere near, but not exactly on, the training points. The more empty space between the boundary and each class, the more a slightly-off tomato can wander and still be graded correctly. A thin margin leaves no room for error.
Here is that best boundary, fit for real on the batch above. The solid line is the boundary; the two dashed lines are the edges of the street; and the two ringed tomatoes are the ones the street is resting against.
Which line does the SVM choose?
You have three lines that all separate the training tomatoes perfectly. A support vector machine has to pick one. Which does it keep, and why?
Writing the margin down
Now the same idea in symbols, because the formula is what R actually optimizes. A straight boundary in two dimensions is a line; in general it is a hyperplane, written \(w^\top x + b = 0\). Here \(x\) is a tomato's feature vector (its redness and give), \(w\) is the weight vector, a direction with one number per feature that points across the boundary, and \(b\) is a single offset number that slides the boundary in or out. The expression \(w^\top x\) is the dot product: multiply matching entries and add them, \(w_1 x_1 + w_2 x_2\). A tomato scores \(w^\top x + b\); we call it ripe when that score is positive and unripe when it is negative, so the boundary is exactly where the score is 0.
How far is a tomato from the boundary? Its signed distance is
\[ \frac{w^\top x + b}{\lVert w \rVert}, \qquad \lVert w \rVert = \sqrt{w_1^2 + w_2^2} \]
where \(\lVert w \rVert\) is the length of the weight vector. The sign says which side; the size says how far.
We are free to rescale \(w\) and \(b\) together without moving the boundary at all (doubling both gives the same line). SVMs spend that freedom to fix the scale so the closest points on each side land exactly at \(w^\top x + b = +1\) and \(w^\top x + b = -1\). Those two parallel lines are the edges of the street. With that scaling the distance from the boundary to each edge, the margin, is \(\frac{1}{\lVert w \rVert}\), so the full street width is \(\frac{2}{\lVert w \rVert}\).
Making the street as wide as possible therefore means making \(\lVert w \rVert\) as small as possible. The whole training problem collapses to one clean sentence:
\[ \text{minimize } \tfrac{1}{2}\lVert w \rVert^2 \quad \text{subject to } \quad y_i\,(w^\top x_i + b) \ge 1 \ \text{ for every tomato } i \]
where \(y_i = +1\) for a ripe tomato and \(y_i = -1\) for an unripe one. The constraint says every tomato must be on its correct side and outside the street; the objective says, among all boundaries that manage that, take the one with the widest street. Minimizing \(\tfrac12\lVert w\rVert^2\) rather than \(\lVert w\rVert\) itself picks the very same winner; the square and the \(\tfrac12\) only turn it into a smooth problem the solver handles cleanly. R solved exactly this a moment ago, and we can read the answer back out:
So this boundary is 2.77 sensor-units wide from curb to curb, and no separating line for this batch is wider.
Support vectors: the points that hold the street
Look again at the constraint \(y_i(w^\top x_i + b) \ge 1\). For most tomatoes it is slack: they sit comfortably beyond the street, so \(y_i(w^\top x_i + b) > 1\). For a special few it is tight, \(y_i(w^\top x_i + b) = 1\): they land exactly on a margin line. Those points are the support vectors, and they are the only ones the boundary touches.
The solution has a beautiful property that makes this precise. The weight vector is a weighted sum of the support vectors alone,
\[ w = \sum_i \alpha_i\, y_i\, x_i, \qquad \alpha_i > 0 \ \text{only for support vectors} \]
where each \(\alpha_i\) is a weight the optimizer assigns to tomato \(i\). Every tomato that is not a support vector gets \(\alpha_i = 0\), so it contributes nothing to \(w\). On our batch, of all 40 tomatoes, exactly 2 are support vectors, one from each class, and each sits precisely on its margin line (signed score \(+1\) and \(-1\)):
Just 2 tomatoes out of 40 decide where the boundary goes. The other 38 are, as far as the SVM is concerned, along for the ride.
Only the support vectors matter
That claim is strong enough to be worth testing rather than trusting. If only the support vectors set the boundary, then two things must be true: moving a tomato that is not a support vector should change nothing, and moving one that is a support vector should change the boundary. Let us check both on the real fit.
Byte-for-byte the same weight vector, \((0.425, 0.583)\). Deleting an interior tomato did not nudge the boundary at all. Now move support vector row 14 about 1.6 units toward the other class, into the street, and refit:
The weight vector swung from \((0.425, 0.583)\) to \((0.674, 3.083)\), and the street collapsed from 2.77 units wide to 0.63. One support vector leaned on the boundary and dragged it right across; one interior point vanished and the boundary never noticed.
Nudge an interior tomato
Your fitted SVM has 2 support vectors. You reach into the ripe cloud and slide a tomato that is sitting comfortably deep inside it (not one of the support vectors) a little further from the boundary. What happens to the decision boundary?
Fit a linear SVM in R
Time to drive it. In R, the e1071 package fits an SVM with svm(). A fresh session starts empty, so the batch is rebuilt first. Fill in the kernel argument so it fits a straight (linear) boundary, then read how many support vectors it used.
Show answer
fit <- svm(grade ~ redness + give, data = tomatoes,
kernel = "linear", cost = 10, scale = FALSE)
fit
#> Parameters:
#> SVM-Type: C-classification
#> SVM-Kernel: linear
#> cost: 10
#> Number of Support Vectors: 2The soft margin, for classes that overlap
Our batch had a tidy empty strip between ripe and unripe. Real crops are messier: a few firm-but-red tomatoes and a few soft-but-green ones land in each other's territory, and then no straight line can separate them. The hard rule "every point outside the street" has no solution.
The fix is to allow a few violations, but to charge for them. We give each tomato a slack \(\xi_i \ge 0\) (the Greek letter xi) that measures how far it intrudes past its margin, and loosen the constraint to \(y_i(w^\top x_i + b) \ge 1 - \xi_i\). A tomato with \(\xi_i = 0\) is well-behaved; \(0 < \xi_i < 1\) means it slipped inside the street but is still on the correct side; \(\xi_i > 1\) means it is outright misclassified. We then minimize
\[ \tfrac{1}{2}\lVert w \rVert^2 \; + \; C \sum_i \xi_i \]
The first term still wants a wide street. The second term, weighted by the cost \(C\), adds up all the trespassing and penalizes it. So \(C\) is a dial. A large \(C\) makes each violation expensive, so the optimizer shrinks the street to avoid them, hugging the data tightly. A small \(C\) shrugs off violations in exchange for a wider, calmer margin. Watch the dial turn on a genuinely overlapping crop:
Small \(C\) gives a wide street held up by many support vectors and a slightly lower training score; large \(C\) narrows the street, leans on fewer points, and squeezes out a bit more training accuracy. Which is better on new tomatoes is the bias-variance question, and it is exactly what you tune \(C\) for.
Turn the cost dial down
Using the overlapping crop below, fit a very forgiving SVM by setting a small cost, and count its support vectors. Fill in the cost so it equals 0.1.
Show answer
soft <- svm(grade ~ redness + give, data = ov,
kernel = "linear", cost = 0.1, scale = FALSE)
soft$tot.nSV
#> [1] 17What does a very large C do?
You crank the cost \(C\) up to a very large value on an overlapping dataset. What is the effect on the boundary?
Three things that will bite you
The linear SVM is elegant, but three practical facts decide whether it works in the wild.
- Standardize your features first. An SVM measures distance, so a feature with a big numeric range (say income in rupees) drowns out one with a small range (say age in years). Put every feature on a comparable scale before fitting;
svm()does this by default (scale = TRUE), and we only switched it off here so the boundary maths lined up with the raw axes. - Outliers can drag a large-C boundary. Because a support vector on the wrong side pulls hard, one mislabelled or freak tomato can swing a high-cost boundary noticeably. A smaller \(C\) is more robust to it.
- A straight line is not always enough. If the ripe tomatoes formed a ring around the unripe ones, no line, at any margin, could separate them. That is the wall this lesson stops at, and the kernel trick is what climbs over it: it bends the boundary into curves by lifting the points into a higher-dimensional space where a flat cut works again. Toggle the widget below from Linear to RBF to see a straight boundary fail on looping data and a curved one succeed.
That curved boundary, and the two dials (\(C\) and gamma) that shape it, are Lesson 2.
References
A few authoritative places to take this further:
- Cortes and Vapnik (1995), "Support-Vector Networks", Machine Learning 20(3) - the paper that introduced the soft-margin SVM.
- An Introduction to Statistical Learning, ch. 9 (free PDF) - the gentlest rigorous treatment of the maximal margin classifier, support vectors, and the SVM, with R labs.
- The Elements of Statistical Learning, ch. 12 (free PDF) - support vector machines with the full optimization and the kernel view.
- e1071 svm vignette (CRAN) - the package you used here, with its options and examples.
Lesson 1 complete
You can now explain the whole chain. Many lines separate two clean classes, and an SVM keeps the one with the widest street, because that leaves the most room for a slightly-off new point. That street is written \(w^\top x + b\) with width \(2/\lVert w\rVert\), and training it means minimizing \(\tfrac12\lVert w\rVert^2\) so the margin is as wide as possible. Only a handful of points, the support vectors on the margin lines, actually fix the boundary; you proved it by moving one and watching the street collapse. And when classes overlap, the soft margin and its cost \(C\) trade margin width against training errors, the SVM's bias-variance dial.
Next, Lesson 2: Kernel SVMs and the kernel trick. You will see how the polynomial and RBF kernels bend the boundary to wrap classes no straight line can separate, and how the two dials \(C\) and gamma trade fit against smoothness.