Support Vector Machines and Soft Margins, machine learning lesson

Two lines can both classify every training point correctly while one passes far from the nearest point and the other almost touches it. A small change in that point, or a new point close to it, can flip the decision of the second line. A support vector machine chooses the boundary with the widest gap to the nearest points, and its soft-margin version lets some points sit inside the gap or on the wrong side at a price set by a parameter $C$ . This lesson separates the two kinds of margin, fits a small soft-margin model exactly and identifies the training points that determine it.

Key terms

Functional margin

Definition As in the previous lesson, labels are $y \in \{-1, +1\}$ , the score is $f(\mathbf{x}) = \mathbf{w}^{\top}\mathbf{x} + b$ , and the prediction is $+1$ when $f(\mathbf{x}) \ge 0$ and $-1$ otherwise. The functional margin of a labeled example $(\mathbf{x}_i, y_i)$ is

m_i = y_i\,(\mathbf{w}^{\top}\mathbf{x}_i + b) ,

and the functional margin of a training set is the smallest of these values, $\min_i m_i$ . A positive value means the example lies strictly on its correct side and a negative value means it lies on the wrong side. Multiplying $\mathbf{w}$ and $b$ by a constant $c > 0$ multiplies every functional margin by $c$ and leaves the boundary where it was.

In plain words The functional margin says whether a point is on its correct side and how large its score is there. Its size alone is not a distance, because rescaling the parameters changes it while the boundary stays put. A requirement such as a functional margin of at least $1$ gets a geometric meaning only together with the length of $\mathbf{w}$ .

Example Take the constructed inputs $-2$ , $-1$ , $1$ and $2$ on a number line, with labels $-1$ , $-1$ , $+1$ and $+1$ . With $w = 1$ and $b = 0$ the functional margins are $2$ , $1$ , $1$ and $2$ , so the training set has functional margin $1$ . With $w = 3$ and $b = 0$ the boundary is still the point $x = 0$ , yet the functional margins become $6$ , $3$ , $3$ and $6$ . A point $x = 0.5$ with label $-1$ would have functional margin $-0.5$ under the first parameters, because it lies on the wrong side.

Geometric margin

Definition For $\mathbf{w} \ne \mathbf{0}$ the geometric margin of example $i$ is

\begin{aligned} \rho_i &= \frac{y_i\,(\mathbf{w}^{\top}\mathbf{x}_i + b)}{\lVert \mathbf{w} \rVert_2} \\[0.4em] &= \frac{m_i}{\lVert \mathbf{w} \rVert_2} , \end{aligned}

the signed Euclidean distance from $\mathbf{x}_i$ to the boundary $\mathbf{w}^{\top}\mathbf{x} + b = 0$ , positive on the correct side. It does not change when $\mathbf{w}$ and $b$ are multiplied by the same $c > 0$ . The geometric margin of a training set is $\min_i \rho_i$ , which is the distance from the boundary to the nearest training point when every point is on its correct side. If the parameters are scaled so that the functional margin of the training set equals $1$ , the geometric margin equals $1/\lVert \mathbf{w} \rVert_2$ . The hyperplanes $f(\mathbf{x}) = 1$ and $f(\mathbf{x}) = -1$ , called the margin hyperplanes, then lie at that distance on either side of the boundary and enclose a slab of width $2/\lVert \mathbf{w} \rVert_2$ .

In plain words The geometric margin is a real distance in the units of the features. It says how far the nearest point could move before it reaches the boundary. Because it is a distance, it depends on how the features are measured, and rescaling one feature can change which boundary leaves the widest gap.

Example For $\mathbf{w} = (3, 4)$ , $b = -5$ and the point $(3, 1)$ with label $+1$ , the functional margin is $9 + 4 - 5 = 8$ and $\lVert \mathbf{w} \rVert_2 = 5$ , so the geometric margin is $8/5 = 1.6$ . The parameters $(6, 8)$ and $-10$ describe the same line and give functional margin $16$ but the same geometric margin $16/10 = 1.6$ . On the number line above, a threshold at $0.8$ separates the classes with geometric margin $0.2$ , set by the input $1$ , while a threshold at $0$ separates them with geometric margin $1$ , the largest possible.

Support vector machine

Definition A support vector machine (SVM) is a linear classifier whose weights and intercept are chosen to make the geometric margin of the training set large, either exactly, as in the hard-margin problem below, or in balance with margin violations, as in the soft-margin problem. For a linearly separable training set that contains both classes, the hard-margin SVM solves

\begin{gathered} \min_{\mathbf{w},\, b}\ \tfrac12 \lVert \mathbf{w} \rVert_2^2 \quad \text{subject to} \\[0.4em] y_i(\mathbf{w}^{\top}\mathbf{x}_i + b) \ge 1 \ \text{for all } i . \end{gathered}

The constraints fix the scale so that the functional margin is at least $1$ , and then the geometric margin is at least $1/\lVert \mathbf{w} \rVert_2$ , so minimizing $\lVert \mathbf{w} \rVert_2$ maximizes the geometric margin. The problem has a solution exactly when the set is linearly separable, the objective is convex, and the optimal $\mathbf{w}$ is unique. New points are classified by the sign rule of the score.

In plain words Among all separating hyperplanes, the SVM picks the one in the middle of the widest empty slab between the classes. Squaring the length of $\mathbf{w}$ and minimizing it, instead of maximizing a minimum distance directly, gives a convex problem that standard solvers handle well. A wide margin on the training data is a sensible preference, not a guarantee of lower error on new data. The SVM score is also not a probability, and turning it into one requires a separate calibration model fitted on held-out or cross-validated scores.

Example For the inputs $-2$ , $-1$ , $1$ and $2$ with labels $-1$ , $-1$ , $+1$ and $+1$ , the constraints of the two inner points are $w - b \ge 1$ and $w + b \ge 1$ . Adding them gives $w \ge 1$ whatever $b$ is, so the smallest possible $\lvert w \rvert$ is $1$ , and with $w = 1$ both constraints force $b = 0$ . The outer points then have functional margin $2$ , so all constraints hold. The hard-margin SVM is $f(x) = x$ with objective $\tfrac12$ , its margin hyperplanes are $x = -1$ and $x = 1$ , and its geometric margin is $1$ .

Hinge loss

Definition For a label $y \in \{-1, +1\}$ and a real score $f$ , the hinge loss is

\ell(y, f) = \max\bigl(0,\ 1 - y f\bigr) .

With $m = yf$ the functional margin, the loss is $0$ when $m \ge 1$ , strictly between $0$ and $1$ when $0 < m < 1$ , exactly $1$ when $m = 0$ and greater than $1$ when $m < 0$ . An example misclassified by the rule that predicts $+1$ when $f \ge 0$ has $m \le 0$ and therefore loss at least $1$ , so the hinge loss is an upper bound on the zero-one loss of that rule. For a linear score it is a convex function of $(\mathbf{w}, b)$ , being the larger of two affine functions, and it has a corner at $m = 1$ where it is not differentiable.

In plain words The hinge charges nothing for a point that is on its correct side by at least the unit margin, and it charges linearly for anything less, including correctly classified points that sit too close to the boundary. Unlike the log loss of logistic regression, it is exactly zero beyond the margin, so points far on their correct side have no effect on the fit.

Example Functional margins of $2$ , $1$ , $0.5$ , $0$ and $-1$ give hinge losses of $0$ , $0$ , $0.5$ , $1$ and $2$ . A point with label $+1$ and score exactly $0$ is classified correctly by the sign rule and still costs $1$ , the same as a point with label $-1$ and score $0$ , which is misclassified.

Soft margin

Definition For a penalty parameter $C > 0$ , the soft-margin SVM solves

\begin{gathered} \min_{\mathbf{w},\, b,\, \boldsymbol{\xi}}\ \tfrac12 \lVert \mathbf{w} \rVert_2^2 + C \sum_{i=1}^{n} \xi_i \\[0.4em] \text{subject to } \xi_i \ge 0 \text{ and} \\[0.4em] y_i(\mathbf{w}^{\top}\mathbf{x}_i + b) \ge 1 - \xi_i . \end{gathered}

The slack variable $\xi_i$ measures how far example $i$ falls short of the unit functional margin. At the optimum $\xi_i = \max(0, 1 - y_i f(\mathbf{x}_i))$ , so the problem is the same as minimizing over $\mathbf{w}$ and $b$

\tfrac12 \lVert \mathbf{w} \rVert_2^2 + C \sum_{i=1}^{n} \ell\bigl(y_i, f(\mathbf{x}_i)\bigr) ,

a convex problem in which the intercept is not penalized. It is always feasible, for example with $\mathbf{w} = \mathbf{0}$ , $b = 0$ and every $\xi_i = 1$ . The optimal $\mathbf{w}$ is unique, but the intercept need not be. Increasing $C$ never widens the slab $2/\lVert \mathbf{w} \rVert_2$ of the solution and never raises its total hinge loss, and on separable data a large enough $C$ gives exactly the hard-margin solution. Some texts and software write the objective as $\tfrac{\lambda}{2}\lVert \mathbf{w} \rVert_2^2$ plus the mean hinge loss, and that version has the same minimizers when $C = 1/(n\lambda)$ . A value of $C$ or $\lambda$ therefore means nothing without its convention and the sample size. Because margins are distances, features are usually standardized first, with the scaler fitted on the training data only, and inside each training fold when $C$ is chosen by cross-validation.

In plain words The parameter $C$ is the price of each unit of violation. A small $C$ accepts points inside the margin, or even on the wrong side, in exchange for a wide margin. A large $C$ narrows the margin to cut violations, which also lets a single mislabeled point pull hard on the boundary. Because violations are allowed, a soft-margin SVM still has a solution when the classes overlap, and it can leave training mistakes even when the classes are separable.

Example Fit the four inputs $-2$ , $-1$ , $1$ and $2$ again. The data are symmetric, since reflecting every input and label gives the same set. So if $(w, b)$ is optimal then so is $(w, -b)$ , and by convexity their average $(w, 0)$ is optimal too, which lets us set $b = 0$ . The functional margins are then $2w$ , $w$ , $w$ and $2w$ , and negative weights only raise every loss above its value at $w = 0$ . The total hinge loss is $4 - 6w$ for $0 \le w \le \tfrac12$ , then $2 - 2w$ for $\tfrac12 \le w \le 1$ , and $0$ for $w \ge 1$ . With $C = 0.1$ the derivative of the objective is $w - 0.6 < 0$ on the first piece and $w - 0.2 > 0$ on the second, so the minimum is at the corner $w = 0.5$ , where

\tfrac12\,(0.5)^2 + 0.1 \cdot 1 = 0.225 ,

less than the value $0.5$ of the hard-margin weight $w = 1$ . At $w = 0.5$ the total hinge loss is $1 + \lvert b \rvert$ for $\lvert b \rvert \le 0.5$ , so $b = 0$ is the only optimal intercept. The margin hyperplanes move out to $x = \pm 2$ , a slab of width $4$ . The inner points sit inside it with functional margin $0.5$ and hinge loss $0.5$ each, and all four points are still classified correctly. With $C = 1$ the derivative is negative on both pieces, so the minimum moves to $w = 1$ and the fit is the hard-margin SVM.

Support vector

Definition The soft-margin problem has a dual problem in variables $\alpha_1, \dots, \alpha_n$ with $0 \le \alpha_i \le C$ and $\sum_i \alpha_i y_i = 0$ , and at the optimum

\mathbf{w} = \sum_{i=1}^{n} \alpha_i\, y_i\, \mathbf{x}_i .

The training examples with $\alpha_i > 0$ are the support vectors. The optimality conditions tie each $\alpha_i$ to the functional margin $m_i$ . An example with $m_i > 1$ has $\alpha_i = 0$ , an example with $m_i < 1$ has $\alpha_i = C$ , and an example exactly on a margin hyperplane, with $m_i = 1$ , can have any $\alpha_i$ from $0$ to $C$ . Every support vector therefore lies on a margin hyperplane, inside the margin or on the wrong side, while an example on a margin hyperplane with $\alpha_i = 0$ is not a support vector. Deleting an example with $\alpha_i = 0$ and refitting leaves the same solution optimal. The hard-margin problem has the same description without the upper bound $C$ .

In plain words The support vectors are the training points that hold the boundary in place. A point outside the margin on its correct side can be moved or deleted without changing the fit, as long as it stays outside the margin. Influence is not trustworthiness, and a mislabeled point inside the margin is a support vector with the largest weight the problem allows.

Example In the hard-margin fit of the four inputs, and in the soft-margin fit with $C = 1$ , the dual weights for the inputs $-2$ , $-1$ , $1$ and $2$ are $0$ , $0.5$ , $0.5$ and $0$ . They satisfy $\sum_i \alpha_i y_i = -0.5 + 0.5 = 0$ and give $w = 0.5 \cdot (-1)(-1) + 0.5 \cdot 1 \cdot 1 = 1$ . The support vectors are the inputs $-1$ and $1$ , and moving the input $2$ to $3$ changes nothing. With $C = 0.1$ the inner points have $m_i = 0.5 < 1$ , so their weights are $0.1$ . The outer points lie exactly on the margin hyperplanes, and the conditions $w = 2\alpha_1 + 0.1 + 0.1 + 2\alpha_4 = 0.5$ and $\sum_i \alpha_i y_i = 0$ give $\alpha_1 = \alpha_4 = 0.075$ . All four points are support vectors at this smaller $C$ .

Check yourself

A candidate soft-margin SVM has functional margins $1.4$ , $0.2$ and $-0.5$ on three training examples, $\lVert \mathbf{w} \rVert_2^2 = 4$ and $C = 0.5$ . Find each hinge loss, say which examples are classified correctly and which satisfy the margin, and compute the objective $\tfrac12 \lVert \mathbf{w} \rVert_2^2 + C \sum_i \ell_i$ .

Show the answer

The hinge losses are $\max(0, 1 - 1.4) = 0$ , $\max(0, 1 - 0.2) = 0.8$ and $\max(0, 1 + 0.5) = 1.5$ , with total $2.3$ . The first example is correct and outside the margin. The second is correct but inside the margin, a margin violation without a classification error. The third has a negative functional margin, so it is misclassified. The objective is

\begin{aligned} \tfrac12 \cdot 4 + 0.5 \cdot 2.3 &= 2 + 1.15 \\[0.4em] &= 3.15 . \end{aligned}

Under the mean-loss convention the same model would be scored with a different formula and parameter, so the number $3.15$ belongs to the sum convention with $C = 0.5$ .

Two linear classifiers are compared at the point $(2, 1)$ with label $+1$ . Model A has $\mathbf{w} = (1, 1)$ and $b = -1$ , and model B has $\mathbf{w} = (4, 4)$ and $b = -4$ . A classmate says that model B keeps this point four times as far from its boundary. Compute both kinds of margin and assess the claim.

Show the answer

Model A gives the score $2 + 1 - 1 = 2$ , so the functional margin is $2$ , and with $\lVert \mathbf{w} \rVert_2 = \sqrt{2}$ the geometric margin is $2/\sqrt{2} = \sqrt{2} \approx 1.414$ . Model B gives the score $8 + 4 - 4 = 8$ , so the functional margin is $8$ , and with $\lVert \mathbf{w} \rVert_2 = 4\sqrt{2}$ the geometric margin is $8/(4\sqrt{2}) = \sqrt{2}$ .

The claim is wrong. Model B is model A with every parameter multiplied by $4$ , so both describe the same line $x_1 + x_2 = 1$ and the point is at the same distance $\sqrt{2}$ from it. Only the functional margin grew, and it grows with any rescaling. This is why the SVM fixes the scale with the constraints $y_i f(\mathbf{x}_i) \ge 1$ before it measures the margin by $1/\lVert \mathbf{w} \rVert_2$ .

Refit the four inputs $-2$ , $-1$ , $1$ and $2$ , with labels $-1$ , $-1$ , $+1$ and $+1$ , using $C = 0.3$ and the intercept $b = 0$ , which is optimal by the symmetry argument above. Find the optimal weight, the width of the slab, the violations and the support vectors with their dual weights, and compare with $C = 0.1$ and $C = 1$ .

Show the answer

On the piece $0 \le w \le \tfrac12$ the objective is $\tfrac12 w^2 + 0.3\,(4 - 6w)$ with derivative $w - 1.8 < 0$ , so it decreases there. On the piece $\tfrac12 \le w \le 1$ it is $\tfrac12 w^2 + 0.3\,(2 - 2w)$ with derivative $w - 0.6$ , which is zero at $w = 0.6$ , inside the piece. For $w \ge 1$ the objective $\tfrac12 w^2$ increases. So $w = 0.6$ , with objective $0.18 + 0.3 \cdot 0.8 = 0.42$ , and the slab has width $2/0.6 \approx 3.33$ .

The functional margins are $1.2$ , $0.6$ , $0.6$ and $1.2$ . The inner points violate the margin, each with hinge loss $0.4$ , and are still classified correctly, while the outer points lie outside the margin. So the inner points have $\alpha = C = 0.3$ , the outer points have $\alpha = 0$ , and the support vectors are the inputs $-1$ and $1$ . As a check, $0.3 + 0.3 = 0.6 = w$ and $\sum_i \alpha_i y_i = -0.3 + 0.3 = 0$ . Here the intercept is not unique, since every $b$ from $-0.2$ to $0.2$ gives the same objective, but the weight is.

Across the three fits, $C = 0.1$ gives $w = 0.5$ and a slab of width $4$ , $C = 0.3$ gives $w = 0.6$ and width about $3.33$ , and $C = 1$ gives $w = 1$ and width $2$ with no violations. Raising $C$ makes violations more expensive, so the margin narrows. In practice $C$ is chosen on validation data, not by the training objective.

Support Vector Machines and Soft Margins

Key terms

Functional margin

Geometric margin

Support vector machine

Hinge loss

Soft margin

Support vector

Check yourself

How this lesson connects

Builds on

Used later in