Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

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):

    1. 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-.
    2. 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||).
    3. 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):

    1. Form Lagrangian L(w,b,ξ,α,μ) combining objective and constraints with multipliers α_i ≥ 0 (for classification constraints) and μ_i ≥ 0 (for ξ_i ≥ 0).
    2. 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).
    3. 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):

  1. Primal: minimize (1/2)||w||^2 s.t. y_i(w·x_i + b) ≥ 1.
  2. Lagrangian: L(w,b,α) = (1/2)||w||^2 - Σ_i α_i [y_i(w·x_i + b) - 1], with α_i ≥ 0.
  3. Stationarity: ∂L/∂w = w - Σ_i α_i y_i x_i = 0 ⇒ w = Σ_i α_i y_i x_i.
  4. ∂L/∂b = -Σ_i α_i y_i = 0 ⇒ Σ_i α_i y_i = 0.
  5. 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.
  6. 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).

  1. Let x = (x1, x2), z = (z1, z2). Expand: (1 + x·z)^2 = 1 + 2(x1 z1 + x2 z2) + (x1 z1 + x2 z2)^2.
  2. Expand the square: = 1 + 2x1 z1 + 2x2 z2 + x1^2 z1^2 + 2 x1 x2 z1 z2 + x2^2 z2^2.
  3. 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

  1. Define a support vector.
  2. State the dual SVM optimisation problem constraints (soft-margin case).
  3. 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?