Ch 7: Sparse Kernel Machines

Chapter 0: Why Sparsity?

In Chapter 6, we saw that kernel methods like Gaussian processes make predictions using all N training points. The predictive function is a weighted sum over every data point:

y(x) = ∑_n=1^N a_n k(x, x_n)

This means prediction costs O(N) per test point — expensive when N is large. Can we find solutions where most of the coefficients a_n are exactly zero?

The sparsity goal: A sparse kernel machine uses only a small subset of the training data to make predictions. If only S out of N points have nonzero coefficients (S « N), prediction costs O(S) instead of O(N). The data points with nonzero coefficients are called support vectors (in SVMs) or relevance vectors (in RVMs).

This chapter covers two approaches to achieving sparsity:

Support Vector Machines (SVMs): Find the maximum margin decision boundary. Sparsity emerges from the geometry — only points on the margin boundary matter.

Relevance Vector Machines (RVMs): Use a Bayesian prior with individual hyperparameters per weight. Sparsity emerges from evidence maximization — most hyperparameters go to infinity, pruning their weights to zero.

Check: Why is sparsity desirable in kernel methods?

It reduces prediction cost from O(N) to O(S) where S is the number of active data points It makes the kernel matrix easier to invert It eliminates the need for a kernel function

Chapter 1: Maximum Margin Classifiers

Consider a two-class problem with a linear decision boundary y(x) = w^Tφ(x) + b. Many hyperplanes can separate the classes perfectly. Which one should we choose?

The margin is the perpendicular distance from the decision boundary to the nearest data point. The SVM chooses the hyperplane that maximizes this margin.

Why maximum margin? Intuitively, a large margin means the classifier is confident about its decision — there's a wide "buffer zone" between classes. A small perturbation to a test point won't change its classification. Formally, computational learning theory (VC theory) shows that larger margins lead to better generalization bounds, independent of the input dimensionality.

The distance from point x_n to the decision surface is t_ny(x_n)/||w||. We want to maximize the minimum such distance:

arg max_w,b { (1/||w||) min_n [t_n(w^Tφ(x_n) + b)] }

Using the canonical representation (rescaling so the closest point has t_ny(x_n) = 1), this becomes:

arg min_w,b ½||w||² subject to t_n(w^Tφ(x_n) + b) ≥ 1 ∀n

This is a quadratic program — minimize a quadratic objective subject to linear inequality constraints. It has a unique global solution.

Check: What does the SVM maximize?

The margin — the perpendicular distance from the decision boundary to the nearest data point The training accuracy The number of support vectors

Chapter 2: The Lagrangian Dual

To solve the constrained optimization, we introduce Lagrange multipliers a_n ≥ 0 for each constraint:

L(w, b, a) = ½||w||² − ∑_n=1^N a_n{t_n(w^Tφ(x_n) + b) − 1}

Setting derivatives to zero: ∂L/∂w = 0 gives w = ∑_n a_n t_n φ(x_n), and ∂L/∂b = 0 gives ∑_n a_n t_n = 0.

Substituting back, we get the dual problem:

maximize L̃(a) = ∑_n=1^N a_n − ½ ∑_n=1^N ∑_m=1^N a_n a_m t_n t_m k(x_n, x_m)

subject to a_n ≥ 0 and ∑_n a_n t_n = 0, where k(x_n, x_m) = φ(x_n)^Tφ(x_m) is the kernel function.

The kernel trick appears: The dual problem depends on the data only through kernel evaluations k(x_n, x_m). We never need to compute φ(x) explicitly. This means we can use infinite-dimensional feature spaces (via the Gaussian kernel, for example) at finite computational cost.

The KKT conditions (Karush-Kuhn-Tucker) require that a_n{t_ny(x_n) − 1} = 0 for every n. This means either a_n = 0 (the point is irrelevant to the solution) or t_ny(x_n) = 1 (the point sits exactly on the margin). Points with a_n > 0 are the support vectors.

Prediction for a new point:

y(x) = ∑_{n ∈ SV} a_n t_n k(x, x_n) + b

Only support vectors contribute. The rest of the training data can be discarded.

Check: What are support vectors?

Training points with nonzero Lagrange multipliers, lying exactly on the margin boundary All training points that are correctly classified The eigenvectors of the kernel matrix

Chapter 3: The Soft Margin

Real data is rarely linearly separable, even in feature space. We need to allow some points to be misclassified. The soft margin SVM introduces slack variables ξ_n ≥ 0:

t_n(w^Tφ(x_n) + b) ≥ 1 − ξ_n

If ξ_n = 0, the point is correctly classified and on or beyond the margin. If 0 < ξ_n < 1, the point is correctly classified but inside the margin. If ξ_n > 1, the point is misclassified.

The objective becomes:

min_w,b,ξ ½||w||² + C ∑_n=1^N ξ_n

The parameter C controls the tradeoff: large C → fewer violations (potentially overfitting), small C → wider margin (more violations allowed).

The C parameter: C is the SVM's complexity parameter. It plays the same role as inverse regularization strength: large C is like low regularization (fit the data closely), small C is like high regularization (prefer simplicity). Unlike Bayesian methods, C must be set by cross-validation.

The dual of the soft-margin SVM is almost identical to the hard-margin case, except that now 0 ≤ a_n ≤ C. Points with 0 < a_n < C lie on the margin; points with a_n = C are inside the margin or misclassified. An alternative formulation using a parameter ν ∈ (0, 1] replaces C and has a nice interpretation: ν is an upper bound on the fraction of margin errors and a lower bound on the fraction of support vectors.

Check: What do slack variables allow in the soft-margin SVM?

Some data points to fall inside the margin or be misclassified, controlled by the penalty parameter C The kernel function to be non-positive-definite The margin to become negative

Chapter 4: SVM vs Logistic Regression

The SVM and logistic regression are more closely related than they might appear. Both find a linear decision boundary in feature space. The difference is in the loss function.

Method	Loss function	Outputs
Logistic regression	ln(1 + exp(−t_ny_n)) — log loss	Probabilities p(C₁\|x)
SVM	[1 − t_ny_n]₊ — hinge loss	Decisions only (sign of y)

The hinge loss [1 − ty]₊ = max(0, 1 − ty) is zero whenever ty ≥ 1, i.e., when the point is correctly classified and beyond the margin. This is why SVMs produce sparse solutions: points safely classified contribute zero loss and zero gradient, so they have no influence on the solution.

Sparsity from the hinge loss: The hinge loss has a "flat region" for ty ≥ 1 where the gradient is exactly zero. This is what causes sparsity — points in this region don't affect the solution. Logistic regression's log loss is always positive and always has a nonzero gradient, so every point influences the solution. No sparsity.

To get probabilities from an SVM, one can fit a sigmoid to the SVM outputs: p(t=1|x) = σ(Ay(x) + B), where A and B are fitted on a validation set. This is known as Platt scaling.

Check: Why does the SVM produce sparse solutions but logistic regression does not?

The hinge loss has a flat region where correctly classified points contribute zero gradient SVMs use a different kernel Logistic regression has too many parameters

Chapter 5: Multiclass & SVR

The SVM is inherently a two-class classifier. Extension to K classes is ad hoc:

One-vs-rest: Train K separate SVMs, each separating one class from the rest. Assign the class with the largest y(x). Problem: different SVMs have different scales, and there's ambiguous regions.

One-vs-one: Train K(K−1)/2 SVMs, one for each pair of classes. Use majority voting. Problem: quadratic number of classifiers and inconsistent decisions.

For regression, the SVM uses the ε-insensitive loss:

E_ε(y − t) = max(0, |y − t| − ε)

This loss is zero when the prediction is within ε of the target. The ε-tube around the regression function plays the same role as the margin: only data points outside the tube (with |y_n − t_n| > ε) contribute to the solution.

Support vector regression (SVR): The ε-insensitive loss creates sparsity in regression: points inside the ε-tube have zero loss and don't affect the solution. The regression function is expressed as a weighted sum over support vectors only. The parameter ε controls the width of the tube and hence the sparsity: larger ε gives fewer support vectors but a coarser fit.

Check: How does the ε-insensitive loss achieve sparsity in SVR?

Points within ε of the prediction contribute zero loss and zero gradient, so they don't influence the solution It forces all weights to be positive It uses L1 regularization

Chapter 6: SVM Decision Boundary

Drag the data points to see how the SVM margin and support vectors change. Notice how only points on or inside the margin affect the decision boundary.

SVM Maximum Margin Classifier

Blue circles = class +1, orange diamonds = class −1. The shaded band is the margin. Support vectors are highlighted. Click "New Data" for a fresh dataset.

C 10.0

Observe sparsity: Most data points have no effect on the decision boundary. Only the support vectors (highlighted with rings) matter. Move a non-support-vector point around — the boundary doesn't change. But move a support vector, and the whole boundary shifts.

Check: If you move a data point that is far from the decision boundary, what happens?

Nothing — only support vectors (points on or inside the margin) affect the boundary The boundary shifts proportionally All support vectors are recalculated

Chapter 7: RVM for Regression

The relevance vector machine (RVM) takes a completely different approach to sparsity. Instead of a geometric argument (maximum margin), the RVM uses Bayesian evidence maximization — the same automatic relevance determination (ARD) framework from Chapter 3.

The model is a linear combination of kernels, just like the SVM:

y(x) = ∑_n=1^N w_n k(x, x_n) + b

The key difference: each weight w_n gets its own precision hyperparameter α_n:

p(w|α) = ∏_n N(w_n|0, α_n⁻¹)

Automatic pruning: When we maximize the evidence (marginal likelihood) with respect to α, many α_n → ∞. This forces the corresponding w_n → 0 in the posterior, effectively pruning those basis functions. The surviving basis functions are the relevance vectors. Typically, the RVM produces much sparser solutions than the SVM.

The posterior over weights is Gaussian: p(w|t, α, β) = N(w|m, Σ) where:

Σ = (A + βΦ^TΦ)⁻¹, m = βΣΦ^Tt

with A = diag(α₁, ..., α_N).

Check: How does the RVM achieve sparsity?

By maximizing evidence: many precision hyperparameters go to infinity, forcing corresponding weights to zero By using L1 regularization By removing points far from the decision boundary

Chapter 8: RVM Sparsity Analysis

Why does evidence maximization produce sparsity? Consider the marginal likelihood as a function of a single hyperparameter α_i. It can be decomposed as:

ln p(t|α, β) = L(α_−i) + ½[ln α_i − ln(α_i + s_i) + q_i²/(α_i + s_i)]

where s_i and q_i are the "sparsity" and "quality" of basis function i, measuring how much adding this basis function improves the fit.

The sparsity criterion: The optimal α_i is finite (keep the basis function) only if q_i² > s_i, i.e., the quality exceeds the sparsity threshold. Otherwise, α_i → ∞ and the basis function is pruned. This provides a principled, automatic criterion for model complexity: each basis function is individually tested against the evidence.

Property	SVM	RVM
Sparsity mechanism	Hinge loss flat region	Evidence maximization / ARD
Typical sparsity	Moderate (10-50% SVs)	Very sparse (often <10%)
Outputs	Decisions only	Full posterior predictive (with uncertainty)
Kernel constraint	Must be positive definite	Any basis function
Hyperparameters	C (or ν), kernel params	None — all learned from data
Training cost	O(N²–N³) QP	O(N³) evidence maximization
Multiclass	Ad hoc (one-vs-rest)	Natural extension

Check: When is a basis function kept in the RVM?

When its quality exceeds its sparsity threshold (q_i^2 > s_i), meaning it contributes enough to the evidence When its weight is larger than a threshold When it is a support vector

Chapter 9: RVM for Classification

For classification, the RVM uses a logistic sigmoid output: p(t=1|x) = σ(y(x)). The non-conjugacy between the sigmoid likelihood and Gaussian prior means the posterior is non-Gaussian.

The solution uses the Laplace approximation (same idea as Ch 4 for Bayesian logistic regression):

p(w|t, α) ≈ N(w|w_MAP, Σ)

where w_MAP is found by iteratively reweighted least squares (IRLS), and Σ is the inverse Hessian at the mode. The hyperparameters α_n are then optimized using the approximate marginal likelihood, exactly as in regression.

RVM classification in practice: The RVM classifier typically uses far fewer basis functions than the SVM for comparable accuracy. This means faster prediction — critical in real-time applications. The RVM also provides genuine posterior probabilities, unlike the SVM where probabilities must be calibrated post-hoc via Platt scaling.

The iterative algorithm alternates between:

1. Fix α, find the posterior mode w_MAP and covariance Σ using IRLS.

2. Fix the posterior, update each α_i using the evidence framework. Prune basis functions where α_i → ∞.

Repeat until convergence.

Check: What approximation does the RVM classifier use for the posterior?

The Laplace approximation — a Gaussian fitted to the mode of the true posterior Variational inference with mean field MCMC sampling

Chapter 10: Summary

Chapter 7 presented two philosophies for building sparse kernel machines:

Aspect	SVM	RVM
Philosophy	Geometric (maximize margin)	Bayesian (maximize evidence)
Why sparse?	Hinge loss has flat zero-gradient region	ARD priors prune irrelevant basis functions
Sweet spot	Large N, need a quick reliable classifier	Need uncertainty, small-to-medium N

The big picture: SVMs dominated machine learning in the 2000s because they provided good generalization with theoretical guarantees. RVMs offered a Bayesian alternative with sparser solutions and uncertainty. Both have been largely superseded by deep learning for large-scale problems, but remain valuable for small datasets and interpretable models. The concepts — maximum margin, kernel trick, automatic relevance determination — continue to influence modern methods.

What comes next: Chapter 8 introduces graphical models — a powerful framework for representing and reasoning about probabilistic models with many variables. The graphical structure reveals conditional independencies that make inference tractable.

"The support vector machine is an example of a sparse
kernel machine, in which predictions for new inputs depend
on the kernel function evaluated at a subset of the training data."
— Christopher Bishop, PRML §7

Check: What is the fundamental advantage of the RVM over the SVM?

The RVM provides posterior probabilities, automatic hyperparameter tuning, and typically sparser solutions The RVM always has higher accuracy The RVM trains faster