Support vector machines and kernels
Concise study notes on Support Vector Machines (SVM) and kernels: definitions, primal and dual formulations, margin geometry, kernel trick, Mercer's condition, worked derivations and exam-style examples.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
SVMs are a widely used supervised-learning method for binary classification and ranking tasks. An engineer uses SVMs when a robust maximum-margin linear separator is needed, or when a non-linear decision boundary is required via kernels without explicit high-dimensional feature construction.
Key ideas
Support vector: a training example that lies on one of the margin boundaries (i.e., satisfies y_i(w·x_i + b) = 1 for the hard-margin case). These points determine the hyperplane.
Primal (hard-margin) SVM problem (assumption: data is linearly separable): Minimise (1/2) ||w||^2 subject to y_i (w·x_i + b) ≥ 1 for all i. The objective minimises model complexity (||w||^2) while constraints enforce correct classification with margin 1.
Derivation of margin width (for exam diagram):
- Draw a 2D scatter plot with two classes; draw a line as the separating hyperplane (label it w·x + b = 0). Draw two parallel lines equidistant from this plane: w·x + b = 1 and w·x + b = -1. Mark the closest points on each side (support vectors) and label them x+ and x-.
- The distance from a point x0 to hyperplane w·x + b = 0 is |w·x0 + b| / ||w|| (derive by projecting vector from point to plane along unit normal w/||w||).
- For x+ on w·x + b = 1, distance = 1/||w||; for x- on w·x + b = -1, distance = 1/||w||. So margin width = 1/||w|| + 1/||w|| = 2/||w||.
Soft-margin SVM (for non-separable or noisy data): introduce slack variables ξ_i ≥ 0 and penalty parameter C > 0. Minimise (1/2) ||w||^2 + C Σ_i ξ_i subject to y_i (w·x_i + b) ≥ 1 - ξ_i and ξ_i ≥ 0. C balances margin width vs misclassification/softness. Equivalently, minimize the regularized hinge loss: (1/2)||w||^2 + C Σ_i max(0, 1 - y_i(w·x_i + b)).
Use of Lagrangian and formation of dual problem (common exam derivation steps):
- Form Lagrangian L(w,b,ξ,α,μ) combining objective and constraints with multipliers α_i ≥ 0 (for classification constraints) and μ_i ≥ 0 (for ξ_i ≥ 0).
- Take partial derivatives of L with respect to primal variables (w, b, ξ) and set to zero to obtain stationarity conditions linking w to α and conditions Σ α_i y_i = 0 and α_i ≤ C (for soft-margin).
- Substitute back to eliminate primal variables and get the dual quadratic program in α: Maximise Σ_i α_i - (1/2) Σ_i Σ_j α_i α_j y_i y_j (x_i·x_j) subject to Σ_i α_i y_i = 0 and 0 ≤ α_i ≤ C (soft-margin). For hard-margin, drop upper bound α_i ≤ C.
Decision function (dual form): once optimal α* found, w = Σ_i α*_i y_i x_i and b can be found from support vectors. A test point x is classified by sign(f(x)) where f(x) = Σ_i α*_i y_i (x_i·x) + b.
Kernel and kernel trick: a kernel function K(x, z) computes an inner product in some (possibly high-dimensional) feature space: K(x, z) = φ(x)·φ(z) where φ is a feature map. The dual depends on inner products x_i·x_j only; replacing them by K(x_i, x_j) we obtain a non-linear SVM without explicitly computing φ(x): f(x) = Σ_i α*_i y_i K(x_i, x) + b.
Common kernels:
- Linear kernel: K(x, z) = x·z (same as no mapping).
- Polynomial kernel (degree p): K(x, z) = (γ x·z + r)^p, typically with p ∈ N, γ > 0, r ≥ 0 to ensure PSD. Example: (1 + x·z)^2 expands to a quadratic feature map (see worked example).
- Radial basis function (RBF/Gaussian): K(x, z) = exp(-||x - z||^2 / (2σ^2)) = exp(-γ ||x - z||^2) with γ = 1/(2σ^2).
Mercer’s condition / positive semi-definite kernel: For K to be a valid kernel in SVMs, the Gram matrix [K(x_i, x_j)] over any finite set {x_i} must be symmetric and positive semi-definite (i.e., for any vector v, v^T K v ≥ 0). Mercer’s theorem (for continuous kernels on compact domains) gives an eigenfunction expansion, but PSD of all Gram matrices is the operative requirement.
KKT conditions: at optimum, complementary slackness holds: α_i [y_i(w·x_i + b) - 1 + ξ_i] = 0 and μ_i ξ_i = 0. For hard-margin, μ_i and ξ_i are absent and α_i > 0 only for support vectors.
Diagram to draw in exams (describe): Draw 2D axes, two classes with a gap. Draw central hyperplane labeled w·x + b = 0. Draw margin lines w·x + b = ±1 parallel to it. Mark support vectors on the margin lines and draw the normal vector w perpendicular to hyperplane from negative to positive side. Label the margin distance 2/||w||.
Formulas
Primal (hard-margin): minimize (1/2) ||w||^2 subject to y_i (w·x_i + b) ≥ 1 — assume features are scaled to be dimensionless; then w, b, and y_i(w·x_i + b) are dimensionless; applies when data is linearly separable.
Margin width = 2 / ||w|| — ||w|| is the Euclidean norm of w; with dimensionless features the margin is dimensionless; applies for canonical margin hyperplanes w·x + b = ±1.
Soft-margin primal: minimize (1/2) ||w||^2 + C Σ_i ξ_i subject to y_i (w·x_i + b) ≥ 1 - ξ_i, ξ_i ≥ 0 — C > 0 is the penalty parameter; with dimensionless features, both C and ξ_i are dimensionless (otherwise C carries units matching ||w||^2).
Dual (soft-margin): maximize Σ_i α_i - (1/2) Σ_i Σ_j α_i α_j y_i y_j (x_i·x_j) subject to Σ_i α_i y_i = 0 and 0 ≤ α_i ≤ C — α_i are Lagrange multipliers; with dimensionless features they are dimensionless; applies after forming the Lagrangian and eliminating primal variables.
Decision function: f(x) = Σ_i α_i y_i K(x_i, x) + b — classify by sign(f(x)); K replaces inner products via the kernel trick; b as above.
Kernel substitution: replace x_i·x_j by K(x_i, x_j) — applies to dual and decision function.
RBF kernel: K(x, z) = exp(-||x - z||^2 / (2 σ^2)) — σ > 0 is the kernel width; equivalently K(x, z) = exp(-γ ||x - z||^2) with γ = 1/(2σ^2).
Polynomial kernel (p=2, γ=1, r=1): K(x, z) = (1 + x·z)^2 — corresponds to a quadratic feature map; more generally, p ∈ N with γ > 0 and r ≥ 0 yields a valid polynomial kernel.
Worked examples
Example 1 — Derive the dual from the hard-margin primal (model exam answer):
- Primal: minimize (1/2)||w||^2 s.t. y_i(w·x_i + b) ≥ 1.
- Lagrangian: L(w,b,α) = (1/2)||w||^2 - Σ_i α_i [y_i(w·x_i + b) - 1], with α_i ≥ 0.
- Stationarity: ∂L/∂w = w - Σ_i α_i y_i x_i = 0 ⇒ w = Σ_i α_i y_i x_i.
- ∂L/∂b = -Σ_i α_i y_i = 0 ⇒ Σ_i α_i y_i = 0.
- Substitute w into L and eliminate primal variables to get dual: maximize W(α) = Σ_i α_i - (1/2) Σ_i Σ_j α_i α_j y_i y_j x_i·x_j subject to α_i ≥ 0 and Σ_i α_i y_i = 0.
- This is a quadratic programming (QP) problem. Support vectors correspond to α_i > 0.
Example 2 — Polynomial kernel mapping (explicit): show (1 + x·z)^2 is a kernel in R^2 and give φ(x).
- Let x = (x1, x2), z = (z1, z2). Expand: (1 + x·z)^2 = 1 + 2(x1 z1 + x2 z2) + (x1 z1 + x2 z2)^2.
- Expand the square: = 1 + 2x1 z1 + 2x2 z2 + x1^2 z1^2 + 2 x1 x2 z1 z2 + x2^2 z2^2.
- Choose φ(x) = [1, sqrt(2) x1, sqrt(2) x2, x1^2, sqrt(2) x1 x2, x2^2]. Then φ(x)·φ(z) gives the same expansion. So K(x,z) = (1 + x·z)^2 = φ(x)·φ(z). (This proves K is a valid kernel and shows explicit features.)
Example 3 — Simple dual decision evaluation (numerical toy): Given two support vectors x1 = (1,0) with y1 = +1 and x2 = (0,1) with y2 = -1. Suppose from solving dual we have α1 = α2 = 0.5 and b = 0. Use linear kernel K(x,z)=x·z. Classify x = (1,1). Compute f(x) = Σ α_i y_i (x_i·x) + b = 0.5*(+1)(11 + 01) + 0.5(-1)(01 + 1*1) = 0.5 - 0.5 = 0. So x lies exactly on the decision boundary (classifier output 0). Final classification: sign(0) is conventionally 0 (boundary) — if forced to ±1, handle by tie rule. Answer: f(x)=0.
Common mistakes
- Using α_i ≤ C only for soft-margin; for hard-margin there is no upper bound.
- Forgetting to compute b from support vectors (one correct formula: for any support vector i with 0 < α_i < C, b = y_i - Σ_j α_j y_j K(x_j, x_i)).
- Mis-expanding polynomial kernels or missing normalization constants (e.g., sqrt(2) factors) when writing explicit φ(x).
- Thinking any symmetric function is a kernel; must be positive semi-definite over any finite set (Mercer condition).
For your exam
Kinds of questions: definitions (define margin, support vector, kernel), short notes (soft vs hard margin, kernel trick), derivations (derive dual from primal using Lagrangian and KKT), numericals (compute margin, classify a point given α, compute φ for a polynomial kernel), diagrams (draw hyperplane and margins), proofs (show margin = 2/||w||, show kernel corresponds to inner product for given φ), multi-class strategies (one-vs-rest, one-vs-one).
What full-marks answers include:
- For derivations: clear statement of primal, correct Lagrangian, stationarity conditions, elimination of primal variables, final dual QP with constraints, and statement about how to recover w and b.
- For kernel questions: explicit φ when requested, and justification of positive semi-definiteness (Gram matrix argument) or citation of Mercer’s theorem.
- For numerical/classification: show substitution into decision function, compute step-by-step, final numeric value and class label.
Quick check
- Define a support vector.
- State the dual SVM optimisation problem constraints (soft-margin case).
- Give the formula for the RBF kernel. Answers: 1) A training point with α_i > 0 in the optimal solution; in soft-margin SVM, if 0 < α_i < C it lies on the margin (y_i(w·x_i + b) = 1), while α_i = C indicates it is inside the margin or misclassified. 2) Σ_i α_i y_i = 0 and 0 ≤ α_i ≤ C, maximise Σ_i α_i - (1/2) Σ_i Σ_j α_i α_j y_i y_j x_i·x_j. 3) K(x,z)=exp(-||x-z||^2/(2σ^2)).
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?