Support Vector Machines

Find the hyperplane with the largest margin to the nearest points; kernels make the boundary nonlinear.

18 min read1817 wordscore16 viewsupdated 2026-10-07

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 y∈{−1,+1}y\in\{-1,+1\}; multi-class via one-vs-one or one-vs-rest. (Regression is the sibling article Support vector regression.)
Input → output
x∈Rdx\in\mathbb{R}^d → class sign⁡f(x)\operatorname{sign} f(x), where f(x)=w⊤x+bf(x)=w^\top x+b is a signed score, not a probability
Learns
a normal vector ww and offset bb; in kernel form, one weight αi∈[0,C]\alpha_i\in[0,C] per training point — nonzero only for support vectors
Loss
hinge loss max⁡(0,1−yf(x))\max(0,1-y f(x)) plus an L2L_2 penalty 12∥w∥2\tfrac12\lVert w\rVert^2
Training
a convex quadratic program — one global optimum. Kernel SMO: roughly O(n2)O(n^2)–O(n3)O(n^3) time, O(n2)O(n^2) kernel memory; linear SVMs: about O(nd)O(nd) per pass
Prediction
O(d)O(d) for a linear SVM; O(nSV d)O(n_{\text{SV}}\,d) with a kernel
Hyperparameters
CC (violations vs margin width), the kernel, and its parameters — RBF γ\gamma, 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; CC 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 {x:w⊤x+b=0}\{x: w^\top x+b=0\} — a line in 2-D. ww is perpendicular to it; bb shifts it.
Decision value
f(x)=w⊤x+bf(x)=w^\top x+b. Its sign is the class; ∣f(x)∣/∥w∥|f(x)|/\lVert w\rVert is the distance to the hyperplane.
Functional margin
yif(xi)y_i f(x_i) — positive when point ii is classified correctly, and at least 1 when it is outside the street.
Margin (street width)
the distance between the two kerbs f=−1f=-1 and f=+1f=+1, equal to 2/∥w∥2/\lVert w\rVert.
Support vector
a training point with αi>0\alpha_i>0: either exactly on a kerb (yif=1y_if=1) or a violator inside the street or on the wrong side.
Slack ξᵢ
how far point ii falls short of the kerb, in units of ff: ξi=max⁡(0,1−yif(xi))\xi_i=\max(0,1-y_if(x_i)). ξi>1\xi_i>1 means misclassified.
Hinge loss
max⁡(0,1−yf)\max(0,1-yf) — zero for points safely outside the street, linear inside it.
Dual weight αᵢ
the Lagrange multiplier of point ii's constraint; how hard that point pushes on the boundary.
Kernel / Gram matrix
k(x,x′)=ϕ(x)⊤ϕ(x′)k(x,x')=\phi(x)^\top\phi(x'), a dot product in a feature space; Kij=k(xi,xj)K_{ij}=k(x_i,x_j) for all pairs of training points.

The math

Distance to a hyperplane. Take any point xx and drop a perpendicular to the hyperplane; it travels along the unit normal w/∥w∥w/\lVert w\rVert. Solving w⊤(x−t w/∥w∥)+b=0w^\top(x-t\,w/\lVert w\rVert)+b=0 for tt gives

dist⁡(x)=∣w⊤x+b∣∥w∥\operatorname{dist}(x)=\frac{|w^\top x+b|}{\lVert w\rVert}
ww
normal vector of the hyperplane (the weights)
bb
offset (bias)
∥w∥\lVert w\rVert
Euclidean length ∑jwj2\sqrt{\sum_j w_j^2}

Fix the scale. Multiplying ww and bb by any k>0k>0 describes the same hyperplane, so we are free to choose kk. Pick it so the closest points have ∣w⊤x+b∣=1|w^\top x+b|=1. Then the kerbs are the lines f=±1f=\pm1, each at distance 1/∥w∥1/\lVert w\rVert from the centre, and the street is 2/∥w∥2/\lVert w\rVert wide. Maximizing 2/∥w∥2/\lVert w\rVert is the same as minimizing 12∥w∥2\tfrac12\lVert w\rVert^2 (the square and the ½ just make the calculus clean):

min⁡w,b 12∥w∥2s.t.yi (w⊤xi+b)≥1,i=1,…,n\min_{w,b}\ \tfrac12\lVert w\rVert^2\quad\text{s.t.}\quad y_i\,(w^\top x_i+b)\ge 1,\quad i=1,\dots,n
yiy_i
label of point ii, −1-1 or +1+1
yi(w⊤xi+b)≥1y_i(w^\top x_i+b)\ge1
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 αi≥0\alpha_i\ge0 to each constraint and form the Lagrangian:

L(w,b,α)=12∥w∥2−∑i=1nαi[yi(w⊤xi+b)−1]\mathcal{L}(w,b,\alpha)=\tfrac12\lVert w\rVert^2-\sum_{i=1}^n\alpha_i\big[y_i(w^\top x_i+b)-1\big]
αi\alpha_i
Lagrange multiplier (dual weight) of point i, ≥ 0

Set the derivatives with respect to the primal variables to zero. ∂L/∂w=w−∑iαiyixi=0\partial\mathcal{L}/\partial w=w-\sum_i\alpha_iy_ix_i=0 and ∂L/∂b=−∑iαiyi=0\partial\mathcal{L}/\partial b=-\sum_i\alpha_iy_i=0, so

w=∑i=1nαi yi xi,∑i=1nαi yi=0w=\sum_{i=1}^n\alpha_i\,y_i\,x_i,\qquad \sum_{i=1}^n\alpha_i\,y_i=0

The weight vector is a weighted sum of training points. Substituting it back into L\mathcal{L} eliminates ww and bb and leaves a problem in α\alpha alone:

max⁡α ∑iαi−12∑i∑jαiαj yiyj xi⊤xjs.t.αi≥0,  ∑iαiyi=0\max_{\alpha}\ \sum_{i}\alpha_i-\tfrac12\sum_{i}\sum_{j}\alpha_i\alpha_j\,y_iy_j\,x_i^\top x_j\quad\text{s.t.}\quad \alpha_i\ge0,\ \ \sum_i\alpha_iy_i=0
xi⊤xjx_i^\top x_j
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: αi [yif(xi)−1]=0\alpha_i\,[y_if(x_i)-1]=0 for every ii. So either αi=0\alpha_i=0 (the point plays no role in ww) or yif(xi)=1y_if(x_i)=1 (the point sits exactly on a kerb). That is the precise sense in which only support vectors matter. Once α\alpha is known, any support vector ss gives the offset: b=ys−w⊤xsb=y_s-w^\top x_s.

Soft margin and the role of C

If the classes overlap, the hard constraints cannot all hold. Give each point a slack ξi≥0\xi_i\ge0 and pay CC per unit of slack:

min⁡w,b,ξ 12∥w∥2+C∑i=1nξis.t.yi(w⊤xi+b)≥1−ξi,  ξi≥0\min_{w,b,\xi}\ \tfrac12\lVert w\rVert^2+C\sum_{i=1}^n\xi_i\quad\text{s.t.}\quad y_i(w^\top x_i+b)\ge1-\xi_i,\ \ \xi_i\ge0
ξi\xi_i
slack: 00 outside the street, (0,1](0,1] inside it, >1>1 misclassified
CC
price of one unit of slack; large C → few violations, narrow street

For fixed w,bw,b the best slack is the smallest allowed, ξi=max⁡(0,1−yif(xi))\xi_i=\max(0,1-y_if(x_i)). Substituting it gives the unconstrained hinge-loss form, which is just a regularized loss like every other model in this course:

min⁡w,b 12∥w∥2+C∑i=1nmax⁡ ⁣(0, 1−yi(w⊤xi+b))\min_{w,b}\ \tfrac12\lVert w\rVert^2+C\sum_{i=1}^n\max\!\big(0,\ 1-y_i(w^\top x_i+b)\big)

Repeating the Lagrangian derivation changes exactly one thing in the dual: the multipliers get a ceiling, 0≤αi≤C0\le\alpha_i\le C. That box constraint is how CC acts mathematically. Each point falls into one of three cases:

Dual weightPositionSlackEffect on the boundary
αi=0\alpha_i=0outside the street, yif≥1y_if\ge10none — moving it (outside the street) changes nothing
0<αi<C0<\alpha_i<Cexactly on a kerb, yif=1y_if=10a free support vector; pins the street; used to compute b
αi=C\alpha_i=Cinside the street or misclassified, yif≤1y_if\le11−yif1-y_ifa bound support vector; pushes as hard as CC allows
The three kinds of training point at a soft-margin optimum (from the KKT conditions).

Read CC as a cap on each point's influence. When CC exceeds the largest αi\alpha_i 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 C→0C\to0 every point ends up at αi=C\alpha_i=C and ww shrinks toward 0. The hinge form shows the same thing from the other side: CC multiplies the loss, so it is the inverse of a ridge penalty, with λ=1/(nC)\lambda=1/(nC) if you average the loss over the nn 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 C≥0.278C\ge0.278 gives the same answer, as we will see).

#x₁x₂y
112−1
221−1
323−1
414−1
531−1
666+1
753+1
855+1
964+1
1046+1
Training data. Highlighted: the three points that turn out to be the support vectors.

Solving the SVM by hand

  1. 1Guess the support vectors. The street must run between the two clouds, so the points facing the gap are the candidates: #3 (2,3)(2,3) and #5 (3,1)(3,1) on the −1-1 side, #7 (5,3)(5,3) on the +1+1 side. Assume all three lie on their kerbs.
  2. 2Kerb equations w1x1+w2x2+b=yw_1x_1+w_2x_2+b=y: #3 gives 2w1+3w2+b=−12w_1+3w_2+b=-1; #5 gives 3w1+w2+b=−13w_1+w_2+b=-1; #7 gives 5w1+3w2+b=+15w_1+3w_2+b=+1.
  3. 3Solve. Subtract #3 from #7: 3w1=23w_1=2, so w1=23w_1=\tfrac23. Subtract #3 from #5: w1−2w2=0w_1-2w_2=0, so w2=13w_2=\tfrac13. Then b=−1−2⋅23−3⋅13=−103b=-1-2\cdot\tfrac23-3\cdot\tfrac13=-\tfrac{10}{3}. So f(x)=23x1+13x2−103f(x)=\tfrac23x_1+\tfrac13x_2-\tfrac{10}3.
  4. 4Check feasibility. Every other point must have yif(xi)≥1y_if(x_i)\ge1. The table below confirms it: the smallest value among non-support vectors is 43\tfrac43 (points #4 and #10).
  5. 5Recover the dual weights from w=∑αiyixiw=\sum\alpha_iy_ix_i and ∑αiyi=0\sum\alpha_iy_i=0: α7=α3+α5\alpha_7=\alpha_3+\alpha_5; the x2x_2 component gives −3α3−α5+3α7=2α5=13-3\alpha_3-\alpha_5+3\alpha_7=2\alpha_5=\tfrac13, so α5=16\alpha_5=\tfrac16; the x1x_1 component gives 3α3+2α5=233\alpha_3+2\alpha_5=\tfrac23, so α3=19\alpha_3=\tfrac19; hence α7=518\alpha_7=\tfrac{5}{18}. All three are positive, so every KKT condition holds and this is the optimum.
  6. 6Margin. ∥w∥=4/9+1/9=5/3=0.745\lVert w\rVert=\sqrt{4/9+1/9}=\sqrt5/3=0.745, so the street is 2/∥w∥=6/5=2.6832/\lVert w\rVert=6/\sqrt5=2.683 wide. Check: ∑αi=19+16+518=59=∥w∥2\sum\alpha_i=\tfrac19+\tfrac16+\tfrac5{18}=\tfrac59=\lVert w\rVert^2, which is a known identity at the hard-margin optimum. The dual objective is 59−12⋅59=518=0.278\tfrac59-\tfrac12\cdot\tfrac59=\tfrac5{18}=0.278, equal to the primal 12∥w∥2\tfrac12\lVert w\rVert^2.
  7. 7Classify a new point q=(4,3)q=(4,3). Primal: f(q)=83+1−103=13f(q)=\tfrac83+1-\tfrac{10}3=\tfrac13. Dual, using only dot products with the support vectors, x3⊤q=17x_3^\top q=17, x5⊤q=15x_5^\top q=15, x7⊤q=29x_7^\top q=29: f(q)=−19(17)−16(15)+518(29)−103=6618−6018=13f(q)=-\tfrac19(17)-\tfrac16(15)+\tfrac5{18}(29)-\tfrac{10}3=\tfrac{66}{18}-\tfrac{60}{18}=\tfrac13. Positive → class +1. Because 0<f<10<f<1, qq falls inside the street, at distance 13/0.745=0.447\tfrac13/0.745=0.447 from the boundary.
#yf(x)y · f(x)DistanceDual weight
1−1−222.6830
2−1−5/35/32.2360
3−1−111.3421/9 = 0.111
4−1−4/34/31.7890
5−1−111.3421/6 = 0.167
6+18/38/33.5780
7+1111.3425/18 = 0.278
8+15/35/32.2360
9+1222.6830
10+14/34/31.7890
Functional margin yif(xi)y_if(x_i) and distance to the boundary for every point, with w=(23,13)w=(\tfrac23,\tfrac13), b=−103b=-\tfrac{10}3. Exactly the three support vectors sit at 1.

The largest dual weight is α7=518≈0.278\alpha_7=\tfrac5{18}\approx0.278. That is why every C≥0.278C\ge0.278 returns this same solution: the ceiling αi≤C\alpha_i\le C never binds.

kernel
0011223344556677x₁ →x₂f = 0.33312345678910dual weight αᵢ(0 ≤ αᵢ ≤ C = 10)102030.1114050.1676070.27880901000 < α < C: on marginα = C: inside margin
w = (0.667, 0.333) · b = -3.333
margin 2/‖w‖ = 2.683
support vectors 3 · inside margin 0 · wrong side 0
Σξᵢ = 0.000 · Σαᵢyᵢ = 0.000
query (4.0, 3.0): f = Σ αᵢyᵢK(xᵢ, q) + b = 0.333 → class +1 (inside the margin)
fig.The worked example, solved live by SMO. At the start (linear kernel, C = 10) it shows w = (0.667, 0.333), b = −3.333, margin 2.683, and three support vectors, #3, #5 and #7 (mint rings), with α = 0.111, 0.167 and 0.278. The query ◆ at (4, 3) has f = 0.333. Drag any point, or the query. Moving a point that sits outside the street leaves the bars on the right untouched; moving a support vector moves everything. Lower C to 0.2: #7 hits the ceiling α = C (rose), the street widens to 3.130, and the dashed rose segment shows its slack. At C = 0.03 the street is 5.000 wide, with 8 support vectors. Switch to RBF with γ = 0.3 and the boundary curves, using 8 support vectors; f(query) becomes 0.463.

Effect of C on the example

Even though these points are separable, a small CC deliberately lets points into the street to buy a wider one. Here is the exact soft-margin optimum for several values of CC:

Cw, bMarginSupport vectorsIn streetTotal slackf(4, 3)
≥ 0.278(0.667, 0.333), −3.3332.6833, 5, 7000.333
0.2(0.571, 0.286), −3.0003.1303, 5, 7, 1010.2860.143
0.1(0.462, 0.308), −2.6923.6063, 4, 5, 7, 1020.6150.077
0.03(0.320, 0.240), −1.8805.0002, 3, 4, 5, 7, 8, 9, 1062.0000.120
0.01(0.170, 0.130), −1.1159.345all 10, all capped105.420−0.045
Soft-margin solutions on the ten points (exact SMO, verified against scikit-learn). Bold support vectors are capped at αᵢ = C. Every setting still classifies all ten training points correctly; what changes is how many points the street swallows.

At C=0.01C=0.01 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 (4,3)(4,3) flips to the −1-1 side. This is the underfitting end of the scale.

The kernel trick

Look at the dual again: the data enter only through dot products xi⊤xjx_i^\top x_j, and the prediction is f(x)=∑iαiyi xi⊤x+bf(x)=\sum_i\alpha_iy_i\,x_i^\top x+b. Map every point to features ϕ(x)\phi(x) and the dot products become ϕ(xi)⊤ϕ(xj)\phi(x_i)^\top\phi(x_j). A kernel computes that number directly from xix_i and xjx_j, without ever forming ϕ\phi:

f(x)=∑i∈SVαi yi k(xi,x)+b,k(x,x′)=exp⁡ ⁣(−γ∥x−x′∥2)f(x)=\sum_{i\in\text{SV}}\alpha_i\,y_i\,k(x_i,x)+b,\qquad k(x,x')=\exp\!\big(-\gamma\lVert x-x'\rVert^2\big)
k(xi,x)k(x_i,x)
kernel: similarity of xx to support vector xix_i, equal to ϕ(xi)⊤ϕ(x)\phi(x_i)^\top\phi(x)
γ\gamma
RBF width parameter; the bump around each support vector has radius ≈ 1/√γ
SV\text{SV}
the support vectors — only they have αi>0\alpha_i>0

With the RBF (Gaussian) kernel, ff is a sum of Gaussian bumps centred on the support vectors, signed by class, plus bb. Its feature space is infinite-dimensional, yet each kernel value costs O(d)O(d). Each hyperparameter has a clear effect on that sum:

How γ and C shape an RBF SVM

γ small
wide bumps: k≈1−γ∥x−x′∥2k\approx1-\gamma\lVert x-x'\rVert^2, so ff is smooth and close to a low-degree polynomial. Risk: underfitting.
γ large
narrow bumps: k(xi,xj)→0k(x_i,x_j)\to0 for i≠ji\ne j, K→IK\to I, and every point becomes its own island. f(x)→bf(x)\to b 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
CC and γ\gamma interact: a large γ\gamma needs a smaller CC and vice versa. Search them jointly on a log grid.
1 · input2 · lift3 · separate4 · project back
-1-0.500.51x²x² = 0.2025−0.45+0.45● B● A

1D input: A sits between two groups of B — no single threshold separates them.

fig.Lifting x to (x, x²) turns two thresholds into one straight line. A kernel does this implicitly, without ever computing φ.
Kernelk(x, x′)Feature spaceParameters
Linearx⊤x′x^\top x'the inputs themselvesC only
Polynomial(γ x⊤x′+r)p(\gamma\,x^\top x'+r)^pall monomials up to degree pppp, γ\gamma, rr, C
RBF (Gaussian)exp⁡(−γ∥x−x′∥2)\exp(-\gamma\lVert x-x'\rVert^2)infinite-dimensionalγ\gamma, C
Sigmoidtanh⁡(γ x⊤x′+r)\tanh(\gamma\,x^\top x'+r)not always PSD — rarely a good choiceγ\gamma, rr, C
Common kernels. A function is a valid kernel when every Gram matrix it produces is positive semidefinite (Mercer's condition).

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 ∑iαiyi=0\sum_i\alpha_iy_i=0, you cannot change one α\alpha alone, but you can change two: moving αi\alpha_i by yity_it and αj\alpha_j by −yjt-y_jt 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)

  1. 1Initialize α=0\alpha=0 and the dual gradient Gi=∑jyiyjKijαj−1=−1G_i=\sum_j y_iy_jK_{ij}\alpha_j-1=-1. Precompute or cache the kernel matrix KK.
  2. 2Select a pair. Among points whose α\alpha may still move up, take i=arg⁡max⁡(−yiGi)i=\arg\max(-y_iG_i); among those that may move down, take j=arg⁡min⁡(−yjGj)j=\arg\min(-y_jG_j). This is the pair that violates the KKT conditions most.
  3. 3Stop if the gap (−yiGi)−(−yjGj)<ε(-y_iG_i)-(-y_jG_j)<\varepsilon: all KKT conditions hold to tolerance ε\varepsilon.
  4. 4Step. The curvature along the pair is η=Kii+Kjj−2Kij\eta=K_{ii}+K_{jj}-2K_{ij}, so the unconstrained step is t=gap/ηt=\text{gap}/\eta. Clip tt so that both αi\alpha_i and αj\alpha_j stay in [0,C][0,C].
  5. 5Update αi+=yit\alpha_i\mathrel{+}=y_it, αj−=yjt\alpha_j\mathrel{-}=y_jt, and the gradient G+=t y⊙(K:,i−K:,j)G\mathrel{+}=t\,y\odot(K_{:,i}-K_{:,j}), which costs O(n)O(n).
  6. 6Finish. Set bb to the average of −ysGs-y_sG_s over free support vectors (0<αs<C0<\alpha_s<C). The model keeps only the points with αi>0\alpha_i>0.

On the worked example this loop converges in 35 pair updates. Complexity: each iteration is O(n)O(n) given kernel columns, and the number of iterations grows superlinearly with nn. In practice that means roughly O(n2)O(n^2)–O(n3)O(n^3) time, plus the O(n2)O(n^2) memory for the kernel matrix (libsvm caches the columns it uses). This is why kernel SVMs are rarely used beyond about 10510^5 rows. Linear SVMs skip the kernel entirely and solve the primal or dual by coordinate descent (liblinear) in about O(nd)O(nd) 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.

▸ Linear SVM · subgradient descentstep 1/22
y = −1y = +1
iteration 0margin 2/‖w‖ = ∞|V| = 0objective 1.0000
  1. 1w ← 0, b ← 0
  2. 2repeat:
  3. 3 V ← {i : yᵢ(w·xᵢ + b) < 1}
  4. 4 w ← w − η(λw − (1/n)Σᵥ yᵢxᵢ)
  5. 5 b ← b + η(1/n)Σᵥ yᵢ
  6. 6until V stops changing
  7. 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.

fig.Subgradient descent on the hinge-loss objective (a different, 28-point dataset). Only points inside the margin (ringed) move the boundary; at convergence just 2 support vectors define it.

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 CC with ν∈(0,1]\nu\in(0,1]: 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 C=1C=1 and gamma="scale", i.e. γ=1/(d⋅Var⁡(X))\gamma=1/(d\cdot\operatorname{Var}(X)).
3. Grid
search C∈{10−2,…,103}C\in\{10^{-2},\dots,10^{3}\} × γ∈{10−4,…,101}\gamma\in\{10^{-4},\dots,10^{1}\} on a log scale, with cross-validation.
4. Imbalance
class_weight="balanced" scales CC per class, Ck∝1/nkC_k\propto 1/n_k, 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

python
1import numpy as np
2
3def kernel(A, B, kind="linear", gamma=0.5):
4 if kind == "linear":
5 return A @ B.T
6 d2 = ((A[:, None, :] - B[None, :, :]) ** 2).sum(-1)
7 return np.exp(-gamma * d2)
8
9def 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 - 1
15 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 * G
19 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 hold
23 break
24 curv = max(K[i, i] + K[j, j] - 2 * K[i, j], 1e-12)
25 t = gap / curv # unconstrained optimum
26 t = min(t, C - a[i] if y[i] > 0 else a[i]) # keep 0 <= a <= C
27 t = min(t, a[j] if y[j] > 0 else C - a[j])
28 a[i] += y[i] * t
29 a[j] -= y[j] * t
30 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]) / 2
33 return a, b
34
35def decision(X_train, y, a, b, Xq, kind="linear", gamma=0.5):
36 return kernel(Xq, X_train, kind, gamma) @ (a * y) + b
37
38X = 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)
41
42a, b = fit_svm(X, y, C=10)
43w = (a * y) @ X
44print("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))
49
50# 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.6833
53# y*f(x) = [2. 1.667 1. 1.333 1. 2.667 1. 1.667 2. 1.333]
54# f(4,3) = [0.3333]
From scratch: the dual SVM by SMO (linear or RBF kernel), applied to the worked example. Output is shown in the comments.
python
1import numpy as np
2from sklearn.svm import SVC
3
4X = 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])
7
8svm = 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 numbers
11print("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]]))
15
16for 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}")
19
20rbf = 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))
22
23# support vectors: [3 5 7]
24# alpha_i * y_i: [-0.1111 -0.1667 0.2778]
25# w = [0.6667 0.3333] b = -3.3333
26# margin width = 2.6833
27# f(4,3) = [0.3333] -> [1]
28# C=0.2: 4 SVs, margin 3.130
29# C=0.1: 5 SVs, margin 3.606
30# C=0.03: 8 SVs, margin 5.000
31# RBF gamma=0.3: 8 SVs, f(4,3) = [0.4633]
scikit-learn on the same data: same support vectors, weights and margin; then the C sweep and an RBF kernel.
python
1from sklearn.model_selection import GridSearchCV
2from sklearn.pipeline import make_pipeline
3from sklearn.preprocessing import StandardScaler
4from sklearn.svm import SVC
5
6pipe = 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))
On real data: always scale inside a pipeline, and tune C and γ together.

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 CC and γ\gamma.
  • +You want a compact model: prediction needs only the support vectors.

Avoid when

  • −Very large nn with a kernel: training grows as roughly n2n^2–n3n^3 and the kernel matrix as n2n^2. 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 ∥w∥=4\lVert w\rVert=4. 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 γ\gamma is asked to classify a point far from every training point. Its decision value is approximately…

Remember

  • ✓Scale so the closest points have ∣f∣=1|f|=1; the margin is 2/∥w∥2/\lVert w\rVert, so maximizing it means minimizing 12∥w∥2\tfrac12\lVert w\rVert^2 subject to yif(xi)≥1y_if(x_i)\ge1.
  • ✓The dual gives w=∑αiyixiw=\sum\alpha_iy_ix_i; complementary slackness makes αi>0\alpha_i>0 only for support vectors, on the kerbs or inside the street.
  • ✓Soft margin = hinge loss + L2L_2 penalty. In the dual, CC is a ceiling 0≤αi≤C0\le\alpha_i\le C on each point's influence: small CC gives a wide street and many SVs.
  • ✓The data enter only through dot products, so a kernel k(x,x′)k(x,x') yields nonlinear boundaries. RBF γ\gamma sets the bump width; tune CC and γ\gamma 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.
← back to ML Algorithms roadmap