Supervised Learning Algorithms

Interview-depth notes on four classic supervised learners for the data-scientist track: k-nearest neighbours, decision trees, support vector machines, and Naive Bayes — with the assumptions, failure modes, and the 'why it matters' framing each one needs.

1 — k-nearest neighbours (s53)

kNN is a lazy, non-parametric learner: there is no training phase beyond storing the data. To predict a query point x, it finds the k closest training points under a distance metric (Euclidean, Manhattan, cosine) and

• classifies by majority vote among those k neighbours, and
• regresses by averaging (optionally distance-weighted) their target values.

The choice of k is the bias–variance knob: small k (e.g. k = 1) gives a jagged, high-variance boundary that overfits; large k oversmooths toward the global majority (high bias). Cross-validation is the usual way to pick it.

Weaknesses.

• Expensive at prediction time — it stores all training data and, done naively, scans every point per query (O(n·d)). Memory and latency both scale with the dataset.
• Requires feature scaling — the distance is dominated by large-range features, so standardise/normalise first.
• The curse of dimensionality degrades distance meaningfulness: in high dimensions the nearest and farthest neighbours become almost equidistant, so 'closeness' stops discriminating.

Mitigations. Spatial indexes — KD-trees and ball-trees — accelerate neighbour search in low-to-moderate dimensions; dimensionality reduction (PCA, feature selection) and learned metrics restore signal before the distance is computed.

2 — Decision trees and why they overfit (s54)

A decision tree partitions feature space by recursive binary splits. At each node it greedily picks the feature and threshold that maximise a purity gain on the resulting child nodes — measured by either Gini impurity (the probability of misclassifying a random label) or entropy:

where the information gain is the entropy reduction H(parent) − Σ (n₍child₎/n)·H(child).

The splits are axis-aligned, so the model carves feature space into rectangular regions and predicts the leaf's majority class (or mean target).

Why they overfit. Left unconstrained, a tree keeps splitting until every leaf is pure — it can memorise the training set, yielding near-zero training error but a wildly unstable, high-variance boundary that fails to generalise. Small data perturbations produce very different trees.

Controls. Limit max depth, require a minimum number of samples per leaf (or per split), cap the number of leaves, and prune back branches that do not improve validation performance (cost-complexity pruning).

Pros. Highly interpretable (a readable set of if-then rules), handle mixed categorical and numeric features and nonlinear interactions, and need no feature scaling because splits depend only on per-feature ordering.

3 — Support vector machines and the kernel trick (s57)

A support vector machine is the maximum-margin linear classifier: among all separating hyperplanes wᵀx + b = 0, it picks the one that maximises the margin — the distance to the nearest points of either class. Those closest points, which alone determine the boundary, are the support vectors.

For non-separable data the soft margin introduces slack variables ξᵢ ≥ 0 and a penalty C, solving

Here C trades margin width against violations: small C = wide margin, more tolerated misclassifications (more regularised); large C = narrow margin, fewer violations (risking overfitting).

The kernel trick. The SVM's dual depends on the data only through inner products xᵢᵀxⱼ. The kernel trick replaces every such inner product with a kernel K(x, x′) = ⟨φ(x), φ(x′)⟩, letting the SVM fit a linear boundary in an implicit, possibly infinite-dimensional feature space φ without ever computing φ. Common choices — the RBF / Gaussian kernel K(x, x′) = exp(−γ‖x − x′‖²) and the polynomial kernel (xᵀx′ + c)ᵈ — yield nonlinear decision boundaries in the original input space at the cost of an ordinary linear solve.

4 — Naive Bayes (s55)

Naive Bayes is a generative classifier: it models P(x | y) and P(y), then applies Bayes' theorem to invert to P(y | x). The 'naive' part is the assumption of conditional independence of the features given the class, which factorises the likelihood:

Prediction is simply the argmax of that product over classes y.

Why it works despite a (usually false) assumption. The conditional-independence assumption is almost never literally true, yet the classifier only needs the argmax to land on the right class, not the probabilities to be calibrated. Even when the estimated posteriors are badly miscalibrated, the ordering of classes is often preserved, so the decision is correct.

Strengths. It is fast to train and predict (a single pass of counts / sufficient statistics), low-variance and robust with little data, and remarkably strong for text and high-dimensional sparse problems (spam filtering, document classification), where the independence approximation costs little relative to the dimensionality it buys.

Laplace smoothing. A feature value unseen for a class gives P(xᵢ | y) = 0, which would zero out the entire product. Laplace (add-one) smoothing adds a pseudo-count so no conditional probability is ever exactly zero, keeping unseen features from vetoing an otherwise likely class.

Interview one-liners

• kNN is lazy and non-parametric: majority vote / average over the k nearest points; k is the bias–variance knob and the curse of dimensionality is its Achilles' heel.
• Decision trees split greedily to maximise purity (Gini / information gain) and overfit because an unconstrained tree memorises the data — bound depth, min-samples-per-leaf, prune.
• SVMs maximise the margin; support vectors define the boundary and C trades margin vs violations.
• The kernel trick swaps inner products for a kernel to get nonlinear boundaries without computing the high-dimensional map.
• Naive Bayes assumes conditional independence of features given the class; only the argmax has to be right, so it thrives on sparse text — with Laplace smoothing for unseen features.

Rigorous references for the classic supervised learners.