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¶
min–max, to [0, 1]; fitted on the training set only
standardisation, to mean 0 and sd 1
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¶
with \(x_{0} = 1\)
least squares in one variable; the line passes through \((\bar{x}, \bar{y})\)
the cost — convex, one minimum
gradient descent — all \(\theta\) updated simultaneously
the normal equation; \(X^{T}X\) is singular iff the columns of \(X\) are dependent
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¶
0 when pure; \(H = 1\) bit and Gini \(= 0.5\) at a 50/50 binary node
information gain; C4.5 divides it by the split's own entropy to get the gain ratio
Naïve Bayes¶
sum logs in practice; predict the class with the largest product
Laplace smoothing over \(V\) possible values; \(\alpha = 1\) is standard
Logistic regression¶
boundary at \(\theta ^{T}x = 0\); log[p/(1−p)] \(= \theta ^{T}x\), so a coefficient is a log-odds
log-loss: convex, unlike squared error on a sigmoid
k-NN, perceptron, networks¶
the perceptron rule — no change when the prediction is right; converges iff the data is linearly separable
back-propagation: \(\delta\) at the far end \(\times\) activation at the near end
SVM¶
margin width \(2/\Vert w\Vert\); soft margin adds \(C \sum \xi _{i}\), equivalently hinge loss \(\max(0, 1 -\) y·f(x))
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¶
Minkowski: \(p = 1\) Manhattan, \(p = 2\) Euclidean, \(p \to \infty\) Chebyshev; always \(d_{\infty } \le d_{2} \le d_{1}\)
cosine similarity — direction only, ignores length; the right choice for text
what k-means minimises; sklearn calls it inertia_
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.