Skip to content

Formula Sheet and Notation

This appendix collects the notation of the book and the formulas of each unit in one place, for revision. Symbols are used as in the chapters; the section on each formula gives its derivation or its use.

Notation

Almost every mistake in a first ML exam is a notation mistake. Fix these and the formulas below read themselves.

Symbol Means Watch out for
\(m\) number of examples (rows) some books use \(n\) for this
\(n\) number of features (input columns) the target is not one of them
\(x^{(i)}\) the i-th example, a vector of \(n\) numbers superscript \(=\) which example
\(x_{j}\) the j-th feature subscript \(=\) which feature
\(x_{j}^{(i)}\) feature \(j\) of example i one number
\(y, \hat{y}\) true target, predicted target \(\hat{y}\) is always the model's output
\(X\) design matrix, \(m \times (n+1)\) with the \(x_{0} = 1\) column rows are examples
\(\theta\), w, b parameters; \(\theta _{0} = b\) is the intercept / bias learned, never chosen
\(\alpha , \lambda , k, C, \gamma\) hyper-parameters chosen on validation data, never learned
\(h_{\theta }(x)\) the hypothesis — the model as a function \(\hat{y} = h_{\theta }(x)\)
\(J(\theta )\) the cost: loss averaged over the training set a function of \(\theta\), not of \(x\)
\(e_{i}\) residual \(y_{i} - \hat{y}_{i}\) sign matters; it sums to 0 with an intercept
\(\sigma (z)\) the sigmoid \(1/(1+e^{-z})\) also written \(g(z)\)
\(\delta _{j}\) \(\partial L/\partial z_{j}\), the error signal at a unit not the same as the residual
\(\Vert w\Vert\) Euclidean length \(\sqrt{\sum w_{j}^{2}}\) \(\Vert w\Vert ^{2}\) has no square root
\(\mu , \sigma\) mean and standard deviation of a feature \(\sigma\) the statistic, \(\sigma ()\) the sigmoid — different things

Unit 1 — Introduction

Idea Statement
Mitchell's definition A program learns from experience \(E\) at task \(T\) measured by \(P\), if its performance at \(T\) under \(P\) improves with \(E\).
Supervised data is (x, y) pairs; categorical \(y \to\) classification, continuous \(y \to\) regression
Unsupervised data is \(x\) only; clustering, dimensionality reduction
Reinforcement states, actions, delayed reward; explore vs exploit
Underfitting training error high, test error \(\approx\) training error \(\to\) high bias
Overfitting training error low, test error much higher \(\to\) high variance
Generalisation gap test error \(-\) training error
Split train fits \(\theta \cdot\) validation chooses hyper-parameters \(\cdot\) test is opened once
No free lunch averaged over all problems every algorithm is equal; an inductive bias is what makes learning possible at all

Unit 2 — Preprocessing

\[ x' = (x - \min) / (\max - \min) \]

min–max, to [0, 1]; fitted on the training set only

\[ z = (x - \mu ) / \sigma \]

standardisation, to mean 0 and sd 1

\[ x' = (x - \text{median}) / \text{IQR} \]

robust scaling, for heavy tails

Quantity Formula
Population \(\sigma\) \(\sqrt( \sum (x - \mu )^{2} / n\) )
Sample \(s\) \(\sqrt( \sum (x - \mu )^{2} / (n - 1)\) )
IQR \(Q3 - Q1\)
Tukey fences [\(Q1 -\) 1.5·IQR, \(Q3 +\) 1.5·IQR]; 3·IQR marks “far out”
Outlier by \(z\) |z| \(> 3\)
Covariance matrix \(S = (1/(m-1)) X^{T}X\) on centred \(X\)
PCA Su \(= \lambda u\) — components are eigenvectors of \(S\), and each \(\lambda\) is the variance along its own component
Variance explained \(\text{PVE}_{i} = \lambda _{i} / \sum \lambda\); \(\sum \lambda = \text{trace}(S) =\) total variance
One-hot columns \(c\) per categorical feature, or \(c - 1\) dropping one level
  • Scale-sensitive: k-NN, k-means, SVM, PCA, gradient descent, neural networks, ridge, lasso.
  • Scale-indifferent: decision trees, random forests, boosting, the normal equation.
  • Order: split \(\to\) impute \(\to\) encode \(\to\) scale \(\to\) select/reduce \(\to\) balance (train fold only) \(\to\) fit \(\to\) evaluate once.

Unit 3 — Regression

\[ h_{\theta }(x) = \theta _{0} + \theta _{1}x_{1} + \ldots + \theta _{n}x_{n} = \theta ^{T}x \]

with \(x_{0} = 1\)

\[ \theta _{1} = \sum (x - \bar{x})(y - \bar{y}) / \sum (x - \bar{x})^{2} \quad \theta _{0} = \bar{y} - \theta _{1}\bar{x} \]

least squares in one variable; the line passes through \((\bar{x}, \bar{y})\)

\[ J(\theta ) = (1/2m) \sum (h_{\theta }(x^{(i)}) - y^{(i)})^{2} \]

the cost — convex, one minimum

\[ \theta _{j} := \theta _{j} - (\alpha /m) \sum (h(x^{(i)}) - y^{(i)}) x_{j}^{(i)} \]

gradient descent — all \(\theta\) updated simultaneously

\[ \theta = (X^{T}X)^{-1}X^{T}y \]

the normal equation; \(X^{T}X\) is singular iff the columns of \(X\) are dependent

\[ J = \sum (y - \hat{y})^{2} + \lambda \sum \theta _{j}^{2} \cdot J = \sum (y - \hat{y})^{2} + \lambda \sum |\theta _{j}| \]

ridge (L2) and lasso (L1); \(\theta _{0}\) never penalised; standardise first

Metric Formula Units
MSE \((1/m)\sum (y - \hat{y})^{2}\) \(y^{2}\)
RMSE \(\sqrt{\text{MSE}}\) \(y\)
MAE \((1/m)\sum \|y - \hat{y}\|\) \(y\)
\(R^{2}\) \(1 - \text{SS}_{\text{res}}/\text{SS}_{\text{tot}}\), with \(\text{SS}_{\text{tot}} = \sum (y - \bar{y})^{2}\) none
Adjusted \(R^{2}\) \(1 - (1 - R^{2})(m - 1)/(m - n - 1)\) none
MAPE \((100/m)\sum \|(y - \hat{y})/y\|\) %

\(\text{RMSE} \ge \text{MAE}\) always; \(R^{2} = 0\) means no better than predicting \(\bar{y}\); \(R^{2}\) can be negative on a test set; \(R^{2}\) never falls when a feature is added; expected error \(= \text{bias}^{2} + \text{variance} + \text{noise}\).

Unit 4 — Classification

Trees

\[ H(S) = - \sum p_{i} \log_{2} p_{i} \cdot \text{Gini} = 1 - \sum p_{i}^{2} \]

0 when pure; \(H = 1\) bit and Gini \(= 0.5\) at a 50/50 binary node

\[ \text{Gain}(S, A) = H(S) - \sum _{v} (|S_{v}|/|S|) H(S_{v}) \]

information gain; C4.5 divides it by the split's own entropy to get the gain ratio

Naïve Bayes

\[ P(C \mid x) \propto P(C) \Pi _{j} P(x_{j} \mid C) \]

sum logs in practice; predict the class with the largest product

\[ P(x_{j} = v \mid C) = (\text{count} + \alpha ) / (n_{C} + \alpha \cdot V) \]

Laplace smoothing over \(V\) possible values; \(\alpha = 1\) is standard

Logistic regression

\[ h(x) = \sigma (\theta ^{T}x) = 1/(1 + e^{-\theta ^{T}x}) \cdot \sigma '(z) = \sigma (z)(1 - \sigma (z)) \le 0.25 \]

boundary at \(\theta ^{T}x = 0\); log[p/(1−p)] \(= \theta ^{T}x\), so a coefficient is a log-odds

\[ J = -(1/m) \sum [ y \log h + (1 - y) \log(1 - h) ] \cdot \partial J/\partial \theta _{j} = (1/m) \sum (h - y) x_{j} \]

log-loss: convex, unlike squared error on a sigmoid

k-NN, perceptron, networks

\[ w := w + \eta (y - \hat{y})x, b := b + \eta (y - \hat{y}) \]

the perceptron rule — no change when the prediction is right; converges iff the data is linearly separable

\[ \partial L/\partial w_{\text{ij}} = \delta _{j}a_{i}, \delta _{\text{out}} = (\hat{y} - y)f'(z_{\text{out}}), \delta _{j} = (\sum _{k} \delta _{k}w_{\text{jk}})f'(z_{j}) \]

back-propagation: \(\delta\) at the far end \(\times\) activation at the near end

SVM

\[ \text{minimise} \tfrac{1}{2}\Vert w\Vert ^{2} \text{subject} \text{to} y_{i}(w^{T}x_{i} + b) \ge 1 \]

margin width \(2/\Vert w\Vert\); soft margin adds \(C \sum \xi _{i}\), equivalently hinge loss \(\max(0, 1 -\) y·f(x))

\[ \text{geometric} \text{distance} = |w^{T}x + b| / \Vert w\Vert \]

the functional margin \(w^{T}x + b\) depends on scaling; this does not

Kernels: RBF \(K = \exp(-\gamma \Vert x - x'\Vert ^{2})\); polynomial \(K = (x^{T}x' + c)^{d}\). In sklearn, C is the inverse of \(\lambda\).

Metrics

Metric Formula Reads as
Accuracy \((\text{TP} + \text{TN})/n\) everything over everything
Precision \(\text{TP}/(\text{TP} + \text{FP})\) of what I flagged, how much was real
Recall \(/ \text{TPR} /\) sensitivity \(\text{TP}/(\text{TP} + \text{FN})\) of what was real, how much I caught
Specificity \(/ \text{TNR}\) \(\text{TN}/(\text{TN} + \text{FP})\) recall for the negative class
FPR \(\text{FP}/(\text{FP} + \text{TN}) = 1 -\) specificity the x-axis of a ROC curve
F1 2PR/(P \(+ R\)) harmonic mean — sits near the smaller one
AUC area under TPR vs FPR \(P(a \text{random} \text{positive} \text{outranks} a \text{random} \text{negative})\)

\(\text{FN} = a\) miss (type II); \(\text{FP} = a\) false alarm (type I); lowering the threshold raises recall and lowers precision, always; sklearn's confusion matrix is [[TN, FP], [FN, TP]].

Unit 5 — Clustering

\[ d_{p}(a, b) = ( \sum |a_{i} - b_{i}|^{p} )^{1/p} \]

Minkowski: \(p = 1\) Manhattan, \(p = 2\) Euclidean, \(p \to \infty\) Chebyshev; always \(d_{\infty } \le d_{2} \le d_{1}\)

\[ \cos \theta = a\cdot b / (\Vert a\Vert \Vert b\Vert ) \]

cosine similarity — direction only, ignores length; the right choice for text

\[ \text{WCSS} = \sum _{j} \sum _{x \in C_{j}} \Vert x - \mu _{j}\Vert ^{2} \]

what k-means minimises; sklearn calls it inertia_

\[ s = (b - a) / \max(a, b) \]

silhouette: \(a =\) mean distance within its own cluster, \(b =\) to the nearest other cluster

Linkage Distance between clusters Character
Single min over pairs long curved shapes; chains through noise
Complete max over pairs compact, equal-diameter; outlier-sensitive
Average mean over pairs the usual default
Ward the merge raising WCSS least spherical, similar sizes

k-means: assign \(\to\) update \(\to\) repeat; the centroid is the mean because the mean minimises squared distance, and that is why it always converges — to a local optimum, so restart it. WCSS falls at every \(k\) and is 0 at \(k = m\), so it can never choose \(k\); use the elbow or maximise the silhouette.