Support Vector Machines and Kernels Explained: Margins, Duals, RBF

Imagine two clouds of points, and you must draw a line between them. There are infinitely many lines that separate the classes perfectly on the training set. So which one should you pick? Today we answer that with one of the most elegant ideas in machine learning, the Support Vector Machine.

• Many lines separate the data
• Only one is the safest

Last time, we combined many trees into random forests and boosted models, and explained them with SHAP. This time we leave trees behind and think geometrically. By the end you will derive the margin formula, solve a tiny SVM by hand, understand the kernel trick, and verify everything in scikit-learn.

• Episode 20: ensembles
• Today: margins and kernels

Here is our route. First the max-margin intuition and the formula for the margin. Then hard and soft margins with hinge loss. Next Lagrange multipliers from scratch, which unlock the dual form, and from the dual the kernel trick. We finish with regression, tuning, and code.

• Margin and support vectors
• Lagrange and the dual
• Kernels, SVR, tuning

Think of driving down a road with obstacles on both sides. The safest path is down the middle, as far as possible from everything. A classifier works the same way. We choose the boundary that leaves the widest empty street between the two classes, and that street is called the margin.

• Boundary far from both classes
• Wider gap, more robust

Why does a wide margin help? New data is never exactly like training data, it is jittered by noise. A boundary hugging the training points will misclassify a slightly shifted neighbor. A boundary with a big margin tolerates that jitter, and this is the intuition behind its good generalization.

• New points are noisy
• Margin gives wiggle room

Here is the surprising part. Only the points sitting exactly on the edge of the margin matter. We call them support vectors. If you delete every other point, the boundary does not move at all. Move a support vector, and the whole street shifts. The model is defined by a handful of critical examples.

• Closest points define the margin
• Other points do not matter

To work with this we need a formula. A line, or in higher dimensions a hyperplane, is the set of points x where w dot x plus b equals zero. The vector w is perpendicular to the hyperplane and b shifts it. The prediction is the sign of w dot x plus b, positive means one class and negative means the other. We label classes as plus one and minus one.

• w dot x plus b equals 0
• w is perpendicular to the line

How far is a point from the hyperplane? Project the point onto the direction of w, the unit normal. That gives the absolute value of w dot x plus b, divided by the length of w. For example, with w equals three four, so length five, and b equals minus five, the point two comma one gives six plus four minus five, which is five, divided by five, so distance one.

• distance = |w·x + b| / ||w||
• Sign tells the side

There is a redundancy. Multiplying both w and b by ten describes exactly the same line. So we are free to pick a scale. We choose it so the closest points on each side give w dot x plus b equal to plus one or minus one. That convention, called the canonical form, makes the algebra clean.

• Scaling w and b changes nothing
• Choose w·x + b = ±1 on the edges

Let x plus lie on the upper edge and x minus on the lower edge, directly across along w. Then w dot x plus plus b equals one, and w dot x minus plus b equals minus one. Subtract the second from the first, and the b cancels, leaving w dot the difference vector equals two. That is the key identity.

• Subtract the two edge equations
• w·(x+ − x−) = 2

Since the two points are across from each other along the normal, their difference is some multiple lambda of w. Plug in, and lambda times w dot w equals two, so lambda equals two over the squared norm of w. The length of the difference is lambda times the norm, which is two divided by the norm of w. The margin width is two over the norm of w.

• Difference = λw
• λ‖w‖² = 2, width = 2/‖w‖

Check the intuition with numbers. If the norm of w is four, the margin is one half. If it is two, the margin is one. If the norm is one, the margin is two. So making the street wider means making w shorter. Maximizing the margin is the same as minimizing the norm of w.

• Big ‖w‖ means thin street
• Small ‖w‖ means wide street

We can now state the hard-margin SVM. Minimize one half the squared norm of w, subject to y sub i times the quantity w dot x sub i plus b being at least one, for every training point. The constraint says every point is correctly classified and outside the street. The one half and the square are only there to make derivatives tidy.

• Minimize ½‖w‖²
• Subject to y(w·x + b) ≥ 1

This problem is a convex quadratic program. The objective is a bowl, and the constraints are straight cuts. That means there are no bad local minima, there is exactly one best answer. This is a major advantage over neural networks, and it is why SVMs were so popular for years.

• Bowl-shaped objective
• One global optimum

Let's solve a tiny problem by hand. One dimension, two points. The point x equals one has label minus one, and x equals three has label plus one. Our eyes say the boundary sits at two. Let's get the machine to confirm it.

• x = 1 has label −1
• x = 3 has label +1

Both points will touch the margin, so both constraints are tight. For the first point, minus one times w plus b equals one, which means w plus b equals minus one. For the second, three w plus b equals one. Subtract, and two w equals two, so w is one and b is minus two. The boundary is x minus two equals zero, at x equals two, and the margin is two over one, which is two.

• w + b = −1 and 3w + b = 1
• w = 1, b = −2, margin = 2

To handle these constraints we need a classic tool from calculus, Lagrange multipliers. Suppose we want the smallest value of x squared plus y squared, but we are only allowed to stand on the line x plus y equals one. We cannot just set derivatives to zero, because the true minimum at the origin is not allowed.

• Need a tool for constrained optimization
• Idea: fold constraints into the objective

Here is the geometry. Walk along the line, and the contours of f get crossed until you reach a point where a contour just touches the line. At that point the gradient of f is parallel to the gradient of the constraint. So we write that the gradient of f equals lambda times the gradient of g, where lambda is the Lagrange multiplier.

• At the optimum, tangent contours
• ∇f = λ∇g

Build the Lagrangian: L equals x squared plus y squared minus lambda times x plus y minus one. Differentiate with respect to x to get two x minus lambda, and with respect to y to get two y minus lambda. Both zero means x equals y equals lambda over two. The constraint x plus y equals one then gives x equals y equals one half, and the minimum value is one half.

• L = x² + y² − λ(x + y − 1)
• x = y = 1/2, minimum = 1/2

SVM constraints are inequalities, not equalities. For these, each multiplier must be greater than or equal to zero. If the optimum lies strictly inside the allowed region, the constraint is inactive and its multiplier is zero. If the optimum is pushed against the wall, the constraint is active and its multiplier is positive.

• Multipliers must be ≥ 0
• Active or inactive constraints

Now apply this to the SVM. Give each training point its own multiplier alpha sub i, which must be at least zero. The Lagrangian is one half the squared norm of w, minus the sum over i of alpha i times the quantity y i times w dot x i plus b, minus one. We minimize over w and b, and maximize over alpha.

• One multiplier α per training point
• L = ½‖w‖² − Σ α[y(w·x+b) − 1]

Take the derivative with respect to w and set it to zero. We get w minus the sum of alpha i y i x i equals zero, so w is a weighted sum of the training points. Take the derivative with respect to b, and we get that the sum of alpha i times y i equals zero. Notice w is built from the data itself.

• ∂L/∂w = 0 gives w = Σ α y x
• ∂L/∂b = 0 gives Σ α y = 0

Substitute w back into the Lagrangian. The b term vanishes because the sum of alpha y is zero, and the w terms collapse into a double sum. What remains depends only on the alphas: the sum of alpha i, minus one half times the double sum of alpha i, alpha j, y i, y j, and the dot product of x i with x j.

• Eliminate w and b
• Only alphas remain

This is the dual problem. Maximize that expression over alpha, subject to each alpha being non-negative and the sum of alpha times y being zero. Look closely at where the data appears. It appears only through dot products between pairs of points. Remember this, because it is the secret behind kernels.

• Maximize over α
• α ≥ 0 and Σ α y = 0

Return to our two points. The constraint forces alpha one to equal alpha two, call it a. Now the double sum: the pair one-one gives one, the pair three-three gives nine, and the two cross pairs give minus three each. The total is four. The dual objective becomes two a minus one half times four a squared, which is two a minus two a squared.

• α1 = α2 = a
• Objective: 2a − 2a²

Maximize two a minus two a squared. The derivative is two minus four a, so a equals one half. Now recover w as the sum of alpha y x: minus one half times one, plus one half times three, which equals one. For b, use a support vector: three times one plus b equals one, so b is minus two. Same answer as before.

• Maximum at a = 1/2
• w = 1, b = −2

The optimality conditions, called KKT, include complementary slackness. Each alpha times its constraint slack must be zero. So a point strictly outside the margin has alpha zero. Only support vectors have positive alpha. Predictions are the sign of the sum over support vectors of alpha i y i times x i dot x, plus b.

• α > 0 only on support vectors
• Prediction uses only support vectors

Hard margins have a fatal flaw. If the classes overlap even slightly, no perfect separating line exists and the problem has no solution. Even when one does exist, a single mislabeled outlier can force a tiny margin. Real data is messy, so we need to allow some mistakes.

• Hard margin fails on overlap
• Outliers can wreck the boundary

We introduce a slack variable xi for each point, measuring how far it violates the margin. Constraints relax to y times w dot x plus b being at least one minus xi, with xi at least zero. The objective becomes one half the squared norm of w, plus C times the sum of slacks. The parameter C sets the price of each violation.

• ξ ≥ 0 measures violation
• Minimize ½‖w‖² + C Σ ξ

Eliminating the slack gives a loss function. The hinge loss is the maximum of zero and one minus y times f of x, where f is w dot x plus b. If the point is correct and beyond the margin, the loss is exactly zero. Inside the street or on the wrong side, the loss grows linearly. Compare this with logistic loss, which never quite reaches zero.

• loss = max(0, 1 − y f(x))
• Zero beyond the margin

Let's compute some. A positive point with f equal to two has y f equal to two, so loss is max of zero and minus one, which is zero. With f equal to zero point five, the loss is zero point five. A positive point scored as minus one has y f equal minus one, and a loss of two. Note a correct point inside the margin still pays.

• y f = 2 gives 0
• y f = 0.5 gives 0.5, y f = −1 gives 2

C is the dial between margin and mistakes. A large C punishes violations heavily, so the model narrows the margin to fit every training point, risking overfitting. A small C tolerates violations, giving a wider and smoother boundary, risking underfitting. In the soft dual, the only change is that each alpha is capped: zero to C.

• Large C: narrow margin, few errors
• Small C: wide margin, more errors

What if the data is not linearly separable at all? Picture a cluster of blue points surrounded by a ring of orange ones. No straight line can split them. Yet the problem looks easy to a human, which suggests that we are simply looking at it from the wrong space.

• Ring-shaped classes
• No line separates them

Here is a 1D example. Blue points sit at minus one, zero and one, and orange at minus three and three. No single threshold separates them. Now map each x to the pair x and x squared. Blue points rise to heights one, zero and one, while orange points rise to height nine. A horizontal line at height four now separates them perfectly.

• Map x to (x, x²)
• Curved becomes straight

Mapping into higher dimensions works, but explicit feature maps get expensive fast. Polynomial features of high degree on many inputs create an enormous number of columns. Some useful maps are infinite dimensional, which cannot be stored at all. We need a way to get the benefit without paying the cost.

• Explicit features explode
• Dimension can be huge or infinite

Remember that the dual only touches the data through dot products. So we replace x i dot x j with a kernel function K of x i and x j, which equals the dot product of the mapped features phi of x i and phi of x j. We compute that number directly, without ever building phi. This is the kernel trick.

• Dual uses only dot products
• K(x, z) = φ(x) · φ(z)

Take the polynomial kernel, x dot z plus one, squared, with x equal to one two and z equal to three one. The dot product is three plus two, which is five. Add one to get six, and square it to get thirty-six. Expanding it, this equals a dot product of six-dimensional feature vectors that include squares and cross terms, and that also gives thirty-six.

• K(x,z) = (x·z + 1)²
• Equals a dot product in 6 dimensions

The most popular choice is the RBF, or Gaussian, kernel: e to the minus gamma times the squared distance between x and z. It is one for identical points and fades toward zero for distant ones. With our earlier points the squared distance is five. Using gamma equals one half, the exponent is minus two point five, and the kernel value is about zero point zero eight two.

• K(x,z) = exp(−γ‖x − z‖²)
• Similarity between 0 and 1

With an RBF kernel, the decision function is a weighted sum of bumps, one centered on each support vector. Positive bumps pull the score up and negative bumps push it down. The boundary is where the total crosses zero. On our ring data, this produces a smooth closed curve around the center cluster.

• Prediction is a sum of bumps
• Flexible, curved boundaries

Gamma controls how far each point's influence reaches. A small gamma makes wide, gentle bumps and a nearly linear boundary. A large gamma makes very narrow bumps, so the boundary wraps tightly around individual points, which is classic overfitting. Gamma and C interact, so they must be tuned together.

• Large γ: narrow bumps, overfit
• Small γ: wide bumps, smooth

Not every function is a legal kernel. The matrix of all pairwise kernel values must be positive semidefinite, meaning its eigenvalues are never negative. That is exactly the idea from our linear algebra episode, and it guarantees a feature space exists and the optimization stays convex. Linear, polynomial, and RBF kernels all satisfy this.

• Gram matrix must be positive semidefinite
• Mercer's condition

Support vector regression carries the same idea over to predicting numbers. We fit a function and draw a tube of half-width epsilon around it. Errors smaller than epsilon cost nothing. Points outside the tube are penalized linearly. As before, only points on or outside the tube become support vectors, and kernels work here too.

• Errors inside ε cost nothing
• Only points outside the tube matter

The objective is one half the squared norm of w, plus C times the slack above and below the tube. The loss is the maximum of zero and the absolute residual minus epsilon. With epsilon zero point five, a residual of zero point three costs nothing, zero point five also costs nothing, and one point two costs zero point seven. Larger epsilon gives a sparser, simpler model.

• Minimize ½‖w‖² + C Σ(ξ + ξ*)
• Epsilon-insensitive loss

One of the most common mistakes is skipping feature scaling. SVMs rely on distances and dot products, so a feature measured in thousands will drown out a feature measured in fractions. Standardize every feature to zero mean and unit variance, and fit the scaler on the training data only, ideally inside a pipeline, to avoid leakage.

• Margins use distances
• Standardize before fitting

To tune, search C and gamma on logarithmic grids, such as zero point one, one, ten, one hundred, and gamma from zero point zero zero one up to ten. Score each pair with cross-validation, never on the test set. The good region often forms a diagonal ridge, because large C with large gamma overfits, and small values of both underfit.

• Search on a log scale
• Use cross-validation

Some practical notes. Kernel SVMs get slow as the number of training samples grows, roughly between quadratic and cubic in the worst case, so for very large datasets a linear SVM is the practical choice. Also, an SVM outputs scores, not probabilities. Scikit-learn can fit a calibration step on top if you request probabilities, at extra cost.

• Training cost grows with samples
• Probabilities need extra calibration

Time to verify our hand calculation. Fit scikit-learn's SVC with a linear kernel on the points one and three, with a huge C to mimic a hard margin. The coefficient prints as one and the intercept as minus two. Both points are support vectors, and the dual coefficients, which are alpha times y, are minus zero point five and plus zero point five. Exactly what we derived.

• SVC(kernel='linear', C=1e10)
• coef = 1, intercept = −2

In practice, build a pipeline with a standard scaler followed by an SVC with an RBF kernel. Wrap it in a grid search over C and gamma with five-fold cross-validation. Because scaling lives inside the pipeline, each fold fits the scaler only on its own training portion, so there is no leakage. For regression, swap in SVR and also tune epsilon.

• StandardScaler then SVC
• GridSearchCV over C and gamma

Let's collect the common mistakes. Forgetting to scale features. Using default C and gamma without tuning. Tuning on the test set. And reaching for a kernel SVM on millions of rows. Avoid these, and an SVM remains a strong choice, especially for medium-sized datasets with many features.

• Forgetting to scale
• Tuning on the test set
• Using kernels on huge data

Let's recap. The best boundary maximizes the margin, which is two over the norm of w, so we minimize one half the squared norm. Only support vectors matter. Lagrange multipliers give the dual, where data appears only in dot products. Soft margins add slack, hinge loss, and the parameter C. Kernels like polynomial and RBF bend the boundary, controlled by gamma. And always scale and tune.

• Margin = 2/‖w‖, support vectors
• Dual, kernels, C, gamma

So far, every model had labels to learn from. In the next episode, we remove the labels and ask the data to organize itself, with k-means, hierarchical clustering, DBSCAN, and Gaussian mixtures.

• Episode 22: no labels at all
• k-Means, DBSCAN, GMM