The Idea

You have one input x and one continuous output y, and you believe the relationship between them is roughly a straight line. Simple linear regression finds the specific line that fits the data best, in the sense of minimising the total squared vertical distance between the line and every point.

The Maths

The model is:

$$y = b_0 + b_1 x + \varepsilon$$

where b0 is the intercept, b1 is the slope, and ε is irreducible noise. We choose b0, b1 by minimising the Ordinary Least Squares (OLS) cost function:

$$J(b_0,b_1)=\sum_{i=1}^{n}\left(y_i-(b_0+b_1x_i)\right)^2$$

Taking partial derivatives and setting both to zero (the normal equations):

$$\frac{\partial J}{\partial b_1}=-2\sum x_i(y_i-b_0-b_1x_i)=0 \qquad \frac{\partial J}{\partial b_0}=-2\sum (y_i-b_0-b_1x_i)=0$$

Solving this pair of equations gives closed-form estimates:

$$b_1=\frac{\sum(x_i-\bar{x})(y_i-\bar{y})}{\sum(x_i-\bar{x})^2}=\frac{\text{Cov}(x,y)}{\text{Var}(x)} \qquad b_0=\bar{y}-b_1\bar{x}$$

How It Works

1. Compute the mean of x and y.
2. Compute the covariance of x and y, and the variance of x.
3. Plug both into the closed-form formulas above to get b0 and b1 directly, no iteration needed.

The Idea

Most real outcomes depend on more than one input. Multiple linear regression fits a hyperplane, rather than a line, across p predictors simultaneously, while still assuming the relationship is linear in the coefficients.

The Maths

In matrix form, with X as the design matrix (one column per feature, plus a column of 1s for the intercept):

$$y = X\beta + \varepsilon$$

Minimising the sum of squared residuals ‖y - Xβ‖² with respect to β and setting the gradient to zero:

$$\frac{\partial}{\partial \beta}\|y-X\beta\|^2 = -2X^T(y-X\beta)=0 \;\;\Longrightarrow\;\; X^TX\beta = X^Ty$$

giving the closed-form normal equation solution:

$$\hat{\beta} = (X^TX)^{-1}X^Ty$$

This requires X^TX to be invertible, which fails under perfect multicollinearity (see the Dummy Variable Trap entry in Foundations).

How It Works

1. Build the design matrix X, including an intercept column of 1s.
2. Check for problematic collinearity between predictors.
3. Solve the normal equation directly, or use QR/SVD decomposition for numerical stability on larger problems.
4. Interpret each coefficient as "the effect of this feature, holding all other features constant".

The Idea

When the relationship between x and y is visibly curved rather than straight, we don't need a new algorithm, we just feed the linear regression machinery extra columns: x², x³, and so on. The model is still linear in its coefficients, only the input features are non-linear transformations of x.

The Maths

$$y = b_0 + b_1x + b_2x^2 + \dots + b_nx^n + \varepsilon$$

Because this is linear in b0...bn, it's fitted with exactly the same normal equation as multiple linear regression, once you build the design matrix as [1, x, x², ..., xⁿ]:

$$\hat{\beta} = (X^TX)^{-1}X^Ty$$

How It Works

1. Generate polynomial feature columns up to degree n.
2. Fit ordinary least squares on this expanded feature set.
3. Choose n using cross-validation, since it directly controls the bias-variance tradeoff.

The Idea

Instead of trying to make every prediction as close as possible to the truth, SVR draws a tube of width 2ε around the fitted function and simply doesn't penalise any point that falls inside it. Only points outside the tube contribute to the loss, and the fitted function is chosen to be as flat as possible subject to that constraint.

The Maths

The optimisation problem (soft margin, allowing some points outside the tube via slack variables ξ, ξ*):

$$\min_{w,b}\; \tfrac{1}{2}\|w\|^2 + C\sum_i(\xi_i+\xi_i^*)$$ $$\text{subject to } \; y_i-(w\cdot x_i+b)\le \varepsilon+\xi_i, \quad (w\cdot x_i+b)-y_i\le \varepsilon+\xi_i^*, \quad \xi_i,\xi_i^*\ge 0$$

This is the ε-insensitive loss: L(y, f(x)) = max(0, |y - f(x)| - ε). The problem is convex and solved via Lagrangian duality, which also opens the door to the kernel trick (see Kernel SVM) for non-linear SVR.

How It Works

1. Choose a kernel (linear, polynomial, RBF) if the relationship is non-linear.
2. Tune C (how much to penalise points outside the tube) and ε (tube width).
3. Solve the dual quadratic programming problem to find the support vectors, the points that actually define the tube's boundary.

The Idea

A decision tree repeatedly asks yes/no questions about the features ("is x1 < 5?") to split the data into increasingly pure regions, then predicts the mean target value of whichever region a new point lands in.

The Maths

At every node, the algorithm searches over every feature j and threshold s to find the split that minimises the combined squared error of the two resulting regions:

$$\min_{j,s}\left[\sum_{x_i\in R_1(j,s)}(y_i-\bar{y}_{R_1})^2 + \sum_{x_i\in R_2(j,s)}(y_i-\bar{y}_{R_2})^2\right]$$

This is applied recursively to each child region until a stopping rule is met (maximum depth, minimum samples per leaf). The prediction at a leaf is simply the mean of the training targets that landed there.

How It Works

1. Start with all data in one root node.
2. Find the single best (feature, threshold) split that most reduces squared error.
3. Split the data into two child nodes, and repeat recursively.
4. Stop by depth limit or minimum leaf size; predict using the leaf's mean.

The Idea

A single decision tree overfits easily. Random Forest trains many trees on different random samples of the data (and different random subsets of features at each split), then averages their predictions, trading a little bias for a large reduction in variance.

The Maths

Bagging: draw B bootstrap samples (sampling with replacement) from the training data, train a tree T_b on each, and predict with the average:

$$\hat{y}(x)=\frac{1}{B}\sum_{b=1}^{B}T_b(x)$$

The reason this helps is variance reduction. For B trees with pairwise correlation ρ and individual variance σ², the variance of their average is:

$$\text{Var}\left(\frac{1}{B}\sum T_b\right) = \rho\sigma^2 + \frac{1-\rho}{B}\sigma^2$$

Averaging alone (bagging) shrinks the second term, but the first term, driven by correlation between trees, remains. Random Forest additionally restricts each split to consider only a random subset of m < p features, which decorrelates the trees (lowers ρ) and drives the variance down further than bagging alone.

How It Works

1. For each of B trees: draw a bootstrap sample of the training rows.
2. Grow the tree, but at each split only consider a random subset of features.
3. Average all B trees' predictions for the final output.

The Idea

We want to predict a probability between 0 and 1, but a straight line runs off to ±∞. Logistic regression fixes this by fitting a linear combination of features, then passing it through the sigmoid function, which squashes any real number into the (0,1) range.

The Maths

$$p(y=1\mid x)=\sigma(z)=\frac{1}{1+e^{-z}}, \qquad z = b_0+b_1x_1+\dots+b_px_p$$

Rearranging shows why it's called "logistic": the log-odds (logit) of the outcome is exactly linear in the features:

$$\log\left(\frac{p}{1-p}\right) = z$$

Unlike linear regression, there's no closed-form solution. Coefficients are found by maximising the likelihood of the observed labels, equivalently minimising the binary cross-entropy loss:

$$L(b) = -\sum_{i=1}^{n}\Big[y_i\log(p_i)+(1-y_i)\log(1-p_i)\Big]$$

This is minimised numerically (gradient descent, or Newton's method / IRLS), using the gradient with respect to each weight:

$$\frac{\partial L}{\partial b_j}=\sum_i (p_i-y_i)\,x_{ij}$$

How It Works

1. Initialise weights (often at zero).
2. Compute predicted probabilities via the sigmoid.
3. Compute the gradient of the cross-entropy loss and update the weights.
4. Repeat until convergence; classify using a threshold (usually 0.5) on the output probability.

The Idea

KNN has no real "training" phase. To classify a new point, it simply looks at the k closest points in the training data and takes a majority vote of their labels. It's often called a "lazy learner" because all the work happens at prediction time.

The Maths

Distance is usually Euclidean, though other metrics generalise this via the Minkowski distance:

$$d(x,x')=\left(\sum_{i=1}^{n}|x_i-x_i'|^p\right)^{1/p}$$

(p=2 gives Euclidean distance, p=1 gives Manhattan distance.) The prediction rule is simply:

$$\hat{y} = \text{mode}\{y_i : x_i \in N_k(x)\}$$

where N_k(x) is the set of k training points closest to x. Choosing k is a direct bias-variance decision: small k gives low bias but high variance (it overfits to noise); large k gives high bias but low variance (it oversmooths the boundary).

How It Works

1. Store the training data (that's the entire "training" step).
2. At prediction time, compute the distance from the new point to every training point.
3. Take the k closest, and predict the majority class among them.

The Idea

Many lines can separate two linearly-separable classes. SVM specifically finds the one that maximises the distance (the "margin") to the closest points of either class, those closest points are the support vectors, and they alone determine the boundary.

The Maths

For a hyperplane w·x + b = 0, the margin width is 2/‖w‖. Maximising the margin is equivalent to minimising ‖w‖, subject to every point being correctly classified with room to spare:

$$\min_{w,b}\;\tfrac{1}{2}\|w\|^2 \quad \text{s.t.} \quad y_i(w\cdot x_i+b)\ge 1 \;\;\forall i$$

Real data usually isn't perfectly separable, so the soft margin version allows some violations via slack variables ξ_i, penalised by a cost C:

$$\min_{w,b}\;\tfrac{1}{2}\|w\|^2+C\sum_i\xi_i \quad \text{s.t.}\quad y_i(w\cdot x_i+b)\ge 1-\xi_i,\;\; \xi_i\ge 0$$

Solved via Lagrangian duality, the dual problem depends on the data only through pairwise dot products x_i · x_j, which is precisely what makes the kernel trick (see Kernel SVM) possible.

How It Works

1. Solve the convex quadratic optimisation problem (dual form) for the Lagrange multipliers α_i.
2. Points with α_i > 0 are the support vectors, everything else can be discarded.
3. Classify new points using the sign of w·x + b.

The Idea

Plain SVM only draws straight lines. Kernel SVM handles classes that can't be separated by any straight line by implicitly mapping the data into a much higher-dimensional space, where a straight separator does exist, without ever actually computing that expensive mapping.

The Maths

Because the SVM dual problem only ever needs dot products x_i · x_j, we can replace that dot product with a kernel function K(x_i, x_j) = φ(x_i)·φ(x_j), computing the result as if the mapping φ had happened, without ever forming it:

$$\text{RBF: } K(x,x')=\exp(-\gamma\|x-x'\|^2) \qquad \text{Polynomial: } K(x,x')=(\gamma\, x\cdot x'+r)^d$$

Mercer's theorem guarantees that any symmetric, positive semi-definite function K corresponds to a genuine dot product in some feature space, which is why this substitution is mathematically valid rather than just a convenient hack. The final decision function becomes:

$$f(x)=\text{sign}\left(\sum_i \alpha_i y_i K(x_i,x)+b\right)$$

How It Works

1. Pick a kernel (RBF is the common default) and its hyperparameters (e.g. γ).
2. Solve the same dual optimisation as linear SVM, but with K(x_i,x_j) replacing every dot product.
3. Classify new points by evaluating the kernel against the stored support vectors.

The Idea

Naive Bayes is a generative classifier: it models how each class produces its features, then inverts that with Bayes' theorem to find the most probable class given the observed features. The "naive" part is assuming every feature is conditionally independent of every other, given the class.

The Maths

Starting from Bayes' theorem and dropping the class-independent denominator, the decision rule (Maximum A Posteriori) is:

$$\hat{y} = \arg\max_{y}\; P(y)\prod_{i=1}^{n}P(x_i\mid y)$$

computed in log-space for numerical stability:

$$\hat{y} = \arg\max_{y}\left[\log P(y) + \sum_{i=1}^{n}\log P(x_i\mid y)\right]$$

The likelihood P(x_i | y) takes a different shape depending on the feature type: Gaussian (continuous features), Multinomial (word counts), or Bernoulli (binary features). Zero-frequency likelihoods are handled with Laplace smoothing, derived from a Dirichlet prior over the class-conditional distribution:

$$P(x_i\mid y=c) = \frac{\text{count}(x_i,c)+\alpha}{\text{count}(c)+\alpha\cdot|\text{features}|}$$

How It Works

1. Estimate the class priors and per-feature likelihoods directly by counting.
2. Apply Laplace smoothing so no probability is ever exactly zero.
3. For a new point, compute the log-posterior score for every class and pick the largest.

The Idea

A classification tree asks a sequence of yes/no questions about the features, at each step choosing the split that makes the resulting groups as "pure" as possible (dominated by a single class), and predicts using the majority class in whichever leaf a point lands in.

The Maths

Purity is usually measured with the Gini index or entropy, for a node with class proportions p_k:

$$\text{Gini}=1-\sum_{k}p_k^2 \qquad \text{Entropy}=-\sum_k p_k\log_2 p_k$$

A split is chosen to maximise information gain, the reduction in impurity from parent to weighted children:

$$\text{Gain} = H(\text{parent}) - \sum_{\text{children}} \frac{n_{\text{child}}}{n_{\text{parent}}}H(\text{child})$$

How It Works

1. At each node, evaluate every possible (feature, threshold) split and compute its information gain.
2. Choose the split with the highest gain, and recurse on both children.
3. Stop by depth or minimum leaf size; predict using the majority class at the leaf.

The Idea

Exactly the same recipe as Random Forest Regression, many decision trees trained on bootstrap samples with random feature subsets at each split, except the final prediction is decided by majority vote instead of averaging.

The Maths

$$\hat{y}(x)=\text{mode}\{T_b(x)\}_{b=1}^{B}$$

Since each tree is trained on a bootstrap sample, roughly 1 - 1/e ≈ 63.2% of the rows are used, leaving about 36.8% of rows unseen by any given tree ((1-1/n)^n → e^{-1} as n grows). These out-of-bag (OOB) rows give a free, built-in estimate of generalisation error without needing a separate validation set. Feature importance is typically measured by the average impurity decrease a feature contributes across all trees, or by permutation importance (shuffle a feature's values and measure the resulting drop in accuracy).

How It Works

1. Grow B classification trees, each on a bootstrap sample with random feature subsets per split.
2. Predict the majority vote across all trees.
3. Use the out-of-bag rows to sanity-check generalisation performance for free.

The Idea

K-Means partitions unlabelled data into K groups by repeatedly assigning each point to its nearest centroid, then moving each centroid to the average of the points assigned to it, until nothing changes.

The Maths

The objective is to minimise the within-cluster sum of squares (WCSS):

$$J = \sum_{k=1}^{K}\sum_{x_i\in C_k}\|x_i-\mu_k\|^2$$

This is minimised via Lloyd's algorithm, alternating between two steps until convergence:

$$\text{Assign: } C_k=\{x_i : k=\arg\min_j\|x_i-\mu_j\|^2\} \qquad \text{Update: } \mu_k=\frac{1}{|C_k|}\sum_{x_i\in C_k}x_i$$

Each step can only decrease or maintain J, so the algorithm always converges, but only to a local minimum, which is why smart initialisation (k-means++) and multiple random restarts are used in practice. Choosing K itself is typically done with the elbow method (plotting WCSS against K and looking for the point of diminishing returns) or the silhouette score.

How It Works

1. Initialise K centroids.
2. Assign every point to its nearest centroid.
3. Recompute each centroid as the mean of its assigned points.
4. Repeat steps 2-3 until assignments stop changing.

The Idea

Rather than committing to a number of clusters upfront, hierarchical clustering builds a full nested tree (a dendrogram) by repeatedly merging the two closest clusters, starting from every point as its own cluster. You choose the final number of clusters afterwards, by deciding where to "cut" the tree.

The Maths

The key choice is the linkage criterion, how "distance between two clusters" is defined:

• Single linkage: the minimum distance between any pair of points across the two clusters.
• Complete linkage: the maximum such distance.
• Average linkage: the mean of all pairwise distances.
• Ward's method: merge whichever pair of clusters causes the smallest increase in total within-cluster variance.

The algorithm greedily merges the closest pair of clusters at every step, recording the merge distance, until only one cluster remains. Cutting the dendrogram at a chosen height yields a chosen number of clusters, often picked visually by finding the tallest vertical gap that no horizontal line crosses.

How It Works

1. Start with every point as its own cluster.
2. Repeatedly merge the two closest clusters, per the chosen linkage rule.
3. Record every merge to build the dendrogram.
4. Cut the tree at the desired height to get a specific number of clusters.

The Idea

Apriori mines transaction data (shopping baskets, browsing sessions) to find frequently co-occurring items, then converts those into "if this, then that" association rules.

The Maths

Three quantities define every rule X → Y:

$$\text{Support}(X)=\frac{\text{transactions containing }X}{\text{total transactions}}$$ $$\text{Confidence}(X\to Y)=\frac{\text{Support}(X\cup Y)}{\text{Support}(X)}=P(Y\mid X)$$ $$\text{Lift}(X\to Y)=\frac{\text{Confidence}(X\to Y)}{\text{Support}(Y)}$$

Lift above 1 means X and Y co-occur more than chance would predict; lift near 1 means they're essentially independent. The whole algorithm rests on the Apriori principle: if an itemset is frequent, every subset of it must also be frequent (equivalently, any superset of an infrequent itemset is also infrequent). This lets the search prune huge portions of the itemset space rather than checking every possible combination.

How It Works

1. Find all frequent single items (support above a minimum threshold).
2. Combine frequent itemsets into candidate pairs, keep only those meeting the support threshold.
3. Repeat for triples, quadruples, and so on, pruning any candidate whose subset isn't already frequent.
4. From the final frequent itemsets, generate rules that meet a minimum confidence.

The Idea

Eclat finds the same frequent itemsets as Apriori, but stores the data differently: instead of scanning the whole transaction list repeatedly, it represents each item by the set of transaction IDs it appears in, and finds itemset support via simple set intersection.

The Maths

Each item i is represented by its tid-set, the set of transaction IDs containing it. Support of a combined itemset comes directly from intersecting tid-sets:

$$\text{tid-set}(X\cup Y) = \text{tid-set}(X)\cap \text{tid-set}(Y), \qquad \text{Support}(X)=\frac{|\text{tid-set}(X)|}{\text{total transactions}}$$

This avoids re-scanning the full database at every level, unlike Apriori's horizontal approach, while relying on the same anti-monotonicity pruning principle underneath.

How It Works

1. Convert the transaction data into vertical tid-sets, one per item.
2. Depth-first search through combinations of items, computing support via tid-set intersection.
3. Prune any branch that falls below the minimum support threshold.

The Idea

PCA finds new, orthogonal axes, ordered by how much variance they capture, so that most of a dataset's information can be kept using far fewer dimensions than the original features.

The Maths

With data X mean-centred, compute the covariance matrix and solve its eigenvalue problem:

$$\Sigma = \frac{1}{n}X^TX, \qquad \Sigma v_i = \lambda_i v_i$$

The eigenvectors v_i are the principal components (the new axes); the eigenvalues λ_i are how much variance each axis explains. Sorting by descending eigenvalue and keeping the top k gives the reduced representation:

$$Z = X V_k$$

In practice this is computed via the numerically stable Singular Value Decomposition, X = UΣV^T, where the columns of V are exactly the principal component directions. The proportion of variance each component explains, λ_i / Σλ_j, is used to decide how many components to keep (commonly enough for 95% cumulative variance).

How It Works

1. Standardise the data (mean 0).
2. Compute the covariance matrix (or run SVD directly on the data matrix).
3. Sort eigenvectors by eigenvalue, keep the top k.
4. Project the original data onto these k components.

The Idea

Ordinary PCA can only find linear structure. Kernel PCA applies the same kernel trick used in Kernel SVM: implicitly map the data to a higher-dimensional space using a kernel function, then perform PCA there, all without ever explicitly computing the mapping.

The Maths

Instead of the covariance matrix, work directly with the kernel matrix K_{ij}=K(x_i,x_j). After centring it in feature space:

$$K' = K - \mathbf{1}_nK - K\mathbf{1}_n + \mathbf{1}_nK\mathbf{1}_n$$

solve the eigenvalue problem on K' directly, and project a point x onto the i-th component using only kernel evaluations against the training points:

$$z_i(x) = \sum_j \alpha_{ij}\,K(x_j,x)$$

This never requires the explicit feature mapping φ(x), exactly the same trick, and the same underlying theoretical guarantee (Mercer's theorem), as Kernel SVM.

How It Works

1. Choose a kernel (RBF is common) and its hyperparameters.
2. Build and centre the kernel matrix.
3. Solve its eigenvalue problem to get the non-linear components.

The Idea

PCA finds directions of maximum variance without caring about class labels. LDA is supervised: it finds the projection that best separates known classes, by maximising the distance between class means while minimising the spread within each class.

The Maths

Define the within-class and between-class scatter matrices:

$$S_W=\sum_k\sum_{i\in \text{class }k}(x_i-\mu_k)(x_i-\mu_k)^T \qquad S_B=\sum_k n_k(\mu_k-\mu)(\mu_k-\mu)^T$$

LDA seeks the projection w that maximises Fisher's criterion, the ratio of between-class to within-class variance:

$$J(w)=\frac{w^TS_Bw}{w^TS_Ww}$$

which is solved as a generalised eigenvalue problem, equivalently the eigenvectors of S_W⁻¹S_B, sorted by descending eigenvalue. With C classes, at most C-1 useful discriminant directions exist, since S_B has rank at most C-1.

How It Works

1. Compute the within-class and between-class scatter matrices.
2. Solve the generalised eigenvalue problem for S_W⁻¹S_B.
3. Project the data onto the top eigenvectors (up to C-1 of them).

The Idea

t-SNE (t-distributed Stochastic Neighbour Embedding) is designed specifically for visualisation: it tries to keep points that are close together in high dimensions close together in a 2D or 3D map, at the deliberate cost of not preserving global distances faithfully.

The Maths

In the high-dimensional space, convert distances into neighbour probabilities using a Gaussian centred on each point, then symmetrise:

$$p_{j|i}=\frac{\exp(-\|x_i-x_j\|^2/2\sigma_i^2)}{\sum_{k\ne i}\exp(-\|x_i-x_k\|^2/2\sigma_i^2)}, \qquad p_{ij}=\frac{p_{j|i}+p_{i|j}}{2n}$$

In the low-dimensional map, use a heavier-tailed Student-t distribution instead of a Gaussian, specifically to avoid the "crowding problem" where moderate high-dimensional distances get artificially squeezed together:

$$q_{ij}=\frac{(1+\|y_i-y_j\|^2)^{-1}}{\sum_{k\ne l}(1+\|y_k-y_l\|^2)^{-1}}$$

The 2D coordinates y_i are then optimised by gradient descent to minimise the KL divergence between the two distributions:

$$KL(P\|Q)=\sum_{i\ne j}p_{ij}\log\frac{p_{ij}}{q_{ij}}$$

How It Works

1. Compute high-dimensional neighbour probabilities, tuned via the perplexity hyperparameter.
2. Initialise a random low-dimensional layout.
3. Iteratively adjust the layout with gradient descent to minimise the KL divergence between high- and low-dimensional neighbour distributions.

The Idea

Where Random Forest builds many independent trees and averages them, Gradient Boosting builds trees sequentially: each new tree is trained specifically to predict the errors of the ensemble so far, gradually correcting the combined model. This is the foundation XGBoost, AdaBoost, and CatBoost all build on.

The Maths

Start with a simple initial prediction F₀(x) (e.g. the mean of y). At each stage m, compute the pseudo-residuals, the negative gradient of the loss with respect to the current prediction:

$$r_{im} = -\left[\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}\right]_{F=F_{m-1}}$$

(for squared-error loss, this is simply the ordinary residual y_i - F_{m-1}(x_i)). Fit a new weak learner h_m(x) (usually a shallow tree) to predict these residuals, then update the ensemble with a shrinkage factor ν (the learning rate):

$$F_m(x) = F_{m-1}(x) + \nu \cdot h_m(x)$$

This is literally gradient descent, just performed in "function space" rather than parameter space: each tree approximates the direction that most reduces the overall loss.

How It Works

1. Start with a simple baseline prediction.
2. Compute the residuals between predictions and true values.
3. Fit a small tree to predict those residuals, and add a shrunk version of it to the ensemble.
4. Repeat for a fixed number of rounds, or until validation performance stops improving.

The Idea

XGBoost (Extreme Gradient Boosting) is a heavily optimised, regularised implementation of gradient boosting. Its key mathematical difference is using a second-order (Newton's method) approximation of the loss at every step, plus an explicit complexity penalty on each tree.

The Maths

At each round, XGBoost minimises a regularised objective, with tree complexity penalty Ω:

$$\text{Obj}^{(m)} = \sum_i L(y_i,F_{m-1}(x_i)+h_m(x_i)) + \Omega(h_m), \qquad \Omega(h)=\gamma T + \tfrac{1}{2}\lambda\sum_j w_j^2$$

(T = number of leaves, w_j = leaf weights). Using a second-order Taylor expansion of the loss around the current prediction, with gradient g_i and Hessian h_i:

$$L(y_i,F_{m-1}+h_m)\approx L(y_i,F_{m-1}) + g_ih_m(x_i)+\tfrac{1}{2}h_ih_m(x_i)^2$$

For a fixed tree structure, this gives a closed-form optimal leaf weight:

$$w_j^{*}=-\frac{\sum_{i\in \text{leaf }j}g_i}{\sum_{i\in \text{leaf }j}h_i+\lambda}$$

Plugging this back in produces a closed-form "gain" score for any candidate split, the direct analogue of information gain, but derived from the actual loss function's curvature rather than a generic impurity measure.

How It Works

1. Compute the gradient and Hessian of the loss for every point, given current predictions.
2. Greedily grow each tree using the closed-form gain formula to choose splits.
3. Apply shrinkage and the γ, λ regularisation penalties to control overfitting.

The Idea

AdaBoost (Adaptive Boosting) trains a sequence of very simple weak learners, often single-split "decision stumps", where each new learner is trained on a reweighted version of the data that emphasises whatever the previous learners got wrong.

The Maths

Initialise equal weights w_i = 1/n for every sample. At each round m:

1. Train a weak learner h_m on the current weighted data.
2. Compute its weighted error rate: ε_m = Σ w_i · 𝟙(h_m(x_i)≠y_i) / Σ w_i
3. Compute its vote weight: α_m = ½ ln((1-ε_m)/ε_m), better-than-random learners get a positive vote, and the smaller the error the larger the vote.
4. Update the weights: w_i ← w_i · exp(-α_m y_i h_m(x_i)), then renormalise.

This last step is the heart of the algorithm: misclassified points get their weight boosted, so the next learner is forced to pay them more attention. The final prediction is a weighted vote:

$$H(x)=\text{sign}\left(\sum_{m=1}^{M}\alpha_mh_m(x)\right)$$

How It Works

1. Train a weak learner, measure its weighted error, and assign it a vote weight based on that error.
2. Boost the weights of the points it got wrong.
3. Repeat, then combine all learners via their weighted vote.

The Idea

CatBoost (Categorical Boosting) tackles a subtle problem in ordinary gradient boosting: when encoding categorical features using target statistics, or when fitting each new tree's residuals, standard approaches can leak information about a sample's own target value into its own features, quietly causing overfitting. CatBoost's core innovations exist specifically to remove that leakage.

The Maths

Ordered Target Statistics: instead of encoding a category using the mean target across the whole dataset (which uses each row's own label to encode itself), CatBoost computes each row's category statistic using only rows that came before it in a random permutation:

$$TS(x_i)=\frac{\sum_{j(P a global prior, a a smoothing weight). This mimics how the statistic would look if it were computed causally, in time order, rather than leaking future information backwards.

Ordered Boosting: applies the same idea to the boosting process itself, each tree's residuals are computed using a model that never saw that particular row during training, using multiple random data permutations to make this efficient in practice.

CatBoost also grows symmetric (oblivious) trees, where the same split condition is applied across an entire level of the tree, trading some flexibility for speed and a built-in regularising effect.

How It Works

1. Encode categorical features using ordered target statistics, rather than naive target means.
2. Grow trees using ordered boosting, so no tree ever benefits from a point's own label.
3. Use symmetric trees for fast, regularised splits.

The Idea

ARIMA (AutoRegressive Integrated Moving Average) forecasts a time series using three ingredients: its own lagged values (AutoRegressive), its own past forecast errors (Moving Average), and differencing to strip out trend so the series becomes stationary (Integrated).

The Maths

An AR(p) model predicts the current value from its own past p values:

$$X_t = c + \phi_1X_{t-1}+\dots+\phi_pX_{t-p}+\varepsilon_t$$

An MA(q) model instead predicts it from past forecast errors:

$$X_t = \mu + \varepsilon_t+\theta_1\varepsilon_{t-1}+\dots+\theta_q\varepsilon_{t-q}$$

Differencing (I, order d) removes trend so the mean and variance stop changing over time: ∇X_t = X_t - X_{t-1}, applied d times if needed, and checked with a stationarity test such as the Augmented Dickey-Fuller test. The full ARIMA(p,d,q) model combines all three, applied to the d-times-differenced series Y_t:

$$Y_t = c+\phi_1Y_{t-1}+\dots+\phi_pY_{t-p}+\varepsilon_t+\theta_1\varepsilon_{t-1}+\dots+\theta_q\varepsilon_{t-q}$$

Orders p and q are chosen by inspecting ACF/PACF plots or comparing candidate models with AIC/BIC; parameters are then fit via Maximum Likelihood Estimation, since the unobserved error terms rule out a simple closed form once MA terms are involved.

How It Works

1. Test for stationarity, and difference the series until it holds.
2. Use ACF/PACF plots to propose candidate p and q orders.
3. Fit candidate models via maximum likelihood, and compare with AIC/BIC.
4. Forecast forward, then reverse the differencing to return to the original scale.

The Idea

SARIMA (Seasonal ARIMA) extends ARIMA with a second, parallel AR/I/MA structure that operates specifically at seasonal lags, letting it model repeating cycles like weekly, monthly, or yearly patterns on top of trend.

The Maths

Written SARIMA(p,d,q)(P,D,Q)ₘ, where m is the season length (e.g. 12 for monthly data with yearly seasonality), and (P,D,Q) mirror (p,d,q) but operate at lag multiples of m. Seasonal differencing removes the seasonal pattern the same way ordinary differencing removes trend:

$$\nabla_mX_t = X_t - X_{t-m}$$

The full model, using the lag operator L (where LX_t = X_{t-1}), combines both the regular and seasonal AR/MA polynomials:

$$\phi_p(L)\,\Phi_P(L^m)\,(1-L)^d(1-L^m)^D\,X_t = \theta_q(L)\,\Theta_Q(L^m)\,\varepsilon_t$$

Order selection follows the same ACF/PACF and AIC/BIC logic as ARIMA, but examined additionally at the seasonal lags (multiples of m) to identify P and Q.

How It Works

1. Identify the seasonal period m (weekly, monthly, yearly).
2. Apply both regular and seasonal differencing until the series is stationary.
3. Select (p,d,q) and (P,D,Q) using ACF/PACF at regular and seasonal lags.
4. Fit via maximum likelihood and forecast forward.

The Idea

Many algorithms are sensitive to the raw scale of a feature. A "salary in pounds" column can numerically dwarf an "age in years" column purely because of units, not because it's more important. Scaling fixes that before it distorts distance calculations or gradient-based optimisation.

The Maths

Normalisation (min-max scaling) rescales into a fixed range, usually [0,1]:

$$x' = \frac{x-\min(x)}{\max(x)-\min(x)}$$

Standardisation (Z-score scaling) rescales to mean 0 and standard deviation 1:

$$x' = \frac{x-\mu}{\sigma}$$

Normalisation is sensitive to outliers, since one extreme value compresses everything else into a tiny range. Standardisation doesn't bound values to a fixed range but is more robust to outliers, and is the more common default.

Where It Matters

• Essential for: KNN, K-Means, SVM, PCA (all distance-based), and gradient-descent-optimised models like logistic regression and neural networks (unscaled features distort the loss surface and slow convergence).
• Not required for: Decision Trees, Random Forest, Gradient Boosting, since splits depend only on the ordering of values within a feature, not their scale.

The Idea

Turning a categorical feature with k categories into k one-hot dummy columns, then feeding all k into a regression alongside an intercept, creates a subtle but serious problem: perfect multicollinearity.

The Maths

By construction, one-hot dummies for every row always sum to exactly 1:

$$D_1+D_2+\dots+D_k = 1 \quad \text{for every row}$$

If the model also has an intercept term (a column of all 1s), one column becomes an exact linear combination of the others, meaning X^TX is singular and cannot be inverted, breaking the normal equation β̂ = (X^TX)⁻¹X^Ty from Multiple Linear Regression entirely.

The Fix

Drop exactly one dummy category. That dropped category becomes the implicit "reference" or "baseline" that the intercept and every other coefficient are measured relative to, leaving k-1 dummy variables for k categories.

The Idea

A stepwise feature selection method for regression: begin with every candidate predictor included, then remove the least statistically useful one at a time, until only genuinely useful predictors remain.

The Procedure

1. Choose a significance level to stay in the model (commonly SL = 0.05).
2. Fit the model with every candidate predictor.
3. Find the predictor with the highest p-value. If it's greater than SL, remove it.
4. Refit the model without that predictor.
5. Repeat steps 3-4 until every remaining predictor has a p-value at or below SL.

The p-value comes from a t-test on each coefficient (H₀: βⱼ = 0), testing whether that predictor still contributes once every other current predictor is accounted for.

The Idea

Start with no predictors at all, and add the single most useful one at each step, stopping as soon as no remaining candidate is good enough to justify adding.

The Procedure

1. Choose a significance level to enter the model (commonly SL = 0.05).
2. Fit every possible simple regression of y on one predictor; keep whichever has the lowest p-value below SL.
3. Fit every model adding one more predictor to those already kept; keep the new addition if its p-value is below SL.
4. Repeat step 3 until the best remaining candidate no longer clears the threshold, then keep the model from the previous step.

Bidirectional Elimination (Stepwise Regression) combines both directions: at every step a feature can be added (if it clears the threshold to enter) or removed (if it later rises above the threshold to stay), giving a more thorough, if more expensive, search than either method alone.

The Idea

Regularisation adds a penalty on coefficient size directly into the regression loss function, trading a small amount of bias for a meaningful reduction in variance, a direct, practical application of the Bias-Variance Tradeoff.

The Maths

Ridge (L2 penalty): shrinks all coefficients smoothly toward zero, rarely to exactly zero:

$$\min_\beta \sum_i(y_i-\hat{y}_i)^2 + \lambda\sum_j\beta_j^2 \;\;\Longrightarrow\;\; \hat{\beta}=(X^TX+\lambda I)^{-1}X^Ty$$

The added λI term also fixes multicollinearity directly, X^TX + λI is always invertible for λ > 0, even when X^TX alone isn't.

Lasso (L1 penalty): because the penalty has sharp corners at zero geometrically, it tends to push some coefficients to exactly zero, performing automatic feature selection:

$$\min_\beta \sum_i(y_i-\hat{y}_i)^2 + \lambda\sum_j|\beta_j|$$

Elastic Net blends both, keeping Lasso's feature-selection tendency while adding Ridge's stability when features are highly correlated:

$$\min_\beta \sum_i(y_i-\hat{y}_i)^2 + \lambda_1\sum_j|\beta_j| + \lambda_2\sum_j\beta_j^2$$

The Idea

Every model's prediction error breaks down into three sources: how wrong its assumptions are on average (bias), how much its predictions swing across different training samples (variance), and irreducible noise in the data itself.

The Maths

For a model f̂ estimating true function f with noise variance σ², the expected squared error at a point decomposes exactly as:

$$E\big[(y-\hat{f}(x))^2\big] = \big(\text{Bias}[\hat{f}(x)]\big)^2 + \text{Var}[\hat{f}(x)] + \sigma^2$$

where Bias[f̂(x)] = E[f̂(x)] - f(x) (how far the average prediction, across many possible training sets, sits from the truth), and Var[f̂(x)] = E[(f̂(x)-E[f̂(x)])²] (how much predictions actually vary across those different training sets).

Why It Matters

Simple models (linear regression, shallow trees, high k in KNN) tend toward high bias, low variance, underfitting, consistently wrong in the same way. Complex models (deep trees, low k in KNN, high-degree polynomials) tend toward low bias, high variance, overfitting, accurate on training data but wildly different if retrained on a new sample.

This single decomposition is the theoretical justification behind nearly everything else in this guide: Regularisation (Ridge/Lasso) trades variance for bias directly; Random Forest reduces variance through averaging; Boosting reduces bias by sequentially correcting errors; and Cross-Validation exists specifically to help find the sweet spot between the two.

The Idea

A single train/validation split gives a noisy, luck-dependent estimate of how well a model generalises. Cross-validation averages that estimate over multiple splits; grid search then uses that more reliable estimate to systematically compare hyperparameter choices.

The Maths

k-Fold Cross-Validation: split the training data into k equal folds. For each fold in turn, train on the remaining k-1 folds and validate on the held-out one, then average all k scores:

$$\text{CV score} = \frac{1}{k}\sum_{i=1}^{k}\text{Score}(\text{model trained without fold }i,\text{ evaluated on fold }i)$$

Every point is used for validation exactly once, giving a lower-variance estimate than any single split. Grid Search then defines a grid of candidate hyperparameter combinations (e.g. C ∈ {0.1, 1, 10}, kernel ∈ {linear, rbf}), evaluates every combination with k-fold cross-validation, and picks whichever combination scores best on average.

Regression Metrics

R² (coefficient of determination) is the proportion of variance in y explained by the model:

$$R^2 = 1-\frac{SS_{res}}{SS_{tot}}, \qquad SS_{res}=\sum(y_i-\hat{y}_i)^2, \;\; SS_{tot}=\sum(y_i-\bar{y})^2$$

Adjusted R² penalises adding predictors that don't genuinely help, unlike plain R² which can only rise or stay flat as more predictors are added, even useless ones:

$$R^2_{adj} = 1-(1-R^2)\frac{n-1}{n-p-1}$$

Classification Metrics

Built from the Confusion Matrix (True Positives, True Negatives, False Positives, False Negatives):

$$\text{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN} \qquad \text{Precision}=\frac{TP}{TP+FP} \qquad \text{Recall}=\frac{TP}{TP+FN}$$ $$F_1 = 2\cdot\frac{\text{Precision}\cdot\text{Recall}}{\text{Precision}+\text{Recall}}$$

The ROC curve plots Recall against the False Positive Rate across every possible classification threshold; the AUC (area under that curve) condenses it into one number, where 0.5 is random guessing and 1.0 is perfect separation, measuring how well the model ranks positives above negatives regardless of the specific threshold used.

Which One To Use

• Accuracy: fine for balanced classes with equal error costs.
• Precision: when false positives are expensive (e.g. spam filtering).
• Recall: when false negatives are expensive (e.g. disease screening).
• F1 / AUC: imbalanced classes, or when you need one balanced summary number.