Machine Learning

Supervised and unsupervised learning

A taxonomy of learning settings defined by what feedback is available: labels, no labels, or delayed rewards.

Supervised learning fits a mapping from input to label. Unsupervised learning finds structure without labels. Reinforcement learning learns from a reward signal after actions.

The amount of supervision determines what is tractable. Labels are expensive and data is cheap, so self-supervision, which manufactures labels from the data itself, changed what scales.

The big idea

Any machine learning problem. Self-supervision applies wherever part of the input can be hidden and predicted from the rest.

Supervised learning has labeled examples and learns a mapping from input to label. Unsupervised learning has inputs alone and looks for structure: clusters, low-dimensional manifolds, density. Reinforcement learning has neither, only a reward signal that arrives after actions, which makes credit assignment the central difficulty. The amount of available supervision has historically decided what was tractable, since labels are expensive and unlabeled data is nearly free.

Self-supervision is the trick that broke that constraint, and it is the reason modern pretraining works at all.

Manufacturing a signal

The idea is to manufacture a supervised problem out of unlabeled data by hiding part of the input and asking the model to predict it. Predict the next token from the previous ones. Predict a masked word from its context. Predict whether two crops came from the same image.

No human labels anything, yet every example provides a dense supervised signal, and the internet supplies the examples. This converted a labeling problem into a compute problem, which is a far better problem to have.

Classification and regression

Classification predicts a category and regression predicts a number, and the distinction matters more in the loss than in the model. Classification uses cross-entropy against a probability distribution over classes, is evaluated with accuracy, precision, recall, or area under a curve, and cares about calibration if the probabilities will be used. Regression uses squared or absolute error, is evaluated in the units of the target, and is sensitive to outliers in proportion to how the loss penalizes them. The same architecture usually serves both with a different final layer.

A language model is self-supervised rather than unsupervised, and the difference is not pedantic. The training objective is a genuine supervised loss with a specific correct answer for every position: the token that actually came next. There is a label, it is dense, and the gradient is well defined. What makes it self-supervised is that the label was extracted from the data itself rather than provided by an annotator. Calling it unsupervised suggests the model is discovering structure without a target, which misdescribes what happens and obscures why the objective scales so well: every token in a corpus of trillions is a training signal.

Transfer and continual learning

Three learning settings share the premise that a model should carry something from earlier tasks into new ones. Transfer learning reuses a representation trained on a large source task as the starting point for a smaller target task, on the bet that early features such as edges or syntax are shared while only the later task-specific mapping must change. Fine-tuning is the usual mechanism, so the paradigm question is which layers to reuse and how far the target is allowed to move them. Meta-learning raises the target one level, training across a distribution of tasks so the model reaches good performance on a new one from very few examples, which is the setting often called learning to learn.

Continual learning drops the assumption that all data is available at once and trains on a stream of tasks arriving in sequence. Its characteristic failure is catastrophic forgetting, where training on a new task overwrites the weights that encoded earlier ones and accuracy on the old tasks falls sharply. Forgetting happens because gradient descent optimizes only the current objective, and nothing in the ordinary update preserves the parameter settings that mattered for data the model no longer sees. Defenses either replay stored examples from earlier tasks alongside the new ones or penalize movement in the parameter directions earlier tasks depended on, and both trade some capacity to learn the new task for retention of the old.

Generalized linear models

A family of models that relate a linear combination of features to a response through a link function, unifying regression and classification.

Linear regression minimizes squared error. Logistic regression models log-odds as linear in features. Ridge and lasso add penalties that shrink or zero coefficients.

Linearity in parameters makes the model interpretable and fast to fit. The link function maps the linear predictor to the response scale.

The big idea

Baseline for any supervised problem. As a predictor, only out-of-sample accuracy matters. As a measurement tool, identification and coefficient interpretation dominate.

When a supervised problem arrives as columns and a target, the first useful model is often the one whose coefficients can still be read. Generalized linear models keep the fitted part linear in the features and move the response scale through a link function, so regression and classification share one frame. That buys a fast baseline and, when the goal is measurement rather than prediction, a place where coefficient interpretation can be argued about explicitly.

Prediction versus measurement

Linear regression used as a predictor is a different exercise from linear regression used to measure an effect, and confusing the two causes a large share of applied errors. As a predictor the only question is out-of-sample accuracy, so correlated features are fine, coefficients need no interpretation, and any transform that improves held-out error is legitimate.

As a measurement tool the coefficient itself is the output, which requires the identification argument set out on the statistics page and makes multicollinearity, omitted variables and specification choices matter enormously. The same fitted object serves both purposes and the standards for judging it are unrelated.

Logistic regression

Logistic regression models the log-odds as a linear function of the inputs, which is what makes its coefficients readable. Writing $p$ for the predicted probability, the model is $\log\frac{p}{1-p} = \beta_0 + \sum_j \beta_j x_j$, so a one-unit increase in $x_j$ adds $\beta_j$ to the log-odds and multiplies the odds by $e^{\beta_j}$.

A coefficient of 0.693 doubles the odds. This is an odds ratio and not a probability ratio, and the gap between them is large when the base rate is high: doubling the odds moves a probability from 0.01 to 0.02 but only from 0.5 to 0.67. Reporting an odds ratio as though it were a relative risk is one of the most common misreadings in applied work.

Ridge and lasso

Ridge and lasso both penalize coefficient size and produce different results because the shape of the penalty differs. Ridge adds a penalty $\lambda \sum_j \beta_j^2$, for a regularization strength $\lambda \ge 0$ that sets how hard the fit is pulled toward the origin, which shrinks every coefficient smoothly toward zero without reaching it, spreads weight across correlated features, and has a closed-form solution.

Lasso adds $\lambda \sum_j |\beta_j|$, whose constraint region has corners on the axes, so the optimum frequently lands exactly on one and the coefficient becomes zero. Lasso therefore selects features while ridge only shrinks them. With a group of correlated features lasso picks one somewhat arbitrarily and zeroes the rest, which makes the selection unstable across resamples, while ridge splits the weight among them. The elastic net combines both penalties to get selection with more stable behavior under correlation.

Decision trees

A model that partitions the feature space by recursive binary splits on single features, producing an interpretable tree of decision rules.

Each split chooses the feature and threshold that most reduce impurity, measured by Gini or entropy. Prediction assigns the majority class or mean of the leaf.

Splits test only whether a value exceeds a threshold, so the model is invariant to monotone transforms of features and needs no scaling.

The big idea

Interpretable models, mixed feature types, data with missing values. Overfits severely without depth limits or pruning. Rarely deployed alone.

A tree splits by choosing the feature and threshold that most reduce impurity in the resulting children. Gini impurity for a binary node is $2p(1-p)$ and entropy is $-p\log_2 p - (1-p)\log_2(1-p)$, where $p$ is the fraction of one class in the node. Both are zero at a pure node and maximal at an even split, and they rank candidate splits almost identically: at $p = 0.5$ Gini is 0.500 and entropy 1.000, at $p = 0.9$ they are 0.180 and 0.469, at $p = 0.99$ they are 0.020 and 0.081. The choice between them almost never changes the fitted tree, and Gini is the more common default only because it avoids a logarithm.

Training cost

Finding the best split sets the training cost. The exact greedy method sorts each of $d$ features once at $O(dn \log n)$ for $n$ training samples, then finds the best threshold on each feature by a single scan, so building a tree of depth $D$ costs $O(dnD)$ beyond that sort. For a fully grown balanced tree, where $D$ is about $\log n$, the two are the same order, $O(dn \log n)$. Histogram methods replace the sort by binning each feature into a fixed number of buckets, 255 by default in LightGBM, which drops split finding to an $O(dn)$ pass to fill the histograms and an $O(db)$ scan to search them across $b$ buckets. That swap of $n$ for $b$ in the inner loop is why the boosted-tree libraries train on tens of millions of rows in minutes.

Scale invariance

Trees need no feature scaling because they only ask whether a value falls above or below a threshold, and that comparison is invariant to any monotone transform.

Multiplying a feature by 1,000 or taking its logarithm produces the same tree. This is a genuine practical advantage over anything distance-based or gradient-based, where scale determines both the geometry and the step size. Mixed types are handled natively for the same reason: a categorical feature splits by set membership, an ordinal one by threshold, and a missing value can be routed to whichever branch reduces impurity more, which means missingness becomes a usable signal instead of a preprocessing problem.

Overfitting

Overfitting is the failure mode, and it is severe because a tree grown without limit will isolate every training point in its own leaf and achieve zero training error while learning nothing. The remedies are to limit depth, to require a minimum number of samples in a node before splitting or in a leaf after it, to require a minimum impurity decrease, or to grow the tree fully and then prune back the branches whose contribution does not survive on held-out data. Cost-complexity pruning does the last of these by penalizing leaf count and choosing the penalty by cross-validation. In practice single trees are used mostly for interpretability, and the ensembles below are what get deployed.

Gradient boosting

An ensemble method that builds a strong predictor by sequentially adding weak learners fitted to the loss gradient.

Each round fits a shallow tree to the negative gradient of the loss, then adds a shrunken copy to the ensemble. Learning rate and round count trade off inversely.

Boosting reduces bias by correcting the directions where the current ensemble still has loss to remove. Shrinkage and early stopping control overfitting.

The big idea

Tabular data, where gradient-boosted trees remain the strongest default. Less effective when features share exploitable structure, as in images or sequences.

Bagging fits many trees on bootstrap resamples and averages them, which reduces variance without touching bias. The averaging helps only to the extent the trees disagree: averaging $B$ predictors with pairwise correlation $\rho$ and individual variance $\sigma^2$ gives variance $\sigma^2\left(\rho + \frac{1-\rho}{B}\right)$, so the second term vanishes with more trees and the first does not. At $B = 100$ the variance factor is 0.010 for independent trees, 0.307 at $\rho = 0.3$, and 0.604 at $\rho = 0.6$. Correlation, not tree count, is the binding constraint. A random forest attacks it by considering only a random subset of features at each split.

Boosting reduces bias instead. It adds models sequentially, each one correcting the loss left by the ensemble before it. Friedman made the precise statement in 2001: boosting is gradient descent in function space, where the object being optimized is the function $F$, not a finite parameter vector alone.

$$r_{im} = -\left[\frac{\partial L(y_i, F(x_i))}{\partial F(x_i)}\right]_{F = F_{m-1}}, \quad h_m = \arg\min_h \sum_{i=1}^{n} (r_{im} - h(x_i))^2, \quad F_m(x) = F_{m-1}(x) + \nu h_m(x)$$

symbol	meaning
$F_m$	the ensemble after $m$ rounds
$L$	the loss being minimized
$r_{im}$	the negative gradient at example $i$ in round $m$
$h_m$	the weak learner fitted to that gradient signal
$\nu$	learning rate, or shrinkage

For squared error, $L(y,F(x)) = \frac{1}{2}(y - F(x))^2$, the negative gradient is $y_i - F_{m-1}(x_i)$, exactly the residual. That equality explains the common description that boosting fits residuals. It is a special case, not the definition. With logistic, Poisson, quantile, or ranking losses, the next tree is fitted to the loss gradient on the current predictions, and ordinary residual language stops being exact.

Each tree is small, often three to eight levels, and the learning rate usually sits between 0.01 and 0.3, with 0.1 a common default. Halving the rate roughly doubles the rounds required, and a tuned model often runs from a few hundred to a few thousand rounds with early stopping. The regularizers are structural: depth, minimum samples per leaf, learning rate, round count, subsampling, column sampling, and penalties on leaf weights in implementations that expose them.

What XGBoost added

XGBoost did not add the idea of gradient boosting. Chen and Guestrin’s 2016 KDD paper added an objective, split rule, and implementation that made tree boosting fast enough and reliable enough to become the default tabular workhorse.

The algorithmic change starts with a second-order approximation of the loss, so the split criterion uses both the first derivative $g_i$ and second derivative $h_i$ of the loss with respect to the current prediction. XGBoost also writes tree complexity directly into the objective, with a penalty on the number of leaves and on leaf weights. In its common form, the tree penalty is $\Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^{T} w_j^2$, where $T$ is the leaf count and $w_j$ is a leaf score. That term is not an after-the-fact pruning rule. It is part of the split calculation.

The missing-value rule mattered just as much in practice. XGBoost’s sparsity-aware split finder learns a default direction at each split, so missing values and sparse zeros flow to the branch that gives the best loss reduction. The same paper describes weighted quantile sketching for approximate split candidates, cache-aware column access, compression, sharding, and out-of-core computation. Those systems choices are why XGBoost changed practice. Papers that summarize only the boosting algorithm miss the part that made the method win production workloads and competitions.

LightGBM and CatBoost then attacked different bottlenecks. LightGBM grows leaf-wise rather than level-wise and bins continuous features into histograms, which is substantially faster on large datasets at some risk of deeper, more overfit trees. CatBoost targets categorical features with ordered target-statistic encoding that avoids the leakage naive target encoding introduces, and uses symmetric trees that are fast to evaluate. All three can land within a small margin of each other, and tuning effort often matters more than the library choice.

Why boosted trees still beat neural networks on tabular data

Grinsztajn, Oyallon, and Varoquaux treated the tabular comparison as an empirical question in 2022 rather than as folklore. Their benchmark used 45 datasets from varied domains, compared tree-based models with standard and newer neural tabular models, and accounted for hyperparameter search. The result in the abstract is deliberately scoped: tree-based models remained state of the art on medium-sized tabular data, around 10,000 samples, even before counting their speed advantage. It is not a theorem about every table, every data scale, or every neural architecture published later.

Their mechanism is about inductive bias. Typical tabular columns have names, units, missingness patterns, and marginal distributions that carry meaning. A tree preserves that axis orientation because every split asks whether one named feature crosses one threshold. Rotation invariance is not an advantage there. If a random rotation mixes income, age, and a lab result into dense linear combinations, the table has lost the coordinate system that made simple thresholds useful.

The same paper found two other pressures. Tree ensembles are robust to uninformative features because a useless column usually does not reduce split loss and is ignored, while a dense neural layer must learn to cancel its contribution. Trees also fit irregular target functions with thresholds and plateaus naturally. Smooth neural networks can represent those functions, but the representation is less aligned with the data. Neural models become more plausible when sample sizes are much larger or when the columns contain exploitable structure beyond a flat table.

Failure modes

Tree ensembles extrapolate badly. A decision tree predicts a constant value in each leaf, and an additive ensemble of trees is still piecewise constant. Outside the observed training range, the prediction stays flat along the terminal leaves rather than continuing a trend. Monotonic constraints can impose direction within the learned partition, but they do not turn a boosted tree into a model with linear or mechanistic extrapolation.

Boosting can overfit through too many rounds. Shrinkage slows the damage, but each additional tree still gets another chance to fit validation noise. Early stopping is therefore part of the estimator, not a convenience. A run that reports only the best training loss has not selected a boosted model. It has selected a round count by looking in the wrong place.

Feature importance is another common failure. Split-count importance and impurity-gain importance favor continuous and high-cardinality features because those variables offer more candidate split points. Zhou and Hooker analyze the bias for tree-based methods. Treat split counts as a debugging hint, not as evidence that a feature matters. Use permutation importance, grouped permutation for correlated columns, held-out ablations, or domain tests when the importance claim will drive a decision.

Naive Bayes and k-NN

Two classical methods: naive Bayes assumes conditional independence of features given the class; k-nearest neighbors predicts from the labels of nearby training points.

Naive Bayes multiplies one-dimensional likelihoods and applies Bayes rule. k-NN finds the k closest training points by a distance metric and votes or averages.

Conditional independence makes the joint distribution tractable. k-NN adapts to any decision boundary because it stores the data rather than compressing it into parameters.

The big idea

Naive Bayes works for text when redundant features are limited. k-NN fails in high dimension because distance loses meaning and the curse of dimensionality dominates.

Naive Bayes applies Bayes’ rule while assuming the features are conditionally independent given the class, which reduces a joint distribution over many features to a product of one-dimensional ones. The assumption is nearly always false, and the classifier often works anyway. The reason is that classification needs only the correct ranking of class posteriors, not correct probabilities, and the errors introduced by the independence assumption frequently move all classes in the same direction and cancel in the comparison.

What naive Bayes destroys is calibration: the posteriors come out pushed toward zero and one, sometimes extremely so, and they should not be used as probabilities.

Where it fails

It fails when features are strongly redundant, since duplicating a feature effectively counts its evidence twice. Text classifiers that repeat correlated terms can be confidently wrong for this reason.

k-nearest neighbors

k-nearest neighbors predicts by finding the closest training points and taking their majority label or average value. It has no training phase, adapts to arbitrary decision boundaries, and is easy to reason about. It collapses in high dimension because the notion of nearest stops meaning anything. Its other weaknesses are practical: prediction requires searching the training set, which is expensive at scale, and the result depends heavily on the distance metric and feature scaling, neither of which the method itself provides guidance on.

Curse of dimensionality

The curse of dimensionality is worth stating with numbers rather than in the abstract. Sampling ten points along each axis takes 10 points in one dimension, 1,000 in three and $10^{20}$ in twenty, so any method that needs the space filled is finished before it starts. Volume concentrates at the boundary: the shell within 0.1 of the surface of a unit cube holds 20 percent of the volume in one dimension, 89 percent in ten and essentially all of it in a hundred, so every point is near an edge and interpolation becomes extrapolation.

With 1,000 uniform points and a random query point, the gap between the farthest and nearest distances, as a fraction of the nearest, falls from the order of 100 in two dimensions to about 2.8 in ten, 0.4 in a hundred and 0.12 in a thousand.

Equidistance at high dimension

By that last case every point sits at nearly the same distance, so nearest carries almost no information and the method degenerates. Real high-dimensional data usually lies on a much lower-dimensional manifold, which is the only reason anything works at all in this regime.

Dimensionality reduction

Methods that project high-dimensional data into fewer dimensions, trading information for tractability or visualization.

PCA finds the linear projection that preserves the most variance by eigendecomposition of the covariance matrix. t-SNE and UMAP optimize a neighborhood-preservation criterion nonlinearly.

The covariance eigenvalues measure variance along each principal direction, so truncating to the top k directions minimizes reconstruction error in a least-squares sense.

The big idea

PCA for preprocessing or compression when linear structure suffices. t-SNE and UMAP for visualization only; their output distances and cluster sizes are not interpretable.

Principal component analysis is the eigendecomposition of the covariance matrix, which is exactly the object introduced on the mathematics page rather than a separate technique. Centering the data and computing the covariance gives a symmetric positive semi-definite matrix whose eigenvectors are orthogonal directions and whose eigenvalues are the variance along each. Sorting by eigenvalue and keeping the top $k$ gives the $k$-dimensional projection that preserves the most variance, and the fraction of eigenvalue mass retained states exactly how much was kept. It is computed through the singular value decomposition rather than by forming the covariance explicitly, for numerical reasons.

PCA is linear, so it cannot unfold a curved manifold, and it is scale-dependent, so features must be standardized first unless their units are genuinely comparable.

t-SNE and UMAP produce the two-dimensional scatter plots that appear in nearly every embedding analysis, and neither may be read as preserving distance or cluster size. Both optimize a criterion about neighborhood structure, not about geometry. The distance between two clusters in the output carries no reliable information about their distance in the original space. The size of a cluster in the output reflects the local density the algorithm chose to expand or compress, not the spread of the underlying points. Both create apparent clusters in data that has none, and the number of apparent clusters changes with the perplexity or neighbor-count parameter.

t-SNE and UMAP are legitimate for one purpose: checking whether known labels separate at all in the representation. They are not evidence for any claim about the shape, separation, or relative size of what appears.

Published figures routinely make claims the method cannot support, and a caption is the place to catch them.

Clustering

Methods that partition data into groups without labels, based on distance, density, or a probabilistic model.

k-means alternates assigning points to the nearest centroid and recomputing centroids. DBSCAN groups points in dense regions and labels sparse points as noise.

k-means minimizes within-cluster variance; DBSCAN identifies connected high-density regions. Neither discovers the right number of clusters automatically.

The big idea

Exploratory analysis, customer segmentation, initializing other algorithms. k-means assumes spherical clusters of similar size. DBSCAN struggles with varying densities.

k-means alternates between assigning each point to the nearest centroid and recomputing centroids as the mean of their assigned points, which monotonically decreases within-cluster variance and converges to a local optimum. It is fast and it carries strong assumptions: clusters are spherical, of comparable size and density, and separable by distance to a center. Data violating any of these gets carved up incorrectly with no warning. The result depends on initialization, so k-means++ seeding and multiple restarts are standard.

Choosing k

Choosing $k$ is not a solved problem, and the popular heuristics are weaker than their ubiquity suggests. The elbow method plots within-cluster variance against $k$ and looks for a bend, but variance decreases monotonically and the bend is often absent or ambiguous. The silhouette score compares within-cluster to nearest-other-cluster distance and gives a defensible number, though it still favors the spherical structure k-means assumes. The gap statistic compares against a null reference distribution, which is more principled and more expensive.

In most real data there is no true $k$: structure exists at multiple scales simultaneously, and $k$ is a choice about the resolution of the question rather than a parameter to be estimated.

Hierarchical and density-based methods

Hierarchical clustering builds a tree instead of a partition, either agglomerating from singletons or dividing from the whole, and produces a dendrogram that shows structure at every scale at once. Cutting it at a chosen height gives a partition, which moves the arbitrary choice from $k$ to a threshold without removing it. The linkage criterion matters: single linkage chains through noise, complete linkage forces compact clusters, and Ward’s method minimizes variance increase and behaves most like k-means.

Density-based clustering, of which DBSCAN is the standard, defines clusters as connected regions of high point density, which lets it find arbitrarily shaped clusters, determine their number automatically, and label sparse points as noise rather than forcing them into a cluster. Its parameters are a neighborhood radius and a minimum point count, and it struggles when clusters have very different densities, which HDBSCAN addresses by varying the threshold across the hierarchy.

Expectation maximization and mixture models

Expectation maximization fits a model with unobserved variables by alternating between filling in the missing information and re-estimating the parameters. Each point is imagined to come from one of several hidden components, and the component label is the latent variable that is never seen. The E step computes, for every point, the posterior probability that each component generated it under the current parameters. The M step then treats those probabilities as soft counts and sets each parameter to the weighted maximum-likelihood value they imply. Every full iteration raises the observed-data log-likelihood or leaves it unchanged, so the sequence of likelihoods is monotone and settles at a stationary point, ordinarily a local maximum, which is why the outcome depends on where the iteration starts and several restarts from different seeds are standard. The hidden Markov model fit by Baum-Welch runs the same procedure over a chain of latent states rather than over independent points.

A Gaussian mixture is the canonical case: each component is a Gaussian with its own mean and covariance, and a mixing weight sets its share of the data. Because the E step returns a probability for every component, a mixture gives each point a graded membership across clusters, where k-means commits each point to a single centroid. k-means is in fact the limiting case of a Gaussian mixture whose components share one spherical covariance as that variance is sent to zero, since the responsibilities then harden into a nearest-centroid rule and the M step reduces to averaging the assigned points. A mixture pays for its flexibility with more parameters and the same initialization fragility EM carries everywhere, and a component whose covariance collapses onto one point drives the likelihood to infinity, so implementations floor the variance or add a prior.

k-means iterating

Illustrative Gaussian points in two dimensions. Lines connect each point to its assigned center; numbered crosses mark centers.

Clusters k

3

Assign pointsPlayReset

Paused. Choose the number of clusters, then assign points and recenter.

Objective, inputs, and seeding

J = ∑ᵢ ‖xᵢ − cₐᵢ‖², in squared coordinate units. Assignment sets aᵢ to the nearest center; recentering sets cⱼ to the mean of points assigned to j. An iteration is one assignment followed by one recentering. The initial display already uses nearest-center assignments so J is defined before the first step. An empty cluster keeps its center; distance ties favor the lower center number.

Inputs: 40 points per blob, centers (-2, -1); (2, -1); (0, 2), independent coordinate standard deviation 0.8, and data seed 42. Box-Muller transforms uniform draws into Gaussian coordinates. Reset repeats k-means++ with seed 7: choose the first center uniformly from the points, then sample each additional center in proportion to squared distance from the nearest chosen center. Changing k restarts the algorithm on the same points. This is one initialization, not a search for the global minimum.

Assign, recentre, repeat; and the same data under a different k. Computed from the expression on this page rather than measured.

Support vector machines

A classifier that finds the hyperplane maximizing the margin to the nearest training points, with a kernel trick enabling nonlinear boundaries.

The optimization depends on inner products between points. A kernel function computes inner products in a high-dimensional feature space without explicit mapping.

Maximizing the margin bounds generalization error. The kernel trick lets the model work in infinite-dimensional spaces while evaluating only a function on the original inputs.

The big idea

Small to moderate datasets with clear margins. The kernel matrix is quadratic in sample size, so exact methods do not scale to large data.

A support vector machine chooses the separating hyperplane that maximizes the margin, meaning the distance to the nearest training point on either side. The optimum is determined entirely by the points sitting on the margin, called the support vectors, and every other training point could be deleted without changing the solution. That subset is not guaranteed to be small: when the classes overlap, the number of support vectors grows roughly in proportion to the sample size, so the sparsity is a property of clean, well-separated data rather than of the method. The generalization argument accordingly rests on the margin and the radius of the data, not on a support-vector count. The soft-margin version allows violations penalized by a constant $C$, which trades margin width against training errors and is the parameter that controls overfitting.

Kernel trick

The kernel trick is the more important idea and it reaches well beyond support vector machines.

The optimization depends on the training data only through inner products between pairs of points. If a feature map $\phi$ sends points into a higher-dimensional space, the algorithm needs only $\langle \phi(x), \phi(y) \rangle$, never $\phi(x)$ itself. A kernel function $K(x,y)$ that equals that inner product therefore buys the entire high-dimensional model at the cost of evaluating a function on the original inputs.

Polynomial kernels and cost

A polynomial kernel corresponds to a finite expansion; the radial basis function kernel corresponds to an infinite-dimensional space and is still a single exponential to evaluate. The same substitution converts principal component analysis, ridge regression and many other linear methods into nonlinear ones without changing their derivations, and it is the reason Gaussian processes and much of the theory around neural tangent kernels are written the way they are.

The kernel matrix is quadratic in sample size, which confines exact kernel methods to modest datasets and is why they lost ground to neural networks on large ones.

Feature engineering

The process of transforming raw columns into inputs a model can use, including encoding, scaling, imputation, and derived features.

Categorical variables are encoded by one-hot, ordinal, target, or hash. Continuous variables are scaled to comparable ranges. Missing values are imputed or flagged.

Models see numbers, not concepts. A feature whose scale dominates or whose missingness is ignored contributes noise rather than information.

The big idea

All supervised learning. Every transform must be fitted on training data alone; fitting on the full dataset before splitting is leakage.

Raw columns rarely match the numerical form a model needs. Categories arrive as labels, units put one feature on a different scale from another, and missing values can carry their own signal. Feature engineering is the set of transformations that makes those columns usable while preserving the train-test boundary. Done carelessly, the transform becomes a source of leakage or erases information the model could have used.

Encoding categoricals

Categorical variables need an encoding and the choice has consequences. One-hot encoding creates a column per level, which is safe and becomes unwieldy at high cardinality. Ordinal encoding assigns integers, which imposes an order that may not exist and misleads any model that reads the value as a magnitude. Trees survive it better than linear models but are not immune, since a threshold split can only take a contiguous run of the arbitrary numbering and needs several splits to isolate what one split on the level itself would catch; implementations with native categorical handling avoid the problem rather than tolerating it. Target encoding replaces a level with the mean outcome for that level, which is compact and leaks the target directly unless computed out-of-fold. Hashing maps levels into a fixed number of buckets, accepting collisions in exchange for bounded width.

Scaling matters for anything distance-based or gradient-based and not at all for trees; standardization to zero mean and unit variance is the default, and robust scaling by median and interquartile range is better under heavy tails. Missingness deserves more thought than it usually gets, because the fact of a value being missing often carries information. Mean imputation destroys that and understates variance, adding an explicit indicator column preserves it, and gradient-boosted trees learn a default direction for missing values directly.

Fitting on training data alone

Every transform must be fitted on training data alone. Computing a mean and standard deviation over the full dataset before splitting lets test-set information into the training transform, which is leakage even though no label was touched.

The same applies to imputation values, target encodings, feature selection, principal components and any resampling for class imbalance. The practical safeguard is to express the whole sequence as a pipeline object that is fitted inside each cross-validation fold, rather than as a script that transforms once and splits afterward. The failure this prevents is not subtle: leaked preprocessing routinely produces validation scores several points above what the model achieves in production, and it is discovered late.

Cross-validation

A resampling procedure that estimates out-of-sample performance by rotating which subset of data is held out.

k-fold splits data into k parts, trains on k-1, tests on the held-out fold, and averages. Time series uses forward-chaining so training never sees the future.

A single train-test split has high variance. Rotating the held-out set averages over splits and uses every point for both training and testing.

The big idea

Model selection and hyperparameter tuning. The test set is spent once; repeated looks transfer information and make the estimate optimistic.

Three splits serve three distinct purposes. The training set fits parameters. The validation set selects among models and hyperparameters. The test set estimates performance on data the whole process has never seen.

The test set is spent once because every look at it transfers information into the choices that follow, and after enough looks the estimate it produces is optimistic by an amount nobody can quantify. This is the multiple comparisons problem from the statistics page wearing different clothes, and the same arithmetic applies: evaluating fifty candidate models against one held-out set and reporting the best gives a number biased upward by roughly the standard error of the estimate times the expected maximum of fifty draws. Organizations that treat the test set as a leaderboard to optimize against have converted it into a second validation set and no longer have an unbiased estimate of anything.

Fold strategies

Cross-validation reuses the data by rotating which fold is held out, averaging performance across folds, which gives a lower-variance estimate than a single split and uses every point for both training and evaluation. Five or ten folds is standard, and leave-one-out is the extreme case with low bias and high variance. The variants exist because the standard version assumes exchangeable observations, which is often false.

Time series require forward-chaining, training on the past and testing on the future, since a random split lets the model see the future and produces results that evaporate in deployment. Grouped data, where multiple rows come from the same patient, user, or site, requires grouped folds that keep all rows from a group on one side, or the model memorizes the group rather than learning the relationship. Stratified folds preserve class proportions, which matters when a class is rare enough that a random fold might contain none of it.

Leakage

Leakage is the most common cause of a result that will not reproduce, and the correct reaction to an unexpectedly good validation score is to look for the leak before celebrating.

• Target leakage occurs when a feature encodes the outcome, sometimes indirectly, as when a field is only populated after the event being predicted has happened
• Temporal leakage occurs when training data postdates test data
• Preprocessing leakage occurs when a transform is fitted before the split
• Group leakage occurs when correlated rows straddle the split
• Duplicate leakage occurs when near-identical records appear on both sides, which is common in scraped data

In applied settings the leak is usually found, and the cost of not looking is a system that fails only after it is deployed.