Murphy, Chapters 16–17

Nonparametric Methods: KNN, Kernels & GPs

No fixed parameter count. The model grows with the data. From nearest neighbors to Gaussian processes, these methods let the data speak with minimal assumptions.

Prerequisites: Probability (Ch 2–3) + Linear Models (Ch 10–11). Bayesian linear regression helps for GPs.

Chapters

Simulations

Quizzes

Chapter 0: Why Nonparametric?

Every model we have seen so far — logistic regression, linear regression, neural networks — has a fixed number of parameters. You choose an architecture, train it, and the parameter count is determined before seeing any data. These are parametric models.

But what if you don't know how complex the true function is? What if a linear model is too simple and a neural network is overkill? Nonparametric models let the data determine the complexity. The number of effective parameters grows with the dataset size.

The big picture: "Nonparametric" does not mean "no parameters." It means "not a fixed number of parameters." KNN stores all training data and classifies by majority vote of the K nearest neighbors. Gaussian processes define a prior over functions and condition on observed data. The model complexity adapts automatically.

Exemplar Methods (Ch 16)

KNN, kernel density estimation, metric learning

↓

Mercer Kernels (Ch 17)

Similarity functions, the kernel trick, kernel ridge regression

↓

Gaussian Processes (Ch 17)

Prior over functions, posterior predictive with uncertainty

↓

SVMs (Ch 17)

Maximum margin classifiers, the dual problem, kernel trick

What does "nonparametric" mean in the context of machine learning models?

The model has zero parameters The number of effective parameters grows with the size of the training data, rather than being fixed in advance The model doesn't need to be trained

Chapter 1: K-Nearest Neighbors

The simplest nonparametric model: store all training data. To classify a new point x, find the K closest training points and take a majority vote.

p(y = c | x, D, K) = (1/K) ∑_{n ∈ N_K(x)} I(y_n = c)

where N_K(x) is the set of K nearest neighbors of x in the training set D, and I(·) is the indicator function. For regression, we replace the vote with an average: f(x) = (1/K) ∑ y_n.

K controls the bias-variance tradeoff: K=1 gives a complex, jagged decision boundary that exactly classifies every training point (zero training error, high variance). Large K gives smoother boundaries (higher bias, lower variance). The optimal K is found by cross-validation. As N → ∞, KNN with K → ∞ and K/N → 0 converges to the Bayes-optimal classifier.

The choice of distance metric matters enormously. Euclidean distance treats all features equally, which is problematic when features have different scales. Options include:

Distance	Formula	When to use
Euclidean	√(∑(x_d − x'_d)²)	Continuous features, same scale
Manhattan	∑\|x_d − x'_d\|	High-dimensional or sparse data
Mahalanobis	√((x−x')^TΣ⁻¹(x−x'))	Correlated features
Cosine	1 − x·x' / (\|\|x\|\| \|\|x'\|\|)	Text, high-dimensional embeddings

Deep metric learning (16.2): Instead of using hand-crafted distances, learn a neural network that maps inputs to an embedding space where Euclidean distance is meaningful. Train with contrastive or triplet loss: similar items should be close, dissimilar items far apart. This combines the power of DNNs with the simplicity of KNN.

What happens to the KNN decision boundary as K increases from 1 to N (the total number of training points)?

It becomes smoother, eventually predicting the majority class everywhere (maximum bias, minimum variance) It becomes more complex and jagged It stays the same

Chapter 2: The Curse of Dimensionality

KNN works beautifully in low dimensions. In high dimensions, it breaks. This is the curse of dimensionality (Murphy 16.1.2).

Consider a unit hypercube [0, 1]^D. To capture a fraction f of the volume, you need a sub-cube with side length f^1/D. For D = 10 and f = 0.01 (1% of data), the side length is 0.01^0.1 ≈ 0.63. Your "local" neighborhood spans 63% of each axis — not local at all!

The geometric argument: In high dimensions, almost all the volume of a sphere concentrates in a thin shell near the surface. Most of the hypercube's volume is in the corners. Distances between random points concentrate around a single value: all points are roughly equidistant. The concept of "nearest" becomes meaningless.

Consequences for KNN:

Dimension	Effect
Low (D ≤ 10)	KNN works well, neighbors are truly "near"
Medium (10–100)	Need exponentially more data; metric learning helps
High (D > 100)	Raw KNN fails; need dimensionality reduction or learned embeddings first

Practical solutions: (1) Reduce dimensionality with PCA or autoencoders (Ch 20) before applying KNN. (2) Learn a distance metric via deep metric learning. (3) Use approximate nearest neighbor search (locality-sensitive hashing, k-d trees) for efficiency. (4) Accept that parametric models with strong inductive biases (like CNNs) often outperform KNN in high dimensions.

Why does the curse of dimensionality make KNN ineffective in high-dimensional spaces?

Because in high dimensions, distances between all points concentrate around a single value, so "nearest" neighbors are barely closer than "farthest" ones Because there are too many possible classes Because the algorithm runs too slowly

Chapter 3: Kernel Density Estimation

KNN classifies but doesn't estimate the underlying density p(x). Kernel density estimation (KDE) does. Place a small "bump" (kernel) at each data point and sum them up (Murphy 16.3).

p̂(x) = (1/Nh^D) ∑_n=1^N K((x − x_n) / h)

where K is a density kernel (a symmetric, non-negative function that integrates to 1) and h is the bandwidth (how wide each bump is). The most common choice is the Gaussian kernel:

K(u) = (2π)^−D/2 exp(−||u||² / 2)

Bandwidth is the key hyperparameter: Small h gives a spiky estimate (each data point is a sharp peak). Large h gives a smooth, spread-out estimate. Too small = overfitting (the density looks like a sum of delta functions). Too large = underfitting (all structure is smoothed away). This is the bias-variance tradeoff again.

From KDE to KNN (16.3.4): KDE fixes the bandwidth h and counts how many points fall within it. KNN fixes the count K and adapts the "bandwidth" (the distance to the K-th neighbor). Both estimate density; they are duals of each other. In regions with dense data, KNN uses a small neighborhood. In sparse regions, it reaches farther. This makes KNN adaptive.

Kernel regression (Nadaraya-Watson estimator) combines KDE with regression: weight each training point's y-value by how close its x-value is to the query:

f̂(x) = ∑_n K((x − x_n)/h) y_n / ∑_n K((x − x_n)/h)

What role does the bandwidth h play in kernel density estimation?

It controls the smoothness of the density estimate: small h overfits (spiky), large h underfits (over-smooth) It sets the number of neighbors to consider It determines the number of kernels

Chapter 4: Mercer Kernels

A Mercer kernel (or positive definite kernel) is a function k(x, x') that measures similarity between two inputs. Murphy (17.1) explains why these are so powerful.

k(x, x') = φ(x)^Tφ(x')

The key insight: every Mercer kernel corresponds to a dot product in some (possibly infinite-dimensional) feature space. The kernel computes this dot product without ever constructing the feature vector. This is the foundation of the kernel trick.

Mercer's theorem: A symmetric function k(x, x') is a valid (Mercer) kernel if and only if the kernel matrix K_ij = k(x_i, x_j) is positive semi-definite for any set of inputs. Equivalently, k can be written as φ(x)^Tφ(x') for some feature map φ.

Kernel	k(x, x')	Feature Space
Linear	x^Tx'	D-dimensional (original space)
Polynomial	(x^Tx' + c)^d	O(D^d)-dimensional
RBF / Gaussian	exp(−\|\|x − x'\|\|² / 2σ²)	Infinite-dimensional
Laplacian	exp(−\|\|x − x'\|\|₁ / σ)	Infinite-dimensional

The RBF kernel is special: Its feature space is infinite-dimensional. It can represent any continuous function. The bandwidth σ controls smoothness: small σ gives a wiggly function (each training point is its own sharp peak); large σ gives a smooth, slowly varying function. This is the analog of the KDE bandwidth, but now applied to regression and classification.

Kernels can be combined: if k₁ and k₂ are valid kernels, then so are k₁ + k₂, c · k₁, k₁ · k₂, and many other combinations. This lets you encode prior knowledge about the function's structure.

What does the kernel trick allow you to do?

Compute dot products in a high-dimensional (even infinite) feature space without ever explicitly constructing the feature vectors Reduce the number of training examples needed Make any model linear

Chapter 5: Gaussian Processes

A Gaussian process (GP) is a distribution over functions (Murphy 17.2). Instead of learning a fixed set of weights, we place a prior directly over the function f(x) and update it with data.

f(x) ∼ GP(m(x), k(x, x'))

This means: for any finite set of inputs {x₁, …, x_N}, the function values [f(x₁), …, f(x_N)] follow a multivariate Gaussian with mean [m(x₁), …, m(x_N)] and covariance matrix K_ij = k(x_i, x_j).

The prior encodes smoothness: The kernel k determines what kinds of functions the GP considers plausible before seeing data. An RBF kernel says "nearby inputs should have similar outputs." A periodic kernel says "the function repeats." A Matérn kernel controls the exact degree of smoothness. The mean function m(x) is typically set to zero.

Think of it this way: sample a random function from the GP prior. It is a smooth, wiggly curve (if using an RBF kernel). Now condition on some observed data points. The posterior is also a GP, but now constrained to pass through (or near) the data. Between data points, the function is uncertain — the posterior variance is large. Near data points, it is confident.

Connection to Bayesian linear regression: A GP with a linear kernel k(x, x') = x^Tx' is exactly equivalent to Bayesian linear regression with a Gaussian prior on weights. GPs generalize this to arbitrary kernels, giving infinite-dimensional Bayesian regression.

What does a Gaussian process place a distribution over?

The training data Functions: for any finite set of inputs, the function values are jointly Gaussian The kernel hyperparameters

Chapter 6: GP Prediction

Given N noisy observations D = {(x_n, y_n)}, where y_n = f(x_n) + ε, ε ∼ N(0, σ_y²), the GP posterior predictive at a new input x_* is (Murphy 17.2.2):

p(f_* | x_*, D) = N(f_* | μ_*, σ_*²)

μ_* = k_*^T(K + σ_y² I)⁻¹ y

σ_*² = k(x_*, x_*) − k_*^T(K + σ_y² I)⁻¹ k_*

where k_* = [k(x_*, x₁), …, k(x_*, x_N)]^T is the kernel vector between the test point and all training points, and K is the N×N kernel matrix of training points.

Interpreting the formulas: The mean μ_* is a weighted sum of training outputs y, where the weights come from (K + σ_y²I)⁻¹k_*. Nearby training points (high k values) contribute more. The variance σ_*² starts at the prior variance k(x_*, x_*) and decreases by the amount of information the training data provides. Far from data, variance stays high. Near data, it shrinks.

Computational cost: The main bottleneck is inverting the N×N matrix (K + σ_y²I), which costs O(N³). For N > 10,000, this is impractical. Solutions include sparse GPs (inducing points), random Fourier features, and scalable variational methods (Murphy 17.2.9).

Estimating the kernel (17.2.6): The kernel has hyperparameters (e.g., lengthscale ℓ and signal variance σ_f² for the RBF kernel). We optimize them by maximizing the log marginal likelihood:

log p(y | X) = −½ y^T(K + σ_y²I)⁻¹y − ½ log |K + σ_y²I| − N/2 log(2π)

This automatically balances data fit (first term) and model complexity (second term) — Bayesian Occam's razor.

What happens to the GP posterior variance at a test point that is far from all training data?

It remains close to the prior variance k(x_*, x_*), reflecting high uncertainty since there is no nearby data to reduce it It goes to zero It grows to infinity

Chapter 7: Support Vector Machines

SVMs (Murphy 17.3) approach classification differently from logistic regression. Instead of maximizing likelihood, they find the hyperplane that maximizes the margin — the distance to the nearest training points.

max_{w, b} 2 / ||w|| s.t. y_n(w^Tx_n + b) ≥ 1 ∀ n

The constraint says every point must be on the correct side with at least margin 1/||w||. The objective maximizes this margin. Only the training points on the margin boundary matter — these are the support vectors.

Why maximum margin? A wider margin means the classifier is more robust to small perturbations. Among all hyperplanes that separate the data, the maximum-margin one generalizes best. The VC dimension of the classifier depends on the margin, not just the number of features.

Soft margin (17.3.3): Real data is rarely perfectly separable. We allow some points to violate the margin by introducing slack variables ξ_n ≥ 0:

min_w ½||w||² + C ∑_n ξ_n s.t. y_n(w^Tx_n + b) ≥ 1 − ξ_n

The parameter C controls the tradeoff: large C penalizes violations heavily (hard margin); small C allows more violations (softer boundary). C is analogous to 1/λ in ridge regression.

SVM vs logistic regression (17.3.6): The SVM loss (hinge loss) is max(0, 1 − y · f(x)). Logistic regression uses log(1 + exp(−y · f(x))). Both are convex upper bounds on the 0-1 loss. Hinge loss is exactly zero for correctly classified points with margin ≥ 1, making SVMs sparse in dual form. Logistic regression always assigns a small gradient to every point.

What are support vectors?

The training points that lie exactly on the margin boundary; only they determine the decision hyperplane All training points The weight vectors of the model

Chapter 8: The Kernel Trick

The SVM optimization can be written in dual form (Murphy 17.3.2), where the solution depends on the data only through dot products x_i^Tx_j:

max_α ∑_n α_n − ½ ∑_i,j α_i α_j y_i y_j x_i^Tx_j s.t. 0 ≤ α_n ≤ C

Now the kernel trick: replace every dot product x_i^Tx_j with a kernel k(x_i, x_j). This implicitly maps the data to a high-dimensional feature space where it may be linearly separable, without ever computing the feature vectors.

A nonlinear SVM in the original space is a linear SVM in the kernel feature space. Using an RBF kernel, the SVM can learn arbitrarily complex decision boundaries. The complexity is controlled by C (regularization) and σ (kernel bandwidth), not by choosing a feature map by hand.

The prediction for a new input x is:

f(x) = ∑_{n ∈ SV} α_n y_n k(x_n, x) + b

The sum is only over support vectors (points with α_n > 0), making prediction sparse and efficient.

Kernel ridge regression (17.3.9): The kernel trick applies beyond SVMs. Kernel ridge regression replaces w^Tx with kernel evaluations: f(x) = k_*^T(K + λI)⁻¹y. This is identical to the GP posterior mean! The kernel trick provides a unified framework for nonlinear regression and classification.

Method	Loss	Sparsity	Probabilistic?
SVM	Hinge loss	Yes (support vectors only)	No (margins, not probabilities)
Kernel ridge regression	Squared loss	No (all points contribute)	Yes (equivalent to GP mean)
Gaussian process	Log marginal likelihood	No	Yes (full posterior)
Relevance vector machine	Type-II ML	Yes	Yes

Why is the kernel SVM prediction efficient despite operating in a potentially infinite-dimensional feature space?

Because the prediction only depends on kernel evaluations k(x_n, x) for the support vectors, not on explicit feature vectors Because the kernel function is always fast to compute Because SVMs do not need the kernel matrix

Chapter 9: KNN Explorer

See how K-nearest neighbors classifies 2D data. Place points, choose K, and watch the decision regions change.

K-Nearest Neighbors: Decision Regions

Click to place points (toggle class below). The background shows how KNN would classify each location. Increase K for smoother boundaries.

0 points

What to observe: With K=1, every training point creates its own region (Voronoi diagram). Increase K and the boundaries smooth out. Try overlapping the classes to see how K affects the noise tolerance.

Why does K=1 in KNN give a Voronoi tessellation as the decision boundary?

Because each query point is classified by its single nearest neighbor, so each training point "owns" the region of space closer to it than to any other point Because the algorithm uses Voronoi diagrams internally Because K=1 minimizes the training error

Chapter 10: GP Regression

Click to add training points and watch the Gaussian process posterior update in real time. The mean prediction is a smooth curve that passes through (or near) the data, with uncertainty bands that grow between observations.

Gaussian Process Regression

Click to add data points. The teal line is the posterior mean. The shaded band is ±2 standard deviations. The dashed lines are prior samples.

Lengthscale ℓ0.30

Noise σ_y0.10

Try this: Place a few points and observe how the uncertainty band narrows near data and widens between observations. Then change the lengthscale: small ℓ gives wiggly fits, large ℓ gives smooth fits. Increase noise σ_y to see the mean curve "relax" away from the data points.

What happens to the GP uncertainty band as you add more training points?

It shrinks near the data points but remains wide in regions with no observations It disappears entirely It stays the same everywhere

Chapter 11: Connections

Nonparametric methods are the bridge between simple linear models and the full Bayesian toolkit.

Concept from this chapter	Where it leads
KNN	Baseline for any classification problem; retrieval-augmented generation (RAG)
Kernel density estimation	Density estimation in GMMs (Ch 21), normalizing flows
Mercer kernels	Kernel PCA (Ch 20), spectral clustering (Ch 21), GP kernels
Gaussian processes	Bayesian optimization, neural tangent kernels, infinite-width DNNs
SVMs	Maximum margin principle, hinge loss in structured prediction
Kernel trick	Kernel PCA, kernel k-means, any algorithm that uses only dot products
Deep metric learning	Face verification, image retrieval, few-shot learning

What we covered: KNN classification and regression, the curse of dimensionality, kernel density estimation, Mercer kernels and the kernel trick, Gaussian processes with posterior predictive, support vector machines with maximum margin and soft margin, and kernel ridge regression.

What comes next: Chapters 20–21 go beyond supervised learning. PCA and autoencoders learn low-dimensional representations. VAEs combine neural networks with probabilistic generative models. K-means and GMMs cluster data without labels. The EM algorithm ties it all together.

"The purpose of computing is insight, not numbers." — Richard Hamming

How is kernel ridge regression related to Gaussian process prediction?

The kernel ridge regression solution is identical to the GP posterior mean, with the regularization parameter λ corresponding to the noise variance σ_y² They are completely unrelated Kernel ridge regression uses SVMs internally