Supervised Learning: Regression, Trees, and Ensembles

Regression"Regression" is a strange name for a family of techniques used to predict continuous values, and the strangeness has a specific origin: Francis Galton, studying the heights of parents and children in the 1880s, found that tall parents tended to have somewhat shorter children and short parents somewhat taller ones — each generation "regressing" back toward the population mean rather than drifting to extremes. The statistical machinery he built to describe that pattern, fitting a line through a scatter of points, is the same machinery a modern classifier or predictor still starts from, and the standard modern treatment of that machinery and everything built on top of it runs through one core textbook¹. Supervised learning is the branch of machine learning built on that idea: given a set of examples, each already labelled with the answer, find a function that predicts the label for a new, unseen example.

From a Line to a Boundary

LinearLinear regression fits a straight line (or, with more than one input variable, a hyperplane) through a set of points by minimising the total squared distance between the line and each observed point — the least-squares criterion. Given inputs x and weights w, the prediction is ŷ = w·x + b, and training means searching for the w and b that minimise the mean squared error between ŷ and the true labels across the whole training set. That search is an optimization problem, and in practice it's solved iteratively by gradient descent — nudging each weight a little in the direction that reduces the error, repeated until the error stops improving; the full mechanics of that process, including why the learning rate matters and what the loss surface looks like for non-linear models, belong to Calculus and Optimization rather than here.

Logistic regression adapts the same linear model to a different job: classification rather than prediction of a continuous value. Instead of outputting w·x + b directly, it passes that value through the sigmoid function, σ(z) = 1 / (1 + e⁻ᶻ), which squashes any real number into the range (0, 1) and is interpreted as a probability — "how likely is this example to belong to the positive class?" A threshold, usually 0.5, turns that probability into a hard yes/no decision. Despite the name, logistic regression is a classifier, not a regression technique in the predicting-a-number sense; the "regression" in the name refers only to the shared linear core.

Decision Trees: Splitting on Impurity

AA decision tree takes a different approach entirely: instead of fitting one global equation, it asks a sequence of yes/no questions about the input features, each one splitting the training examples into purer and purer subsets, until each leaf is (ideally) dominated by a single class. The question a tree asks at each split is chosen by testing every candidate feature and threshold, and picking whichever split does the most to reduce impurity — how mixed the classes are within a node. Two measures of impurity are in common use:

where pᵢ is the proportion of examples in the node belonging to class i. Both measures reach zero for a perfectly pure node (every example the same class) and their maximum when classes are evenly mixed, and both are used the same way: compute the impurity of a node before a candidate split, compute the weighted average impurity of the two children after it, and pick the split with the largest reduction.

def gini(labels: list[int]) -> float:
    n = len(labels)
    if n == 0:
        return 0.0
    counts = {c: labels.count(c) for c in set(labels)}
    return 1.0 - sum((count / n) ** 2 for count in counts.values())

def gini_gain(parent: list[int], left: list[int], right: list[int]) -> float:
    n = len(parent)
    weighted_child_impurity = (
        (len(left) / n) * gini(left) + (len(right) / n) * gini(right)
    )
    return gini(parent) - weighted_child_impurity

A tree grown without any limit will keep splitting until every leaf is pure, which usually means memorising noise in the training data rather than learning a generalisable rule — a single tree left unconstrained is one of the easiest models to overfit, which is exactly why it is rarely used alone in practice.

Ensembles: Bagging and Boosting

AnAn ensemble combines many individually weak or overfit models into one that generalises better than any of its parts, and the two dominant ways of building one differ in how the individual models are trained relative to each other.

Bagging (bootstrap aggregating) trains many trees independently and in parallel, each on a different random resample (with replacement) of the training data, and averages their predictions. A random forest adds a second layer of randomness on top: at each split, only a random subset of the available features is considered, which decorrelates the individual trees from each other — without that extra step, trees trained on similar bootstrap samples tend to make similar splits near the root and end up highly correlated, which limits how much averaging them actually helps. Breiman's original paper both names the method and proves that the generalisation error of a random forest converges as more trees are added, rather than eventually overfitting the way a single deep tree does².

Boosting takes the opposite approach: models are trained sequentially, and each new model is trained specifically to correct the mistakes of the ensemble built so far, typically by upweighting the training examples the current ensemble gets wrong. AdaBoost, the algorithm that established the approach, reweights misclassified examples after every round and combines all the weak learners into a single weighted vote at the end³; gradient boosting generalises the same idea, fitting each new model to the residual error of the ensemble rather than to reweighted examples.

Overfitting and Regularization

AA model with enough free parameters can always fit the training data more closely by memorising its idiosyncrasies rather than learning the pattern underneath — the gap between how well a model does on the data it trained on and on new, unseen data is the practical symptom of overfitting. Regularization controls this by adding a penalty term to the loss function that discourages large weights, on the reasoning that a simpler model (smaller weights, fewer weights actually used) generalises better than a needlessly complex one. Two forms are standard:

• L2 regularization (ridge) adds the sum of squared weights, λΣwᵢ², to the loss. It shrinks every weight toward zero smoothly, but rarely to exactly zero.
• L1 regularization (lasso) adds the sum of absolute weights, λΣ|wᵢ|, instead. Its penalty has a sharp corner at zero, which tends to drive some weights to exactly zero — L1 regularization performs a form of automatic feature selection as a side effect, while L2 does not.

λ controls how strongly the penalty is weighted against the original loss; too small and it does nothing, too large and the model underfits by shrinking every weight toward triviality regardless of whether the corresponding feature actually mattered.

Evaluating a Classifier: Why Accuracy Lies

AccuracyAccuracy — the proportion of predictions a classifier gets right — is the first metric anyone reaches for, and the first one that misleads on realistic data. A fraud-detection model that always predicts "not fraud" on a dataset where 99.5% of transactions are legitimate scores 99.5% accuracy while catching precisely zero fraud, because accuracy treats getting the rare class wrong exactly the same as getting the common class wrong. A confusion matrix breaks a classifier's predictions down by what actually happened versus what was predicted, and gives the vocabulary needed to say something more useful than "accuracy":

Precision (TP / (TP + FP)) asks: of everything flagged positive, how much actually was? Recall (TP / (TP + FN)) asks: of everything that actually was positive, how much did the model catch? The two trade off against each other — a model can trivially reach 100% recall by flagging everything positive, at the cost of terrible precision — and the F1 score, their harmonic mean (2 · precision · recall / (precision + recall)), gives a single number that penalises a model for doing badly on either. Which of precision or recall matters more depends entirely on what a false positive versus a false negative costs in the actual application: a spam filter's false positive buries a real email, while a cancer-screening model's false negative misses an actual case — the same confusion matrix, read against two different costs, points toward two different acceptable trade-offs.

Random forests and gradient boosting remain, in practice, the default choice for structured, tabular data — spreadsheets and database tables rather than images or free text — precisely because they need little of the manual feature engineering older linear models required and little of the training data volume that neural architectures need to outperform them. Where the data stops being tabular and starts being pixels, raw audio, or sequences, the more useful starting point is a model built to exploit that structure directly, which is where Neural Networks and Deep Learning picks up.

References