Skip to content
learn
  1. Learn
  2. Machine Learning
  3. Classification

Machine Learning ML-04.04

Support Vector Machines and kernels

Find the boundary with the widest margin, see why only support vectors matter, tune the soft margin C, and bend boundaries with the kernel trick.

Intermediate 15 min Last reviewed

The big idea

When two classes can be separated by a straight line, there are usually infinitely many lines that do it. Logistic regression picks one by fitting probabilities. A support vector machineA classifier that chooses the decision boundary with the largest margin to the nearest training points of each class, optionally in a kernel-induced feature space. (SVM) asks a different question: which line leaves the widest empty street between the classes?

Picture a road between two villages. You want to build it as wide as possible without demolishing any house. The houses right at the edge of the road decide where it can go; houses deep inside a village are irrelevant. Those edge houses are the support vectorsThe training points that lie on or inside the margin. They alone determine the SVM's boundary; removing any other point changes nothing.. A wide road is a safe road: new points that land a little off from the training points are still classified correctly.

How it works

Step 1: Maximise the margin

A linear SVM uses the same boundary shape as logistic regression, w . x + b = 0, and predicts the sign of w . x + b. It adds two parallel lines, w . x + b = +1 and w . x + b = -1, and requires every training point to sit on the correct side of its line. The gap between them is the marginThe width of the empty band around an SVM's decision boundary, equal to 2 / ||w||., and its width is 2 / ||w||. So maximising the margin means making the weights as small as possible while keeping every point outside the band.

Maximum margin and support vectors Seven cyan points on the left and six purple points on the right. Step 1 shows a red dashed line that separates them but runs close to a purple point. Step 2 shows the maximum-margin boundary as a glowing gold vertical line at feature 1 equals 0, with dashed margin lines at -1 and +1 and a shaded band between them. Two cyan points on the left edge and one purple point on the right edge are ringed as support vectors. feature 1feature 2 also separates widest margin support vectors are ringed Figure 1. Any line in the gap separates the training data; the SVM chooses the one with the widest empty band. The three ringed points on the band's edges are the support vectors. Move any other point (without crossing the band) and the boundary does not change.
  1. Many lines separate the classes The red dashed line makes no training errors, but it passes close to the purple point at (1, -0.2). A new purple point slightly to its left would be misclassified.
  2. The SVM picks the widest street The gold boundary sits midway between the classes with the widest possible band. Three points touch the edges of the band: they are the support vectors, and only they fix the boundary.

Step 2: Soft margin and C

Real data overlaps, so no line separates it perfectly. A soft marginAn SVM formulation that allows some points inside the margin or on the wrong side, paying a penalty for each, controlled by the parameter C. lets points violate the band at a cost. The parameter C sets the price of each violation:

  • Small C: violations are cheap. The SVM prefers a wide margin and tolerates many points inside it. Smoother, more regularized, more support vectors.
  • Large C: violations are expensive. The SVM narrows the margin to classify more training points correctly. Closer fit, higher risk of overfitting.

On overlapping clusters in the code below, raising C from 0.01 to 100 shrinks the margin width from 2.96 to 1.23 and the number of support vectors from 104 to 42, while training accuracy barely moves. C plays the same role as the inverse regularization strength in logistic regression.

Step 3: When a line is not enough, lift the data

Take points on a line: one class in the middle, the other on both sides. No single cut point separates them. Now add a second feature, x^2. Each point moves up onto a parabola, the outer points rise higher than the inner ones, and a horizontal line separates them perfectly.

Lifting data into a higher dimension Step 1: twelve points on a horizontal axis, six cyan in the middle between -0.8 and 0.85 and six purple on both sides beyond 1.6 in absolute value. Step 2: the same points placed on the dashed parabola y = x squared; the purple points rise above 2.5 while cyan stay below 0.75, and a glowing horizontal line at 1.6 separates them. -2-10120246xx squared (new feature) a straight line separates no single cut on x works Figure 2. Points that no single cut can separate in one dimension become linearly separable after adding the feature x squared. The same idea, in 2D, turns a ring around a blob into a bowl that a flat plane can slice.
  1. One feature: not separable Cyan points sit in the middle, purple points on both sides. Any single threshold on x leaves purple points on both sides of it.
  2. Add x squared: separable Plot each point at (x, x squared). The purple points rise above 2.5, the cyan ones stay below 0.75, and the horizontal line at 1.6 separates them. In the original x space that line is two cut points, a curved boundary.

Step 4: The kernel trick

Lifting works, but explicitly building many new features is expensive: all pairwise products of 1,000 features is half a million new columns. The SVM's training and predictions only ever need dot products between pairs of points. A kernelA function K(a, b) that equals the dot product of a and b after some feature mapping, computed without building the mapped features explicitly. computes that dot product in the lifted space directly from the original features, without building the lifted features. This shortcut is the kernel trickReplacing every dot product in an algorithm with a kernel function, so the algorithm works in a high-dimensional feature space at the cost of the original one..

  • Polynomial kernel: K(a, b) = (a . b + 1)^d equals a dot product over all feature products up to degree d.
  • RBF kernel: K(a, b) = exp(-gamma ||a - b||^2). A similarity score that is 1 for identical points and falls toward 0 with distance. It corresponds to an infinite-dimensional lift and can draw almost any smooth boundary. gamma sets how far each point's influence reaches: small gamma gives smooth boundaries; large gamma gives tight blobs around each training point and overfits.

The prediction for a new point is a weighted sum of kernel similarities to the support vectors, sum of alpha_i y_i K(x_i, x) + b, where only support vectors have nonzero alpha_i.

Try it

This interactive needs JavaScript. The diagrams and text above cover the same idea.

Try this:

  1. On "two clusters" with a linear kernel, count the ringed support vectors. Then lower C to 0.01: the band widens and swallows more points, and every point inside it becomes a support vector.
  2. Switch to "ring around a blob". The linear kernel cannot do it: training errors stay high. Switch to RBF and watch a closed boundary appear.
  3. With RBF on the ring, push gamma to its maximum. The boundary shrinks into small islands around individual points: the classic overfit.

Going deeper

Code: C, kernels and gamma

svm.pyruns with python3 + numpy + scikit-learn
import numpy as np
from sklearn.datasets import make_blobs, make_circles
from sklearn.model_selection import train_test_split
from sklearn.svm import SVC

# Two overlapping blobs: how C changes the margin
X, y = make_blobs(n_samples=200, centers=[[-1.5, 0], [1.5, 0]], cluster_std=1.0, random_state=0)
print("    C   support vectors   margin width   train acc")
for C in [0.01, 0.1, 1, 100]:
    m = SVC(kernel="linear", C=C).fit(X, y)
    width = 2 / np.linalg.norm(m.coef_)
    print(f"{C:>5}   {m.n_support_.sum():>15}   {width:>12.2f}   {m.score(X, y):.3f}")

# A ring around a blob: no straight line can separate it
X, y = make_circles(n_samples=400, factor=0.4, noise=0.1, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.5, random_state=0)
print("\nkernel        test acc")
for name, m in [("linear", SVC(kernel="linear")),
                ("poly deg 2", SVC(kernel="poly", degree=2, coef0=1)),
                ("rbf", SVC(kernel="rbf", gamma=1))]:
    print(f"{name:<12}  {m.fit(Xtr, ytr).score(Xte, yte):.3f}")

# The lift by hand: add r^2 = x1^2 + x2^2 as a third feature, then a LINEAR SVM works
lift = lambda A: np.column_stack([A, (A ** 2).sum(axis=1)])
m = SVC(kernel="linear").fit(lift(Xtr), ytr)
print(f"linear on (x1, x2, x1^2 + x2^2): {m.score(lift(Xte), yte):.3f}")

print("\nRBF gamma   train acc   test acc   support vectors")
for g in [0.1, 1, 10, 100]:
    m = SVC(kernel="rbf", gamma=g).fit(Xtr, ytr)
    print(f"{g:>9}   {m.score(Xtr, ytr):.3f}       {m.score(Xte, yte):.3f}      {m.n_support_.sum()}")

Output

    C   support vectors   margin width   train acc
 0.01               104           2.96   0.915
  0.1                56           1.75   0.910
    1                45           1.36   0.915
  100                42           1.23   0.910

kernel        test acc
linear        0.615
poly deg 2    1.000
rbf           1.000
linear on (x1, x2, x1^2 + x2^2): 1.000

RBF gamma   train acc   test acc   support vectors
      0.1   0.890       0.845      186
        1   1.000       1.000      35
       10   1.000       1.000      52
      100   1.000       0.995      154

On the ring data, a linear SVM gets 0.615 test accuracy, barely better than guessing. A degree-2 polynomial kernel and an RBF kernel both reach 1.000, and so does a plain linear SVM once you add the feature x1^2 + x2^2 by hand: the kernel is doing exactly that lift for you. The gamma table shows the other side: at gamma = 0.1 the boundary is too smooth (0.845 test), and at gamma = 100 the model needs 154 of 200 training points as support vectors and test accuracy starts to slip.

Practical notes

  • Scale features first. Both the margin and the RBF distance are measured in feature units.
  • Tune C and gamma together on a log grid with cross-validation ( Hyperparameter tuning ).
  • Kernel SVM training scales between quadratically and cubically with the number of examples, so it is comfortable up to tens of thousands of rows, not millions. Linear SVMs scale much further.
  • SVMs output distances, not probabilities. scikit-learn's probability=True fits a calibration on top ( Probability calibration ).

Trade-offs

OptionWins whenLoses when
Linear SVM High-dimensional sparse data such as text, where classes are nearly linearly separable Curved boundaries; you need probabilities directly
RBF SVM Small to medium datasets with complex boundaries Hundreds of thousands of rows; C and gamma need careful tuning
Logistic regression You need calibrated probabilities and simple weights You want the margin's robustness without probability modelling
Gradient boosted trees Large tabular data with mixed feature types Smooth geometric boundaries in a few continuous features

Common mistakes

  • Running an RBF SVM on unscaled features, so one feature's units decide every distance.
  • Tuning C with gamma fixed (or the reverse); they interact and should be searched together.
  • Training a kernel SVM on millions of rows and waiting hours; use a linear model or trees instead.
  • Treating decision_function outputs as probabilities.
  • Reading "only support vectors matter" as "the other data was useless"; it was needed to find which points are the support vectors.

In the wild

Before deep learning took over images and text, kernel SVMs were among the best general-purpose classifiers, used widely for text categorisation, handwritten digit recognition and bioinformatics, where datasets are small and features are many. Linear SVMs remain a standard tool for large sparse text problems, and the kernel idea lives on in Gaussian processes and other kernel methods.

Check yourself

  1. You delete a training point that is far from the boundary and outside the margin. What happens to a trained SVM's boundary?

    Show answer

    B. Nothing: only support vectors define it Points outside the margin have zero weight (alpha = 0) in the solution. Only support vectors, on or inside the margin, shape the boundary.

  2. An SVM with C = 1000 has a very narrow margin and 100 percent training accuracy, but poor validation accuracy. What should you try?

    Show answer

    B. Decrease C to allow a wider, softer margin Large C makes violations expensive, so the SVM contorts itself to fit every training point. Smaller C trades a few training errors for a wider, more robust margin.

  3. What does the kernel trick avoid?

    Show answer

    B. Building the high-dimensional features explicitly; the kernel gives their dot products directly The algorithm only needs dot products between points, and a kernel computes those for the lifted space from the original features.

  4. With an RBF kernel, raising gamma very high makes the boundary...

    Show answer

    B. Tight islands around individual training points, which overfits Large gamma makes each point's influence very local, so the boundary wraps around individual points. Training accuracy is high, generalisation suffers.

Recap

  • An SVM picks the separating boundary with the widest margin; the margin width is 2 / ||w||.
  • Only support vectors, the points on or inside the margin, determine the boundary.
  • C sets the price of margin violations: small C means wide, tolerant margins; large C fits training data tightly.
  • Kernels compute dot products in a lifted feature space, letting a linear method draw curved boundaries.
  • Scale features and tune C with gamma together; kernel SVMs suit small to medium datasets.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy

Next up