# Support Vector Machines

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

Source: https://www.mlfoundry.in/learn/support-vector-machines  
Section: ML Algorithms › Supervised · Classification  
Level: core · 18 min read · updated 2026-10-07

**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.

- **Task:** Binary classification, labels $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\in\mathbb{R}^d$ → class $\operatorname{sign} f(x)$, where $f(x)=w^\top x+b$ is a signed score, not a probability
- **Learns:** a normal vector $w$ and offset $b$; in kernel form, one weight $\alpha_i\in[0,C]$ per training point — nonzero only for support vectors
- **Loss:** hinge loss $\max(0,1-y f(x))$ plus an $L_2$ penalty $\tfrac12\lVert w\rVert^2$
- **Training:** a convex quadratic program — one global optimum. Kernel SMO: roughly $O(n^2)$–$O(n^3)$ time, $O(n^2)$ kernel memory; linear SVMs: about $O(nd)$ per pass
- **Prediction:** $O(d)$ for a linear SVM; $O(n_{\text{SV}}\,d)$ with a kernel
- **Hyperparameters:** $C$ (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; $C$ 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^\top x+b=0\}$ — a line in 2-D. $w$ is perpendicular to it; $b$ shifts it.
- **Decision value:** $f(x)=w^\top x+b$. Its sign is the class; $|f(x)|/\lVert w\rVert$ is the distance to the hyperplane.
- **Functional margin:** $y_i f(x_i)$ — positive when point $i$ is classified correctly, and at least 1 when it is outside the street.
- **Margin (street width):** the distance between the two kerbs $f=-1$ and $f=+1$, equal to $2/\lVert w\rVert$.
- **Support vector:** a training point with $\alpha_i>0$: either exactly on a kerb ($y_if=1$) or a violator inside the street or on the wrong side.
- **Slack ξᵢ:** how far point $i$ falls short of the kerb, in units of $f$: $\xi_i=\max(0,1-y_if(x_i))$. $\xi_i>1$ means misclassified.
- **Hinge loss:** $\max(0,1-yf)$ — zero for points safely outside the street, linear inside it.
- **Dual weight αᵢ:** the Lagrange multiplier of point $i$'s constraint; how hard that point pushes on the boundary.
- **Kernel / Gram matrix:** $k(x,x')=\phi(x)^\top\phi(x')$, a dot product in a feature space; $K_{ij}=k(x_i,x_j)$ for all pairs of training points.

## The math

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

$$
\operatorname{dist}(x)=\frac{|w^\top x+b|}{\lVert w\rVert}
$$

- $w$: normal vector of the hyperplane (the weights)
- $b$: offset (bias)
- $\lVert w\rVert$: Euclidean length $\sqrt{\sum_j w_j^2}$

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

$$
\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
$$

- $y_i$: label of point $i$, $-1$ or $+1$
- $y_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 $\alpha_i\ge0$ to each constraint and form the Lagrangian:

$$
\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]
$$

- $\alpha_i$: Lagrange multiplier (dual weight) of point i, ≥ 0

Set the derivatives with respect to the primal variables to zero. $\partial\mathcal{L}/\partial w=w-\sum_i\alpha_iy_ix_i=0$ and $\partial\mathcal{L}/\partial b=-\sum_i\alpha_iy_i=0$, so

$$
w=\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 $\mathcal{L}$ eliminates $w$ and $b$ and leaves a problem in $\alpha$ alone:

$$
\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
$$

- $x_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: $\alpha_i\,[y_if(x_i)-1]=0$ for every $i$. So either $\alpha_i=0$ (the point plays no role in $w$) or $y_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 $s$ gives the offset: $b=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 $\xi_i\ge0$ and pay $C$ per unit of slack:

$$
\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
$$

- $\xi_i$: slack: $0$ outside the street, $(0,1]$ inside it, $>1$ misclassified
- $C$: price of one unit of slack; large C → few violations, narrow street

For fixed $w,b$ the best slack is the smallest allowed, $\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}\ \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\le\alpha_i\le C$. That box constraint is how $C$ acts mathematically. Each point falls into one of three cases:

The three kinds of training point at a soft-margin optimum (from the KKT conditions).

| Dual weight | Position | Slack | Effect on the boundary |
| --- | --- | --- | --- |
| $\alpha_i=0$ | outside the street, $y_if\ge1$ | 0 | none — moving it (outside the street) changes nothing |
| $0<\alpha_i<C$ | exactly on a kerb, $y_if=1$ | 0 | a *free* support vector; pins the street; used to compute b |
| $\alpha_i=C$ | inside the street or misclassified, $y_if\le1$ | $1-y_if$ | a *bound* support vector; pushes as hard as $C$ allows |

Read $C$ as a cap on each point's influence. When $C$ exceeds the largest $\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\to0$ every point ends up at $\alpha_i=C$ and $w$ shrinks toward 0. The hinge form shows the same thing from the other side: $C$ multiplies the loss, so it is the inverse of a ridge penalty, with $\lambda=1/(nC)$ if you average the loss over the $n$ points.

> **Hinge loss vs log-loss:** Logistic regression minimizes $\log(1+e^{-yf})$, which is never exactly zero, so **every** training point pulls on the boundary and the model returns calibrated-ish probabilities $\sigma(f)$. The hinge loss is **exactly zero** once $yf\ge1$. Well-classified points drop out entirely, which is what makes the solution sparse in support vectors. The price is that $f(x)$ is a distance-like score, not a probability. If you need $P(y=1\mid x)$, fit a sigmoid $1/(1+e^{Af+B})$ on held-out scores (Platt scaling, scikit-learn's `probability=True`).

## 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\ge0.278$ gives the same answer, as we will see).

Training data. Highlighted: the three points that turn out to be the support vectors.

| # | 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**

1. **Guess the support vectors.** The street must run between the two clouds, so the points facing the gap are the candidates: #3 $(2,3)$ and #5 $(3,1)$ on the $-1$ side, #7 $(5,3)$ on the $+1$ side. Assume all three lie on their kerbs.
2. **Kerb equations** $w_1x_1+w_2x_2+b=y$: #3 gives $2w_1+3w_2+b=-1$; #5 gives $3w_1+w_2+b=-1$; #7 gives $5w_1+3w_2+b=+1$.
3. **Solve.** Subtract #3 from #7: $3w_1=2$, so $w_1=\tfrac23$. Subtract #3 from #5: $w_1-2w_2=0$, so $w_2=\tfrac13$. Then $b=-1-2\cdot\tfrac23-3\cdot\tfrac13=-\tfrac{10}{3}$. So $f(x)=\tfrac23x_1+\tfrac13x_2-\tfrac{10}3$.
4. **Check feasibility.** Every other point must have $y_if(x_i)\ge1$. The table below confirms it: the smallest value among non-support vectors is $\tfrac43$ (points #4 and #10).
5. **Recover the dual weights** from $w=\sum\alpha_iy_ix_i$ and $\sum\alpha_iy_i=0$: $\alpha_7=\alpha_3+\alpha_5$; the $x_2$ component gives $-3\alpha_3-\alpha_5+3\alpha_7=2\alpha_5=\tfrac13$, so $\alpha_5=\tfrac16$; the $x_1$ component gives $3\alpha_3+2\alpha_5=\tfrac23$, so $\alpha_3=\tfrac19$; hence $\alpha_7=\tfrac{5}{18}$. All three are positive, so every KKT condition holds and this is **the** optimum.
6. **Margin.** $\lVert w\rVert=\sqrt{4/9+1/9}=\sqrt5/3=0.745$, so the street is $2/\lVert w\rVert=6/\sqrt5=2.683$ wide. Check: $\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 $\tfrac59-\tfrac12\cdot\tfrac59=\tfrac5{18}=0.278$, equal to the primal $\tfrac12\lVert w\rVert^2$.
7. **Classify a new point** $q=(4,3)$. Primal: $f(q)=\tfrac83+1-\tfrac{10}3=\tfrac13$. Dual, using only dot products with the support vectors, $x_3^\top q=17$, $x_5^\top q=15$, $x_7^\top q=29$: $f(q)=-\tfrac19(17)-\tfrac16(15)+\tfrac5{18}(29)-\tfrac{10}3=\tfrac{66}{18}-\tfrac{60}{18}=\tfrac13$. Positive → class **+1**. Because $0<f<1$, $q$ falls *inside* the street, at distance $\tfrac13/0.745=0.447$ from the boundary.

Functional margin $y_if(x_i)$ and distance to the boundary for every point, with $w=(\tfrac23,\tfrac13)$, $b=-\tfrac{10}3$. Exactly the three support vectors sit at 1.

| # | 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 $\alpha_7=\tfrac5{18}\approx0.278$. That is why every $C\ge0.278$ returns this same solution: the ceiling $\alpha_i\le C$ never binds.

> Figure: 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 $C$ deliberately lets points into the street to buy a wider one. Here is the exact soft-margin optimum for several values of $C$:

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.

| 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 $C=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)$ flips to the $-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 $x_i^\top x_j$, and the prediction is $f(x)=\sum_i\alpha_iy_i\,x_i^\top x+b$. Map every point to features $\phi(x)$ and the dot products become $\phi(x_i)^\top\phi(x_j)$. A **kernel** computes that number directly from $x_i$ and $x_j$, without ever forming $\phi$:

$$
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(x_i,x)$: kernel: similarity of $x$ to support vector $x_i$, equal to $\phi(x_i)^\top\phi(x)$
- $\gamma$: RBF width parameter; the bump around each support vector has radius ≈ 1/√γ
- $\text{SV}$: the support vectors — only they have $\alpha_i>0$

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

**How γ and C shape an RBF SVM**

- **γ small:** wide bumps: $k\approx1-\gamma\lVert x-x'\rVert^2$, so $f$ is smooth and close to a low-degree polynomial. Risk: underfitting.
- **γ large:** narrow bumps: $k(x_i,x_j)\to0$ for $i\ne j$, $K\to I$, and every point becomes its own island. $f(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:** $C$ and $\gamma$ interact: a large $\gamma$ needs a smaller $C$ and vice versa. Search them jointly on a log grid.

> Figure: Lifting x to (x, x²) turns two thresholds into one straight line. A kernel does this implicitly, without ever computing φ.

Common kernels. A function is a valid kernel when every Gram matrix it produces is positive semidefinite (Mercer's condition).

| Kernel | k(x, x′) | Feature space | Parameters |
| --- | --- | --- | --- |
| Linear | $x^\top x'$ | the inputs themselves | C only |
| Polynomial | $(\gamma\,x^\top x'+r)^p$ | all monomials up to degree $p$ | $p$, $\gamma$, $r$, C |
| RBF (Gaussian) | $\exp(-\gamma\lVert x-x'\rVert^2)$ | infinite-dimensional | $\gamma$, C |
| Sigmoid | $\tanh(\gamma\,x^\top x'+r)$ | not always PSD — rarely a good choice | $\gamma$, $r$, 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 $\sum_i\alpha_iy_i=0$, you cannot change one $\alpha$ alone, but you can change **two**: moving $\alpha_i$ by $y_it$ and $\alpha_j$ by $-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. **Initialize** $\alpha=0$ and the dual gradient $G_i=\sum_j y_iy_jK_{ij}\alpha_j-1=-1$. Precompute or cache the kernel matrix $K$.
2. **Select a pair.** Among points whose $\alpha$ may still move up, take $i=\arg\max(-y_iG_i)$; among those that may move down, take $j=\arg\min(-y_jG_j)$. This is the pair that violates the KKT conditions most.
3. **Stop** if the gap $(-y_iG_i)-(-y_jG_j)<\varepsilon$: all KKT conditions hold to tolerance $\varepsilon$.
4. **Step.** The curvature along the pair is $\eta=K_{ii}+K_{jj}-2K_{ij}$, so the unconstrained step is $t=\text{gap}/\eta$. Clip $t$ so that both $\alpha_i$ and $\alpha_j$ stay in $[0,C]$.
5. **Update** $\alpha_i\mathrel{+}=y_it$, $\alpha_j\mathrel{-}=y_jt$, and the gradient $G\mathrel{+}=t\,y\odot(K_{:,i}-K_{:,j})$, which costs $O(n)$.
6. **Finish.** Set $b$ to the average of $-y_sG_s$ over free support vectors ($0<\alpha_s<C$). The model keeps only the points with $\alpha_i>0$.

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

> Figure: 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 $C$ with $\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=1$ and `gamma="scale"`, i.e. $\gamma=1/(d\cdot\operatorname{Var}(X))$.
- **3. Grid:** search $C\in\{10^{-2},\dots,10^{3}\}$ × $\gamma\in\{10^{-4},\dots,10^{1}\}$ on a log scale, with cross-validation.
- **4. Imbalance:** `class_weight="balanced"` scales $C$ per class, $C_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.

> **Siblings:** The ε-insensitive loss, tube width and regression metrics are covered in *Support vector regression*. For a non-parametric classifier that also predicts from similarity to stored training points, but keeps all of them, see *k-Nearest neighbors*. An RBF SVM is in effect a sparse, learned, weighted vote of its support vectors.

## In code

```python
import numpy as np

def kernel(A, B, kind="linear", gamma=0.5):
    if kind == "linear":
        return A @ B.T
    d2 = ((A[:, None, :] - B[None, :, :]) ** 2).sum(-1)
    return np.exp(-gamma * d2)

def fit_svm(X, y, C=1.0, kind="linear", gamma=0.5, eps=1e-6, max_iter=10000):
    """Dual SVM by SMO with maximal-violating-pair selection (as in libsvm)."""
    n = len(y)
    K = kernel(X, X, kind, gamma)
    a = np.zeros(n)
    G = -np.ones(n)                                   # gradient of the dual: Q a - 1
    for _ in range(max_iter):
        up = ((y > 0) & (a < C)) | ((y < 0) & (a > 0))  # alpha may move "up"
        low = ((y > 0) & (a > 0)) | ((y < 0) & (a < C))
        s = -y * G
        i = np.where(up)[0][np.argmax(s[up])]
        j = np.where(low)[0][np.argmin(s[low])]
        gap = s[i] - s[j]
        if gap < eps:                                 # KKT conditions hold
            break
        curv = max(K[i, i] + K[j, j] - 2 * K[i, j], 1e-12)
        t = gap / curv                                # unconstrained optimum
        t = min(t, C - a[i] if y[i] > 0 else a[i])    # keep 0 <= a <= C
        t = min(t, a[j] if y[j] > 0 else C - a[j])
        a[i] += y[i] * t
        a[j] -= y[j] * t
        G += t * y * (K[:, i] - K[:, j])
    free = (a > 1e-8) & (a < C - 1e-8)
    b = np.mean(-y[free] * G[free]) if free.any() else (s[i] + s[j]) / 2
    return a, b

def decision(X_train, y, a, b, Xq, kind="linear", gamma=0.5):
    return kernel(Xq, X_train, kind, gamma) @ (a * y) + b

X = np.array([[1, 2], [2, 1], [2, 3], [1, 4], [3, 1],
              [6, 6], [5, 3], [5, 5], [6, 4], [4, 6]], float)
y = np.array([-1, -1, -1, -1, -1, 1, 1, 1, 1, 1], float)

a, b = fit_svm(X, y, C=10)
w = (a * y) @ X
print("alpha =", a.round(4))
print("support vectors:", np.where(a > 1e-6)[0] + 1)
print("w =", w.round(4), " b =", round(b, 4), " margin =", round(2 / np.linalg.norm(w), 4))
print("y*f(x) =", (y * decision(X, y, a, b, X)).round(3))
print("f(4,3) =", decision(X, y, a, b, np.array([[4.0, 3.0]])).round(4))

# alpha = [0.     0.     0.1111 0.     0.1667 0.     0.2778 0.     0.     0.    ]
# support vectors: [3 5 7]
# w = [0.6667 0.3333]  b = -3.3333  margin = 2.6833
# y*f(x) = [2.    1.667 1.    1.333 1.    2.667 1.    1.667 2.    1.333]
# 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
import numpy as np
from sklearn.svm import SVC

X = np.array([[1, 2], [2, 1], [2, 3], [1, 4], [3, 1],
              [6, 6], [5, 3], [5, 5], [6, 4], [4, 6]], float)
y = np.array([-1, -1, -1, -1, -1, 1, 1, 1, 1, 1])

svm = SVC(kernel="linear", C=10, tol=1e-8).fit(X, y)
w, b = svm.coef_[0], svm.intercept_[0]
print("support vectors:", svm.support_ + 1)          # 1-based point numbers
print("alpha_i * y_i:  ", svm.dual_coef_[0].round(4))
print("w =", w.round(4), " b =", round(b, 4))
print("margin width =", round(2 / np.linalg.norm(w), 4))
print("f(4,3) =", svm.decision_function([[4, 3]]).round(4), "->", svm.predict([[4, 3]]))

for C in [0.2, 0.1, 0.03]:
    m = SVC(kernel="linear", C=C, tol=1e-8).fit(X, y)
    print(f"C={C}: {len(m.support_)} SVs, margin {2 / np.linalg.norm(m.coef_):.3f}")

rbf = SVC(kernel="rbf", C=10, gamma=0.3, tol=1e-8).fit(X, y)
print("RBF gamma=0.3:", len(rbf.support_), "SVs, f(4,3) =", rbf.decision_function([[4, 3]]).round(4))

# support vectors: [3 5 7]
# alpha_i * y_i:   [-0.1111 -0.1667  0.2778]
# w = [0.6667 0.3333]  b = -3.3333
# margin width = 2.6833
# f(4,3) = [0.3333] -> [1]
# C=0.2: 4 SVs, margin 3.130
# C=0.1: 5 SVs, margin 3.606
# C=0.03: 8 SVs, margin 5.000
# 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
from sklearn.model_selection import GridSearchCV
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

pipe = make_pipeline(StandardScaler(), SVC(kernel="rbf"))
grid = {"svc__C": [0.1, 1, 10, 100], "svc__gamma": [0.001, 0.01, 0.1, 1]}
search = GridSearchCV(pipe, grid, cv=5).fit(X_train, y_train)
print(search.best_params_, search.score(X_test, y_test))
```

On real data: always scale inside a pipeline, and tune C and γ together.

**Strengths**

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

**Limitations**

- Very large $n$ with a kernel: training grows as roughly $n^2$–$n^3$ and the kernel matrix as $n^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.

- **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.

> **Scale features first:** Both the margin $2/\lVert w\rVert$ and the RBF distance $\lVert x-x'\rVert$ are Euclidean. A feature measured in thousands dominates both, and the SVM effectively ignores the others. Standardize inside a pipeline so the scaler only ever sees training folds.

> **Tune C and γ jointly, on a log scale:** A large $\gamma$ with a large $C$ memorizes the training set: every point becomes a support vector with a tiny bump of influence. A one-at-a-time search misses the good diagonal in the $(C,\gamma)$ plane. Search both together, over powers of 10.

> **decision_function is not a probability:** $f(x)=0.333$ means "on the $+1$ side, inside the street", not "33% likely". Compare classifiers with ranking metrics (ROC AUC), or calibrate before thresholding on probabilities.

**Question:** An SVM ends with $\lVert w\rVert=4$. How wide is the margin (street)?

- A. 4
- B. 0.25
- C. 0.5
- D. 2

**Answer:** C. 0.5 — The kerbs are $f=\pm1$, each at distance $1/\lVert w\rVert$ from the boundary, so the width is $2/\lVert w\rVert=2/4=0.5$.

**Question:** In the worked example you drag point #9 (6, 4) to (7, 2), still far outside the street. What happens to the boundary?

- A. It rotates toward #9
- B. It shifts away from #9
- C. Nothing — #9 has α = 0
- D. The margin widens

**Answer:** C. Nothing — #9 has α = 0 — $\alpha_9=0$, so #9 contributes nothing to $w=\sum\alpha_iy_ix_i$. At $(7,2)$, $y f=\tfrac{14}3+\tfrac23-\tfrac{10}3=2\ge1$, so it still satisfies its constraint and the optimum is unchanged.

**Question:** In the worked example, what is the smallest C for which the soft-margin SVM returns exactly the hard-margin solution?

- A. 0.111
- B. 0.278
- C. 1
- D. Any C > 0

**Answer:** B. 0.278 — The soft-margin dual only adds the ceiling $\alpha_i\le C$. The hard-margin weights are $\tfrac19,\tfrac16,\tfrac5{18}$; the ceiling is inactive exactly when $C\ge\max\alpha_i=\tfrac5{18}\approx0.278$. At $C=0.2$, $\alpha_7$ is capped and the street widens to 3.130.

**Question:** An RBF SVM with a very large $\gamma$ is asked to classify a point far from every training point. Its decision value is approximately…

- A. +1
- B. −1
- C. the offset $b$
- D. the label of the nearest support vector, times its α

**Answer:** C. the offset $b$ — $k(x_i,x)=e^{-\gamma\lVert x_i-x\rVert^2}\to0$ for every support vector, so $f(x)=\sum\alpha_iy_ik(x_i,x)+b\to b$. The model has learned nothing about that region: a classic sign of overfitting.

**Key points**

- Scale so the closest points have $|f|=1$; the margin is $2/\lVert w\rVert$, so maximizing it means minimizing $\tfrac12\lVert w\rVert^2$ subject to $y_if(x_i)\ge1$.
- The dual gives $w=\sum\alpha_iy_ix_i$; complementary slackness makes $\alpha_i>0$ only for **support vectors**, on the kerbs or inside the street.
- Soft margin = hinge loss + $L_2$ penalty. In the dual, $C$ is a ceiling $0\le\alpha_i\le C$ on each point's influence: small $C$ gives a wide street and many SVs.
- The data enter only through dot products, so a kernel $k(x,x')$ yields nonlinear boundaries. RBF $\gamma$ sets the bump width; tune $C$ 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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
