Definition
A support vector machine (SVM) is a classifier that separates two classes with the hyperplane of maximum margin — the widest possible empty band between the classes. The band is pinned by a few training points on its edge, the support vectors; every other point could be deleted without changing the model. With a kernel, the same optimization runs in a high-dimensional feature space, which gives curved boundaries in the original one.
At a glance
- Task
- Binary classification, labels ; multi-class via one-vs-one or one-vs-rest. (Regression is the sibling article Support vector regression.)
- Input → output
- → class , where is a signed score, not a probability
- Learns
- a normal vector and offset ; in kernel form, one weight per training point — nonzero only for support vectors
- Loss
- hinge loss plus an penalty
- Training
- a convex quadratic program — one global optimum. Kernel SMO: roughly – time, kernel memory; linear SVMs: about per pass
- Prediction
- for a linear SVM; with a kernel
- Hyperparameters
- (violations vs margin width), the kernel, and its parameters — RBF , polynomial degree
- Assumes
- features on comparable scales; classes separable, up to a few violations, in the chosen feature space
The problem
When two classes can be separated by a line, they can usually be separated by infinitely many lines. The Perceptron stops at the first one that makes no training mistakes — wherever its updates happened to leave it. Logistic regression on separable data has no finite optimum at all: its weights grow without bound. Neither method prefers a line that leaves room for error.
Yet the choice matters. A boundary that grazes a training point will misclassify a test point that differs from it only slightly. Intuitively the safest line sits in the middle of the gap, as far from both classes as it can be. The SVM makes that intuition the objective, and it turns out to be a convex problem with a unique answer that depends on only a handful of points.
The idea
Picture the widest street you can lay between the two classes, with no point on the road. The decision boundary is the centre line. The kerbs touch a few points from each side; those points hold the street in place. Push any other point around — as long as it stays off the road — and nothing changes.
Two refinements make this practical. Real data overlaps, so we let some points stand on the road or even across it, but charge for each one; is the price. And when no straight street works, we lay a straight street in a richer feature space instead. The kernel trick lets us do that without ever building the features.
Vocabulary
- Hyperplane
- the set — a line in 2-D. is perpendicular to it; shifts it.
- Decision value
- . Its sign is the class; is the distance to the hyperplane.
- Functional margin
- — positive when point is classified correctly, and at least 1 when it is outside the street.
- Margin (street width)
- the distance between the two kerbs and , equal to .
- Support vector
- a training point with : either exactly on a kerb () or a violator inside the street or on the wrong side.
- Slack ξᵢ
- how far point falls short of the kerb, in units of : . means misclassified.
- Hinge loss
- — zero for points safely outside the street, linear inside it.
- Dual weight αᵢ
- the Lagrange multiplier of point 's constraint; how hard that point pushes on the boundary.
- Kernel / Gram matrix
- , a dot product in a feature space; for all pairs of training points.
The math
Distance to a hyperplane. Take any point and drop a perpendicular to the hyperplane; it travels along the unit normal . Solving for gives
- normal vector of the hyperplane (the weights)
- offset (bias)
- Euclidean length
Fix the scale. Multiplying and by any describes the same hyperplane, so we are free to choose . Pick it so the closest points have . Then the kerbs are the lines , each at distance from the centre, and the street is wide. Maximizing is the same as minimizing (the square and the ½ just make the calculus clean):
- label of point , or
- every point is on its own side, on or beyond its kerb
This is the hard-margin primal: a convex quadratic objective with linear constraints, so any local optimum is the global one.
From primal to dual
Attach a multiplier to each constraint and form the Lagrangian:
- Lagrange multiplier (dual weight) of point i, ≥ 0
Set the derivatives with respect to the primal variables to zero. and , so
The weight vector is a weighted sum of training points. Substituting it back into eliminates and and leaves a problem in alone:
- dot product of two training points — the only way the data appears
Who becomes a support vector? At the optimum the KKT condition of complementary slackness holds: for every . So either (the point plays no role in ) or (the point sits exactly on a kerb). That is the precise sense in which only support vectors matter. Once is known, any support vector gives the offset: .
Soft margin and the role of C
If the classes overlap, the hard constraints cannot all hold. Give each point a slack and pay per unit of slack:
- slack: outside the street, inside it, misclassified
- price of one unit of slack; large C → few violations, narrow street
For fixed the best slack is the smallest allowed, . Substituting it gives the unconstrained hinge-loss form, which is just a regularized loss like every other model in this course:
Repeating the Lagrangian derivation changes exactly one thing in the dual: the multipliers get a ceiling, . That box constraint is how acts mathematically. Each point falls into one of three cases:
| Dual weight | Position | Slack | Effect on the boundary |
|---|---|---|---|
| outside the street, | 0 | none — moving it (outside the street) changes nothing | |
| exactly on a kerb, | 0 | a free support vector; pins the street; used to compute b | |
| inside the street or misclassified, | a bound support vector; pushes as hard as allows |
Read as a cap on each point's influence. When exceeds the largest of the hard-margin solution, the cap never binds and you get the hard-margin SVM exactly. Below that value, the most demanding points hit the cap, stop pushing, and the street widens until more points share the load. As every point ends up at and shrinks toward 0. The hinge form shows the same thing from the other side: multiplies the loss, so it is the inverse of a ridge penalty, with if you average the loss over the points.
Worked example: ten points by hand
Ten points in the plane, five per class. They are linearly separable, so we look for the hard-margin solution (any gives the same answer, as we will see).
| # | x₁ | x₂ | y |
|---|---|---|---|
| 1 | 1 | 2 | −1 |
| 2 | 2 | 1 | −1 |
| 3 | 2 | 3 | −1 |
| 4 | 1 | 4 | −1 |
| 5 | 3 | 1 | −1 |
| 6 | 6 | 6 | +1 |
| 7 | 5 | 3 | +1 |
| 8 | 5 | 5 | +1 |
| 9 | 6 | 4 | +1 |
| 10 | 4 | 6 | +1 |
Solving the SVM by hand
- 1Guess the support vectors. The street must run between the two clouds, so the points facing the gap are the candidates: #3 and #5 on the side, #7 on the side. Assume all three lie on their kerbs.
- 2Kerb equations : #3 gives ; #5 gives ; #7 gives .
- 3Solve. Subtract #3 from #7: , so . Subtract #3 from #5: , so . Then . So .
- 4Check feasibility. Every other point must have . The table below confirms it: the smallest value among non-support vectors is (points #4 and #10).
- 5Recover the dual weights from and : ; the component gives , so ; the component gives , so ; hence . All three are positive, so every KKT condition holds and this is the optimum.
- 6Margin. , so the street is wide. Check: , which is a known identity at the hard-margin optimum. The dual objective is , equal to the primal .
- 7Classify a new point . Primal: . Dual, using only dot products with the support vectors, , , : . Positive → class +1. Because , falls inside the street, at distance from the boundary.
| # | y | f(x) | y · f(x) | Distance | Dual weight |
|---|---|---|---|---|---|
| 1 | −1 | −2 | 2 | 2.683 | 0 |
| 2 | −1 | −5/3 | 5/3 | 2.236 | 0 |
| 3 | −1 | −1 | 1 | 1.342 | 1/9 = 0.111 |
| 4 | −1 | −4/3 | 4/3 | 1.789 | 0 |
| 5 | −1 | −1 | 1 | 1.342 | 1/6 = 0.167 |
| 6 | +1 | 8/3 | 8/3 | 3.578 | 0 |
| 7 | +1 | 1 | 1 | 1.342 | 5/18 = 0.278 |
| 8 | +1 | 5/3 | 5/3 | 2.236 | 0 |
| 9 | +1 | 2 | 2 | 2.683 | 0 |
| 10 | +1 | 4/3 | 4/3 | 1.789 | 0 |
The largest dual weight is . That is why every returns this same solution: the ceiling never binds.
Effect of C on the example
Even though these points are separable, a small deliberately lets points into the street to buy a wider one. Here is the exact soft-margin optimum for several values of :
| C | w, b | Margin | Support vectors | In street | Total slack | f(4, 3) |
|---|---|---|---|---|---|---|
| ≥ 0.278 | (0.667, 0.333), −3.333 | 2.683 | 3, 5, 7 | 0 | 0 | 0.333 |
| 0.2 | (0.571, 0.286), −3.000 | 3.130 | 3, 5, 7, 10 | 1 | 0.286 | 0.143 |
| 0.1 | (0.462, 0.308), −2.692 | 3.606 | 3, 4, 5, 7, 10 | 2 | 0.615 | 0.077 |
| 0.03 | (0.320, 0.240), −1.880 | 5.000 | 2, 3, 4, 5, 7, 8, 9, 10 | 6 | 2.000 | 0.120 |
| 0.01 | (0.170, 0.130), −1.115 | 9.345 | all 10, all capped | 10 | 5.420 | −0.045 |
At the street is wider than the data cloud, so every point is inside it. The boundary then depends on all points almost equally, and the query flips to the side. This is the underfitting end of the scale.
The kernel trick
Look at the dual again: the data enter only through dot products , and the prediction is . Map every point to features and the dot products become . A kernel computes that number directly from and , without ever forming :
- kernel: similarity of to support vector , equal to
- RBF width parameter; the bump around each support vector has radius ≈ 1/√γ
- the support vectors — only they have
With the RBF (Gaussian) kernel, is a sum of Gaussian bumps centred on the support vectors, signed by class, plus . Its feature space is infinite-dimensional, yet each kernel value costs . Each hyperparameter has a clear effect on that sum:
How γ and C shape an RBF SVM
- γ small
- wide bumps: , so is smooth and close to a low-degree polynomial. Risk: underfitting.
- γ large
- narrow bumps: for , , and every point becomes its own island. away from the data. Training accuracy hits 100%: overfitting.
- C small
- αᵢ are capped low, so many points share the work → smooth boundary, many support vectors
- C large
- few violations tolerated → the boundary bends to fit individual points
- Together
- and interact: a large needs a smaller and vice versa. Search them jointly on a log grid.
1D input: A sits between two groups of B — no single threshold separates them.
| Kernel | k(x, x′) | Feature space | Parameters |
|---|---|---|---|
| Linear | the inputs themselves | C only | |
| Polynomial | all monomials up to degree | , , , C | |
| RBF (Gaussian) | infinite-dimensional | , C | |
| Sigmoid | not always PSD — rarely a good choice | , , C |
The algorithm, step by step
Kernel SVMs are trained by Sequential Minimal Optimization (SMO, Platt 1998), the algorithm inside libsvm and scikit-learn's SVC. Because , you cannot change one alone, but you can change two: moving by and by keeps the sum fixed. Along that direction the dual is a one-dimensional parabola, so its optimum has a closed form.
SMO (maximal-violating-pair version)
- 1Initialize and the dual gradient . Precompute or cache the kernel matrix .
- 2Select a pair. Among points whose may still move up, take ; among those that may move down, take . This is the pair that violates the KKT conditions most.
- 3Stop if the gap : all KKT conditions hold to tolerance .
- 4Step. The curvature along the pair is , so the unconstrained step is . Clip so that both and stay in .
- 5Update , , and the gradient , which costs .
- 6Finish. Set to the average of over free support vectors (). The model keeps only the points with .
On the worked example this loop converges in 35 pair updates. Complexity: each iteration is given kernel columns, and the number of iterations grows superlinearly with . In practice that means roughly – time, plus the memory for the kernel matrix (libsvm caches the columns it uses). This is why kernel SVMs are rarely used beyond about rows. Linear SVMs skip the kernel entirely and solve the primal or dual by coordinate descent (liblinear) in about per pass, which scales to millions of sparse rows.
The same objective can also be minimized directly in its hinge-loss form by (sub)gradient descent, as SGDClassifier(loss="hinge") does. The step-through below shows that view: only points with margin below 1 contribute a gradient.
- 1w ← 0, b ← 0
- 2repeat:
- 3 V ← {i : yᵢ(w·xᵢ + b) < 1}
- 4 w ← w − η(λw − (1/n)Σᵥ yᵢxᵢ)
- 5 b ← b + η(1/n)Σᵥ yᵢ
- 6until V stops changing
- 7SVs: yᵢ(w·xᵢ + b) = 1
Start with w = 0, b = 0: there is no boundary yet and every margin yᵢ(w·xᵢ+b) equals 0.
Variants and practical tuning
Choosing an implementation
- SVC (libsvm)
- kernel SVM by SMO; any kernel; multi-class by one-vs-one (K(K−1)/2 binary SVMs). Best up to tens of thousands of rows.
- LinearSVC (liblinear)
- linear kernel only, coordinate descent, one-vs-rest; squared hinge by default. Fast on large sparse data such as text.
- SGDClassifier(loss='hinge')
- linear SVM by stochastic gradient descent; streams data, supports
partial_fit. - ν-SVM (NuSVC)
- replaces with : an upper bound on the fraction of margin errors and a lower bound on the fraction of support vectors.
- Kernel approximation
- Random Fourier features (
RBFSampler) or Nyström map data to a few hundred explicit features, then a linear SVM. This gives near-RBF accuracy at linear cost. - Relatives
- Support vector regression uses an ε-insensitive tube instead of a street; One-class SVM draws a boundary around a single class for novelty detection.
Tuning recipe
- 1. Scale
- standardize every feature (fit the scaler on the training fold only).
- 2. Start
- RBF with and
gamma="scale", i.e. . - 3. Grid
- search × on a log scale, with cross-validation.
- 4. Imbalance
class_weight="balanced"scales per class, , so the minority class's violations cost more.- 5. Diagnose
- a support vector fraction near 100% suggests C too small or γ too large; very few SVs with poor validation accuracy suggests underfitting with a linear kernel.
In code
1import numpy as np23def kernel(A, B, kind="linear", gamma=0.5):4 if kind == "linear":5 return A @ B.T6 d2 = ((A[:, None, :] - B[None, :, :]) ** 2).sum(-1)7 return np.exp(-gamma * d2)89def fit_svm(X, y, C=1.0, kind="linear", gamma=0.5, eps=1e-6, max_iter=10000):10 """Dual SVM by SMO with maximal-violating-pair selection (as in libsvm)."""11 n = len(y)12 K = kernel(X, X, kind, gamma)13 a = np.zeros(n)14 G = -np.ones(n) # gradient of the dual: Q a - 115 for _ in range(max_iter):16 up = ((y > 0) & (a < C)) | ((y < 0) & (a > 0)) # alpha may move "up"17 low = ((y > 0) & (a > 0)) | ((y < 0) & (a < C))18 s = -y * G19 i = np.where(up)[0][np.argmax(s[up])]20 j = np.where(low)[0][np.argmin(s[low])]21 gap = s[i] - s[j]22 if gap < eps: # KKT conditions hold23 break24 curv = max(K[i, i] + K[j, j] - 2 * K[i, j], 1e-12)25 t = gap / curv # unconstrained optimum26 t = min(t, C - a[i] if y[i] > 0 else a[i]) # keep 0 <= a <= C27 t = min(t, a[j] if y[j] > 0 else C - a[j])28 a[i] += y[i] * t29 a[j] -= y[j] * t30 G += t * y * (K[:, i] - K[:, j])31 free = (a > 1e-8) & (a < C - 1e-8)32 b = np.mean(-y[free] * G[free]) if free.any() else (s[i] + s[j]) / 233 return a, b3435def decision(X_train, y, a, b, Xq, kind="linear", gamma=0.5):36 return kernel(Xq, X_train, kind, gamma) @ (a * y) + b3738X = np.array([[1, 2], [2, 1], [2, 3], [1, 4], [3, 1],39 [6, 6], [5, 3], [5, 5], [6, 4], [4, 6]], float)40y = np.array([-1, -1, -1, -1, -1, 1, 1, 1, 1, 1], float)4142a, b = fit_svm(X, y, C=10)43w = (a * y) @ X44print("alpha =", a.round(4))45print("support vectors:", np.where(a > 1e-6)[0] + 1)46print("w =", w.round(4), " b =", round(b, 4), " margin =", round(2 / np.linalg.norm(w), 4))47print("y*f(x) =", (y * decision(X, y, a, b, X)).round(3))48print("f(4,3) =", decision(X, y, a, b, np.array([[4.0, 3.0]])).round(4))4950# alpha = [0. 0. 0.1111 0. 0.1667 0. 0.2778 0. 0. 0. ]51# support vectors: [3 5 7]52# w = [0.6667 0.3333] b = -3.3333 margin = 2.683353# y*f(x) = [2. 1.667 1. 1.333 1. 2.667 1. 1.667 2. 1.333]54# f(4,3) = [0.3333]1import numpy as np2from sklearn.svm import SVC34X = np.array([[1, 2], [2, 1], [2, 3], [1, 4], [3, 1],5 [6, 6], [5, 3], [5, 5], [6, 4], [4, 6]], float)6y = np.array([-1, -1, -1, -1, -1, 1, 1, 1, 1, 1])78svm = SVC(kernel="linear", C=10, tol=1e-8).fit(X, y)9w, b = svm.coef_[0], svm.intercept_[0]10print("support vectors:", svm.support_ + 1) # 1-based point numbers11print("alpha_i * y_i: ", svm.dual_coef_[0].round(4))12print("w =", w.round(4), " b =", round(b, 4))13print("margin width =", round(2 / np.linalg.norm(w), 4))14print("f(4,3) =", svm.decision_function([[4, 3]]).round(4), "->", svm.predict([[4, 3]]))1516for C in [0.2, 0.1, 0.03]:17 m = SVC(kernel="linear", C=C, tol=1e-8).fit(X, y)18 print(f"C={C}: {len(m.support_)} SVs, margin {2 / np.linalg.norm(m.coef_):.3f}")1920rbf = SVC(kernel="rbf", C=10, gamma=0.3, tol=1e-8).fit(X, y)21print("RBF gamma=0.3:", len(rbf.support_), "SVs, f(4,3) =", rbf.decision_function([[4, 3]]).round(4))2223# support vectors: [3 5 7]24# alpha_i * y_i: [-0.1111 -0.1667 0.2778]25# w = [0.6667 0.3333] b = -3.333326# margin width = 2.683327# f(4,3) = [0.3333] -> [1]28# C=0.2: 4 SVs, margin 3.13029# C=0.1: 5 SVs, margin 3.60630# C=0.03: 8 SVs, margin 5.00031# RBF gamma=0.3: 8 SVs, f(4,3) = [0.4633]1from sklearn.model_selection import GridSearchCV2from sklearn.pipeline import make_pipeline3from sklearn.preprocessing import StandardScaler4from sklearn.svm import SVC56pipe = make_pipeline(StandardScaler(), SVC(kernel="rbf"))7grid = {"svc__C": [0.1, 1, 10, 100], "svc__gamma": [0.001, 0.01, 0.1, 1]}8search = GridSearchCV(pipe, grid, cv=5).fit(X_train, y_train)9print(search.best_params_, search.score(X_test, y_test))Use when
- +Small-to-medium data (up to ~10⁵ rows) where you want a strong, well-founded classifier with a convex, reproducible fit.
- +High-dimensional data with few samples — text (TF-IDF), genomics — where a max-margin linear model generalizes well.
- +Nonlinear boundaries with only two knobs: an RBF SVM needs just and .
- +You want a compact model: prediction needs only the support vectors.
Avoid when
- −Very large with a kernel: training grows as roughly – and the kernel matrix as . Use a linear SVM, kernel approximation or boosting instead.
- −You need calibrated probabilities or a cost-sensitive threshold: scores need Platt scaling, which costs an extra cross-validation.
- −Heavily overlapping, noisy classes: almost every point becomes a support vector and prediction gets slow.
- −Heterogeneous tabular data with categorical features and missing values — gradient-boosted trees are usually better and need no scaling.
Where it's used
Text classification
Spam, sentiment and topic labelling on sparse TF-IDF features with a linear SVM (Joachims, 1998) — still a strong baseline.
Bioinformatics
Cancer classification from gene-expression arrays and protein-family detection with string kernels: few samples, thousands of features.
Classic computer vision
HOG features + linear SVM (Dalal & Triggs, 2005) was the standard pedestrian detector; SVMs on CNN features remain common for small-data transfer learning.
Handwriting and signals
RBF and polynomial SVMs on MNIST digits and on EEG/ECG features for event detection.
Check yourself
An SVM ends with . How wide is the margin (street)?
Check yourself
In the worked example you drag point #9 (6, 4) to (7, 2), still far outside the street. What happens to the boundary?
Check yourself
In the worked example, what is the smallest C for which the soft-margin SVM returns exactly the hard-margin solution?
Check yourself
An RBF SVM with a very large is asked to classify a point far from every training point. Its decision value is approximately…
Remember
- ✓Scale so the closest points have ; the margin is , so maximizing it means minimizing subject to .
- ✓The dual gives ; complementary slackness makes only for support vectors, on the kerbs or inside the street.
- ✓Soft margin = hinge loss + penalty. In the dual, is a ceiling on each point's influence: small gives a wide street and many SVs.
- ✓The data enter only through dot products, so a kernel yields nonlinear boundaries. RBF sets the bump width; tune and jointly.
- ✓SVM scores are not probabilities, and kernel training scales about n²–n³. Standardize features, and prefer a linear SVM for large or sparse data.