The SVM Dual and the Kernel Trick: The Math Explained Step by Step

Here is a strange claim. There is a classifier that can work in a feature space with infinitely many dimensions, and it never computes a single coordinate in that space. It is the support vector machine, and the magic behind it is two ideas: the dual problem and the kernel trick. Today we derive both, with real numbers.

• Work in infinite dimensions
• Never compute a coordinate

In lesson 21 we met the picture: a separating line with the widest possible margin. We will not redraw it here. In lesson 37 we learned Lagrange multipliers and the KKT conditions, and in the last lesson we studied gradient boosting. Today we use that optimization toolkit to open up the support vector machine and see why it works so well with kernels.

• Lesson 21: margin geometry
• Lesson 37: Lagrange and KKT
• Today: the algebra

The hard-margin primal problem says: minimize one half of 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 labels y are plus one or minus one. The margin width is two divided by the norm of w, so shrinking the norm widens the margin. This is a convex quadratic objective with linear constraints.

• Minimize half norm w squared
• Subject to y(w·x+b) ≥ 1

Why not solve the primal directly? Because the primal lives in the space of w, whose size equals the number of features. The dual lives in the space of one multiplier per training example, and, crucially, it touches the data only through inner products. That single property is what will make kernels possible.

• Primal depends on w directly
• Dual depends on inner products

From lesson 37, we attach a multiplier alpha sub i, which must be greater than or equal to zero, to each inequality constraint. The Lagrangian is one half the squared norm of w, minus the sum over i of alpha sub i times the quantity y sub i times w dot x sub i plus b, minus one. A violated constraint now costs us, and the multipliers decide how much.

• One multiplier alpha_i per point
• alpha_i ≥ 0

Now set the gradient with respect to w to zero. The derivative of one half w dot w is w, and the constraint terms give minus the sum of alpha y x. So w equals the sum over i of alpha sub i, y sub i, x sub i. The weight vector is just a weighted combination of training points. Setting the derivative with respect to b to zero gives a second condition: the sum of alpha sub i times y sub i is zero.

• ∂L/∂w = 0 gives w = Σ α_i y_i x_i
• ∂L/∂b = 0 gives Σ α_i y_i = 0

Think of each training point as pulling on w with strength alpha sub i, in the direction of its label times its position. Most points will turn out to have alpha equal to zero, so they have no say at all. Only a handful of points build the entire solution. Hold that thought, because it is the definition of support vectors.

• Points with alpha zero vanish
• Others pull w toward them

Substitute w back into the Lagrangian. The first term becomes one half of a double sum of alpha i, alpha j, y i, y j, and x i dot x j. The constraint term produces the same double sum with a minus sign, plus the sum of alphas. The b term vanishes because the sum of alpha y is zero. Collecting what remains gives something remarkably clean.

• Plug w into L
• b term vanishes by Σ α y = 0

The dual problem is: maximize the sum of alpha sub i, minus one half times the double sum of alpha i, alpha j, y i, y j, and x i dot x j. The constraints are that every alpha is non-negative, and the sum of alpha y is zero. Look at the data: it appears only inside x i dot x j. The whole problem depends on the Gram matrix of pairwise inner products.

• Max Σα_i − ½ ΣΣ α_i α_j y_i y_j x_i·x_j
• α_i ≥ 0, Σ α_i y_i = 0

Because the primal is convex with linear constraints, strong duality holds: the best dual value equals the best primal value. Once we have the alphas, predictions also use only inner products. The decision function is the sum of alpha i, y i, times x i dot x, plus b. New points are compared to training points, never expanded into coordinates.

• Convex problem: dual optimum equals primal
• f(x) = Σ α_i y_i x_i·x + b

Let us solve one by hand. Three points in two dimensions. Point one is at two, zero, with label plus one. Point two is at the origin with label minus one. Point three is at three, two, with label plus one. By eye, a vertical line between the first two points looks right.

• x1=(2,0), y=+1
• x2=(0,0), y=−1
• x3=(3,2), y=+1

First compute inner products. Point one with itself is two times two, which is four. Point one with point two is zero, and point two with itself is zero. Point three has inner products six with point one, zero with point two, and thirteen with itself. We guess that point three is not a support vector, so its alpha is zero, and we will verify that afterwards.

• x1·x1 = 4
• x1·x2 = 0, x2·x2 = 0

With alpha three set to zero, the constraint says alpha one minus alpha two equals zero, so both equal a single number alpha. The objective is alpha plus alpha, minus one half times alpha squared times four, which simplifies to two alpha minus two alpha squared. Its derivative, two minus four alpha, vanishes at alpha equals one half. The dual value there is one half.

• Constraint: α1 − α2 + α3 = 0
• Objective: 2α − 2α²
• α = 0.5

Now recover w. It equals one half times two, zero, minus one half times zero, zero, which is one, zero. For b, use a support point: label plus one at point one gives one times the quantity two plus b equals one, so b is minus one. The line is x one equals one, and the margin width is two over the norm of w, which is two. The primal value, one half the squared norm of w, is one half, matching the dual exactly.

• w = 0.5(2,0) − 0.5(0,0) = (1,0)
• b = −1
• Margin = 2

Does point three respect the margin? The score is one times three, plus zero times two, minus one, which is two. Multiplied by its label, that is two, comfortably above one. The constraint is slack, so setting its multiplier to zero was legitimate. All KKT conditions hold, so this solution is optimal.

• f(x3) = 3 − 1 = 2
• y·f = 2 > 1: inactive
• α3 = 0 is consistent

This is complementary slackness from lesson 37. For every point, alpha sub i times the quantity y sub i f of x sub i minus one equals zero. So either alpha is zero, or the point sits exactly on the margin. Points with positive alpha are the support vectors. Delete every other point and the solution does not change at all.

• α_i [y_i f(x_i) − 1] = 0
• Either α_i = 0 or on the margin

A common mistake is to maximize the dual while forgetting the equality constraint, or using labels zero and one instead of minus one and plus one. Without the constraint, in our example the objective could grow without bound along some directions, and the answer is meaningless. The equality constraint is what keeps the bias term b consistent. Always check that your alphas satisfy it.

• Ignoring Σ α y = 0 gives wrong α
• Labels must be plus or minus one

Real data overlaps, and the hard-margin problem then has no solution at all. The soft-margin fix gives each point a slack variable xi sub i, at least zero, measuring how far it violates the margin. The constraint becomes y sub i times f of x sub i is at least one minus xi sub i. Violations are allowed, but they will cost us.

• Hard margin fails on overlap
• Allow slack ξ_i ≥ 0

The soft-margin objective is one half the squared norm of w, plus C times the sum of the slacks. The hyperparameter C sets the price of a violation. A huge C behaves almost like the hard margin, fitting every point, and risks overfitting. A small C tolerates many violations and gives a wider, smoother margin.

• min ½‖w‖² + C Σ ξ_i
• Large C: strict, small C: wide

Here is the neat part. Carry out the same Lagrangian derivation, and the dual objective is identical. Only one thing changes: each alpha must now lie between zero and C. That upper bound arises because the slack multiplier is also non-negative. The dual becomes a quadratic program in a box, which is why we call this the box constraint.

• Dual is the same, except 0 ≤ α_i ≤ C
• Σ α_i y_i = 0 stays

Complementary slackness now sorts points into three groups. Points beyond the margin have alpha zero. Points sitting exactly on the margin have alpha strictly between zero and C. Points inside the margin, or on the wrong side, have alpha equal to C. All points with positive alpha are support vectors, and a tighter C means more of them sit at the cap.

• α = 0: outside margin
• 0 < α < C: on margin
• α = C: inside or misclassified

At the optimum, each slack equals the smallest value allowed: the maximum of zero and one minus y f of x. That is exactly the hinge loss. Check a few values: a score of two with label plus one costs zero. A score of zero point three costs zero point seven. A score of minus zero point five costs one point five. So the SVM is hinge loss plus an L2 penalty, with C playing the inverse role of the regularization strength.

• ξ_i = max(0, 1 − y_i f(x_i))
• Same as regularized hinge loss

Compare this with logistic loss from lesson 15. Logistic loss never reaches zero, so every point always contributes a little gradient. Hinge loss is exactly zero once a point clears the margin, which is why only support vectors matter. Both are convex stand-ins for the unfriendly zero-one loss.

• Hinge vs logistic loss
• Hinge is exactly zero past the margin

Linear boundaries are limited. The classic fix is to map each input through a feature map phi, then run the SVM on phi of x. Points on a line, with one class in the middle, become separable when we add x squared as a second coordinate. The cost is that features can explode in number. This is where the dual shines.

• Map x to φ(x)
• Linear in φ, curved in x

The dual uses only inner products. So replace each x i dot x j with phi of x i dot phi of x j, and we are done. The kernel trick says: define a function K of x and z that returns that inner product directly, without ever building phi. Prediction becomes the sum of alpha i, y i, K of x i and x, plus b. We skip the coordinates entirely.

• K(x,z) = φ(x)·φ(z)
• Replace x_i·x_j by K(x_i,x_j)

Let us prove one. In two dimensions, take K of x and z equal to x dot z, squared. Expand: x one z one plus x two z two, squared, gives x one squared z one squared, plus two x one x two z one z two, plus x two squared z two squared. That is the dot product of phi of x, equal to x one squared, root two times x one x two, x two squared, with the same map applied to z.

• K(x,z) = (x·z)²
• φ(x) = (x₁², √2 x₁x₂, x₂²)

Take x equal to one, two and z equal to three, one. The dot product is three plus two, which is five, and squared that is twenty-five. Now the long way. Phi of x is one, two root two, four. Phi of z is nine, three root two, one. The products are nine, twelve, and four, which sum to twenty-five. Same answer, and the kernel took one multiplication-and-square instead of a trip through feature space.

• x=(1,2), z=(3,1)
• Kernel: 5² = 25
• Features: 9 + 12 + 4 = 25

This saving grows fast. A polynomial of degree p over d inputs has a number of monomial features that grows roughly like d to the power p. The kernel, x dot z plus one, raised to the power p, costs about d operations plus one power. The price we pay is that training now scales with the number of examples, through the n by n Gram matrix, instead of with the feature dimension.

• Degree p in d dims: huge feature count
• Kernel costs O(d)

The most popular kernel is the radial basis function kernel: K of x and z equals e to the minus gamma times the squared distance between x and z. It equals one when the points coincide, and decays toward zero as they move apart. Check: with gamma one half, x equal to one and z equal to two, the squared distance is one, so the kernel is e to the minus one half, about zero point six one. Gamma controls how local the similarity is.

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

Why is this infinite-dimensional? Expand the squared distance, and the kernel factors into e to the minus gamma norm x squared, times the same for z, times e to the two gamma x dot z. Now expand that last exponential as a Taylor series: one, plus two gamma x dot z, plus half of that squared, and so on forever. Each term is a polynomial kernel of higher degree, and each has its own feature map. Stacking them gives a feature map with infinitely many coordinates, and yet the kernel is one cheap exponential.

• Factor out norms
• Expand exp(2γ x·z) as a series

Can any function be a kernel? No. Mercer's condition, at an intuition level, says K must be symmetric, and for any set of points the Gram matrix must be positive semi-definite, as in lesson 5. When that holds, a feature map phi exists, even if we cannot write it down. If it fails, the dual may stop being concave and the optimizer can misbehave, so use known valid kernels or combinations like sums and products of them.

• Gram matrix must be symmetric PSD
• Then a feature map φ exists

With the RBF kernel, two knobs matter. A large gamma makes each point's influence tiny, so the boundary wraps around individual points and overfits. A small gamma makes it nearly linear. Combined with C, you search both together using cross-validation, from lesson 24, on a logarithmic grid. Also scale your features first, since distances drive everything.

• High γ: wiggly, overfits
• Low γ: smooth, underfits
• Tune both with CV

The same ideas extend to regression. Support vector regression fits a function while ignoring errors smaller than epsilon, forming a tube around the prediction. The loss is the maximum of zero and the absolute residual minus epsilon. With epsilon equal to zero point five, a residual of zero point three costs nothing, and a residual of one point two costs zero point seven.

• Fit a tube of half-width ε
• No loss inside the tube

The SVR dual has two multipliers per point, alpha and alpha star, one for each side of the tube, both bounded between zero and C. The prediction is the sum of alpha minus alpha star, times the kernel, plus b. Points strictly inside the tube get both multipliers zero, so only points on or outside the tube are support vectors. A wider epsilon means a sparser model, and kernels work here exactly as before.

• Two multipliers: α_i and α_i*
• Points inside tube: both zero

Let us verify our hand solution with scikit-learn. Fit SVC with a linear kernel and a huge C, to mimic the hard margin, on our three points. The attribute dual underscore coef gives alpha times y: minus zero point five and plus zero point five, only two support vectors, and point three is absent. The weights come out as one, zero, and the intercept is minus one. Everything matches the pencil-and-paper result.

• SVC(kernel='linear', C=1e10)
• dual_coef_ = α·y
• Matches our hand solution

Do one more check with an RBF kernel. Compute the kernel between your new points and the stored support vectors, multiply by dual underscore coef, sum, and add the intercept. That matches decision underscore function exactly. This shows the model is literally a weighted list of similarities to its support vectors, and shows why prediction cost grows with their number.

• Rebuild f(x) from α, y, K
• Compare with decision_function

Let us recap. The hard-margin primal becomes a Lagrangian, which gives w as a sum of alpha y x, and a dual that uses only inner products. Complementary slackness shows that only support vectors have positive alpha. The soft margin adds the box constraint, which is hinge loss with an L2 penalty. Replacing inner products with kernels gives curved boundaries, from polynomial to infinite-dimensional RBF, and epsilon tubes carry the idea into regression.

• Primal → Lagrangian → dual
• Support vectors via slackness
• Kernels replace inner products

In the next lesson, we leave supervised learning behind and derive the Expectation-Maximization algorithm for Gaussian mixtures, the engine behind soft clustering. Thanks for watching, and I will see you in lesson 44.

• Next: lesson 44, EM for Gaussian mixtures
• Subscribe for the full course