Support Vector Machine (SVM)

Support Vector Machine

So far in both regression and classification, we have used probabilistic predictors that model \(p(y \mid \mathbf{x})\) and fit them by maximum likelihood, possibly with a penalty. 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\}\) (that is, \(\tilde{y} = 2y - 1\) in terms of the labels \(y \in \{0, 1\}\) of logistic regression), we use for inputs \(\mathbf{x} \in \mathbb{R}^D\) the affine score \[ f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b, \quad \mathbf{w} \neq \mathbf{0}, \tag{1} \] predict \(h(\mathbf{x}) = \operatorname{sign}(f(\mathbf{x}))\), and take the decision boundary to be the hyperplane \(H = \{\mathbf{x} : f(\mathbf{x}) = 0\}\). To obtain a robust solution, we would like to maximize the margin between data points and the decision boundary.

To express the distance of a point to the decision boundary, fix any \(\mathbf{x}_0 \in H\). Then \(H = \mathbf{x}_0 + W\), where \(W = \{\mathbf{v} : \mathbf{w}^\top \mathbf{v} = 0\}\) is a subspace of dimension \(D - 1\) whose orthogonal complement is the line spanned by \(\mathbf{w}\). Applying the orthogonal decomposition to \(\mathbf{x} - \mathbf{x}_0\) relative to \(W\), we write any point \(\mathbf{x}\) as a point of \(H\) plus a signed normal component: \[ \mathbf{x} = \operatorname{proj}_H \mathbf{x} + r \frac{\mathbf{w}}{\|\mathbf{w}\|}, \tag{2} \] where \(\operatorname{proj}_H \mathbf{x} = \mathbf{x}_0 + \operatorname{proj}_W (\mathbf{x} - \mathbf{x}_0) \in H\), \(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}\|}\).

We assume that the training data are linearly separable, so that some \((\mathbf{w}, b)\) classifies every point correctly. The normalization then reads \(\min_n \tilde{y}_n f(\mathbf{x}_n) = 1\), and maximizing \(\frac{1}{\|\mathbf{w}\|}\) is equivalent to minimizing \(\|\mathbf{w}\|^2\). Relaxing the normalization to \(\tilde{y}_n f(\mathbf{x}_n) \geq 1\) for all \(n\) does not change the optimum. If every one of these constraints held strictly at a minimizer, dividing \((\mathbf{w}, b)\) by \(\min_n \tilde{y}_n f(\mathbf{x}_n) \gt 1\) would keep it feasible and decrease \(\|\mathbf{w}\|\). Thus our objective becomes:

This constrained optimization problem is known as the primal problem. Rather than solving it directly, we pass to its dual. Scaling any feasible \((\mathbf{w}, b)\) by \(2\) gives \(\tilde{y}_n(\mathbf{w}^\top \mathbf{x}_n + b) \geq 2 \gt 1\) for every \(n\), so Slater's condition holds. Since the objective is convex and the constraints are affine, 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} \] The dual objective at \(\boldsymbol{\alpha} \geq \mathbf{0}\) is the Lagrange dual function \(\inf_{\mathbf{w}, b} \mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha})\). Since \(\mathcal{L}\) is linear in \(b\) with coefficient \(-\sum_n \alpha_n \tilde{y}_n\), this infimum is \(-\infty\) unless \(\sum_n \alpha_n \tilde{y}_n = 0\), which therefore becomes a constraint of the dual. Under that constraint, \(\mathcal{L}\) is a strictly convex quadratic in \(\mathbf{w}\), minimized where its gradient vanishes. Together, the two conditions are the stationarity conditions \[ \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 give \[ \begin{align*} \mathbf{w} &= \sum_{n=1}^N \alpha_n \tilde{y}_n \mathbf{x}_n, \\\\ 0 &= \sum_{n=1}^N \alpha_n \tilde{y}_n. \end{align*} \] Substituting these into the Lagrangian (3), for any \(b\): \[ \begin{align*} \inf_{\mathbf{w}, b} \mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) &= \frac{1}{2}\mathbf{w}^\top \mathbf{w} - \sum_{n=1}^N \alpha_n \tilde{y}_n \mathbf{w}^\top \mathbf{x}_n - b \sum_{n=1}^N \alpha_n \tilde{y}_n + \sum_{n=1}^N \alpha_n \\\\ &= \frac{1}{2}\mathbf{w}^\top \mathbf{w} - \mathbf{w}^\top \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*} \]

The KKT conditions follow from strong duality. Both optima are attained. The dual optimum is attained by the strong duality theorem, since the primal optimal value is at least \(0\). The primal optimum is attained because the primal is a feasible convex quadratic program whose objective grows without bound in \(\mathbf{w}\), and for fixed \(\mathbf{w}\) the constraints confine \(b\) to a bounded interval once both classes are present. For a primal optimum \((\hat{\mathbf{w}}, \hat{b})\) and a dual optimum \(\hat{\boldsymbol{\alpha}}\), \[ \begin{align*} \tfrac{1}{2}\|\hat{\mathbf{w}}\|^2 &= \inf_{\mathbf{w}, b} \mathcal{L}(\mathbf{w}, b, \hat{\boldsymbol{\alpha}}) \\\\ &\leq \mathcal{L}(\hat{\mathbf{w}}, \hat{b}, \hat{\boldsymbol{\alpha}}) \\\\ &\leq \tfrac{1}{2}\|\hat{\mathbf{w}}\|^2, \end{align*} \] where the first equality is strong duality and the last step uses \(\hat{\boldsymbol{\alpha}} \geq \mathbf{0}\) and primal feasibility. Both inequalities are therefore equalities. The first makes \((\hat{\mathbf{w}}, \hat{b})\) a minimizer of the convex function \(\mathcal{L}(\cdot, \cdot, \hat{\boldsymbol{\alpha}})\), which is stationarity. The second says that \(\sum_n \hat{\alpha}_n (\tilde{y}_n f(\mathbf{x}_n) - 1) = 0\), a sum of nonnegative terms, so each term vanishes, which is complementary slackness.

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, every inner product \(\mathbf{x}_i^\top \mathbf{x}_j\) in the dual objective and in this expansion can be replaced with a positive definite kernel \(\mathcal{K}(\mathbf{x}, \mathbf{x}')\). For every such kernel, the Moore-Aronszajn theorem supplies a Hilbert space of functions in which \(\phi(\mathbf{x}) = \mathcal{K}(\cdot, \mathbf{x})\) satisfies \(\mathcal{K}(\mathbf{x}, \mathbf{x}') = \langle \phi(\mathbf{x}), \phi(\mathbf{x}') \rangle\), so the kernelized SVM is the linear SVM run on the features \(\phi(\mathbf{x}_n)\). The kernel implicitly maps inputs to a higher- (or infinite-) dimensional feature space without ever computing \(\phi\) explicitly.

The average for \(\hat{b}\) uses \(\tilde{y}_n f(\mathbf{x}_n) = 1\), equivalently \(\hat{b} = \tilde{y}_n - \hat{\mathbf{w}}^\top \mathbf{x}_n\) since \(\tilde{y}_n^2 = 1\), at every support vector. The set \(\mathcal{S}\) is nonempty whenever the training data contain both labels, because \(\hat{\mathbf{w}} = \mathbf{0}\) is then infeasible. In the soft-margin problem below, the equality holds only on part of \(\mathcal{S}\), and the demo section returns to this point.

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:

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 three conditions back into the Lagrangian eliminates the primal variables (the third makes the coefficient \(C - \alpha_n - \mu_n\) of each \(\xi_n\) vanish) 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. \] The soft-margin problem is always strictly feasible (take \(\mathbf{w} = \mathbf{0}\), \(b = 0\), and \(\xi_n = 2\)), so the argument given for the hard-margin case again yields strong duality and the KKT conditions at the optimum. These conditions 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.