Support Vector Max-Margin Classifiers

Two classes of sensor readings are cleanly separated, and the interviewer draws them on a whiteboard with infinitely many lines that split the classes, then asks: which line do you pick, and prove it? Decision trees and logistic regression each have an answer about loss; the support vector machine's answer is geometric: pick the separating hyperplane that is farthest from the nearest data points of each class — the maximum-margin boundary.

Set it up precisely. A hyperplane in d dimensions is {x : w·x + b = 0} with weight vector w and bias b. The signed distance of any point from it is (w·x + b) / ‖w‖, positive on one side, negative on the other. Labels y ∈ {−1, +1} encode the sides. Because scaling (w, b) by a constant describes the same plane, we are free to rescale so that the closest points satisfy |w·x + b| = 1 — those points then sit at functional margin 1, at true distance 1/‖w‖ from the plane. The street width between the two class faces is therefore:

margin width = 2 / ‖w‖        (with all points satisfying yᵢ(w·xᵢ + b) ≥ 1)

Maximizing the margin is minimizing ‖w‖ — and the standard quadratic-programming form keeps the algebra friendly by squaring it:

minimize    ½‖w‖²
subject to  yᵢ(w·xᵢ + b) ≥ 1    for every training row i

A convex quadratic program with linear constraints: unique optimum (up to the w, b parameterization), solvable by dedicated algorithms — no local minima to argue about, which is itself an interview talking point versus neural networks.

Work a 2D example to make the margin a number rather than a slogan. Positives: (2, 1) and (1, 2). Negatives: (0, 1) and (1, 0). Consider w = (1, 1), b = −2, i.e. the plane x₁ + x₂ − 2 = 0:

(2,1): w·x + b = 1   → y=+1, functional margin 1  ✓
(1,2): w·x + b = 1   → y=+1, functional margin 1  ✓
(0,1): w·x + b = −1  → y=−1, y(w·x+b) = 1        ✓
(1,0): w·x + b = −1  → y=−1, y(w·x+b) = 1        ✓

margin = 2 / ‖(1,1)‖ = 2 / 1.414 ≈ 1.41

import numpy as np
X = np.array([[2, 1], [1, 2], [0, 1], [1, 0]])
y = np.array([1, 1, -1, -1])
w, b = np.array([1.0, 1.0]), -2.0
functional = y * (X @ w + b)          # [1, 1, 1, 1] — all constraints tight
margin = 2 / np.linalg.norm(w)        # 1.414
assert np.all(functional >= 1)

Every one of those four points sits exactly on a constraint boundary — they are the support vectors, the entire data-dependent content of the model. Delete any point outside the margin and the optimum does not move at all; move a support vector and the boundary shifts. That sparsity is why SVMs compare to k-Nearest Neighbors Classification from the opposite direction: kNN needs every row at serving time, the SVM needs only its support vectors.

Why should you prefer maximum margin over, say, logistic regression's maximum likelihood? Two defensible answers. First, geometric robustness: among infinitely many separators, the one maximizing distance to its nearest observations tolerates the most perturbation — a small measurement shift or a slightly different sample is less likely to flip a point across a wide street. Second, statistical intuition: in classical margin-based learning theory, generalization bounds scale inversely with the margin, so a wider margin behaves like a simpler model even when the weight vector lives in a high-dimensional space. Say "the margin acts as a capacity control" rather than quoting theorems you cannot finish.

All of the above assumes the classes are perfectly separable. Real data is not, and the next question in the interview room is what happens when a point crosses the line.

A single mislabeled outlier sits deep in the other class's territory. Under the hard-margin formulation you wrote — yᵢ(w·xᵢ + b) ≥ 1 — that row makes the problem infeasible: no solution exists, or if the outlier is merely inside the margin but not mislabeled, the optimizer contorts the boundary to satisfy it and the margin narrows to a ribbon. Soft margin is the release valve, and its one parameter, C, is the most-asked SVM hyperparameter in interviews.

Introduce a slack variable ξᵢ ≥ 0 for every row: how much that row is allowed to violate its constraint, measured in margin units:

minimize    ½‖w‖² + C · Σᵢ ξᵢ
subject to  yᵢ(w·xᵢ + b) ≥ 1 − ξᵢ ,   ξᵢ ≥ 0

The two terms are in direct conflict: ½‖w‖² wants a wide street (small w), C·Σξᵢ wants no violations. C sets the exchange rate between width and obedience. Rewrite the slack out and the objective becomes regularized hinge loss, which is how SVMs connect to the rest of the loss-function world:

minimize    ½‖w‖² + C · Σᵢ max(0, 1 − yᵢ·f(xᵢ))     where f(x) = w·x + b

Read the hinge max(0, 1 − y·f) term point by point — a row's contribution depends only on where it sits relative to the margin:

That first row is the structural difference from logistic regression: log-loss keeps pushing every point forever, however confidently it is classified; hinge loss switches off completely outside the margin. The switch-off is why SVM solutions are sparse — points that contribute nothing to the objective are, precisely, non-support vectors (α = 0 in the dual, next chapter).

Choosing C, concretely:

from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

pipe = Pipeline([
    ("scale", StandardScaler()),   # mandatory: the margin is measured in feature units
    ("svm", SVC(C=1.0, kernel="linear", class_weight="balanced")),
])
pipe.fit(X_train, y_train)
print(pipe.named_steps["svm"].n_support_)   # vectors per class pinning the boundary

Two practical notes. Scaling is not optional for SVMs — the margin 2/‖w‖ is computed in raw feature coordinates, so an income-in-dollars feature reweights the geometry exactly as it did for distance metrics (Distance and Similarity Metrics made the same argument for kNN); this is the most common real-world SVM bug. And for imbalanced classes, class_weight='balanced' scales each row's contribution inversely to class frequency — equivalently, it applies a different effective C per class — because with 99% negatives the optimizer happily buys a narrow margin around the majority.

You have now specified the primal problem completely. The form that makes SVMs fast, sparse, and extensible to kernels is the one you get by writing down its Lagrangian.

Interviewers ask "explain the SVM dual" not because they want Lagrangian calculus on the spot, but because the dual explains three properties you already observed — sparsity, prediction cost, and the kernel trick — in a single line each. Here is the route, compactly.

Attach a multiplier αᵢ ≥ 0 to each constraint and write the Lagrangian:

L(w, b, α) = ½‖w‖² + Σᵢ αᵢ (1 − yᵢ(w·xᵢ + b))

Optimize by setting derivatives to zero — stationarity conditions:

∂L/∂w = 0  →  w = Σᵢ αᵢ yᵢ xᵢ          (the model IS a weighted sum of training rows)
∂L/∂b = 0  →  Σᵢ αᵢ yᵢ = 0             (class-balance constraint on the weights)

Substituting back into L and canceling the w terms leaves the dual problem — maximize over α:

maximize    Σᵢ αᵢ − ½ Σᵢ Σⱼ αᵢ αⱼ yᵢ yⱼ (xᵢ · xⱼ)
subject to  0 ≤ αᵢ ≤ C   and   Σᵢ αᵢ yᵢ = 0

(αᵢ ≤ C appears only in the soft-margin version — the hard margin has no upper bound — a box constraint. KKT conditions then classify every row):

Three consequences follow immediately, and each is a good interview answer on its own. Sparsity: since w = Σ αᵢ yᵢ xᵢ, only support vectors are in the sum — prediction is f(x) = Σ_{SV} αᵢ yᵢ (xᵢ·x) + b, costing O(#SV·d) per query instead of kNN's O(n·d). You can verify this experimentally: refit on only the support vectors and the decision function is unchanged to numerical precision.

from sklearn.svm import SVC
import numpy as np

svc = SVC(C=1.0, kernel="linear").fit(X_train, y_train)
sv = svc.support_                       # indices of rows with alpha > 0
print(f"{len(sv)} of {len(X_train)} rows are support vectors")

svc_sv = SVC(C=1.0, kernel="linear").fit(X_train[sv], y_train[sv])
print(np.allclose(svc.decision_function(X_test),
                  svc_sv.decision_function(X_test)))   # True — same boundary

Scalability: the dual is a quadratic program whose size tracks n, with the kernel/inner-product matrix costing O(n²) memory and solvers like SMO running around O(n²)–O(n³) — so SVMs get uncomfortable around tens of thousands to low millions of rows, and teams with more data reach for a linear SGD hinge model or gradient boosting instead. The kernel trick: notice the data enters the dual only as inner products xᵢ·xⱼ, and predictions only as xᵢ·x. Replace that inner product with any valid kernel function K(xᵢ, xⱼ) and the solution implicitly operates in a far higher-dimensional feature space without ever computing a coordinate there. That substitution — where non-linear boundaries come from, and why kernel='rbf' suddenly carves circles — is the whole subject of The Kernel Trick in SVMs, the next topic in this phase.

The complete through-line for the interview: max-margin geometry gives the objective (½‖w‖² with constraints), soft margin makes it feasible on real data (C = exchange rate between width and violations), and the dual reveals the model as a sparse weighted sum of support vectors — cheap to evaluate, elegant to derive, and one substitution away from unlimited non-linearity.