Classical Models, Model Selection and the Interview Cheat Sheet

This closing chapter covers the remaining classical models that interviewers like to ask about (k-nearest neighbours, naive Bayes, SVMs), a guide to choosing between models, and a compact cheat sheet of the questions that come up most often with short model answers.

1. k-nearest neighbours (k-NN)

Predict from the $k$ closest training points (majority vote or mean). There is no training step: the data is the model (a "lazy" learner).

• Distance: Euclidean by default; cosine for text and embeddings; Manhattan for sparse or high-variance features. Scale features first, or the largest-scale feature dominates.
• Choosing $k$: small $k$ gives low bias and high variance (jagged boundary); large $k$ smooths. Pick by cross-validation; use odd $k$ for binary votes.
• Cost: prediction is $O(nd)$ naively. Use KD-trees (low dimension) or approximate nearest-neighbour indexes (high dimension).
• Curse of dimensionality: in high dimensions, distances between points concentrate, so "nearest" loses meaning. Reduce dimensionality or learn an embedding.

import numpy as np

def knn_predict(Xtr, ytr, x, k=3):
    d = np.linalg.norm(Xtr - x, axis=1)
    nearest = ytr[np.argsort(d)[:k]]
    return np.bincount(nearest).argmax()

Xtr = np.array([[0, 0], [0, 1], [1, 0], [5, 5], [5, 6], [6, 5]], dtype=float)
ytr = np.array([0, 0, 0, 1, 1, 1])
assert knn_predict(Xtr, ytr, np.array([0.5, 0.5])) == 0
assert knn_predict(Xtr, ytr, np.array([5.5, 5.5])) == 1

# the curse of dimensionality: nearest and farthest neighbours become almost equally far
rng = np.random.default_rng(0)
def contrast(d):
    X = rng.uniform(size=(2000, d)); q = rng.uniform(size=d)
    dist = np.linalg.norm(X - q, axis=1)
    return dist.max() / dist.min()
assert contrast(2) > 10 * contrast(1000)

2. Naive Bayes

Apply Bayes' theorem with the naive assumption that features are independent given the class:

$P(y\mid x)\propto P(y){\prod }_{j}P(x_j\mid y)$

Variants: Gaussian (continuous features), multinomial (word counts), Bernoulli (binary features). Training is just counting, so it is extremely fast and works with little data. It is a strong baseline for text classification and spam.

The independence assumption is usually false, so the probabilities are poorly calibrated, but the ranking of classes is often still right. Use Laplace smoothing (add one to counts) so an unseen word does not zero out the whole product, and work in log space to avoid underflow.

import numpy as np

# tiny spam example with word counts: vocabulary = [free, meeting, win]
spam = np.array([[3, 0, 2], [2, 0, 3]])
ham = np.array([[0, 3, 0], [1, 2, 0]])
vocab = 3
logp_spam = np.log((spam.sum(0) + 1) / (spam.sum() + vocab))      # Laplace smoothing
logp_ham = np.log((ham.sum(0) + 1) / (ham.sum() + vocab))
prior = np.log(0.5)

def predict(counts):
    s = prior + counts @ logp_spam
    h = prior + counts @ logp_ham
    return "spam" if s > h else "ham"

assert predict(np.array([2, 0, 1])) == "spam"
assert predict(np.array([0, 2, 0])) == "ham"
assert np.isfinite(logp_ham[2])                    # smoothing keeps an unseen word finite

3. Support vector machines (SVM)

A linear SVM finds the hyperplane that maximises the margin between classes. Only the points nearest the boundary (the support vectors) determine it. With a soft margin, a parameter $C$ trades margin width against training errors: large $C$ penalises errors heavily (low bias, high variance), small $C$ allows more slack.

The loss is the hinge loss $\max (0,1-y{w}^{\top }x)$ with $y\in \{-1,+1\}$, plus an L2 penalty.

The kernel trick: replace dot products by a kernel $K(x,x^{\prime })$ that equals a dot product in a higher-dimensional space, giving nonlinear boundaries without computing that space. The RBF kernel $K=\exp (-\gamma \Vert x-x^{\prime }{\Vert }^2)$ is the usual choice; large $\gamma$ means very local, wiggly boundaries.

Strengths: effective in high dimensions and on small or medium data. Weaknesses: training scales poorly beyond tens of thousands of samples ($O(n^2)$ to $O(n^3)$ for kernel methods), needs feature scaling, no native probabilities, and kernel and $C$ need tuning. Today, gradient boosting and neural networks are more common, but SVM questions persist.

import numpy as np

def hinge(y, score):
    return np.maximum(0, 1 - y * score)

y = np.array([1, 1, -1, -1])
assert np.allclose(hinge(y, np.array([2.0, 0.5, -3.0, 0.2])), [0.0, 0.5, 0.0, 1.2])
# correct and beyond the margin costs nothing; correct but inside the margin still costs something; wrong costs more than 1

4. Linear model, tree, boosting, neural net: how to choose

Always compare against a simple baseline and a tuned boosted-tree model on tabular tasks. Complexity must earn its place.

5. A short model-comparison table

6. The cheat sheet: questions you will actually be asked

What is overfitting and how do you prevent it? The model fits noise, so validation error is far above training error. Use more data, regularisation, simpler models, early stopping, dropout, augmentation, ensembling and proper cross-validation.

Explain bias and variance. Bias is error from wrong assumptions (underfitting); variance is sensitivity to the training sample (overfitting). Error = bias² + variance + noise. More flexibility lowers bias and raises variance.

L1 versus L2? L1 penalises $|w|$: sparse solutions, feature selection. L2 penalises $w^2$: smooth shrinkage, handles collinearity. Priors: Laplace and Gaussian.

Precision versus recall? Precision: of flagged items, how many are real. Recall: of real items, how many were found. Choose by the cost of each error, and tune the threshold.

Why is accuracy bad for imbalanced data? A constant majority prediction scores high but finds nothing. Use PR-AUC, recall at precision, or cost-based metrics.

ROC-AUC meaning? The probability a random positive is scored above a random negative; threshold-free and ranking-only.

How does a random forest differ from boosting? Forests average many independent deep trees (reduce variance); boosting adds shallow trees sequentially to fix errors (reduce bias).

What is the vanishing gradient problem? Gradients shrink through many layers (saturating activations, small weights), so early layers barely learn. Fix with ReLU-like activations, residual connections, normalisation, good initialisation.

What is regularisation for neural nets? Weight decay, dropout, early stopping, data augmentation, label smoothing, smaller networks.

What is batch norm for? Normalises activations per mini-batch to stabilise and speed training; layer norm does the same per example and is used in transformers.

How do you handle missing data? Understand why; impute (median, model-based), add missing indicators, or use models that handle missing values natively; fit imputers on training data only.

How do you detect data leakage? Implausibly high validation scores, features with near-perfect importance, check each feature's availability at prediction time, point-in-time correctness, and no preprocessing before the split.

How do you do feature selection? Filter (correlation, mutual information), wrapper (RFE), embedded (L1, tree importance), permutation importance, plus cost and availability constraints.

Generative versus discriminative? Discriminative models learn $P(y\mid x)$; generative models learn the joint or $P(x)$ and can sample.

What is the curse of dimensionality? As dimensions grow, data becomes sparse and distances concentrate, so local methods break down; you need exponentially more data or lower dimensionality.

Explain attention in one minute. Each token creates a query, key and value; the output is a softmax-weighted average of values where weights come from scaled query-key dot products. It lets every position look at every other directly, parallelises over positions, and costs quadratic time in sequence length.

How would you deploy and monitor a model? Baseline, shadow, canary or A/B with guardrails; monitor data drift, prediction distribution, latency and business metrics; plan retraining and rollback.

7. How to practise

1. Implement from scratch (NumPy only): linear and logistic regression, k-means, a decision-tree split, PCA via SVD, softmax and cross-entropy, a two-layer network with backprop and a gradient check, scaled dot-product attention. Every one is a plausible coding question.
2. Explain aloud one concept a day in under two minutes, with an example.
3. Do an end-to-end project on a messy dataset: leakage-free split, baseline, model, error analysis, and a short writeup of what you would monitor. Be ready to discuss it for 20 minutes.
4. Read error cases: look at the examples your model gets wrong; interviewers love this evidence of judgement.
5. Mock design rounds with the framework from the system-design chapter: goal, metric, data, features, model, serving, monitoring.

8. Common mistakes

• Memorising definitions without examples or trade-offs.
• Claiming a favourite model is always best. The answer is "it depends, and here is how I would test".
• Skipping the baseline.
• No error analysis.
• Forgetting business context, cost of errors and constraints.
• Overstating certainty about results from one split or one run.

9. Practice questions

1. Implement k-NN and explain how the choice of $k$ affects bias and variance.
2. Why does naive Bayes work despite a false independence assumption? What is Laplace smoothing for?
3. Explain the margin and the kernel trick in an SVM.
4. For a tabular dataset of 50,000 rows with mixed features, what is your first model and why?
5. Compare a random forest and a logistic regression for a credit-risk model that regulators will audit.
6. Which classical models need feature scaling, and which do not?
7. Pick any model and describe how it fails.