Support Vector Machines Deep Dive - Maximizing the Margin

A Support Vector Machine classifies data by finding the hyperplane that separates two classes with the widest possible margin—not just any boundary that separates the classes, but the one farthest from the nearest points of either class.

many valid separating lines exist -> SVM picks the one maximizing distance to nearest points

The Margin and Support Vectors

For linearly separable data, the decision boundary is w·x + b = 0, and the margin width is 2/||w||. Maximizing the margin is equivalent to minimizing ||w|| subject to every point being correctly classified with some buffer:

$$\min_{w,b} \frac{1}{2}|w|^2 \quad \text{subject to} \quad y_i(w \cdot x_i + b) \geq 1 ;; \forall i$$

Only the points lying exactly on the margin boundary—the support vectors—determine the final decision boundary. Every other point could be removed from the training set without changing the result, which is why SVMs can be memory-efficient at prediction time relative to their training set size.

Soft Margins

Real data is rarely perfectly separable. The soft-margin SVM introduces slack variables ξ_i that allow some points to violate the margin, penalized by a regularization parameter C:

$$\min_{w,b,\xi} \frac{1}{2}|w|^2 + C\sum_i \xi_i$$

A small C tolerates more margin violations for a wider, more generalizable margin; a large C fits the training data more tightly at the risk of overfitting.

The Kernel Trick

Many real datasets aren’t linearly separable in their original feature space. Rather than explicitly transforming data into a higher-dimensional space where it might become separable, SVMs use a kernel function to compute the effect of that transformation implicitly:

$$K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)$$

Common kernels include the polynomial kernel and the RBF (Gaussian) kernel. Because the optimization only ever needs dot products between points—never the transformed points themselves—the kernel trick lets SVMs fit highly nonlinear boundaries without ever explicitly computing the (potentially infinite-dimensional) transformed features.

Practical Considerations

SVMs work well on small to medium datasets with clear margins and high-dimensional feature spaces (like text classification with bag-of-words features), but they scale poorly to very large datasets since training complexity grows faster than linearly with the number of samples, and they don’t naturally output calibrated probabilities without an additional calibration step (like Platt scaling).