Support Vector Machine
So far in both regression and classification, we have used probabilistic predictors that model \(p(y \mid \mathbf{x})\)
and optimize via maximum likelihood. Here, we take a fundamentally different, geometric approach. Rather than modeling
probabilities, we seek the hyperplane that separates the classes with the largest possible margin. This formulation leads
naturally to a constrained optimization problem whose
dual formulation enables the kernel trick.
This margin-based approach often generalizes well, especially in high-dimensional spaces with limited
samples. By employing the kernel trick (for example, the RBF kernel), SVMs can implicitly map
inputs into higher-dimensional feature spaces. This enables the classification of nonlinearly separable data
without explicitly computing those transformations. Despite the rise of deep learning, SVMs remain valuable for
small- to medium-sized datasets. They offer robustness and interpretability through a sparse set of support vectors.
In binary classification with labels \(\tilde{y} \in \{-1, +1\}\), the prediction is \(h(\mathbf{x}) = \operatorname{sign}(f(\mathbf{x}))\), and the decision boundary (hyperplane) is defined by
\[
f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b. \tag{1}
\]
To obtain a robust solution, we would like to maximize the margin between data points and the decision boundary.
To express the distance of the closest point to the decision boundary, we decompose any point \(\mathbf{x}\) as its
orthogonal projection
onto the hyperplane \(H = \{\mathbf{x} : f(\mathbf{x}) = 0\}\) plus a signed normal component:
\[
\mathbf{x} = \operatorname{proj}_H \mathbf{x} + r \frac{\mathbf{w}}{\|\mathbf{w}\|}, \tag{2}
\]
where \(r\) is the signed distance from \(\mathbf{x}\) to \(H\), and \(\mathbf{w}/\|\mathbf{w}\|\) is the unit normal vector to \(H\).
Substituting Expression (2) into the boundary function (1):
\[
\begin{align*}
f(\mathbf{x}) &= \mathbf{w}^\top \!\left(\operatorname{proj}_H \mathbf{x} + r \frac{\mathbf{w}}{\|\mathbf{w}\|}\right) + b \\\\
&= \underbrace{\mathbf{w}^\top \operatorname{proj}_H \mathbf{x} + b}_{= \, f(\operatorname{proj}_H \mathbf{x}) \, = \, 0} + r \|\mathbf{w}\| \\\\
&= r \|\mathbf{w}\|.
\end{align*}
\]
Hence
\[
r = \frac{f(\mathbf{x})}{\|\mathbf{w}\|},
\]
and each correctly classified point satisfies
\[
\tilde{y}_n f(\mathbf{x}_n) \gt 0.
\]
Therefore, our objective is
\[
\max_{\mathbf{w},\, b} \frac{1}{\|\mathbf{w}\|} \min_{1 \leq n \leq N} \tilde{y}_n \!\left(\mathbf{w}^\top \mathbf{x}_n + b\right).
\]
Since both \(\mathbf{w}\) and \(b\) can be freely rescaled without changing the decision boundary, we may normalize so that the
closest point satisfies \(\tilde{y}_n f(\mathbf{x}_n) = 1\) exactly. Under this normalization, the margin (distance between the two
parallel supporting hyperplanes) equals \(\frac{2}{\|\mathbf{w}\|}\).
Note that \(\max \frac{1}{\|\mathbf{w}\|}\) is equivalent to \(\min \|\mathbf{w}\|^2\). Thus our objective becomes:
Hard-Margin SVM (Primal)
\[
\min_{\mathbf{w},\, b} \frac{1}{2}\|\mathbf{w}\|^2
\]
subject to
\[
\tilde{y}_n(\mathbf{w}^\top \mathbf{x}_n + b) \geq 1, \quad n = 1, \ldots, N.
\]
The factor of \(\frac{1}{2}\) is included for convenience when differentiating.
This constrained optimization problem, known as the primal problem, is difficult to solve directly. Since the
objective is convex and the inequality constraints are linear, Slater's condition is automatically satisfied, so
strong duality holds and the problem
can equivalently be solved via its dual.
The dual is often computationally more convenient, and it is the form in which the kernel trick applies.
Let \(\boldsymbol{\alpha} \in \mathbb{R}^N\) be the vector of Lagrange multipliers associated with the inequality constraints. The Lagrangian is
\[
\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\mathbf{w}^\top \mathbf{w} - \sum_{n=1}^N \alpha_n \!\left(\tilde{y}_n (\mathbf{w}^\top \mathbf{x}_n + b) - 1\right). \tag{3}
\]
A primal-dual optimum \((\hat{\mathbf{w}}, \hat{b}, \hat{\boldsymbol{\alpha}})\) satisfies
\[
(\hat{\mathbf{w}}, \hat{b}, \hat{\boldsymbol{\alpha}}) = \min_{\mathbf{w}, b} \max_{\boldsymbol{\alpha} \geq \mathbf{0}} \mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}).
\]
Taking derivatives with respect to \(\mathbf{w}\) and \(b\) and setting them to zero (the stationarity condition):
\[
\begin{align*}
\nabla_{\mathbf{w}} \mathcal{L} &= \mathbf{w} - \sum_{n=1}^N \alpha_n \tilde{y}_n \mathbf{x}_n = \mathbf{0}, \\\\
\frac{\partial \mathcal{L}}{\partial b} &= -\sum_{n=1}^N \alpha_n \tilde{y}_n = 0,
\end{align*}
\]
which gives
\[
\begin{align*}
\hat{\mathbf{w}} &= \sum_{n=1}^N \hat{\alpha}_n \tilde{y}_n \mathbf{x}_n, \\\\
0 &= \sum_{n=1}^N \hat{\alpha}_n \tilde{y}_n.
\end{align*}
\]
Substituting these into the Lagrangian (3):
\[
\begin{align*}
\mathcal{L}(\hat{\mathbf{w}}, \hat{b}, \boldsymbol{\alpha})
&= \frac{1}{2}\hat{\mathbf{w}}^\top \hat{\mathbf{w}} - \sum_{n=1}^N \alpha_n \tilde{y}_n \hat{\mathbf{w}}^\top \mathbf{x}_n
- \hat{b} \sum_{n=1}^N \alpha_n \tilde{y}_n + \sum_{n=1}^N \alpha_n \\\\
&= \frac{1}{2}\hat{\mathbf{w}}^\top \hat{\mathbf{w}} - \hat{\mathbf{w}}^\top \hat{\mathbf{w}} - 0 + \sum_{n=1}^N \alpha_n \\\\
&= \sum_{n=1}^N \alpha_n - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j \tilde{y}_i \tilde{y}_j \, \mathbf{x}_i^\top \mathbf{x}_j.
\end{align*}
\]
Hard-Margin SVM (Dual)
\[
\max_{\boldsymbol{\alpha}} \sum_{n=1}^N \alpha_n - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j \tilde{y}_i \tilde{y}_j \, \mathbf{x}_i^\top \mathbf{x}_j
\]
subject to
\[
\sum_{n=1}^N \alpha_n \tilde{y}_n = 0, \quad \alpha_n \geq 0, \quad n = 1, \ldots, N.
\]
The primal-dual solution must satisfy the KKT conditions:
\[
\begin{align*}
\mathbf{w} - \sum_{n=1}^N \alpha_n \tilde{y}_n \mathbf{x}_n &= \mathbf{0}, \quad \sum_{n=1}^N \alpha_n \tilde{y}_n = 0 &&\text{(stationarity)} \\\\
\tilde{y}_n f(\mathbf{x}_n) - 1 &\geq 0 &&\text{(primal feasibility)} \\\\
\alpha_n &\geq 0 &&\text{(dual feasibility)} \\\\
\alpha_n (\tilde{y}_n f(\mathbf{x}_n) - 1) &= 0 &&\text{(complementary slackness)}
\end{align*}
\]
Complementary slackness implies that, for each data point, either
\[
\hat{\alpha}_n = 0 \quad \text{or} \quad \tilde{y}_n (\hat{\mathbf{w}}^\top \mathbf{x}_n + \hat{b}) = 1.
\]
The points with \(\hat{\alpha}_n \gt 0\) are called support vectors. For such a point the
first alternative fails, so the second one must hold and the point lies exactly on the margin. Every
remaining point has \(\hat{\alpha}_n = 0\) and therefore contributes nothing to \(\hat{\mathbf{w}}\).
Let the set of support vectors be \(\mathcal{S}\). To perform prediction, we expand
\(\hat{\mathbf{w}} = \sum_{n \in \mathcal{S}} \hat{\alpha}_n \tilde{y}_n \mathbf{x}_n\):
\[
\begin{align*}
f(\mathbf{x};\, \hat{\mathbf{w}}, \hat{b})
&= \hat{\mathbf{w}}^\top \mathbf{x} + \hat{b} \\\\
&= \sum_{n \in \mathcal{S}} \hat{\alpha}_n \tilde{y}_n\, \mathbf{x}_n^\top \mathbf{x} + \hat{b}.
\end{align*}
\]
By the kernel trick, the inner product can be replaced with a
positive definite kernel
\(\mathcal{K}(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle\). The kernel implicitly maps
inputs to a higher- (or infinite-) dimensional feature space without ever computing \(\phi\) explicitly.
SVM Prediction (Kernel Form)
\[
f(\mathbf{x}) = \sum_{n \in \mathcal{S}} \hat{\alpha}_n \tilde{y}_n \mathcal{K}(\mathbf{x}_n, \mathbf{x}) + \hat{b},
\]
where the bias is computed by averaging over the support vectors:
\[
\begin{align*}
\hat{b} &= \frac{1}{|\mathcal{S}|} \sum_{n \in \mathcal{S}} \!\left(\tilde{y}_n - \hat{\mathbf{w}}^\top \mathbf{x}_n \right) \\\\
&= \frac{1}{|\mathcal{S}|} \sum_{n \in \mathcal{S}} \!\left(\tilde{y}_n - \sum_{m \in \mathcal{S}} \hat{\alpha}_m \tilde{y}_m \mathbf{x}_m^\top \mathbf{x}_n \right).
\end{align*}
\]
Applying the kernel trick to the bias as well:
\[
\hat{b} = \frac{1}{|\mathcal{S}|} \sum_{n \in \mathcal{S}} \!\left(\tilde{y}_n - \sum_{m \in \mathcal{S}} \hat{\alpha}_m \tilde{y}_m \mathcal{K}(\mathbf{x}_m, \mathbf{x}_n) \right).
\]
Soft Margin Constraints
Consider the case where the data are not linearly separable. In this case there is no feasible solution in which
\(\tilde{y}_n f(\mathbf{x}_n) \geq 1\) for all \(n\). By introducing slack variables \(\xi_n \geq 0\), we relax the constraint
\(\tilde{y}_n f(\mathbf{x}_n) \geq 1\) to the soft margin constraint:
\[
\tilde{y}_n f(\mathbf{x}_n) \geq 1 - \xi_n.
\]
Thus our objective becomes:
Soft-Margin SVM (Primal)
\[
\min_{\mathbf{w},\, b,\, \boldsymbol{\xi}} \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{n=1}^N \xi_n
\]
subject to
\[
\xi_n \geq 0, \quad \tilde{y}_n(\mathbf{w}^\top \mathbf{x}_n + b) \geq 1 - \xi_n,
\]
where \(C \gt 0\) is a hyperparameter that controls how many data points are allowed to violate the margin.
The Lagrangian becomes
\[
\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}, \boldsymbol{\xi}, \boldsymbol{\mu})
= \frac{1}{2} \mathbf{w}^\top \mathbf{w} + C \sum_{n=1}^N \xi_n
- \sum_{n=1}^N \alpha_n \!\left(\tilde{y}_n(\mathbf{w}^\top \mathbf{x}_n + b) - 1 + \xi_n\right)
- \sum_{n=1}^N \mu_n \xi_n,
\]
where \(\alpha_n \geq 0\) and \(\mu_n \geq 0\) are Lagrange multipliers.
Setting the derivatives of \(\mathcal{L}\) to zero with respect to \(\mathbf{w}\), \(b\), and \(\xi_n\):
\[
\begin{align*}
\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = \mathbf{0}
&\implies \mathbf{w} = \sum_{n=1}^N \alpha_n \tilde{y}_n \mathbf{x}_n, \\\\
\frac{\partial \mathcal{L}}{\partial b} = 0
&\implies \sum_{n=1}^N \alpha_n \tilde{y}_n = 0, \\\\
\frac{\partial \mathcal{L}}{\partial \xi_n} = 0
&\implies C - \alpha_n - \mu_n = 0.
\end{align*}
\]
The third condition, combined with \(\mu_n \geq 0\), gives \(\alpha_n \leq C\). Since we also require \(\alpha_n \geq 0\),
we obtain the box constraint \(0 \leq \alpha_n \leq C\).
Substituting the first two conditions back into the Lagrangian eliminates the primal variables and yields the same dual objective
as the hard-margin case:
\[
\mathcal{L}(\boldsymbol{\alpha}) = \sum_{i=1}^N \alpha_i - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j \tilde{y}_i \tilde{y}_j \, \mathbf{x}_i^\top \mathbf{x}_j,
\]
but now subject to the constraints
\[
0 \leq \alpha_n \leq C, \quad
\sum_{n=1}^N \alpha_n \tilde{y}_n = 0.
\]
These constraints partition the training points into three cases. Complementary slackness for \(\alpha_n\) and
\(\mu_n\), combined with \(C - \alpha_n - \mu_n = 0\), pins down both the slack and the position of each
point:
- If \(\alpha_n = 0\): then \(\mu_n = C \gt 0\), which forces \(\xi_n = 0\) and leaves
\(\tilde{y}_n f(\mathbf{x}_n) \geq 1\). The point lies on or outside the margin and is correctly
classified (ignored by the model).
- If \(0 \lt \alpha_n \lt C\): then \(\mu_n \gt 0\) forces \(\xi_n = 0\), and \(\alpha_n \gt 0\) forces
\(\tilde{y}_n f(\mathbf{x}_n) = 1\). The point lies exactly on the margin boundary. These are the
free support vectors.
- If \(\alpha_n = C\): then \(\mu_n = 0\) leaves \(\xi_n\) free, while \(\alpha_n \gt 0\) forces
\(\tilde{y}_n f(\mathbf{x}_n) = 1 - \xi_n\). These are the bound support vectors, and
the slack alone decides where the point sits.
- If \(\xi_n \lt 1\): correctly classified, on or inside the margin.
- If \(\xi_n = 1\): exactly on the decision boundary.
- If \(\xi_n \gt 1\): misclassified.
SVM Demo: Solving the Dual QP
This demo solves the soft-margin dual problem derived above. The solution is exact, not approximate. Pressing
Solve starts from \(\boldsymbol{\alpha} = \mathbf{0}\) and maximizes
\[
\sum_{n=1}^N \alpha_n - \frac{1}{2} \sum_{i=1}^N \sum_{j=1}^N \alpha_i \alpha_j \tilde{y}_i \tilde{y}_j \, \mathcal{K}(\mathbf{x}_i, \mathbf{x}_j)
\]
subject to
\[
0 \leq \alpha_n \leq C, \quad \sum_{n=1}^N \alpha_n \tilde{y}_n = 0.
\]
Prediction then uses the kernel form \(f(\mathbf{x}) = \sum_{n} \hat{\alpha}_n \tilde{y}_n \mathcal{K}(\mathbf{x}_n, \mathbf{x}) + \hat{b}\)
with the solved multipliers.
Every quantity on display is computed from \(\hat{\boldsymbol{\alpha}}\) itself. That includes the support-vector
rings, the three-case counts, the duality gap, and the KKT violation. Nothing is inferred from geometric
proximity to the boundary.
How the Solver Works
The dual is a quadratic program in \(N\) variables, coupled by the box constraints and one linear equality.
The equality constraint means a single \(\alpha_n\) can never move alone. The smallest working set that
preserves \(\sum_n \alpha_n \tilde{y}_n = 0\) is a pair. Sequential Minimal Optimization (SMO)
exploits that fact. At each step it selects the pair of multipliers that violates the KKT conditions most, and
solves the resulting two-variable subproblem in closed form. The subproblem is a one-dimensional
quadratic maximization over an interval. Because every step is an exact maximization, the dual objective
\(D(\boldsymbol{\alpha})\) never decreases. The left-hand curve makes this monotonicity visible.
The right-hand curve tracks the duality gap. At each stage the demo reconstructs the primal
variables from the current \(\boldsymbol{\alpha}\), evaluates the soft-margin primal objective
\(P(\mathbf{w}, b, \boldsymbol{\xi}) = \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_n \xi_n\), and plots
\(P - D\) on a log scale. Weak duality guarantees \(P \geq D\) at every feasible point, so watching the gap
collapse toward zero is a certificate of optimality that requires no knowledge of the true solution.
Convergence is declared only when the maximal KKT violation falls below \(10^{-3}\). If the step cap is
reached first, the demo reports the failure explicitly rather than presenting the result as optimal.
Stopping a run midway discards the partial solution entirely.
Reading the Visualization
- Training points. Solid circles with labels \(\tilde{y} \in \{-1, +1\}\).
- Test points. Semi-transparent squares, never seen by the solver.
- Decision boundary. The solid contour \(f(\mathbf{x}) = 0\). It is an analytic line for the
linear kernel and a numerically traced contour for the RBF kernel.
- Margin boundaries. Dashed contours where \(f(\mathbf{x}) = \pm 1\). The shading encodes the
sign and magnitude of \(f\).
- True boundary. The dashed curve from which the data were generated. It is the target the
learned boundary should recover.
- Free support vectors (\(0 \lt \alpha_n \lt C\)). These carry gold rings and sit exactly on
the margin.
- Bound support vectors (\(\alpha_n = C\)). These carry orange rings and lie on or inside the margin, possibly misclassified.
- Points without rings have \(\alpha_n = 0\). Deleting them would leave the solution unchanged.
The Three Cases and the Bias
The KKT panel counts the partition established for the soft-margin problem: \(\alpha_n = 0\) (outside the
margin), \(0 \lt \alpha_n \lt C\) (on the margin), and \(\alpha_n = C\), split by whether \(\xi_n \leq 1\)
(not misclassified) or \(\xi_n \gt 1\) (misclassified). It also reports the largest KKT violation
over all training points and the residual of \(\sum_n \alpha_n \tilde{y}_n\), so the optimality claim can be
checked against the numbers rather than taken on faith.
One practical subtlety concerns the bias. The kernel prediction formula above averages
\(\tilde{y}_n - \sum_m \hat{\alpha}_m \tilde{y}_m \mathcal{K}(\mathbf{x}_m, \mathbf{x}_n)\) over support
vectors. That step uses the fact that they satisfy \(\tilde{y}_n f(\mathbf{x}_n) = 1\). In the soft-margin
problem this equality is guaranteed only for the free support vectors. A bound point
(\(\alpha_n = C\)) may violate its margin. The demo therefore averages over exactly the free set. In the rare
case that no free support vector exists, it falls back to the midpoint of the KKT-feasible interval for
\(\hat{b}\).
Experiment Suggestions
- Sweep \(C\) on the linear pattern (with some label noise). The margin \(2/\|\mathbf{w}\|\) shrinks
monotonically as \(C\) grows, and the bound support vectors thin out. Small \(C\) buys a wide margin at the
price of many margin violations. That trade-off is written directly into the primal objective.
- Give the linear kernel circular data. Test accuracy collapses to chance or below. No half-plane
separates an annulus from a disk. Switch to the RBF kernel and the same solver, on the same data, recovers
the circle.
- Sweep \(\gamma\) at fixed \(C\) on circular data. Small \(\gamma\) underfits (the boundary is too
smooth to close around the inner disk), moderate \(\gamma\) generalizes best, and large \(\gamma\) overfits.
The support-vector count traces a U-shape across the sweep.
- Force overfitting with large \(\gamma\), large \(C\), and heavy noise. Training accuracy reaches
100% while test accuracy drops. The boundary contorts around individual mislabeled points, and each such
point is held by its own support vectors.
- Approach the hard margin. At zero noise and large \(C\), the bound set empties out and only a
handful of free support vectors remain. They sit exactly on the dashed margin lines. The hard-margin
picture is recovered as a limit.
SVMs demonstrate how maximizing the margin, a purely geometric intuition, leads to strong generalization guarantees,
particularly in high-dimensional spaces with limited data. In PCA & Autoencoders,
we shift from supervised to unsupervised learning and ask how to discover low-dimensional
structure in data without any labels. That question connects
eigenvalue decomposition to neural
network-based representation learning.
