Chapter 8 · Part II: Supervised Learning
Nearest Neighbors and Generative Classifiers
Two classifiers that look nothing like logistic regression. One memorizes the data and asks its neighbors; the other models how each class generates data and inverts the model with Bayes' rule. Each teaches a lesson that matters far beyond itself.
After this chapter you will be able to
- Classify and regress with $k$-nearest neighbors and explain how $k$ trades bias for variance.
- Explain the curse of dimensionality.
- Describe the Bayes-optimal classifier and generative versus discriminative models.
- Derive Naive Bayes, its maximum likelihood estimates, and Laplace smoothing.
- Implement Naive Bayes for text in log space.
8.1Nearest-Neighbor Classification
To classify $\vx$, find the $k$ closest training examples and take a majority vote (or average, for regression). There is no training step.
- Distance. Usually Euclidean, which mixes all features, so standardize first. Cosine distance suits text and embeddings.
- The role of $k$. $k = 1$ gives a jagged Voronoi boundary with zero training error: low bias, high variance. Larger $k$ smooths the boundary. Choose $k$ by cross-validation.
- Guarantee. As $n\to\infty$, 1-NN's error is at most twice the best possible error.
- Cost. Free to train, $O(nd)$ per query. Approximate nearest-neighbor indexes make search over billions of embeddings practical; they power retrieval for language models (Chapter 24).
8.2The Curse of Dimensionality
Nearest neighbors assumes nearby points have similar labels. In high dimensions "nearby" stops meaning much:
- Neighborhoods are not local. A sub-cube holding 1% of uniform data in $[0,1]^d$ has side $0.01^{1/d}$: 0.1 for $d = 2$, but 0.955 for $d = 100$.
- Volume concentrates near the surface. The fraction of a ball within $\epsilon$ of its surface is $1 - (1-\epsilon)^d\to 1$.
- Distances concentrate. With independent coordinates, $\E\norm{\vx - \vx'}^2$ grows like $d$ while its standard deviation grows like $\sqrt d$, so all points end up roughly equally far away.
Key idea: why high-dimensional learning works at all
Real data rarely fill their space. Digit images live in $\R^{784}$ but on a thin, curved, low-dimensional manifold: random pixel arrays look like static. Methods succeed by finding that structure (PCA, Chapter 14) or by learning features where simple distances become meaningful (neural networks and embeddings).
8.3Generative and Discriminative Classifiers
The Bayes-optimal classifier predicts $\argmax_y p(y\mid\vx)$; its error, the Bayes error, is the irreducible noise of a classification problem. Two ways to approximate it:
- Discriminative models learn $p(y\mid\vx)$ directly (logistic regression, neural classifiers).
- Generative models learn $p(\vx\mid y)$ and $p(y)$, then apply Bayes' rule: $p(y\mid\vx) = \frac{p(\vx\mid y)p(y)}{\sum_{y'}p(\vx\mid y')p(y')}$.
Generative models can also synthesize examples, flag unusual inputs, handle missing features, and often need less data. Discriminative models usually win when data are plentiful.
8.4Naive Bayes
Modeling $p(\vx\mid y)$ for 10,000 word indicators is hopeless. Naive Bayes assumes conditional independence given the class:
$$p(\vx\mid y) = \prod_{j=1}^d p(x_j\mid y), \qquad \hat y = \argmax_y\Big[\log p(y) + \sum_{j=1}^d\log p(x_j\mid y)\Big]. \tag{8.2, 8.3}$$The assumption is almost always false, yet classification only needs the argmax to be right. Work in log space to avoid underflow.
Gaussian NB fits a per-class mean and variance to each continuous feature. Multinomial NB for text represents a document by word counts $x_j$ (a bag of words) and each class by a word distribution $\boldsymbol\theta_y$, so $\log p(\vx\mid y) = \sum_j x_j\log\theta_{jy}$ plus a constant.
Show derivation: the MLE is normalized counts
Let $N_{jy}$ be the count of word $j$ in class-$y$ documents and $N_y = \sum_j N_{jy}$. Maximize $\sum_j N_{jy}\log\theta_{jy}$ subject to $\sum_j\theta_{jy} = 1$. The Lagrangian condition gives $\theta_{jy} = N_{jy}/\nu$, and the constraint forces $\nu = N_y$. So $\hat\theta_{jy} = N_{jy}/N_y$ and $\hat p(y) = n_y/n$.
Two event models for text. The multinomial model counts repeated words and ignores absent ones. The multivariate Bernoulli model records only whether each vocabulary word occurs, $p(\vx\mid y)=\prod_{j}\phi_{jy}^{x_j}(1-\phi_{jy})^{1-x_j}$ with $\hat\phi_{jy}$ the fraction of class-$y$ documents containing word $j$: absent words are evidence, repetitions are not. With large vocabularies the multinomial model usually wins (McCallum and Nigam 1998).
Laplace smoothing. A word never seen in spam gives $\log 0 = -\infty$ and vetoes the class. Add a pseudo-count $\alpha$ (usually 1):
$$\hat\theta_{jy} = \frac{N_{jy} + \alpha}{N_y + \alpha V}. \tag{8.4}$$This is the MAP estimate under a Dirichlet prior, the categorical analog of ridge.
Naive Bayes is linear. For two classes the log-odds is $\log\frac{p(1)}{p(0)} + \sum_j x_j\log\frac{\theta_{j1}}{\theta_{j0}}$, linear in the counts. Logistic regression on counts has the same boundary shape but fits the weights jointly to minimize classification loss. Project 2 compares them on real SMS spam.
8.5Gaussian Discriminant Analysis
For continuous features we can afford a full Gaussian per class. Gaussian discriminant analysis (GDA) assumes
$$y\sim\mathrm{Bernoulli}(\phi),\qquad \vx\mid y=0\sim\Normal(\boldsymbol\mu_0,\boldsymbol\Sigma),\qquad \vx\mid y=1\sim\Normal(\boldsymbol\mu_1,\boldsymbol\Sigma), \tag{8.5}$$with a shared covariance. The MLEs are the class fraction $\hat\phi$, the class means $\hat{\boldsymbol\mu}_k$, and the pooled covariance $\hat{\boldsymbol\Sigma}=\frac1n\sum_i(\vx^{(i)}-\hat{\boldsymbol\mu}_{y^{(i)}})(\vx^{(i)}-\hat{\boldsymbol\mu}_{y^{(i)}})\T$. Training is one pass; no optimization.
The posterior is logistic. In the log-odds, the shared $\boldsymbol\Sigma$ makes the quadratic terms $\vx\T\boldsymbol\Sigma^{-1}\vx$ cancel:
So GDA with shared covariance is a linear classifier, also called linear discriminant analysis (LDA). With a covariance per class the quadratic terms survive: quadratic discriminant analysis (QDA), with a curved boundary.
GDA or logistic regression? GDA's assumptions imply a logistic posterior, but not conversely (Poisson classes, or any exponential family with shared dispersion, also give one). GDA assumes more: when classes are near Gaussian it needs less data; when they are not (heavy tails, clusters), its means and covariance are pulled by points irrelevant to the boundary, and logistic regression is more robust. Ng and Jordan (2002) showed the generative model approaches its higher asymptotic error faster; the discriminative one reaches a lower error with more data.
import numpy as np
from sklearn.datasets import make_classification
from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
def fit_gda(X, y):
phi = y.mean()
mu0, mu1 = X[y == 0].mean(0), X[y == 1].mean(0)
R = X - np.where(y[:, None] == 1, mu1, mu0) # residuals around own class mean
Sigma = R.T @ R / len(y) # pooled covariance
theta = np.linalg.solve(Sigma, mu1 - mu0) # Eq. (8.6)
theta0 = (0.5 * mu0 @ np.linalg.solve(Sigma, mu0) - 0.5 * mu1 @ np.linalg.solve(Sigma, mu1)
+ np.log(phi / (1 - phi)))
return theta, theta0
X, y = make_classification(500, n_features=5, n_informative=3, random_state=0)
theta, theta0 = fit_gda(X, y)
ours = (X @ theta + theta0 > 0).astype(int)
lda = LinearDiscriminantAnalysis().fit(X, y)
print("agreement with sklearn LDA:", np.mean(ours == lda.predict(X)))
print("training accuracy:", np.mean(ours == y))
8.6Implementation
import numpy as np
def knn_predict(Xtr, ytr, Xq, k=5):
d2 = (Xq**2).sum(1)[:, None] - 2 * Xq @ Xtr.T + (Xtr**2).sum(1)[None, :]
idx = np.argpartition(d2, k, axis=1)[:, :k] # k nearest, unordered
return np.array([np.bincount(v).argmax() for v in ytr[idx]])
class MultinomialNB:
def __init__(self, alpha=1.0): self.alpha = alpha
def fit(self, X, y): # X: (n, V) word counts
self.classes = np.unique(y)
counts = np.array([X[y == c].sum(0) for c in self.classes])
self.log_theta = np.log(counts + self.alpha) - \
np.log(counts.sum(1, keepdims=True) + self.alpha * X.shape[1])
self.log_prior = np.log(np.array([np.mean(y == c) for c in self.classes]))
return self
def predict(self, X):
return self.classes[(X @ self.log_theta.T + self.log_prior).argmax(1)]
In scikit-learn: KNeighborsClassifier, MultinomialNB, and CountVectorizer to turn text into counts.
8.7Common Pitfalls
Pitfall: unscaled features in $k$-NN
Features with the largest range dominate distances. Standardize, and drop irrelevant features, since each adds noise to every distance.
Pitfall: trusting Naive Bayes probabilities
Correlated features are counted as independent evidence, so posteriors are pushed toward 0 and 1. Use its decisions, not its probabilities, unless you recalibrate.
8.8Summary
- $k$-NN predicts from the $k$ closest training labels; small $k$ means low bias, high variance.
- In high dimensions neighborhoods stop being local and distances concentrate.
- Bayes-optimal: $\argmax_y p(y\mid\vx)$. Generative models learn $p(\vx\mid y)p(y)$; discriminative models learn $p(y\mid\vx)$.
- Naive Bayes assumes conditional independence; MLEs are normalized counts; Laplace smoothing avoids zeros.
- Multinomial NB is a linear classifier on word counts.
- GDA models each class as a Gaussian with shared covariance; its posterior is logistic with a linear boundary (LDA). Separate covariances give QDA. GDA needs less data when its assumptions hold; logistic regression is more robust when they do not.
8.9Exercises
- MathSide length of a sub-cube holding 10% of uniform data in $[0,1]^d$ for $d = 1, 10, 100$?
- MathFor i.i.d. $\Normal(0,1)$ coordinates, show $\E\norm{\vx - \vx'}^2 = 2d$ and $\Var\norm{\vx - \vx'}^2 = 8d$.
- MathShow that Gaussian NB with shared per-feature variances has a linear decision boundary, and find its weights.
- MathShow that Laplace smoothing is the MAP estimate under a symmetric Dirichlet$(\alpha+1)$ prior.
- CodingCross-validate $k$-NN on
load_digitsfor $k = 1..21$. Then append 50 noise features and repeat. Explain the change. - CodingCompare Gaussian NB and logistic regression on
load_breast_cancerwith training sets of 20, 50, 100, and 300 examples. - MathDerive Equation (8.6) from (8.5) and Bayes' rule. Repeat with class-specific covariances and show the log-odds is quadratic in $\vx$.
- CodingCompare GDA, QDA, and logistic regression on standardized
load_breast_cancerwith 20, 50, 100, and 400 training examples, averaged over 20 repetitions. Relate the result to Ng and Jordan (2002).