11.3 Support Vector Machines (SVM) I: Linear SVM

Introduction

Support Vector Machines are powerful supervised learning models for classification and regression. Linear SVMs find the optimal hyperplane that maximizes the margin between classes. This geometric approach provides strong theoretical guarantees and excellent generalization performance.

1. The Geometric Intuition

Consider a binary classification problem with labels $y \in \{-1, +1\}$ and feature vectors $\mathbf{x} \in \mathbb{R}^d$. A linear classifier uses a hyperplane to separate the classes:

$$\mathbf{w}^T \mathbf{x} + b = 0$$

where $\mathbf{w}$ is the normal vector to the hyperplane and $b$ is the bias term.

Decision Function

The classification decision is:

$$f(\mathbf{x}) = \text{sign}(\mathbf{w}^T \mathbf{x} + b)$$

Points on one side of the hyperplane ($\mathbf{w}^T \mathbf{x} + b > 0$) are classified as +1, while points on the other side are classified as -1.

2. The Margin

The margin is the distance from the hyperplane to the nearest data point from either class. The SVM finds the hyperplane that maximizes this margin.

Functional Margin

For a training point $(\mathbf{x}_i, y_i)$, the functional margin is:

$$\hat{\gamma}_i = y_i(\mathbf{w}^T \mathbf{x}_i + b)$$

A correct classification requires $\hat{\gamma}_i > 0$. The functional margin of the dataset is:

$$\hat{\gamma} = \min_{i=1,\ldots,n} \hat{\gamma}_i$$

Problem: The functional margin can be made arbitrarily large by scaling $\mathbf{w}$ and $b$.

Geometric Margin

The geometric margin normalizes by $\|\mathbf{w}\|$:

$$\gamma_i = \frac{y_i(\mathbf{w}^T \mathbf{x}_i + b)}{\|\mathbf{w}\|}$$

This represents the actual Euclidean distance from $\mathbf{x}_i$ to the hyperplane. The geometric margin of the dataset is:

$$\gamma = \min_{i=1,\ldots,n} \gamma_i = \frac{\hat{\gamma}}{\|\mathbf{w}\|}$$

3. The Hard-Margin SVM

For linearly separable data, we want to find $\mathbf{w}$ and $b$ that maximize the geometric margin $\gamma$.

Primal Formulation

The optimization problem is:

$$\begin{align} \max_{\mathbf{w}, b} \quad & \gamma \\ \text{subject to} \quad & \frac{y_i(\mathbf{w}^T \mathbf{x}_i + b)}{\|\mathbf{w}\|} \geq \gamma, \quad i=1,\ldots,n \end{align}$$

By setting $\hat{\gamma} = 1$ (scaling constraint), this becomes:

$$\begin{align} \min_{\mathbf{w}, b} \quad & \frac{1}{2}\|\mathbf{w}\|^2 \\ \text{subject to} \quad & y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1, \quad i=1,\ldots,n \end{align}$$

This is a quadratic programming (QP) problem with linear constraints.

4. Support Vectors

Points that lie exactly on the margin boundaries satisfy:

$$y_i(\mathbf{w}^T \mathbf{x}_i + b) = 1$$

These are the support vectors. They are the critical points that determine the optimal hyperplane. Points further from the boundary ($y_i(\mathbf{w}^T \mathbf{x}_i + b) > 1$) do not affect the solution.

5. The Dual Formulation

Using Lagrange multipliers $\alpha_i \geq 0$ for each constraint, the Lagrangian is:

$$L(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{n} \alpha_i [y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1]$$

Karush-Kuhn-Tucker (KKT) Conditions

At the optimum, the following conditions must hold:

1. Stationarity: $\nabla_{\mathbf{w}} L = \mathbf{w} - \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i = 0$
2. Stationarity: $\frac{\partial L}{\partial b} = -\sum_{i=1}^{n} \alpha_i y_i = 0$
3. Complementary slackness: $\alpha_i [y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1] = 0$
4. Primal feasibility: $y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1$
5. Dual feasibility: $\alpha_i \geq 0$

Dual Optimization Problem

Substituting $\mathbf{w} = \sum_{i=1}^{n} \alpha_i y_i \mathbf{x}_i$ into the Lagrangian gives the dual:

$$\begin{align} \max_{\boldsymbol{\alpha}} \quad & \sum_{i=1}^{n} \alpha_i - \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j \\ \text{subject to} \quad & \alpha_i \geq 0, \quad i=1,\ldots,n \\ & \sum_{i=1}^{n} \alpha_i y_i = 0 \end{align}$$

Solution Representation

The optimal weight vector is:

$$\mathbf{w}^* = \sum_{i=1}^{n} \alpha_i^* y_i \mathbf{x}_i$$

Only support vectors have $\alpha_i^* > 0$, so:

$$\mathbf{w}^* = \sum_{i \in SV} \alpha_i^* y_i \mathbf{x}_i$$

The bias can be computed from any support vector:

$$b^* = y_i - \mathbf{w}^{*T} \mathbf{x}_i$$

In practice, we average over all support vectors for numerical stability.

6. Soft-Margin SVM

Real data is often not linearly separable. The soft-margin SVM allows some misclassifications by introducing slack variables $\xi_i \geq 0$.

Primal Formulation

$$\begin{align} \min_{\mathbf{w}, b, \boldsymbol{\xi}} \quad & \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{n} \xi_i \\ \text{subject to} \quad & y_i(\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i \\ & \xi_i \geq 0, \quad i=1,\ldots,n \end{align}$$

The parameter $C > 0$ controls the trade-off between:

• Maximizing the margin (small $\|\mathbf{w}\|^2$)
• Minimizing training errors (small $\sum \xi_i$)

Interpretation of Slack Variables

• $\xi_i = 0$: Point is correctly classified with margin $\geq 1$
• $0 < \xi_i < 1$: Point is correctly classified but within the margin
• $\xi_i \geq 1$: Point is misclassified

Dual Formulation

The dual problem becomes:

$$\begin{align} \max_{\boldsymbol{\alpha}} \quad & \sum_{i=1}^{n} \alpha_i - \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j \\ \text{subject to} \quad & 0 \leq \alpha_i \leq C, \quad i=1,\ldots,n \\ & \sum_{i=1}^{n} \alpha_i y_i = 0 \end{align}$$

The only difference from the hard-margin case is the box constraint $\alpha_i \leq C$.

7. Hinge Loss Interpretation

The soft-margin SVM can be rewritten as:

$$\min_{\mathbf{w}, b} \frac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{n} \max(0, 1 - y_i(\mathbf{w}^T \mathbf{x}_i + b))$$

The term $\max(0, 1 - y_i f(\mathbf{x}_i))$ is the hinge loss:

$$\ell_{hinge}(y, f(\mathbf{x})) = \max(0, 1 - y f(\mathbf{x}))$$

This shows that SVM minimizes a regularized empirical risk:

$$\frac{\lambda}{2}\|\mathbf{w}\|^2 + \frac{1}{n}\sum_{i=1}^{n} \ell_{hinge}(y_i, f(\mathbf{x}_i))$$

where $\lambda = 1/(nC)$.

8. Multi-class SVM

SVMs are inherently binary classifiers. For $K$ classes, we use:

One-vs-Rest (OvR)

Train $K$ binary classifiers, each separating one class from all others. Predict the class with the highest decision function value:

$$\hat{y} = \arg\max_{k=1,\ldots,K} f_k(\mathbf{x})$$

One-vs-One (OvO)

Train $\binom{K}{2} = \frac{K(K-1)}{2}$ binary classifiers, one for each pair of classes. Use voting: predict the class that wins the most pairwise comparisons.

Structured SVM

A unified formulation that learns all $K$ decision functions jointly:

$$\min_{\mathbf{W}, b} \frac{1}{2}\|\mathbf{W}\|_F^2 + C\sum_{i=1}^{n} \max_{k \neq y_i} \max(0, 1 + \mathbf{w}_k^T \mathbf{x}_i - \mathbf{w}_{y_i}^T \mathbf{x}_i)$$

9. Computational Aspects

Solving the Dual Problem

The dual is a QP problem with $n$ variables. Standard QP solvers have complexity $O(n^3)$, which is prohibitive for large datasets.

Sequential Minimal Optimization (SMO)

SMO breaks the large QP into a series of smallest possible QP problems:

1. Select two Lagrange multipliers $\alpha_i$ and $\alpha_j$
2. Optimize these two while holding all others fixed
3. This two-variable problem has an analytical solution
4. Repeat until convergence

SMO is efficient and scales to large datasets. Typical complexity is $O(n^2)$ to $O(n^3)$ depending on the data.

10. Connection to LLMs

SVM principles influence modern language models:

• Margin maximization: Contrastive learning objectives maximize separation between correct and incorrect outputs
• Support vectors: Hard negative mining focuses training on challenging examples (analogous to support vectors)
• Hinge loss: Used in ranking objectives for information retrieval components
• Dual representation: Attention mechanisms compute predictions as weighted combinations of training examples
• Regularization: Weight decay in neural networks serves a similar role to the $\|\mathbf{w}\|^2$ term
• Decision boundaries: Understanding linear separability informs embedding space design

Key Takeaways

• SVMs find the maximum margin hyperplane separating classes
• Only support vectors (points on the margin) determine the decision boundary
• The dual formulation depends only on inner products between data points
• Soft-margin SVMs use slack variables to handle non-separable data
• The parameter $C$ controls the trade-off between margin and training error
• Hinge loss provides a convex surrogate for 0-1 loss
• SVMs have strong theoretical guarantees and excellent generalization
• The dual representation enables the kernel trick (next section)