Support vector machines

The linear classifiers note replaced the 0–1 loss by convex surrogates, and the classification metrics note measured how the resulting classifiers err. One question was left open. When the two classes can be separated by a hyperplane, there are infinitely many separating hyperplanes, all with zero training error, and the training loss alone does not say which one to take. Logistic regression answers with probabilities; the support vector machine answers with geometry: take the hyperplane that stays as far as possible from the nearest training points (Boser, Guyon and Vapnik, 1992; Cortes and Vapnik, 1995). This note derives that rule, extends it to classes that overlap, and works out its dual problem, which shows that the solution depends on a few training points only and on nothing but inner products between them. The second fact is what the next note builds on.

Notation. Training points $x_1, \dots, x_n \in \mathbb R^d$ with labels $y_i \in \{-1, +1\}$. A linear classifier predicts $\operatorname{sign}(\langle w, x\rangle + b)$ with weights $w \in \mathbb R^d$ and bias $b$; its score is $f(x) = \langle w, x\rangle + b$. As in the linear classifiers note, the margin of an example is $M_i = y_i f(x_i)$: positive when $x_i$ is classified correctly. The margin of the hyperplane, $\gamma$, is the distance from the hyperplane to the nearest training point. $\lVert w \rVert$ is the Euclidean norm. Dual variables are $\alpha_i$ and $\mu_i$.

Which separating line?#

Figure

The maximum-margin line and its support vectors

All three lines in the figure classify the twenty training points correctly. The dotted ones pass within $0.35$ and $0.27$ of a training point; a new point drawn from the same clouds, slightly displaced from its neighbours, can easily land on the wrong side. The solid line keeps a distance of $0.81$ from every training point. The idea of the SVM is to make this distance, the margin of the hyperplane, as large as possible. Why a wide margin generalizes gives the theoretical reason; the intuition is that a classifier whose decision does not change when every training point is moved a little is less likely to be fitting accidents of the sample.

The distance from a point $x$ to the hyperplane $\langle w, x\rangle + b = 0$ is

$$\operatorname{dist}(x) = \frac{\lvert \langle w, x\rangle + b \rvert}{\lVert w \rVert} :$$

for any $x_0$ on the hyperplane, the distance is the length of the projection of $x - x_0$ on the unit normal $w / \lVert w \rVert$, which is $\lvert\langle w, x - x_0\rangle\rvert / \lVert w\rVert$, and $\langle w, x_0\rangle = -b$. For a hyperplane that classifies every point correctly, $\lvert f(x_i)\rvert = M_i$, so its margin is $\gamma = \min_i M_i / \lVert w\rVert$.

The hard-margin problem#

Multiplying $w$ and $b$ by the same positive number changes neither the classifier nor $\gamma$, so one scale can be fixed for free. The SVM fixes it so that the nearest points have $M_i = 1$: all points satisfy $M_i \ge 1$, with equality for the nearest ones. Then $\gamma = 1/\lVert w\rVert$, the band between the hyperplanes $f(x) = -1$ and $f(x) = +1$ contains no training point and has width $2/\lVert w\rVert$, and maximizing the margin is minimizing $\lVert w\rVert$. Squaring and halving make the objective smooth:

$$\begin{aligned} &\min_{w,\, b}\ \tfrac12 \lVert w \rVert^2\\ &\text{subject to}\ \ y_i(\langle w, x_i\rangle + b) \ge 1, \quad i = 1, \dots, n . \end{aligned}$$

This is the hard-margin SVM. The objective is strictly convex in $w$ and the constraints are linear, so when the data are separable the optimal $w$ is unique, and the problem is a quadratic program that standard solvers handle.

Worked example. Four points: $A = (0, 0)$ and $B = (2, 0)$ with $y = -1$, $C = (1, 2)$ and $D = (3, 3)$ with $y = +1$. The negative points span the segment $x_2 = 0$, $0 \le x_1 \le 2$, and the closest positive point to it is $C$, at distance 2. No separating line can be more than half of that, 1, from both classes, and the horizontal line $x_2 = 1$ achieves it. In the scaling of the SVM it is $w = (0, 1)$, $b = -1$: $M_A = M_B = M_C = 1$, $M_D = 2$, $\gamma = 1/\lVert w\rVert = 1$, and $\tfrac12\lVert w\rVert^2 = 0.5$. Three points touch the band; $D$ does not. The dual will recover the same answer from the other side.

When the classes overlap: slack variables#

Real classes overlap, and then no $w$ satisfies all the constraints $M_i \ge 1$. The soft-margin SVM (Cortes and Vapnik, 1995) lets each point violate its constraint by a slack $\xi_i \ge 0$ and pays $C$ per unit of slack:

$$\begin{aligned} &\min_{w,\, b,\, \xi}\ \tfrac12 \lVert w \rVert^2 + C \sum_{i=1}^n \xi_i\\ &\text{subject to}\ \ y_i(\langle w, x_i\rangle + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0 . \end{aligned}$$

A point with $\xi_i = 0$ is on the correct side of its edge of the band; $0 \lt \xi_i \lt 1$ means inside the band but still correctly classified; $\xi_i = 1$ puts the point on the hyperplane; $\xi_i \gt 1$ means on the wrong side of it. Each misclassified point contributes more than 1 to $\sum_i \xi_i$, so the total slack bounds the number of training errors from above. The constant $C \gt 0$ sets the exchange rate between a wide band and few violations: a large $C$ makes violations expensive, a small $C$ accepts many violations to keep $\lVert w\rVert$ small. On separable data the hard margin is the limit $C \to \infty$. On overlapping data it is not a limit of anything: the hard-margin constraints have no feasible point, and a larger $C$ only makes the unavoidable slack more expensive.

The soft margin is hinge loss plus L2#

For fixed $w$ and $b$ the best slack is the smallest one allowed: $\xi_i \ge 1 - M_i$ and $\xi_i \ge 0$ give $\xi_i = \max(0, 1 - M_i)$. Substituting it removes the constraints:

$$\min_{w,\, b}\ \ C \sum_{i=1}^n \max\big(0,\ 1 - y_i(\langle w, x_i\rangle + b)\big) + \tfrac12\lVert w\rVert^2 .$$

The first term is the hinge loss of the linear classifiers note, summed over the training set; the second is the ridge penalty of the regularization note. Dividing by $Cn$ gives the familiar form “average loss plus $\lambda \lVert w\rVert^2$” with $\lambda = 1/(2Cn)$: a large $C$ is weak regularization. So the SVM is not a new kind of model but a linear classifier trained with a particular surrogate loss and an L2 penalty. The geometry explains why this particular pair is natural: the penalty measures the inverse width of the band, and the hinge charges only the points that enter it.

The probabilistic reading of the two terms differs. The penalty is the negative log of a Gaussian prior on $w$, as in MAP estimation. The hinge, however, is not a negative log-likelihood. A conditional model $p(y \mid x) \propto e^{-C \max(0,\, 1 - y f(x))}$ would need $e^{-C\max(0,\,1 - f)} + e^{-C\max(0,\,1 + f)}$ to be the same for every score $f$, and it is not: $2e^{-C}$ at $f = 0$ against $1 + e^{-2C}$ at $f = 1$. For the logistic loss the same sum is exactly 1, which is why logistic regression outputs probabilities and the SVM does not.

What the hinge does estimate follows from the recipe of other losses, other targets: minimize the expected loss at each $x$ separately. With $\eta = P(Y = 1 \mid X = x)$ the expected hinge loss of a score $f$ is $\eta \max(0, 1 - f) + (1 - \eta)\max(0, 1 + f)$. On $[-1, 1]$ it equals $1 + (1 - 2\eta) f$, a straight line, and outside that interval it only grows. So the minimizer is $f^* = +1$ when $\eta \gt 1/2$ and $f^* = -1$ when $\eta \lt 1/2$: the sign of the Bayes classifier and nothing more (Lin, 2002), the hinge row of the table in what each surrogate estimates. With $\eta = 0.7$ and $\eta = 0.95$ the hinge asks for the same score $+1$, while the logistic loss asks for the log-odds $0.85$ and $2.94$. The SVM targets the right decision and discards the confidence; when probabilities are needed, they are fitted afterwards on held-out scores, as in the calibration section of the logistic regression note (Platt, 1999).

The dual problem#

The constrained form is where the structure of the solution shows. The tool is Lagrange duality (Boyd and Vandenberghe, 2004, Chapter 5). Write each constraint as “something $\ge 0$”: $M_i - 1 + \xi_i \ge 0$ and $\xi_i \ge 0$. Give each a multiplier, $\alpha_i \ge 0$ and $\mu_i \ge 0$, and subtract them from the objective:

$$\begin{aligned} L(w, b, \xi, \alpha, \mu) = {}&\tfrac12 \lVert w \rVert^2 + C \sum_i \xi_i\\ &- \sum_i \alpha_i \big(y_i(\langle w, x_i\rangle + b) - 1 + \xi_i\big) - \sum_i \mu_i \xi_i . \end{aligned}$$

Step 1: weak duality. At any feasible $(w, b, \xi)$ both subtracted sums are non-negative, so $L$ is at most the objective. Hence the dual function $g(\alpha, \mu) = \min_{w, b, \xi} L$ is a lower bound on the optimal value $p^*$ of the SVM problem, for every $\alpha, \mu \ge 0$. The dual problem asks for the best lower bound, $d^* = \max_{\alpha, \mu \ge 0} g(\alpha, \mu) \le p^*$.

Step 2: strong duality. The objective is convex and every constraint is affine, and the problem is feasible ($w = 0$, $b = 0$, $\xi_i = 1$ satisfies all constraints). For such problems the refined Slater condition holds and gives $d^* = p^*$, with the dual optimum attained (Boyd and Vandenberghe, 2004, §5.2.3). Solving the dual therefore solves the SVM.

Step 3: minimize $L$ over the primal variables. $L$ is a convex quadratic in $w$ and linear in $b$ and in each $\xi_i$. A linear function has a finite minimum only if its slope is zero; otherwise $g = -\infty$, which is useless as a bound. Setting the derivatives to zero:

$$\begin{aligned} \frac{\partial L}{\partial w} &= w - \sum_i \alpha_i y_i x_i = 0 &&\Longrightarrow\ w = \sum_i \alpha_i y_i x_i ,\\ \frac{\partial L}{\partial b} &= -\sum_i \alpha_i y_i = 0 &&\Longrightarrow\ \sum_i \alpha_i y_i = 0 ,\\ \frac{\partial L}{\partial \xi_i} &= C - \alpha_i - \mu_i = 0 &&\Longrightarrow\ \mu_i = C - \alpha_i . \end{aligned}$$

Step 4: substitute. With $\sum_i \alpha_i y_i = 0$ the term in $b$ vanishes, with $C - \alpha_i - \mu_i = 0$ the terms in $\xi_i$ vanish, and $\sum_i \alpha_i y_i \langle w, x_i\rangle = \langle w, w\rangle$ by the first condition:

$$g(\alpha) = \tfrac12\lVert w\rVert^2 - \lVert w\rVert^2 + \sum_i \alpha_i = \sum_{i} \alpha_i - \tfrac12 \sum_{i, j} \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle .$$

Step 5: collect the constraints. $\mu_i = C - \alpha_i \ge 0$ and $\alpha_i \ge 0$ together say $0 \le \alpha_i \le C$. The dual of the soft-margin SVM is

$$\begin{aligned} &\max_{\alpha}\ \sum_{i} \alpha_i - \tfrac12 \sum_{i, j} \alpha_i \alpha_j y_i y_j \langle x_i, x_j \rangle\\ &\text{subject to}\ \ 0 \le \alpha_i \le C,\quad \sum_i \alpha_i y_i = 0 . \end{aligned}$$

It is a concave quadratic program in $n$ variables: the matrix $(y_i y_j \langle x_i, x_j\rangle)$ is the Gram matrix of the vectors $y_i x_i$ and therefore positive semidefinite. The hard margin gives the same dual without the upper bound $C$. Two features matter for what follows. The data enter only through the inner products $\langle x_i, x_j\rangle$. And the solution is read off as $w = \sum_i \alpha_i y_i x_i$, so the classifier is

$$f(x) = \sum_{i} \alpha_i y_i \langle x_i, x\rangle + b ,$$

again a function of inner products only.

The KKT conditions#

Strong duality ties the primal and dual solutions together. At the optimum, $p^* = d^* = g(\alpha) \le L(w, b, \xi, \alpha, \mu) \le p^*$, so both inequalities are equalities; the second one forces each subtracted product to be zero. Together with the stationarity of Step 3 and the constraints, these are the Karush–Kuhn–Tucker conditions (Boyd and Vandenberghe, 2004, §5.5.3), necessary and, for a convex problem, sufficient for optimality:

• stationarity: $w = \sum_i \alpha_i y_i x_i$, $\ \sum_i \alpha_i y_i = 0$, $\ \alpha_i + \mu_i = C$;
• primal feasibility: $M_i \ge 1 - \xi_i$, $\ \xi_i \ge 0$;
• dual feasibility: $\alpha_i \ge 0$, $\ \mu_i \ge 0$;
• complementary slackness: $\alpha_i (M_i - 1 + \xi_i) = 0$, $\ \mu_i \xi_i = 0$.

Complementary slackness says that a multiplier can be non-zero only where its constraint is tight.

Worked example, continued. For the four points, $D$ has $M_D = 2 \gt 1$, so $\alpha_D = 0$. Stationarity gives $w = -\alpha_A (0, 0) - \alpha_B (2, 0) + \alpha_C (1, 2) = (\alpha_C - 2\alpha_B,\ 2\alpha_C)$, and $w = (0, 1)$ requires $\alpha_C = \tfrac12$, $\alpha_B = \tfrac14$. Then $\sum_i \alpha_i y_i = 0$ gives $\alpha_A = \alpha_C - \alpha_B = \tfrac14$. All multipliers are non-negative, so the KKT conditions hold and $w = (0, 1)$, $b = -1$ is optimal. The dual objective is $\sum_i \alpha_i - \tfrac12\lVert w\rVert^2 = 1 - 0.5 = 0.5$, equal to the primal $\tfrac12\lVert w\rVert^2$. Summing complementary slackness $\alpha_i(M_i - 1) = 0$ over the points gives $\sum_i \alpha_i = \lVert w\rVert^2$ for any hard-margin solution, so the margin can be read from the dual alone: $\gamma = 1/\sqrt{\sum_i \alpha_i}$. In the first figure $\sum_i \alpha_i = 1.5123$ and $\gamma = 0.81$.

Support vectors: what the dual variables tell you#

Figure

The soft margin: what the dual variables say

The KKT conditions sort the training points into three groups by their $\alpha_i$:

• $\alpha_i = 0$. Then $\mu_i = C \gt 0$, so $\xi_i = 0$ and $M_i \ge 1$: the point is on the correct side of its edge of the band. It does not appear in $w = \sum_i \alpha_i y_i x_i$.
• $0 \lt \alpha_i \lt C$. Then $\mu_i \gt 0$ forces $\xi_i = 0$, and $\alpha_i \gt 0$ forces $M_i = 1 - \xi_i = 1$: the point lies exactly on an edge of the band. These points give the bias: $y_i(\langle w, x_i\rangle + b) = 1$ and $y_i^2 = 1$ yield $b = y_i - \langle w, x_i\rangle$, averaged over all such points for numerical stability.
• $\alpha_i = C$. Then $\mu_i = 0$, $\xi_i$ may be positive and $M_i = 1 - \xi_i \le 1$: the point is on the edge, inside the band, or on the wrong side.

Read backwards: a point strictly outside the band ($M_i \gt 1$) must have $\alpha_i = 0$, and a point with positive slack must have $\alpha_i = C$. The points with $\alpha_i \gt 0$ are the support vectors; the solution is a weighted sum of them alone. In the figure 6 of 20 points are support vectors: three on the edges with $\alpha = 0.64, 0.68, 0.96$, and three with $\alpha = C = 1$ and slacks $0.66$, $0.92$ (inside the band) and $1.54$ (misclassified).

Sparsity has two practical consequences. Deleting a point with $\alpha_i = 0$ and refitting leaves the KKT conditions satisfied by the same $w$ and $b$, so the solution does not change; refitting the twenty separable points on their three support vectors alone gives the same line, as the Code section checks. And in leave-one-out validation every point with $\alpha_i = 0$ is classified correctly when held out, since the classifier trained without it is the same and puts it outside the band. The leave-one-out error is therefore at most the number of support vectors divided by $n$, provided the solver returns the same solution when a point with $\alpha_i = 0$ is removed. This bounds the leave-one-out estimate, which, like cross-validation, describes the procedure on training sets of size $n - 1$; few support vectors are a good sign, but not a finite-sample guarantee for the risk of the one deployed model.

How C trades margin for errors#

On the breast cancer data (569 tumours, 30 standardized features, 70% for training) the choice of $C$ moves the solution from a wide band with many violations to a narrow band that fits the training set exactly:

$C$	support vectors	of them with $\alpha = C$	band width $2/\lVert w\rVert$	train accuracy	test accuracy
0.001	195	189	6.38	0.940	0.930
0.01	92	83	3.01	0.980	0.959
0.1	44	32	1.46	0.992	0.959
1	27	11	0.69	0.992	0.953
10	25	3	0.32	0.995	0.953
100	25	1	0.09	1.000	0.930

With small $C$ almost every support vector sits at the bound $\alpha = C$: the band is wide and many points are inside it. As $C$ grows the band narrows, the training accuracy reaches 1, and the test accuracy falls back to $0.930$: large $C$ is weak regularization and overfits, exactly like a small ridge penalty. $C$ is a hyperparameter, chosen by cross-validation on a logarithmic grid. Because the band width is measured in the units of the features, the features must be standardized first; otherwise the feature with the largest scale dominates $\lVert w\rVert$.

Why a wide margin generalizes#

The first generalization bound of the probability course controlled the gap between training and true risk through the number of candidate models. Hyperplanes in $\mathbb R^d$ are infinitely many, and the classical replacement for $\ln K$ grows with $d$: in high dimension, separating the training set says little. Margins remove the dimension. Suppose every input has $\lVert x\rVert \le \rho$ and the distribution is separable with margin $\gamma$ by a hyperplane through the origin. Then with probability at least $1 - \delta$ over a training set of size $n$, the hard-margin SVM has 0–1 risk at most

$$\sqrt{\frac{4 (\rho/\gamma)^2}{n}} + \sqrt{\frac{2 \ln (2/\delta)}{n}}$$

(Shalev-Shwartz and Ben-David, 2014, Theorem 15.4). The dimension $d$ does not appear; only the ratio of the data radius to the margin does. With $\rho/\gamma = 10$, $n = 10{,}000$ and $\delta = 0.05$ the bound is $0.200 + 0.027 = 0.227$: loose, as such bounds are, but it holds in a million dimensions as well as in two. This is what makes it reasonable to map the data into a space of enormous dimension and separate it there with a wide margin, the programme of the next note.

Solving it in practice#

The dual has one equality constraint, so the smallest set of variables that can be changed while keeping $\sum_i \alpha_i y_i = 0$ is a pair. Sequential minimal optimization (Platt, 1998) repeatedly picks two multipliers, solves the two-variable problem in closed form and clips it to the box $[0, C]$. LIBSVM, the solver behind scikit-learn’s SVC, takes as the first multiplier the one that most violates the KKT conditions and as the second the one that, paired with it, gives the largest increase of the dual objective, as estimated from second-order information (LIBSVM minimizes the negative of the dual written above, so in its own terms this is the largest decrease) (Fan, Chen and Lin, 2005; Chang and Lin, 2011). The figures of this note are computed by the same method in a few dozen lines. For linear SVMs on large data, the unconstrained hinge-plus-L2 form is minimized directly by stochastic subgradient steps, as in Pegasos (Shalev-Shwartz et al., 2011), whose cost does not grow with $n$ for a fixed accuracy. A linear SVM on TF-IDF vectors was for years the standard strong baseline for text classification (Joachims, 1998), the setting of the bag-of-words note of the NLP course.

What changed#

	Logistic regression	Support vector machine
Which separating line	the maximum-likelihood one	the one with the widest margin
Loss	logistic, smooth, never zero	hinge, zero for $M_i \ge 1$
Training points that matter	all, each with weight $p_i - [y_i = 1]$ in the gradient	only the support vectors, $\alpha_i \gt 0$
Output	a probability $P(y = 1 \mid x)$	a score whose sign is the class; probabilities need calibration
Optimization	unconstrained, smooth	a quadratic program, usually solved through its dual
Regularization knob	$\lambda$	$C$, with $\lambda = 1/(2Cn)$
Data enter as	feature vectors	inner products $\langle x_i, x_j\rangle$ in the dual

Limitations#

• No probabilities. The hinge loss targets only the sign of $P(y = 1 \mid x) - 1/2$; any probability has to be fitted afterwards, which needs held-out data.
• Sensitive to scale and to $C$. The margin is a Euclidean distance, so features must be standardized, and $C$ must be tuned; the table shows test accuracy moving by three points across the grid.
• Outliers still pull. The hinge grows linearly, so a mislabelled point far on the wrong side becomes a support vector with $\alpha_i = C$ and shifts the solution; the bound $C$ limits but does not remove its influence.
• Linear. As written, the SVM separates with a hyperplane in the original features. Two concentric rings of points defeat it, whatever $C$.
• Two classes. Several classes need a reduction to binary problems or a joint formulation; the multiclass note compares them.

What you should remember#

• The distance from $x$ to the hyperplane is $\lvert\langle w, x\rangle + b\rvert / \lVert w\rVert$; scaling so that the nearest points have $M_i = 1$ makes the margin $1/\lVert w\rVert$ and the band width $2/\lVert w\rVert$.
• Hard margin: minimize $\tfrac12\lVert w\rVert^2$ subject to $M_i \ge 1$. Soft margin: add slacks $\xi_i$ at price $C$, which is the same as minimizing $C\sum_i \max(0, 1 - M_i) + \tfrac12\lVert w\rVert^2$, hinge loss plus an L2 penalty.
• The dual is $\max \sum_i \alpha_i - \tfrac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\langle x_i, x_j\rangle$ subject to $0 \le \alpha_i \le C$, $\sum_i \alpha_i y_i = 0$; strong duality holds, and $w = \sum_i \alpha_i y_i x_i$.
• KKT: $\alpha_i = 0$ outside the band, $0 \lt \alpha_i \lt C$ exactly on its edge (these give $b$), $\alpha_i = C$ inside it or misclassified. Only support vectors, $\alpha_i \gt 0$, shape the solution.
• Large $C$ means weak regularization. The hinge estimates the Bayes decision, not probabilities. Margin bounds depend on $\rho/\gamma$, not on the dimension.

Code#

The worked example, the two figures, the dual solved by a generic optimizer, and the effect of $C$:

import numpy as np
from scipy.optimize import minimize
from sklearn.svm import SVC
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

def fit(X, y, C):
    m = SVC(kernel='linear', C=C, tol=1e-8).fit(X, y)
    alpha = np.zeros(len(y)); alpha[m.support_] = np.abs(m.dual_coef_[0])   # dual_coef_ holds y_i * alpha_i
    return m.coef_[0], m.intercept_[0], alpha

# the worked example: four points, hard margin (a very large C)
X4 = np.array([[0, 0], [2, 0], [1, 2], [3, 3]]); y4 = np.array([-1, -1, 1, 1])
w, b, alpha = fit(X4, y4, 1e6)
print(w.round(3), round(b, 3), alpha.round(3))          # [0. 1.] -1.0 [0.25 0.25 0.5  0.  ]

# twenty separable points (the first figure); class -1 first
Xh = np.array([[-0.9, -0.7], [-1.7, -0.4], [-1.5, -1.9], [-0.6, -1], [-1.9, -0.2], [-2.6, -0.3], [-1.8, -0.7], [-1.7, -0.1], [-1.6, -0.4], [-1.5, -1.2],
               [2, 1.5], [0.7, 1.3], [0.4, 0.5], [1.5, -0.4], [0.1, 2.1], [2.8, 2], [0.4, 0.8], [1.5, 0.8], [2.5, 0.3], [0.3, 0.4]])
y = np.repeat([-1, 1], 10)
w, b, alpha = fit(Xh, y, 1e6)
sv = np.flatnonzero(alpha > 1e-6)
print(w.round(3), round(b, 3), round(2 / np.linalg.norm(w), 3), sv, alpha[sv].round(3))
# [0.87 0.87] 0.391 1.626 [ 0  3 19] [0.63  0.126 0.756]
print(round(alpha.sum(), 4), round(w @ w, 4))           # 1.5123 1.5123: at the hard-margin optimum, sum(alpha) = ||w||^2
w2, b2, _ = fit(Xh[sv], y[sv], 1e6)
print(w2.round(3), round(b2, 3))                        # [0.87 0.87] 0.391: the support vectors alone give the same line

# twenty overlapping points (the second figure), C = 1
Xs = np.array([[-0.7, -1.3], [-1.6, -0.5], [-0.9, -0.3], [-2.2, -1], [-1.5, 0.1], [-0.4, -0.3], [-0.9, -0.5], [-0.5, -1.3], [0.4, 0.4], [0.7, -0.9],
               [1.6, 0.7], [0.1, 1.5], [0.3, 0.3], [1.1, -0.1], [0.4, 1.4], [1.9, 1.2], [1.8, 0.3], [1.7, 1.8], [1.8, -1.3], [2.3, 0.2]])
w, b, alpha = fit(Xs, y, 1.0)
M = y * (Xs @ w + b); xi = np.maximum(0, 1 - M)
print(w.round(3), round(b, 3), np.flatnonzero((alpha > 1e-6) & (alpha < 1 - 1e-6)), np.flatnonzero(alpha > 1 - 1e-6), xi[alpha > 1 - 1e-6].round(2))
# [1.256 0.762] -0.269 [ 5 11 18] [ 8  9 12] [1.54 0.92 0.66]
print(round(0.5 * w @ w + xi.sum(), 4), round(alpha.sum() - 0.5 * w @ w, 4))   # 4.2044 4.2044: primal = dual

# the same dual solved by a generic optimizer: max sum(a) - 1/2 a^T Q a, 0 <= a <= C, sum(a y) = 0
Q = (y[:, None] * Xs) @ (y[:, None] * Xs).T
res = minimize(lambda a: 0.5 * a @ Q @ a - a.sum(), np.zeros(20), jac=lambda a: Q @ a - 1, method='SLSQP',
               bounds=[(0, 1)] * 20, constraints={'type': 'eq', 'fun': lambda a: a @ y}, options={'ftol': 1e-12, 'maxiter': 500})
a = res.x; w_dual = (a * y) @ Xs
free = (a > 1e-4) & (a < 1 - 1e-4)
print(w_dual.round(3), round(np.mean(y[free] - Xs[free] @ w_dual), 3))   # [1.256 0.762] -0.269

# the effect of C on breast cancer (569 tumours, 30 standardized features)
X, t = load_breast_cancer(return_X_y=True)
Xtr, Xte, ttr, tte = train_test_split(X, 2 * t - 1, test_size=0.3, random_state=0, stratify=t)
sc = StandardScaler().fit(Xtr); Xtr, Xte = sc.transform(Xtr), sc.transform(Xte)
for C in (0.001, 0.01, 0.1, 1, 10, 100):
    m = SVC(kernel='linear', C=C).fit(Xtr, ttr)
    at_C = int((np.abs(m.dual_coef_[0]) > C * (1 - 1e-6)).sum())
    print(C, len(m.support_), at_C, round(2 / np.linalg.norm(m.coef_[0]), 3), round(m.score(Xtr, ttr), 3), round(m.score(Xte, tte), 3))
# C, support vectors, of them with alpha = C, band width, train and test accuracy
# 0.001 195 189 6.381 0.94 0.93 | 0.01 92 83 3.014 0.98 0.959 | 0.1 44 32 1.459 0.992 0.959
# 1 27 11 0.686 0.992 0.953     | 10 25 3 0.321 0.995 0.953    | 100 25 1 0.089 1.0 0.93

Next#

The dual and the classifier touch the data only through inner products $\langle x_i, x_j\rangle$, and the margin bound does not care about the dimension. Both facts point the same way: replace $x$ by a richer representation $\phi(x)$, perhaps of enormous or infinite dimension, and never compute $\phi$ at all, only $\langle \phi(x_i), \phi(x_j)\rangle$. The next note shows which functions can play the role of that inner product and what they buy: curved decision boundaries from the same quadratic program.

References#

• B. E. Boser, I. M. Guyon, V. N. Vapnik. A Training Algorithm for Optimal Margin Classifiers. COLT, 1992, pp. 144–152. The hard-margin classifier and its dual.
• C. Cortes, V. Vapnik. Support-Vector Networks. Machine Learning, 20(3), pp. 273–297, 1995. The soft margin.
• S. Boyd, L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004. Chapter 5: the Lagrange dual (§5.1–5.2), Slater’s condition and its refinement for affine constraints (§5.2.3), complementary slackness and the KKT conditions (§5.5.2–5.5.3).
• S. Shalev-Shwartz, S. Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014. Chapter 15: hard and soft SVM, Theorem 15.4 (the margin bound), §15.3 (support vectors), §15.4 (duality), §15.5 (SGD).
• Y. Lin. Support Vector Machines and the Bayes Rule in Classification. Data Mining and Knowledge Discovery, 6(3), pp. 259–275, 2002. The minimizer of the expected hinge loss.
• J. C. Platt. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods. In A. Smola, P. Bartlett, B. Schölkopf, D. Schuurmans (eds.), Advances in Large Margin Classifiers, pp. 61–74. MIT Press, 1999.
• J. Platt. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Microsoft Research, MSR-TR-98-14, 1998.
• C.-C. Chang, C.-J. Lin. LIBSVM: A Library for Support Vector Machines. ACM Transactions on Intelligent Systems and Technology, 2(3), 2011. Section 4.1: the working set selection.
• R.-E. Fan, P.-H. Chen, C.-J. Lin. Working Set Selection Using Second Order Information for Training Support Vector Machines. Journal of Machine Learning Research, 6, pp. 1889–1918, 2005.
• S. Shalev-Shwartz, Y. Singer, N. Srebro, A. Cotter. Pegasos: Primal Estimated Sub-Gradient Solver for SVM. Mathematical Programming, 127(1), pp. 3–30, 2011.
• T. Joachims. Text Categorization with Support Vector Machines: Learning with Many Relevant Features. ECML, 1998, pp. 137–142.
• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Section 7.1 (maximum margin classifiers, overlapping classes, relation to logistic regression), Appendix E (Lagrange multipliers).
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Section 12.2 (the support vector classifier), Section 12.3.2 (the SVM as a penalization method).
• E. Sokolov et al. Машинное обучение (HSE), lecture notes: lecture 5 (the support vector machine), lecture 14 (the dual and the kernel SVM).