Support Vector Machines

A support vector machine (SVM) is a binary classifier that draws a single hyperplane through feature space and positions that hyperplane as far as possible from the nearest training points of either class. This lesson covers, in order: the geometric intuition of a maximum-margin separator, the hinge loss that turns that geometric intuition into an optimisation problem, the kernel trick that lets SVMs draw curved boundaries without ever writing the curves down explicitly, the scaling requirement that makes the margin a meaningful number, and the practical comparison against logistic regression, decision trees and k-nearest neighbours. The lesson ends with a checklist for "is SVM the right pick for this problem".

Learning Objectives

1. Describe the maximum-margin hyperplane geometrically and explain why maximising the geometric margin improves generalisation rather than memorising the training set.
2. Derive hinge loss from the geometric margin and write the soft-margin SVM objective with a regularisation parameter $C$, then explain how $C$ trades margin width against misclassification tolerance.
3. State the kernel trick for SVMs: how a kernel $K(x_i, x_j)$ replaces an inner product in a higher-dimensional space, why the explicit feature map is never computed, and the role of the $\gamma$ parameter in the RBF kernel.
4. Explain why SVMs require feature scaling as a hard prerequisite and demonstrate the consequence of skipping it on a dataset with mixed-scale features.
5. Fit a linear SVM and an RBF-kernel SVM with scikit-learn, choose $C$ and $\gamma$ by cross-validation, and read the support vectors and dual coefficients from the fitted model.
6. Compare SVM against logistic regression, decision trees and kNN on five axes — margin, probability output, data needs, training cost, scaling requirement — and decide which algorithm is the right pick for a given problem.

1. Maximum Margin: The Geometric Intuition

Picture a feature space where every training example has been plotted as a single dot, coloured by class. When the two classes are linearly separable — there exists at least one straight hyperplane that puts every positive on one side and every negative on the other — infinitely many such hyperplanes exist. The SVM picks the one that maximises the margin, the perpendicular distance from the hyperplane to the nearest training points of either class.

   class -1 (negatives)                 class +1 (positives)
       o   o                                 +   +
         o                                     +   +
            \              |               /
             \             |              /
              \            |             /
               \           |            /
                \          |           /    <- margin band
                 \         |          /
                  \        |         /      width = 2 / ||w||
        ───────── \───────|──────── / ────── decision boundary
                  /        |        \
                 /         |         \
                /          |          \
               /           |           \
              /            |            \
        x   x           x   x

A prose figure description: imagine two clusters of points on a sheet of graph paper, the negatives on the left and the positives on the right. Many straight lines can separate them. The SVM draws the line that is farthest from both clusters at once, then thickens that line into a band by walking perpendicular distance $1/\|\mathbf{w}\|$ outward in each direction. The band stops touching the two clusters at the points that define its width — those touching points are the support vectors, and the width of the band is the margin. Every other training point sits comfortably inside its class region and plays no role in the solution.

The decision boundary is the hyperplane

and the margin boundaries are the two parallel hyperplanes

where the +1 side holds the support vectors of the positive class and the -1 side holds the support vectors of the negative class. The geometric margin is

Maximising the margin is equivalent to minimising $\|\mathbf{w}\|$ (or $\tfrac{1}{2}\|\mathbf{w}\|^2$, the standard squared form because its derivative is linear and friendly to quadratic programming).

Why does maximising the margin help generalisation? An intuitive answer: the wider the empty band around the decision boundary, the more "perturbation room" a new test point has before it crosses the boundary. A narrow-band classifier memorises the training points that happen to be close to the boundary; a wide-band classifier commits only to a boundary that many training points agree on, and is therefore less sensitive to small changes in the input. The classical result by Vapnik and Chervonenkis makes this precise: the generalisation error of an SVM is bounded above by a quantity that grows with the ratio of the margin to the radius of the enclosing ball around the data, and decreases as the margin grows.

2. From Geometry to Optimisation: Hinge Loss

The geometric statement "put the hyperplane as far as possible from the nearest training points" has to be turned into a formula that an optimiser can minimise. Encode the class labels as $y_i \in \{-1, +1\}$ rather than $\{0, 1\}$ — the $\{+1, -1\}$ convention turns the "positive side / negative side" decision into a single sign check, which makes the algebra cleaner. The classifier then predicts

For a correctly classified point on the correct side of its margin boundary, the quantity

is at least $1$. If the point is closer than the margin (but still correctly classified) the quantity is between $0$ and $1$; if it is misclassified or on the wrong side of the decision boundary, the quantity is negative. That observation drives the loss function.

The hinge loss for a single training point is

Three regimes in one line:

The hard-margin SVM optimisation problem is

which is a convex quadratic program with $n$ inequality constraints. The primal objective $\|\mathbf{w}\|^2$ rewards margin width; the constraints enforce that every point sits outside the margin band on its correct side.

The hinge loss is the unconstrained, soft-margin-friendly reformulation of the same idea. Add the hinge losses to the margin objective and you get

where the parameter $C > 0$ trades off margin width against tolerance for points that violate the margin. The next section unpacks $C$.

Why hinge loss and not, say, the logistic loss $-(y \log \hat{p} + (1-y)\log(1-\hat{p}))$ that logistic regression uses? Three reasons:

1. Hinge loss is zero beyond the margin, so moving a correctly classified point farther from the boundary does not change the objective. Logistic loss never quite reaches zero; it still penalises confident correct predictions by a vanishing amount. The SVM therefore commits only to a margin, not to specific probability values, which is why SVMs are not natural probabilistic classifiers.
2. Hinge loss is convex and has a subgradient, which makes the optimisation a quadratic program — globally solvable in polynomial time. Logistic loss is also convex but does not yield a quadratic program.
3. Hinge loss is the convex upper bound on the 0-1 misclassification loss, so minimising it is a principled surrogate for minimising the classification error rate itself.

3. Soft-Margin SVM and the Parameter C

Real data is rarely linearly separable. Two clouds of points with a mild overlap cannot be cut by any straight hyperplane without slicing through a few examples. The hard-margin SVM would either declare the problem infeasible or commit to an absurd boundary that zig-zags around individual points.

The soft-margin SVM relaxes the constraints by introducing slack variables $\xi_i \geq 0$, one per training point, that measure how far each point is allowed to penetrate the margin (or cross the boundary). The primal problem becomes

The hinge-loss objective of the previous section is the unconstrained version of this same problem — the $\xi_i$ and the hinge are two faces of the same coin.

The parameter $C$ is the regularisation knob, but with a sign that is easy to misremember. Small $C$ means "regularise heavily" — the objective is dominated by $\tfrac{1}{2}\|\mathbf{w}\|^2$, the margin is forced wide, and many points are allowed to violate the margin. Large $C$ means "fit the training data hard" — the objective cares more about the per-point hinge penalties, the margin shrinks to wrap closer around the training points, and few violations are tolerated.

A useful mental model: $1/C$ plays the role that $1/\lambda$ plays in ridge regression — a larger $C$ is less regularisation, a smaller $C$ is more.

Geometrically:

The standard practice is to pick $C$ by cross-validation on a log scale, typically $C \in \{10^{-3}, 10^{-2}, 10^{-1}, 1, 10, 10^2, 10^3\}$.

4. The Kernel Trick

A linear SVM can only draw straight hyperplanes. Many real classification problems — the classic XOR pattern, concentric rings, spiral arms — are not linearly separable in their original features. The textbook answer is to lift the inputs into a higher-dimensional feature space where they become separable, then fit a linear SVM there.

For example, the XOR problem in two dimensions is not linearly separable, but in three dimensions with the lifted features $(x_1, x_2, x_1 x_2)$ the four points are separable by a plane. The principle generalises: for almost any non-linear decision boundary in the original space, there exists a sufficiently high-dimensional space in which a linear separator exists.

The catch is that the lifted space can be enormous. The polynomial lift to degree $d$ of a $p$-dimensional input has $\binom{p+d}{d}$ features — for $p = 100$ and $d = 5$, that is more than 96 million features, and computing the lift explicitly is hopeless. The kernel trick sidesteps this cost entirely.

The SVM dual problem expresses the classifier as a weighted sum of training points,

where $K(\mathbf{x}_i, \mathbf{x})$ is a kernel function that replaces the inner product $\langle \mathbf{x}_i, \mathbf{x} \rangle$ of the lifted feature space. The crucial point: the formula never computes the lift $\phi(\mathbf{x})$ explicitly. It only needs the value of $K(\mathbf{x}_i, \mathbf{x}) = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}) \rangle$. A kernel function that can be evaluated cheaply on raw inputs is equivalent to a linear classifier in the lifted space, but with the cost of computing the lift replaced by the cost of evaluating the kernel.

Formally, a kernel is any symmetric positive semi-definite function $K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$. Mercer's theorem guarantees that for any such kernel there exists a feature map $\phi$ with $K(\mathbf{x}_i, \mathbf{x}_j) = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle$. The kernel trick lets you design $K$ first and let $\phi$ come along for free.

Three common kernels:

The next section unpacks the third row, which is the most widely used kernel in practice.

5. The RBF Kernel and Gamma

The radial basis function (RBF) kernel, also called the Gaussian kernel, is

where $\|\mathbf{x}_i - \mathbf{x}_j\|^2$ is the squared Euclidean distance between the two points and $\gamma > 0$ is a hyperparameter that controls the kernel's width.

Reading the formula top-to-bottom:

• When $\mathbf{x}_i = \mathbf{x}_j$ (distance $0$), $K = 1$ — a point is maximally similar to itself.
• As the distance grows, $K$ decays toward $0$. The rate of decay is controlled by $\gamma$.
• $\gamma$ is the inverse of a "characteristic length scale". A large $\gamma$ means a small effective length scale — only points very close together contribute, and the kernel has narrow bumps. A small $\gamma$ means a large length scale — distant points still contribute, and the kernel is wide and smooth.

The intuitive picture: the RBF kernel places a Gaussian bump centred at every training point and lets the decision boundary be a weighted sum of those bumps. The parameter $\gamma$ controls how wide each bump is. With $\gamma$ too small, the bumps are wide and the boundary is over-smoothed — the model underfits. With $\gamma$ too large, the bumps are narrow, every training point becomes its own island of influence, and the model memorises the training set. The right $\gamma$ is the one that lets the bumps cover the data at the scale of the true class boundary.

The RBF kernel corresponds to an infinite-dimensional feature map $\phi(\mathbf{x})$. Every monomial of every degree appears in the lift, with weights that decay with degree. The kernel evaluates this infinite-dimensional inner product in closed form using the identity

which is a Taylor expansion of the exponential in the squared distance. The point of the trick is that the right-hand side, an infinite sum of polynomial features, never has to be written down — the left-hand side is evaluated directly in $O(p)$ time on the raw inputs.

Two hyperparameters control an RBF-kernel SVM: $C$ from Section 3 and $\gamma$ from this section. The standard cross-validation grid for both is

typically with sklearn.model_selection.GridSearchCV and a small holdout set.

A worked intuition for $\gamma$: with $\gamma = 1/p$ (where $p$ is the number of features) the kernel's typical length scale matches the average feature distance; with $\gamma$ ten times larger the kernel becomes ten times more local; with $\gamma$ ten times smaller it becomes ten times more global.

6. Feature Scaling: A Hard Prerequisite

The margin $2/\|\mathbf{w}\|$ is a distance measured in the same units as the features. If one feature ranges in $[0, 1]$ and another in $[0, 10000]$, the margin is dominated by the large-scale feature: a one-unit change in the small feature is invisible against a ten-thousand-unit change in the large one, so the hyperplane ends up almost orthogonal to the small feature and almost parallel to the large one. The SVM still fits, but it fits a boundary that is meaningless in the original feature units and that generalises poorly.

The fix is standardisation: transform every feature to zero mean and unit variance,

where $\boldsymbol{\mu}$ is the per-feature mean and $\boldsymbol{\sigma}$ is the per-feature standard deviation, both estimated on the training set and then applied identically to the test set. Two practical caveats:

1. Compute $\boldsymbol{\mu}$ and $\boldsymbol{\sigma}$ on the training set only. Re-using test-set statistics is a leak.
2. Persist the scaler. The fitted StandardScaler has to be saved alongside the SVM and applied to every future input before prediction. A model file plus a separate scaler file is the usual pattern.

The same requirement applies to logistic regression, kNN, and any distance- or gradient-based learner that uses Euclidean geometry. SVM and kNN are the two algorithms where it is most load-bearing, because both depend on distances directly: SVMs through the margin, kNN through the neighbour search. Decision trees are immune — they only care about feature ordering, not about scale — which is one reason trees remain popular on raw, unscaled data.

A worked illustration. Take a dataset with one feature in $[0, 1]$ (an image-pixel intensity) and one in $[0, 10000]$ (a price in dollars). Fit a linear SVM without scaling: the coefficients come out $\mathbf{w} \approx (0.001, 0.0001)$, the hyperplane is effectively "ignore the pixel, use the price", and any new test point whose price falls outside the training range is misclassified. Standardise first: both features have unit variance, the SVM learns a sensible combination, and the test-set accuracy rises.

7. SVM vs Logistic Regression, Decision Trees and kNN

Choosing a classifier is mostly choosing a set of trade-offs. The four classifiers this course covers — logistic regression, decision trees, kNN, and SVM — differ along five axes that matter in practice.

A prose summary of the practical takeaways:

• Pick SVM when the dataset is medium-sized (a few thousand to tens of thousands of examples), the features are dense and continuous, and the classes are reasonably well separated so a margin is meaningful. Kernel SVMs are strong out-of-the-box for text and image problems and are often the second model to try after logistic regression.
• Pick logistic regression when you need a calibrated probability output (for ranking, threshold tuning, expected-value calculations) or when the dataset is large enough that the $O(n^2)$ cost of kernel SVM becomes painful. Logistic regression is also the natural baseline for any new classification problem.
• Pick a decision tree when interpretability matters more than raw accuracy, when the features are a mix of numerical and categorical with non-linear interactions, or when you cannot standardise the features. For raw accuracy on tabular data, prefer a random forest or gradient-boosted ensemble.
• Pick kNN when the data is small, the local structure of the feature space is genuinely meaningful, and you need a model that can be updated without retraining (just add the new example to the index). On anything larger than a few thousand points, kNN starts to suffer from the curse of dimensionality and from the cost of the nearest-neighbour search.

The scaling row of the table is worth re-reading. SVM and kNN are the two that require scaling — fit StandardScaler before either. Logistic regression benefits from scaling for stable gradient descent; trees do not care.

8. When SVM Is the Right Pick

The maximum-margin intuition only helps when the data is approximately separable. SVM is the right pick under the following conditions:

1. Binary classification with a clear margin. Spam-vs-ham, fraud- vs-legitimate, malignant-vs-benign — problems where the two classes form clusters with a thin gap between them. SVM excels because its objective is precisely "make that gap as wide as possible".
2. Medium-sized, dense, continuous features. Text classification with TF-IDF vectors, image features, sensor signals. SVM is less suited to one-hot encoded categorical data with thousands of sparse features — a linear model with L1 regularisation is usually faster and equally accurate there.
3. You can afford the $O(n^2 \text{–} n^3)$ training cost. For tens of thousands of examples the kernel SVM fits in minutes; for hundreds of thousands, switch to the linear SVM (LinearSVC / SGDClassifier(loss="hinge")) or to logistic regression with a sparse solver.
4. You do not need calibrated probabilities. SVM scores are signed distances from the margin and are not probabilities. For a probability output use CalibratedClassifierCV(SVC()), which wraps an SVM in a Platt-scaling logistic regression on its decision scores.

SVM is not the right pick when:

• The dataset is huge ($n > 100{,}000$) and the linear model suffices. Linear SVMs still scale, but logistic regression with a sparse solver is faster and gives calibrated probabilities for free.
• The problem is multi-class with many classes ($K > 10$). SVM is natively binary; multi-class is implemented as $K$ one-vs-rest classifiers, which is awkward. Logistic regression handles multi-class via softmax with no overhead.
• The relationship between features and label is highly non-linear with no obvious kernel. A tree-based ensemble or a neural network is more flexible.
• Interpretability of a single rule is required. Trees win on readability; SVM coefficients of an RBF model are not directly readable.

A useful pre-flight checklist before fitting an SVM:

1. Are the features continuous and roughly standardised?
2. Is $n$ in the range $[10^3, 10^5]$ (not too small, not too big)?
3. Is the binary class balance reasonable (no 99:1 imbalance)?
4. Is a probability output needed? If yes, plan for calibration.
5. Have I budgeted for hyperparameter search over $C$ (and $\gamma$ for RBF)?

If the answer to four or five of these is "yes", SVM is a strong candidate. If two or more are "no", reach for a different model first.

9. Worked Example with scikit-learn

A short, complete script that fits a linear SVM and an RBF-kernel SVM on a synthetic two-class dataset. The dataset is generated with make_classification so the example is reproducible.

import numpy as np
from sklearn.datasets import make_classification
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score

dataset = "synthetic: 800 examples, 8 features, 2 classes, no noise"
X, y = make_classification(
    n_samples=800, n_features=8, n_informative=5, n_redundant=1,
    random_state=0,
)
X_tr, X_te, y_tr, y_te = train_test_split(
    X, y, test_size=0.25, random_state=0, stratify=y,
)

pipe = Pipeline([
    ("scaler", StandardScaler()),   # hard prerequisite for SVM
    ("svm",    SVC(kernel="rbf")),  # RBF-kernel soft-margin SVM
])

param_grid = {
    "svm__C":     [1e-2, 1e-1, 1, 10, 100],
    "svm__gamma": [1e-3, 1e-2, 1e-1, 1],
}

search = GridSearchCV(pipe, param_grid, cv=5, scoring="accuracy", n_jobs=-1)
search.fit(X_tr, y_tr)

print("best params :", search.best_params_)
print("CV accuracy  :", search.best_score_)
print("test accuracy:", accuracy_score(y_te, search.predict(X_te)))

Typical output on this synthetic dataset:

best params : {'svm__C': 10, 'svm__gamma': 0.01}
CV accuracy  : 0.945
test accuracy: 0.955

The Pipeline is important for two reasons. First, the scaler is fit on each training fold inside GridSearchCV and applied to the matching validation fold — there is no leakage of test-set statistics. Second, when the fitted pipeline is saved with joblib, the scaler comes along and is applied automatically to every future input at prediction time.

A second snippet inspects the support vectors of the fitted model:

import numpy as np
from sklearn.svm import SVC
from sklearn.preprocessing import StandardScaler
from sklearn.datasets import make_classification

X, y = make_classification(n_samples=400, n_features=4, random_state=1)
X_std = StandardScaler().fit_transform(X)

clf = SVC(kernel="rbf", C=1.0, gamma=0.1).fit(X_std, y)

print(f"n support vectors per class : {clf.n_support_}")
print(f"total support vectors       : {clf.support_vectors_.shape[0]}")
print(f"dual coefficients (alpha*y) : "
      f"{np.round(clf.dual_coef_[0][:6], 3)} ...")

The output:

n support vectors per class : [32 28]
total support vectors       : 60
dual coefficients (alpha*y) : [-0.872  0.501 -0.443  0.610  0.215 -0.288] ...

60 of the 400 training points are support vectors — they alone define the boundary. The other 340 points could be deleted from the training set without changing the fitted model. The dual coefficients $\alpha_i y_i$ are the Lagrange multipliers of the dual problem; their sum equals the bias-free portion of the decision function and a non-zero $\alpha_i$ marks that point as a support vector.

A third snippet shows the linear SVM, which is the right starting point for high-dimensional problems:

from sklearn.svm import LinearSVC
from sklearn.datasets import load_iris

X, y = load_iris(return_X_y=True)
clf = LinearSVC(C=1.0, dual=True, max_iter=5000, random_state=0).fit(X, y)

print("coefficients shape :", clf.coef_.shape)   # (3 classes, 4 features)
print("classes            :", clf.classes_)      # ['setosa' 'versicolor' 'virginica']
print("intercept          :", clf.intercept_)

LinearSVC is implemented in liblinear rather than libsvm and scales roughly linearly with $n$, which is why it is the right choice for text-classification and other large, sparse problems. It does not support kernels and does not expose support vectors — those are features of the kernel SVM in the first snippet.

Key Takeaways

• The maximum-margin intuition places the separating hyperplane as far as possible from the nearest training points of either class. The margin is $2/\|\mathbf{w}\|$, and maximising it is equivalent to minimising $\tfrac{1}{2}\|\mathbf{w}\|^2$.
• Hinge loss $\ell = \max(0, 1 - y(\mathbf{w}^\top \mathbf{x} + b))$ is the unconstrained reformulation of the margin constraint. It is zero beyond the margin, grows linearly inside the margin, and is the convex upper bound on the 0-1 misclassification loss. Soft-margin SVM adds a penalty $C \sum \xi_i$ that trades margin width against tolerance for margin violations.
• The kernel trick replaces the inner product of an (often infinite-dimensional) feature space with a kernel function $K(\mathbf{x}_i, \mathbf{x}_j)$ that can be evaluated on the raw inputs. The lift $\phi(\mathbf{x})$ is never computed; only the kernel value matters. This is what makes non-linear SVMs feasible.
• The RBF kernel $K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma\|\mathbf{x}_i - \mathbf{x}_j\|^2)$ corresponds to an infinite-dimensional polynomial lift. The parameter $\gamma$ controls the kernel's length scale: small $\gamma$ gives a wide, smooth kernel (underfitting risk); large $\gamma$ gives a narrow, local kernel (overfitting risk).
• Feature scaling is a hard prerequisite for SVM. Standardise every feature to zero mean and unit variance before fitting, fit the scaler on training data only, and persist it alongside the model for use at prediction time. SVM and kNN are the two classifiers where scaling is most load-bearing.
• Across the four classifiers covered in this course, SVM is the right pick for medium-sized, dense, continuous binary problems where a margin is meaningful and probability output is not. Logistic regression is the right pick when probabilities matter. Decision trees are the right pick when interpretability matters. kNN is the right pick when the local structure of feature space is meaningful and the dataset is small.