ML Explorer · Level 3 · Classic ML
Support vector machines
Of all the straight lines that split two classes, pick the one with the widest empty street around it.
Overview
Logistic regression and Naive Bayes both end with a boundary between two classes, and both get there through probabilities. A support vector machine (SVM) goes straight for the boundary, and chooses it by geometry: the line that keeps as far as it can from both classes.
One change of labels first. Earlier lessons wrote the classes as y = 0 and y = 1. In this lesson class 0 is y = −1 and class 1 is y = +1. The shapes stay the same: circles are class 0, now y = −1, and triangles are class 1, now y = +1. With these labels one test tells us whether a point is on its own side of the line, as step 3 shows.
All the points are made up. See "About the data" at the end.
You'll learn
- why an SVM picks the separating line with the widest street, and which points decide where it goes
- how the setting C trades the street's width against points inside it when the classes overlap
- how adding a new feature lets a straight-line method draw a curved boundary
-
Many lines separate
Many straight lines put every circle on one side and every triangle on the other. Which should we pick?
Here are 24 points with two features, x₁ and x₂: 12 circles and 12 triangles. The solid line splits them. It starts at a tilt of 120° and a shift of 0.5.
The dashed lines mark the street around the line: the widest band, centred on the line, with no point inside it. Its width here is 1.98.
Move the sliders. Tilt turns the line; shift slides it sideways without turning it. Some lines split the classes with a narrow street, some with a wide one, and some do not split them at all. The read-out then counts the points on the wrong side.
A line with a wide street leaves room for new points that land a little away from where their class usually sits. That is the idea behind the SVM.
The maths
A line with tilt has the unit normal , an arrow of length 1 at right angles to it. With shift , the line is every point with
and the distance from a point to the line is . The street drawn has width , twice the distance to the nearest point.
-
The margin
The street's width is set by the nearest point on each side. We call that width the margin.
The dotted lines join the line to the nearest circle and the nearest triangle. At the start, the nearest circle is 1.65 away and the nearest triangle 0.99 away.
The street is the same width on both sides of the line, so it is twice the smaller distance: 1.98.
Slide the line away from the nearer triangle and the street widens, until the two distances are equal. At this tilt the widest street is the two distances added, 2.64, with the line in the middle. The read-out calls it "centred".
Now change the tilt too. A different tilt can give a wider street still.
The maths
Write and for the distances to the nearest circle and the nearest triangle. The street has width . Sliding the line changes and by equal and opposite amounts while their sum stays the same, so the best place is the middle, with width .
In this lesson the margin is the full width of the street. Some books, ISLR among them, use the word for half of it: the distance from the line to the nearest point.
-
The widest street
The SVM picks the line with the widest street. The points on the street's edges are the support vectors.
Solving gives a street 3.61 wide, with the line at a tilt of 144.4°. No straight line has a wider empty street: trying every tilt in steps of 0.01° never beats it.
The SVM writes the line as w·x + b = 0, where w·x = w₁x₁ + w₂x₂. Here w₁ = 0.32, w₂ = 0.45 and b = −0.03. Points where w·x + b is above 0 are predicted as triangles, y = +1, and points where it is below 0 as circles, y = −1. The edges of the street are where it equals +1 and −1.
So a point is on its own side and outside the street when y × (w·x + b) is at least 1. One test works for both classes because the labels are −1 and +1.
The 3 ringed points sit exactly on the edges: 2 circles and 1 triangle. They are the support vectors. Each point is a vector of its two features, and these are the ones that hold the street in place.
The maths
Multiplying and by the same positive number does not move the line, so we choose the scale that makes for the nearest points. The distance from the line to a point is , so the street is
wide. A wider street means a shorter , so the widest street solves
This is the hard margin: no point may sit inside the street. It has an answer only when some line separates the classes.
-
Only the support vectors matter
Move a point that is not a support vector and nothing changes. Move a support vector towards or away from the line and the line moves with it.
Two points can be moved. Drag them, or select one with Tab and use the arrow keys. The page solves the problem again after every move.
Point A is a triangle clear of the street. Move it anywhere on its own side, outside the street: the line does not move, and the read-out says so.
Point B is a support vector. Move it towards or away from the line and the line and street follow; slide it along the edge of the street and the line may stay put. The dotted line shows where the boundary was. Move A into the street and it becomes a support vector, the line moves, and other points can stop being support vectors: watch the count.
If a point goes inside the street or across the line, the street may no longer be empty. The page then lets points sit inside the street, as the next step explains, and counts them. A point inside the street or on the wrong side of the line is a margin violation. "Put A and B back" resets them.
The maths
The problem can be rewritten with one number per point. This second form is called the dual. Its answer gives
and is 0 for every point off the edges of the street (in the hard margin; with the soft margin of step 5, points inside the street have ). Only the support vectors have , so only they appear in and . The maximise
with from the next step (for the hard margin there is no upper limit). The page solves it in your browser by sequential minimal optimisation, which improves two at a time, and checks the answer against the conditions for the best answer to within .
Steps 3 and 4 use = 1. On the original points the largest is 0.15, well below that limit, so the answer is exactly the hard-margin one. With = 1 the page may let a point into the street even when some line could still split the classes. The read-out then gives the margin as , the width between the dashed edges, which some points sit inside.
-
Overlap and C
When the classes overlap, no empty street exists. A soft margin lets points into the street, at a price set by C.
New made-up points: 12 circles and 12 triangles, more spread out than before. No straight line splits them.
So we let points into the street, and charge each one. The charge is its hinge loss: 0 for a point on its own edge of the street or beyond it, and growing in a straight line the further the point goes in. A point on the line itself is charged 1, and a point past the line more than 1.
The SVM now balances two things: a wide street, and a small total hinge loss. The number C sets the price of the hinge loss. The ringed support vectors are now the points on an edge, inside the street or on the wrong side.
Move C. At C = 0.01 violations are cheap: the street is 6.66 wide and 22 points are margin violations. At C = 100 they are dear: the street narrows to 1.59 and 4 points are violations. On these points nothing changes above C = 10. At every C at least one point stays on the wrong side, because the classes overlap.
Small C gives a wide street that shrugs off a few odd points; large C gives a narrow street that bends to fit them. The right C is the one that does best on new data, chosen as in Train and test.
The maths
The soft margin gives each point a slack , how far it is allowed past its edge of the street:
At the best answer each slack is the hinge loss
The margin is still , but now some points sit inside the street. As grows, the street can only narrow or stay the same, on any data. Compare the best answers for : each is at least as good as the other under its own , and adding the two statements shows that the larger has no more total hinge loss and no shorter . Here the street stops changing above C = 10. The still grow with , but their changes cancel out in and .
The labels make every condition one inequality: is positive exactly when the point is on its own side of the line.
-
Curved boundaries
Some classes no straight line can split. Add a new feature, and a flat cut in three dimensions becomes a curve back in two.
New made-up points: 40 in all, 20 circles within distance 1 of the middle and 20 triangles in a ring around them. No straight line splits a ring from its middle. The line the SVM finds, with C = 1, gets 30 of them right, 75.0%.
Press "Add x₁² + x₂²". Each point gets a third feature, x₁² + x₂², its squared distance from the middle. The circles all get values below 1, and the triangles values above 1.6² = 2.56.
The right panel is a side view, with the new feature as the height. We look along the flat plane the SVM finds in three dimensions, so the plane shows as a line: circles below it, triangles above it. All 40 points are on the right side, with a street 1.79 wide, measured in three dimensions.
Back on the flat picture of x₁ and x₂, that plane is a circle of radius 1.35, with its street between the two dashed circles. The method is still the straight-line SVM. Only the features changed.
The maths
With features the boundary is
Here = 1.11. Because and have the same weight, completing the square turns this into a circle, centred at . The street's edges, where the left side equals , are circles with the same centre.
The dual in step 4 uses the points only through dot products . Swap each one for , the dot product of the two points after a change of features, worked out straight from the original features. That is the kernel trick: the SVM learns with the new features without ever writing them down. A common choice is the radial basis function (RBF) kernel, which scores two points by how close they are. Its new features are infinitely many, so it is used through the kernel trick. This page writes its one new feature out in full and uses no kernel.
Quick check
Lesson complete
- An SVM picks the line w·x + b = 0 with the widest street around it. The street's width, the margin, is 2/‖w‖.
- Only the support vectors, the points on the edges, inside the street or on the wrong side, fix the line. The other points could move or vanish without changing it.
- When the classes overlap, a soft margin lets points into the street. Small C gives a wide street with many violations; large C a narrow one with few.
- A new feature such as x₁² + x₂² lets the same straight-line method draw a curved boundary. The kernel trick does this without writing the features down.
Common misconceptions
- "An SVM uses every training point to place the line." Every point is checked, but only the support vectors decide where the line goes.
- "A larger C is better, because it makes fewer mistakes on the training points." Fewer training mistakes can mean a street bent around odd points. Choose C on data the model has not seen.
- "The kernel is what makes it an SVM." The straight-line SVM is complete on its own. Kernels are a way to give it new features.
Further reading
- James, Witten, Hastie & Tibshirani, An Introduction to Statistical Learning (2nd ed.), Section 9.1, "Maximal Margin Classifier", and Section 9.2, "Support Vector Classifiers". One warning: there C is a budget for violations, so a larger C means a wider margin, the opposite of the C on this page.
- The same book, Section 9.3, "Support Vector Machines", for kernels, including the radial kernel.
About the data. All the points are made up, in your browser, by the mulberry32 random number generator. In steps 1 to 4, seed 71: feature 1 = m₁ + 0.8 z₁ and feature 2 = m₂ + 0.8 z₂, where z₁ and z₂ are independent draws from a normal distribution with mean 0 and SD 1. Class 0 has centre (m₁, m₂) = (−2, −1.5) and class 1 has centre (2, 1.5), with 12 points each, class 0 first. Step 5 uses the same recipe with seed 77 and 1.4 in place of 0.8. Step 6 uses seed 73: for each of 40 points in turn, a distance r is drawn uniformly, between 0 and 1 for the first 20 (class 0) and between 1.6 and 2.4 for the last 20 (class 1), then an angle θ uniformly between 0 and 2π, and the point is (r cos θ, r sin θ).
If this helped, you can .