9. Support Vector Machines
Support vector machines are large-margin linear classifiers. They pick the boundary that maximizes the distance to the nearest points, control overfitting with the hinge loss and a penalty \(C\), and use kernels to fit nonlinear boundaries without ever forming the feature map. Throughout, labels are \(y \in \{-1,+1\}\) and the decision uses a raw score \(z = w^T x - b\).
Objectives
- Define the SVM hypothesis, its separating hyperplane, and the geometric margin.
- State the hard-margin primal and the soft-margin primal with hinge loss and penalty \(C\).
- Define kernels, the kernel trick, and the Mercer condition.
- Form the Lagrangian, derive the dual and KKT conditions, and define support vectors.
9.1 Optimal margin classifier
Labels are \(y \in \{-1,+1\}\), with weight vector \(w \in \mathbb{R}^{n}\) and bias \(b\).
9.1.1 Hypothesis and boundary
The hypothesis is defined as the sign of the raw score \(z = w^T x - b\):
\[\boxed{ h(x) = \operatorname{sign}(w^T x - b) }\]The decision boundary is the set of points with zero score:
\[\boxed{ w^T x - b = 0 }\]Remark: \(w\) is orthogonal to the boundary, so it sets the orientation, and \(b\) sets the offset.
9.1.2 Geometric margin
The geometric margin of example \(i\) is defined as its signed distance to the boundary, made positive by the label:
\[\boxed{ \gamma^{(i)} = y^{(i)} \, \frac{w^T x^{(i)} - b}{\lVert w \rVert} }\]A correctly classified point has \(\gamma^{(i)} > 0\). The margin of the dataset is the smallest \(\gamma^{(i)}\) over all examples.
Remark: dividing by \(\lVert w \rVert\) makes the margin invariant to rescaling \((w,b)\), unlike the raw score \(z\).
9.1.3 Hard-margin primal
Fixing the scale so the closest points satisfy \(y^{(i)}(w^T x^{(i)} - b) = 1\), maximizing the margin is equivalent to minimizing \(\lVert w \rVert^2\) subject to a unit functional margin:
\[\boxed{ \min_{w,b} \tfrac{1}{2}\lVert w \rVert^2 \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} - b) \ge 1 \ \ \forall i }\]This is a convex quadratic program with linear constraints, so it has a unique optimum.
Remark: it requires the data to be linearly separable. The next lesson relaxes that with slack variables.
The optimal hyperplane (solid) maximizes the margin (dashed). Circled points are the support vectors.
9.2 Hinge loss
The raw score is \(z = w^T x - b\) and labels are \(y \in \{-1,+1\}\).
9.2.1 Hinge loss
The hinge loss is defined as the amount by which the margin \(yz\) falls short of \(1\), clipped at zero:
\[\boxed{ L(z,y) = \max(0,\, 1 - yz), \quad z = w^T x - b }\]It is zero once \(yz \ge 1\) (the point is correct and beyond the margin) and grows linearly inside or past the margin.
Remark: the hinge loss is convex but not differentiable at \(yz = 1\), so it is optimized with subgradients.
9.2.2 Soft-margin primal
Introduce a slack \(\xi_i \ge 0\) per example to allow margin violations, penalized by \(C > 0\):
\[\boxed{ \min_{w,b,\xi} \tfrac{1}{2}\lVert w \rVert^2 + C\sum_{i=1}^{m}\xi_i \quad \text{s.t.} \quad y^{(i)}(w^T x^{(i)} - b) \ge 1 - \xi_i, \ \ \xi_i \ge 0 }\]At the optimum \(\xi_i = \max(0,\, 1 - y^{(i)}(w^T x^{(i)} - b))\), so eliminating the slacks gives the unconstrained regularized form:
\[\boxed{ \min_{w,b} \tfrac{1}{2}\lVert w \rVert^2 + C\sum_{i=1}^{m}\max\!\big(0,\, 1 - y^{(i)}(w^T x^{(i)} - b)\big) }\]This is regularization plus hinge loss: the \(\tfrac{1}{2}\lVert w \rVert^2\) term widens the margin and the sum penalizes violations.
9.2.3 Role of \(C\)
| \(C\) | Penalty on violations | Margin | Behaviour |
|---|---|---|---|
| small | weak | wide | more violations tolerated, lower variance |
| large | strong | narrow | fewer violations, fits training data harder |
Remark: as \(C \to \infty\) no violation is tolerated, which recovers the hard-margin classifier.
9.3 Kernels
9.3.1 Kernel definition
A kernel is defined as the inner product of a feature map \(\phi\) applied to two inputs:
\[\boxed{ K(x,z) = \phi(x)^T \phi(z) }\]A valid kernel computes this inner product directly, so \(\phi\) never has to be formed (it may even be infinite-dimensional).
9.3.2 Kernel trick
The SVM dual depends on the data only through inner products \(\langle x^{(i)}, x^{(j)} \rangle\). The kernel trick replaces each inner product with a kernel:
\[\boxed{ \langle x^{(i)}, x^{(j)} \rangle \ \longrightarrow \ K(x^{(i)}, x^{(j)}) }\]This fits a linear boundary in the feature space, which is nonlinear in the original space, at the cost of evaluating \(K\) instead of \(\phi\).
A widely used choice is the Gaussian (RBF) kernel:
\[\boxed{ K(x,z) = \exp\!\left( -\frac{\lVert x - z \rVert^2}{2\sigma^2} \right) }\]9.3.3 Mercer condition
A function \(K\) is a valid kernel if and only if, for every finite sample, its Gram matrix is symmetric positive semidefinite:
\[\boxed{ K = K^T, \qquad K \succeq 0 }\]Remark: this is the Mercer condition. It guarantees a feature map \(\phi\) exists, so the dual stays convex.
9.3.4 Common kernels
| Kernel | \(K(x,z)\) | Note |
|---|---|---|
| Linear | \(x^T z\) | no mapping, recovers the linear SVM |
| Polynomial | \((x^T z + c)^d\) | degree \(d\), offset \(c\) |
| Gaussian (RBF) | \(\exp\!\big(-\tfrac{\lVert x - z \rVert^2}{2\sigma^2}\big)\) | infinite-dimensional, local |
Remark: a small \(\sigma\) makes the RBF kernel very local, which can overfit. It trades off against \(C\).
An RBF kernel separates classes that are not linearly separable, with a nonlinear boundary in the input space.
9.4 Lagrangian and duality
9.4.1 Lagrangian
For a primal objective \(f(w)\) with inequality constraints \(g_i(w) \le 0\) and multipliers \(\beta_i \ge 0\), the Lagrangian is defined as:
\[\boxed{ \mathcal{L}(w,\beta) = f(w) + \sum_{i=1}^{m} \beta_i \, g_i(w) }\]Applied to the SVM primal \(\tfrac{1}{2}\lVert w \rVert^2\) with constraints \(1 - y^{(i)}(w^T x^{(i)} - b) \le 0\), the stationarity conditions \(\nabla_w \mathcal{L} = 0\) and \(\partial_b \mathcal{L} = 0\) give:
\[\boxed{ w = \sum_{i=1}^{m} \beta_i\, y^{(i)} x^{(i)}, \qquad \sum_{i=1}^{m} \beta_i\, y^{(i)} = 0 }\]So the optimal \(w\) is a linear combination of the training inputs weighted by \(\beta_i y^{(i)}\).
9.4.2 Dual problem
Substituting these back eliminates \(w\) and \(b\), leaving a problem in \(\beta\) that depends on the data only through inner products:
\[\boxed{ \max_{\beta} \ \sum_{i=1}^{m}\beta_i - \tfrac{1}{2}\sum_{i,j}\beta_i \beta_j\, y^{(i)} y^{(j)} \langle x^{(i)}, x^{(j)} \rangle \quad \text{s.t.} \quad \beta_i \ge 0, \ \ \sum_{i}\beta_i y^{(i)} = 0 }\]The inner products are exactly where a kernel \(K\) is substituted (see Kernels).
9.4.3 KKT and support vectors
At the optimum, complementary slackness ties each multiplier to its constraint:
\[\boxed{ \beta_i \big[\, y^{(i)}(w^T x^{(i)} - b) - 1 \,\big] = 0 }\]Support vectors are defined as the examples with a nonzero multiplier:
\[\boxed{ \text{support vectors} = \{\, i : \beta_i > 0 \,\} }\]These are the points exactly on the margin. All others have \(\beta_i = 0\) and do not affect \(w\).
9.4.4 Kernelized decision
Replacing the inner product by a kernel gives a decision rule expressed only through support vectors:
\[\boxed{ h(x) = \operatorname{sign}\!\left( \sum_{i=1}^{m} \beta_i\, y^{(i)}\, K(x^{(i)}, x) - b \right) }\]Remark: only support vectors (\(\beta_i > 0\)) contribute, so prediction cost scales with their count, not with \(m\).
9.4.5 From primal to decision
flowchart TD A["primal QP: minimize half norm squared"] B["Lagrangian with multipliers"] C["dual problem in beta"] D["KKT conditions"] E["support vectors: beta greater than zero"] F["kernelized decision rule"] A --> B B --> C C --> D D --> E E --> F
Support vector machines draw a single, possibly kernelized, boundary. The final part takes a different route: split the feature space with simple rules and combine many such models into an ensemble.