### The maximum margin classifier Given linearly separable data with labels y_i in {-1, +1} and feature vectors x_i, we want a hyperplane w^T x + b = 0 that separates the classes. The distance from a point x_i to the hyperplane is: ``` distance = |w^T x_i + b| / ||w|| ``` For a correctly classified point: y_i * (w^T x_i + b) > 0. The margin is twice the distance from the hyperplane to the nearest point on either side. ```mermaid graph LR subgraph Margin direction TB A["w^T x + b = +1"] ~~~ B["w^T x + b = 0"] ~~~ C["w^T x + b = -1"] end D["+ class points"] --> A E["- class points"] --> C B --- F["Decision boundary"] ``` The optimization problem: ``` maximize 2 / ||w|| (the margin width) subject to y_i * (w^T x_i + b) >= 1 for all i ``` Equivalently (minimizing ||w||^2 is easier to optimize): ``` minimize (1/2) ||w||^2 subject to y_i * (w^T x_i + b) >= 1 for all i ``` This is a convex quadratic program. It has a unique global solution. The data points that sit exactly on the margin boundaries (where y_i * (w^T x_i + b) = 1) are the support vectors. They are the only points that determine the decision boundary. Move or remove any non-support-vector point, and the boundary does not change. ### Support vectors: the critical few ```mermaid graph TD subgraph Classification SV1["Support Vector (+ class)
y(w'x+b) = 1"] --- DB["Decision Boundary
w'x+b = 0"] DB --- SV2["Support Vector (- class)
y(w'x+b) = 1"] end O1["Other + points
(do not affect boundary)"] -.-> SV1 O2["Other - points
(do not affect boundary)"] -.-> SV2 ``` Most training points are irrelevant. Only the support vectors matter. This is why SVMs are memory-efficient at prediction time: you only need to store the support vectors, not the entire training set. The number of support vectors also gives a bound on generalization error. Fewer support vectors relative to the dataset size means better generalization. ### Soft margin: handling noise with the C parameter Real data is rarely perfectly separable. Some points may be on the wrong side of the boundary, or inside the margin. The soft margin formulation allows violations by introducing slack variables. ``` minimize (1/2) ||w||^2 + C * sum(xi_i) subject to y_i * (w^T x_i + b) >= 1 - xi_i xi_i >= 0 for all i ``` The slack variable xi_i measures how much point i violates the margin. C controls the trade-off: | C value | Behavior | |---------|----------| | Large C | Penalizes violations heavily. Narrow margin, fewer misclassifications. Overfits | | Small C | Allows more violations. Wide margin, more misclassifications. Underfits | C is the regularization strength, inverted. Large C = less regularization. Small C = more regularization. ### Hinge loss: the SVM loss function The soft margin SVM can be rewritten as an unconstrained optimization: ``` minimize (1/2) ||w||^2 + C * sum(max(0, 1 - y_i * (w^T x_i + b))) ``` The term max(0, 1 - y_i * f(x_i)) is the hinge loss. It is zero when the point is correctly classified and beyond the margin. It is linear when the point is inside the margin or misclassified. ``` Hinge loss for a single point: loss | | \ | \ | \ | \ | \_______________ | +-----|-----|--------> y * f(x) 0 1 Zero loss when y*f(x) >= 1 (correctly classified, outside margin). Linear penalty when y*f(x) < 1. ``` Compare with logistic loss (logistic regression): ``` Hinge: max(0, 1 - y*f(x)) Hard cutoff at margin Logistic: log(1 + exp(-y*f(x))) Smooth, never exactly zero ``` Hinge loss produces sparse solutions (only support vectors have nonzero contribution). Logistic loss uses all data points. This makes SVMs more memory-efficient at prediction time. ### Training a linear SVM with gradient descent You can train a linear SVM using gradient descent on the hinge loss plus L2 regularization, without solving the constrained QP: ``` L(w, b) = (lambda/2) * ||w||^2 + (1/n) * sum(max(0, 1 - y_i * (w^T x_i + b))) Gradient with respect to w: If y_i * (w^T x_i + b) >= 1: dL/dw = lambda * w If y_i * (w^T x_i + b) < 1: dL/dw = lambda * w - y_i * x_i Gradient with respect to b: If y_i * (w^T x_i + b) >= 1: dL/db = 0 If y_i * (w^T x_i + b) < 1: dL/db = -y_i ``` This is called the primal formulation. It runs in O(n * d) per epoch, where n is the number of samples and d is the number of features. For large, sparse, high-dimensional data (text classification), this is fast. ### The dual formulation and the kernel trick The Lagrangian dual of the SVM problem (from Phase 1 Lesson 18, KKT conditions) is: ``` maximize sum(alpha_i) - (1/2) * sum_ij(alpha_i * alpha_j * y_i * y_j * (x_i . x_j)) subject to 0 <= alpha_i <= C sum(alpha_i * y_i) = 0 ``` The dual only involves dot products x_i . x_j between data points. This is the key insight. Replace every dot product with a kernel function K(x_i, x_j) and the SVM can learn nonlinear boundaries without ever computing the transformation explicitly. ``` Linear kernel: K(x, z) = x . z Polynomial kernel: K(x, z) = (x . z + c)^d RBF (Gaussian): K(x, z) = exp(-gamma * ||x - z||^2) ``` The RBF kernel maps data into an infinite-dimensional space. Points that are close in input space have kernel value near 1. Points that are far apart have kernel value near 0. It can learn any smooth decision boundary. ```mermaid graph LR subgraph "Input Space (not separable)" A["Data points in 2D
circular boundary"] end subgraph "Feature Space (separable)" B["Data points in higher dim
linear boundary"] end A -->|"Kernel trick
K(x,z) = phi(x).phi(z)"| B ``` The kernel trick computes the dot product in the high-dimensional space without ever going there. For the polynomial kernel of degree d in D dimensions, the explicit feature space has O(D^d) dimensions. But K(x, z) is computed in O(D) time. ### SVM for regression (SVR) Support Vector Regression fits a tube of width epsilon around the data. Points inside the tube have zero loss. Points outside the tube are penalized linearly. ``` minimize (1/2) ||w||^2 + C * sum(xi_i + xi_i*) subject to y_i - (w^T x_i + b) <= epsilon + xi_i (w^T x_i + b) - y_i <= epsilon + xi_i* xi_i, xi_i* >= 0 ``` The epsilon parameter controls the tube width. Wider tube = fewer support vectors = smoother fit. Narrower tube = more support vectors = tighter fit. ### Why SVMs lost to deep learning (and when they still win) SVMs dominated ML from the late 1990s through the early 2010s. Deep learning surpassed them for several reasons: | Factor | SVMs | Deep learning | |--------|------|---------------| | Feature engineering | Requires it | Learns features | | Scalability | O(n^2) to O(n^3) for kernel | O(n) per epoch with SGD | | Image/text/audio | Needs handcrafted features | Learns from raw data | | Large datasets (>100k) | Slow | Scales well | | GPU acceleration | Limited benefit | Massive speedup | SVMs still win in these situations: - Small datasets (hundreds to low thousands of samples) - High-dimensional sparse data (text with TF-IDF features) - When you need mathematical guarantees (margin bounds) - When training time must be minimal (linear SVM is very fast) - Binary classification with clear margin structure - Anomaly detection (one-class SVM) ```figure svm-margin ```