Glossary

The construction of a function from examples rather than from explicitly written rules. A learning algorithm searches a set of candidate functions for one that reproduces observed input–output pairs and generalises to unseen inputs.

In plain words: You supply examples; the computer works out the rule. You write the search procedure, not the rule.

The set of functions a learning algorithm is permitted to return, written ℋ. Restricting ℋ is what makes generalisation possible; an unrestricted ℋ provides no reason to prefer one data-fitting function over another.

In plain words: The shapes of answer you allow the model to consider.

The set of assumptions a learning algorithm makes about which patterns are plausible, encoded by its choice of hypothesis space and objective. Every algorithm has one, and no algorithm can learn without one.

In plain words: The assumption the model brings before it sees any data.

The process of choosing parameter values that minimise a loss function on the training data. Fitting is distinct from learning: a model that fits perfectly may have memorised rather than generalised.

In plain words: Adjusting the model's numbers so it matches the training examples.

Performance on data not used during fitting. It is the only thing a model is ultimately judged on, and it is measured by the true risk R(h) rather than the empirical risk on the training sample.

In plain words: Doing well on examples the model has never seen.

The difference between true risk and empirical risk for the fitted model, R(ĥ) − R̂(ĥ). Estimated in practice as validation error minus training error.

The difference between the true value and the average prediction of a model fitted across many independent training samples. Bias is systematic error: it does not shrink as sample size grows, and averaging many models does not remove it.

In plain words: The model is consistently wrong in the same direction, because it is too rigid to represent the truth.

The expected squared deviation of a model's prediction from its own average prediction, taken over the randomness in which training sample was drawn. Variance is instability: a high-variance procedure gives very different models from similar datasets.

In plain words: The model changes a lot depending on which particular examples it happened to be trained on.

Variation in the target that no function of the available inputs can explain, with variance σ². It sets a floor on achievable error: even a perfect model attains σ², so no amount of data or model capacity reduces it.

In plain words: Randomness in the outcome itself. Two identical inputs can have different labels, and nothing can predict which.

Fitting patterns present in the training sample but not in the wider distribution, typically its noise. Diagnosed by low training error together with substantially higher validation error.

In plain words: The model memorised the training data, including its accidents.

Failing to capture structure that is present in the data, because the hypothesis space is too restricted or the model is too heavily constrained. Diagnosed by high training error and validation error of similar size.

In plain words: The model is too simple to represent the pattern that is actually there.

The expected loss of a hypothesis over the whole data distribution. It is the quantity we want to minimise and cannot compute, because the distribution is unknown.

The average loss over the training sample. It is computable and is used as a proxy for true risk, but it is optimistically biased for any hypothesis chosen by minimising it.

A function L(y, ŷ) ≥ 0 giving the cost of predicting ŷ when the truth is y. It encodes which mistakes matter and by how much; changing it changes what the fitted model optimises for.

Any modification to a learning procedure that reduces variance by constraining the effective capacity of the model, usually at the cost of some additional bias. It includes penalty terms added to the objective, but also early stopping, dropout and data augmentation.

In plain words: Making the model pay a price for complexity, so it prefers simpler explanations.

A penalty proportional to the sum of squared weights. It shrinks all coefficients proportionally towards zero without setting any exactly to zero, and stabilises estimates when predictors are correlated.

In plain words: Penalise large coefficients, shrinking them all by the same proportion.

A penalty proportional to the sum of absolute weights. Unlike L2 it drives some coefficients to exactly zero, so it performs feature selection as a side effect of fitting.

In plain words: Penalise coefficient size in a way that switches useless features off entirely.

A regularisation penalty combining L1 and L2 terms. It retains L1's ability to zero out coefficients while sharing weight among correlated features as L2 does, which stabilises the selection.

How rich a set of functions a model can express. It is affected by parameter count, but also by regularisation strength, training duration, and how many decisions were made using the data.

The portion of data used to fit model parameters. Error measured on it is optimistically biased and must not be reported as model performance.

Data held out from fitting and used to choose between models or hyperparameter settings. Because it informs selection, its error is also optimistically biased, increasingly so with the number of configurations compared.

Data used exactly once, after all decisions are final, to obtain an unbiased performance estimate. Any change made in response to a test score converts it into a validation set.

Repeatedly partitioning the data into training and validation folds so that every observation serves as validation exactly once, then averaging the fold scores. Reduces the variance of the performance estimate relative to a single split.

The presence in training of information that will not be available at prediction time. It inflates measured performance and is uniquely dangerous because it makes results look better rather than worse.

Of the cases the model predicted positive, the fraction that truly are positive. Its denominator is the model's predictions, which makes it a posterior probability and therefore sensitive to class balance.

Of the cases that truly are positive, the fraction the model identified. Its denominator is the actual positives, so unlike precision it does not depend on how many predictions were made.

The property that predicted probabilities match observed frequencies: among cases assigned probability p, a fraction p are positive. Independent of ranking quality — a model can rank perfectly and be badly calibrated.

A function mapping each outcome of an experiment to a number. It is a function, not a number: the notation X = x denotes the event consisting of all outcomes that X maps to x.

The probability-weighted average of a random variable's values — the balance point of its distribution. Need not be an attainable value.

The expected squared deviation of a random variable from its mean, measuring spread. Not linear: Var(aX) = a²Var(X), and variances of independent variables add even when the variables are subtracted.

Two events are independent when the probability of both equals the product of their probabilities — equivalently, when knowing one occurred does not change the probability of the other. Distinct from mutual exclusivity, which concerns addition rather than multiplication.

Two separate assumptions about a sample: each observation carries no information about the others, and all are drawn from the same distribution. Nearly every guarantee in statistics and learning theory depends on it, and real data frequently violates it.

The standard deviation of a statistic across hypothetical repeated samples. For a sample mean of independent observations it is σ/√n, which is why halving uncertainty requires four times the data.

Count data whose variance exceeds what the assumed model allows — for Poisson, variance greater than the mean. Indicates that events cluster or that the rate varies, and fitting the simpler model produces intervals that are too narrow.

An iterative minimisation method that repeatedly steps in the direction of steepest decrease of the objective, scaled by a learning rate.

A function is convex if the line segment between any two points on its graph lies on or above the graph. Convex objectives have no non-global local minima, which is why convex problems are considered solved.

A setting chosen before fitting that is not determined by the training objective — regularisation strength, tree depth, learning rate, number of neighbours. Chosen by search against validation performance rather than learned.

The scalar multiplying the gradient in an iterative update, controlling how far each step moves. Too large and the iterates oscillate or diverge; too small and progress is needlessly slow.

Minimising an objective by optimising one coordinate at a time, holding the rest fixed, and cycling through coordinates until convergence. Effective when each one-dimensional subproblem has a closed form.

The function that shrinks a number towards zero by a fixed amount and clamps it at zero once it would cross. It is the exact solution of the one-dimensional L1-penalised least-squares problem, which is why lasso produces exact zeros.

The reformulation of a constrained minimisation as a maximisation over multipliers on the constraints. The dual optimum never exceeds the primal optimum, and under convexity plus mild conditions the two coincide.

The first-order conditions a point must satisfy to solve a constrained optimisation problem: stationarity, primal and dual feasibility, and complementary slackness. For convex problems they are sufficient as well as necessary.

The signed difference between an observed target and the value a fitted model predicts for it, $e_i = y_i - \hat y_i$. Residuals are observable; the errors they estimate are not.

In plain words: How far off the model was on one data point, with a sign telling you which direction.

The criterion that selects the parameters minimising the sum of squared residuals. Squaring makes the objective differentiable and penalises large misses disproportionately, and yields a closed-form solution for linear models.

The $n \times p$ matrix $X$ whose rows are observations and columns are features, usually with a leading column of ones to carry the intercept. Every linear-model formula is written in terms of it.

The condition in which one feature is closely predictable from a linear combination of the others. It leaves predictions largely intact but makes individual coefficients unstable and their standard errors large, because the data cannot distinguish which correlated feature deserves the credit.

The assumption that the error variance is the same for every observation, $\Var(\varepsilon_i) = \sigma^2$ for all $i$. Its failure — heteroscedasticity — leaves coefficient estimates unbiased but invalidates the usual standard errors.

In plain words: The spread of the errors does not grow or shrink as the prediction changes.

A fixed nonlinear transformation of the input used as a feature, so that a model linear in its parameters can represent a nonlinear function of the original input. Polynomial terms, splines and radial bumps are all basis functions.

The ratio of the probability that an event occurs to the probability that it does not, $p/(1-p)$. Odds run from 0 to infinity while probability runs from 0 to 1.

The natural logarithm of the odds. It maps a probability in $(0,1)$ onto the whole real line, which is what allows an unbounded linear predictor to model a bounded probability.

The S-shaped function mapping the real line onto $(0,1)$. It is the inverse of the logit, so it converts a linear predictor back into a probability.

The function converting a vector of real scores into a probability distribution by exponentiating each entry and dividing by the total. It generalises the sigmoid from two classes to many.

The loss that charges a model the negative logarithm of the probability it assigned to the observed label. It is the negative log-likelihood of a categorical model, and it diverges when a model is confidently wrong.

The set of input points at which a classifier is exactly indifferent between two classes. Its shape — a hyperplane, a quadric, an axis-aligned staircase — is the clearest summary of what a classifier can and cannot express.

A classifier that models the joint distribution of features and label, usually as a class prior times a class-conditional density, then applies Bayes' theorem to obtain the posterior. Naive Bayes, LDA and QDA are generative.

A classifier that models the conditional distribution of the label given the features directly, without describing how the features are distributed. Logistic regression, SVMs and neural networks are discriminative.

Adding a positive constant to every observed count before converting counts to probabilities, so that no outcome receives probability zero. Without it, a single unseen feature value can zero out an entire product of probabilities.

A strategy that stores the training data and defers all computation to prediction time, rather than fitting parameters in advance. k-nearest neighbours is the canonical example: training is free, prediction is expensive.

A scalar measuring how mixed the class labels are within a subset of the data. Zero for a subset containing one class only, maximal when all classes are equally represented. Entropy and Gini impurity are the two measures in standard use.

The average information content of a random label, in bits. Used as an impurity measure it is zero for a pure node and $\log_2 K$ for $K$ equally likely classes.

The probability that two items drawn independently at random from a node carry different labels. Zero for a pure node, $1 - 1/K$ for a uniform mix over $K$ classes.

The reduction in impurity produced by a split, with each child's impurity weighted by the fraction of examples reaching it. A decision tree chooses, at each node, the split maximising it.

Removing subtrees from a grown decision tree to reduce its capacity. Cost-complexity pruning does this by penalising leaf count, collapsing any subtree whose accuracy gain does not pay for its size.

A labelled dataset is linearly separable if some hyperplane places every positive example strictly on one side and every negative example strictly on the other. XOR is the standard example of a dataset that is not.

The perpendicular distance from a separating hyperplane to the nearest training point. A support vector machine selects, among all separating hyperplanes, the one maximising this distance.

The loss charging zero once an example is classified correctly with margin at least one, and growing linearly in the shortfall otherwise. Its flat region is what makes most training points irrelevant to the fitted SVM.

A training point with a nonzero dual coefficient — one lying on or inside the margin. The fitted decision function depends only on these points; deleting any other training point leaves the solution unchanged.

A function returning the inner product of two inputs after some feature map, $K(x,x') = \langle\phi(x),\phi(x')\rangle$, computable without ever forming $\phi$. Any symmetric positive semi-definite function is a valid kernel.

Replacing every inner product in an algorithm by a kernel evaluation, so the algorithm operates in a high- or infinite-dimensional feature space at the cost of working in the original one.

The scalar nonlinearity applied to each unit's weighted input in a neural network. Without one, stacking layers collapses to a single linear map and depth buys nothing.

The result that a feed-forward network with one hidden layer and a non-polynomial activation can approximate any continuous function on a compact set to arbitrary accuracy, given enough hidden units. It is an existence statement, not a guarantee that training will find such a network.

A model that combines the predictions of several base models, by averaging, voting or a learned combination. Ensembles improve on their members when the members' errors are not perfectly correlated.

A sample of size $n$ drawn with replacement from a dataset of size $n$. Each such sample omits about 36.8% of the original rows, which is what supplies bagging with its out-of-bag validation set.

Training one model per bootstrap sample and averaging their predictions. It reduces variance without increasing bias, so it helps exactly those models that are unstable — deep trees above all.

An estimate of generalisation error computed by predicting each training row using only the ensemble members whose bootstrap sample excluded it. It is nearly free and behaves much like k-fold cross-validation.

Fitting base models in sequence, each one targeting the errors its predecessors made, and summing their contributions. Unlike bagging it reduces bias, and unlike bagging it can overfit as members are added.

A model required only to beat random guessing by some margin. Boosting theory shows that a weak learner, applied repeatedly to reweighted data, can be combined into an arbitrarily accurate predictor.

Scaling each boosting stage's contribution by a factor below one, so that progress is made in many small steps rather than a few large ones. Smaller shrinkage needs more stages but generalises better.

A prediction for a training row produced by a model that did not see that row during fitting. Stacking must be built from out-of-fold predictions, or the meta-learner trains on leaked information.

A feature's importance measured as the drop in validation performance when its values are randomly shuffled, breaking its association with the target while leaving its marginal distribution intact.

The average predicted value as one feature is varied across its range, with all other features held at their observed values and then averaged over. It shows a model's marginal response, not a causal effect.

A per-prediction feature attribution defined as that feature's Shapley value in a game whose payoff is the model output. It is the unique attribution satisfying efficiency, symmetry, dummy and additivity.