The whole Machine Learning formula sheet, to print

Average squared residual; the sum of squared errors (SSE) is the same without the factor $1/n$. Minimising either gives the same $\mathbf{w}$.

Needs at least two distinct $x$ values ($S_{xx}>0$). The fitted line always passes through $(\bar{x},\bar{y})$.

The two forms agree for least squares with an intercept on the training data, where SST = SSR + SSE; then $0\le R^2\le 1$ (assuming SST $>0$). For simple regression $R^2=r^2={\hat{\beta }}_1^2{S}_{xx}/S_{yy}$. On new (test) data, or for a model without an intercept, $1-\text{SSE}/\text{SST}$ can be negative.

The inverse form requires $X^{T}X$ to be invertible, i.e. the columns of $X$ (including the column of ones, if present) are linearly independent. This needs $n$ to be at least the number of columns. If one column is a linear combination of others (exact collinearity, or more columns than samples), $X^{T}X$ is singular: minimisers still exist, but there are infinitely many.

Sum of squared errors plus $\lambda$ times the squared Euclidean norm of the weights. $\lambda =0$ gives OLS. For $\lambda >0$ the objective is strictly convex, so the minimiser is unique. Equivalent constrained form: minimise $\Vert \mathbf{y}-X\mathbf{w}{\Vert }^2$ subject to $\Vert \mathbf{w}{\Vert }^2\le t$, for a $t$ that depends on $\lambda$.

For $\lambda >0$ the matrix $X^{T}X+\lambda I$ is always invertible (positive definite), even when $X^{T}X$ is singular. Here $I$ is the identity of size equal to the number of weights.

$\eta >0$ is the learning rate. The iterates converge from any starting point if $0<\eta <2/{\mu }_{\max }$, where ${\mu }_{\max }$ is the largest eigenvalue of $H=\frac{2}{n}{X}^{T}X$. If $\eta >2/{\mu }_{\max }$ they generally diverge.

The output lies in (0, 1). $\sigma (0)=0.5$; $\sigma (z)\to 1$ as $z\to \infty$ and $\sigma (z)\to 0$ as $z\to -\infty$.

The derivative is at most 0.25, reached at $z=0$. This identity is what makes the gradient of the cross-entropy loss so simple.

Binary classification. The prediction is class 1 when this probability exceeds the chosen threshold, which is 0.5 unless the question states another.

With the other features fixed, each unit increase in $x_j$ adds $w_j$ to the log-odds, which multiplies the odds by $e^{w_j}$.

The boundary is a hyperplane, so logistic regression is a linear classifier. $\mathbf{w}$ is normal to the boundary and points towards the class-1 side. Changing $t$ moves the hyperplane parallel to itself.

Each sample contributes $\ln P(y_i\mid {\mathbf{x}}_i)$. Maximising $\ell$ and minimising $J$ give the same weights.

For one sample the loss is $-\ln p$ if $y=1$ and $-\ln (1-p)$ if $y=0$. Using ${\log }_2$ instead only multiplies the loss by a constant.

This is identical to the cross-entropy above, rewritten for $\pm 1$ labels using $\sigma (-z)=1-\sigma (z)$. Check which label convention a question uses before you substitute.

Labels in $\{0,1\}$. This has the same form as linear regression's gradient when that loss is written $\frac{1}{2n}\sum ({\hat{y}}_i-y_i{)}^2$, with $p_i$ in place of the linear prediction. For a single sample, drop the $\frac{1}{n}$ and the sum.

$\lambda \ge 0$ sets the strength of the penalty. The bias is usually not penalised, so $\partial J_{\lambda }/\partial b$ is unchanged. Books scale $\lambda$ differently (with or without $\frac{1}{n}$ or $\frac{1}{2}$), so use the form the question gives.

$\eta >0$ is the learning rate. With the squared-error loss $\frac{1}{2}(p-y{)}^2$ per sample instead, the gradient picks up an extra factor $p(1-p)$. Learning then slows when the sigmoid saturates, and the loss is no longer convex in $\mathbf{w}$.

Euclidean is $r=2$, Manhattan is $r=1$, and Chebyshev is the limit $r\to \infty$. $d_r$ is a metric for $r\ge 1$. The order is written $r$ here because $p$ means a predicted probability in these notes. The nearest neighbour can change from one metric to another, so always use the one the question names.

$N_k(\mathbf{x})$ is the set of the $k$ nearest training points. A distance-weighted version uses weights proportional to $1/d$. A query that coincides with a training point ($d=0$) is usually given that point's value.

$\bar{x}$ and $s$ are the mean and standard deviation of the feature. Compute $x_{\min }$, $x_{\max }$, $\bar{x}$ and $s$ from the training data, and apply the same values to the query.

This assumes the features are conditionally independent given the class. The denominator is the same for every class, so you need it only when the question asks for an actual probability.

Compare the unnormalised scores. In practice the logs are summed, $\ln P(c)+{\sum }_j\ln P(x_j\mid c)$, to avoid numerical underflow. With equal priors, the rule reduces to picking the class with the largest likelihood (maximum likelihood).

$N_c$ is the number of training samples in class $c$, and $N_{j,v,c}$ is how many of them have feature $j$ equal to $v$. These are maximum-likelihood estimates and can be zero. Priors are smoothed only if the question says so.

$V_j$ is the number of distinct values feature $j$ can take (2 for a binary feature). $\alpha =1$ is Laplace smoothing. It stops a single unseen value from forcing the whole product to zero.

Used for text classification. $\mathrm{count}(w,c)$ is the number of times word $w$ appears across the training documents of class $c$, $|V|$ is the vocabulary size, and $n_w$ is how often $w$ occurs in the document being classified.

For continuous features. ${\mu }_{jc}$ and ${\sigma }_{jc}^2$ are the mean and variance of feature $j$ within class $c$ (here ${\sigma }_{jc}$ is a standard deviation, not the sigmoid). The maximum-likelihood variance divides by $N_c$ and the unbiased one by $N_c-1$; use the one the question states. The result is a density, so it can exceed 1. Multiply the terms together as before.

The independence assumption makes the parameter count grow linearly in $d$ instead of exponentially. The $K-1$ term counts the priors, since they sum to 1.

Euclidean distance from ${\mathbf{x}}_0$ to the hyperplane $\mathbf{w}\cdot \mathbf{x}+b=0$, for $\mathbf{w}\ne 0$.

Class means, priors and the pooled within-class covariance, where $n_k$ is the number of samples in class $k$. Dividing by $n$ instead of $n-K$ only rescales $\hat{\Sigma }$. With equal priors the decisions are unchanged. With unequal priors the $\ln {\pi }_k$ term gets a slightly different relative weight, so borderline decisions can change.

Assign $\mathbf{x}$ to the class with the largest ${\delta }_k(\mathbf{x})$; $\ln$ is the natural logarithm. This assumes Gaussian classes with a common $\Sigma$.

This is ${\delta }_1(\mathbf{x})-{\delta }_0(\mathbf{x})>0$. The boundary is a hyperplane with normal vector ${\Sigma }^{-1}({\mathbf{\mu }}_1-{\mathbf{\mu }}_0)$. It passes through the midpoint of the means when ${\pi }_0={\pi }_1$. Unequal priors shift it away from the more probable class.

Here $m_k={\mathbf{w}}^T{\mathbf{\mu }}_k$ are the projected means and $s_k^2={\sum }_{i\in k}({\mathbf{w}}^T{\mathbf{x}}_i-m_k{)}^2$ the projected scatters. Maximise over $\mathbf{w}$. $J$ depends only on the direction of $\mathbf{w}$, not on its length.

The same direction as the two-class LDA weight vector, because $S_W=(n-2)\hat{\Sigma }$ is proportional to the pooled covariance. $S_W$ must be invertible.

The distance between the hyperplanes $\mathbf{w}\cdot \mathbf{x}+b=\pm 1$. Valid only under the canonical scaling (closest points at $\pm 1$). The bias $b$ does not affect it.

Requires linearly separable data. Maximising $2/\Vert \mathbf{w}\Vert$ is the same as minimising $\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$.

Only points with ${\alpha }_i>0$ contribute to $\mathbf{w}$; these are the support vectors. By complementary slackness, ${\alpha }_i[y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)-1]=0$, so every support vector lies exactly on $y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b)=1$.

In the dual, the only change from the hard margin is the box constraint $0\le {\alpha }_i\le C$.

At the optimum ${\xi }_i=\max (0,1-y_i(\mathbf{w}\cdot {\mathbf{x}}_i+b))$, which turns the constrained problem into this unconstrained one.

Polynomial kernel: degree $p$ a positive integer and $c\ge 0$. RBF (Gaussian) kernel: $\gamma >0$, often written $\gamma =1/(2{\sigma }^2)$. RBF values lie in $(0,1]$ and equal 1 only when $\mathbf{x}=\mathbf{z}$.

Only the support vectors (${\alpha }_i>0$) contribute to the sum.

$p_k$ is the fraction of class $k$ in node $S$. Entropy ranges from $0$ (a pure node) to ${\log }_{2}K$ (all classes equally likely), which is $1$ bit for two balanced classes.

Ranges from $0$ (pure) to $1-1/K$ (equal classes), which is $0.5$ for two balanced classes. For two classes with proportions $p,1-p$: $G=2p(1-p)$.

Ranges from $0$ to $1-1/K$. For two classes, $E=\min (p,1-p)$. Entropy and Gini respond more strongly to changes in node purity, so they are the usual criteria for growing a tree.

$S_v$ is the subset sent to child $v$ by the test $A$. The same weighted-average pattern with $G$ in place of $H$ gives the Gini reduction. Choose the split with the largest gain.

Divides the gain by the entropy (in bits) of the split proportions themselves. This penalises tests that break the node into many small branches.

Systematic error: how far the average prediction over training sets is from the truth.

Sensitivity: how much the prediction changes from one training set to another.

Valid for squared-error loss, with zero-mean noise in the test response that is independent of the training data. The term ${\sigma }^2$ is irreducible: no model can remove it.

Convention: $X$ is $n\times p$ with samples in its rows, $\mathbf{y}$ holds the $n$ responses, and $\mathbf{w}$ the weights. The bias (intercept) $b$ is not penalised: $\mathbf{y}$ and each column of $X$ are centred first, so $b$ drops out and is recovered afterwards. For $\lambda >0$, $X^{\top }X+\lambda I$ is always invertible. $\lambda =0$ gives ordinary least squares (when $X^{\top }X$ is invertible), the lowest-bias and highest-variance member of the ridge family. $\lambda \to \infty$ drives $\hat{\mathbf{w}}\to 0$ (high bias, low variance). The penalty depends on the scale of each feature, so features are usually standardised first.

Holds when the training inputs are fixed and $y_i=f(x_i)+{\epsilon }_i$ with independent zero-mean noise of variance ${\sigma }^2$. Here $x_{(1)},\dots ,x_{(k)}$ are the $k$ training inputs nearest to $x_0$, and ${\hat{f}}_k(x_0)$ is the average of their $y$ values. The middle term is bias squared, which usually grows with $k$ as farther neighbours are averaged in. The variance ${\sigma }^2/k$ falls as $k$ grows.

$n_i$ is the number of samples in fold $i$, and ${\hat{y}}_j$ is the prediction of the model trained without fold $i$. For classification, $E_i$ is the misclassification rate on fold $i$.

Assumes equal-sized folds. With unequal folds, use ${\sum }_{i=1}^k(n_i/n)E_i$. Number of models trained: $k$, each on about $n(k-1)/k$ samples.

LOO is $k$-fold with $k=n$. $\ell$ is the loss, and ${\hat{f}}^{(-i)}$ is trained on every sample except the $i$-th, so $n$ models are trained, each on $n-1$ samples.

Valid only for linear least squares with squared error, fitted once on all the data. ${\hat{y}}_i$ is the full-data fit. $h_{ii}={\mathbf{x}}_i^{\top }(X^{\top }X{)}^{-1}{\mathbf{x}}_i$ is the $i$-th diagonal entry of the hat matrix $H=X(X^{\top }X{)}^{-1}{X}^{\top }$, with samples in the rows of $X$. It requires $X^{\top }X$ to be invertible and $h_{ii}<1$. If an intercept is fitted, $X$ includes a column of ones. No refitting is needed.

With several hyperparameters, the number of candidate settings is the product of the grid sizes. The $+1$ is the refit on all the data. Leave it out if the question asks only about the search.

Misleading when the classes are very unbalanced.

Of everything predicted positive, the fraction that is truly positive. Undefined if nothing is predicted positive.

Of everything truly positive, the fraction found.

Specificity is the fraction of true negatives correctly identified.

The harmonic mean of precision $P$ and recall $R$. TN does not appear in it.

Targets are 0 or 1. The tie z = 0 is assigned to class 1 here. A question may use the opposite tie rule or targets of -1 and +1, so read the convention given.

Applied sample by sample, where t is the target. If the sample is classified correctly, t - y is 0 and nothing changes. A missed class-1 sample pulls w towards x, and a missed class-0 sample pushes w away from x.

W(l) has one row per unit of layer l and one column per unit of layer l-1. f is applied element-wise, except softmax, which acts on the whole vector.

n_l is the number of units in layer l. The network total is the sum over all layers after the input. The first term counts weights, the second counts biases.

Write the derivative in terms of the output y = sigma(z), so backpropagation needs no recomputation. Also 1 - sigma(z) = sigma(-z).

Valid for all real z.

K output units. Outputs are positive and sum to 1. Adding the same constant to every z_i leaves p unchanged.

Only the difference of the two logits matters, which is why one sigmoid unit is enough for binary classification.

The factor 1/2 is a convention that cancels the 2 on differentiation. If a question defines L without it, the gradient is doubled.

t is 0 or 1 and y = sigmoid(z). The gradient with respect to the output unit's net input z simplifies to y - t.

t is a one-hot vector. With true class c, the loss is -ln p_c.

theta is any weight or bias. All gradients are computed at the old parameter values, and then all parameters are updated together.

Squared-error loss with factor 1/2, output activation f applied element-wise. For a single output unit this is (y - t) f'(z). For sigmoid output, f' = y(1 - y); for linear output, f' = 1. With cross-entropy and sigmoid or softmax, delta = y - t directly.

The symbol is the element-wise product. The error of a hidden unit is the weighted sum of the errors of the units it feeds, times its own activation slope. Use the weights as they were before this step's update.

For a single weight: dL/dw = delta of the receiving unit times the output of the sending unit.

Default distance. k-means is built around its square.

Sum of absolute coordinate differences. For (1,1) and (4,5): Manhattan = 3 + 4 = 7, Euclidean = 5.

Squared Euclidean distance of each point to its own cluster's centroid, summed over all points.

Nearest centroid in Euclidean distance (squaring does not change which centroid is nearest). Ties need a fixed rule: keep the point in its current cluster if that cluster is among the nearest, otherwise take the lowest index.

Defined for a non-empty cluster. The mean is the point that minimises the sum of squared Euclidean distances to the cluster's points, so this step cannot increase $J$.

The double sum runs over all ordered pairs (each unordered pair counted twice). Useful when only distances are given. Check: for {1, 2, 4} the right side is 28/6 = 4.667, the same as the left.

$a(i)$ = mean distance from point $i$ to the other points of its own cluster; $b(i)$ = the smallest, over the other clusters, of the mean distance from $i$ to that cluster's points. $-1\le s(i)\le 1$: near 1 means well placed, negative means $i$ is on average closer to another cluster. By convention $s(i)=0$ if $i$ is alone in its cluster. A higher average $s(i)$ over all points indicates a better $K$.

The member of the cluster with the smallest total dissimilarity to the other members. k-medoids minimises ${\sum }_k{\sum }_{\mathbf{x}\in C_k}d(\mathbf{x},{\mathbf{m}}_k)$.

Closest pair across the two clusters. Prone to chaining: a line of nearby points joins distant groups into one long cluster.

Farthest pair across the two clusters. Favours compact clusters of similar diameter.

Mean of all cross-cluster pairwise distances. For the same pair of clusters it lies between the single-linkage and complete-linkage values.

The increase in total WCSS caused by merging $A$ and $B$; it merges the pair that increases the WCSS least. Needs Euclidean coordinates (centroids). Software scales the reported height differently, but the order of merges is the same.

Distance between the cluster means. Needs Euclidean coordinates, and it can give inversions (a later merge lower than an earlier one).

Weight the two old distances by cluster size. The plain average of $D(A,C)$ and $D(B,C)$ is wrong unless $|A|=|B|$.

Centre each feature (column) to mean zero. $X_c$ denotes the centred matrix, whose rows are $({\mathbf{x}}_i^c{)}^{\top }$.

Symmetric and positive semi-definite. Diagonal entries are feature variances; off-diagonal entries are covariances. Some texts divide by $n$ instead. The eigenvectors and the proportions of variance do not change; every eigenvalue is scaled by the same factor.

The eigenvectors of the symmetric matrix $S$ are chosen orthonormal. ${\mathbf{v}}_j$ is the $j$-th principal direction (component). A direction is fixed only up to sign.

$V=[{\mathbf{v}}_1\cdots {\mathbf{v}}_d]$ is orthogonal and $\Lambda =\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_d)$. The scores $Z=X_c{V}_k$ (defined below) have the diagonal covariance ${\Lambda }_k=\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_k)$.

Projections onto different components are uncorrelated: ${\mathbf{v}}_i^{\top }S{\mathbf{v}}_j=0$ for $i\ne j$.

The largest possible projected variance is ${\lambda }_1$, reached at ${\mathbf{v}}_1$. The smallest is ${\lambda }_d$, reached at ${\mathbf{v}}_d$.

Total variance is unchanged by rotating to the principal axes. For standardised data it equals $d$.

Choose the smallest $k$ whose cumulative proportion reaches a stated target, such as 90 percent.

$V_k=[{\mathbf{v}}_1\cdots {\mathbf{v}}_k]$ has orthonormal columns. The coordinate along ${\mathbf{v}}_j$ is $z_{ij}={\mathbf{v}}_j^{\top }({\mathbf{x}}_i-\bar{\mathbf{x}})$.

The ${\lambda }_j$ are eigenvalues of $S$ with divisor $n-1$. With divisor $n$, the mean squared error $\frac{1}{n}{\sum }_i\Vert {\mathbf{x}}_i-{\hat{\mathbf{x}}}_i{\Vert }^2$ equals the sum of the discarded eigenvalues exactly. Among all $k$-dimensional affine subspaces (all rank-$k$ linear reconstructions of the centred data), projecting onto the top $k$ components gives the smallest total squared reconstruction error. Maximising the retained variance and minimising the reconstruction error lead to the same components.

The columns of $V$ (right singular vectors) are the principal directions. The ${\sigma }_j$ are the singular values in decreasing order. The ${\lambda }_j$ are eigenvalues of $S$ with divisor $n-1$.

This uses the first $k$ columns of $U$ and $V$ and the top-left $k\times k$ block of $\Sigma$. The best rank-$k$ approximation of $X_c$ is $U_k{\Sigma }_k{V}_k^{\top }$.

The $n\times n$ matrix $X_c{X}_c^{\top }$ has the same non-zero eigenvalues ${\sigma }_j^2$ as $X_c^{\top }{X}_c$. When $d>n$ it is the smaller matrix to decompose.