🤖 Classical ML

Classical ML covers the pre-deep-learning toolkit still central to interviews: evaluation metrics (precision and recall), linear and logistic regression, SVMs and kernels, and tree ensembles like random forests and gradient boosting. These models win when data is tabular, small, or interpretability matters.

Classical Machine Learning

The classical ML toolbox (evaluation metrics, linear and logistic regression, SVMs, tree ensembles, clustering, and shallow word embeddings) is what runs the majority of production ML in 2026. Despite the dominance of deep learning in vision, audio, and language, the workhorses of fraud detection, credit scoring, ads CTR, recommendations, and tabular analytics are still these methods. This chapter walks through each in the order you actually need to reason about them when designing a system: start with how you will measure success, then pick the model class that fits your constraints.

Evaluation Metrics

Picking the wrong evaluation metric is the single most common reason ML projects fail in production despite "looking good offline." A model with 99% accuracy on a fraud dataset may be useless; an AUC of 0.95 may hide catastrophic behavior at the operating threshold. Good ML system design starts with choosing metrics that align with the business cost of errors.

Classification: The Confusion Matrix Is the Foundation

Every classification metric ultimately derives from the confusion matrix: counts of True Positives (TP), False Positives (FP), True Negatives (TN), and False Negatives (FN).

• Accuracy = (TP + TN) / total. Misleading whenever classes are imbalanced: a 99%-negative dataset gets 99% accuracy by predicting "no" always.
• Precision = TP / (TP + FP). "Of the items I flagged, how many were correct?" Optimize this when false positives are expensive: spam filters, ad targeting, content moderation auto-removal.
• Recall (Sensitivity, TPR) = TP / (TP + FN). "Of the actual positives, how many did I catch?" Optimize this when false negatives are dangerous: cancer screening, fraud detection, safety-critical anomaly detection.
• F1 = harmonic mean of precision and recall. Useful when you need balance but the harmonic mean punishes the weaker of the two.
• F-beta generalizes F1: β > 1 weights recall more (F2 is common in medical screening), β < 1 weights precision more (F0.5 in spam/ads).

Threshold-Independent vs Threshold-Dependent Metrics

Most classifiers output a probability or score; precision/recall/F1 require choosing a threshold. Threshold-independent metrics summarize performance across all thresholds:

• ROC-AUC plots TPR vs FPR. Probability that a random positive is ranked above a random negative. Misleading under heavy class imbalance: FPR's denominator (true negatives) is huge, so even a wave of false positives barely moves the curve.
• PR-AUC plots precision vs recall. Far more informative when positives are rare (fraud, click prediction, rare disease) because both axes use only the positive class.
• Rule of thumb: if positives are <10% of data, report PR-AUC alongside ROC-AUC. If positives are <1%, ROC-AUC alone is essentially marketing.

Multi-class Averaging

For K-way classification:

• Macro-average: compute the metric per class, then average. Treats all classes equally, which is good for imbalanced datasets when you care about minority class performance.
• Micro-average: pool all TP/FP/FN globally. Dominated by majority classes; equivalent to accuracy for single-label problems.
• Weighted-average: macro, but weighted by class support. A compromise that respects prevalence.

Calibration: Are the Probabilities Trustworthy?

A model can have great AUC and terrible calibration. A "70% confident" prediction must actually be right ~70% of the time for the score to be usable as a probability (e.g., for expected-value decisions in finance, ad bidding, medical risk).

• Brier score = mean squared error of predicted probabilities vs outcomes. Lower is better.
• Expected Calibration Error (ECE) bins predictions and measures the gap between average confidence and average accuracy per bin.
• Reliability diagrams plot bin confidence vs bin accuracy. Modern deep nets are typically overconfident; fix with temperature scaling or Platt scaling.

Ranking & Retrieval Metrics

When the output is an ordered list (search, recommendations, RAG retrieval):

• Precision@k: fraction of top-k that are relevant.
• Recall@k: fraction of all relevant items that appear in top-k. Critical for retrieval where the next stage (reranker, LLM) can use everything you surface.
• Hit-rate@k: binary "any relevant item in top-k?" Common in recommendation systems with implicit feedback.
• MRR (Mean Reciprocal Rank): 1 / rank of the first relevant result, averaged. Good when there's typically one right answer (Q&A, "I feel lucky").
• MAP@k (Mean Average Precision): averages precision at each relevant position. Rewards ranking relevant items higher.
• NDCG@k: normalized discounted cumulative gain. Uses graded relevance (not just binary) and a logarithmic position discount. The default for web search, ads, recommendations.

Regression Metrics

• MSE / RMSE: squared error, heavily penalizes outliers. Use when large errors are disproportionately bad.
• MAE: absolute error, robust to outliers. Use when all errors should be weighted linearly.
• MAPE: percentage error, scale-free but blows up near zero and is asymmetric.
• RMSLE: log-space error, penalizes underestimation more, robust to right-skewed targets (prices, counts, durations).

Linear & Logistic Regression

Linear models are the workhorse of classical machine learning and, despite the deep-learning revolution, remain dominant in domains where interpretability, latency, or scale push you away from neural nets. Logistic regression in particular still powers the world's largest ads and credit-scoring systems in 2026.

Linear Regression

Linear regression models a continuous target y as a linear combination of features: y = Xβ + ε. The standard estimator minimizes MSE, which under Gaussian noise is also the MLE.

Closed-form solution (normal equation): β̂ = (X^T X)^(-1) X^T y is exact in one step but requires inverting a p × p matrix in O(p³). Fine for p < 10,000; infeasible at internet scale (a CTR system with billions of feature crosses cannot afford this). The Gram matrix X^T X is also O(np²) to construct and becomes ill-conditioned when features are correlated.

Gradient descent (and its variants): For large p or large n, iterative methods are mandatory. Stochastic / mini-batch gradient descent scales to billions of examples and supports streaming/online updates. FTRL (Follow-The-Regularized-Leader) is the per-coordinate adaptive optimizer that Google introduced for ads CTR and remains a workhorse.

Assumptions (and when they fail)

1. Linearity: E[y|X] is linear in features. Fails for non-linear relationships; partial fix is polynomial / interaction features or kernel methods.
2. Independence of residuals: fails for time series (autocorrelation) and grouped data (need mixed-effects / GEE).
3. Homoscedasticity: constant residual variance. Heteroscedastic data inflates SEs; use weighted least squares or robust (sandwich) SEs.
4. Normality of residuals: needed for valid t-tests / CIs in small samples; CLT rescues you at large n for point estimates.
5. No perfect multicollinearity: X^T X becomes singular; near-multicollinearity inflates variance of β̂ (high VIF). Ridge regularization fixes this directly by adding λI to the inverted matrix.

Regularization (Brief)

• Ridge (L2): β̂ = (X^T X + λI)^(-1) X^T y shrinks coefficients, handles multicollinearity.
• Lasso (L1): induces exact sparsity (zeros out features), used for feature selection in high-dimensional regimes.
• ElasticNet: convex combination of L1 + L2, handles correlated feature groups better than pure Lasso.

L2 regularization is essentially mandatory for production linear/logistic models; the unregularized estimator overfits badly with high-dimensional feature crosses.

Logistic Regression

P(y=1|x) = σ(w^T x + b) = 1 / (1 + e^(-(w^T x + b)))

Training minimizes the cross-entropy (log-loss): L = -Σ [y log p + (1-y) log(1-p)]. No closed-form solution exists; use gradient descent, L-BFGS, or Newton's method.

Linear decision boundary. P(y=1|x) = 0.5 corresponds to w^T x + b = 0, a hyperplane. Logistic regression cannot learn non-linear boundaries without feature engineering. This is its main weakness but also why it's interpretable.

Log-odds interpretation. log(p / (1-p)) = w^T x + b, so each coefficient w_j is the change in log-odds per unit increase in feature x_j. exp(w_j) is the odds ratio. This is why logistic regression dominates credit scoring and clinical risk models: a regulator can ask "why did you reject this applicant?" and you can answer with the contribution of each feature in basis points of log-odds.

Multinomial Extension

• Softmax (multinomial) logistic regression: P(y=k|x) = exp(w_k^T x) / Σ_j exp(w_j^T x). Jointly trained, mutually exclusive classes, naturally calibrated.
• One-vs-Rest (OvR): train K independent binary classifiers, predict argmax. Easier to parallelize and to extend with new classes, but probabilities don't sum to 1 and per-classifier imbalance hurts rare classes.

Calibration

Logistic regression is naturally well-calibrated because it directly optimizes the proper scoring rule (log-loss) corresponding to its probabilistic output. SVMs output uncalibrated margins; random forests are over-confident at the extremes; deep neural nets trained with cross-entropy are notoriously over-confident after many epochs. Production ranking systems often layer logistic regression on top of neural net scores (Platt scaling / temperature scaling); isotonic regression is a common post-hoc calibration step.

Generalized Linear Models (GLMs)

Linear and logistic regression are the two most-used members of the GLM family, which generalizes the framework to any response distribution in the exponential family via a link function:

• Gaussian + identity link = linear regression
• Bernoulli + logit link = logistic regression
• Poisson + log link = Poisson regression (counts: visits per hour, claims per policyholder)
• Gamma + log link = gamma regression (positive continuous skewed: insurance claims, transaction values)

GLMs are everywhere in insurance pricing, ad-tech, and demand forecasting.

Industry Use at Scale

• Ads CTR prediction (Google, Meta, ByteDance): the base CTR scorer is often a massive logistic regression with hundreds of millions to billions of one-hot feature crosses, trained online with FTRL. Streaming updates, per-coordinate learning rates, exact sparsity from L1, and a sub-10ms latency budget make LR the right tool on the hot path. Modern systems combine: deep model for embeddings → logistic regression for calibration and final score (the canonical "Wide & Deep" architecture).
• Credit scoring (FICO, banks): Logistic regression on hand-engineered features is the default, because the model has to be auditable, defensible in court, and stable across decades.
• Healthcare risk scores (CHADS₂, Framingham, MELD): all logistic / Cox regression models; doctors trust them because they can recompute the score on a napkin.

SVMs & Kernels

A Support Vector Machine (SVM) is a max-margin classifier: among all hyperplanes that separate two classes, it picks the one that maximizes the distance to the closest training points (the support vectors), and those are the only training examples that influence the final decision boundary.

Hard-Margin SVM

For linearly separable data: min (1/2) ||w||² s.t. yᵢ(w·xᵢ + b) ≥ 1. Maximizing the margin 2/||w|| is equivalent to minimizing ||w||². This is a convex quadratic program with a unique global optimum, one of the SVM's most attractive theoretical properties.

Soft-Margin SVM and Slack Variables

Real data is rarely linearly separable. Soft-margin introduces slack ξᵢ ≥ 0:

min (1/2) ||w||² + C Σ ξᵢ s.t. yᵢ(w·xᵢ + b) ≥ 1 - ξᵢ

Large C penalizes violations heavily (low bias, high variance); small C is more permissive. Equivalently, this minimizes the hinge loss max(0, 1 - yᵢ(w·xᵢ + b)) plus an L2 regularizer.

Primal vs Dual, and the Kernel Trick

The Lagrangian dual reformulates the problem in terms of multipliers αᵢ per training point:

max Σ αᵢ - (1/2) Σᵢⱼ αᵢαⱼ yᵢyⱼ (xᵢ·xⱼ) s.t. 0 ≤ αᵢ ≤ C, Σ αᵢyᵢ = 0

KKT complementary slackness implies that only points with αᵢ > 0 are support vectors. Crucially, the data enters only through dot products xᵢ·xⱼ, which unlocks the kernel trick: replace xᵢ·xⱼ with K(xᵢ, xⱼ) = φ(xᵢ)·φ(xⱼ) and the SVM operates as if it were in some (possibly infinite-dimensional) feature space φ without ever computing φ explicitly (Mercer's theorem). This was the breakthrough that gave SVMs nonlinear decision boundaries at the cost of a linear-model dual.

Common Kernels

• Linear: K(x,y) = x·y, same as no kernel; use the dual when n_features > n_samples.
• Polynomial: K(x,y) = (γ·x·y + r)^d captures feature interactions up to degree d.
• RBF / Gaussian: K(x,y) = exp(-γ ||x-y||²), the workhorse. Large γ = narrow influence, wiggly boundary (overfit); small γ = smoother, more bias.
• Sigmoid: K(x,y) = tanh(γ·x·y + r), of historical interest.

Why SVMs Faded, and Where They Still Earn Their Keep

The kernel SVM training cost is roughly O(n²) to O(n³) and prediction requires storing all support vectors. Gradient-boosted trees beat kernel SVMs on most tabular problems while training in a fraction of the time; deep nets dominate vision, audio, and language. But SVMs still matter in 2026 for:

• Small/medium tabular datasets (under ~50K rows) with clean, well-separated features.
• High-dimensional sparse text classification: linear SVMs trained with LIBLINEAR or SGD are still strong baselines on TF-IDF and train in seconds on millions of documents.
• One-class SVMs for anomaly detection: a staple in fraud, intrusion detection, quality control.
• Classifier heads on frozen embeddings: a linear SVM on top of a frozen vision or text encoder is a hard-to-beat few-shot baseline.

The max-margin idea also lives on in contrastive learning (SimCLR, CLIP), metric learning (triplet, ArcFace), and structured prediction.

Decision Trees & Ensembles

Tree-based methods remain the workhorse of tabular machine learning. Despite a decade of attempts to replace them with neural nets, gradient-boosted decision trees (GBDTs) still win the majority of structured-data Kaggle competitions and dominate production systems in finance, ads, and recommendations.

Decision Tree Basics

A decision tree recursively partitions feature space via greedy splits. At each node it picks the (feature, threshold) that maximally reduces an impurity measure:

• Gini impurity: 1 - Σ p_i² (CART).
• Entropy / information gain: -Σ p_i log p_i (ID3/C4.5).
• Variance reduction for regression trees.

Single trees overfit catastrophically; they can memorize any training set. Mitigate via pre-pruning (max_depth, min_samples_leaf) and post-pruning (cost-complexity α). The real power comes from ensembling.

Bagging vs Boosting (the bias-variance lens)

• Bagging trains many high-variance, low-bias trees on bootstrap samples and averages them. Averaging reduces variance without affecting bias, so deep, overfit individual trees are desirable here.
• Boosting trains weak learners (shallow trees) sequentially, each one correcting the errors of the previous ensemble. This reduces bias; variance can creep in, so regularization matters.

Random Forests

Random Forests = bagging + random feature subsetting at each split to decorrelate the trees. Typical settings: sqrt(p) features per split for classification, p/3 for regression.

• Out-of-bag (OOB) error: ~37% of rows are unused per bootstrap, giving a free validation estimate.
• Feature importance: mean decrease in impurity (biased toward high-cardinality features) or permutation importance (more reliable).
• Embarrassingly parallel: trees train independently.

Gradient Boosting Machines (GBM)

GBM treats boosting as gradient descent in function space. At each iteration, fit a new tree to the negative gradient of the loss with respect to current predictions (for squared error, exactly the residual). The new tree is added with a small learning rate (shrinkage):

F_{m+1}(x) = F_m(x) + η · h_m(x) where h_m is fit to -∂L/∂F_m.

XGBoost

XGBoost (Chen & Guestrin, 2016) made GBDTs production-grade. Key innovations:

1. Second-order Taylor expansion of the loss using gradients g_i and Hessians h_i. Optimal leaf weight: w* = -G / (H + λ); split gain: (G_L²/(H_L+λ) + G_R²/(H_R+λ) - G²/(H+λ))/2 - γ. This is Newton's method per leaf, giving much faster convergence than first-order GBM.
2. Regularized objective: Ω(f) = γT + (1/2)λ‖w‖² penalizing both leaves T and their weights.
3. Sparsity-aware split finding: learns a default direction for missing values per node.
4. Histogram-based / approximate splits with weighted quantile sketches for distributed training.
5. Cache-aware block structure and out-of-core computation.

LightGBM

LightGBM (Microsoft, 2017) is typically 2-10× faster than XGBoost at comparable accuracy:

• Histogram binning of continuous features into ~255 bins, so split finding becomes O(bins) instead of O(n) per feature.
• Leaf-wise (best-first) growth instead of level-wise. Faster convergence but can overfit narrow paths; cap with num_leaves and min_data_in_leaf.
• GOSS (Gradient-based One-Side Sampling): keep all rows with large gradients, randomly sample small-gradient rows.
• EFB (Exclusive Feature Bundling): bundles mutually exclusive sparse features into one for a large speedup on sparse data.

CatBoost

CatBoost (Yandex, 2018) targets two pain points:

• Ordered boosting: standard GBDTs suffer from prediction shift, where the gradient for row i is computed using a model that already saw row i, leaking target information. CatBoost trains on a permutation so each prediction uses only "past" rows. Less overfitting on small data.
• Native categorical handling: ordered target statistics replace categories with running mean-target encodings computed only from prior rows: no leakage, no manual one-hot.
• Symmetric (oblivious) trees: the same split at every node of a level. Faster inference and acts as regularization.

Why Tree Ensembles Still Dominate Tabular Data

Despite TabPFN, SAINT, FT-Transformer and a steady drumbeat of "this is the year deep learning wins tabular" papers, GBDTs win on most real-world tabular benchmarks. Reasons:

• Heterogeneous features (mixed types, scales, missingness): trees handle this natively.
• Axis-aligned splits match human-engineered features.
• Robust to irrelevant features.
• Default hyperparameters work: XGBoost defaults are competitive.
• Excellent on small datasets (10K-1M rows) where deep models overfit.

The challengers gain ground only on very large tabular datasets (10M+ rows) or when text/image features must be jointly modeled.

When NOT to Use Tree Ensembles

• High-dimensional sparse data (text bag-of-words, one-hot user IDs): linear models or NNs with embeddings are usually better.
• Sequential / time-series data: RNNs, Transformers, or state-space models capture order natively.
• Very low-data regimes (< few hundred rows): regularized linear models are more robust.
• When calibrated probabilities matter: wrap with Platt scaling or isotonic regression on a held-out calibration set.
• Raw images / audio / text: deep learning wins by orders of magnitude.

Clustering

Clustering is the classical unsupervised tool for finding structure in unlabeled data: segmentation, exploratory analysis, anomaly detection.

k-means partitions n points into k clusters by minimizing within-cluster sum of squared distances to the centroid. Lloyd's algorithm alternates: (1) assign each point to its nearest centroid, (2) recompute centroids as the mean of assigned points. Fast (O(n·k·d·i)), easy to parallelize, but very sensitive to initialization. k-means++ seeds centroids with probability proportional to squared distance from already-chosen centroids, giving O(log k) approximation guarantees and dramatically better convergence. Picking k is the hard question: the elbow method plots inertia vs k, the silhouette score measures cluster separation (range -1 to 1), and Davies-Bouldin measures inter-cluster similarity (lower is better). k-means assumes roughly spherical, equal-variance clusters and fails on elongated, density-varying, or non-convex shapes.

DBSCAN defines a cluster as a dense region of points; anything not in a dense region is noise. Parameters: eps (neighborhood radius) and min_samples (points to form a dense region). Advantages: no need to pre-specify k, handles arbitrary cluster shapes, naturally identifies outliers. Drawbacks: sensitive to eps, struggles with varying density (HDBSCAN fixes this), scales O(n²) naively (O(n log n) with a spatial index).

Hierarchical clustering builds a tree of clusters: agglomerative (bottom-up, merge closest pair) or divisive (top-down, split recursively). Linkage criteria: single, complete, average, or Ward (often the best default). Output is a dendrogram you can cut at any height to choose granularity. Naively O(n³), practical up to ~10K points.

For 5M+ customer-segmentation problems, the practical default is mini-batch k-means on top of standardized features (often after a PCA denoising step). DBSCAN is the right choice when you need explicit outlier detection or irregular cluster shapes. Hierarchical clustering is for small-to-medium scale where the dendrogram itself is useful for interpretation.

Classical Embeddings: The Bridge to Deep Representation Learning

Before BERT, before the transformer, before "embedding" became a generic word for any learned vector, the breakthrough idea was that you could learn dense, distributed word representations from raw text using simple shallow neural networks, and the resulting vectors captured remarkable semantic structure. Word2Vec, GloVe, and FastText were not classical statistical models in the sense of linear regression or SVMs; they were the first widely-deployed neural embedding learners, and they opened the door to everything that followed. They belong in this chapter because they are the historical and conceptual bridge from the classical bag-of-words era to the deep representation learning era that culminated in transformers.

Word2Vec: The Trigger

Word2Vec (Mikolov et al., 2013) introduced two architectures: CBOW (Continuous Bag-of-Words) predicts the center word from surrounding context words, while skip-gram predicts surrounding context words from the center word. Skip-gram works better on rare words; CBOW trains faster on frequent ones. Training the full softmax over a 100K-word vocabulary on every example is prohibitively expensive, so Word2Vec uses two tricks: negative sampling (for each positive context pair, sample k=5-20 random "negative" words and train a binary classifier instead of a multi-class softmax) and hierarchical softmax (organize the vocabulary as a Huffman tree, reducing softmax from O(V) to O(log V)). Negative sampling dominates in practice.

GloVe and FastText

GloVe (Pennington et al., 2014) factorizes the global word-word co-occurrence count matrix via a weighted least-squares regression that fits word vectors such that their dot product approximates the log of their co-occurrence count. The argument: skip-gram only sees local context, while GloVe combines local context with global corpus statistics in one objective. In practice the two produce similar-quality embeddings.

FastText (Bojanowski et al., 2017) extends Word2Vec by representing each word as the sum of its character n-gram embeddings (typically n = 3 to 6). For "playing" with 3-grams: <pl, pla, lay, ayi, yin, ing, ng> plus the special whole word <playing>. This solves two problems: (1) OOV handling, building a vector for any word, even unseen, by summing its n-grams; (2) morphological structure, since "play", "playing", "played", "plays" share most of their n-grams so they end up with similar embeddings. Essential for morphologically rich languages (Finnish, Turkish, Hindi).

Why They Were a Breakthrough

Before Word2Vec, NLP used sparse one-hot vectors (dimension = vocab size, no notion of similarity) or hand-engineered features. Word2Vec produced dense, low-dimensional, distributed representations where semantic and syntactic relationships emerged as linear structure: the famous king - man + woman ≈ queen, Paris - France + Germany ≈ Berlin. Cosine similarity between vectors gave a meaningful similarity metric for free. Suddenly any downstream NLP model (sentiment classifiers, NER taggers, retrieval systems) could start from a pre-trained semantic representation rather than learning from scratch.

Foreshadowing the Transformer

The fundamental limitation of static embeddings: each word gets one fixed vector regardless of context. "Bank" in "river bank" and "bank loan" has the same embedding. The fix had to wait for contextual embeddings: ELMo (2018) using stacked biLSTMs, then BERT (2018) and the entire transformer family, where the same word produces different vectors in different sentences based on its surrounding context. Transformers solved precisely what Word2Vec could not: word-sense disambiguation, syntactic role, long-range semantic dependencies. The conceptual lineage is direct: Word2Vec showed that dense distributed representations could be learned end-to-end from a self-supervised next-word/skip-gram objective; transformers kept the self-supervised objective (masked or causal language modeling) but made the representation contextual and stacked deep enough that it could be transferred to any downstream task. Everything from BERT to GPT-4 to modern embedding models like E5 and BGE inherits the core Word2Vec insight: representations learned from unsupervised text capture meaningful semantic and syntactic structure that transfers across tasks. The transformer is what the classical embedding methods were trying to be, given enough compute and a way to handle context.

Where Static Embeddings Still Live

Static embeddings haven't disappeared. They remain the right choice for:

• Microsecond-latency lookups at massive scale (recommendation candidate retrieval, search autocomplete).
• Edge devices where a 100MB embedding table is acceptable but a 400MB transformer is not.
• Fast baselines before investing in transformer fine-tuning.
• Bag-of-words-shaped tasks (keyword expansion, simple semantic search, related-term suggestion) where context doesn't add much.