Simple Algorithm
Artificial Intelligence · Hidden Layer · 22 min

Unsupervised Learning

Clustering, dimensionality reduction and density estimation.

Most data come without labels: shopping baskets, gene-expression profiles, billions of photos. Unsupervised learning asks what structure is there anyway. This lesson develops the classic answers with their algorithms and guarantees: clustering (k-means, hierarchies, DBSCAN, Gaussian mixtures fitted by EM), dimensionality reduction (PCA), and density estimation, along with the curse of dimensionality that haunts all three.

What you’ll learn

  • State the k-means objective, prove that Lloyd's algorithm never increases it and terminates, and explain k-means++ seeding and why the problem is NP-hard.
  • Compare hierarchical clustering, DBSCAN and Gaussian mixtures, and derive the EM updates for a Gaussian mixture with their monotonicity.
  • Derive PCA as variance maximization, connect it to the eigenvectors of the covariance and the SVD of the data, and use explained variance to choose a dimension.
  • Build a kernel density estimate, explain the bandwidth's bias–variance trade-off and its n−4/(d+4)n^{-4/(d+4)} rate, and quantify the curse of dimensionality.

k-means and Lloyd's algorithm

In unsupervised learning there is no label to predict, so every method must say what structure it is looking for. Clustering looks for groups. Given points x1,…,xn∈Rd\mathbf x_1,\dots,\mathbf x_n\in\R^d and a number kk, k-means chooses centroids μ1,…,μk\boldsymbol\mu_1,\dots,\boldsymbol\mu_k and an assignment c(i)∈{1,…,k}c(i)\in\{1,\dots,k\} that minimize the within-cluster sum of squares, or inertia:

J(c,μ)=∑i=1n∥xi−μc(i)∥2.J(c,\boldsymbol\mu)=\sum_{i=1}^n\norm{\mathbf x_i-\boldsymbol\mu_{c(i)}}^2.

Lloyd's algorithm (1957, published 1982) minimizes it by alternating over the two blocks of variables:

text
LLOYD(points x_1..x_n, initial centroids μ_1..μ_k)
  repeat
      for i = 1..n:                                # assignment step, O(nkd)
          c(i) ← argmin_j ||x_i − μ_j||²   (on a tie, keep the current cluster)
      for j = 1..k with cluster j nonempty:        # update step, O(nd)
          μ_j ← mean of { x_i : c(i) = j }
  until no assignment changes
  return c, μ
DerivationProof
  1. J(cnew,μ)=∑imin⁡j∥xi−μj∥2≤J(cold,μ)J(c_{\text{new}},\boldsymbol\mu)=\sum_i\min_j\norm{\mathbf x_i-\boldsymbol\mu_j}^2\le J(c_{\text{old}},\boldsymbol\mu)

    Assignment. With the centroids fixed, JJ is a sum of separate terms, one per point, and each is minimized by the nearest centroid:

  2. ∑x∈S∥x−m∥2=∑x∈S∥x−xˉS∥2+∣S∣ ∥xˉS−m∥2\sum_{\mathbf x\in S}\norm{\mathbf x-\mathbf m}^2=\sum_{\mathbf x\in S}\norm{\mathbf x-\bar{\mathbf x}_S}^2+\abs S\,\norm{\bar{\mathbf x}_S-\mathbf m}^2

    Update. With the assignment fixed, JJ splits by cluster. For a cluster SS with mean xˉS\bar{\mathbf x}_S and any point m\mathbf m, the cross term vanishes because ∑x∈S(x−xˉS)=0\sum_{\mathbf x\in S}(\mathbf x-\bar{\mathbf x}_S)=\mathbf 0, so the mean is the unique minimizer:

  3. J(P1)>J(P2)>J(P3)>⋯over finitely many partitionsJ(P_1)>J(P_2)>J(P_3)>\cdots\quad\text{over finitely many partitions}

    Termination. After each update the centroids are the means of the current partition, so JJ is a function of the partition alone, and there are at most knk^n partitions. A point changes cluster only if it gets strictly closer (the tie rule), so every iteration that changes the partition strictly lowers JJ. No partition can recur, and the algorithm stops.

Termination is not efficiency or optimality. Lloyd usually converges in a few dozen iterations, but some inputs need 2Ω(n)2^{\Omega(n)} iterations even in the plane (Vattani, 2011), although its smoothed complexity is polynomial (Arthur, Manthey & Röglin, 2011). The fixed point is only a local optimum, and finding the global one is NP-hard, already for k=2k=2 when the dimension is part of the input (Aloise et al., 2009) and for general kk in the plane (Mahajan, Nimbhorkar & Varadarajan, 2012).

Starts matter, so use good ones. k-means++ (Arthur & Vassilvitskii, 2007) picks the first centroid uniformly from the data and each next one with probability proportional to D(x)2D(\mathbf x)^2, the squared distance to the nearest centroid chosen so far. Before Lloyd even runs, its expected inertia is at most 8(ln⁡k+2)8(\ln k+2) times the optimum.

Check your understanding

Which property does Lloyd's algorithm guarantee on every dataset?

  1. It finds the clustering with the minimum possible inertia
  2. It converges in a number of iterations polynomial in nn
  3. It stops after finitely many iterations at a clustering that neither the assignment nor the update step can improve
  4. It reaches the same clustering from every initialization
Show the answer

C. It stops after finitely many iterations at a clustering that neither the assignment nor the update step can improve

Each step weakly lowers JJ, every change of partition lowers it strictly, and there are finitely many partitions. That gives termination at a fixed point, a local optimum, and nothing more: global optimality is NP-hard, the worst-case iteration count is exponential, and different starts reach different fixed points.

Hierarchies and density

Every clustering method encodes a notion of what a cluster is. k-means assigns each point to its nearest centroid, so its clusters are the cells of a Voronoi diagram: convex, and best suited to round groups of similar size and spread. Two families make different assumptions.

Agglomerative hierarchical clustering starts from nn singletons and repeatedly merges the two closest clusters, recording a tree of merges (a dendrogram) that can be cut at any height. The linkage defines the distance between clusters: single (closest pair; equivalent to building a minimum spanning tree and prone to chaining), complete (farthest pair), average, or Ward (the merge that least increases the within-cluster sum of squares, the k-means criterion). The general algorithm needs O(n2)\order{n^2} memory and O(n2log⁡n)\order{n^2\log n} time; single linkage runs in O(n2)\order{n^2} time with SLINK (Sibson, 1973).

DBSCAN (Ester, Kriegel, Sander & Xu, 1996) has two parameters, a radius ε\varepsilon and a count mm. A core point has at least mm points within ε\varepsilon; clusters are the connected groups of core points within ε\varepsilon of each other, plus the border points near them; everything else is labeled noise. It finds clusters of any shape and needs no kk, but one ε\varepsilon cannot fit clusters of very different densities.

MethodA cluster is…NeedsWeak spot
k-meansa Voronoi cell around a centroidkknon-convex or elongated shapes; outliers; feature scaling
Single linkagea connected chain of close pointsa cut heightchaining through bridges of noise
Ward linkagea compact group, merged greedilya cut height or kksame biases as k-means, and greedy
DBSCANa dense region separated by sparse spaceε\varepsilon, mmclusters of very different densities; high dimension
Gaussian mixtureone elliptical Gaussian componentkklocal optima; degenerate covariances

Gaussian mixtures and EM

A Gaussian mixture model is a generative model: pick a component z∈{1,…,k}z\in\{1,\dots,k\} with probability πz\pi_z, then draw x∼N(μz,Σz)\mathbf x\sim\mathcal N(\boldsymbol\mu_z,\Sigma_z). Its density is p(x)=∑jπj N(x∣μj,Σj)p(\mathbf x)=\sum_j\pi_j\,\mathcal N(\mathbf x\mid\boldsymbol\mu_j,\Sigma_j), and it clusters softly: each point gets a posterior probability of belonging to each component. Fitting it by maximum likelihood means maximizing ℓ(θ)=∑ilog⁡∑jπj N(xi∣μj,Σj)\ell(\theta)=\sum_i\log\sum_j\pi_j\,\mathcal N(\mathbf x_i\mid\boldsymbol\mu_j,\Sigma_j), the log of a sum, which has no closed-form maximizer. Expectation–maximization (EM; Dempster, Laird & Rubin, 1977) alternates two easy steps instead.

DerivationEM for a Gaussian mixture
  1. γij=P(zi=j∣xi,θ)=πj N(xi∣μj,Σj)∑l=1kπl N(xi∣μl,Σl)\gamma_{ij}=P(z_i=j\mid\mathbf x_i,\theta)=\frac{\pi_j\,\mathcal N(\mathbf x_i\mid\boldsymbol\mu_j,\Sigma_j)}{\sum_{l=1}^k\pi_l\,\mathcal N(\mathbf x_i\mid\boldsymbol\mu_l,\Sigma_l)}

    E-step. Given the current parameters, compute each point's responsibilities, the posterior probabilities of the components, by Bayes' rule:

  2. μj=1Nj∑iγijxi,Σj=1Nj∑iγij(xi−μj)(xi−μj)⊤\boldsymbol\mu_j=\frac1{N_j}\sum_i\gamma_{ij}\mathbf x_i,\qquad\Sigma_j=\frac1{N_j}\sum_i\gamma_{ij}(\mathbf x_i-\boldsymbol\mu_j)(\mathbf x_i-\boldsymbol\mu_j)^\top

    M-step. Treat the responsibilities as fractional labels and maximize the expected complete-data log-likelihood Q(θ)=∑i,jγij[log⁡πj+log⁡N(xi∣μj,Σj)]Q(\theta)=\sum_{i,j}\gamma_{ij}\big[\log\pi_j+\log\mathcal N(\mathbf x_i\mid\boldsymbol\mu_j,\Sigma_j)\big]. Each component gets a weighted Gaussian fit; with Nj=∑iγijN_j=\sum_i\gamma_{ij}:

  3. πj=Njn\pi_j=\frac{N_j}n

    For the weights, add a Lagrange multiplier for ∑jπj=1\sum_j\pi_j=1: ∂/∂πj\partial/\partial\pi_j gives Nj/πj+λ=0N_j/\pi_j+\lambda=0, and summing over jj gives λ=−n\lambda=-n:

  4. ℓ(θ)=∑ilog⁡∑jqij πj N(xi∣μj,Σj)qij ≥ ∑i,jqijlog⁡πj N(xi∣μj,Σj)qij=F(q,θ)\ell(\theta)=\sum_i\log\sum_jq_{ij}\,\frac{\pi_j\,\mathcal N(\mathbf x_i\mid\boldsymbol\mu_j,\Sigma_j)}{q_{ij}}\ \ge\ \sum_{i,j}q_{ij}\log\frac{\pi_j\,\mathcal N(\mathbf x_i\mid\boldsymbol\mu_j,\Sigma_j)}{q_{ij}}=F(q,\theta)

    Why the likelihood never decreases. For any weights qij≥0q_{ij}\ge0 with ∑jqij=1\sum_jq_{ij}=1, Jensen's inequality gives a lower bound F(q,θ)F(q,\theta), with equality when qq is the posterior at θ\theta. The E-step makes the bound tight at θold\theta_{\text{old}}; the M-step raises it; so ℓ(θnew)≥F(γ,θnew)≥F(γ,θold)=ℓ(θold)\ell(\theta_{\text{new}})\ge F(\gamma,\theta_{\text{new}})\ge F(\gamma,\theta_{\text{old}})=\ell(\theta_{\text{old}}).

python
import numpy as np
from scipy.stats import multivariate_normal

def em_step(X, pi, mu, Sigma, ridge=1e-6):
    n, d = X.shape
    k = len(pi)
    # E-step: responsibilities r[i, j] = P(z_i = j | x_i)
    dens = np.column_stack([pi[j] * multivariate_normal.pdf(X, mu[j], Sigma[j])
                            for j in range(k)])
    loglik = np.log(dens.sum(axis=1)).sum()       # of the old parameters
    r = dens / dens.sum(axis=1, keepdims=True)
    # M-step: responsibility-weighted maximum likelihood
    Nk = r.sum(axis=0)
    pi = Nk / n
    mu = (r.T @ X) / Nk[:, None]
    Sigma = np.stack([(r[:, j, None] * (X - mu[j])).T @ (X - mu[j]) / Nk[j]
                      + ridge * np.eye(d) for j in range(k)])
    return pi, mu, Sigma, loglik

Successive values of loglik never decrease. Production code works with log-densities (the log-sum-exp trick) to avoid underflow. The small ridge keeps covariances invertible.

Three facts connect EM to the rest of the lesson. k-means is a limit of EM: fix Σj=σ2I\Sigma_j=\sigma^2I and πj=1/k\pi_j=1/k and let σ→0\sigma\to0; the responsibilities harden into nearest-centroid assignments and the M-step becomes the centroid update. The likelihood is unbounded: a component that centers on one data point and shrinks its covariance to zero sends ℓ→∞\ell\to\infty, so the global "maximum" is degenerate and EM is valued for the good local maxima it finds; a floor or prior on the covariances prevents collapse. Choosing kk uses held-out likelihood or penalized criteria such as BIC, −2ℓ+(#parameters)ln⁡n-2\ell+(\#\text{parameters})\ln n.

The same E-step/M-step pattern fits hidden Markov models (Baum–Welch, in HMM Algorithms), and its lower bound FF is the evidence lower bound of variational inference (Information Theory for AI).

PCA: variance, eigenvectors and the SVD

Dimensionality reduction represents each x∈Rd\mathbf x\in\R^d by a few coordinates z∈Rk\mathbf z\in\R^k, k≪dk\ll d. Principal component analysis (Pearson, 1901; Hotelling, 1933) looks for the kk-dimensional subspace that keeps the most variance or, equivalently, loses the least squared reconstruction error. Center the data, x~i=xi−xˉ\tilde{\mathbf x}_i=\mathbf x_i-\bar{\mathbf x}, and let S=1n∑ix~ix~i⊤S=\frac1n\sum_i\tilde{\mathbf x}_i\tilde{\mathbf x}_i^\top be the sample covariance.

DerivationPrincipal components are eigenvectors
  1. 1n∑i=1n(w⊤x~i)2=w⊤S w\frac1n\sum_{i=1}^n\big(\mathbf w^\top\tilde{\mathbf x}_i\big)^2=\mathbf w^\top S\,\mathbf w

    Projecting onto a unit vector w\mathbf w gives scores w⊤x~i\mathbf w^\top\tilde{\mathbf x}_i, whose variance is a quadratic form in the covariance:

  2. 2Sw−2λw=0 ⟹ Sw=λw,w⊤Sw=λ2S\mathbf w-2\lambda\mathbf w=\mathbf 0\ \Longrightarrow\ S\mathbf w=\lambda\mathbf w,\qquad\mathbf w^\top S\mathbf w=\lambda

    Maximize subject to w⊤w=1\mathbf w^\top\mathbf w=1 with the Lagrangian w⊤Sw−λ(w⊤w−1)\mathbf w^\top S\mathbf w-\lambda(\mathbf w^\top\mathbf w-1). Its gradient vanishes exactly at eigenvectors, where the variance captured equals the eigenvalue, so the best w\mathbf w is the top eigenvector:

  3. max⁡W⊤W=Iktr⁡(W⊤SW)=λ1+⋯+λk\max_{W^\top W=I_k}\operatorname{tr}\big(W^\top SW\big)=\lambda_1+\dots+\lambda_k

    Each further component maximizes the variance subject to orthogonality to the previous ones, which by the spectral theorem (The Math Toolkit of AI) gives the next eigenvectors. For W=[w1⋯wk]W=[\mathbf w_1\cdots\mathbf w_k] with orthonormal columns, the top kk eigenvectors maximize the total variance kept:

  4. 1n∑i=1n∥x~i−WW⊤x~i∥2=tr⁡S−tr⁡(W⊤SW)=∑j>kλj\frac1n\sum_{i=1}^n\norm{\tilde{\mathbf x}_i-WW^\top\tilde{\mathbf x}_i}^2=\operatorname{tr}S-\operatorname{tr}\big(W^\top SW\big)=\sum_{j>k}\lambda_j

    The reconstruction WW⊤x~iWW^\top\tilde{\mathbf x}_i loses exactly what is not kept, so maximizing variance and minimizing squared reconstruction error are the same problem:

In practice PCA is computed from the SVD of the centered data matrix, X~=UΣV⊤\tilde X=U\Sigma V^\top: then S=V(Σ2/n)V⊤S=V(\Sigma^2/n)V^\top, so the principal directions are the right singular vectors, λj=σj2/n\lambda_j=\sigma_j^2/n, and the scores are the columns of UΣU\Sigma. This avoids forming X~⊤X~\tilde X^\top\tilde X, which squares the condition number. A full SVD costs O(ndmin⁡(n,d))\order{nd\min(n,d)}; the top kk components cost about O(ndk)\order{ndk} with Lanczos or randomized methods. Choose kk from the explained-variance ratio ∑j≤kλj/∑jλj\sum_{j\le k}\lambda_j/\sum_j\lambda_j or the elbow of a scree plot, and standardize the features first if their units differ, because PCA is not scale-invariant.

Predict before you look

A covariance matrix has eigenvalues 4,2,1,0.5,0.54,2,1,0.5,0.5. What percentage of the variance do the first two principal components keep?

Show the answer

75 %

(4+2)/(4+2+1+0.5+0.5)=6/8=75%(4+2)/(4+2+1+0.5+0.5)=6/8=75\%. The mean squared reconstruction error of the 2-D projection is the rest, 1+0.5+0.5=21+0.5+0.5=2.

Density estimation and the curse of dimensionality

The most complete description of unlabeled data is its density p(x)p(\mathbf x). A histogram estimates it by counting points in bins of width hh. The kernel density estimate (Rosenblatt, 1956; Parzen, 1962) replaces each point by a smooth bump, a probability density KK scaled by the bandwidth hh:

p^h(x)=1nhd∑i=1nK(x−xih),e.g. K(u)=(2π)−d/2e−∥u∥2/2\hat p_h(\mathbf x)=\frac1{nh^d}\sum_{i=1}^nK\Big(\frac{\mathbf x-\mathbf x_i}h\Big),\qquad\text{e.g. }K(\mathbf u)=(2\pi)^{-d/2}e^{-\norm{\mathbf u}^2/2}
The estimate is a density itself: nonnegative, and integrating to 1.

The bandwidth is a bias–variance dial. In one dimension a Taylor expansion gives E p^h(x)−p(x)≈h22μ2(K) p′′(x)\E\,\hat p_h(x)-p(x)\approx\frac{h^2}2\mu_2(K)\,p''(x), where μ2(K)=∫u2K(u) du\mu_2(K)=\int u^2K(u)\,du: wide bumps blur peaks and fill valleys. The variance is about p(x)R(K)/(nh)p(x)R(K)/(nh) with R(K)=∫K2R(K)=\int K^2: narrow bumps make a spiky estimate that changes with every sample. In dd dimensions the variance becomes order 1/(nhd)1/(nh^d). Minimizing the integrated squared bias plus variance gives

h∗∝n−1/(d+4),MISE∗∝n−4/(d+4).h^*\propto n^{-1/(d+4)},\qquad\text{MISE}^*\propto n^{-4/(d+4)}.

For a roughly Gaussian 1-D sample with a Gaussian kernel, this yields Silverman's rule of thumb h≈1.06 σ^ n−1/5h\approx1.06\,\hat\sigma\,n^{-1/5}; in practice hh is also chosen by cross-validated likelihood.

Predict before you look

In one dimension, you collect 32 times more data. By what factor should the error-optimal bandwidth shrink?

Show the answer

2 ×

h∗∝n−1/5h^*\propto n^{-1/5} and 321/5=232^{1/5}=2, so the bandwidth halves, while the optimal error falls by 324/5=1632^{4/5}=16. Slower than the parametric rate 1/n1/n: that is the price of assuming only smoothness.

Now read the rate n−4/(d+4)n^{-4/(d+4)} as a function of dimension. Halving the error takes 2(d+4)/42^{(d+4)/4} times more data: 2.4 times in one dimension, 11 times in ten. Geometry says why. To capture 1% of points spread uniformly over a 10-dimensional unit cube, a sub-cube needs side 0.011/10≈0.630.01^{1/10}\approx0.63, so a "local" neighborhood spans most of the range of every coordinate, and distances between random points concentrate around a common value. Silverman (1986) computed that estimating a standard normal density at its center to 10% relative mean squared error takes about 4 points in one dimension and about 842,000 in ten. This is the curse of dimensionality.

What rescues high-dimensional data is structure: points near low-dimensional manifolds, smoothness, and models with the right assumptions, such as mixtures, or the deep generative models (flows, VAEs, diffusion models) of Generative Models.

Key takeaways

  • k-means minimizes the inertia; Lloyd's assignment and update steps never increase it and terminate at a local optimum. The global problem is NP-hard, and k-means++ seeding is within 8(ln⁡k+2)8(\ln k+2) of optimal in expectation.
  • Clustering methods encode assumptions: Voronoi cells (k-means), chains (single linkage), density (DBSCAN), elliptical components (Gaussian mixtures). EM fits mixtures by alternating responsibilities and weighted maximum likelihood, and never decreases the likelihood.
  • PCA keeps the top eigenvectors of the covariance, the right singular vectors of the centered data: the variance kept is ∑j≤kλj\sum_{j\le k}\lambda_j and the reconstruction error ∑j>kλj\sum_{j>k}\lambda_j.
  • Low-dimensional pictures distort: PCA keeps spread, not neighborhoods; t-SNE and UMAP keep neighborhoods, not cluster sizes or distances.
  • A kernel density estimate trades bias O(h2)\order{h^2} against variance O(1/(nhd))\order{1/(nh^d)}, for an optimal error n−4/(d+4)n^{-4/(d+4)}: the curse of dimensionality, beaten only by structure.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Why must Lloyd's algorithm for k-means terminate?

  1. Its step size decreases geometrically
  2. The centroids converge to the true cluster centers
  3. The inertia never increases, drops strictly whenever the partition changes, and there are finitely many partitions
  4. It stops after a fixed number of iterations
Show the answer

C. The inertia never increases, drops strictly whenever the partition changes, and there are finitely many partitions

Both steps weakly decrease JJ; with ties broken consistently, every change of partition strictly decreases it, and JJ depends only on the partition once centroids are means. With at most knk^n partitions, none can repeat, so the algorithm stops.

Question 2

Why can k-means with k=2k=2 never separate two interleaved crescents?

  1. Its two clusters are Voronoi cells of the centroids, separated by a straight line, and the crescent split is not even its optimum
  2. It needs more restarts
  3. It needs k-means++ initialization
  4. The crescents have too many points
Show the answer

A. Its two clusters are Voronoi cells of the centroids, separated by a straight line, and the crescent split is not even its optimum

Each point joins its nearest centroid, so the boundary between two clusters is the perpendicular bisector of the centroids. In the widget, the true moon split has inertia 48.5, worse than the straight cut's 31.7, so better optimization would not help: the objective does not describe these clusters.

Question 3

In EM for a Gaussian mixture, what is the M-step update of a component's mean μj\boldsymbol\mu_j?

  1. The mean of the points closest to μj\boldsymbol\mu_j
  2. The data point with the highest responsibility for component jj
  3. The overall mean of the data
  4. The responsibility-weighted average ∑iγijxi/∑iγij\sum_i\gamma_{ij}\mathbf x_i/\sum_i\gamma_{ij}
Show the answer

D. The responsibility-weighted average ∑iγijxi/∑iγij\sum_i\gamma_{ij}\mathbf x_i/\sum_i\gamma_{ij}

The M-step is weighted maximum likelihood, with each point counted in component jj with weight γij\gamma_{ij}. In the hard-assignment limit (weights 0 or 1) it reduces to k-means' centroid update.

Question 4

For centered data X~∈Rn×d\tilde X\in\R^{n\times d} with SVD X~=UΣV⊤\tilde X=U\Sigma V^\top, the first principal direction is…

  1. the first column of UU
  2. the first column of VV, the top eigenvector of the covariance X~⊤X~/n\tilde X^\top\tilde X/n
  3. the direction of the largest data point
  4. the eigenvector of the covariance with the smallest eigenvalue
Show the answer

B. the first column of VV, the top eigenvector of the covariance X~⊤X~/n\tilde X^\top\tilde X/n

X~⊤X~/n=V(Σ2/n)V⊤\tilde X^\top\tilde X/n=V(\Sigma^2/n)V^\top, so the right singular vectors are the covariance eigenvectors and v1\mathbf v_1 maximizes the projected variance w⊤Sw\mathbf w^\top S\mathbf w. The columns of UΣU\Sigma are the scores, the coordinates of the points along each direction.

Question 5

A kernel density estimate is computed with a very small bandwidth hh. What does it look like?

  1. A single broad bump, regardless of the data
  2. Exactly the true density, since smaller hh means less bias
  3. A spike at each data point: low bias but high variance
  4. A uniform density
Show the answer

C. A spike at each data point: low bias but high variance

As h→0h\to0, each kernel collapses onto its point and p^h\hat p_h becomes a set of spikes: unbiased in the limit but wildly variable, with variance of order 1/(nhd)1/(nh^d). As h→∞h\to\infty it becomes one broad, heavily biased bump. The best hh balances the two and shrinks like n−1/(d+4)n^{-1/(d+4)}.

Go deeper

Further reading

  • C. M. Bishop, Pattern Recognition and Machine Learning (Springer, 2006), chapters 9 and 12.
  • T. Hastie, R. Tibshirani & J. Friedman, The Elements of Statistical Learning, 2nd ed. (Springer, 2009), chapter 14.
  • D. Arthur & S. Vassilvitskii, "k-means++: the advantages of careful seeding," Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 1027–1035 (2007).
  • B. W. Silverman, Density Estimation for Statistics and Data Analysis (Chapman & Hall, 1986).