KNN & Naive Bayes

The idea

These two families are merged here on purpose: they are the two simplest classifiers that are still strong baselines, and each fits in one sentence. KNN says you are what your neighbors are. Naive Bayes says multiply the evidence and pretend the features never talk to each other. One defers all work to query time; the other compresses the data to counts and defers nothing. Interviewers love both because each has one big idea and one famous failure mode.

K-nearest neighbors: prediction by memory

KNN has no training step — it is lazy (instance-based) learning. The "model" is the stored training set. To classify a query $x$, find the $k$ training points closest to it under some distance and take a majority vote:

$\hat{y}(x) = \operatorname{mode}\{\, y_i : i \in N_k(x) \,\}$

where $N_k(x)$ is the index set of the $k$ nearest neighbors. Training costs $O(1)$ (store the data); every query costs $O(nd)$ — a full scan of $n$ points in $d$ dimensions. Eager models pay once up front; KNN pays at every prediction, which is exactly backwards from what production usually wants.

$k$ is the bias-variance dial. At $k = 1$ the classifier memorizes the training set — zero training error, a Voronoi-cell boundary around every point, and maximal variance: one mislabeled neighbor flips predictions in its whole cell. At $k = n$ every query receives the global majority class — maximal bias, zero variance, and the model has collapsed into "predict the prior". Tune $k$ by cross-validation (a common starting heuristic is $k \approx \sqrt{n}$), and use odd $k$ for binary problems to dodge ties.

Distance choice and scaling. Standard metrics:

• Euclidean $\|x - x'\|_2$ — the default for dense, comparable features.
• Manhattan $\|x - x'\|_1$ — less dominated by a single coordinate's large deviation.
• Cosine distance $1 - \frac{x^{\top}x'}{\|x\|\,\|x'\|}$ — direction only, magnitude ignored; the workhorse for sparse text and embeddings.

Because distances add raw per-feature differences, scaling is mandatory: an income gap of 1000 contributes $1000^2 = 10^6$ to squared Euclidean distance while a 25-year age gap contributes $25^2 = 625$ — the neighbor search becomes a one-feature model. Standardize (or min-max) before any distance computation.

The famous failure mode: the curse of dimensionality. As $d$ grows with $n$ fixed, pairwise distances concentrate — the ratio of the farthest to the nearest neighbor's distance tends toward 1, so "nearest" carries almost no information and the vote approaches a poll of random points. Each irrelevant feature adds pure noise to every distance. Mitigations: feature selection, PCA or learned embeddings, cosine on sparse data.

Query-cost mitigations: KD-trees and ball trees give roughly logarithmic queries but only help in low dimension (rule of thumb: $d$ below about 20). Beyond that, approximate nearest neighbors — LSH, HNSW graphs (the engines inside libraries like FAISS) — trade exactness for orders-of-magnitude speedups.

Naive Bayes: multiply the evidence

Start from Bayes' rule and drop the denominator, which is constant across classes:

$P(y \mid x) \propto P(y)\, P(x \mid y)$

Estimating the joint $P(x \mid y)$ over $d$ features is hopeless — the table is exponential in $d$. The naive move assumes features are conditionally independent given the class:

$P(x \mid y) = \prod_{j=1}^{d} P(x_j \mid y) \qquad\Rightarrow\qquad \hat{y} = \arg\max_y \Big[ \log P(y) + \sum_j \log P(x_j \mid y) \Big]$

That factorization turns one $d$-dimensional estimation problem into $d$ one-dimensional ones — which is why NB trains in a single counting pass and shrugs at a 100,000-word vocabulary. Always work in log space: a product of hundreds of probabilities like $1/8$ underflows double precision after a few hundred factors; sums of logs never do.

Variants — match the likelihood to the feature type:

• Gaussian NB — continuous features; fits a per-class mean and variance for each feature.
• Multinomial NB — count features (word frequencies, tf); the text baseline.
• Bernoulli NB — binary presence/absence features; explicitly counts absent words as evidence, which can win on short documents.

Laplace smoothing. With counts, an unseen word-class pair gives $P(w \mid y) = 0$, and one zero in a product vetoes the entire class no matter how strong the rest of the evidence is. Add-one smoothing fixes this:

$\hat{P}(w \mid y) = \frac{N_{wy} + \alpha}{N_y + \alpha V}, \qquad \alpha = 1$

where $N_{wy}$ is the count of word $w$ in class $y$, $N_y$ the total token count in class $y$, and $V$ the vocabulary size. ($\alpha$ below 1 — Lidstone smoothing — often edges out add-one on real text.)

Calibration caveat. Correlated features get multiplied in as if independent, so NB's posteriors slam toward 0 and 1. The ranking and the argmax are usually fine; the probabilities are not. Calibrate (Platt scaling, isotonic regression) before anyone consumes them as probabilities.

Worked example

Multinomial NB spam filter. Four training documents, vocabulary $V = 3$ words: free, win, meeting.

Priors: 2 spam, 2 ham out of 4 docs, so $P(\text{spam}) = P(\text{ham}) = 1/2$. Token counts per class (spam has $5$ tokens total, ham has $3$):

Laplace-smoothed likelihoods, denominators $5 + 3 = 8$ (spam) and $3 + 3 = 6$ (ham):

Sanity check: each column sums to 1 ($\tfrac{4+3+1}{8}$ and $\tfrac{2+1+3}{6}$).

Classify "free win":

Normalize over a common denominator of 288: $3/32 = 27/288$ and $1/36 = 8/288$, so

$P(\text{spam} \mid \text{"free win"}) = \frac{27}{27 + 8} = \frac{27}{35} \approx 0.771$

Why the smoothing mattered: without it, $P(\text{win} \mid \text{ham}) = 0/3 = 0$, the ham score collapses to exactly zero, and the posterior becomes a certainty of 1.0 for spam — one never-seen word-class pair silently vetoes a class. With a realistic vocabulary this happens on virtually every document.

Log-space view: the posterior odds are $(3/32)\big/(1/36) = 27/8$, and $\log(27/8) \approx 1.216$ — the same $27/35$ after the sigmoid. On real documents you are summing hundreds of terms like $\log(1/8)$; multiplying the raw probabilities instead would underflow double precision after a few hundred words.

Cheat sheet

KNN

• Rule: majority vote of the $k$ nearest points; distance-weighted votes are the standard upgrade (helps ties and imbalance).
• Costs: train $O(1)$, query $O(nd)$; KD/ball trees help only for $d$ below about 20; use approximate NN (LSH, HNSW) beyond that.
• $k = 1$: Voronoi memorization, high variance. $k = n$: always the majority class, high bias. Tune by CV; odd $k$ for binary.
• Named fact (Cover-Hart): as $n \to \infty$, the 1-NN error rate is at most twice the Bayes-optimal error.
• Scale features first, always; cosine for sparse/text; watch class imbalance — a large $k$ drifts toward the majority class.

Naive Bayes

• Rule: $\hat{y} = \arg\max_y \big[\log P(y) + \sum_j \log P(x_j \mid y)\big]$ — always in log space.
• Smoothing: $\hat{P}(w \mid y) = \frac{N_{wy} + \alpha}{N_y + \alpha V}$; $\alpha = 1$ is add-one, $\alpha < 1$ (Lidstone) often better on text.
• Variant picker: continuous features — Gaussian; counts/tf — Multinomial; binary presence — Bernoulli (uses absences as evidence; strong on short docs).
• Boundary geometry: multinomial/Bernoulli NB have a log-posterior linear in the count/binary features (the weights are log-probabilities); Gaussian NB is quadratic (linear if variances are tied across classes).
• Probabilities are overconfident by construction; ranking is fine — calibrate if the number itself matters.

Head to head

Symptom to fix