Mathematical Foundations for Machine Learning

Support Vector Machines

Published: 2026-07-11

Level: postgraduate

Audience: Postgraduate students in Machine Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Vector spaces, rank, and linear independence — covered in Lecture 3 (Groups. Vector Spaces, and Linear Combinations) and Lecture 4 (Vector Spaces, Linear Independence, Basis and Dimension) Partial derivatives, the chain rule. And gradients — covered in Lecture 8 (Singular Value Decomposition and Vector Calculus) and Lecture 9 (Gradients, the Jacobian, and Taylor Series) Convexity and the Hessian matrix — covered in Lecture 10 (Taylor Series and Hessian-Based Optimization) and Lecture 12 (Challenges of Gradient Descent and Constrained Optimization) Gradient descent — covered in Lecture 11 (Gradient Descent) Taylor series — covered in Lecture 9 and Lecture 10; the exponential expansion underpins the RBF kernel's infinite-dimensional interpretation

20.1 Hard Margin SVM — Review

20.1.1 Maximizing the Margin

Hook. Imagine you are a city planner drawing a road to separate two neighborhoods. You could sketch the road right next to one neighborhood. — but then a single new house could land on the wrong side. What if you instead built the widest possible road, keeping it as far from both neighborhoods as possible? That road would survive small changes in house locations. SVM does the same thing with data.

Intuition. Think of a sheet of paper with red dots on one half and blue dots on the other. You lay a ruler between them. You can slide the ruler around and tilt it — many straight lines separate the dots. But one particular placement leaves the most breathing room on both sides. SVM finds that placement. The trick is to measure distance not to all dots. But only to the ones nearest the ruler — those are the support vectors.

Analogy — the widest street. Picture two rows of houses facing each other across an empty lot. You want to pave a street between them. If the street hugs one row. A new house built slightly closer to the other side could end up in the middle of the road. The safest street is the one whose edges are as far as possible from the nearest house on either side. That is exactly what the margin is: the width of the empty strip between the closest houses of the two classes.

Where the analogy breaks: real houses sit on a flat 2D lot. Data lives in

d

-dimensional space and the "street" is a

(d - 1)

-dimensional hyperplane. But the geometry works the same way — the margin is still the perpendicular distance between two parallel boundary planes.

Formal definition. A Support Vector Machine in its hard-margin form finds a hyperplane that separates two classes with the widest possible margin. The margin is the perpendicular distance from the separating hyperplane to the nearest data point on either side.

The hyperplane is written as:

w \cdot X + B = 0

where

w \in R^{d}

is the weight vector (a normal vector. — it points perpendicular to the hyperplane) and

B \in R

is the bias term (it shifts the hyperplane away from the origin). For any two points on the hyperplane, the vector between them is orthogonal to

w

The margin. Imagine three parallel planes with the same normal vector

w

Positive margin boundary:

w \cdot X + B = + 1

Decision boundary:

w \cdot X + B = 0

Negative margin boundary:

w \cdot X + B = - 1

We set the margin boundaries at

\pm 1

. This is a normalization choice — scaling

w

and

B

by the same factor leaves the decision boundary unchanged. So we have the freedom to pin the boundaries at

\pm 1

. This is called the canonical hyperplane convention.

The margin is the perpendicular distance between the two boundary planes. Let

X_{+}

be a point on the

+ 1

boundary and

X_{-}

be a point on the

- 1

boundary. The vector connecting them is

X_{+} - X_{-}

. Projecting this vector onto the unit normal

w /∥ w ∥

margin = \frac{∣ w ^{T} ( X _{+} - X _{-} ) ∣}{∥ w ∥} = \frac{∣ w ^{T} X _{+} - w ^{T} X _{-} ∣}{∥ w ∥}

Since

w^{T} X_{+} = 1 - B

and

w^{T} X_{-} = - 1 - B

= \frac{∣ ( 1 - B ) - ( - 1 - B ) ∣}{∥ w ∥} = \frac{∣1 - B + 1 + B ∣}{∥ w ∥} = \frac{2}{∥ w ∥}

So the margin is:

margin = \frac{2}{∥ w ∥}

where

∥ w ∥ = w \cdot w

is the Euclidean norm of

w

To maximize the margin

2/∥ w ∥

, you minimize

∥ w ∥

. For mathematical convenience, SVM minimizes

\frac{1}{2} ∥ w ∥^{2}

. The

\frac{1}{2}

factor makes derivatives cleaner. The square makes the objective strictly convex — the surface curves upward everywhere with exactly one minimum and no local traps.

Symbol registry:

Symbol	Meaning	Type	Domain
$w$	weight vector (normal to hyperplane)	$R^{d}$	any real $d$ -vector
$B$	bias term (intercept)	$R$	any real number
$X_{i}$	$i$ -th data point	$R^{d}$	any real $d$ -vector
$Y_{i}$	label of $i$ -th point	${- 1, + 1}$	$+ 1$ or $- 1$
$α_{i}$	Lagrange multiplier (penalty)	$[0, \infty)$	non-negative

20.1.2 The Primal Optimization Problem

You want every data point correctly classified and at least one unit away from the decision boundary. Multiply the signed output

w \cdot X_{i} + B

by the label

Y_{i}

If the point is on the correct side,

Y_{i} (w \cdot X_{i} + B) > 0

If the point is on the wrong side, the product is negative

The constraint

Y_{i} (w \cdot X_{i} + B) \geq 1

enforces two things at once: correct classification AND distance of at least 1 from the boundary. When

Y_{i} = + 1

, the constraint becomes

w \cdot X_{i} + B \geq 1

(point is at or beyond the positive boundary). When

Y_{i} = - 1

, it becomes

w \cdot X_{i} + B \leq - 1

(point is at or beyond the negative boundary).

Primal Hard-Margin SVM:

w, B min \frac{1}{2} ∥ w ∥^{2} subject to Y_{i} (w \cdot X_{i} + B) \geq 1, \forall i

This is a convex quadratic programming problem. The objective is quadratic (and strictly convex in

w

), and the constraints are linear in both

w

and

B

Scope. Hard-margin SVM applies only when:

The data is linearly separable — a hyperplane exists that perfectly splits the two classes. If the data is not separable, the feasible set is empty and no solution exists.No outliers contaminate the boundary — a single mislabeled point on the wrong side of the margin makes the problem infeasible. This is why soft-margin SVM (Section 20.4) exists.The classes are balanced enough that pushing the margin out evenly does not favor one class. When one class has far fewer examples, the margin may be dominated by the majority class's layout.

If you try hard-margin SVM on non-separable data, the optimization has no feasible solution — the constraints cannot all be satisfied. The solver will simply fail.

20.1.3 Lagrangian and Dual Formulation

To solve the constrained optimization, we use the method of Lagrange multipliers. Each constraint

Y_{i} (w \cdot X_{i} + B) - 1 \geq 0

gets a multiplier

α_{i} \geq 0

. The Lagrangian function is:

L (w, B, α) = \frac{1}{2} ∥ w ∥^{2} - i \sum α_{i} [Y_{i} (w \cdot X_{i} + B) - 1]

Think of each

α_{i}

as a fine levied by an inspector when a data point sits on or inside the margin. A zero fine means the point is safely outside. A positive fine means the point is "touching" the margin and matters.

Analogy — site inspector. Hire an inspector (

α_{i} \geq 0

) for each house. If the house is on the pavement or on the wrong side of the street, the inspector levies a fine. Your job: build the widest street possible while minimizing the total fines you pay. The Lagrangian combines both goals — widen the street (

\frac{1}{2} ∥ w ∥^{2}

) and avoid fines (

- \sum α_{i} [constraint satisfaction]

We find the stationary point by setting the partial derivatives to zero.

Derivative with respect to $w$ :

\frac{\partial L}{\partial w} = w - i \sum α_{i} Y_{i} X_{i} = 0 ⟹ w = i \sum α_{i} Y_{i} X_{i}

The optimal weight vector is a linear combination of the training data points. This is an instance of the representer theorem — the solution lies in the span of the data.

Derivative with respect to $B$ :

\frac{\partial L}{\partial B} = - i \sum α_{i} Y_{i} = 0 ⟹ i \sum α_{i} Y_{i} = 0

The weighted sum of labels must balance. The positive and negative influences cancel out.

Substituting back to get the dual. Replace

w

in the Lagrangian with

\sum_{i} α_{i} Y_{i} X_{i}

. The algebra (collecting terms, using

\sum_{i} α_{i} Y_{i} = 0

to drop the

B

-term. And simplifying the quadratic form) yields the dual problem:

α max i \sum α_{i} - \frac{1}{2} i \sum j \sum α_{i} α_{j} Y_{i} Y_{j} (X_{i} \cdot X_{j})

subject to:

α_{i} \geq 0 and i \sum α_{i} Y_{i} = 0

This is a simpler problem. The decision variables are now the

α_{i}

's — one per data point — instead of the

d

-dimensional

w

. The dual depends only on dot products between data points. No weight vector or bias appears directly. This dot-product dependency is the door the kernel trick walks through later (Section 20.6).

Visual intuition. Imagine a 2D scatter plot. The x-axis is feature

X_{1}

, the y-axis is feature

X_{2}

. Blue discs are the positive class, orange crosses are the negative class. The decision boundary is a straight line

w \cdot X + B = 0

. Two dashed lines parallel to it, at distances

+ 1

and

- 1

in the scaled coordinate system, mark the margin edges. The weight vector

w

points perpendicular to all three lines. The distance between the two dashed lines is

2/∥ w ∥

. A shorter

w

means a wider gap. The support vectors are the points that touch the dashed lines — typically just a few points. The ones closest to the boundary.

Pitfalls.

Forgetting the bias. Without the bias term

B

, the hyperplane must pass through the origin. This forces

w \cdot X = 0

for the decision boundary. In general, the data is not centered at the origin, and you need the bias to shift the boundary anywhere.Confusing the margin formula. The margin is

2/∥ w ∥

, not

1/∥ w ∥

. The factor of 2 comes from the two boundaries being at

+ 1

and

- 1

— total width is 2 units in the canonical scale.Scaling trap.

w

and

B

are defined only up to a scale factor. If you multiply both by 10, the decision boundary

w \cdot X + B = 0

stays the same, but

∥ w ∥

changes. The SVM convention fixes this by pinning the margin boundaries at

\pm 1

.Assumption of separability. Hard-margin SVM assumes perfect linear separability. Real data rarely satisfies this. If your solver returns "infeasible," switch to soft-margin SVM.

Recap. Hard-margin SVM finds the widest possible empty strip separating two classes. The margin is

2/∥ w ∥

. And maximizing it leads to a quadratic program: minimize

\frac{1}{2} ∥ w ∥^{2}

subject to every point being at least one unit from the boundary. The dual formulation reveals that

w

is built only from dot products among data points. — a fact that will let us lift data into higher dimensions using kernels.

Bridge. Now that you have the optimization problem, the next question is: which data points actually matter? The answer lies in the KKT conditions and the idea of support vectors. — only the points sitting exactly on the margin influence the classifier. The rest of the data is irrelevant. Section 20.2 makes this precise through complementary slackness.

Real-world connection. SVMs powered text classification for over a decade — spam filters, document categorization, sentiment analysis. The hard-margin variant is mostly a pedagogical stepping stone, but the geometry it establishes (maximum margin. Support vectors, dual formulation) is the foundation every kernel method builds on. In bioinformatics, hard-margin ideas underpin protein fold recognition where data from different structural classes genuinely separates in feature space.

20.2 Support Vectors via Complementary Slackness

20.2.1 Complementary Slackness Condition

Hook. You solved a classification problem and got a weight vector

w

. Now ask: which training points actually decided where the boundary went? Surprisingly, the answer is "hardly any of them." Most of your training data contributed nothing at all to the classifier.

Intuition. Think of a tug-of-war. The rope's position is determined by the strongest pullers at the front — not by the crowd cheering from behind. In SVM, the "pullers" are the data points closest to the separating hyperplane. Points deep inside their class region are like bystanders — they exert zero force on where the boundary sits.

Analogy — the fence posts. Imagine you stretch a fence between two fields. You only need posts at the points where the fence comes closest to the crop on either side. Once those posts are in, the rest of the fence is determined. You do not need a post for every inch of field — just the critical spots. Support vectors are the fence posts. Complementary slackness is the rule that says: only posts at the tightest spots get any pull.

The KKT (Karush-Kuhn-Tucker) conditions are the "optimality checklist" for a constrained optimization problem. One of them — complementary slackness — is the reason SVM is sparse. It says: for every constraint, the product of the Lagrange multiplier and the constraint slack must be zero.

For hard-margin SVM, the primal constraint is:

Y_{i} (w \cdot X_{i} + B) - 1 \geq 0

The dual constraint on the multiplier is

α_{i} \geq 0

. Complementary slackness demands:

α_{i} [Y_{i} (w \cdot X_{i} + B) - 1] = 0 for every i

This is a binary switch. For each data point, the product is zero only if at least one factor is zero:

Scenario A:

α_{i} = 0

. The multiplier is "switched off." The point's constraint slack has no influence on the solution. This means the point is safely outside the margin —

Y_{i} (w \cdot X_{i} + B) > 1

.Scenario B:

Y_{i} (w \cdot X_{i} + B) - 1 = 0

. The point sits exactly on the margin boundary. Its multiplier

α_{i}

can be positive (it may be zero, but it is allowed to be non-zero). This point contributes to

w

and therefore shapes the classifier.

These are the only two possibilities. A point cannot both have a positive multiplier AND sit far from the margin — the product would be non-zero. Violating complementary slackness.

The four KKT conditions together are:

Primal feasibility:

Y_{i} (w \cdot X_{i} + B) \geq 1

for all

i

Dual feasibility:

α_{i} \geq 0

for all

i

Stationarity:

\nabla_{w, B} L = 0

(gave us

w = \sum α_{i} Y_{i} X_{i}

and

\sum α_{i} Y_{i} = 0

)Complementary slackness:

α_{i} [Y_{i} (w \cdot X_{i} + B) - 1] = 0

for all

i

For convex problems like SVM, Slater's condition guarantees strong duality — the dual solution equals the primal solution. The SVM problem is convex (quadratic objective. Linear constraints) and the feasible region has an interior (at least one point satisfies the constraints with strict inequality). So Slater's condition holds. This is why we can confidently solve the dual problem and get the correct answer.

20.2.2 Support Vectors Define the Classifier

Recall from the Lagrangian stationarity condition:

w = i \sum α_{i} Y_{i} X_{i}

The weight vector is built as a weighted sum of data points, each scaled by

α_{i} Y_{i}

. Complementary slackness drives this home: any point with

α_{i} = 0

contributes exactly nothing. So the sum reduces to only those points with

α_{i} > 0

w = i : α_{i} > 0 \sum α_{i} Y_{i} X_{i}

These points — the ones with

α_{i} > 0

— are the support vectors. They "support" the hyperplane. Remove or move one, and the boundary shifts. Remove a non-support-vector, and nothing changes at all.

This is why the method is called Support Vector Machine. The classifier lives and dies by its support vectors. Change a point far from the margin and nothing happens. Move a support vector and the whole boundary shifts.

In practice, the number of support vectors is typically a small fraction of the training data. The sparsity is a huge practical advantage: prediction only requires computing dot products with the support vectors, not the full training set.

Visual intuition. Picture the 2D scatter plot from Section 20.1. Three parallel lines: the decision boundary in the center, and two margin boundaries at

\pm 1

. Most blue discs are far to the right of the

+ 1

line. Most orange crosses are far to the left of the

- 1

line. Only a handful of points — maybe 2 or 3 — actually touch the dashed lines. Draw a circle around those touching points. Those are the support vectors. Now erase all other points. The maximum-margin line stays exactly the same. The support vectors alone determine everything.

Scope. Complementary slackness as stated here applies to the hard-margin case where the margin boundaries are at exactly

\pm 1

. In soft-margin SVM (Section 20.4), the condition becomes:

α_{i} [Y_{i} (w \cdot X_{i} + B) - 1 + ξ_{i}] = 0

Plus an additional condition

μ_{i} ξ_{i} = 0

for the slack variable multipliers. The interpretation changes: points with

0 < α_{i} < C

are margin support vectors; points with

α_{i} = C

are inside the margin or misclassified.

Pitfalls.

Thinking all $α_{i} > 0$ points are on the margin. In the hard-margin case. Complementary slackness forces

α_{i} > 0

iff the point is exactly on the margin. But in soft-margin, points inside the margin or misclassified can also have positive

α_{i}

. The exact location depends on whether

α_{i} < C

(on the margin) or

α_{i} = C

(inside or wrong side).Confusing Slater's condition with KKT. Slater's condition is a qualification — it guarantees strong duality applies. KKT conditions are the optimality checks the solution must pass. For SVM, both hold because the problem is convex and strictly feasible, but they serve different roles.Why not use all points? If every point contributed, the classifier would be a dense sum over the entire dataset. Prediction would be slow. The sparsity from complementary slackness is a feature, not a bug — it makes SVM efficient at test time.

Recap. Complementary slackness forces

α_{i} > 0

only for points on the margin. Those points are the support vectors, and they alone build the weight vector

w

. All other points contribute nothing. This is why SVM is sparse: the classifier depends on a handful of critical points near the boundary.

Bridge. Section 20.3 works through a concrete numerical example where you solve for

α

w

, and

B

with two data points — showing the full machinery in action on a tiny dataset.

Real-world connection. The sparsity of support vectors is what made SVM practical at scale long before GPUs existed. A classifier trained on a million documents might depend on only a few thousand support vectors. In text classification (spam detection, news categorization). This meant fast predictions — you only compute dot products against the support vectors, not the full vocabulary. The same sparsity principle re-emerges in modern techniques like prototype-based learning and coreset selection.

20.3 Hard Margin SVM: Worked Numerical Example

20.3.1 Problem Setup

Hook. All the theory — Lagrangians, duality, KKT — means nothing until you can solve a concrete problem with real numbers. Here is one. Two data points, opposite classes. Find the maximum-margin line.

Intuition. With exactly two points of opposite class, the maximum-margin line is simply the perpendicular bisector of the segment joining them. The SVM machinery should recover exactly that. Watch as the algebra confirms what geometry tells you upfront — a nice sanity check.

Analogy. You and a friend stand 10 meters apart in a field. You claim the ground on your side is yours; your friend claims the other side. The fairest boundary is the line exactly halfway between you, running perpendicular to the line connecting you. SVM with two opposite-class points does exactly the same thing in higher dimensions.

You are given two data points:

X_{1} = (1, 2), Y_{1} = + 1 (positive class)

X_{2} = (3, 4), Y_{2} = - 1 (negative class)

With only two points, both must be support vectors. The decision boundary is a line exactly halfway between them.

The hyperplane equation is:

W_{1} X_{1} + W_{2} X_{2} + B = 0

where

w = (W_{1}, W_{2}) \in R^{2}

is the weight vector. For the two support vectors, the margin conditions are:

w \cdot X_{1} + B = 1 (positive margin boundary, since Y_{1} = + 1)

w \cdot X_{2} + B = - 1 (negative margin boundary, since Y_{2} = - 1)

The unknowns are

α_{1}

α_{2}

B

w

— but

w

is expressed in terms of

α_{1}, α_{2}

through the Lagrangian derivative. So the true unknowns are

α_{1}, α_{2}, B

20.3.2 Expressing $w$ in Terms of Data Points

From the Lagrangian derivative

\partial L / \partial w = 0

w = α_{1} Y_{1} X_{1} + α_{2} Y_{2} X_{2}

Substitute this into the two margin equations.

For point 1:

(α_{1} Y_{1} X_{1} + α_{2} Y_{2} X_{2}) \cdot X_{1} + B = 1

Expanding with the bilinearity of the dot product:

α_{1} Y_{1} (X_{1} \cdot X_{1}) + α_{2} Y_{2} (X_{1} \cdot X_{2}) + B = 1

For point 2:

(α_{1} Y_{1} X_{1} + α_{2} Y_{2} X_{2}) \cdot X_{2} + B = - 1

Expanding:

α_{1} Y_{1} (X_{1} \cdot X_{2}) + α_{2} Y_{2} (X_{2} \cdot X_{2}) + B = - 1

We have three unknowns (

α_{1}

α_{2}

B

) and two equations. We need a third.

20.3.3 The Third Equation and Dot Product Computation

From the stationarity condition

\partial L / \partial B = 0

α_{1} Y_{1} + α_{2} Y_{2} = 0

Plugging in

Y_{1} = 1

and

Y_{2} = - 1

α_{1} (1) + α_{2} (- 1) = 0 ⟹ α_{1} = α_{2}

This makes sense: with two symmetric points, their multipliers balance.

Now compute the dot products:

X_{1} \cdot X_{1} = (1) (1) + (2) (2) = 1 + 4 = 5

X_{1} \cdot X_{2} = (1) (3) + (2) (4) = 3 + 8 = 11

X_{2} \cdot X_{2} = (3) (3) + (4) (4) = 9 + 16 = 25

20.3.4 Solving the System of Equations

Plug the dot products and known

Y

values into the two main equations.

Equation 1 (from point 1, with margin

+ 1

α_{1} (1) (5) + α_{2} (- 1) (11) + B = 1

5 α_{1} - 11 α_{2} + B = 1

Equation 2 (from point 2, with margin

- 1

α_{1} (1) (11) + α_{2} (- 1) (25) + B = - 1

11 α_{1} - 25 α_{2} + B = - 1

Equation 3 (from stationarity):

α_{1} = α_{2}

Substitute

α_{2} = α_{1}

into both equations:

Equation 1 becomes:

5 α_{1} - 11 α_{1} + B = 1 ⟹ - 6 α_{1} + B = 1

Equation 2 becomes:

11 α_{1} - 25 α_{1} + B = - 1 ⟹ - 14 α_{1} + B = - 1

Subtract the first transformed equation from the second:

(- 14 α_{1} + B) - (- 6 α_{1} + B) = - 1 - 1

- 8 α_{1} = - 2

α_{1} = \frac{1}{4}

Since

α_{1} = α_{2}

α_{1} = α_{2} = \frac{1}{4}

Now find

B

. Use

- 6 α_{1} + B = 1

- 6 (\frac{1}{4}) + B = 1 ⟹ - \frac{3}{2} + B = 1 ⟹ B = 1 + \frac{3}{2} = \frac{5}{2}

Now compute

w

w = α_{1} Y_{1} X_{1} + α_{2} Y_{2} X_{2} = \frac{1}{4} \cdot 1 \cdot (1, 2) + \frac{1}{4} \cdot (- 1) \cdot (3, 4) = (\frac{1}{4}, \frac{2}{4}) + (- \frac{3}{4}, - 1) = (\frac{1}{4} - \frac{3}{4}, \frac{1}{2} - 1) = (- \frac{1}{2}, - \frac{1}{2})

W_{1} = - \frac{1}{2}

and

W_{2} = - \frac{1}{2}

The decision boundary is

w \cdot X + B = 0

- \frac{1}{2} X_{1} - \frac{1}{2} X_{2} + \frac{5}{2} = 0

Multiply through by

- 2

X_{1} + X_{2} - 5 = 0 or X_{1} + X_{2} = 5

The margin boundaries are

X_{1} + X_{2} = 4

(positive side) and

X_{1} + X_{2} = 6

(negative side). The margin is:

\frac{2}{∥ w ∥} = \frac{2}{( - \frac{1}{2} ) ^{2} + ( - \frac{1}{2} ) ^{2}} = \frac{2}{\frac{1}{4} + \frac{1}{4}} = \frac{2}{\frac{1}{2}} = \frac{2}{\frac{1}{2}} = 22

Sense check. The two points are 2.83 units apart (distance from

(1, 2)

(3, 4)

2^{2} + 2^{2} = 8 = 22

). The margin equals exactly the distance between the points. — which makes sense: both are support vectors on opposite margins. So the total gap between the boundary planes equals the distance between the two closest opposite-class points.

20.3.5 Geometric Interpretation

Plot the two points:

(1, 2)

is in the positive class and

(3, 4)

is in the negative class. The line connecting them runs diagonally. The separating hyperplane is perpendicular to that connecting line and passes through the midpoint. The midpoint of

(1, 2)

and

(3, 4)

(2, 3)

. And

2 + 3 = 5

— exactly what the equation

X_{1} + X_{2} = 5

says.

The weight vector

w = (- \frac{1}{2}, - \frac{1}{2})

is parallel to

(- 1, - 1)

. Which is perpendicular to the line

X_{1} + X_{2} = 5

(since the normal to

X_{1} + X_{2} = 5

(1.1)

. And

(- 1, - 1)

is just the negative of that normal — same direction, flipped sign by the label convention).

Logic check: Even without SVM machinery. The maximum-margin line between two points of opposite class is the perpendicular bisector of the segment joining them. The SVM math recovers exactly that. The midpoint

(2, 3)

satisfies

X_{1} + X_{2} = 5

, and the weight vector is orthogonal to the bisector.

Scope. This 2-point solution strategy works cleanly only for the hard-margin case. With 3+ points, not every point is a support vector. And you need to use complementary slackness to identify which

α_{i}

are zero and which are positive. The approach here — setting up equations from the margin conditions for every point. — only works when you know in advance which points are support vectors. For larger problems, you solve the dual quadratic program numerically using SMO (Sequential Minimal Optimization) or a QP solver.

20.3.6 Student Questions on the Worked Example

Q: Can we just take the bias

B

as 1 and avoid solving for it?

A: You can set bias to 1 only if the data is normalized first. With unnormalized data, the bias can be any value — the optimization finds the right number. Setting it to 1 without normalization would force the hyperplane to be one unit from the origin. Which may sit nowhere near your data. You must solve for

B

from the equations.

Q: How do you get the derivative

\partial L / \partial B

and the condition

\sum α_{i} Y_{i} = 0

A: Take the Lagrangian:

L = \frac{1}{2} ∥ w ∥^{2} - \sum_{i} α_{i} [Y_{i} (w \cdot X_{i} + B) - 1]

. Differentiate with respect to

B

. The first term

\frac{1}{2} ∥ w ∥^{2}

has no

B

, so its derivative is zero. The sum expands to

- \sum_{i} α_{i} Y_{i} (w \cdot X_{i}) - B \sum_{i} α_{i} Y_{i} + \sum_{i} α_{i}

. Only the middle term depends on

B

. Its derivative is

- \sum_{i} α_{i} Y_{i}

. Setting this to zero gives the stationarity condition

\sum_{i} α_{i} Y_{i} = 0

Q: What would happen if we left bias out entirely?

A: Without bias, the equation becomes

w \cdot X \geq 0

for positive points. A plane of that form must pass through the origin — the decision boundary is forced through

(0.0)

no matter what direction

w

points. That works only if the data happens to be separable by a plane through the origin. In general, the bias term

B

is what lets the boundary sit anywhere in space. Drop it and you severely restrict what the classifier can do.

Recap. For two opposite-class points, SVM algebraically recovers the perpendicular bisector:

w = (- \frac{1}{2}, - \frac{1}{2})

B = \frac{5}{2}

, decision boundary

X_{1} + X_{2} = 5

, margin

= 22

. The three equations come from two margin conditions plus the stationarity condition

\sum α_{i} Y_{i} = 0

Bridge. This example used hard-margin SVM. But what if one of the points was mislabeled or the data was not perfectly separable? Section 20.4 introduces soft-margin SVM, which lets some points violate the margin — paying a penalty for each violation.

Real-world connection. Solving small SVM problems by hand like this builds the intuition you need to debug production classifiers. When scikit-learn's `SVC` gives a surprising decision boundary. You can trace it back: check the support vectors, verify their dot products, and ensure the margin conditions hold. In practice, numerical solvers like LIBSVM use SMO to solve the dual. But the underlying linear system for the support vectors is exactly the structure you just solved manually.

20.4 Soft Margin SVM

20.4.1 The Slack Variable

Hook. Hard-margin SVM is a perfectionist — it demands every point sit outside the margin. One outlier, one mislabeled point, and the whole problem becomes infeasible. Real data is never that clean. How do you build a street when a few houses are already built in the middle of the road?

Intuition. Instead of demanding perfection, you allow some points to break the rules — but you charge them a penalty. The deeper a point intrudes into the margin or crosses to the wrong side, the more it pays. This creates a trade-off: you can have a wide margin (good for generalization) if you accept a few violations (tolerable if the cost is low).

Analogy — the speed limiter. Driving a car with a speed limiter set to 100 km/h. Going above 100 costs you a fine proportional to how much you exceed it. If fines are cheap (small

C

), you speed whenever convenient. If fines are ruinous (large

C

), you stay strictly under 100 no matter what. Soft-margin SVM uses exactly this penalty structure — the slack variable

ξ_{i}

measures "how much over the limit" each point goes. And

C

is the fine per unit of violation.

A slack variable

ξ_{i} \geq 0

is introduced for each data point. It measures how far a point intrudes into the margin or crosses to the wrong side. Three regimes:

ξ_{i} = 0

: Point is correctly classified and outside (or on) the margin. No penalty.

0 < ξ_{i} < 1

: Point is correctly classified but inside the margin strip. It is between the

+ 1

boundary and the decision boundary (or the

- 1

boundary and the decision boundary).

ξ_{i} \geq 1

: Point is misclassified — on the wrong side of the decision boundary. The larger

ξ_{i}

, the deeper the violation.

The hard constraint

Y_{i} (w \cdot X_{i} + B) \geq 1

relaxes to:

Y_{i} (w \cdot X_{i} + B) \geq 1 - ξ_{i}, ξ_{i} \geq 0 for all i

When

ξ_{i} = 0

, this reduces to the hard-margin constraint. When

ξ_{i} > 0

, the right-hand side drops below 1. Letting the point sit closer to the decision boundary or even cross it.

20.4.2 Soft Margin Primal Form

The objective now has two competing forces. You still want a wide margin (minimize

\frac{1}{2} ∥ w ∥^{2}

), but you also penalize violations (minimize

C \sum ξ_{i}

). The soft-margin primal:

w, B, ξ min \frac{1}{2} ∥ w ∥^{2} + C i = 1 \sum n ξ_{i}

subject to:

Y_{i} (w \cdot X_{i} + B) \geq 1 - ξ_{i}, ξ_{i} \geq 0 for all i

C > 0

is a hyperparameter you choose before training. The sum

\sum_{i = 1}^{n} ξ_{i}

is the total slack — the aggregate violation across all points. Points that are correctly classified and outside the margin contribute zero to this sum.

Note that the regularization is on

∥ w ∥^{2}

only — the bias term

B

is not regularized. This is because the bias does not affect the margin width; the margin depends only on

∥ w ∥

20.4.3 The C Parameter — Trade-off Control

C

controls the trade-off between margin width and training error:

Large $C$ (e.g.,

C = 10000

C \to \infty

): Every unit of slack is heavily penalized. The optimizer works hard to keep

\sum ξ_{i}

tiny. The margin becomes narrow. The boundary twists to avoid errors. The model memorizes noise — it overfits. At the limit

C \to \infty

, soft-margin approaches hard-margin.Small $C$ (e.g.,

C = 0.01

): Slack is cheap. The optimizer prioritizes a wide margin over perfect classification. The boundary is smooth and generalizes well, but some training points may be misclassified or sit inside the margin.

Think of

C

as an inverse regularization strength. A large

C

means weak regularization (the

∥ w ∥^{2}

term gets relatively little weight compared to the penalty sum). A small

C

means strong regularization (the margin term dominates, forcing

∥ w ∥

small and the margin large).

Symbol note: Some texts parametrize with

λ = 1/ C

and write the objective as

λ ∥ w ∥^{2} + \sum ξ_{i}

. This flips the intuition — large

λ

then means strong regularization. The professor uses the

C

-SVM convention:

\frac{1}{2} ∥ w ∥^{2} + C \sum ξ_{i}

Scope.

Soft-margin SVM still requires the data to be mostly separable. If the two classes are completely mixed (e.g., random labels), even soft margin cannot find a good classifier. The kernel trick (Section 20.6) can help with non-linear separability, but fundamentally inseparable distributions need a different model.The primal formulation has

n + d + 1

variables (

w, B, ξ

), which is impractical for large feature dimensions. The dual (Section 20.4.4) recasts it in terms of

n

variables (

α

). Making it suitable when

n

is moderate but

d

is large.

C

is scale-sensitive. If you rescale your features (e.g., from meters to millimeters), the same

C

has a very different effect. Always normalize features before tuning

C

20.4.4 Soft Margin Dual Form

The Lagrangian for soft-margin SVM introduces multipliers

α_{i} \geq 0

for the classification constraints and

μ_{i} \geq 0

for the non-negativity constraints

ξ_{i} \geq 0

L (w, B, ξ, α, μ) = \frac{1}{2} ∥ w ∥^{2} + C i \sum ξ_{i} - i \sum α_{i} [Y_{i} (w \cdot X_{i} + B) - 1 + ξ_{i}] - i \sum μ_{i} ξ_{i}

Stationarity conditions:

\partial L / \partial w = 0 ⟹ w = \sum_{i} α_{i} Y_{i} X_{i}

(same as hard margin)

\partial L / \partial B = 0 ⟹ \sum_{i} α_{i} Y_{i} = 0

(same as hard margin)

\partial L / \partial ξ_{i} = 0 ⟹ C - α_{i} - μ_{i} = 0

Since

μ_{i} \geq 0

, the third condition gives

α_{i} = C - μ_{i} \leq C

. Combined with the dual feasibility

α_{i} \geq 0

, this yields the box constraint:

0 \leq α_{i} \leq C

The dual maximization problem is identical in form to hard margin:

α max i \sum α_{i} - \frac{1}{2} i \sum j \sum α_{i} α_{j} Y_{i} Y_{j} (X_{i} \cdot X_{j})

But with the modified constraint on

α_{i}

0 \leq α_{i} \leq C and i \sum α_{i} Y_{i} = 0

Interpretation of $α_{i}$ values:

α_{i} = 0

: Point is correctly classified and outside the margin.

0 < α_{i} < C

: Point is a support vector exactly on the margin boundary (margin support vector).

α_{i} = C

: Point is a support vector inside the margin or misclassified. Its

ξ_{i} > 0

The box constraint

0 \leq α_{i} \leq C

is what makes the dual easy to solve numerically. — it constrains each

α_{i}

to a bounded interval. Which is efficient for coordinate-descent solvers like SMO.

Visual intuition. Picture the 2D scatter with a soft-margin boundary. Most blue discs are to the right of the

+ 1

dashed line (zero slack). A few blue discs sit between the

+ 1

line and the decision boundary (

ξ_{i} < 1

). Maybe one blue disc is on the wrong side (

ξ_{i} > 1

). The weight vector

w

is shorter than it would be under hard margin — the margin is wider. The boundary does not contort to accommodate every outlier.

Pitfalls.

Not tuning $C$ . The default

C = 1

in most libraries is rarely optimal. You must cross-validate over a logarithmic grid (e.g.,

{1 0^{- 3}, 1 0^{- 2}, \dots, 1 0^{3}}

).Forgetting to normalize. Features with large ranges dominate the norm

∥ w ∥

and the dot products. Always standardize to zero mean and unit variance before training SVM.Large $C$ on noisy data. A very large

C

forces the boundary to fit every point, creating a wiggly, overfitted decision surface. The test accuracy collapses.Confusing the box constraint.

0 \leq α_{i} \leq C

means no alpha can exceed

C

. Points with

α_{i} = C

are not "more important" — they are actually the troublemakers (inside the margin or misclassified).

Recap. Soft-margin SVM introduces slack variables

ξ_{i}

that let points violate the margin at cost

C ξ_{i}

. The dual has the same objective as hard-margin but constrains

0 \leq α_{i} \leq C

. Points with

α_{i} = 0

are safe,

0 < α_{i} < C

are margin support vectors. And

α_{i} = C

are margin-violating support vectors. The hyperparameter

C

trades off margin width against training error.

Bridge. The slack variables directly lead to the hinge loss. When you optimize out the slacks, the objective becomes an unconstrained problem: minimize

\frac{1}{2} ∥ w ∥^{2} + C \sum max (0, 1 - Y_{i} (w \cdot X_{i} + B))

. Section 20.5 derives and analyzes this loss function in detail.

Real-world connection. Soft-margin SVM is the version used in every production library (scikit-learn's `SVC`, LIBSVM, SVMlight). Hard-margin is a teaching tool. In medical diagnosis, a soft-margin classifier tolerates a few misclassified patients (false positives or false negatives) to achieve a wider. More generalizable margin — critical when diagnostic measurements are noisy and overlapping.

20.5 Hinge Loss

20.5.1 Deriving the Hinge Loss

Hook. The soft-margin primal has both

w

and

ξ

as variables —

n + d + 1

unknowns. But you can eliminate the slacks entirely and get a single, clean optimization problem in just

w

and

B

. The function that replaces the slacks is the hinge loss — the native loss function of SVM.

Intuition. Imagine a grading scheme: if your answer is far on the correct side of the cutoff, you get zero penalty. If it is close to the boundary or wrong, you lose points. The penalty grows linearly as you drift further from the safe zone. The hinge loss captures exactly this: zero penalty for "comfortably correct" and linear penalty for "too close" or "wrong."

Analogy — a restaurant rating system. A chef's performance is rated by customer satisfaction scores. If the score is above 4 stars (comfortably good), no penalty. If it drops below 4, the penalty is

4 - score

— a chef with a 3.2 gets a penalty of 0.8. A chef with a 1.5 gets a penalty of 2.5. The penalty is zero for solid performers and grows linearly for underperformers. The hinge loss works the same way: it is zero above the threshold of 1, and rises linearly below it.

Start from the soft-margin constraint:

Y_{i} (w \cdot X_{i} + B) \geq 1 - ξ_{i}

Rearrange to isolate

ξ_{i}

ξ_{i} \geq 1 - Y_{i} (w \cdot X_{i} + B)

Together with the non-negativity constraint

ξ_{i} \geq 0

, the slack must be at least the larger of these two lower bounds. Since the objective wants to minimize each

ξ_{i}

, the optimizer will set it to the smallest value that satisfies both:

ξ_{i} = max (0, 1 - Y_{i} (w \cdot X_{i} + B))

Define

Z_{i} = Y_{i} (w \cdot X_{i} + B)

— the score, the label-signed output. Then the hinge loss is:

ℓ_{hinge} (Z_{i}) = max (0, 1 - Z_{i})

Substituting this into the soft-margin objective gives an unconstrained problem:

w, B min \frac{1}{2} ∥ w ∥^{2} + C i = 1 \sum n max (0, 1 - Y_{i} (w \cdot X_{i} + B))

The first term (regularizer) controls margin width. The second term (loss) penalizes points that are too close to or on the wrong side of the boundary. This is empirical risk minimization with L2 regularization and hinge loss.

20.5.2 Two Cases for the Hinge Loss

The hinge loss naturally splits into two regimes based on the score

Z_{i} = Y_{i} (w \cdot X_{i} + B)

Case 1 — Comfortably correct ( $Z_{i} \geq 1$ ): The point is classified correctly and lies on or outside the margin. Then

1 - Z_{i} \leq 0

, so

max (0, negative) = 0

. No penalty. These points do not contribute to the loss term at all.

Case 2 — Too close or wrong ( $Z_{i} < 1$ ): Two sub-cases:

0 \leq Z_{i} < 1

: The point is on the correct side of the boundary but inside the margin. The loss is

1 - Z_{i} \in (0, 1]

Z_{i} < 0

: The point is on the wrong side of the boundary (misclassified). The loss is

1 - Z_{i} > 1

The loss grows linearly without bound as the point moves further into the wrong territory. This is why hinge loss is called a linear penalty loss — unlike squared loss. It does not explode quadratically for large errors. This makes SVM robust to outliers that are correctly classified (they produce zero loss) but still penalizes misclassified points proportionally.

Comparison with zero-one loss: The zero-one loss is 1 for any misclassification and 0 otherwise. The hinge loss is a convex upper bound — it is always at least as large as the zero-one loss. And being convex makes it far easier to optimize. Minimizing the hinge loss pushes the zero-one loss down indirectly.

Worked hinge loss calculation. Given

w = (1, 1)

B = - 1.5

X = (2, 2)

Y = + 1

Step 1 — Compute the linear output:

w \cdot X + B = 1 \cdot 2 + 1 \cdot 2 - 1.5 = 4 - 1.5 = 2.5

Step 2 — Compute the score:

Z = Y \cdot (w \cdot X + B) = 1 \cdot 2.5 = 2.5

Step 3 — Compute the hinge loss:

max (0, 1 - 2.5) = max (0, - 1.5) = 0

Result: The point has a score of 2.5, which is well above 1 — it sits far on the correct side. Hinge loss is zero.

Another example — point

X = (0, 0)

with same

w = (1, 1)

B = - 1.5

Y = + 1

w \cdot X + B = 0 - 1.5 = - 1.5

Z = 1 \cdot (- 1.5) = - 1.5

max (0, 1 - (- 1.5)) = max (0, 2.5) = 2.5

This point is misclassified (negative score) and pays a penalty of 2.5.

Scope.

Hinge loss is not differentiable at

Z = 1

(the "hinge" point). Gradient-based optimizers need subgradient methods — the subgradient is 0 for

Z > 1

[- 1, 0]

Z = 1

, and

- 1

for

Z < 1

.For the dual formulation, hinge loss manifests as the box constraint

0 \leq α_{i} \leq C

. There is no explicit hinge loss in the dual — it shows up only in the primal/unconstrained form.

Q: How do you actually compute hinge loss for a given point?

A: Three steps: (1) compute the dot product

w \cdot X

. Add the bias

B

; (2) multiply by the label

Y_{i}

to get the score

Z_{i}

; (3) compute

max (0, 1 - Z_{i})

. This gives the loss for that single point. The total loss is the sum over all points.

Pitfalls.

Confusing the score with the dot product. The dot product alone (

w \cdot X + B

) is not the score. — you must multiply by the label. A positive dot product for a negative-class point means misclassification, but the raw dot product doesn't capture this. The score

Z_{i} = Y_{i} (w \cdot X_{i} + B)

folds the label into the signal.Hinge loss is not cross-entropy. For binary classification with

Y \in {- 1, + 1}

, the hinge loss is

max (0, 1 - Y f (X))

. For labels in

{0, 1}

, the hinge loss is

max (0.1 - y f (X))

where

y \in {0, 1}

— a different convention. Know which label encoding your framework uses.Forgetting the margin term. The unconstrained objective is

\frac{1}{2} ∥ w ∥^{2} + C \sum hinge

, not just

\sum hinge

. Without the regularizer. The optimizer would make

∥ w ∥

large enough to push all scores above 1 — trivially achieving zero loss but with no margin.

Recap. The hinge loss

max (0, 1 - Z_{i})

is zero for points correctly classified with margin. And grows linearly for points too close to or on the wrong side of the boundary. It is a convex upper bound on the zero-one loss, making it optimizable. Substituting hinge loss into the soft-margin objective eliminates the slack variables, giving an unconstrained regularized empirical risk minimization problem.

Bridge. Armed with soft margin and hinge loss, you can now handle non-separable data. But what if the data is separable only by a curve, not a line? Section 20.6 introduces the kernel trick — a way to lift data into higher dimensions where linear separation becomes possible. Without ever visiting those dimensions.

Real-world connection. Hinge loss appears beyond SVM — in ranking algorithms (RankSVM). Structured prediction, and some neural network training schemes (maximum-margin neural networks). In text categorization, hinge-loss-trained linear classifiers can match the accuracy of much more complex models while training in seconds on CPUs. Making them the go-to baseline for production systems with tight latency budgets.

20.6 The Kernel Trick

20.6.1 Non-Linear Separability

Hook. A straight line can separate two classes in many problems. But what about the XOR pattern — four points arranged like a checkerboard? No single line can split them. You have two choices: accept misclassifications forever, or get clever. The kernel trick is the clever one.

Intuition. Imagine you have red and blue marbles on a flat table, arranged in the XOR pattern. You cannot draw a straight line that separates them. Now lift one color of marbles slightly above the table. In 3D, a flat sheet of paper can slide between the lifted marbles and the ones still on the table. Look down from above — the boundary looks curved. But in the elevated space, it is perfectly flat. The kernel trick does this mathematically: it lifts data into a higher dimension where separation becomes trivial. But it never actually moves the points — it just computes what their dot products would be in that higher space.

Analogy — the map projection trick. A flat map of Earth distorts distances. But if you measure the straight-line distance through the Earth (3D). You can get the true shortest path without ever needing a globe. — you compute it from latitude and longitude using spherical geometry. The kernel function is that formula: it computes similarity in the high-dimensional "true" space directly from low-dimensional coordinates.

20.6.2 Projecting to Higher Dimensions

The XOR problem shows why linear classifiers fail on non-linear data. Points at

(0, 0)

and

(1, 1)

are class A. Points at

(0, 1)

and

(1, 0)

are class B. Any line that gets three right gets the fourth wrong.

The mathematical insight: define a feature map

Φ : R^{n} \to R^{p}

that transforms each data point into a higher-dimensional space (

p > n

Φ : R^{n} \to R^{p}, X \mapsto Φ (X) = (ϕ_{1} (X), \dots, ϕ_{p} (X))

In this new space, you find a linear hyperplane

W \cdot Φ (X) + B = 0

. When mapped back to the original space, this linear hyperplane becomes a non-linear decision boundary.

For XOR, using

Φ (X_{1}, X_{2}) = (X_{1}, X_{2}, X_{1} X_{2})

lifts the points into 3D. The blue points (same signs) stay near the floor. The red points (different signs) get lifted upward by the interaction term

X_{1} X_{2}

. A flat plane in 3D neatly separates them.

20.6.3 SVM as a Similarity-Based Classifier

The key observation is in the dual prediction formula. Recall

w = \sum_{i} α_{i} Y_{i} X_{i}

. Substitute into the prediction function:

f (X_{new}) = w \cdot X_{new} + B = i \sum α_{i} Y_{i} (X_{i} \cdot X_{new}) + B

For a new input

X_{new}

, you compute its dot product with every support vector

X_{i}

. Weight by

α_{i} Y_{i}

, sum them up, and add the bias.

A dot product

X_{i} \cdot X_{new}

measures similarity. Parallel vectors give large positive values. Orthogonal vectors give zero. Opposite vectors give large negative values. SVM is fundamentally a similarity-based classifier: it compares your new point to the support vectors and votes based on which support vectors it most resembles. The sign of

f (X_{new})

makes the final call — positive for class

+ 1

, negative for class

- 1

The training objective (the dual) also depends only on dot products between data points:

X_{i} \cdot X_{j}

. At no point does the algorithm need individual coordinates — only pairwise similarities.

20.6.4 The Kernel Trick Intuition

Now the crucial problem: projecting all data into a high-dimensional feature space and then computing dot products there is computationally crushing. Suppose your data lives in

D = 100

dimensions and you want polynomial features up to degree 5. The number of expanded features is:

(5 D + 5) = (5 105) \approx 96 million features

Computing explicit 96-million-dimensional vectors for every point and then taking dot products is not practical.

The kernel trick sidesteps this entirely. You define a kernel function

K (X_{i} . X_{j})

that computes the dot product in the high-dimensional feature space directly from the original low-dimensional coordinates, without ever constructing

Φ (X_{i})

K (X_{i}, X_{j}) = Φ (X_{i}) \cdot Φ (X_{j})

In the prediction formula, you replace every dot product with the kernel:

f (X) = i \sum α_{i} Y_{i} K (X_{i}, X) + B

In the dual training objective:

α max i \sum α_{i} - \frac{1}{2} i \sum j \sum α_{i} α_{j} Y_{i} Y_{j} K (X_{i}, X_{j})

The kernel gives you the power of operating in a high-dimensional feature space while only paying the computational cost of operating in the original low-dimensional space. The data points never leave their original coordinates.

Why this works: The kernel function must correspond to a valid inner product in some (possibly infinite-dimensional) Hilbert space. This is guaranteed if the kernel is symmetric and positive semidefinite — the Gram matrix

K_{ij} = K (X_{i} . X_{j})

must be positive semidefinite for any set of points. This is Mercer's condition.

Visual intuition. Left panel: a 2D scatter of XOR data — two blue squares at opposite corners. Two red circles at the other corners. No straight line separates them. Middle panel: an arrow showing the feature map

Φ

lifting the data into a 3D space. The red circles rise above the blue squares. Right panel: a flat semi-transparent plane in 3D cleanly separates the lifted points. Dotted lines project the 3D plane back to 2D — it becomes a curved hyperbola. Below the panels: "The decision boundary is a straight plane in the lifted space. It looks curved only because you are viewing its shadow in the original 2D."

Scope.

The kernel trick works for any algorithm whose training and prediction depend only on dot products between data points. This includes kernel PCA, kernel ridge regression, and kernel k-means — not just SVM.Not every function of two vectors is a valid kernel. It must be a symmetric, positive semidefinite function satisfying Mercer's theorem. Linear, polynomial, RBF, and sigmoid (under certain parameters) kernels are valid.The kernel trick does not help if the data is linearly separable in the original space. — a linear kernel

K (X_{i}, X_{j}) = X_{i} \cdot X_{j}

suffices. Kernels are for when linear separation fails.

Pitfalls.

Kernel does not mean "automatically better." A poorly chosen kernel or badly tuned kernel parameter can give worse results than a linear SVM. Start with a linear kernel as a baseline.Confusing the kernel with the Gram matrix. The kernel function

K (\cdot, \cdot)

is the formula. The Gram matrix

K \in R^{n \times n}

is the matrix whose entries are

K_{ij} = K (X_{i}, X_{j})

. You compute it once before solving the dual.Forgetting that the support vectors stay in the original space. You do not find support vectors in the high-dimensional feature space. The support vectors are still the original data points

X_{i}

with

α_{i} > 0

. Only the similarity measure changes.

Recap. The dual SVM formulation depends only on dot products between data points. The kernel trick replaces every dot product

X_{i} \cdot X_{j}

with a kernel function

K (X_{i} . X_{j})

that computes the dot product in a high-dimensional feature space without ever constructing that space. This lets SVM find non-linear decision boundaries in the original space by finding linear hyperplanes in an implicit high-dimensional space.

Bridge. The kernel trick is a beautiful idea, but which kernel should you use? The next two sections cover the two most important ones: the polynomial kernel (Section 20.7) and the RBF/Gaussian kernel (Section 20.8). — the latter being the workhorse kernel used in practice.

Real-world connection. The kernel trick is one of the most influential ideas in machine learning. It decouples the learning algorithm from the data representation. The same SVM solver works with a linear kernel for text, a string kernel for DNA sequences. A graph kernel for molecular structures, and a pyramid match kernel for images — just swap the kernel function. Google's early ranking systems used kernel methods, and kernel-based Gaussian processes are standard in Bayesian optimization for hyperparameter tuning.

20.7 Polynomial Kernel

20.7.1 Polynomial Feature Explosion

Hook. You want to fit a curved decision boundary. The obvious approach: create polynomial features (

X_{1}

X_{2}

X_{1}^{2}

X_{1} X_{2}

X_{2}^{2}

, ...), then run a linear SVM on the expanded dataset. But watch out — the number of features explodes combinatorially. A 100-dimensional input with degree-5 polynomial features produces nearly 100 million features. That is impossible to store, let alone compute dot products on.

Intuition. Imagine you are writing out every monomial term like

X_{1}^{3} X_{2} X_{5}

by hand for a 100-dimensional dataset. The number of unique monomials grows faster than your patience. But computing

(X \cdot Y + 1)^{5}

takes roughly 100 multiplications and one exponentiation. The polynomial kernel is a shortcut: it computes the dot product in the expanded space using only the original features. Bypassing the combinatorial explosion entirely.

Analogy — the expanded shopping cart. You go shopping with a list of 100 items (your original features). You want to consider all pairs of items that go well together (polynomial interactions up to degree 2). Writing out all pairs would take 5050 entries. But if someone gives you a magic formula that computes the "pairwise compatibility score" of two shopping carts using only the individual items. You get the same result without ever listing the pairs. The polynomial kernel is that magic formula.

20.7.2 The Polynomial Kernel Formula

For a

D

-dimensional input and polynomial degree

P

, the number of polynomial features up to degree

P

is:

(P D + P)

This counts all monomials like

1, X_{1}, X_{2}, X_{1}^{2}, X_{1} X_{2}, X_{2}^{2}, X_{1}^{3}, \dots

up to degree

P

. For example,

D = 2, P = 2

gives

(2 4) = 6

features:

1, X_{1}, X_{2}, X_{1}^{2}, X_{1} X_{2}, X_{2}^{2}

. For

D = 100, P = 5

(5 105) \approx 96, 560, 646

features — nearly 100 million.

Derivation (stars and bars): How many monomials of exactly degree

k

can you form from

D

variables? A monomial is

X_{1}^{k_{1}} X_{2}^{k_{2}} \dots X_{D}^{k_{D}}

with

k_{1} + \dots + k_{D} = k

. This is the classic "stars and bars" problem: arranging

k

stars and

D - 1

bars. The count is

(k k + D - 1)

. Summing over

k = 0

P

gives

(P D + P)

The polynomial kernel avoids this explosion:

K (X, Y) = (X \cdot Y + c)^{d}

where

d

is the polynomial degree and

c \geq 0

is an optional constant.

c = 0

: the pure polynomial kernel

(X \cdot Y)^{d}

. This creates features of exactly degree

d

(homogeneous polynomials).

c = 1

: the inhomogeneous kernel

(X \cdot Y + 1)^{d}

. This includes all lower-degree terms as well. For

d = 2

(x_{1} z_{1} + x_{2} z_{2} + 1)^{2} = (x_{1} z_{1})^{2} + (x_{2} z_{2})^{2} + 2 x_{1} x_{2} z_{1} z_{2} + 2 x_{1} z_{1} + 2 x_{2} z_{2} + 1

. Which is exactly the dot product of

Φ (X) = (X_{1}^{2}, X_{2}^{2}, 2 X_{1} X_{2}, 2 X_{1}, 2 X_{2}, 1)

with

Φ (Y)

Note the

2

coefficients in the feature map. These come from the multinomial expansion. The binomial coefficients

(k _{1} , \dots . K _{D} d)

appear inside the square root to ensure the dot product of the scaled features reproduces the kernel value exactly.

Worked comparison — polynomial kernel vs. explicit expansion. With 2D vectors

X = (1, 2)

Y = (3, 4)

, the dot product is

1 \cdot 3 + 2 \cdot 4 = 11

. Degree-5 polynomial kernel:

K (X, Y) = 1 1^{5} = 161, 051

The explicit expansion would create

(5 5 + 2) = 21

features per point, requiring 21-component vectors and a 21-dimensional dot product. The kernel computes the result in one power operation.

Cost comparison. Kernel trick: 2 multiplications, 1 addition, 1 exponentiation. Explicit: 21 features per point

\times

2 points = 42 feature computations, then 21 multiplications and 20 additions for the dot product. For

D = 100, d = 5

, the gap becomes astronomical: one 100-dimensional dot product + power vs. ~96 million explicit features.

Q: How do you choose the polynomial degree?

A: There is no closed-form answer. Try degrees 2, 3, 4, 5 and use cross-validation to pick the one with lowest error. In practice. Most practitioners skip polynomial kernels entirely and go straight to the RBF kernel. — the RBF implicitly includes all polynomial degrees (up to infinity) and removes the need to guess. Tune gamma well and RBF handles almost any situation.

Scope.

The polynomial kernel works well when the true decision boundary is approximately a low-degree polynomial surface. Image data and text data rarely satisfy this — RBF kernels are almost always better for those domains.The parameter

c

(the additive constant) controls the influence of lower-order terms. Larger

c

gives more weight to lower degrees.

c = 0

uses only homogeneous degree-

d

terms.Polynomial kernels with high degree (

d ≫ 1

) can become numerically unstable. — kernel values can explode (large dot product raised to a high power). Normalize your data and consider using a moderate degree.

Visual intuition. A 2D scatter plot with a circular decision boundary separating an inner cluster (class +1) from an outer ring (class -1). Left panel: a linear kernel fails — no straight line can separate them. Middle panel: a degree-2 polynomial kernel finds a circular boundary. Right panel: a degree-3 polynomial kernel produces a more complex, wavy boundary that starts overfitting. Caption: "Higher polynomial degrees produce more flexible boundaries but risk overfitting."

Pitfalls.

Numerical overflow. If

X \cdot Y

is large (e.g., 100) and

d = 5

, the kernel value is

10 0^{5} = 1 0^{10}

. This overwhelms floating-point arithmetic. Always scale features to small ranges before using polynomial kernels.Odd-degree kernels with all-positive features. If all features are positive, an odd-degree polynomial kernel cannot separate data that requires sign changes. The polynomial will always be a monotonic function of the dot product.Choosing degree too high. Degree-10 or degree-20 kernels almost always overfit catastrophically. In practice,

d \leq 3

or use RBF instead.

Recap. The polynomial kernel

K (X, Y) = (X \cdot Y + c)^{d}

computes the dot product in the space of all polynomial features up to degree

d

using only the original dot product. — one number. It avoids computing the

(d D + d)

expanded features explicitly. The constant

c

controls whether lower-degree terms are included, and the degree

d

controls the flexibility of the decision boundary.

Bridge. The polynomial kernel solves the linear-separability problem for a wide class of curved boundaries. But it has a major limitation: you must choose the degree in advance. The RBF kernel (Section 20.8) eliminates this choice by giving the model access to all polynomial degrees. — up to infinity — in a single kernel function.

Real-world connection. Polynomial kernels are the kernel of choice when domain knowledge suggests polynomial structure — for example. In image retrieval using color histograms (bhattacharyya kernel is a special polynomial kernel). In natural language processing with bigram/trigram features, and in certain genomics applications where gene-gene interaction effects are known to be low-order. However, for general-purpose classification, polynomial kernels have been almost entirely superseded by RBF.

20.8 Radial Basis Function (RBF) Kernel

20.8.1 RBF Kernel Formula

Hook. What if you could give your SVM access to every polynomial degree — first. Second, third, all the way to infinity — in a single kernel? And you only have to tune one parameter? The RBF kernel does exactly that. It is the default kernel in every SVM library for good reason.

Intuition. The RBF kernel measures similarity by distance. Two points close together get a kernel value near 1. Two points far apart get a value near 0. It is like a "fuzzy indicator" of whether two points are neighbors. The parameter

γ

controls what counts as "close."

Analogy — the thermal camera. A thermal camera blurs heat signatures: nearby warm objects blend together in the image. Far objects stay sharply separate. The RBF kernel does the same for data points. A small

γ

blurs widely — even distant points look similar. A large

γ

sharpens — only points in the immediate neighborhood look alike. The kernel value is the "heat similarity" between two points, and gamma is the sensitivity knob.

The RBF (Radial Basis Function) kernel, also called the Gaussian kernel, is:

K (X, Y) = exp (- γ ∥ X - Y ∥^{2})

where:

∥ X - Y ∥^{2} = (X - Y) \cdot (X - Y)

is the squared Euclidean distance between

X

and

Y

γ > 0

is a scaling hyperparameter you choose

exp (z) = e^{z}

is the exponential function

The exponential maps large distances to kernel values near zero and small distances to values near one. The kernel value is always in

(0, 1]

. When

X = Y

, the distance is zero and

K = 1

(maximum similarity).

20.8.2 Gamma as a Scaling Parameter

Gamma controls how fast similarity decays with distance. Expand the squared norm:

∥ X - Y ∥^{2} K (X, Y) = ∥ X ∥^{2} - 2 X \cdot Y + ∥ Y ∥^{2} = exp (- γ ∥ X ∥^{2}) \cdot exp (2 γ X \cdot Y) \cdot exp (- γ ∥ Y ∥^{2})

The first and third factors depend only on individual points — they are scaling factors. The middle term

exp (2 γ X \cdot Y)

contains the dot product

X \cdot Y

, which is where the similarity comparison actually happens. This connects the RBF kernel back to the linear kernel through the exponential of the dot product.

Effect of gamma:

Large $γ$ (e.g.,

γ = 10

): Distance of 1 unit gives

K \approx exp (- 10) \approx 0.000045

— nearly zero. Even nearby points are treated as dissimilar. Each support vector influences only its immediate neighborhood. The decision boundary is wiggly and highly localized — it can fit any shape, but it overfits noise.Small $γ$ (e.g.,

γ = 0.1

): Distance of 1 unit gives

K \approx exp (- 0.1) \approx 0.90

— still very high similarity. Points influence each other over long distances. The boundary is smooth and generalizes well.

Gamma is like $1/ σ^{2}$ in a Gaussian distribution. A large

γ

means a narrow Gaussian. — only very close points are "similar." A small

γ

means a wide Gaussian — distant points still share similarity.

20.8.3 RBF and Infinite Dimensions via Taylor Series

The real power of the RBF kernel is that it corresponds to an infinite-dimensional feature space. You can prove this with the Taylor series of the exponential.

Recall the Taylor series:

e^{Z} = 1 + Z + \frac{Z ^{2}}{2 !} + \frac{Z ^{3}}{3 !} + \frac{Z ^{4}}{4 !} + \dots = k = 0 \sum \infty \frac{Z ^{k}}{k !}

Set

Z = 2 γ X \cdot Y

in the middle term of the RBF expansion:

exp (2 γ X \cdot Y) = 1 + 2 γ (X \cdot Y) + \frac{( 2 γ ) ^{2}}{2 !} (X \cdot Y)^{2} + \frac{( 2 γ ) ^{3}}{3 !} (X \cdot Y)^{3} + \dots = k = 0 \sum \infty \frac{( 2 γ ) ^{k}}{k !} (X \cdot Y)^{k}

Now here is the key insight: each term

(X \cdot Y)^{k}

is itself the exact result of a degree-

k

polynomial kernel. So the infinite sum is equivalent to using ALL polynomial kernels — degrees

0, 1, 2, 3. \dots

— simultaneously, weighted by the Taylor coefficients

\frac{( 2 γ ) ^{k}}{k !}

The full feature map for the RBF kernel is infinite-dimensional:

Φ (X) = e^{- γ ∥ X ∥^{2}} (1, \frac{2 γ}{1 !} X, \frac{( 2 γ ) ^{2}}{2 !} vec (X X^{T}), \frac{( 2 γ ) ^{3}}{3 !} \dots)

The factors

e^{- γ ∥ X ∥^{2}}

at the front ensure the dot product

Φ (X) \cdot Φ (Y)

exactly equals

exp (- γ ∥ X - Y ∥^{2})

. The

vec (X X^{T})

represents all degree-2 monomial terms, and the pattern continues for all degrees.

Why this matters: You do not need to decide whether your decision boundary is degree-2, degree-3, or degree-10. The RBF kernel grants the model access to all degrees simultaneously. The Taylor coefficients

\frac{( 2 γ ) ^{k}}{k !}

provide a natural weighting — they decay rapidly for large

k

(since

k!

grows fast). So very high-degree features contribute less unless

γ

is large. Tuning

γ

adjusts how much influence each degree gets.

Q: When should I use polynomial kernel versus RBF kernel?

A: The RBF kernel is, in practice, a superset of the polynomial kernel. If polynomial features of any degree provide good separation, the RBF kernel can capture that and more — and usually performs better. Most practitioners go straight to RBF. The real tuning effort goes into picking a good

γ

value through cross-validation. Tune

γ

well, and RBF handles almost any situation.

Q: When we project to a higher dimension, how do we identify the support vectors there?

A: You never explicitly find support vectors in the high-dimensional space. The support vectors remain the same data points from the original low-dimensional space. — the indices

i

with

α_{i} > 0

are the support vectors. The kernel trick computes what their dot products would be in the high-dimensional space without ever constructing that space. You try different kernels and gamma values and pick the one with the lowest classification error. The support vectors themselves do not change identity — only how their similarity to other points is computed changes.

Visual intuition. Two side-by-side plots. Left: RBF kernel with very small

γ = 0.01

— the decision boundary is almost a straight line. The Gram matrix heatmap shows a smooth, broad band of high similarity along the diagonal. Right: RBF kernel with

γ = 100

— the decision boundary wraps tightly around individual data points, creating complex isolated islands. The Gram matrix is nearly diagonal — each point is only similar to itself. Caption: "Small gamma = smooth, general boundary. Large gamma = wiggly, overfit boundary that treats each point as its own island."

Scope.

The RBF kernel's feature space is infinite-dimensional, so there is no explicit weight vector

w

you can inspect. You cannot say "feature 17 has weight 3.2" — the weights are implicitly encoded in the support vector coefficients.RBF kernels are stationary — they depend only on the distance

∥ X - Y ∥

, not on the absolute positions. This means the kernel cannot capture directional effects like "points in the right half of space behave differently."RBF kernels underperform on sparse, high-dimensional data (like bag-of-words text). Linear kernels often beat RBF on text because the data is already nearly linearly separable in the high-dimensional sparse space.

Pitfalls.

Not tuning $γ$ . The default

γ = 1/ (D \cdot Var (X))

in some libraries is a starting point, not an optimum. Always cross-validate

γ

over a logarithmic grid (e.g.,

{1 0^{- 3}, 1 0^{- 2}, \dots, 1 0^{3}}

).Gamma and $C$ are coupled. When you increase

γ

(more complex boundary). You often need to decrease

C

(stronger regularization) to prevent overfitting. Tune them together with a grid search.Large gamma + many support vectors = slow predictions. With a large gamma. Each support vector influences only a tiny region, so the model uses many support vectors to cover the space. Prediction time scales linearly with the number of support vectors.Forgetting to normalize features. The RBF kernel uses Euclidean distance, which is dominated by features with large scales. Standardize all features to zero mean and unit variance before using RBF.

Recap. The RBF kernel

K (X, Y) = exp (- γ ∥ X - Y ∥^{2})

measures local similarity — close points get near-1 similarity. Far points get near-0 similarity. Its Taylor expansion reveals it is equivalent to a weighted infinite sum of polynomial kernels of every degree. Gamma controls the "reach" of each point: small gamma means broad influence and smooth boundaries; large gamma means narrow influence and complex. Overfit boundaries.

Bridge. The RBF kernel is the gold standard in practice. But kernels need data where distance is meaningful. — the XOR problem on a number line shows perfectly how a kernel can fail in 1D but succeed in higher dimensions. Section 20.9 walks through a complete worked example of the kernel trick in action on a simple 1D-to-2D mapping.

Real-world connection. RBF-kernel SVMs were the state-of-the-art for image classification before deep learning took over (2000-2012). They still dominate in low-data regimes — bioinformatics (protein classification with few hundred samples). Chemoinformatics (drug activity prediction), and anomaly detection (one-class SVM with RBF). They are also the default kernel in scikit-learn's `SVC` class. In finance, RBF-SVMs predict credit defaults and fraud from tabular data with few features but complex non-linear interactions.

20.9 Kernel Trick: Worked Example

20.9.1 Problem Setup — 1D Non-Separable Data

Hook. The kernel trick sounds abstract until you see it in action. Here is the simplest possible non-separable dataset — three points on a 1D line. — and a feature map that makes them linearly separable in 2D. Every step is spelled out.

Problem. You have three points in one dimension:

Point	Coordinate	Label
$X = - 1$	$- 1$	$+ 1$ (positive)
$X = 0$	$0$	$- 1$ (negative)
$X = 1$	$1$	$+ 1$ (positive)

On the number line, the negative point at

X = 0

is sandwiched between two positive points at

- 1

and

+ 1

. No single threshold can separate them. Any cut at a threshold

t

places both positive points on one side. The negative point ends up on the other side only if one positive point is on the wrong side. For example, cut at

t = - 0.5

: positive at

- 1

is below (wrong). Positive at 1 is above (correct), negative at 0 is above (wrong). The data is fundamentally not linearly separable in 1D.

20.9.2 Feature Mapping to 2D

Define the feature map

Φ (X) = (X, X^{2})

. This lifts each 1D point into a 2D point:

Original $X$	$Φ (X) = (Z_{1}, Z_{2})$	Label
$- 1$	$(- 1, 1)$	$+ 1$
$1$	$(1, 1)$	$+ 1$
$0$	$(0, 0)$	$- 1$

In the new 2D space, the two positive points both sit at height

Z_{2} = 1

— one at

Z_{1} = - 1

. One at

Z_{1} = 1

. The negative point sits at the origin

(0, 0)

. A horizontal line at

Z_{2} = 0.5

cleanly separates the positive points (above the line) from the negative point (below the line). The data is now linearly separable.

Why $X^{2}$ ? The squared term folds the number line into a parabola. Points at

- 1

and

+ 1

both map to the same

X^{2}

value of

1

because squaring loses the sign. The negative point at

0

maps to

X^{2} = 0

. The sign-based distinction (both

- 1

and

+ 1

are positive class) becomes a height-based distinction in 2D.

20.9.3 Formulating Hard Margin SVM in the New Space

The transformed points are 2D, so the hyperplane equation is:

W_{1} Z_{1} + W_{2} Z_{2} + B = 0 where (Z_{1}, Z_{2}) = Φ (X)

The hard margin primal becomes:

W_{1}, W_{2}, B min \frac{1}{2} (W_{1}^{2} + W_{2}^{2})

subject to the constraints for each transformed point.

For $Φ (- 1) = (- 1, 1)$ with $Y = + 1$ :

+ 1 (W_{1} (- 1) + W_{2} (1) + B) \geq 1 ⟹ - W_{1} + W_{2} + B \geq 1

For $Φ (1) = (1, 1)$ with $Y = + 1$ :

+ 1 (W_{1} (1) + W_{2} (1) + B) \geq 1 ⟹ W_{1} + W_{2} + B \geq 1

For $Φ (0) = (0, 0)$ with $Y = - 1$ :

- 1 (W_{1} (0) + W_{2} (0) + B) \geq 1 ⟹ - B \geq 1 ⟹ B \leq - 1

Look at the structure. The first two constraints together require

W_{2} + B \geq 1

(adding them:

(- W_{1} + W_{2} + B) + (W_{1} + W_{2} + B) = 2 W_{2} + 2 B \geq 2

implies

W_{2} + B \geq 1

). The third constraint pins

B \leq - 1

. Since

W_{2}

is unconstrained by sign, you can satisfy these — for instance,

W_{2} = 2

and

B = - 1

works:

- W_{1} + 2 - 1 = - W_{1} + 1 \geq 1 ⟹ W_{1} \leq 0

W_{1} + 2 - 1 = W_{1} + 1 \geq 1 ⟹ W_{1} \geq 0

W_{1} = 0

W_{2} = 2

B = - 1

is a feasible solution. Giving the hyperplane

0 \cdot Z_{1} + 2 Z_{2} - 1 = 0

, or

Z_{2} = 0.5

. This is exactly the horizontal line we identified geometrically. The margin is

2/∥ W ∥ = 2/2 = 1

This is now a standard hard margin SVM in 2D. You can solve it using the same method as Section 20.3. The key takeaway: the feature map

Φ (X) = (X, X^{2})

turned a 1D non-separable problem into a 2D separable one. The kernel trick would let you do this without ever computing

Φ (X)

— but for this simple case. Explicit mapping is easy to understand and verify.

Visual intuition. Three panels. Left panel: a horizontal number line with points at

- 1

(blue, +1),

0

(red, -1), and

+ 1

(blue, +1). A vertical dashed line attempts to separate them — no position works. Middle panel: an arrow labeled

Φ (X) = (X, X^{2})

showing the mapping from the 1D line to a 2D coordinate system. Right panel: the

(Z_{1}, Z_{2})

plane with

(- 1, 1)

and

(1.1)

as blue points at the top, and

(0, 0)

as a red point at the bottom. A solid horizontal line at

Z_{2} = 0.5

cleanly separates them. The dashed line projects the 2D boundary back to the original 1D line. — it becomes two points marking where the decision boundary crosses the parabola's projection.

Scope.

The feature map

Φ (X) = (X, X^{2})

was chosen because we know the problem structure (positives at

\pm 1

, negative at 0). In general, you do not know the right mapping in advance. That is why you use kernels like RBF that implicitly try an infinite family of mappings.This explicit mapping approach (compute

Φ (X)

. Then run linear SVM) works for low-dimensional feature maps, but it defeats the purpose of the kernel trick. Real kernelized SVMs replace

X_{i} \cdot X_{j}

with

K (X_{i}, X_{j})

directly in the dual — no explicit mapping step.

Pitfalls.

Choosing the wrong mapping. If you used

Φ (X) = (X, X^{3})

instead. The positive points would map to

(- 1, - 1)

and

(1, 1)

— one above, one below — destroying the linear separability. The feature map must be chosen to match the data structure.Forgetting the bias. Even in the transformed space, you still need a bias

B

in the hyperplane equation. Without it, the decision boundary would be forced through the origin of the feature space, which may not separate the data.

Recap. Three 1D points

(- 1, + 1), (0, - 1), (1, + 1)

are not linearly separable on a line. The feature map

Φ (X) = (X, X^{2})

lifts them to 2D:

(- 1, 1), (0, 0), (1, 1)

. In 2D. The positives sit at height 1 and the negative at height 0 — a horizontal line at

Z_{2} = 0.5

separates them. The SVM primal in the transformed space produces this line as the maximum-margin solution.

Bridge. This section showed a concrete feature map worked by hand. In practice, you rarely know the right map. The RBF kernel (Section 20.8) avoids this choice by implicitly using an infinite-dimensional feature space. Section 20.10 rounds out the lecture with exam-oriented practice problems that test your ability to solve SVM problems of each type.

Real-world connection. The "1D non-separable to 2D separable via squaring" pattern appears in real problems too. In signal processing. Audio features at frequencies

f

and

1000 - f

Hz may belong to the same class (symmetric harmonics) while the midpoint

500

Hz belongs to the other. — exactly the same

- 1.0, + 1

structure after centering. A quadratic kernel or RBF kernel handles this naturally without manual feature engineering.

20.10 Practice Problem Types

20.10.1 Problem Types to Expect

Hook. You have seen the theory, the derivations, and a worked example. Now: what kind of problems will actually appear on the exam? Here is the complete list of SVM problem types you should be able to solve, organized by what they test.

Several distinct problem types appear regularly. Practice each one — the patterns repeat:

1. Primal formulation problems. You are given a small dataset (typically 3-4 points in 2D) and a value for

C

. Your task: write out the full soft-margin primal optimization problem.

Example structure:

Objective:

min \frac{1}{2} (W_{1}^{2} + W_{2}^{2}) + C (ξ_{1} + ξ_{2} + ξ_{3} + ξ_{4})

Constraint per point:

Y_{i} (W_{1} X_{i 1} + W_{2} X_{i 2} + B) \geq 1 - ξ_{i}

Non-negativity:

ξ_{i} \geq 0

for all

i

This tests whether you can mechanically translate labeled data points into the standard SVM form. The constraints must be written explicitly — for each point, plug in its coordinates and label.

2. Hinge loss calculation. Given a weight vector, bias, data point, and label, compute the loss.

Three-step recipe:

Compute

s = w \cdot X + B

(the raw linear output)Compute

Z = Y \cdot s

(the label-signed score)Compute

max (0, 1 - Z)

You may be asked to do this for multiple points and sum the losses. Remember: if

Z \geq 1

, the loss is zero regardless of how large

Z

is.

3. Support vector identification. Given a trained SVM (you have

w

B

, and the data points with labels). Determine which points are support vectors.

Hard margin: check if

Y_{i} (w \cdot X_{i} + B) = 1

(exactly on margin boundary). If it equals 1, the point is a support vector. If it is greater than 1, it is not.Soft margin: a point is a support vector if

Y_{i} (w \cdot X_{i} + B) \leq 1

(inside or on margin). Points with score less than 1 but on the correct side have

0 < ξ_{i} < 1

and are still support vectors. Misclassified points (score negative) are also support vectors.

4. Margin calculation. The margin is

2/∥ w ∥

. Compute

∥ w ∥ = W_{1}^{2} + W_{2}^{2} + \dots

and then divide 2 by it. Example:

w = (1, 2)

gives

∥ w ∥ = 5

and margin

= 2/ 5

5. Hard margin SVM with 2 points. Like the worked example in Section 20.3. With exactly two points of opposite class, you have three unknowns (

α_{1}, α_{2}, B

) and three equations. The solution path is always the same:

Write margin conditions

w \cdot X_{1} + B = Y_{1}

w \cdot X_{2} + B = Y_{2}

Replace

w

with

\sum α_{i} Y_{i} X_{i}

in both equationsUse

\sum α_{i} Y_{i} = 0

as the third equationCompute dot products, solve the linear system, and recover

w

and

B

6. Kernel mapping problems. Given a feature mapping like

Φ (X) = (X, X^{2}, X^{3})

, transform each data point into the new coordinates. Then formulate the hard-margin SVM in the new space. Write the primal or dual with the transformed points. This tests your ability to apply the kernel idea explicitly before seeing the implicit kernel trick.

20.10.2 Student Questions on Problem Types

Q: In exams, how many variables or data points will SVM problems have?

A: For finding the full linear hyperplane (solving for

α

w

. And

B

), you will typically get two data points — that makes the system solvable with three equations. You may also see problems with three or four points. In those, you are asked to write the primal formulation or identify which points are support vectors. You are not asked to solve the full optimization.

Q: Does the hard margin SVM always produce the perpendicular bisector for two opposite-class points?

A: Yes. With exactly two points of opposite classes, the maximum-margin hyperplane is always the perpendicular bisector of the segment joining them. The SVM math (the three-equation system) recovers this geometry exactly — a good sanity check after you solve. If your answer does not give the perpendicular bisector, you made an algebra mistake.

Pitfalls for exam problems.

Mixing up the margin formula. The margin is

2/∥ w ∥

, not

1/∥ w ∥

. The factor of 2 comes from the two margin boundaries at

\pm 1

. You lose a mark every time this is wrong.Forgetting the $\frac{1}{2}$ in the objective. The primal minimizes

\frac{1}{2} ∥ w ∥^{2}

, not

∥ w ∥^{2}

. If you write the objective without the

\frac{1}{2}

. Your derivative will be off by a factor of 2, and your dual will not match.Writing the constraint wrong. The primal constraint is

Y_{i} (w \cdot X_{i} + B) \geq 1

. Not

Y_{i} (w \cdot X_{i} + B) = 1

. The inequality is crucial — points must be at least one unit away, not exactly one unit.Skipping the $ξ_{i} \geq 0$ constraint. In soft margin. You need both

Y_{i} (w \cdot X_{i} + B) \geq 1 - ξ_{i}

AND

ξ_{i} \geq 0

. Forgetting the non-negativity is a common mistake.KKT sign errors. For equality constraints

h (x) = 0

in a minimization problem, the Lagrangian term is

+ μ h (x)

. In a maximization problem, it is

- μ h (x)

. The sign flips depending on whether you minimize or maximize. Many students get this wrong. For the SVM primal (minimization), the Lagrangian subtracts the constraints — see Section 20.1.3.

Exam priority order for SVM:

Two-point hard margin solution (Section 20.3) — most likely full-credit problemSoft margin primal formulation from data points — tests structural understandingHinge loss computation — quick calculation, easy marksSupport vector identification / margin calculation — tests interpretationKernel mapping — given

Φ (X)

, transform and set up SVM

Exam Guidance Summary

The post-midterm material (lectures 9 through 16, covering modules M5, M6, M7) receives roughly 70-80% of the marks. The remaining 20-30% comes from pre-midterm topics (lectures 1 through 8).

Post-midterm core areas. Three major problem domains drive the exam:

Gradient descent — RMSProp, momentum variants, convergence behaviorSVM — hard margin (2-point problems), soft margin primal formulation, hinge loss, support vector identification, margin computation, kernel trickPCA — principal component derivation, eigenvalue problems, variance explained

Exam problems typically combine two of these three areas. You may see gradient descent + PCA, or SVM + PCA. All three are unlikely to appear in a single exam.

SVM-specific exam notes:

Hard margin 2-point problem: Expect a problem with two data points — solve for

α

B

w

, and the decision boundary. Show every intermediate step. This is the most predictable SVM question. The solution always recovers the perpendicular bisector — use that fact to check your answer.Soft margin primal formulation: Given 3-4 points and a value for

C

, write the full optimization problem with all constraints. Every point gets its own constraint and its own

ξ_{i}

. Do not forget

ξ_{i} \geq 0

.Hinge loss: Be able to compute it for any given

w

B

, and data point. Three steps: dot product, multiply by label,

max (0, 1 - Z)

.Margin formula:

2/∥ w ∥

— know it without thinking. Also know that maximizing margin is equivalent to minimizing

∥ w ∥

\frac{1}{2} ∥ w ∥^{2}

.Kernel trick: Given a feature mapping

Φ (X)

, transform points and set up the SVM in the new space. Understand that implicit kernels compute the result without explicit mapping — the dual form reveals why.

Pre-midterm topics that matter for SVM context:

Rank of a matrix — problems on rank appear in nearly every exam. The Gram matrix

K_{ij} = K (X_{i}, X_{j})

must be full rank for the SVM dual to have a unique solution.Hessian matrix — second derivative structure and positive definiteness. The SVM objective

\frac{1}{2} ∥ w ∥^{2}

has Hessian

I

(identity), which is positive definite — guaranteeing convexity and a unique minimum.Partial derivatives and the chain rule — used throughout the Lagrangian derivation. Know how to differentiate

∥ w ∥^{2} = w^{T} w

to get

2 w

.Vector spaces — proving whether a set is a vector space. The dual variables

α

live in

R^{n}

with the linear constraint

\sum α_{i} Y_{i} = 0

, forming an affine subspace.Taylor series — the expansion

e^{Z} = \sum Z^{k} / k!

is required knowledge. And it connects directly to the RBF kernel's infinite-dimensional feature space interpretation (Section 20.8.3).

General exam advice:

Work through every problem in the practice document — they mirror the type and difficulty of exam questions exactly.Show all work in a clear, step-by-step manner. Write assumptions explicitly. Partial credit is awarded generously when the reasoning is visible.For constrained optimization, know when to use KKT conditions. For equality constraints

h (x) = 0

in a minimization problem, the Lagrangian term is

+ μ h (x)

. In a maximization problem, it becomes

- μ h (x)

. The sign convention flips depending on the optimization direction.Check your answer dimensionally. Does

w

have the right number of components? Is the bias

B

a scalar? Does

Y_{i} (w \cdot X_{i} + B)

give a value near 1 for the support vectors you identified?The perpendicular bisector check: if your 2-point SVM solution does not produce the line perpendicular to the segment connecting the points and passing through its midpoint. Something went wrong. Re-check your algebra.

Key Industry Applications

SVM with RBF kernel as the standard baseline. SVM with the RBF kernel is a reliable. Well-understood classifier for tabular data, text classification, and bioinformatics. You tune exactly one hyperparameter — gamma — and get competitive results without the architecture search that neural networks demand. In credit scoring, SVMs classify loan applicants as low-risk or high-risk from structured financial features. In bioinformatics, SVMs with custom string kernels classify protein sequences into structural families. In spam detection, linear SVMs on bag-of-words features still achieve >99% accuracy on clean datasets.

The kernel trick beyond SVM. The kernel trick — replacing dot products with kernel evaluations. — applies to any algorithm whose computation depends only on pairwise similarities. This gives rise to:

Kernel PCA: non-linear dimensionality reduction for visualizing high-dimensional dataKernel ridge regression: non-linear regression with L2 regularizationKernel k-means: non-linear clustering that can separate concentric ringsKernel canonical correlation analysis (CCA): finding non-linear relationships between two datasets

The same mathematical insight (Mercer's theorem guarantees that any positive semidefinite function corresponds to a dot product in some Hilbert space) unifies all these methods. If you understand the SVM dual and the kernel trick, you understand a design pattern that recurs across machine learning.

The combinatorial cost of explicit feature expansion. The formula

(P D + P)

for polynomial feature count is the reason feature engineering pipelines fail on high-dimensional data. A 100-feature dataset with degree-3 interactions generates ~176,851 features — more than the number of training examples in most tabular datasets. This "curse of dimensionality" in feature space is exactly what kernels avoid. The same combinatorial explosion affects polynomial regression, interaction-term models in statistics, and any explicit basis-function expansion. Recognizing this limit is essential for practical machine learning. — it tells you when to reach for kernels or deep learning instead of manual feature creation.

Hinge loss as a general-purpose classification loss. The hinge loss

max (0, 1 - Z)

appears beyond SVM:

Structured SVMs use hinge loss for predicting sequences, trees, and graphsRanking SVMs minimize hinge loss over pairwise preferences (document A should rank above document B)Maximum-margin neural networks combine hinge loss with neural architectures. Especially in few-shot learning and metric learning where the margin itself is the quantity of interest

The property that makes hinge loss special is the zero-loss zone for

Z \geq 1

. Points that are "comfortably correct" generate no gradient signal and do not influence the optimizer. This sparsity is why SVM generalizes well — it actively ignores the majority of the data that is already well-classified. Compare this to cross-entropy loss (used in logistic regression and neural networks), which always produces non-zero gradients even for correctly classified points. — driving probabilities toward 0 or 1 but never being satisfied.

When to use SVM (and when not to). SVMs are the right choice when:

Your dataset is small to medium (~100 to ~10,000 examples). Training time scales as

O (n^{2})

O (n^{3})

with the number of training examples.Your features are moderately dimensional and you do not have deep domain knowledge about feature interactions. — the RBF kernel handles non-linear relationships automatically.You need a deterministic. Reproducible baseline — SVMs with fixed random seeds and cross-validated hyperparameters produce identical results on reruns (unlike neural networks with random initialization).

SVMs are not ideal when:

Your dataset has millions of examples — kernel methods become too slow. Use linear SVMs or logistic regression instead.Your data is raw pixels, audio waveforms, or text tokens — deep learning extracts hierarchical features that kernels cannot.You need probabilistic outputs (class membership probabilities) — SVM outputs raw scores that need Platt scaling to convert to probabilities. Adding an extra calibration step.

MFML Lecture 20 notes · Support Vector Machines

Mathematical Foundations for Machine Learning· postgraduate· 2026-07-11

Sections Breakdown

120.1 Hard Margin SVM — Review

20.1 Hard Margin SVM — Review

220.2 Support Vectors via Complementary Slackness

20.2 Support Vectors via Complementary Slackness

320.3 Hard Margin SVM: Worked Numerical Example

20.3 Hard Margin SVM: Worked Numerical Example

420.4 Soft Margin SVM

20.4 Soft Margin SVM

520.5 Hinge Loss

20.5 Hinge Loss

620.6 The Kernel Trick

20.6 The Kernel Trick

720.7 Polynomial Kernel

20.7 Polynomial Kernel

820.8 Radial Basis Function (RBF) Kernel

20.8 Radial Basis Function (RBF) Kernel

920.9 Kernel Trick: Worked Example

20.9 Kernel Trick: Worked Example

1020.10 Practice Problem Types

20.10 Practice Problem Types

11Exam Guidance Summary

Exam Guidance Summary

12Key Industry Applications

Key Industry Applications

Postgraduate students in Machine Learning

Exam Revision Notes

Below is the distilled, exam-ready core of this lecture. Every entry is built from the full textbook notes above. Use this section for rapid review — but if something doesn't make sense, go back to the full explanation in the main content.

Hard-Margin SVM

Must-know: SVM finds the hyperplane that separates the two classes with the widest possible margin. The margin equals

2/∥ w ∥

; maximizing it is the same as minimizing

\frac{1}{2} ∥ w ∥^{2}

w, B min \frac{1}{2} ∥ w ∥^{2} s.t. Y_{i} (w \cdot X_{i} + B) \geq 1

⚠️ Top pitfall: Writing the margin as

1/∥ w ∥

instead of

2/∥ w ∥

. The factor of 2 comes from the two boundaries at

\pm 1

Self-check: Why does pinning the boundaries at

\pm 1

not lose generality?

Connects to: Dual formulation, support vectors, soft margin.

Support Vectors & Complementary Slackness

Must-know: Complementary slackness forces

α_{i} > 0

only for points that sit exactly on the margin. Those are the support vectors; they alone build

w = \sum_{i : α_{i} > 0} α_{i} Y_{i} X_{i}

. All other points contribute nothing.

α_{i} [Y_{i} (w \cdot X_{i} + B) - 1] = 0 \forall i

⚠️ Top pitfall: Assuming every point with

α_{i} > 0

is on the margin. In soft margin that is false — points inside or past the margin also have positive

α_{i}

Self-check: If you delete a point far from the boundary, does the classifier change?

Connects to: Hard-margin SVM, the dual, sparsity, kernel trick.

Two-Point Worked Example

Must-know: With exactly two opposite-class points the max-margin line is the perpendicular bisector. Solve three equations: two margin conditions plus

\sum α_{i} Y_{i} = 0

w = α_{1} Y_{1} X_{1} + α_{2} Y_{2} X_{2}, α_{1} = α_{2} = \frac{1}{4}, B = \frac{5}{2}

⚠️ Top pitfall: Forgetting to solve for the bias

B

from the equations instead of assuming it is 1.

Self-check: Does your answer give the line perpendicular to the segment joining the two points, through its midpoint?

Connects to: Hard margin, support vectors, margin calculation.

Soft-Margin SVM

Must-know: Slack variables

ξ_{i} \geq 0

let points violate the margin at a cost

C ξ_{i}

. Large

C

gives a narrow margin (overfitting); small

C

gives a wide margin (better generalization).

w, B, ξ min \frac{1}{2} ∥ w ∥^{2} + C i \sum ξ_{i} s.t. Y_{i} (w \cdot X_{i} + B) \geq 1 - ξ_{i}

⚠️ Top pitfall: Not normalizing features before tuning

C

C

is scale-sensitive, so the same

C

behaves very differently after rescaling.

Self-check: What happens to the dual box constraint as

C \to \infty

Connects to: Hinge loss, the dual, the

C

hyperparameter.

Hinge Loss

Must-know: Eliminating the slacks gives the hinge loss

max (0, 1 - Z_{i})

, where

Z_{i} = Y_{i} (w \cdot X_{i} + B)

is the label-signed score. It is zero for comfortably correct points and grows linearly otherwise.

ℓ_{hinge} (Z_{i}) = max (0, 1 - Z_{i}), Z_{i} = Y_{i} (w \cdot X_{i} + B)

⚠️ Top pitfall: Using the raw dot product

w \cdot X + B

as the score. You must multiply by the label

Y_{i}

first.

Self-check: For

w = (1, 1), B = - 1.5

and

X = (2, 2), Y = + 1

, what is the hinge loss?

Connects to: Soft margin, regularization, support vector identification.

The Kernel Trick

Must-know: The dual depends only on dot products. So every

X_{i} \cdot X_{j}

can be replaced by a kernel

K (X_{i}, X_{j})

that computes a high-dimensional inner product directly — no explicit mapping needed.

f (X) = i \sum α_{i} Y_{i} K (X_{i}, X) + B

⚠️ Top pitfall: Thinking the kernel "auto-wins". A badly chosen kernel can do worse than a linear SVM; start with linear as a baseline.

Self-check: Which two properties must a kernel satisfy (Mercer's condition)?

Connects to: Polynomial kernel, RBF kernel, similarity-based prediction.

Polynomial Kernel

Must-know:

K (X, Y) = (X \cdot Y + c)^{d}

computes the dot product of all polynomial features up to degree

d

from a single number. Avoiding the

(d D + d)

feature explosion.

K (X, Y) = (X \cdot Y + c)^{d}

⚠️ Top pitfall: Choosing a degree too high. Degree-10 or 20 kernels almost always overfit; in practice most people skip straight to RBF.

Self-check: What does the constant

c

control in the inhomogeneous polynomial kernel?

Connects to: Kernel trick, RBF kernel, feature explosion.

RBF (Gaussian) Kernel

Must-know:

K (X, Y) = exp (- γ ∥ X - Y ∥^{2})

measures local similarity and is equivalent to an infinite sum of polynomial kernels (Taylor series). Small

γ

= smooth boundary; large

γ

= wiggly, overfit boundary.

K (X, Y) = exp (- γ ∥ X - Y ∥^{2})

⚠️ Top pitfall: Treating

γ

and

C

as independent. Raising

γ

usually requires lowering

C

to avoid overfitting; tune them together.

Self-check: Why does the RBF kernel correspond to an infinite-dimensional feature space?

Connects to: Kernel trick, polynomial kernel, gamma tuning.

Kernel Worked Example (1D → 2D)

Must-know: The map

Φ (X) = (X, X^{2})

lifts three 1D points

(- 1, + 1), (0, - 1), (1, + 1)

into a 2D space where a horizontal line at

Z_{2} = 0.5

separates them — the maximum-margin solution.

Φ (X) = (X, X^{2}), margin = \frac{2}{∥ W ∥} = \frac{2}{2} = 1

⚠️ Top pitfall: Picking the wrong feature map.

Φ (X) = (X, X^{3})

would scatter the positives to opposite sides and destroy separability.

Self-check: Why does squaring the number line fold

- 1

and

+ 1

to the same height?

Connects to: Kernel trick, RBF, non-linear separability.

Exam Problem Types

Must-know: Expect: two-point hard-margin solutions, soft-margin primal formulation from data, hinge-loss computation, support-vector / margin identification, and kernel mapping. Show every algebra step.

margin = \frac{2}{∥ w ∥}, hinge = max (0, 1 - Z), Z = Y (w \cdot X + B)

⚠️ Top pitfall: Dropping the

\frac{1}{2}

in the objective, or writing the constraint as an equality

= 1

instead of

\geq 1

Self-check: For two opposite-class points, what geometry must your answer always recover?

Connects to: Every concept in this lecture.

Previous LectureLecture 19 · Support Vector Machines — Hard Margin Classifier

Next LectureLecture 01 · Introduction to Natural Language Processing

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

20.1 Hard Margin SVM — Review

20.1.1 Maximizing the Margin

20.1.2 The Primal Optimization Problem

20.1.3 Lagrangian and Dual Formulation

20.2 Support Vectors via Complementary Slackness

20.2.1 Complementary Slackness Condition

20.2.2 Support Vectors Define the Classifier

20.3 Hard Margin SVM: Worked Numerical Example

20.3.1 Problem Setup

20.3.2 Expressing w in Terms of Data Points

20.3.3 The Third Equation and Dot Product Computation

20.3.4 Solving the System of Equations

20.3.5 Geometric Interpretation

20.3.6 Student Questions on the Worked Example

20.4 Soft Margin SVM

20.4.1 The Slack Variable

20.4.2 Soft Margin Primal Form

20.4.3 The C Parameter — Trade-off Control

20.4.4 Soft Margin Dual Form

20.5 Hinge Loss

20.5.1 Deriving the Hinge Loss

20.5.2 Two Cases for the Hinge Loss

20.6 The Kernel Trick

20.6.1 Non-Linear Separability

20.6.2 Projecting to Higher Dimensions

20.6.3 SVM as a Similarity-Based Classifier

20.6.4 The Kernel Trick Intuition

20.7 Polynomial Kernel

20.7.1 Polynomial Feature Explosion

20.7.2 The Polynomial Kernel Formula

20.8 Radial Basis Function (RBF) Kernel

20.8.1 RBF Kernel Formula

20.8.2 Gamma as a Scaling Parameter

20.8.3 RBF and Infinite Dimensions via Taylor Series

20.9 Kernel Trick: Worked Example

20.9.1 Problem Setup — 1D Non-Separable Data

20.9.2 Feature Mapping to 2D

20.9.3 Formulating Hard Margin SVM in the New Space

20.10 Practice Problem Types

20.10.1 Problem Types to Expect

20.10.2 Student Questions on Problem Types

Exam Guidance Summary

Key Industry Applications

MFML Lecture 20 notes · Support Vector Machines

Sections Breakdown

Exam Revision Notes

Hard-Margin SVM

Support Vectors & Complementary Slackness

Two-Point Worked Example

Soft-Margin SVM

Hinge Loss

The Kernel Trick

Polynomial Kernel

RBF (Gaussian) Kernel

Kernel Worked Example (1D → 2D)

Exam Problem Types

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat

20.3.2 Expressing $w$ in Terms of Data Points