Full search page →

PR 02 · Density Estimation and Bayesian Learning

Pattern RecognitionIntermediate22 minUpdated Nov 5, 2026

Needs: PR 01 · Patterns, Probability and Bayes Decisions, ML 01A · Linear Algebra for Learning

Navigate: this page and this track: Navigate: this page and this track
Explore this chapter 1 interactive experiment

Change the bandwidth and inspect individual kernels, the estimated density and leave-one-out prediction.

What you’ll learn

  • Why a Bayes classifier needs density estimates, and the difference between parametric and non-parametric estimation.
  • How to derive maximum-likelihood (ML) estimates for a Gaussian, why the covariance becomes singular with few samples, and how shrinkage fixes it.
  • How MAP and full Bayesian estimation use a prior over parameters, worked out for a Gaussian mean and a Bernoulli rate.
  • How histograms, Parzen windows (kernel density estimation) and kk-nearest-neighbor estimates follow from one formula, and how to choose the bandwidth or kk.
  • How the kk-NN classifier falls out of kk-NN density estimation, what the Cover–Hart bound says, and why all local methods suffer from the curse of dimensionality.

The big picture

PR 01 showed that the best possible classifier needs the class priors P(ck)P(c_k) and the class-conditional densities p(x∣ck)p(x\mid c_k). In practice nobody hands us these distributions; we have a finite set of labelled examples. This chapter is about turning examples into densities. Once we have p^(x∣ck)\hat p(x\mid c_k) and P^(ck)\hat P(c_k), we can plug them into the Bayes rule. This is the generative route to classification. The next chapter takes the discriminative route and fits the decision boundary directly.

There are two families of estimators [1, 2, 3]:

  • Parametric methods assume a functional form, such as a Gaussian, and estimate a fixed number of parameters. They need little data when the form is right and give systematically wrong answers when it is wrong.
  • Non-parametric methods let the data decide the shape. Their complexity grows with the number of samples. They are flexible but need much more data, especially in high dimensions.

Both families face the same central question: how much structure can the available data support? A flexible estimator can describe the training data beautifully and still predict new data poorly. Every method below has a “smoothness knob” (the number of parameters, the prior, the bin width, the bandwidth, kk), and choosing it well matters more than choosing the method.

Maximum-likelihood estimation

Plain version. Choose the parameter values under which the observed data would have been most probable.

Precise version. Let D={x1,…,xN}D=\{x_1,\ldots,x_N\} be samples drawn independently from a density p(x∣θ)p(x\mid\theta) with unknown parameter vector θ\theta. The likelihood of θ\theta is p(D∣θ)=∏np(xn∣θ)p(D\mid\theta)=\prod_n p(x_n\mid\theta), and the ML estimate maximizes its logarithm:

θ^ML=arg⁡max⁡θ ℓ(θ),ℓ(θ)=∑n=1Nlog⁡p(xn∣θ).\hat\theta_{\mathrm{ML}} =\arg\max_\theta\ \ell(\theta),\qquad \ell(\theta)=\sum_{n=1}^N\log p(x_n\mid\theta).

The independence assumption is about sampling (different observations do not influence each other), not about independence between the coordinates of one feature vector. For a classifier we fit one model per class, using only that class’s samples, and estimate the prior as the class frequency P^(ck)=Nk/N\hat P(c_k)=N_k/N.

The Gaussian case

For a dd-dimensional Gaussian N(μ,Σ)\mathcal N(\mu,\Sigma) the log-likelihood is

ℓ(μ,Σ)=−N2log⁡∣Σ∣−12∑n(xn−μ)⊤Σ−1(xn−μ)+const.\ell(\mu,\Sigma)=-\frac N2\log|\Sigma|-\frac12\sum_n (x_n-\mu)^\top\Sigma^{-1}(x_n-\mu)+\text{const}.

Setting the gradient with respect to μ\mu to zero gives Σ−1∑n(xn−μ)=0\Sigma^{-1}\sum_n(x_n-\mu)=0. Differentiating with respect to Σ−1\Sigma^{-1} (using ∂log⁡∣A∣/∂A=A−⊤\partial\log|A|/\partial A=A^{-\top} and ∂ a⊤Aa/∂A=aa⊤\partial\, a^\top Aa/\partial A=aa^\top) gives the estimates

μ^=1N∑nxn,Σ^=1N∑n(xn−μ^)(xn−μ^)⊤.\hat\mu=\frac1N\sum_n x_n,\qquad \hat\Sigma=\frac1N\sum_n(x_n-\hat\mu)(x_n-\hat\mu)^\top.

The sample mean is unbiased. The ML covariance is slightly biased: E[Σ^]=N−1NΣ\mathbb E[\hat\Sigma]=\tfrac{N-1}N\Sigma, because μ^\hat\mu was fitted to the same data and sits closer to them than the true mean does. The familiar sample covariance divides by N−1N-1 to remove this bias. For large NN the difference is negligible.

When ML breaks: too many parameters

A full covariance has d(d+1)/2d(d+1)/2 distinct entries. With d=64d=64 features that is 2,0802{,}080 numbers per class, plus 6464 for the mean. Worse, Σ^\hat\Sigma is a sum of NN rank-one matrices centered at μ^\hat\mu, so its rank is at most N−1N-1. When a class has no more samples than dimensions, its ML covariance is singular: it has zero variance in some directions, log⁡∣Σ^∣=−∞\log|\hat\Sigma|=-\infty, and the Gaussian discriminant of PR 01 is undefined. Even when NN is a bit larger than dd, the smallest eigenvalues are systematically underestimated, and the inverse Σ^−1\hat\Sigma^{-1} hugely amplifies noise along those directions.

Regularization shrinks the covariance towards a simpler target:

Σ~=(1−α)Σ^+ατI,τ=tr⁡(Σ^)/d,0≤α≤1.\tilde\Sigma=(1-\alpha)\hat\Sigma+\alpha\tau I,\qquad \tau=\operatorname{tr}(\hat\Sigma)/d,\qquad 0\le\alpha\le1 .

Here τI\tau I is a spherical matrix with the same average variance, and α\alpha is the shrinkage intensity. Shrinkage pulls large eigenvalues down and small ones up, trading a little bias for a much better-conditioned estimate. Ledoit and Wolf [14] derived a closed-form estimate of the α\alpha that minimizes the expected squared error, so it needs no cross-validation. Other common restrictions are a diagonal covariance (ignore correlations; this is Gaussian naive Bayes, below) and a shared covariance across classes (pool the evidence; this is LDA from PR 01). These are different modelling assumptions, not interchangeable numerical tricks.

Code: when the ML covariance fails

Code · Python · 21 lines
import numpy as np
from scipy.stats import multivariate_normal
from sklearn.covariance import EmpiricalCovariance, LedoitWolf

rng = np.random.default_rng(0)
d = 40
A = rng.normal(size=(d, d))
true_cov = A @ A.T / d + 0.5 * np.eye(d)          # a well-conditioned truth
test = rng.multivariate_normal(np.zeros(d), true_cov, 2000)

for n in [30, 60, 200, 1000]:
    train = rng.multivariate_normal(np.zeros(d), true_cov, n)
    mu = train.mean(0)
    S_ml = EmpiricalCovariance().fit(train).covariance_   # divisor n
    S_lw = LedoitWolf().fit(train)
    rank = np.linalg.matrix_rank(S_ml)
    ll_ml = (multivariate_normal(mu, S_ml, allow_singular=True).logpdf(test).mean()
             if rank == d else -np.inf)
    ll_lw = multivariate_normal(mu, S_lw.covariance_).logpdf(test).mean()
    print(f"n={n:4d}: rank(S_ML)={rank:2d}, test log-lik ML={ll_ml:8.2f}, "
          f"Ledoit-Wolf={ll_lw:8.2f} (shrinkage {S_lw.shrinkage_:.2f})")

With d=40d=40 and n=30n=30 the ML covariance has rank 2929 and assigns zero density to almost every test point (log-likelihood −∞-\infty). At n=60n=60 it is invertible but poor (test log-likelihood −94.6-94.6 versus −63.0-63.0 for Ledoit–Wolf). The automatically chosen shrinkage falls from 0.650.65 to 0.080.08 as nn grows, and at n=1000n=1000 the two estimates almost coincide. The rule of thumb: the fewer samples per parameter, the more you should shrink.

MAP and Bayesian estimation

Plain version. Maximum likelihood trusts the data completely. Bayesian estimation starts from a prior belief about the parameters and lets the data gradually overrule it. With little data the prior matters; with lots of data it hardly does.

Precise version. Treat θ\theta as a random variable with a parameter prior p(θ)p(\theta). Bayes’ rule gives the parameter posterior

p(θ∣D)=p(D∣θ) p(θ)∫p(D∣θ′) p(θ′) dθ′  ∝  p(D∣θ) p(θ).p(\theta\mid D)=\frac{p(D\mid\theta)\,p(\theta)}{\int p(D\mid\theta')\,p(\theta')\,d\theta'}\;\propto\;p(D\mid\theta)\,p(\theta).

A parameter prior is different from the class prior of PR 01. The class prior says how common a category is; a parameter prior says which model settings are plausible before seeing this training set. Three ways to use the posterior are common:

  • MAP estimation keeps only its mode: θ^MAP=arg⁡max⁡θ [log⁡p(D∣θ)+log⁡p(θ)]\hat\theta_{\mathrm{MAP}}=\arg\max_\theta\,[\log p(D\mid\theta)+\log p(\theta)]. The log prior acts as a regularizer; a Gaussian prior on weights is exactly an L2L_2 (ridge) penalty, which PR 03 uses.
  • Full Bayesian prediction averages over all parameter values instead of choosing one:
p(xnew∣D)=∫p(xnew∣θ) p(θ∣D) dθ.p(x_{\mathrm{new}}\mid D)=\int p(x_{\mathrm{new}}\mid\theta)\,p(\theta\mid D)\,d\theta .

This posterior predictive distribution carries parameter uncertainty into the prediction.

  • Plug-in prediction uses p(xnew∣θ^)p(x_{\mathrm{new}}\mid\hat\theta) with θ^\hat\theta from ML or MAP. It ignores parameter uncertainty and is therefore overconfident when data are scarce.

One subtle point: MAP is not invariant to re-parameterization. The mode of a density over σ\sigma is not the square root of the mode of the corresponding density over σ2\sigma^2, because densities pick up a Jacobian factor when the variable changes. ML estimates and full posteriors do not have this problem.

Worked example: the mean of a Gaussian

Let xn∼N(μ,σ2)x_n\sim\mathcal N(\mu,\sigma^2) with known σ2\sigma^2, and put a Gaussian prior on the unknown mean, μ∼N(m0,s02)\mu\sim\mathcal N(m_0,s_0^2). Multiplying the likelihood and the prior and completing the square in μ\mu shows that the posterior is again Gaussian, μ∣D∼N(mN,sN2)\mu\mid D\sim\mathcal N(m_N,s_N^2), with [1, 2]

1sN2=1s02+Nσ2,mN=sN2(m0s02+Nxˉσ2),\frac1{s_N^2}=\frac1{s_0^2}+\frac N{\sigma^2},\qquad m_N=s_N^2\left(\frac{m_0}{s_0^2}+\frac{N\bar x}{\sigma^2}\right),

where xˉ\bar x is the sample mean. Two readings make this formula memorable. Precisions add: the posterior precision 1/sN21/s_N^2 is the prior precision plus NN times the precision of one observation. The mean is a precision-weighted average of the prior mean and the sample mean. As N→∞N\to\infty, mN→xˉm_N\to\bar x (the ML estimate) and sN→0s_N\to0. Since the posterior is Gaussian, its mode equals its mean, so here μ^MAP=mN\hat\mu_{\mathrm{MAP}}=m_N. The posterior predictive is N(mN, σ2+sN2)\mathcal N(m_N,\ \sigma^2+s_N^2): wider than the plug-in N(mN,σ2)\mathcal N(m_N,\sigma^2) by the remaining uncertainty about μ\mu.

A prior whose posterior stays in the same family is called conjugate. Conjugate pairs (Gaussian–Gaussian, Beta–Bernoulli, Dirichlet–categorical, Normal–inverse-Wishart for a mean and covariance) give closed-form updates; other priors require the approximate inference methods of PR 08.

Posterior densities over a Gaussian mean for 0, 1, 5, 20 and 100 observations; the curves narrow and move towards the true mean 0.8.
Figure 1 — Bayesian estimation of a Gaussian mean (true value 0.8, prior N(0, 0.5²)). With one sample the ML estimate (2.84) is far off and the posterior mean is pulled back to 0.57; with 100 samples ML (0.74) and MAP (0.71) nearly agree and the posterior is narrow.

Worked example: a Bernoulli rate

For a Bernoulli rate qq (for instance the defect rate on a line) with prior Beta⁡(a,b)\operatorname{Beta}(a,b), observing ss successes in NN trials gives

q∣D∼Beta⁡(a+s, b+N−s),p(xnew=1∣D)=a+sa+b+N.q\mid D\sim\operatorname{Beta}(a+s,\ b+N-s), \qquad p(x_{\mathrm{new}}=1\mid D)=\frac{a+s}{a+b+N}.

The prior acts like aa imaginary successes and bb imaginary failures. With one success and no failures, ML predicts probability one, which is absurd. A uniform prior Beta⁡(1,1)\operatorname{Beta}(1,1) predicts 2/32/3; this is Laplace’s rule of succession. The same idea, called additive or Laplace smoothing, keeps a naive Bayes text classifier from assigning zero probability to a document because one word never appeared with a class in training.

Code: ML, MAP and the posterior predictive

Code · Python · 22 lines
import numpy as np

rng = np.random.default_rng(3)
sigma = 1.0                 # known noise standard deviation
m0, s0 = 0.0, 0.5           # prior on the mean: N(m0, s0^2)
x = rng.normal(0.8, sigma, 5)
n = len(x)

mu_ml = x.mean()
post_var = 1 / (1 / s0**2 + n / sigma**2)
post_mean = post_var * (m0 / s0**2 + x.sum() / sigma**2)   # = MAP for a Gaussian
pred_var = sigma**2 + post_var                              # predictive variance

# brute-force check on a grid: posterior is proportional to likelihood x prior
grid = np.linspace(-3, 3, 200001)
log_post = (-0.5 * ((x[:, None] - grid) ** 2).sum(0) / sigma**2
            - 0.5 * (grid - m0) ** 2 / s0**2)
w = np.exp(log_post - log_post.max())
w /= w.sum()
print(f"ML {mu_ml:.3f} | MAP/posterior mean {post_mean:.3f} "
      f"(grid {np.sum(w * grid):.3f}) | posterior sd {np.sqrt(post_var):.3f}")
print(f"predictive sd {np.sqrt(pred_var):.3f} vs plug-in sd {sigma:.3f}")

With five samples the ML mean is 0.5770.577, the posterior mean is 0.3200.320 (the grid integration agrees), and the posterior standard deviation is 0.3330.333. The predictive standard deviation, 1.0541.054, is 5%5\% wider than the plug-in value: small here, but it grows quickly as data get scarcer or dimension grows.

Classifiers built from densities

Plain version. Fit one density per class, multiply by the class frequency, and pick the class with the largest product. How you model each density decides what the classifier can learn.

Gaussian plug-in classifiers. Estimate μ^k\hat\mu_k, Σ^k\hat\Sigma_k and P^(ck)\hat P(c_k) and insert them into the Gaussian discriminant of PR 01. Separate covariances give QDA, a shared (pooled) covariance gives LDA, and the boundary geometry is exactly as derived there. For computation, use a Cholesky factorization or a linear solve rather than an explicit inverse.

Naive Bayes. Assume that the features are conditionally independent given the class:

p(x∣ck)=∏j=1dp(xj∣ck).p(x\mid c_k)=\prod_{j=1}^d p(x_j\mid c_k).

This needs only dd one-dimensional densities per class instead of one dd-dimensional density, so it can be estimated from very little data. It does not assume that features are independent in the overall population; it assumes that the class explains all of their dependence. Gaussian naive Bayes gives each coordinate a univariate Gaussian per class; its boundary is quadratic when the per-class variances differ. When features are strongly correlated (or duplicated), naive Bayes counts the same evidence several times, so its posteriors become overconfident even when its decisions remain reasonable.

Generative versus discriminative. Ng and Jordan [15] compared naive Bayes with logistic regression, its discriminative counterpart. They showed that logistic regression has a lower (or equal) error in the limit of infinite data, but naive Bayes approaches its own, higher, asymptotic error much faster: with a number of samples logarithmic in the dimension, rather than linear. So the generative model often wins with few samples and the discriminative one with many. This is a useful mental model for the trade-off between the two routes.

Non-parametric estimation: one formula, three estimators

Plain version. To estimate density at a point, look at a small region around it and count how many samples fall inside. Density is “count divided by (number of samples times region size)”. You can fix the region and count, or fix the count and grow the region.

Precise version. The probability that a sample falls in a small region R\mathcal R around xx is P=∫Rp(x′) dx′≈p(x) VP=\int_{\mathcal R}p(x')\,dx'\approx p(x)\,V, where VV is the volume of R\mathcal R. If kk of the NN samples fall inside, k≈NPk\approx NP, so [1, 2]

p^(x)=kN V.\hat p(x)=\frac{k}{N\,V}.

Two approximations are hidden here, and they pull in opposite directions. P≈p(x)VP\approx p(x)V needs a small region (otherwise p^\hat p is a blurred average of pp: bias). k≈NPk\approx NP needs many samples inside (otherwise the count is noisy: variance). Duda, Hart and Stork [1] show that the estimate converges to p(x)p(x) as N→∞N\to\infty if the region shrinks (VN→0V_N\to0) while the count grows (kN→∞k_N\to\infty) more slowly than NN (kN/N→0k_N/N\to0). There are two ways to satisfy this:

  • fix VV and count kk: histograms and Parzen windows (kernel density estimation);
  • fix kk and measure VV: kk-nearest-neighbor density estimation.

Histograms

Divide the axis into bins of width ww and set p^(x)=ni/(Nw)\hat p(x)=n_i/(Nw) for xx in bin ii with count nin_i. Histograms are simple and fast, but have three weaknesses visible in Figure 2. The estimate is discontinuous at bin edges. It depends on the origin of the grid as well as the width: shifting all bins by 0.30.3 changes the picture. And in dd dimensions the number of bins grows like (1/w)d(1/w)^d, so most bins are empty long before dd reaches ten. Scott’s analysis [8] shows that the bin width minimizing the mean integrated squared error shrinks only like N−1/3N^{-1/3}, so more data buy finer bins slowly.

Three histograms of the same 180 samples from a bimodal distribution: width 0.1 is spiky, width 0.6 with origin 0 and width 0.6 with origin 0.3 look different from each other.
Figure 2 — The same 180 samples (dashed: true density). Narrow bins are noisy; wide bins depend on where the grid starts. The two right panels differ only in the bin origin.

Parzen windows and kernel density estimation

The Parzen window or kernel density estimate (KDE), introduced by Rosenblatt [5] and analysed by Parzen [6], centers a window on every sample instead of fixing a grid:

p^h(x)=1N hd∑n=1NK ⁣(x−xnh).\hat p_h(x)=\frac1{N\,h^d}\sum_{n=1}^N K\!\left(\frac{x-x_n}{h}\right).

Here KK is the kernel, a function with K(u)≥0K(u)\ge0 and ∫K(u) du=1\int K(u)\,du=1 (so p^h\hat p_h is a valid density), and h>0h>0 is the bandwidth, which plays the role of the bin width. With a box kernel (K=1K=1 inside the unit cube) the formula is literally “count the samples within a cube of side hh around xx”, the fixed-VV estimator above. A Gaussian kernel K(u)=(2π)−d/2e−∥u∥2/2K(u)=(2\pi)^{-d/2}e^{-\|u\|^2/2} replaces the hard count with a smooth weight, giving a smooth estimate (Figure 3, left). In practice the shape of the kernel matters much less than the bandwidth.

Bias and variance. For a smooth density in one dimension, the bias of a KDE grows like h2h^2 (times the curvature p′′(x)p''(x)) and the variance like 1/(Nh)1/(Nh). Minimizing their sum gives an optimal bandwidth proportional to N−1/5N^{-1/5} and a mean integrated squared error that falls like N−4/5N^{-4/5}, slower than the N−1N^{-1} of a correctly specified parametric model [7, 8]. In dd dimensions the optimal bandwidth scales like N−1/(d+4)N^{-1/(d+4)} and the error like N−4/(d+4)N^{-4/(d+4)}. The slowdown with dd is one face of the curse of dimensionality.

Choosing the bandwidth. This is the important practical decision. Common options:

  • Rules of thumb. Silverman’s rule h=0.9min⁡(σ^, IQR/1.34) N−1/5h=0.9\min(\hat\sigma,\ \mathrm{IQR}/1.34)\,N^{-1/5} [7], where σ^\hat\sigma is the sample standard deviation and IQR the interquartile range, is optimal if the data are Gaussian. For multimodal data it oversmooths.
  • Cross-validation. Choose hh to maximize the log-likelihood of held-out samples (likelihood cross-validation), or to minimize an unbiased estimate of the integrated squared error (least-squares cross-validation, analysed by Scott and Terrell [9]).
  • Plug-in methods. Sheather and Jones [10] estimate the unknown curvature term in the optimal-bandwidth formula from the data and plug it in; their selector is a widely used reliable default in one dimension.

Whatever rule you use, choose hh without looking at the final test data. Figure 4 shows why the choice matters: on a bimodal sample, h=0.08h=0.08 produces spurious bumps, h=1.2h=1.2 merges the two modes into one, and the validation log-likelihood correctly prefers h=0.2h=0.2.

Left: box-window and Gaussian-window Parzen estimates with h = 0.3 on a bimodal sample. Right: k-NN density estimates with k = 5 (very spiky) and k = 30 (smoother, with heavy tails).
Figure 3 — Left: a box window gives a jagged estimate, a Gaussian window of the same width a smooth one. Right: k-NN density estimates adapt their width to the data but are spiky for small k and have tails that decay too slowly.
Four KDE bandwidths fitted to the same synthetic bimodal training sample, with true density and validation scores.
Figure 4 — KDE with four bandwidths on the training sample used in the code below. Narrow bandwidths show sampling fluctuations; wide bandwidths blur the modes. The mean validation log-density (in each title) is highest for h = 0.2.

Code: bandwidth selection and a Beta posterior

This example uses scikit-learn’s KernelDensity [26] on a synthetic bimodal distribution, separate validation samples, Silverman’s rule for comparison, and the closed-form Beta posterior from the previous section.

Code · Python · 28 lines
import numpy as np
from scipy.stats import beta
from sklearn.neighbors import KernelDensity

rng = np.random.default_rng(4)
def sample(n):
    means = np.where(rng.random(n) < 0.6, -1.5, 1.5)
    return (means + rng.normal(0, 0.4, n)).reshape(-1, 1)
train, validation = sample(180), sample(100)
bandwidths = [0.08, 0.2, 0.5, 1.2]
scores = []
for h in bandwidths:
    model = KernelDensity(bandwidth=h).fit(train)
    scores.append(model.score(validation) / len(validation))
best = bandwidths[int(np.argmax(scores))]

# Silverman's rule of thumb for comparison
x = train.ravel()
iqr = np.subtract(*np.percentile(x, [75, 25]))
h_silverman = 0.9 * min(x.std(ddof=1), iqr / 1.34) * len(x) ** (-1 / 5)

posterior = beta(2, 1)  # uniform prior + one success
print("validation mean log densities:",
      {h: round(float(s), 3) for h, s in zip(bandwidths, scores)})
print("selected bandwidth:", best, "| Silverman's rule:", round(h_silverman, 3))
print("posterior mean:", posterior.mean())
print("95% credible interval:", posterior.ppf([0.025, 0.975]))
assert np.isclose(posterior.mean(), 2 / 3)

Validation selects h=0.2h=0.2, while Silverman’s rule gives h≈0.475h\approx0.475. The rule assumes a single Gaussian; the spread of this sample comes mostly from the gap between the two modes, so the rule oversmooths. The Beta posterior after one success under a uniform prior has mean 2/32/3 and a 95%95\% credible interval of roughly [0.16,0.99][0.16, 0.99]: one observation tells us very little.

A credible interval describes uncertainty under the assumed prior and likelihood; it is not automatically a calibrated frequentist coverage guarantee. Likewise, a good density score does not by itself guarantee a good classification boundary: some of the modelled variation may be irrelevant to the labels.

kk-nearest-neighbor density estimation

Fix kk instead of VV: around xx, grow a ball until it contains exactly kk samples, and let Vk(x)V_k(x) be its volume. Then [11]

p^k(x)=kN Vk(x).\hat p_k(x)=\frac{k}{N\,V_k(x)} .

Loftsgaarden and Quesenberry [11] showed that this estimate is consistent when k→∞k\to\infty and k/N→0k/N\to0. Its bandwidth adapts automatically: narrow where data are dense, wide where they are sparse. But Figure 3 (right) shows its flaws. For small kk it is very spiky, because VkV_k is tiny near clusters of samples. In the tails, VkV_k grows only linearly with the distance in 1-D, so p^k\hat p_k decays like 1/∣x∣1/|x|, and the estimate does not integrate to one (its integral diverges). It is therefore a poor density estimate, yet, as the next section shows, an excellent basis for classification.

The kk-nearest-neighbor classifier

Plain version. To classify a new point, find the kk training points closest to it and take a majority vote. No model is trained; the training set is the model.

Precise version. Draw a ball around xx that contains kk samples in total, of which kck_c belong to class cc. Applying the k/(NV)k/(NV) estimate separately to each class, with NcN_c samples in class cc, gives

p^(x∣c)=kcNcV,P^(c)=NcN,p^(x)=kNV⟹P^(c∣x)=p^(x∣c)P^(c)p^(x)=kck.\hat p(x\mid c)=\frac{k_c}{N_c V},\qquad \hat P(c)=\frac{N_c}{N},\qquad \hat p(x)=\frac{k}{NV} \quad\Longrightarrow\quad \hat P(c\mid x)=\frac{\hat p(x\mid c)\hat P(c)}{\hat p(x)}=\frac{k_c}{k}.

The volume cancels, and the posterior estimate is simply the fraction of neighbors from each class. The Bayes rule then becomes the majority vote. With k=1k=1 it is the nearest-neighbor rule.

How good is it? Cover and Hart [12] proved that, as N→∞N\to\infty, the error P1NNP_{1\mathrm{NN}} of the 1-NN rule satisfies

P∗≤P1NN≤P∗(2−KK−1P∗)≤2P∗,P^*\le P_{1\mathrm{NN}}\le P^*\Bigl(2-\frac{K}{K-1}P^*\Bigr)\le 2P^*,

where P∗P^* is the Bayes error and KK the number of classes. This is an error-rate bound under the theorem’s sampling assumptions, not a statement that a neighbor contains half the information in the information-theoretic sense. As kk grows (with k/N→0k/N\to0), the kk-NN error approaches P∗P^* itself. This is an asymptotic statement; with finite data and many dimensions, things are much less rosy.

Choosing kk. Small kk gives low bias but high variance: the 1-NN boundary in Figure 5 wraps around individual noisy points. Large kk smooths the boundary but eventually ignores real structure. Choose kk by cross-validation. Two practical details: use an odd kk for two classes to avoid ties, and standardize the features first, because the Euclidean distance is dominated by whichever feature has the largest numeric range. In PR 04, kernels and nearest neighbors are compared with other nonlinear classifiers, and learned distance metrics are discussed there and in later chapters.

k-NN decision regions on noisy two-moons data for k = 1 (fragmented boundary with islands), k = 15 (smooth curve) and k = 101 (oversmoothed, nearly straight).
Figure 5 — k-NN on 400 noisy two-moons points. Shading shows the vote fraction k_c/k; the black curve is the 0.5 boundary. k = 1 overfits individual points, k = 101 starts to straighten the moons.

Code: k-NN versus Gaussian classifiers

Code · Python · 21 lines
import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import GridSearchCV, train_test_split
from sklearn.naive_bayes import GaussianNB
from sklearn.neighbors import KNeighborsClassifier
from sklearn.discriminant_analysis import QuadraticDiscriminantAnalysis

X, y = make_moons(1000, noise=0.3, random_state=0)
Xtr, Xte, ytr, yte = train_test_split(X, y, test_size=0.5, random_state=0)

search = GridSearchCV(KNeighborsClassifier(),
                      {"n_neighbors": [1, 3, 5, 9, 15, 31, 61, 101]}, cv=5)
search.fit(Xtr, ytr)                     # k chosen on training folds only
print("cross-validated k:", search.best_params_["n_neighbors"])
models = {"1-NN": KNeighborsClassifier(1),
          f"{search.best_params_['n_neighbors']}-NN": search.best_estimator_,
          "Gaussian naive Bayes": GaussianNB(),
          "QDA": QuadraticDiscriminantAnalysis()}
for name, m in models.items():
    m.fit(Xtr, ytr)
    print(f"{name:22s} test error {1 - m.score(Xte, yte):.3f}")

Cross-validation picks k=31k=31, with a test error of 10.6%10.6\%, against 12.4%12.4\% for 1-NN. The Gaussian models, whose single-ellipse class shapes cannot follow the moons, are worse (17.4%17.4\% for naive Bayes, 17.6%17.6\% for QDA). On this 2-D problem, the non-parametric method wins because the parametric form is wrong. The next section shows why the advantage shrinks as dimension grows.

The curse of dimensionality

Plain version. Local methods need neighbors that are close. When many coordinates contain diffuse or irrelevant variation, distance can become a poor guide: to collect even a small fraction of the data you must reach across most of the space, and the nearest and farthest points end up at almost the same distance.

Precise version. The phrase “curse of dimensionality” covers several related effects; Bishop [2, Section 1.4] gives geometric illustrations. Three are easy to check (Figure 6):

  1. Neighborhoods must be huge. For data uniform in the unit cube [0,1]d[0,1]^d, a sub-cube that contains a fraction rr of the data has edge length r1/dr^{1/d}. To capture 10%10\% of the data, the edge is 0.320.32 in 2-D, 0.790.79 in 10-D and 0.980.98 in 100-D. A “local” neighborhood spans almost the full range of every feature, so the estimate is no longer local.
  2. Volume is in the corners and the shell. The volume of the unit ball divided by the volume of its enclosing cube [−1,1]d[-1,1]^d tends to zero rapidly, and for a ball almost all volume lies in a thin shell near its surface. Samples from high-dimensional Gaussians sit at nearly the same distance from the mean, not near it.
  3. Distances concentrate. Beyer et al. [13] proved that, under broad conditions on the data distribution, the ratio of the farthest to the nearest neighbor distance tends to one as dd grows, so “nearest neighbor” stops being meaningful. In the simulation below, the ratio of nearest to farthest distance rises from 0.020.02 in 2-D to about 0.70.7 in 100-D.
Left: the mean ratio of nearest to farthest distance rises from near 0 in 1-D to 0.85 in 500-D. Right: the sub-cube edge needed to capture 1% or 10% of uniform data rises towards 1 with dimension, while the ball-to-cube volume ratio falls to zero by about d = 10.
Figure 6 — Left: distance concentration for 1,000 uniform points and 50 queries. Right: edge length of a sub-cube that captures 1% or 10% of uniform data, and the fraction of the cube [-1, 1]^d occupied by the unit ball.

Code: distance concentration

Code · Python · 11 lines
import numpy as np

rng = np.random.default_rng(0)
for d in [1, 2, 10, 100, 1000]:
    pts = rng.random((1000, d))          # 1000 uniform points in [0, 1]^d
    q = rng.random((50, d))              # 50 query points
    dist = np.sqrt(((q[:, None, :] - pts[None]) ** 2).sum(-1))
    ratio = (dist.min(1) / dist.max(1)).mean()
    edge = 0.1 ** (1 / d)                # sub-cube edge holding 10% of the volume
    print(f"d={d:5d}: nearest/farthest = {ratio:.3f}, "
          f"edge for 10% of data = {edge:.3f}")

The nearest/farthest ratio is 0.0170.017 in 2-D, 0.270.27 in 10-D, 0.700.70 in 100-D and 0.890.89 in 1000-D.

Why does anything work in high dimensions, then? Real data are not uniform. Images, sounds and text lie close to low-dimensional structures (manifolds, clusters) inside their huge ambient spaces, and their informative directions are far fewer than their raw coordinates. Practical defences are therefore: reduce or learn the representation first (PR 05: features and dimensionality), constrain the model (shared or diagonal covariances, naive Bayes), and regularize. Nearest-neighbor methods work very well today precisely because they are applied to learned embeddings rather than raw pixels, as the Modern view explains.

Modern view

Density estimation has split into two streams since the textbooks were written: classical statistics refined KDE and covariance estimation, while deep learning built density models that scale to images, and nearest-neighbor search became infrastructure.

Kernel density estimation, revisited. Chen’s tutorial [16] is a gentle modern introduction: convergence rates, bandwidth selection, confidence bands and how to handle their bias, and recent work on estimating geometric and topological features of a density (modes, level sets, ridges) with KDE. Wang and Scott [17] review non-parametric density estimators designed for high-dimensional data, including applications such as modal clustering, and list open research directions. Scott’s monograph [8] and Silverman’s classic [7] remain the references for the theory.

High-dimensional covariance. The singular-covariance problem of this chapter is a whole research area. Fan, Liao and Liu [18] review estimators of large covariance and precision (inverse covariance) matrices, focusing on rank-based methods and factor-model-based methods; Ledoit–Wolf shrinkage [14] is still the default regularizer in libraries.

Deep density models. Normalizing flows build a flexible density by passing a simple base distribution through a chain of invertible, differentiable maps; the change-of-variables formula then gives an exact log-likelihood. Papamakarios et al. [19] and Kobyzev, Prince and Brubaker [20] are the two standard reviews: the first emphasizes design principles, expressive power and computational trade-offs, the second the construction of flows and open questions. Autoregressive models, VAEs and diffusion models are other ways to learn high-dimensional densities; see ML 07: generative models and ML 08: diffusion and flow matching. Murphy’s two-volume text [4] covers both the classical estimators of this chapter and these modern models in one notation.

Nearest neighbors at scale. kk-NN is now everywhere, but on learned embeddings instead of raw features. Johnson, Douze and Jégou [21] showed how to run billion-scale similarity search on GPUs, and the Faiss library paper [22] describes the trade-off space of vector search (accuracy, speed, memory) and the indexing methods behind modern vector databases. Papernot and McDaniel’s deep kk-NN [23] compares a test input with its training neighbors in every layer’s representation, using label disagreement among neighbors as a confidence and robustness signal. For out-of-distribution detection, Sun et al. [24] use the plain kk-th nearest-neighbor distance in feature space, without any distributional assumption, and report large improvements over a parametric Mahalanobis-distance baseline. That parametric baseline, from Lee et al. [25], fits class-conditional Gaussians with shared covariance to network features, which is LDA from PR 01. The parametric versus non-parametric choice of this chapter is being replayed on top of deep features.

Open problems. Reliable density estimation in high dimension remains hard. Nalisnick et al. [27] showed that flow-based models, VAEs and PixelCNNs trained on one image dataset can assign higher likelihood to a different dataset (for example, a model trained on a dataset of everyday objects scores a dataset of house-number photos higher), so likelihood alone is not a safe novelty score. Bandwidth or kk selection for embeddings, and calibrated uncertainty for non-parametric estimates, are active questions.

Key takeaways

  • Generative classifiers need p^(x∣ck)\hat p(x\mid c_k) and P^(ck)\hat P(c_k); the estimator’s assumptions decide the boundary’s shape.
  • ML estimates for a Gaussian are the sample mean and the divisor-NN covariance; with N≤dN\le d samples the covariance is singular, and shrinkage (e.g. Ledoit–Wolf) or shared/diagonal structure is needed.
  • MAP keeps the posterior mode; full Bayesian prediction integrates over parameters and is wider than plug-in prediction when data are scarce. Conjugate priors give closed forms: precisions add for a Gaussian mean, counts add for a Beta–Bernoulli rate.
  • Non-parametric estimates all follow from p^=k/(NV)\hat p=k/(NV): histograms and Parzen/KDE fix VV, kk-NN fixes kk. The bandwidth or kk matters more than the kernel; choose it by cross-validation or a justified rule, never on test data.
  • The kk-NN classifier estimates P(c∣x)≈kc/kP(c\mid x)\approx k_c/k; asymptotically 1-NN is within a factor two of the Bayes error.
  • In high dimensions neighborhoods stop being local and distances concentrate; whether local methods work depends on intrinsic structure, feature scaling and sample size, not ambient dimension alone.

Exercises

  1. Counting parameters. Count the mean and covariance parameters of one 64-dimensional Gaussian. Explain why fitting it to 30 samples fails, and give two ways to fix it.
Hint

6464 means plus 64⋅65/2=2,08064\cdot65/2=2{,}080 covariance entries. With 30 samples, Σ^\hat\Sigma has rank at most 29, so it is singular. Fixes: shrinkage towards τI\tau I (Ledoit–Wolf), a diagonal covariance (naive Bayes), a covariance shared across classes, or dimensionality reduction first.

  1. Beta–Bernoulli update. Start with Beta⁡(2,3)\operatorname{Beta}(2,3), observe three successes and two failures, and compute the posterior, the MAP estimate and the posterior predictive probability of success.
Hint

Posterior Beta⁡(5,5)\operatorname{Beta}(5,5). MAP (mode) =(5−1)/(5+5−2)=0.5=(5-1)/(5+5-2)=0.5. Predictive =5/10=0.5=5/10=0.5. Compare with ML, 3/5=0.63/5=0.6.

  1. Precision-weighted means. For the Gaussian mean with prior N(0,1)\mathcal N(0,1) and noise variance σ2=4\sigma^2=4, after how many samples does the data weight equal the prior weight? What is the posterior standard deviation then?
Hint

Prior precision 11; each sample adds 1/41/4. Equal weight at N=4N=4. Posterior precision 22, so sN=1/2≈0.71s_N=1/\sqrt2\approx0.71.

  1. Duplicated features. Duplicate one feature in Gaussian naive Bayes. Predict what happens to accuracy and to the confidence of the posteriors, then check with scikit-learn on load_breast_cancer.
Hint

The extra coordinate adds no new information, but the factorized likelihood counts it twice, squaring its likelihood ratio. Decisions may change a little; posteriors move closer to 0 or 1 (more overconfident). Compare predict_proba histograms and the log-loss before and after.

  1. k-NN density is not a density. Show that in 1-D the kk-NN estimate p^k(x)\hat p_k(x) decays like 1/∣x∣1/|x| far from the data, and conclude that ∫p^k(x) dx\int\hat p_k(x)\,dx diverges. Why does this not hurt the kk-NN classifier?
Hint

Far from all samples, the distance to the kk-th neighbor is about ∣x∣|x|, so Vk≈2∣x∣V_k\approx2|x| and p^k≈k/(2N∣x∣)\hat p_k\approx k/(2N|x|), whose integral is logarithmically divergent. The classifier only uses ratios kc/kk_c/k at the same point, where the common volume cancels.

  1. Bandwidth rules. Generate 500 samples from a mixture of N(−2,0.52)\mathcal N(-2,0.5^2) and N(2,0.52)\mathcal N(2,0.5^2). Compare Silverman’s rule, likelihood cross-validation (GridSearchCV over KernelDensity) and, if you have statsmodels, a plug-in selector. Which oversmooths, and why?
Hint

Silverman’s rule uses the overall spread (about 2.12.1 here), which is dominated by the gap between the modes, so it gives a bandwidth several times too large for each mode. Cross-validated likelihood picks something close to the within-mode optimum.

References

  1. R. O. Duda, P. E. Hart and D. G. Stork, Pattern Classification, 2nd ed., Wiley, 2001 (Ch. 3, maximum-likelihood and Bayesian estimation; Ch. 4, non-parametric techniques). publisher page
  2. C. M. Bishop, Pattern Recognition and Machine Learning, Springer, 2006 (Sections 1.4, 2.1–2.3, 2.5 and 4.2). official page and free PDF
  3. S. Theodoridis and K. Koutroumbas, Pattern Recognition, 4th ed., Academic Press, 2008 (Ch. 2, density estimation and Bayesian classification). publisher page
  4. K. P. Murphy, Probabilistic Machine Learning: An Introduction, MIT Press, 2022. official page
  5. M. Rosenblatt, “Remarks on some nonparametric estimates of a density function,” The Annals of Mathematical Statistics, vol. 27, no. 3, pp. 832–837, 1956. doi
  6. E. Parzen, “On estimation of a probability density function and mode,” The Annals of Mathematical Statistics, vol. 33, no. 3, pp. 1065–1076, 1962. doi
  7. B. W. Silverman, Density Estimation for Statistics and Data Analysis, Chapman and Hall, 1986 (reissued by Routledge, 2018). doi
  8. D. W. Scott, Multivariate Density Estimation: Theory, Practice, and Visualization, 2nd ed., Wiley, 2015. doi
  9. D. W. Scott and G. R. Terrell, “Biased and unbiased cross-validation in density estimation,” Journal of the American Statistical Association, vol. 82, no. 400, pp. 1131–1146, 1987. doi
  10. S. J. Sheather and M. C. Jones, “A reliable data-based bandwidth selection method for kernel density estimation,” Journal of the Royal Statistical Society, Series B, vol. 53, no. 3, pp. 683–690, 1991. doi
  11. D. O. Loftsgaarden and C. P. Quesenberry, “A nonparametric estimate of a multivariate density function,” The Annals of Mathematical Statistics, vol. 36, no. 3, pp. 1049–1051, 1965. doi
  12. T. M. Cover and P. E. Hart, “Nearest neighbor pattern classification,” IEEE Transactions on Information Theory, vol. 13, no. 1, pp. 21–27, 1967. doi
  13. K. Beyer, J. Goldstein, R. Ramakrishnan and U. Shaft, “When is ‘nearest neighbor’ meaningful?,” in Database Theory — ICDT’99, Lecture Notes in Computer Science, Springer, 1999. doi
  14. O. Ledoit and M. Wolf, “A well-conditioned estimator for large-dimensional covariance matrices,” Journal of Multivariate Analysis, vol. 88, no. 2, pp. 365–411, 2004. doi
  15. A. Y. Ng and M. I. Jordan, “On discriminative vs. generative classifiers: a comparison of logistic regression and naive Bayes,” in Advances in Neural Information Processing Systems (NIPS), 2001. paper
  16. Y.-C. Chen, “A tutorial on kernel density estimation and recent advances,” Biostatistics & Epidemiology, vol. 1, no. 1, pp. 161–187, 2017. doi
  17. Z. Wang and D. W. Scott, “Nonparametric density estimation for high-dimensional data — algorithms and applications,” WIREs Computational Statistics, vol. 11, no. 4, 2019. doi
  18. J. Fan, Y. Liao and H. Liu, “An overview of the estimation of large covariance and precision matrices,” The Econometrics Journal, vol. 19, no. 1, pp. C1–C32, 2016. doi
  19. G. Papamakarios, E. Nalisnick, D. J. Rezende, S. Mohamed and B. Lakshminarayanan, “Normalizing flows for probabilistic modeling and inference,” Journal of Machine Learning Research, vol. 22, no. 57, pp. 1–64, 2021. arXiv
  20. I. Kobyzev, S. J. D. Prince and M. A. Brubaker, “Normalizing flows: an introduction and review of current methods,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 43, no. 11, pp. 3964–3979, 2021. doi
  21. J. Johnson, M. Douze and H. Jégou, “Billion-scale similarity search with GPUs,” IEEE Transactions on Big Data, vol. 7, no. 3, pp. 535–547, 2021. doi
  22. M. Douze, A. Guzhva, C. Deng, J. Johnson, G. Szilvasy, P.-E. Mazaré, M. Lomeli, L. Hosseini and H. Jégou, “The Faiss library,” arXiv:2401.08281, 2024. arXiv
  23. N. Papernot and P. McDaniel, “Deep k-nearest neighbors: towards confident, interpretable and robust deep learning,” arXiv:1803.04765, 2018. arXiv
  24. Y. Sun, Y. Ming, X. Zhu and Y. Li, “Out-of-distribution detection with deep nearest neighbors,” in Proc. International Conference on Machine Learning (ICML), PMLR 162, 2022. paper
  25. K. Lee, K. Lee, H. Lee and J. Shin, “A simple unified framework for detecting out-of-distribution samples and adversarial attacks,” in Advances in Neural Information Processing Systems (NeurIPS), 2018. paper
  26. scikit-learn developers, “Density estimation,” scikit-learn user guide. documentation
  27. E. Nalisnick, A. Matsukawa, Y. W. Teh, D. Gorur and B. Lakshminarayanan, “Do deep generative models know what they don’t know?,” in Proc. International Conference on Learning Representations (ICLR), 2019. arXiv

Check your understanding

This tutorial has 6 exercises. Can you solve them without opening the hints?

Go to the exercises ↑

Next PR 03 · Linear Models for Regression and Classification · 23 min