Supervised Models: Cheat Sheet

Assembled from the matching per-unit cheat-sheet slices. This is the single revision page for the whole topic - trees, KNN, neural networks and SVM.

Decision trees and ID3

#NumbersEntropy, information and gain

• Entropy $\mathrm{Entropy}(S) = -\sum_i p_i \log_2 p_i$. A pure node gives 0; a balanced two-class node gives 1.
• Information $I(A) = \sum (\text{weighted}) \ \mathrm{Entropy}(\text{branch})$.
• Gain $G(S, A) = \mathrm{Entropy}(S) - I(A)$.
• Play-Tennis worked numbers: $\mathrm{Entropy}(S) = 0.94$; gains are Outlook 0.247 (the root), Humidity 0.152, Windy 0.048, Temp 0.029.

≡FactsID3 and what it prefers

• ID3: compute the gains, pick the highest, split, recurse - stopping when a node is pure. It is greedy with no backtracking.
• Hypothesis space = all decision trees, so it is complete. It keeps a single hypothesis, never backtracks, and uses all the examples at each step (which makes it noise-robust).
• Inductive bias (a preference bias): prefer shorter trees, and high-gain attributes near the root. Occam's razor.
• Overfitting: great on train, worse on test. Fix with pre-pruning or, better, post-pruning; choose the size with a validation set, a $\chi^2$ test, or MDL.
• Continuous attributes: turn $A$ into a Boolean $A^c = (A < c)$, and pick the threshold $c$ - a midpoint where the class changes - that maximises gain.

Instance-based learning and KNN

≡FactsLazy versus eager

• Lazy: store the data and do the work at query time, giving a rich local hypothesis. KNN is lazy.
• Eager: build the model upfront, giving a single global hypothesis. A decision tree is eager.

#NumbersKNN itself

• KNN classifies by the $k$ nearest neighbours. Discrete targets take the mode, real-valued targets the mean.
• Euclidean distance $\sqrt{\sum_i (x_i - a_i)^2}$.
• K must be odd, to avoid ties. K = 1 produces a Voronoi partition.
• Small K captures structure but is noisy; large K is noise-robust but needs more data. The elbow method picks K from the error-rate-versus-K plot.
• Weighted KNN: closer neighbours weigh more, with $w = 1/d^2$. Its inductive bias is "birds of a feather flock together".
• Complexity is $O(knd)$.

⚠GotchaWhere KNN falls over

Slow at query time, cursed by dimensionality, needs same-scale features, no easy way to pick the optimal K, and it struggles with imbalanced classes, outliers and missing values. The curse of dimensionality shrinks the influence radius as dimensions grow; mitigate it with attribute weighting or leave-one-out, and aim for roughly 5 instances per attribute.

Perceptron and gradient descent

#NumbersThe single unit

• Perceptron: $y = 1$ if $w \cdot x \ge 0$, else 0. The bias is $w_0 = -\theta$ with $x_0 = 1$, and $w$ is perpendicular to the decision boundary.
• It represents AND, OR, NAND, NOR - all linear. AND: $w_0 = -0.8$, $w_1 = w_2 = 0.5$. OR: $w_0 = -0.3$, $w_1 = w_2 = 0.5$.
• It cannot do XOR, which is not linearly separable, so a multilayer network is required.
• Perceptron training rule: $w_i \leftarrow w_i + \eta (t - o) x_i$.

≡FactsDelta rule and gradient descent

• Minimise $E(\vec{w}) = \frac{1}{2}\sum (t - o)^2$ and update $\theta_j \leftarrow \theta_j - \alpha \frac{\partial E}{\partial \theta_j}$.
• $\alpha$ small is slow; $\alpha$ large overshoots. Either way gradient descent can settle in a local minimum.

Neural networks

≡FactsLayers and the forward pass

• Layers: input (no computation) → hidden (the learning core, any number of them) → output. Number of layers = hidden layers + output layer.
• Activation adds non-linearity, applied to $z = \text{inputs} \cdot \text{weights} + \text{bias}$. Without it the network is just linear regression.
• Forward propagation: $Z_1 = X W_{xh} + b_h \rightarrow a_1 = \sigma(Z_1) \rightarrow Z_2 = a_1 W_{hy} + b_y \rightarrow \hat{y} = \sigma(Z_2)$.
• Weight-matrix dimension = (units in the current layer) × (units in the next layer).

≡FactsBackpropagation

• Minimise the loss by the chain rule, working output → input.
• $\frac{\partial E}{\partial w^{(L)}} = a^{(L-1)} \cdot \sigma'(z^{(L)}) \cdot 2(a^{(L)} - y)$.
• $\sigma'(x) = \sigma(x)(1 - \sigma(x))$, and $\tanh'(x) = 1 - \tanh^2(x)$.
• Overfitting fix: keep a validation set and retain the weights with the least validation error.

Activation functions

Function	Range	Note
Sigmoid 1/(1+e⁻ˣ)	(0, 1)	probability
Tanh	(−1, 1)	zero-centred
ReLU max(0, x)	[0, ∞)	can "die"
Leaky ReLU (αx for negative x)	ℝ	fixes dying ReLU
Softmax eˣⁱ/Σeˣʲ	(0, 1), sums to 1	multi-class output

Vanishing and exploding gradients

#NumbersDepth and the weight scale

• In a deep net $y = W_L \cdot \ldots \cdot W_1 \cdot x$: a per-layer scale above 1 explodes, below 1 vanishes. The gradients do the same.
• Fix with weight initialisation. $\mathrm{Var}(w_i) = 1/n$ is Xavier, for tanh; $2/n$ is He, for ReLU.

SVM

≡FactsMargin, planes and support vectors

• SVM is a maximum-margin classifier. The planes are H0 w·x + b = 0, H1 = +1, H2 = −1, and the support vectors define the boundary.
• The two class constraints combine into $y_i(w \cdot x_i + b) \ge 1$.
• Margin width $= 2 / \lVert w \rVert$.

≡FactsPrimal, dual and KKT

• Primal: minimise $\frac{1}{2}\lVert w \rVert^2$ subject to $y_i(w \cdot x_i + b) \ge 1$.
• Dual (Wolfe): maximise $\sum_i \alpha_i - \frac{1}{2}\sum_i \sum_j \alpha_i \alpha_j y_i y_j (x_i \cdot x_j)$, subject to $\alpha_i \ge 0$ and $\sum_i \alpha_i y_i = 0$. Then $w = \sum_i \alpha_i y_i x_i$.
• KKT: every non-support-vector has $\alpha_i = 0$; only the support vectors have $\alpha_i > 0$.

Kernels

≡FactsThe trick and the two kernels

• The dual touches the data only through a dot product, which licenses the kernel trick: $K(x_i, x_j) = \varphi(x_i) \cdot \varphi(x_j)$ without ever computing $\varphi$. A kernel is valid exactly when it is expressible as a dot product.
• Polynomial: $K(a,b) = (a \cdot b + 1)^d$.
• Gaussian / RBF: $K(x, x') = \exp(-\gamma \lVert x - x' \rVert^2)$ - the default, a similarity measure, effectively infinite dimensions.
• γ: high gives a tight boundary that overfits, low gives a smooth one. C: high punishes errors and overfits, low gives a soft margin that generalises.

Notes on the source

⚠GotchaTwo slide errors corrected in these notes

1. Decision trees are supervised, not unsupervised, as one slide had it.
2. The "salary / job-acceptance" information-gain arithmetic on the slides was internally inconsistent, so entropy and gain are taught here with the fully correct Play Tennis worked example instead.

≡FactsProvenance

• Everything above covers every slide topic in the Unit 1 folder and the Unit 2 folder (decks 13-24).
• Several SVM and backpropagation slides were equation-only images that do not extract as text; those derivations are reconstructed here from standard ML and match the slide flow.
• The "Lecture 22-23" video is the SVM recording, and its content corresponds to the 21-23 deck covered under SVM above.