Machine Learning reference sheet

This sheet follows the fifteen units of the course in order. Each unit starts with the big idea in a few sentences, then gives the definitions, formulas, metrics and algorithms you will look up most often, with the assumptions they need. When you want the full explanation, a derivation or more examples, follow the lesson links under each topic. The numerical examples use small constructed data, chosen so that every number can be checked by hand.

A data set has $n$ examples and $p$ features. The feature vector of example $i$ is the column $\mathbf{x}_i \in \mathbb{R}^p$, the design matrix $X$ has the rows $\mathbf{x}_i^{\top}$ and size $n \times p$, the targets form the vector $\mathbf{y}$, and a prediction is $\hat{y}$. Vectors are bold lowercase, matrices are capitals and scalars are italic. A linear model has weights $\mathbf{w}$ and an intercept $b$, and a general parameter vector is $\boldsymbol{\theta}$. A hat marks an estimate or a fitted value, so $\hat{\theta}$ estimates the parameter $\theta$. The transpose is $X^{\top}$, and $\lVert \mathbf{v} \rVert_2$ and $\lVert \mathbf{v} \rVert_1$ are the Euclidean norm and the sum of the absolute entries.

A loss $L(y, \hat{y})$ scores one prediction $\hat{y}$ of the target $y$. The empirical risk of a predictor $f$ is its average loss on the $n$ training examples, and its population risk is its expected loss on a new example $(\mathbf{x}, y)$ drawn from the data distribution $P$,

Probabilities are written $P(\cdot)$ and $P(Y = 1 \mid \mathbf{x})$, expectations $E[\cdot]$ and variances $\operatorname{Var}(\cdot)$. The letter $\sigma$ is a standard deviation, except that $\sigma(z) = 1/(1 + e^{-z})$ applied to a score $z$ is the logistic sigmoid and $\sigma_1 \ge \sigma_2 \ge \cdots$ are the singular values of a matrix. The learning rate is $\eta$, and $\log$ is the natural logarithm unless a base is written. Training data fit a model, validation data choose among models and settings, and test data are used once at the end to estimate performance on new cases. A feature that predicts the target well is a predictive association, not evidence that changing the feature would change the outcome.

Learning Problems, Data, and a First Model

A learning task names what is predicted, from which information, at what time and for which decision. The data are split by role before any model-driven choice, every preprocessing rule is learned from the training data alone, and a first model is judged against a simple baseline on data it has not seen.

Learning tasks, features and targets

Machine learning fits a prediction rule, or a description of structure, from examples instead of writing the rule by hand.

Regression and classification are supervised learning, since every training example has a recorded target. The unit of observation is what one row describes, such as one parcel or one customer on one day, and rows that share a customer or a time period need not be independent. A feature is a value available when the prediction is made, the target is the quantity to predict, and the label is the recorded target of one example. Prediction time is the moment the prediction is made, and the prediction horizon is how far ahead of it the target lies. A data schema lists every column with its meaning, type, units and the time at which it becomes known.

Target leakage is a feature that carries information about the target but is not available at prediction time, such as the actual arrival time used to predict whether a parcel will be late. A baseline is a simple rule that any proposed model has to beat, such as the training mean of the target or the most frequent training class. A model that predicts well can still be useless for deciding what to change, because prediction and causation are different questions.

Lessons What Is Machine Learning?, Features, Targets, and Prediction Time

Arrays and tables in Python

A NumPy array has a shape, the tuple of its sizes along each axis. A design matrix is a two-dimensional array of shape (n, p), a target vector has shape (n,), and a pandas DataFrame is a table with named columns of possibly different types that converts to such arrays.

Broadcasting stretches an axis of length 1, or a missing leading axis, to match the other array. It never stretches an axis of any other length, so arrays of shapes (3, 2) and (2,) combine, while (3, 2) and (3,) do not. The product A * B multiplies matching entries and is not the matrix product A @ B. A notebook runs code in cells, and the order in which cells were run can differ from their order on the page, so rerun a notebook from the top before trusting its results.

Lessons Python Arrays and Tables for Machine Learning

Training, validation and test sets

Generalization is good performance on new cases from the deployment population, the cases the model will meet in use. A test score estimates performance only for data drawn the way the test data were drawn. Choosing anything because of a test score makes the test set part of development, and its score is then optimistic.

A constant baseline predicts one value for every case. On the training data the best constant is the mean of the targets for squared error, a median for absolute error and the most frequent class for accuracy. A model that does not beat this baseline on validation data shows no useful gain from its features.

Lessons Training, Validation, and Test Sets

Data leakage and honest splitting

Data leakage is any route by which information that will not be available at prediction time, or information from the evaluation data, reaches model fitting or model selection. The information boundary separates what the model may use from what it may not.

A random row split suits rows that are independent and exchangeable. A group split keeps all rows of one group on the same side and estimates performance for new groups. A temporal split trains on earlier data and evaluates on later data, which matches forecasting and any use in which the model predicts the future. The split has to match the intended use, so the right choice depends on the question as well as on the data.

Lessons Data Leakage and Honest Splitting

Exploratory analysis and missing data

Exploratory data analysis checks units, types, ranges, duplicates, missing values and distributions before modeling. Exploration that looks at the target belongs on the training data, so that the evaluation data stay unseen. The empirical distribution of a sample puts mass $1/n$ on each observed value. Its mean is the average, its median the middle ordered value or the average of the two middle values, and a $q$ quantile has a fraction of about $q$ of the data at or below it under a stated rule. A histogram shows counts in bins. An outlier lies far from the bulk of the data, which is a reason to check the record, and a valid extreme value stays in the data.

These mechanisms are assumptions, and observed data alone generally cannot tell the last two apart. Imputation fills a missing value with a modeling input, such as a training mean, a training median or a prediction from other features, and it does not recover the true value. A missingness indicator is a feature equal to 1 when the value was missing and 0 otherwise, which lets a model use the fact of missingness. Complete-case analysis drops every row with a missing value. Under missing completely at random this only loses data, while under the other mechanisms the complete cases can differ systematically from the rest. A row with a missing target is left out of fitting and scoring, since an imputed label is not an observation. Every imputation rule is fitted on the training data alone.

Lessons Exploratory Data Analysis and Data Quality, Missing Data and Reliable Imputation

Feature scaling and categorical encoding

Standardization uses the mean and standard deviation of each feature on the $n$ training rows,

and applies the same $\bar{x}_j$ and $s_j$ unchanged to validation, test and future rows. The course divides by $n$ here, and dividing by $n - 1$ is another convention, so record which one a fitted scaler used. A column with $s_j = 0$ is constant on the training data and the division is undefined, so a stated convention is needed, such as dividing by 1 after centering, which turns the column into zeros, or dropping it. Standardized training columns with $s_j > 0$ have mean 0 and standard deviation 1, and standardizing does not make a distribution normal. Min-max scaling maps $x$ to $(x - m_j)/(M_j - m_j)$ with the training minimum $m_j$ and maximum $M_j > m_j$, and new values can fall outside $[0, 1]$.

For example, training weights of 2, 4, 6 and 8 kilograms have mean 5 and standard deviation $\sqrt{5} \approx 2.236$, so a new parcel of 9 kilograms gets $z = 4/\sqrt{5} \approx 1.789$. Scaling matters for distances. With weight in kilograms and distance in kilometers, the query $(2, 5)$ has squared distances 5 to $(3, 7)$ and $9.01$ to $(5, 5.1)$, while with distance in meters the squared distances become 4,000,001 and 10,009, and $(5, 5.1)$ becomes the nearer point.

One-hot encoding turns a categorical feature with categories $c_1, \dots, c_K$ into $K$ indicator columns, where column $k$ is 1 for an example of category $c_k$ and 0 otherwise. It imposes no order on the categories. Next to an intercept the $K$ columns add up to the column of ones, so one category is dropped as the reference level or a penalty is used. An ordinal category with a meaningful order, such as small, medium and large, can be coded as ordered integers when equal steps between levels are acceptable. The list of categories is learned from the training data, and an unknown category at prediction time needs a stated rule, such as a row of zeros or an explicit column for other categories.

Lessons Feature Scaling and Categorical Encoding

K-nearest neighbors

For a query $\mathbf{x}$, k-nearest neighbors finds the $k$ training examples with the smallest Euclidean distance

Classification predicts the majority class among those $k$ neighbors, and k-nearest neighbor regression predicts the mean of their targets. A tie-breaking rule has to be stated, both for equal distances at the $k$th place and for a tied vote, for example the class of the single nearest neighbor or the smallest class index. The number of neighbors $k$ is chosen on validation data, and the features are scaled with training statistics first, because the distance adds squared differences in whatever units the features have. A small $k$ gives a flexible and noisy rule, $k = 1$ returns the stored label of any training input that is not repeated, and $k = n$ predicts the training majority class or the training mean everywhere.

For the query $(1, 0)$ and the training points $(0, 0)$ labeled red, $(2, 0)$ labeled blue and $(0, 2)$ labeled blue, the distances are 1, 1 and $\sqrt{5} \approx 2.236$. With $k = 1$ two points of different classes tie, so the answer depends on the tie rule, while $k = 3$ predicts blue by a vote of 2 to 1.

Lessons K-Nearest Neighbors

Overfitting, underfitting and model complexity

Training error is the average loss on the data used for fitting, and validation error is the average loss on held-out data. Model complexity is the flexibility of the fitted rule, such as a small $k$ in nearest neighbors, a high polynomial degree or a deep tree.

As complexity grows, training error usually falls, while validation error often falls and then rises. That shape is common but not a theorem, and a gap between the two errors can also come from noise in a small validation set or from a difference between the two sets. A memorizing predictor stores the training rows and returns the stored label, which gives zero training error whenever no input appears twice with different labels, and it says nothing about new inputs.

Lessons Overfitting, Underfitting, and Model Complexity

Linear Algebra and Calculus for Learning

A data table becomes a design matrix, and a linear model turns it into one prediction per row. Span, rank and projection decide which predictions a linear model can produce and when its coefficients are unique. Derivatives show how a loss changes with each parameter, and gradient descent uses them to move downhill with a step size small enough for the curvature.

Feature vectors, design matrices and linear predictions

The dot product of $\mathbf{w}$ and $\mathbf{x}$ in $\mathbb{R}^p$ is $\mathbf{w}^{\top}\mathbf{x} = w_1x_1 + \cdots + w_px_p$. A linear prediction for one example and for all $n$ examples at once is

where $X$ is $n \times p$, $\mathbf{w}$ has $p$ entries, $\mathbf{1}$ is the column of $n$ ones and $\hat{\mathbf{y}}$ has $n$ entries. Entry $i$ of the matrix-vector product $X\mathbf{w}$ is $\mathbf{x}_i^{\top}\mathbf{w}$, and the product needs exactly as many entries in $\mathbf{w}$ as $X$ has columns. Adding an intercept column of ones gives the augmented design matrix $\tilde{X} = [\mathbf{1} \; X]$ of size $n \times (p + 1)$ and the parameter vector $\boldsymbol{\theta} = (b, \mathbf{w})$, so that $\hat{\mathbf{y}} = \tilde{X}\boldsymbol{\theta}$ is a single product. The intercept column is a modeling device, not a feature.

For example, with weights of 2 minutes per kilometer and $0.5$ minutes per package and an intercept of 10 minutes, a delivery of 12 kilometers with 4 packages gets $\hat{y} = 10 + 2 \cdot 12 + 0.5 \cdot 4 = 36$ minutes.

Lessons Vectors, Matrices, and Linear Predictions

Norms, rank and orthogonal projection

The Euclidean norm is $\lVert \mathbf{v} \rVert_2 = \sqrt{\mathbf{v}^{\top}\mathbf{v}}$, and two vectors are orthogonal when their dot product is 0. The span of some vectors is the set of their linear combinations, and the column space of $X$ is the span of its columns, the set of all possible $X\mathbf{w}$. The columns are linearly independent when $X\mathbf{w} = \mathbf{0}$ only for $\mathbf{w} = \mathbf{0}$, and the rank of $X$ is the largest number of linearly independent columns, the dimension of the column space.

The orthogonal projection of $\mathbf{y}$ onto a subspace is the unique vector $\hat{\mathbf{y}}$ of the subspace with $\mathbf{y} - \hat{\mathbf{y}}$ orthogonal to the whole subspace, and it is the point of the subspace closest to $\mathbf{y}$. Onto the span of one nonzero vector $\mathbf{a}$,

For $\mathbf{a} = (1, 2)$ and $\mathbf{y} = (3, 1)$, both $\mathbf{a}^{\top}\mathbf{y}$ and $\mathbf{a}^{\top}\mathbf{a}$ equal 5, so $\hat{\mathbf{y}} = (1, 2)$, and the difference $\mathbf{y} - \hat{\mathbf{y}} = (2, -1)$ is orthogonal to $\mathbf{a}$. The projection is unique even when the coefficients are not. If the column is duplicated, $X = [\mathbf{a} \; \mathbf{a}]$, every $\mathbf{w}$ with $w_1 + w_2 = 1$ gives the same $\hat{\mathbf{y}}$.

A square matrix is singular when it has no inverse, which happens exactly when its columns are linearly dependent, and $X^{\top}X$ is invertible exactly when $X$ has full column rank. Conditioning describes near dependence. For $X$ with full column rank, the condition number $\kappa(X) = \sigma_{\max}/\sigma_{\min}$ is the ratio of its largest and smallest singular values, and a large value means that small changes in the data can move the solution a lot, even though the matrix is not exactly singular.

Lessons Vector Geometry, Rank, and Projection

Derivatives, gradients and the chain rule

The derivative of $f$ at $t$ is

when this limit exists, and $f$ is differentiable at $t$ when it does. The partial derivative $\partial f/\partial \theta_j$ differentiates in $\theta_j$ with the other coordinates held fixed. The gradient $\nabla f(\boldsymbol{\theta})$ is the column of partial derivatives in the order of the parameter vector, so it has the same shape as $\boldsymbol{\theta}$. For differentiable $f$, the directional derivative along a unit vector $\mathbf{u}$ is $\nabla f(\boldsymbol{\theta})^{\top}\mathbf{u}$, a nonzero gradient points in the direction of steepest increase, and $f(\boldsymbol{\theta} + \boldsymbol{\Delta}) \approx f(\boldsymbol{\theta}) + \nabla f(\boldsymbol{\theta})^{\top}\boldsymbol{\Delta}$ for small $\boldsymbol{\Delta}$.

The chain rule says that if $L = g(u)$ and $u = h(\theta)$, then $dL/d\theta = g'(u)\,h'(\theta)$, and when $\theta$ affects $L$ through several paths the contributions of the paths add. For one example with feature $x$ and target $y$, the squared error $L(w, b) = (wx + b - y)^2$ has

With $x = 2$, $y = 5$, $w = 1$ and $b = 0$ the prediction misses by $-3$, so the partial derivatives are $-12$ and $-6$. The central difference $(f(t + h) - f(t - h))/(2h)$ approximates $f'(t)$ with an error of order $h^2$ for smooth $f$. Agreement between it and a coded derivative is a numerical check, not a proof. Where $f$ is not differentiable, as $\lvert u \rvert$ at 0, a stated convention or a subgradient is needed.

Lessons Derivatives, Partial Derivatives, and the Chain Rule

Gradient descent and convexity

An objective function is the quantity a training method minimizes. Gradient descent repeats

with a learning rate $\eta > 0$. At a differentiable point with nonzero gradient the negative gradient is a descent direction, so a small enough step lowers $J$, but a large step can raise it. A stationary point has $\nabla J = \mathbf{0}$. A local minimum is lowest within a neighborhood and a global minimum is lowest overall.

For $J(w) = (w - 3)^2$ the gradient at $w = 0$ is $-6$, and one step with $\eta = 0.1$ gives $w = 0.6$. Each step multiplies the error $w - 3$ by $1 - 2\eta$, so the iterates converge to 3 exactly when $0 < \eta < 1$. At $\eta = 1$ they jump between 0 and 6 forever, and at $\eta = 1.1$ they move farther away at every step. In general, if the gradient is $\beta$-Lipschitz, which means $\lVert \nabla J(\mathbf{u}) - \nabla J(\mathbf{v}) \rVert_2 \le \beta\lVert \mathbf{u} - \mathbf{v} \rVert_2$ for all $\mathbf{u}$ and $\mathbf{v}$, a constant step $\eta \le 1/\beta$ never increases $J$, and for a convex $J$ that attains its minimum the values $J(\boldsymbol{\theta}_t)$ converge to that minimum.

A function $J$ is convex when, for all $\mathbf{u}$ and $\mathbf{v}$ and every $c \in [0, 1]$,

Every local minimum of a convex function is a global minimum, though it need not be unique. The Hessian is the matrix of second partial derivatives. A twice differentiable function on $\mathbb{R}^p$ is convex exactly when its Hessian is positive semidefinite everywhere, and at a stationary point a positive definite Hessian gives a strict local minimum, while a Hessian with both positive and negative eigenvalues gives a saddle point. Squared error and logistic loss are convex in the weights of a linear model, and the training loss of a neural network is generally not convex. A global minimum of the training loss still says nothing about performance on new data.

Lessons Gradient Descent and Optimization

Probability and Statistical Reasoning

Predictions are made under uncertainty. Conditional probability keeps track of the reference group, Bayes’ rule combines a base rate with new evidence, and distributions, expectations and variances describe what a random quantity tends to do. Estimates computed from a sample vary from sample to sample, and standard errors and confidence intervals describe that variation under stated assumptions.

Conditional probability and Bayes’ rule

An event is a set of outcomes, and $P(A \cap B)$ is the joint probability that $A$ and $B$ both occur. For $P(B) > 0$, the conditional probability and Bayes’ rule are

with $P(B) = P(B \mid A)P(A) + P(B \mid A^c)P(A^c)$. Here $P(A)$ is the prior probability or base rate, $P(B \mid A)$ is the likelihood of the evidence and $P(A \mid B)$ is the posterior probability. Events are independent when $P(A \cap B) = P(A)P(B)$, and conditionally independent given $C$, with $P(C) > 0$, when $P(A \cap B \mid C) = P(A \mid C)P(B \mid C)$. Neither kind of independence implies the other.

For example, suppose 2 percent of items are defective, and an inspection flags 90 percent of defective items and 5 percent of good ones. A flagged item is defective with probability

where $0.018 = 0.9 \cdot 0.02$ and $0.049 = 0.05 \cdot 0.98$. The probability $P(+ \mid D) = 0.9$ answers a different question, and confusing the two ignores the base rate.

Lessons Conditional Probability and Bayes’ Rule

Random variables and probability distributions

A random variable assigns a number to each outcome. Its cumulative distribution function $F(x) = P(X \le x)$ is nondecreasing, with limits 0 and 1. A discrete variable has a probability mass function $p(x) = P(X = x)$ whose values add to 1, written with summation notation as $\sum_x p(x) = 1$. A continuous variable has a probability density function $f(x) \ge 0$ with

The integral is the area under the density between $a$ and $b$. Every single value has probability 0, and a density can exceed 1, as the uniform density on $[0, 0.5]$, which equals 2 there.

With $m = 10$ independent trials and $q = 0.1$, the probability of no success is $0.9^{10} \approx 0.349$. About 95 percent of a normal distribution lies within $1.96$ standard deviations of its mean.

Lessons Random Variables and Probability Distributions

Expectation, variance and covariance

The expected value is $E[X] = \sum_x x\,p(x)$ for a discrete variable and $E[X] = \int x f(x)\,dx$ for a continuous one, when the sum or integral converges absolutely. Expectation is linear, $E[aX + bY + c] = aE[X] + bE[Y] + c$, whether or not $X$ and $Y$ are independent. With $\mu_X = E[X]$ and $\mu_Y = E[Y]$, and finite second moments, the variance $\sigma_X^2 = \operatorname{Var}(X)$ and the covariance $\sigma_{XY} = \operatorname{Cov}(X, Y)$ are

Variance is in squared units and $\operatorname{Var}(aX + c) = a^2\operatorname{Var}(X)$. Covariance depends on the units, while the correlation $\operatorname{Cov}(X, Y)/\sqrt{\operatorname{Var}(X)\operatorname{Var}(Y)}$, defined when both variances are positive, has no units and lies in $[-1, 1]$. Zero covariance does not imply independence. If $X$ is $-1$, 0 or 1 with equal probabilities and $Y = X^2$, then $\operatorname{Cov}(X, Y) = E[X^3] - E[X]E[X^2] = 0$, although $Y$ is a function of $X$.

The covariance matrix of a random vector $\mathbf{x}$ with mean $\boldsymbol{\mu}$ is $\Sigma = E[(\mathbf{x} - \boldsymbol{\mu})(\mathbf{x} - \boldsymbol{\mu})^{\top}]$. It is symmetric and positive semidefinite, with the variances on its diagonal. The conditional expectation $E[Y \mid X = x]$ is the mean of $Y$ among cases with $X = x$, and the law of total expectation says $E\big[E[Y \mid X]\big] = E[Y]$. When $E[Y^2]$ is finite, the function of $x$ with the smallest expected squared error for predicting $Y$ is $E[Y \mid X = x]$. Expectations belong to a distribution, while averages over a sample estimate them.

Lessons Expectation, Variance, and Covariance

Sampling, estimation and uncertainty

An estimator is a rule that turns a sample into an estimate of a parameter, and its sampling distribution describes how the estimate varies over repeated samples. Observations are independent and identically distributed, or iid, when they are independent draws from one distribution, and independence and identical distribution are separate conditions. For iid observations with mean $\mu$ and finite variance $\sigma^2$, the sample mean satisfies

and the standard error is estimated by $s/\sqrt{n}$, where $s^2 = \frac{1}{n - 1}\sum_{i}(x_i - \bar{x})^2$. The law of large numbers says that $\bar{X}$ converges to $\mu$ as $n$ grows, for iid observations with a finite mean, and it gives no guarantee for a particular finite $n$.

An approximate 95 percent confidence interval for $\mu$ is $\bar{x} \pm 1.96\,s/\sqrt{n}$, justified for large $n$ by the central limit theorem. It is only approximate in general, and for independent normal observations the interval with the Student $t$ quantile for $n - 1$ degrees of freedom in place of $1.96$ is exact. With $s = 12$ and $n = 36$ the estimated standard error is 2 and the interval is $\bar{x} \pm 3.92$. Coverage describes the procedure, so about 95 percent of the intervals from repeated samples contain $\mu$, while one computed interval either contains $\mu$ or does not. Selection bias arises when the sampled units differ systematically from the target population, and a larger sample from the same process does not remove it.

Lessons Sampling, Estimation, and Statistical Uncertainty

Regression, Loss, and Regularization

Regression predicts a number. A loss measures one error, the empirical risk averages it over the training data, and the population risk is the quantity that matters for new cases. Least squares fits linear models, features and penalties change what they can express, and regression metrics compare models on the same held-out cases against simple baselines.

Loss functions and empirical risk

A loss function $L(y, \hat{y})$ scores a single prediction. The common regression losses are the squared error $(y - \hat{y})^2$ and the absolute error $\lvert y - \hat{y} \rvert$. Training minimizes a training objective, the empirical risk plus any penalty, possibly with sample weights, while the evaluation metric reported on held-out data can be a different quantity.

The choice of loss decides what is being predicted. Among constant predictions $c$, the expected squared error $E[(Y - c)^2]$ is smallest at $c = E[Y]$ when $E[Y^2]$ is finite, and the expected absolute error $E\lvert Y - c \rvert$ is smallest at any median of $Y$ when $E\lvert Y \rvert$ is finite. Given the features, squared loss therefore targets the conditional mean $E[Y \mid \mathbf{x}]$ and absolute loss a conditional median. For residuals 1, $-1$ and 4, the mean squared error is 6 and the mean absolute error is 2, and under squared error the residual 4 contributes 16 of the total 18. Neither loss is better in general, since they answer different questions.

Lessons Loss Functions and Empirical Risk

Simple linear regression

For pairs $(x_i, y_i)$ with at least two distinct $x$ values, least squares minimizes $\sum_i (y_i - b - wx_i)^2$ and gives

The fitted value is $\hat{y}_i = b + wx_i$, and the residual is $r_i = \hat{y}_i - y_i$, prediction minus target in the course convention, while some texts use the opposite sign. The residuals satisfy $\sum_i r_i = 0$ and $\sum_i x_ir_i = 0$, and the line passes through $(\bar{x}, \bar{y})$. The slope is the difference in fitted value per unit of $x$, in target units per feature unit. Computing the fit needs no assumption of normal errors, which matter only for classical intervals and tests.

The points $(0, 1)$, $(1, 2)$ and $(2, 2)$ give $\bar{x} = 1$, $\bar{y} = 5/3$, $w = 1/2$ and $b = 7/6$, with residuals $1/6$, $-1/3$ and $1/6$. Extrapolation beyond the observed range of $x$ assumes that the line continues there, which the data cannot check, and the slope describes an association in the data, not the effect of changing $x$.

Lessons Simple Linear Regression

Multiple linear regression and least squares

With the augmented design matrix $\tilde{X} = [\mathbf{1} \; X]$ of size $n \times (p + 1)$ and $\boldsymbol{\theta} = (b, \mathbf{w})$, least squares minimizes $\lVert \mathbf{y} - \tilde{X}\boldsymbol{\theta} \rVert_2^2$, and every minimizer solves the normal equations

When $\tilde{X}$ has full column rank, which needs $n \ge p + 1$, the matrix $\tilde{X}^{\top}\tilde{X}$ is invertible and the solution $\hat{\boldsymbol{\theta}} = (\tilde{X}^{\top}\tilde{X})^{-1}\tilde{X}^{\top}\mathbf{y}$ is unique. Without full column rank infinitely many coefficient vectors fit equally well, yet they all give the same fitted vector $\hat{\mathbf{y}} = \tilde{X}\hat{\boldsymbol{\theta}}$, the orthogonal projection of $\mathbf{y}$ onto the column space of $\tilde{X}$. The residual vector $\hat{\mathbf{y}} - \mathbf{y}$ is orthogonal to every column of $\tilde{X}$.

A coefficient $w_j$ is a partial effect, the difference in prediction for a one-unit difference in $x_j$ with the other features held fixed. It is an association within this model and can change, even in sign, when features are added or removed. For computation, a QR decomposition $\tilde{X} = QR$, with orthonormal columns in $Q$ and an upper triangular $R$, turns the problem into $R\boldsymbol{\theta} = Q^{\top}\mathbf{y}$, solved by back substitution when $\tilde{X}$ has full column rank. The SVD also handles the rank-deficient case. Forming $(\tilde{X}^{\top}\tilde{X})^{-1}$ explicitly squares the condition number and loses accuracy.

Lessons Multiple Linear Regression and Least Squares

Stochastic gradient descent and mini-batches

Full-batch gradient descent uses the gradient of the empirical risk over all $n$ examples at every step. Stochastic gradient descent replaces it with the average gradient over a mini-batch $B$ of examples,

where $L_i$ is the loss on example $i$. When the batch is drawn uniformly at random, this stochastic gradient is an unbiased estimate of the full gradient. An epoch is one pass through the training data, about $n/\lvert B \rvert$ updates. A learning-rate schedule lowers $\eta$ over time. With a fixed $\eta$ the iterates keep fluctuating near a minimum, and the classical convergence results for convex objectives use steps with $\sum_t \eta_t = \infty$ and $\sum_t \eta_t^2 < \infty$.

Standardize the features with training statistics first, since very different feature scales make one fixed step too large in some directions and too small in others, and handle any feature with zero training variance by a stated convention. A fixed random seed makes a run repeatable on one setup. The run-to-run variation of the optimizer belongs to the training procedure and is a different thing from statistical uncertainty about the predictions.

Lessons Stochastic Gradient Descent and Mini-Batches

Polynomial features, interactions and splines

Feature engineering builds new columns from the raw inputs. A model is linear in parameters when its prediction is a weighted sum of fixed basis functions $\phi_k$,

so least squares and the penalized methods still apply, even when $\hat{y}$ is a curved function of $\mathbf{x}$. Polynomial features $x, x^2, \dots, x^d$ give curves, an interaction term $x_1x_2$ lets the effect of one feature depend on another, and indicator variables code categories, with $K - 1$ indicators for $K$ levels next to an intercept. A spline is a piecewise polynomial joined smoothly at chosen knots, built from local basis functions such as $\max(0, x - \kappa)$ for a knot $\kappa$.

In $\hat{y} = 10 + 2x_1 + 3x_2 - x_1x_2$, a one-unit step in $x_1$ changes $\hat{y}$ by $2 - x_2$, so the effect of $x_1$ is positive for $x_2 < 2$ and negative for $x_2 > 2$. High-degree polynomials swing wildly outside the training range, so scale the input, choose the degree on validation data and do not extrapolate. Every learned expansion, such as the category list or the knot positions, is fitted on the training data.

Lessons Polynomial Features and Interactions

Ridge, lasso and elastic net

With features standardized on the training data, residuals $r_i = b + \mathbf{w}^{\top}\mathbf{x}_i - y_i$ and an unpenalized intercept $b$, the course writes the penalized least-squares objectives as

with regularization strength $\lambda \ge 0$ and mixing weight $\alpha \in [0, 1]$. At $\lambda = 0$ all three are least squares. Ridge shrinks the coefficients smoothly toward zero and has a unique solution for every $\lambda > 0$. With the centered and standardized matrix $Z$ and the centered target $\mathbf{y}_c$, it is

and $b$ is the training mean of the target. Lasso can set coefficients exactly to zero and so also selects features. Its penalty is not differentiable at zero, so it is solved by coordinate descent with soft thresholding, or another method that handles the corner, rather than by plain gradient descent.

For a single standardized feature whose average square is 1, let $c$ be its average product with the centered target. The three solutions are

where the soft-thresholding function is $S_t(c) = \operatorname{sign}(c)\max(\lvert c \rvert - t, 0)$. For $c = 0.7$ and $\lambda = 0.5$ they are about $0.467$, $0.2$ and, with $\alpha = 0.5$, $0.36$. The regularization path plots the fitted coefficients against $\lambda$. Choose $\lambda$ and $\alpha$ on validation data or by cross-validation, never on the test set. With strongly correlated features lasso may keep one and drop another almost arbitrarily, so a zero coefficient is not evidence that a feature is unrelated to the target. Software packages scale these objectives differently, so the same printed $\lambda$ can mean different fits.

Lessons Ridge, Lasso, and Elastic Net

Regression metrics and baselines

For $m$ evaluated predictions with errors $e_i = \hat{y}_i - y_i$, prediction minus target,

where $\bar{y}$ is the mean of the evaluation targets. The MAE and RMSE are in target units and the MSE in squared units. The value $R^2$ is undefined when all evaluation targets are equal. Otherwise it is 1 for perfect predictions, 0 when every prediction equals $\bar{y}$, and negative for predictions worse than that, which can happen on held-out data. The mean absolute percentage error, $\operatorname{MAPE} = \frac{100}{m}\sum_i \lvert e_i \rvert/\lvert y_i \rvert$ in percent, needs every $y_i \ne 0$ and becomes huge near zero targets.

Targets 2, 4, 6 and 8 with predictions 3, 4, 5 and 12 have errors 1, 0, $-1$ and 4, so the MAE is $1.5$, the MSE is $4.5$, the RMSE is about $2.121$, $R^2 = 1 - 18/20 = 0.1$ and the MAPE is about $29.2$ percent. Compare models on the same held-out cases. The mean baseline predicts the training mean of the target, the best constant for squared error on the training data, and the median baseline predicts the training median, the best constant for absolute error. Any constant prediction has $R^2 \le 0$ on the evaluation data, with equality only when the constant equals $\bar{y}$, so a mean baseline fitted on training data usually has a negative $R^2$ on test data.

Lessons Regression Metrics and Baseline Comparisons

Huber loss and quantile prediction

Robust regression limits the pull of large errors. With $u = y - \hat{y}$, the target minus the prediction,

Huber loss is quadratic near zero and linear in the tails, with its slope capped at $\pm\delta$, so one large error pulls with bounded force. The threshold $\delta$ is in target units. In a regression the gradient also multiplies by the features, so an example with an extreme feature value can still move the fit a lot, and Huber loss offers no protection against high-leverage points. With $\delta = 2$, an error of size 1 costs $0.5$ and an error of size 6 costs 10.

The pinball loss penalizes underprediction with slope $\tau$ and overprediction with slope $1 - \tau$, so at $\tau = 0.9$ underpredicting by 10 costs 9 and overpredicting by 10 costs 1. When $E\lvert Y \rvert$ is finite its expected value is minimized by a $\tau$ quantile of $Y$, so quantile regression, which fits $q_{\tau}(\mathbf{x}) = b + \mathbf{w}^{\top}\mathbf{x}$ by minimizing the average pinball loss, estimates a conditional quantile. It expresses an asymmetric cost, and two fitted quantiles are not automatically a calibrated prediction interval.

Lessons Robust Regression and Quantile Prediction

Classification, Probabilities, and Decisions

Classification predicts a category, often through a probability. Logistic regression and softmax turn scores into probabilities fitted by maximum likelihood, a threshold turns a probability into a decision, and the confusion matrix and its rates count the consequences. Ranking quality, threshold performance and calibration are separate properties, and each needs its own check.

Logistic regression

Binary classification predicts a label $y \in \{0, 1\}$. Logistic regression models $p(\mathbf{x}) = P(Y = 1 \mid \mathbf{x})$ as

The sigmoid maps every real score into $(0, 1)$, and its inverse is the log-odds,

where $p/(1 - p)$ is the odds. A one-unit increase in $x_j$ with the other features fixed adds $w_j$ to the log-odds and multiplies the odds by the odds ratio $e^{w_j}$, while the change in probability is not constant and is largest near $p = 0.5$. The decision boundary $\mathbf{w}^{\top}\mathbf{x} + b = 0$ is the hyperplane where $p = 0.5$, and other thresholds give parallel hyperplanes. With $b = -3$ and $w = 0.5$ per kilometer, $p = \sigma(0) = 0.5$ at 6 kilometers and $p = \sigma(2) \approx 0.881$ at 10 kilometers, and each kilometer multiplies the odds by $e^{0.5} \approx 1.65$. The coefficients describe associations in units of the features, and the probabilities are not calibrated just because they lie between 0 and 1.

Lessons Logistic Regression

Likelihood and cross-entropy

If the labels are conditionally independent given their features, and $p_i$ is the model probability that $y_i = 1$, the Bernoulli likelihood of the parameters is

It is a function of $\boldsymbol{\theta}$ for the observed data, not a probability distribution over $\boldsymbol{\theta}$. Maximum likelihood estimation maximizes it, which is the same as minimizing the negative log likelihood, and dividing that by $n$ gives the binary cross-entropy $J(\boldsymbol{\theta}) = \frac{1}{n}\sum_{i=1}^{n}\ell_i$, the average of the per-example losses

For logistic regression the gradient is $\nabla_{\mathbf{w}}J = \frac{1}{n}X^{\top}(\mathbf{p} - \mathbf{y})$, and $\partial J/\partial b$ is the mean of $p_i - y_i$. The objective is convex in $(\mathbf{w}, b)$, and it has no finite minimizer when a hyperplane separates the two classes perfectly. Compute $\log(1 + e^{z})$ in a numerically stable form instead of exponentiating large scores. For labels 1, 0 and 1 with probabilities $0.8$, $0.2$ and $0.8$, the likelihood is $0.8^3 = 0.512$ and the cross-entropy is $-\log 0.8 \approx 0.223$, while a positive case given probability $0.02$ alone costs $-\log 0.02 \approx 3.91$.

Maximum a posteriori estimation maximizes likelihood times a prior distribution on the parameters. With the mean cross-entropy and the penalty $\tfrac{\lambda}{2}\lVert \mathbf{w} \rVert_2^2$, independent $N(0, s^2)$ priors on the weights correspond to $\lambda = 1/(ns^2)$, and independent Laplace priors with scale $a$ give the penalty $\lambda\lVert \mathbf{w} \rVert_1$ with $\lambda = 1/(na)$. For $n = 4$ and $s^2 = 2$ this gives $\lambda = 1/8$. A MAP estimate is the posterior mode, a single point that describes no uncertainty, and the prior is an assumption.

Lessons Maximum Likelihood and Cross-Entropy

Multiclass classification and softmax

Multiclass classification gives each example exactly one of $K$ classes, while multilabel classification allows several labels at once and usually uses one sigmoid per label. For scores $z_1, \dots, z_K$ the softmax function gives the class probability vector

whose entries are positive and add to 1. Adding the same constant to every score leaves it unchanged, so implementations subtract $M = \max_j z_j$ first, and the log-sum-exp trick computes $\log\sum_j e^{z_j} = M + \log\sum_j e^{z_j - M}$. For the true class $y$ the multiclass cross-entropy is

Scores 2, 1 and 0 give probabilities of about $0.665$, $0.245$ and $0.090$, and a loss of about $0.408$ when the first class is correct. One-vs-rest fits $K$ binary classifiers, each separating one class from all others, and predicts the class with the largest score. Their probabilities need not add to 1, unlike multinomial logistic regression, which applies the softmax to $K$ linear scores.

Lessons Multiclass Classification and Softmax

Confusion matrices and decision thresholds

The positive class is the outcome the decision is about, and it is named before anything is counted. A decision threshold $t$ turns a score into a decision, positive when the score is at least $t$.

Sensitivity is the true positive rate, also called recall, and the false positive rate is $1 - \text{specificity} = \text{FP}/(\text{FP} + \text{TN})$. Each ratio is undefined when its denominator is 0. Raising $t$ moves cases from predicted positive to predicted negative, so sensitivity can only fall or stay the same while specificity can only rise or stay the same.

Suppose a false positive costs $c_{\text{FP}}$, a false negative costs $c_{\text{FN}}$ and correct decisions cost nothing. If $p = P(Y = 1 \mid \mathbf{x})$ is a calibrated probability, predicting positive has expected cost $(1 - p)c_{\text{FP}}$ and predicting negative has $p\,c_{\text{FN}}$, so the expected cost is smallest when the rule predicts positive for

With $c_{\text{FN}} = 5$ and $c_{\text{FP}} = 1$ the threshold is $1/6$, not $0.5$. On a set of cases the total cost of a threshold is $c_{\text{FP}}\,\text{FP} + c_{\text{FN}}\,\text{FN}$, and a threshold chosen for accuracy alone ignores these costs.

Lessons Confusion Matrices and Decision Thresholds

Precision, recall, ROC and precision-recall curves

The main threshold metrics are

and accuracy, the share of all cases classified correctly. Precision is undefined when nothing is predicted positive, and $F_1$ is undefined only when $\text{TP} + \text{FP} + \text{FN} = 0$. When precision $P$ and recall $R$ are both positive, $F_1 = 2PR/(P + R)$ is their harmonic mean. It ignores true negatives and the costs of errors, and replacing an undefined value by 0 is a reporting choice that should be stated.

The ROC curve plots the true positive rate against the false positive rate as the threshold moves from above the highest score to below the lowest, with tied scores entering together. ROC AUC, the area under this curve with straight segments, equals the probability that a randomly chosen positive scores above a randomly chosen negative, with ties counted one half. For $n_+$ positives with scores $s_i$ and $n_-$ negatives with scores $s_j$,

where $c_{ij}$ is 1, $1/2$ or 0 as positive $i$ scores above, equal to or below negative $j$. A constant score has AUC $0.5$, both classes must be present, and any strictly increasing change of the scores leaves AUC unchanged, so it measures ranking and says nothing about calibration or about a particular threshold. Positive scores $0.8$ and $0.5$ against negative scores $0.5$ and $0.2$ earn $1 + 1 + 0.5 + 1 = 3.5$ of 4 pairs, so AUC $= 0.875$.

The precision-recall curve plots precision against recall over the thresholds. Average precision, in the noninterpolated form used in the course, is

over the distinct thresholds in decreasing order, with recall $R_k$, precision $P_k$ and $R_0 = 0$. A ranking that ignores the features has precision near the prevalence at every threshold, so AP is read against that level. With two positives among ten cases ranked first and fifth, $\text{AP} = 0.5 \cdot 1 + 0.5 \cdot 0.4 = 0.7$, while ROC AUC is $13/16 \approx 0.81$. The two summaries reward different parts of the ranking.

Lessons Precision, Recall, and Classification Metrics

Imbalanced classes and cost-sensitive learning

Class imbalance means one class is much rarer than the other, and the prevalence $\pi$ is the share of positives. Accuracy can look excellent for a useless rule, since always predicting negative is right for a share $1 - \pi$ of the cases. Precision depends on prevalence. For a fixed true positive rate $t$ and false positive rate $f$,

so at $t = 0.8$, $f = 0.1$ and $\pi = 0.01$ precision is only about $0.075$. As another example, 12 true positives, 8 false negatives, 40 false positives and 940 true negatives give accuracy $0.952$, below the $0.98$ of always predicting negative, while recall is $0.6$, specificity about $0.959$ and precision about $0.231$.

Balanced accuracy is the mean of sensitivity and specificity, about $0.780$ in this example and $0.5$ for the rule that always predicts negative. A macro average computes a metric for each class and averages the results with equal weights, while a micro average pools the counts of all classes first. In single-label multiclass problems micro precision, micro recall and micro $F_1$ all equal accuracy.

Class weights multiply each example’s loss by a weight that depends on its class, and cost-sensitive learning chooses the weights or the threshold from the costs of errors. Resampling repeats minority rows or drops majority rows, and SMOTE creates a synthetic minority point $\mathbf{x}_i + u(\mathbf{x}_{\text{nn}} - \mathbf{x}_i)$ between a minority example and one of its minority neighbors, with $u$ uniform on $[0, 1]$. Synthetic points are not new evidence. Resample only inside training folds, evaluate on data with the real class mix, and remember that weighting or resampling changes the meaning of predicted probabilities. Moving the threshold is often enough, and it leaves the fitted probabilities unchanged.

Lessons Imbalanced Classes and Cost-Sensitive Learning

Probability calibration

A probability model is calibrated when, among cases given probability $p$, the share of positives is $p$, that is $P(Y = 1 \mid \hat{p} = p) = p$ for every $p$. Calibration is separate from discrimination, the ability to rank positives above negatives, and an increasing change of the scores keeps the ranking and AUC while it can change calibration. A reliability diagram groups the predictions into bins and plots the mean predicted probability against the observed share of positives in each bin. Points near the diagonal suggest calibration in those bins, up to sampling noise that is large for small bins.

For $m$ cases the Brier score is $\frac{1}{m}\sum_{i}(p_i - y_i)^2$, and the log loss is the binary cross-entropy of the held-out predictions. Both are proper scoring rules that reward calibration and discrimination together, so a better score alone does not show better calibration. Ten cases all given $0.6$, of which 4 are positive, sit at the point $(0.6, 0.4)$ of the diagram and have Brier score $0.28$ and log loss about $0.754$.

Platt scaling fits $p = \sigma(as + c)$ to a score $s$ by maximum likelihood, and isotonic regression fits a nondecreasing step function by least squares. Fit the calibrator on a calibration set that was not used to train the model, or on out-of-fold predictions, and check the result on separate evaluation data. Moving the decision threshold changes the decisions, not the calibration.

Lessons Probability Calibration

Naive Bayes classification

A generative classifier models the class prior $P(c) = P(Y = c)$ and the class-conditional distribution of the features, then classifies with Bayes’ rule. The naive Bayes assumption is that the features are conditionally independent given the class, $P(\mathbf{x} \mid c) = \prod_{j} P(x_j \mid c)$, so the classifier picks the class with the largest log-probability score