Support vector machines: maximum margin, duality and the soft margin

The SVM lectures start by revisiting the perceptron from Part 15, whose properties lead to a more principled way of building a classifier. Perceptron's convergence proof bounded the number of mistakes it makes:

Two assumptions sit behind the bound. \(R\) is a radius: \(\lVert\mathbf{x}_i\rVert^2 \le R^2\) for every point, so all the data lies inside a ball of radius \(R\). \(\gamma\) is the margin: the data set is linearly separable with margin \(\gamma\), meaning

In pictures, the lines \(\{\mathbf{x} : \mathbf{w}^{*\top}\mathbf{x} = \gamma\}\) and \(\{\mathbf{x} : \mathbf{w}^{*\top}\mathbf{x} = -\gamma\}\) run parallel to the separator. Every positive point lies on or beyond the first, every negative point on or beyond the second. That gap of nonzero width is what the proof needs: Part 15 showed an example without it where perceptron may never converge. With the gap, perceptron makes finitely many mistakes and so converges. As in the proof, \(\mathbf{w}^*\) is taken to have unit length.

What does the bound say about the quality of the final solution? The lecture's example is a separable data set with positives on one side and negatives on the other, and two unit directions that both separate it.

• \(\mathbf{w}^*_1\) points diagonally. Its two margin lines lie far apart: a wide margin.
• \(\mathbf{w}^*_2\) is the x-axis direction, so its separating line is the y-axis. All positives are on one side of the y-axis and all negatives on the other, but the nearest points are close to it: a thin margin.

Given this data, \(\mathbf{w}^*_1\) feels like the better separator, because it separates the classes with a larger margin.

Observation 1: the bound uses the best margin L57 · 8:53

The proof assumed only that some \(\mathbf{w}^*\) separates the data with margin \(\gamma\); it said nothing else about \(\mathbf{w}^*\). So the bound holds for every separating unit vector with its own margin, and the tightest version comes from the largest margin. With the lecture's illustrative numbers, if one separator has \(\gamma = 1\) and another has \(\gamma = 10\), the mistake count is bounded by \(R^2/10^2\). The number of mistakes depends on the margin of the best possible \(\mathbf{w}^*\): the larger it is, the fewer mistakes.

Observation 2: perceptron need not find that separator L57 · 10:59

The vector \(\mathbf{w}_{\text{perc}}\) that perceptron outputs need not be the \(\mathbf{w}^*\) with the largest margin. Nothing in the update rule pushes toward a large margin. Perceptron only updates on mistakes, so the moment it reaches a vector like \(\mathbf{w}^*_2\) that classifies every training point correctly, it stops and reports convergence.

This is no contradiction 13:04. A large margin makes the problem easier because the two classes are well separated, so perceptron needs few mistakes to find some separator. An easy problem does not mean it finds the widest one.

We prefer separators with a large margin, and perceptron, for all its simplicity, does not have the power to find them. So the lecture lets go of perceptron and asks directly: given a linearly separable data set, can we find the \(\mathbf{w}^*\) that separates it with as large a margin as possible?

Why is a wide margin better? Loosely, because of generalization. Think of test data as a noisy version of the training data. Take a negative point near the thin-margin separator and add a little noise: it can cross that line and be predicted positive, while it is still on the correct side of the wide-margin separator. The margin is leeway that absorbs such perturbations, so the wider it is, the more robust the classifier.

Goal: a principled way to find the \(\mathbf{w}\) that classifies the data with the largest possible margin.

To make "largest margin" precise, treat both \(\mathbf{w}\) and \(\gamma\) as parameters. Make \(\gamma\) as large as possible, but allow only those \(\mathbf{w}\) that separate the data with margin \(\gamma\):

Every positive point is then on or beyond the line \(\mathbf{w}^\top\mathbf{x} = \gamma\) and every negative point on or beyond \(\mathbf{w}^\top\mathbf{x} = -\gamma\). But something is missing. Suppose the problem returned some \(\mathbf{w}\) with \(\gamma = 5\). Every \(\mathbf{x}\) with \(\mathbf{w}^\top\mathbf{x} = 5\) also satisfies \((2\mathbf{w})^\top\mathbf{x} = 10\), so \(\mathbf{w}' = 2\mathbf{w}\) separates the same data with margin 10. Keep scaling and \(\gamma\) grows to infinity. As stated, the problem has no useful answer.

One fix 5:07, as in the perceptron analysis: allow only unit-length \(\mathbf{w}\).

Now \(2\mathbf{w}\) is not allowed, since \(\lVert 2\mathbf{w}\rVert^2 = 4\). This is a reasonable formulation, and optimization techniques will solve it.

Do we need two variables? With \(\lVert\mathbf{w}\rVert = 1\), choosing \(\mathbf{w}\) only chooses a direction, and then the data decide \(\gamma\): slide the two parallel lines away from the separator until they hit the nearest points. In the lecture's sketch, one unit direction \(\mathbf{w}_1\) gives the margin line \(\mathbf{w}_1^\top\mathbf{x} = 5\), so \(\gamma = 5\), and another, \(\mathbf{w}_2\), gives \(\mathbf{w}_2^\top\mathbf{x} = 3\), so \(\gamma = 3\). Once \(\mathbf{w}\) is fixed, \(\gamma\) is a function of \(\mathbf{w}\).

The other way to stop the scaling is to drop \(\lVert\mathbf{w}\rVert = 1\) and pin \(\gamma\) instead, at \(\gamma = 1\). Any direction that separates the data can be rescaled so that its margin lines read exactly \(\pm1\) 10:16: the line \(\mathbf{w}_1^\top\mathbf{x} = 5\) is the same set of points as \((\mathbf{w}_1/5)^\top\mathbf{x} = 1\). So use \(\mathbf{w}_1' = \mathbf{w}_1/5\) and \(\mathbf{w}_2' = \mathbf{w}_2/3\). The lines are the same; only their equations, and the lengths of the vectors, change.

With \(\gamma\) fixed it can no longer be the thing we maximize. What still changes from one \(\mathbf{w}\) to another is the width between the lines \(\mathbf{w}^\top\mathbf{x} = 1\) and \(\mathbf{w}^\top\mathbf{x} = -1\), so the equivalent formulation is 13:56

\(\gamma\) has disappeared, and the length of \(\mathbf{w}\) is unrestricted: any \(\mathbf{w}\) that separates the data with margin 1 is allowed. It remains to find the width as a function of \(\mathbf{w}\).

The width is the distance between two parallel lines. Take any \(\mathbf{x}\) on the line \(\mathbf{w}^\top\mathbf{x} = -1\) and find the closest point \(\mathbf{z}\) on \(\mathbf{w}^\top\mathbf{z} = 1\); their distance is the width, whichever \(\mathbf{x}\) we start from. As an optimization problem:

Minimizing the distance, its square or half its square gives the same \(\mathbf{z}\). The lecture states the answer without solving the problem (it suggests Lagrange multipliers). A quick way to see it, added here: the closest point is reached by moving from \(\mathbf{x}\) along \(\mathbf{w}\), so \(\mathbf{z} = \mathbf{x} + t\,\mathbf{w}\). Then \(\mathbf{w}^\top\mathbf{z} = -1 + t\lVert\mathbf{w}\rVert^2 = 1\) gives \(t = 2/\lVert\mathbf{w}\rVert^2\), and

The lecture's "width of \(\mathbf{w}\)" is the value of this problem, half the squared distance, \(2/\lVert\mathbf{w}\rVert^2\). The distance itself is \(2/\lVert\mathbf{w}\rVert\). Either way it shrinks as \(\lVert\mathbf{w}\rVert\) grows. As a sanity check, the answer depends only on \(\mathbf{w}\) and not on the starting point \(\mathbf{x}\), as it must for the distance between two parallel lines.

Put the width into the formulation: maximize \(2/\lVert\mathbf{w}\rVert^2\) subject to \((\mathbf{w}^\top\mathbf{x}_i)y_i \ge 1\). Maximizing \(2/\lVert\mathbf{w}\rVert^2\) is the same as minimizing \(\lVert\mathbf{w}\rVert^2\), which the lecture writes with a convenient \(\tfrac12\).

Why does a short \(\mathbf{w}\) mean a wide margin? 20:35 The margin is pinned at 1 on both sides. If the margin is narrow, the points on the line \(\mathbf{w}^\top\mathbf{x} = 1\) in any fixed direction are close to the origin, so they are short. For a short \(\mathbf{x}\) to give \(\mathbf{w}^\top\mathbf{x} = 1\), \(\mathbf{w}\) must be long. A narrow margin forces a long \(\mathbf{w}\); a wide one allows a short \(\mathbf{w}\).

If the data are not linearly separable, no \(\mathbf{w}\) satisfies the constraints and the problem simply has no feasible solution. If they are, its solution is the separator with the largest width. It can be solved by gradient-based methods such as projected gradient descent (gradient descent itself is in Part 10). The lecture is after insight instead 26:48, and the standard route to insight about an optimization problem is its dual problem: another way of looking at the same problem, which here will also show how to go beyond linear separators.

Call the hard-margin problem problem A. To find its dual, the lecture takes a detour through a general problem with a single constraint:

Problem A has this shape once its constraints, which read "\(\ge 1\)", are rewritten as "\(\le 0\)". It has \(n\) constraints, one per point; the many-constraint version comes at the end of the lecture. Define the Lagrangian, a function of \(\mathbf{w}\) and a new real variable \(\alpha\):

The objective stays intact and the constraint becomes part of it. How is this related to the original problem? Fix any \(\mathbf{w}\) and look at \(\max_{\alpha \ge 0} L(\mathbf{w}, \alpha)\). There are two cases.

Case 1: \(g(\mathbf{w}) > 0\) L59 · 4:36

The lecture's example: \(f(\mathbf{w}) = -100\) and \(g(\mathbf{w}) = 5\), so we maximize \(-100 + 5\alpha\) over \(\alpha \ge 0\). \(\alpha = 1\) gives \(-95\), \(\alpha = 10\) gives \(-50\), \(\alpha = 100\) gives \(400\). \(f(\mathbf{w})\) is a fixed number, however small, while \(\alpha\) can grow without limit, so the maximum is \(+\infty\).

Case 2: \(g(\mathbf{w}) \le 0\) L59 · 7:11

Example: \(\mathbf{w} = (3, 4, 5, 6)\) with \(f(\mathbf{w}) = 100\) and \(g(\mathbf{w}) = -5\), so we maximize \(100 - 5\alpha\). Every positive \(\alpha\) lowers the value and negative \(\alpha\) is not allowed, so the best choice is \(\alpha = 0\), with value \(100 = f(\mathbf{w})\). If \(g(\mathbf{w}) = 0\) exactly, the second term vanishes for every \(\alpha\) and the value is again \(f(\mathbf{w})\).

As a function of \(\mathbf{w}\), this equals \(f\) on the feasible region and \(+\infty\) outside it. Minimizing it over \(\mathbf{w}\) can never pick an infeasible point, and inside the region it is just \(f\). So the constrained problem equals an unconstrained min–max, which the lecture calls B:

Once we have a min–max problem, we can ask whether the order can be swapped without changing the answer:

In general the answer is no. But if \(f\) and \(g\) are "nice", which here means convex, the swap is allowed 14:52. This is a fundamental result of convex optimization, which the lecture calls convex duality; it is not proved in the course, and a convex optimization book or course covers it. For the SVM, only quadratic and linear functions appear, and both are convex. (Convex functions were introduced in Part 9.)

Several constraints \(g_1(\mathbf{w}) \le 0, \dots, g_k(\mathbf{w}) \le 0\) work the same way, with one multiplier per constraint, each restricted to be non-negative.

At first glance nothing is gained 19:27: a constrained minimization became a min–max and then a max–min, neither obviously easier. The next lecture shows what the swap buys for the SVM.

Problem A is convex: \(\tfrac12\lVert\mathbf{w}\rVert^2\) is quadratic in \(\mathbf{w}\) and each constraint is linear in \(\mathbf{w}\). So the min–max swap applies. In standard form the constraints are

Each data point gets its own multiplier, and the lecture collects them in one vector \(\boldsymbol\alpha = (\alpha_1, \dots, \alpha_n)\); \(\boldsymbol\alpha \ge 0\) means every \(\alpha_i \ge 0\).

The right-hand side helps for this reason. Fix any \(\boldsymbol\alpha \ge 0\). The inner minimization over \(\mathbf{w}\) then has no constraints at all, so we can take the gradient and set it to zero 5:42:

The subscript is a reminder that this is the best \(\mathbf{w}\) for the \(\boldsymbol\alpha\) we fixed. It has a simple form: a linear combination of the data points, point \(i\) weighted by \(\alpha_i y_i\) (a non-negative number times \(\pm1\)). In matrix notation 8:46:

\(X\) has the data points as columns and \(Y\) has the labels on its diagonal, so \(XY\) has columns \(y_i\mathbf{x}_i\), and multiplying by \(\boldsymbol\alpha\) weights column \(i\) by \(\alpha_i\). The sizes \((d\times n)(n\times n)(n\times 1)\) give a \(d\times 1\) vector, the shape of \(\mathbf{w}\).

Substitute \(\mathbf{w} = XY\boldsymbol\alpha\) back into the Lagrangian, and every \(\mathbf{w}\) disappears. The lecture skips the algebra; it is short. The constraint term is \(\sum_i \alpha_i - \sum_i \alpha_i y_i\,\mathbf{x}_i^\top\mathbf{w} = \boldsymbol\alpha^\top\mathbf{1} - (XY\boldsymbol\alpha)^\top\mathbf{w}\), so

Here \(\mathbf{1}\) is the \(n\)-dimensional vector of all ones. This is the value of the inner minimization for a given \(\boldsymbol\alpha\); the outer maximization then chooses \(\boldsymbol\alpha\).

If both problems give the same answer, why bother with the dual? The lecture lists three gains.

1. Dimension. The dual searches in \(n\) dimensions, the primal in \(d\). When \(d\) is much larger than \(n\), the dual is the smaller search, which helps algorithms (for example gradient-based ones) whose convergence depends on the dimension of the space. This only pays off when \(d \gg n\).
2. Simpler constraints 15:01. Both problems are still constrained. A projected gradient method takes a step and, if it leaves the feasible set, projects back onto it. Projecting onto the region cut out by \(n\) linear constraints is harder than projecting onto the non-negative quadrant \(\boldsymbol\alpha \ge 0\).
3. Kernels, the main benefit. The dual objective depends on the data only through \(X^\top X \in \mathbb{R}^{n\times n}\), the matrix of dot products between every pair of points. Anything written in terms of dot products can be kernelized (Part 5, and kernel regression in Part 11): replace \(X^\top X\) by a kernel matrix \(K\), whose entries \(K_{ij} = k(\mathbf{x}_i, \mathbf{x}_j)\) are dot products in some high-dimensional feature space. The same problem then finds separators that are quadratic, cubic or given by a Gaussian (radial basis function) kernel. The primal gave no hint of this: it looks for a line with margin 1, and it is unclear how to use it for quadratically separable data.

The first two advantages are side benefits. The reason to look at the dual is that it reveals the problem can be kernelized.

For the optimal \(\boldsymbol\alpha^*\), the optimal \(\mathbf{w}^*\) is a linear combination of the data points:

The multiplier \(\alpha_i^*\) is the importance of point \(i\). If \(\alpha_i^* = 0\), the point contributes nothing to \(\mathbf{w}^*\); if \(\alpha_i^* > 0\), it contributes something. The dual only guarantees \(\alpha_i^* \ge 0\), so some multipliers may be zero and others positive. Which points have \(\alpha_i^* > 0\)? Characterizing them tells us how many points actually shape \(\mathbf{w}^*\). Lecture 61 answers this.

Return to the general problem with one constraint, with \(f\) and \(g\) convex so that duality holds. Let \(\mathbf{w}^*\) solve the primal (the min over \(\mathbf{w}\) of the max over \(\alpha\)) and \(\alpha^*\) solve the dual (the max over \(\alpha\) of the min over \(\mathbf{w}\)). Evaluate each side at its solution.

• Primal side. \(\max_{\alpha\ge0} L(\mathbf{w}^*, \alpha) = f(\mathbf{w}^*)\), because \(\mathbf{w}^*\) is feasible, \(g(\mathbf{w}^*) \le 0\), and at a feasible point the max over \(\alpha\) returns \(f\).
• Dual side. \(\min_{\mathbf{w}} L(\mathbf{w}, \alpha^*) \le L(\mathbf{w}^*, \alpha^*) = f(\mathbf{w}^*) + \alpha^* g(\mathbf{w}^*)\), since a minimum over all \(\mathbf{w}\) is no larger than the value at the particular point \(\mathbf{w}^*\) 3:07.

Duality says the two optimal values are equal, so

Feasibility says the opposite. The optimal points are feasible points, so \(\alpha^* \ge 0\) (dual feasible) and \(g(\mathbf{w}^*) \le 0\) (primal feasible). A non-negative number times a non-positive one cannot be strictly positive: \(\alpha^* g(\mathbf{w}^*) \le 0\) (2). Both (1) and (2) can hold only if the product is zero.

For the SVM, \(g_i(\mathbf{w}^*) = 1 - (\mathbf{w}^{*\top}\mathbf{x}_i)\,y_i\), so complementary slackness reads

If point \(i\) contributes to \(\mathbf{w}^*\), that is \(\alpha_i^* > 0\), the bracket must vanish:

So \(\mathbf{x}_i\) lies exactly on the line \(\mathbf{w}^{*\top}\mathbf{x} = 1\) (if it is positive) or \(\mathbf{w}^{*\top}\mathbf{x} = -1\) (if negative). Read the other way: a point that is not on one of these two lines has \(\alpha_i^* = 0\) and does not contribute to \(\mathbf{w}^*\) at all. The implication runs one way only. A point on one of the lines may still have \(\alpha_i^* = 0\).

The two lines are the supporting hyperplanes, and the points on them, the only ones that can carry \(\alpha_i^* > 0\), are the support vectors. Because the algorithm relies on them, it is called the support vector machine (SVM); "machine" is just a fancy word. It was developed mainly by Vapnik and colleagues in the 1990s 14:36.

This is the big advantage: \(\mathbf{w}^*\) is a sparse linear combination of the data points 15:06. Out of a billion points, perhaps only hundreds lie on the supporting hyperplanes, and they are all that matters for \(\mathbf{w}^*\). The rest can be thrown away. The algorithm automatically compresses the data set into a small set of relevant points, an instance of the course's compression theme from Part 2.

To classify a test point, compute \(\mathbf{w}^{*\top}\mathbf{x}_{\text{test}}\); the side of the separator it falls on, its sign, gives the label. Substituting \(\mathbf{w}^*\):

Only dot products appear again, so in the kernel version, with feature map \(\phi\), the high-dimensional \(\mathbf{w}^*\) is never built explicitly:

The SVM is now a solid algorithm: it can be kernelized and its solution is sparse. One question is left: how to adapt it when the data have outliers. The algorithm assumes the data are linearly separable (or, with a kernel, separable in some high-dimensional space). In the lecture's example, pluses and minuses are separated by a line except for one plus sitting among the minuses and one minus among the pluses. No \(\mathbf{w}\) classifies every point correctly, so the SVM gives up: there is no feasible \(\mathbf{w}\).

Why not map the data to a high-dimensional space with a kernel, where it might become separable? Because kernels address structure. Their hypothesis is that the true separator is nonlinear (quadratic, cubic and so on) in the original space but linear in a higher one. Here the structure is still linear, and a few noisy points cause the trouble. Outliers are a problem of noise, and a tool built for structure may not give the best accuracy on them.

The fix is a small modification of the formulation with profound consequences: the soft-margin support vector machine, one of its most powerful variants.

The hard-margin problem only admits a \(\mathbf{w}\) with \((\mathbf{w}^\top\mathbf{x}_i)y_i \ge 1\) for every point. With outliers no such \(\mathbf{w}\) exists. The insight of the soft margin is to make every \(\mathbf{w}\) feasible.

Fix any \(\mathbf{w}\). It classifies some points correctly and others not. Instead of rejecting it, let each offending point pay a bribe \(\xi_i\) to be counted on the correct side (the lecture writes the bribe as \(\epsilon_i\) or \(\xi_i\)):

A point that already meets its margin pays nothing. Any other point has \((\mathbf{w}^\top\mathbf{x}_i)y_i < 1\) and needs an extra push to reach 1; that push is its bribe. Bribes are never negative.

A first attempt fails L62 · 5:43

Every \(\mathbf{w}\) is now feasible, including the all-zeros vector: then \((\mathbf{w}^\top\mathbf{x}_i)y_i = 0\) and each point pays \(\xi_i = 1\). The length cannot go below 0, so this problem always returns \(\mathbf{w} = \mathbf{0}\). Something is badly wrong.

Bribes must cost something L62 · 7:17

Allowing bribes is fine; letting them be free is the flaw. Points should pay as little as possible, and the only place to penalize bribes is the objective, where the goodness of a \(\mathbf{w}\) is judged. So add the total bribe to it. Then \(\mathbf{w} = \mathbf{0}\) pays a total of \(n\), which is probably too much for it to be optimal.

The two terms have incompatible units, a squared length and an amount of bribe, so a balancing factor \(C \ge 0\) weighs them 9:20. How large \(C\) should be depends on the data, for instance on how many outliers there are, so \(C\) is a hyperparameter chosen by cross-validation (Part 11).

\(C\) is the price of one unit of bribe. The two extremes show its role.

• \(C = 0\). Bribes cost nothing, and we are back to the failed first attempt: only the length is minimized, and \(\mathbf{w} = \mathbf{0}\) is feasible, so it is the solution.
• \(C = \infty\) 11:21. Each unit of bribe costs infinitely more than length, so only a \(\mathbf{w}\) that pays no bribe at all has a finite objective. That is a \(\mathbf{w}\) that classifies every point correctly with margin 1: the hard-margin, linearly separable case. If the data are not separable, every \(\mathbf{w}\) costs \(\infty\) and all are equally bad, which is useless.

In between, \(C\) interpolates between how much we care about the margin (through the length of \(\mathbf{w}\)) and how much we care about handling outliers. Since we don't know in advance how many outliers the data has, cross-validation picks \(C\).

One question remains. The hard-margin problem became powerful through its dual: kernelizable, with simple constraints. The soft-margin primal has the extra variables \(\xi_i\), and it is not obvious what its dual looks like. If the dual lost those advantages, this would be a poor formulation. The only way to find out is to derive it.

Why does kernelizing still matter? Data can have a nonlinear structure and outliers. The lecture's example is 2-D data where a quadratic curve separates the classes, except for a few negatives on the positive side and a few positives on the negative side. We want slack for the outliers and a kernel for the curve.

The primal variables are now \(\mathbf{w}\) and \(\boldsymbol\xi\). Each point has two constraints and therefore two multipliers: \(\alpha_i\) for \((\mathbf{w}^\top\mathbf{x}_i)y_i + \xi_i \ge 1\) and \(\beta_i\) for \(\xi_i \ge 0\). In standard form these are \(1 - (\mathbf{w}^\top\mathbf{x}_i)y_i - \xi_i \le 0\) and \(-\xi_i \le 0\), so

The objective and all constraints are convex, so the min–max equals the max–min (the lecture names this strong duality):

As before, fix \(\boldsymbol\alpha\) and \(\boldsymbol\beta\); the inner minimization is unconstrained, so set the gradients with respect to \(\mathbf{w}\) and each \(\xi_i\) to zero:

The equation for \(\mathbf{w}^*\) is exactly the hard-margin one. The new condition \(\alpha_i + \beta_i = C\) has to hold for whatever \(\boldsymbol\alpha, \boldsymbol\beta\) the dual ends up with.

Substitute \(\mathbf{w} = XY\boldsymbol\alpha\) back. The lecture notes that a lot cancels; in detail, the \(\xi\) terms are \(C\sum_i\xi_i - \sum_i\alpha_i\xi_i - \sum_i\beta_i\xi_i = \sum_i (C - \alpha_i - \beta_i)\,\xi_i = 0\). What remains is the hard-margin expression:

Here \(\boldsymbol\alpha + \boldsymbol\beta = C\mathbf{1}\) means \(\alpha_i + \beta_i = C\) for every \(i\). \(\boldsymbol\beta\) does not appear in the objective; it only restricts \(\boldsymbol\alpha\). Since \(\beta_i = C - \alpha_i\) must be non-negative, the restriction is \(\alpha_i \le C\), and \(\boldsymbol\beta\) can be dropped.

Sanity checks on \(C\) L63 · 14:35

• \(C = 0\). \(0 \le \alpha_i \le 0\) leaves only \(\boldsymbol\alpha = \mathbf{0}\), the single feasible and hence optimal point. Then \(\mathbf{w}^* = \sum_i 0\cdot y_i\mathbf{x}_i = \mathbf{0}\), as the primal argument predicted: free bribes give \(\mathbf{w} = \mathbf{0}\).
• \(C = \infty\). There is no upper bound, so this is exactly the hard-margin dual, matching the primal argument that infinitely expensive bribes bring back the hard-margin case.

The data still enter only through \(X^\top X\), so the soft-margin SVM can still be kernelized. The constraints \(0 \le \alpha_i \le C\) are called box constraints: \(\boldsymbol\alpha\) must lie in a hypercube of side \(C\), a square in two dimensions. Projecting onto a box is easy 18:15. If a gradient method pushes some \(\alpha_i\) above \(C\), clip it to \(C\); if below 0, clip it to 0.

So the soft margin keeps both advantages of the hard-margin dual and also handles outliers, which makes it a very powerful algorithm. One property is still unchecked: sparsity. In the hard-margin case, complementary slackness showed that only points on the supporting hyperplanes contribute to \(\mathbf{w}^*\), so for kernel predictions we kept only those. With bribes allowed, could \(\mathbf{w}^*\) suddenly depend on every point, forcing us to keep the whole data set? Complementary slackness for the soft margin answers this.

Complementary slackness links the primal and dual optimal solutions. Let \(\mathbf{w}^*, \boldsymbol\xi^*\) solve the primal and \(\boldsymbol\alpha^*, \boldsymbol\beta^*\) solve the dual. Keeping \(\boldsymbol\beta^*\) in the analysis makes the cases easier. Each term added to the Lagrangian for a constraint is zero at the optimum:

In the hard-margin case there were two cases, \(\alpha_i^* = 0\) or \(\alpha_i^* > 0\). Now \(\alpha_i^*\) lies between 0 and \(C\), and the value \(C\) turns out to be special, so there are three 3:33. The lecture assumes \(C\) is strictly positive.

Suppose we solved the dual and look at one point's \(\alpha_i^*\). What can we infer about where the point is?

Case 1: \(\alpha_i^* = 0\)

Then \(\beta_i^* = C > 0\), so CS2 forces \(\xi_i^* = 0\). Primal feasibility becomes \((\mathbf{w}^{*\top}\mathbf{x}_i)\,y_i \ge 1\). The point is correctly classified, either on its supporting hyperplane or beyond it; nothing more can be said. It does not contribute to \(\mathbf{w}^*\): it is a well-classified point that the solution does not need.

Case 2: \(0 < \alpha_i^* < C\)

Then \(\beta_i^* = C - \alpha_i^*\) is also strictly between 0 and \(C\). CS2 with \(\beta_i^* \ne 0\) gives \(\xi_i^* = 0\). CS1 with \(\alpha_i^* \ne 0\) gives \(1 - (\mathbf{w}^{*\top}\mathbf{x}_i)y_i - \xi_i^* = 0\). Together:

The point lies exactly on a supporting hyperplane. Its \(\alpha_i^*\) is positive, so it contributes to \(\mathbf{w}^*\): it is a support vector.

Case 3: \(\alpha_i^* = C\)

Then \(\beta_i^* = 0\), and CS2 says nothing about \(\xi_i^*\) beyond the constraint \(\xi_i^* \ge 0\). But \(\alpha_i^* = C > 0\), so CS1 gives

Where are such points 14:57? For a positive point, \(\mathbf{w}^{*\top}\mathbf{x}_i \le 1\): on its supporting hyperplane or anywhere on the near side of it. Predictions use the separator \(\mathbf{w}^{*\top}\mathbf{x} = 0\), so a point strictly inside this region is in one of two situations:

• \((\mathbf{w}^{*\top}\mathbf{x}_i)\,y_i < 0\): the point is on the wrong side of the separator and is misclassified;
• \(0 < (\mathbf{w}^{*\top}\mathbf{x}_i)\,y_i < 1\): the point is on the correct side but closer to the separator than its supporting hyperplane, so it is correctly classified without enough margin. The lecture calls this strip the danger zone, where we are not confident about the classification.

These are the outliers of the data set, together with the points too close to the separator. The solution is robust to them in the sense that it accepts misclassifying an outlier. Yet they get the largest possible weight, \(\alpha_i^* = C\), so they influence \(\mathbf{w}^*\) the most 19:07.

In the soft margin, every point with \(\alpha_i^* > 0\) is a support vector. It lies on a supporting hyperplane (\(0 < \alpha_i^* < C\)), or inside the margin, or on the wrong side of the separator (\(\alpha_i^* = C\)). In the hard margin only the first kind exists.

Lecture 64 started from \(\alpha_i^*\), the dual solution, and asked where the point is. Now start from the primal solution \(\mathbf{w}^*\), look at a point's margin \((\mathbf{w}^{*\top}\mathbf{x}_i)y_i\), and ask what \(\alpha_i^*\) must be.

Margin strictly less than 1: inside the margin or misclassified

Feasibility gives \(\xi_i^* \ge 1 - (\mathbf{w}^{*\top}\mathbf{x}_i)y_i > 0\). With \(\xi_i^* > 0\), CS2 forces \(\beta_i^* = 0\), so \(\alpha_i^* = C\). Such a point is strictly off its supporting hyperplane on the wrong side, and it is among the most important points.

Margin exactly 1: on a supporting hyperplane

Feasibility only gives \(\xi_i^* \ge 0\). Then \(\beta_i^*\) can be anything in \([0, C]\), and so can \(\alpha_i^*\), including 0 and \(C\). Nothing more follows. Lecture 64's case 2 is not an "if and only if": \(0 < \alpha_i^* < C\) puts a point on the hyperplane, but a point on the hyperplane can have any \(\alpha_i^*\) in \([0, C]\).

Margin strictly greater than 1: well clear of the hyperplane

Then \(1 - (\mathbf{w}^{*\top}\mathbf{x}_i)y_i < 0\), and subtracting \(\xi_i^* \ge 0\) keeps it negative: \(1 - (\mathbf{w}^{*\top}\mathbf{x}_i)y_i - \xi_i^* < 0\). CS1 then forces \(\alpha_i^* = 0\). Points classified with margin greater than 1 do not contribute to \(\mathbf{w}^*\).

"Margin" here is \((\mathbf{w}^{*\top}\mathbf{x}_i)\,y_i\). The two halves of the table are not mirror images, because of the points that sit exactly on a supporting hyperplane.

The lecture walks through a picture. Points well beyond their supporting hyperplane, on the correct side, have \(\alpha^* = 0\). Points on the wrong side of their supporting hyperplane, whether misclassified or correctly classified without enough margin, all get \(\alpha^* = C\); being correctly classified does not help if the margin is too small. Points exactly on a supporting hyperplane can have any value: one might have 0, another 1, another \(C\) (with \(C > 1\)). On one side of the line you get exactly 0, on the other exactly \(C\), and on the line anything in between. The widget below solves a small soft-margin problem so you can see the three groups move as \(C\) changes.

Is the soft-margin solution still sparse? The points with \(\alpha^* = 0\) drop out, and only points on a supporting hyperplane or on its wrong side can contribute. If the data are linearly separable apart from some outliers, in the feature space of whatever kernel is used, those points should still be few compared with the whole data set. So the soft margin loses nothing on sparsity.

The lecture's summary of the soft-margin SVM, seen through its dual:

1. Kernelizable. The data appear only through dot products.
2. Simple constraints. Box constraints \(0 \le \alpha_i \le C\) are easy to handle, even in a projected gradient method.
3. Sparse. Only a handful of points have \(\alpha_i^* \ne 0\) compared with the total.

These properties are not only theoretically elegant: the algorithm performs very well in practice and has been applied successfully in many applications, especially on structured data, where features come in a structured (tabular) format 14:56. Training is a quadratic optimization problem, and a lot of work has gone into fast solvers; the lecture mentions that the fastest ones run in time linear in the size of the problem. Those techniques are not covered in this course.

The lecture closes with a comparison to logistic regression (Part 15). It can also deal with outliers and has a kernel version. Both are well-motivated algorithms that differ subtly in what they optimize (Part 18 compares their loss functions), and in practice they are usually competitive. A sensible approach is to try both and choose by performance on a validation set.

Next, in Part 17, the course takes a broader, meta view of classification after naive Bayes, decision trees, nearest neighbours, logistic regression, perceptron and SVMs: ensemble classifiers, leading to bagging and boosting.

Margin \(\gamma\)

For a unit \(\mathbf{w}\), the smallest \((\mathbf{w}^\top\mathbf{x}_i)y_i\) over the data: how far the nearest point is from the separator.

Radius-margin bound

Perceptron makes at most \(R^2/\gamma^2\) mistakes on data within radius \(R\) that is separable with margin \(\gamma\).

Supporting hyperplanes

The lines \(\mathbf{w}^\top\mathbf{x} = 1\) and \(\mathbf{w}^\top\mathbf{x} = -1\) once the margin is fixed at 1; they are \(2/\lVert\mathbf{w}\rVert\) apart.

Hard-margin SVM

\(\min \tfrac12\lVert\mathbf{w}\rVert^2\) such that \((\mathbf{w}^\top\mathbf{x}_i)y_i \ge 1\) for all \(i\): the maximum-margin separator. Needs linearly separable data.

Lagrangian

\(f(\mathbf{w}) + \sum_j \alpha_j g_j(\mathbf{w})\) with one multiplier \(\alpha_j \ge 0\) per constraint; maximizing over \(\boldsymbol\alpha\) enforces the constraints.

Primal and dual

\(\min_{\mathbf{w}}\max_{\boldsymbol\alpha\ge0} L\) and \(\max_{\boldsymbol\alpha\ge0}\min_{\mathbf{w}} L\). For convex problems they are equal (convex, or strong, duality).

Dot-product matrix \(X^\top X\)

The \(n\times n\) matrix of all \(\mathbf{x}_i^\top\mathbf{x}_j\); the only way the data enter the dual, so it can be replaced by a kernel matrix.

Complementary slackness

\(\alpha_i^* g_i(\mathbf{w}^*) = 0\) at the optimum: a multiplier can be positive only if its constraint holds with equality.

Support vectors

Points with \(\alpha_i^* > 0\). In the hard margin they lie on the supporting hyperplanes; \(\mathbf{w}^*\) and predictions depend only on them.

Soft-margin SVM

\(\min \tfrac12\lVert\mathbf{w}\rVert^2 + C\sum_i\xi_i\) such that \((\mathbf{w}^\top\mathbf{x}_i)y_i + \xi_i \ge 1\), \(\xi_i \ge 0\); handles outliers.

Slack variable \(\xi_i\)

The lecture's "bribe": how much point \(i\) falls short of margin 1, paid so that every \(\mathbf{w}\) is feasible.

Hyperparameter \(C\)

The price of one unit of slack. \(C = 0\) gives \(\mathbf{w} = \mathbf{0}\); \(C = \infty\) gives the hard margin. Chosen by cross-validation.

Box constraints

\(0 \le \alpha_i \le C\) in the soft-margin dual; projecting onto them is clipping each \(\alpha_i\).

Danger zone

The lecture's name for the region between a class's supporting hyperplane and the separator; points there, and misclassified points, get \(\alpha^* = C\).