kNN and Naive Bayes

Two simple algorithms worth knowing for different reasons: kNN because vector search is kNN and it’s now infrastructure, and Naive Bayes because it’s the fast baseline for text and a clean illustration of a modelling assumption.

k-nearest neighbours

No training. Store the data; at prediction time find the k closest points and vote (classification) or average (regression).

from sklearn.neighbors import KNeighborsClassifier

model = KNeighborsClassifier(
    n_neighbors=15,
    weights="distance",     # closer neighbours count more
    metric="minkowski", p=2,
)

Choosing k

Odd k for binary classification avoids ties. Tune by cross-validation. Note this is inverted relative to most models: larger k means more regularisation.

Scaling is mandatory

Distance-based, so a feature measured in thousands swamps one measured in units. Always scale.

The curse of dimensionality

The reason kNN fails in high dimensions, and a good interview answer.

As dimensions grow, distances between points concentrate — the ratio between the nearest and farthest neighbour approaches 1. “Nearest” stops being meaningful, and every point is roughly equidistant from every other.

import numpy as np
for d in (2, 10, 100, 1000):
    X = np.random.rand(1000, d)
    dists = np.linalg.norm(X - X[0], axis=1)[1:]
    print(f"d={d:5d}  near/far ratio = {dists.min() / dists.max():.3f}")
# ratio climbs toward 1.0 - the neighbourhood dissolves

Mitigation: reduce dimensions first (PCA, UMAP), or use a learned embedding where distance is trained to be meaningful. That second option is exactly what modern retrieval does — see below.

Cost

Naive kNN is O(n*d) per query. Fine for thousands of points, hopeless for millions.

Both tree structures degrade to brute force in high dimensions, which is why approximate nearest neighbour (ANN) indexes exist.

kNN is the foundation of vector search

This connection is worth stating explicitly in an interview: semantic search and RAG retrieval are kNN over embeddings. The changes from textbook kNN are:

• The space is a learned embedding, so distance encodes semantic similarity rather than raw feature distance — which sidesteps the curse of dimensionality, because the dimensions are meaningful rather than arbitrary.
• The search is approximate (HNSW, IVF-PQ), trading a small recall loss for orders-of-magnitude speed.

See ../09_rag_embeddings/04_vector_databases.md.

Naive Bayes

Apply Bayes’ theorem, assuming all features are conditionally independent given the class:

P(class | x) ∝ P(class) * prod( P(x_i | class) )

The independence assumption is “naive” — obviously false for text, where words correlate heavily. It works anyway, because for classification you only need the correct class to score highest; the probability estimates themselves can be badly wrong without changing the argmax.

That’s the interesting part of the answer: the model is wrong about probabilities but often right about the decision.

Variants

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.naive_bayes import ComplementNB
from sklearn.pipeline import make_pipeline

model = make_pipeline(TfidfVectorizer(ngram_range=(1, 2)), ComplementNB())

Laplace smoothing

If a word never appears with a class in training, P(word|class) = 0 zeroes the entire product — one unseen word vetoes the classification. Add-one (Laplace) smoothing, alpha=1.0 by default in sklearn, prevents it.

This is a standard question, and the “one zero kills the whole product” framing is the memorable way to answer it.

Strengths

• Extremely fast to train and predict; scales to enormous vocabularies.
• Works with very little data — it estimates simple per-feature statistics rather than a joint model.
• Naturally incremental via partial_fit.
• A genuinely useful baseline for text classification. If a transformer beats Naive Bayes by two points, that’s worth knowing before you deploy the transformer.

Weaknesses

• Probabilities are badly calibrated — typically pushed toward 0 or 1 because multiplying many correlated “independent” probabilities compounds. Use the ranking, not the number.
• Ignores feature interactions entirely.
• GaussianNB assumes normality per class, which is often violated.

Choosing between them

Interview angle

• “How does kNN work and what’s the main hyperparameter?” — no training; at query time find k nearest points and vote. k controls the bias-variance trade-off, inverted relative to most models: larger k is more regularisation.
• “Why does kNN break in high dimensions?” — distance concentration. As dimensionality rises, the nearest and farthest neighbours become nearly equidistant, so “nearest” loses meaning. Fix by reducing dimensions or by using a learned embedding where distance is trained to be semantic.
• “How is vector search related to kNN?” — it is kNN, over learned embeddings, with an approximate index (HNSW, IVF-PQ) instead of exhaustive search. The embedding is what makes high-dimensional distance meaningful.
• “What’s naive about Naive Bayes, and why does it still work?” — it assumes conditional independence of features given the class, which is false for text. It works because classification needs only the correct class to rank highest; the probability magnitudes can be wrong without flipping the argmax.
• “Why is smoothing necessary?” — an unseen feature-class combination gives probability zero, and since the model multiplies probabilities, a single zero eliminates that class entirely. Laplace smoothing adds a pseudo-count to prevent it.
• “Would you trust Naive Bayes probabilities?” — no. They’re systematically over-confident because correlated features are multiplied as if independent. Use the ordering, or calibrate.