The hypothesis and the setup
This blog post has an interactive demo (mostly used toward the end of the post). The source for this demo is available in a Github repository.
Last time we saw how the inner product of two vectors gives rise to a decision rule: if is the normal to a line (or hyperplane) , the sign of the inner product tells you whether is on the same side of as .
Let’s translate this to the parlance of machine-learning. Let be a training data point, and is its label (green and red, in the images in this post). Suppose you want to find a hyperplane which separates all the points with -1 labels from those with +1 labels (assume for the moment that this is possible). For this and all examples in this post, we’ll use data in two dimensions, but the math will apply to any dimension.
Some data labeled red and green, which is separable by a hyperplane (line).
The hypothesis we’re proposing to separate these points is a hyperplane, i.e. a linear subspace that splits all of into two halves. The data that represents this hyperplane is a single vector , the normal to the hyperplane, so that the hyperplane is defined by the solutions to the equation .
As we saw last time, encodes the following rule for deciding if a new point has a positive or negative label.
You’ll notice that this formula only works for the normals of hyperplanes that pass through the origin, and generally we want to work with data that can be shifted elsewhere. We can resolve this by either adding a fixed term —often called a bias because statisticians came up with it—so that the shifted hyperplane is the set of solutions to . The shifted decision rule is:
Now the hypothesis is the pair of vector-and-scalar . A trickier but perhaps cleaner way to do the same thing is to make the normal , i.e., add one dimension, and then augment all your data with a new dimension whose coordinate is always 1. This makes the normal inner product output the same formula above. We’ll do this, and call the new coordinate , so that the original data is .
Now, the key intuitive idea behind the formulation of the SVM problem is that there are many possible separating hyperplanes for a given set of labeled training data. For example, here is a gif showing infinitely many choices.
The question is: how can we find the separating hyperplane that not only separates the training data, but generalizes as well as possible to new data? The assumption of the SVM is that a hyperplane which separates the points, but is also as far away from any training point as possible, will generalize best.
More specifically, fix a labeled dataset of points , or more precisely:
And a hypothesis defined by the normal . Let’s also suppose that defines a hyperplane that correctly separates all the training data into the two labeled classes, and we just want to measure its quality. That measure of quality is the length of its margin.
Definition: The geometric margin of a hyperplane with respect to a dataset is the shortest distance from a training point to the hyperplane defined by .
The best hyperplane has the largest possible margin.
This margin can even be computed quite easily using our work from last post. The distance from to the hyperplane defined by is the same as the length of the projection of onto . And this is just computed by an inner product.
A naive optimization objective
If we wanted to, we could stop now and define an optimization problem that would be very hard to solve. It would look like this:
The reasons this is hard boil down to this formulation being horrifyingly nonlinear. In more detail:
- The constraints are nonlinear due to the sign comparisons.
- There’s a min and a max! A priori, we have to do this because we don’t know which point is going to be the closest to the hyperplane.
- The objective is nonlinear in two ways: the absolute value and the projection requires you to take a norm and divide.
The rest of this post (and indeed, a lot of the work in grokking SVMs) is dedicated to converting this optimization problem to one in which the constraints are all linear inequalities and the objective is a single, quadratic polynomial we want to minimize or maximize.
Along the way, we’ll notice some neat features of the SVM.
Trick 1: linearizing the constraints
To solve the first problem, we can use a trick. We want to know whether for a labeled training point . The trick is to multiply them together. If their signs agree, then their product will be positive, otherwise it will be negative.
So each constraint becomes:
This is still linear because is a constant (input) to the optimization problem. The variables are the coefficients of .
The left hand side of this inequality is often called the functional margin of a training point, since, as we will see, it still works to classify , even if is scaled so that it is no longer a unit vector. Indeed, the sign of the inner product is independent of how is scaled.
Trick 1.5: the optimal solution is midway between classes
This small trick is to notice that if is the supposed optimal separating hyperplane, i.e. its margin is maximized, then it must necessarily be exactly halfway in between the closest points in the positive and negative classes.
In other words, if and are the closest points in the positive and negative classes, respectively, then . If this were not the case, then you could adjust the bias entry of until it they are exactly equal, and you will have increased the margin. The closest point, say will have gotten farther away, and the closest point in the opposite class, will have gotten closer, but will not be closer than .
Trick 2: getting rid of the max + min
Resolving this problem essentially uses the fact that the hypothesis, which comes in the form of the normal vector , has a degree of freedom in its length.
Indeed, in the animation below, I can increase or decrease the length of without changing the decision boundary.
Let’s combine this with tricks 1 and 1.5. If we increase the length of , that means the absolute values of the dot products used in the constraints will all increase by the same amount (without changing their sign). Indeed, for any vector we have .
In this world, the inner product measurement of distance from a point to the hyperplane is no longer faithful. The true distance is , but the distance measured by is measured in units of .
In this example, the two numbers next to the green dot represent the true distance of the point from the hyperplane, and the dot product of the point with the normal (respectively). The dashed lines are the solutions to <x, w> = 1. The magnitude of w is 2.2, the inverse of that is 0.46, and indeed 2.2 = 4.8 * 0.46 (we’ve rounded the numbers).
Now suppose we had the optimal hyperplane and its normal . No matter how near (or far) the nearest positively labeled training point is, we could scale the length of to force . This is the core of the trick. One consequence is that the actual distance from to the hyperplane is .
The same as above, but with the roles reversed. We’re forcing the inner product of the point with w to be 1. The true distance is unchanged.
In particular, if we force the closest point to have inner product 1, then all other points will have inner product at least 1. This has two consequences. First, our constraints change to instead of . Second, we no longer need to ask which point is closest to the candidate hyperplane! Because after all, we never cared which point it was, just how far away that closest point was. And now we know that it’s exactly away. Indeed, if the optimal points weren’t at that distance, then that means the closest point doesn’t exactly meet the constraint, i.e. that for every training point . We could then scale shorter until , hence increasing the margin .
In other words, the coup de grâce, provided all the constraints are satisfied, the optimization objective is just to maximize , a.k.a. to minimize .
This intuition is clear from the following demonstration, which you can try for yourself. In it I have a bunch of positively and negatively labeled points, and the line in the center is the candidate hyperplane with normal that you can drag around. Each training point has two numbers next to it. The first is the true distance from that point to the candidate hyperplane; the second is the inner product with . The two blue dashed lines are the solutions to . To solve the SVM by hand, you have to ensure the second number is at least 1 for all green points, at most -1 for all red points, and then you have to make as short as possible. As we’ve discussed, shrinking moves the blue lines farther away from the separator, but in order to satisfy the constraints the blue lines can’t go further than any training point. Indeed, the optimum will have those blue lines touching a training point on each side.
I bet you enjoyed watching me struggle to solve it. And while it’s probably not the optimal solution, the idea should be clear.
The final note is that, since we are now minimizing , a formula which includes a square root, we may as well minimize its square . We will also multiply the objective by , because when we eventually analyze this problem we will take a derivative, and the square in the exponent and the will cancel.
The final form of the problem
Our optimization problem is now the following:
This is much simpler to analyze. The constraints are all linear equalities (which, because of linear programming, we know are tractable to optimize). The objective to minimize, however, is a convex quadratic function of the input variables—a sum of squares of the inputs.
Such problems are generally called quadratic programming problems (or QPs, for short). There are general methods to find solutions! However, they often suffer from numerical stability issues and have less-than-satisfactory runtime. Luckily, the form in which we’ve expressed the support vector machine problem is specific enough that we can analyze it directly, and find a way to solve it without appealing to general-purpose numerical solvers.
We will tackle this problem in a future post (planned for two posts sequel to this one). Before we close, let’s just make a few more observations about the solution to the optimization problem.
In Trick 1.5 we saw that the optimal separating hyperplane has to be exactly halfway between the two closest points of opposite classes. Moreover, we noticed that, provided we’ve scaled properly, these closest points (there may be multiple for positive and negative labels) have to be exactly “distance” 1 away from the separating hyperplane.
Another way to phrase this without putting “distance” in scare quotes is to say that, if is the normal vector of the optimal separating hyperplane, the closest points lie on the two lines .
Now that we have some intuition for the formulation of this problem, it isn’t a stretch to realize the following. While a dataset may include many points from either class on these two lines , the optimal hyperplane itself does not depend on any of the other points except these closest points.
This fact is enough to give these closest points a special name: the support vectors.
We’ll actually prove that support vectors “are all you need” with full rigor and detail next time, when we cast the optimization problem in this post into the “dual” setting. To avoid vague names, the formulation described in this post called the “primal” problem. The dual problem is derived from the primal problem, with special variables and constraints chosen based on the primal variables and constraints. Next time we’ll describe in brief detail what the dual does and why it’s important, but we won’t have nearly enough time to give a full understanding of duality in optimization (such a treatment would fill a book).
When we compute the dual of the SVM problem, we will see explicitly that the hyperplane can be written as a linear combination of the support vectors. As such, once you’ve found the optimal hyperplane, you can compress the training set into just the support vectors, and reproducing the same optimal solution becomes much, much faster. You can also use the support vectors to augment the SVM to incorporate streaming data (throw out all non-support vectors after every retraining).
Eventually, when we get to implementing the SVM from scratch, we’ll see all this in action.