Maximum Margin Classifier | ML-101

Drawing the Best Possible Line

Imagine you have two groups of points on a 2D plane — red and blue — and you need to draw a line that separates them. There are infinitely many lines that could work. But which one is best? The answer that Support Vector Machines (SVMs) give is elegant: choose the line that is as far as possible from both groups. This is the idea of the maximum margin classifier.

The intuition is that a decision boundary far from both classes is more likely to generalize well. A boundary squeezed close to one class would misclassify points that are only slightly different from the training data. By maximizing the gap — the margin — we build in robustness against small perturbations.

The Decision Hyperplane

In two dimensions, the decision boundary is a line. In higher dimensions, it is a hyperplane: an (n−1)-dimensional flat subspace in an n-dimensional feature space. A hyperplane is defined by a weight vector w and a bias b. Any point x on the hyperplane satisfies:

Hyperplane Equation

\mathbf{w}^\top \mathbf{x} + b = 0

w is the normal vector (perpendicular to the hyperplane). b is the bias (offset from the origin). Points on opposite sides of the hyperplane get opposite signs.

For classification, we assign a label based on which side of the hyperplane a point falls on: if w^Tx + b > 0, predict class +1; if < 0, predict class −1. The hyperplane itself (where the expression equals zero) is the decision boundary.

The Margin

The margin is the total width of the band between the two classes, measured perpendicularly to the decision boundary. SVMs define two parallel margin hyperplanes, one for each class: w^Tx + b = +1 and w^Tx + b = −1. The training data must lie on or beyond these planes. The margin — the distance between the two planes — is:

Geometric Margin

\text{margin} = \dfrac{2}{\|\mathbf{w}\|}

The margin width is 2 divided by the norm of the weight vector. Maximizing the margin is equivalent to minimizing ‖w‖.

To maximize the margin, we minimize ‖w‖ subject to the constraint that all training points are correctly classified and lie outside the margin band. This is a convex quadratic optimization problem with a unique global solution — a critical advantage over methods like neural networks that can have many local optima.

Support Vectors

The training points that lie exactly on the margin hyperplanes (where w^Tx + b = ±1) are called support vectors. These are the closest points to the decision boundary from each class, and they are the only points that actually determine the position and orientation of the hyperplane.

This is a profound property: the SVM solution depends only on a small subset of the training data. If you removed any non-support-vector point from the training set, the decision boundary would not change. This sparsity makes SVMs memory-efficient at prediction time — only the support vectors need to be stored. It also gives SVMs a theoretical connection to structural risk minimization, which bounds generalization error.

Why "Support" Vectors?

The term "support" comes from the fact that these points support the margin boundaries — they hold the two margin planes in place. Move one support vector slightly and the whole boundary shifts. Move any other training point (as long as it stays outside the margin band) and nothing changes. This is geometrically intuitive: the boundary is determined entirely by the most informative, most borderline examples.

Hard Margin SVM

When the data is linearly separable — there exists at least one hyperplane that perfectly classifies all training points — we can use the hard margin SVM. It finds the maximum-margin separating hyperplane with zero misclassification. The optimization problem is:

Hard Margin Optimization

\min_{\mathbf{w},b}\;\tfrac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.}\quad y_i(\mathbf{w}^\top \mathbf{x}_i + b) \geq 1 \;\forall\, i

Minimize the squared norm of w (equivalent to maximizing margin) subject to the constraint that every training point is classified correctly and lies outside the margin band. y_i ∈ {-1, +1} are the class labels.

The hard margin SVM has one critical weakness: it requires the data to be perfectly separable. Real-world datasets almost never are — there is always noise, outliers, or overlapping classes. A single misplaced point can make the problem infeasible. This motivates the soft margin extension.

Soft Margin SVM

The soft margin SVM relaxes the hard constraints by introducing slack variables ξ_i ≥ 0, one per training point. A slack variable represents how much the constraint is violated: ξ_i = 0 means the point is correctly classified and outside the margin; 0 < ξ_i ≤ 1 means the point is inside the margin but correctly classified; ξ_i > 1 means the point is misclassified.

Soft Margin Optimization

\min_{\mathbf{w},b,\boldsymbol{\xi}}\;\tfrac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{n}\xi_i \quad \text{s.t.}\quad y_i(\mathbf{w}^\top \mathbf{x}_i + b) \geq 1-\xi_i,\;\xi_i\geq 0

The penalty term C·Σξ_i allows some points to violate the margin. C controls the trade-off between margin width and the total penalty for violations.

The C Parameter

The regularization parameter C is the most important hyperparameter in an SVM. It controls the trade-off between maximizing the margin and minimizing training error:

Large C: The penalty for misclassification is high, so the optimizer will try hard to classify all points correctly. This leads to a narrower margin but fewer training errors. The model has lower bias but higher variance — it may overfit if the data is noisy.

Small C: The penalty is low, allowing more margin violations. The optimizer prioritizes a wide margin over perfect classification. This produces a smoother, more regularized boundary — higher bias but lower variance, better for noisy or overlapping data.

In the limit as C → ∞, the soft margin SVM approaches the hard margin SVM. In practice, C is selected by cross-validation, typically searching over a logarithmic scale (e.g., 0.001, 0.01, 0.1, 1, 10, 100).

Feature Scaling is Essential

SVMs are sensitive to the scale of input features because the margin is measured in the original feature space. A feature with values in [0, 1000] will dominate the norm of w compared to a feature with values in [0, 1]. Always standardize features to zero mean and unit variance (or scale to [0, 1]) before training an SVM. This is one of the most common sources of poor SVM performance.

Strengths and Limitations

The maximum margin classifier has several compelling properties. It has strong theoretical foundations rooted in statistical learning theory — maximizing the margin directly minimizes an upper bound on generalization error. It is effective in high-dimensional spaces, which is why SVMs were state-of-the-art on text classification for many years. And the sparse representation using only support vectors makes prediction efficient.

However, the hard and soft margin SVM are limited to linearly separable problems (or nearly so). Many real-world problems require nonlinear boundaries — the classes may form clusters, spirals, or concentric rings that no hyperplane can separate. This limitation is addressed elegantly by the kernel trick, which we explore in the next lesson.

In the next lesson, we will see how the kernel trick allows SVMs to find nonlinear decision boundaries by implicitly mapping data to a higher-dimensional space — without ever computing the mapping explicitly.

Key Takeaways

The maximum margin classifier finds the hyperplane that maximizes the distance to the nearest points of each class.
The margin width is 2/‖w‖ — maximizing margin is equivalent to minimizing the norm of the weight vector.
Support vectors are the training points on the margin planes; only they determine the decision boundary.
Hard margin SVM requires linearly separable data; soft margin SVM allows violations via slack variables ξ_i.
The C parameter trades off margin width against training error: large C = narrow margin + fewer errors; small C = wide margin + some errors allowed.
Feature scaling is essential — SVMs are sensitive to the scale of input features.
The linear SVM is limited to linear boundaries; the kernel trick (next lesson) extends it to nonlinear problems.