Support vector machines (SVM)

Many lines can separate two classes. An SVM chooses the one that lies furthest from both — the one with the largest margin.

Only the points lying exactly on the edge of the margin affect the solution. They are called support vectors, and the rest of the data can be removed without the model changing. That is unusual among ML methods and makes SVMs robust against points far from the boundary.

A soft margin: real data is rarely perfectly separable. The parameter C governs the trade-off — a small C allows more misclassifications for a wider margin, a large C prioritises classifying everything correctly (and risks overfitting).

The primal problem (soft margin): $\min_{w,b,\xi}\ \tfrac12\|w\|^2 + C\sum_i \xi_i \quad\text{s.t.}\quad y_i(w^\top x_i + b)\ge 1-\xi_i,\ \xi_i\ge 0$

The width of the margin is $2/\|w\|$, so minimising $\|w\|^2$ is maximising the margin. The problem is convex — one global optimum, no local traps, a deterministic result.

The dual form contains the data only through the dot products $x_i^\top x_j$. That opens the way to the kernel trick: replace the dot product with a kernel function $K(x_i,x_j)$ corresponding to a dot product in a higher-dimensional space — without ever computing the coordinates there.

Kernel	$K(x,z)$	Effect
Linear	$x^\top z$	a straight boundary
Polynomial	$(\gamma x^\top z + r)^d$	a polynomial boundary
RBF	$\exp(-\gamma\|x-z\|^2)$	an infinite-dimensional space, very flexible

When an SVM is the right choice today: small to medium datasets (< ~50 000 examples), high dimensions relative to the number of examples (text with TF-IDF), and when determinism and theoretical guarantees are valued. When it is not: large datasets (the training scales roughly $O(n^2)$–$O(n^3)$), and when probabilities are needed (an SVM gives distances, not calibrated probabilities — Platt scaling is required).

import numpy as np
from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline
from sklearn.model_selection import GridSearchCV

# Scaling is COMPULSORY for an SVM — distance is the core of the method
pipe = make_pipeline(StandardScaler(), SVC(kernel="rbf"))
search = GridSearchCV(pipe, {"svc__C": [0.1, 1, 10, 100],
                             "svc__gamma": ["scale", 0.01, 0.1, 1]},
                      cv=5, scoring="f1_macro", n_jobs=-1).fit(X_tr, y_tr)
print(search.best_params_, round(search.best_score_, 3))

model = search.best_estimator_
svc = model[-1]
print("support vectors:", svc.n_support_, "out of", len(X_tr))
# support vectors: [43 39] out of 800   ← only 10 % of the data defines the boundary

C and gamma belong together: a large C and a large gamma almost always give overfitting (the boundary winds itself around every point). Search them together in a grid, never separately.