How the main algorithms actually work

You can already fit these models and read their scores. This section is about what each one does internally: the assumptions a linear model makes, how a tree picks a split, why fitting new trees to the errors of previous ones works at all, and where support vector machines and nearest neighbours still fit. The point is to choose one for a stated reason rather than by habit, and to know which of them you can read an explanation out of, where the answer for linear coefficients is often no.

Model                  Fitted by              Capacity set by        Read an explanation out of it?
linear / logistic      closed form or convex  the features you give  yes, if features are uncorrelated
decision tree          greedy search          max_depth, min_leaf    yes, as rules, if shallow
random forest          many trees, averaged   max_features           only as feature importances
gradient boosting      many trees, sequential learning_rate x trees  only as SHAP or importances
SVM                    convex optimisation    C and the kernel       not really
k-nearest neighbours   no fitting at all      k                      yes: here are the neighbours

Linear models#

Linear regression finds the weights minimising squared error. It assumes the relationship is linear and the errors are roughly independent with constant variance. When those assumptions hold it is fast, stable and interpretable, and each coefficient says how the prediction moves with that feature.

Squared error is not an arbitrary choice. It makes the problem convex with a single solution reachable in closed form, and it is what you get if you assume the noise is Gaussian and ask for the most likely weights. The same derivation with a different noise assumption gives a different loss, which is where absolute error and the rest come from.

Regularisation is the fix for that instability and for overfitting generally: add a penalty on the size of the weights, so the model prefers a simpler explanation unless the data insists otherwise. The two penalties behave differently in a way worth seeing rather than being told. L2, called ridge, penalises squared weights and shrinks everything smoothly towards zero without reaching it. L1, called lasso, penalises absolute weights, and its solution sets coefficients exactly to zero, which makes it a feature selector.

import numpy as np
from sklearn.linear_model import Ridge, Lasso

rng = np.random.default_rng(0)
X = rng.normal(0, 1, (200, 30))
true = np.zeros(30); true[:4] = [3.0, -2.0, 1.5, 1.0]     # only 4 of the 30 matter
y = X @ true + rng.normal(0, 0.5, 200)

for name, m in [("plain", Ridge(alpha=1e-9)),
                ("ridge a=10", Ridge(alpha=10.0)),
                ("lasso a=0.1", Lasso(alpha=0.1))]:
    m.fit(X, y)
    print(name, (np.abs(m.coef_) > 1e-6).sum(), np.abs(m.coef_[4:]).max().round(3))

# plain         nonzero 30/30    largest junk coefficient 0.101
# ridge a=10    nonzero 30/30    largest junk coefficient 0.091
# lasso a=0.1   nonzero  4/30    largest junk coefficient 0.000   <- exactly zero

So the choice is not about which regularises better. Use L2 when you believe most features contribute a little, which is the usual case and the safer default. Use L1 when you believe most do not and you want the model to tell you which, accepting that with correlated features it picks one of each group arbitrarily. ElasticNet mixes both and exists mainly to soften that arbitrariness.

How a tree splits#

At each node the tree tries every feature and every threshold and picks the split that makes the two resulting groups purest. For classification purity is usually measured by Gini impurity or entropy; for regression, by reduction in variance. It repeats until a stopping rule.

Node: 100 samples, 50 positive  (impurity high)

Split on age < 30:
  left   40 samples, 35 positive   (purer)
  right  60 samples, 15 positive   (purer)

Chosen because it reduced impurity more than any other split.

Gini and entropy almost always choose the same split, and the difference is not worth an argument: Gini is the default because it avoids a logarithm. The consequence worth knowing is a bias in the search itself. Trying every threshold means a feature with a thousand distinct values gets a thousand chances to look good by luck, while a binary feature gets one. Tree feature importances therefore favour high-cardinality columns, which is why an id column left in the data will appear near the top of the importance list having taught the model nothing.

Why boosting works#

Each new tree is fitted to the errors the ensemble currently makes, specifically to the gradient of the loss. The ensemble moves step by step towards lower loss, which is gradient descent in the space of functions. A small learning rate and many trees beats a large rate and few, at the cost of time.

That explains why boosting and bagging fix opposite problems, which is the thing to be able to say. A deep tree has low bias and high variance: it can represent anything and is wildly sensitive to which rows it saw. Averaging hundreds of them, as a forest does, leaves the bias alone and cancels the variance. A stump has the reverse problem, high bias and low variance, and boosting drives that bias down one correction at a time. Both arrive somewhere good from opposite directions.

from sklearn.tree import DecisionTreeRegressor
from sklearn.ensemble import RandomForestRegressor, HistGradientBoostingRegressor
from sklearn.model_selection import train_test_split

X2 = rng.uniform(-3, 3, (600, 1))
y2 = np.sin(X2[:, 0] * 2) + 0.3 * X2[:, 0] ** 2 + rng.normal(0, 0.2, 600)
Xtr, Xte, ytr, yte = train_test_split(X2, y2, test_size=0.3, random_state=0)

for name, m in [
    ("stump (depth 1)",      DecisionTreeRegressor(max_depth=1)),
    ("deep tree",            DecisionTreeRegressor()),
    ("forest of deep trees", RandomForestRegressor(n_estimators=300, random_state=0)),
    ("boosted stumps",       HistGradientBoostingRegressor(
                                 max_depth=1, max_iter=300,
                                 early_stopping=False, random_state=0)),
]:
    m.fit(Xtr, ytr)
    print(name, round(np.mean((ytr - m.predict(Xtr)) ** 2), 4),
                round(np.mean((yte - m.predict(Xte)) ** 2), 4))

# stump (depth 1)        train 0.5619  test 0.5512   high bias: wrong on train too
# deep tree              train 0.0000  test 0.0810   high variance: perfect on train, not on test
# forest of deep trees   train 0.0089  test 0.0588   averaging killed the variance
# boosted stumps         train 0.0507  test 0.0674   correcting killed the bias

Support vector machines#

An SVM draws the boundary that sits as far as possible from the nearest point of either class, and that widest-gap criterion is what distinguishes it from logistic regression, which will accept any boundary that separates the classes. Only the points on the edge of the gap, the support vectors, affect the answer; move a point deep inside its own class and the boundary does not shift.

The kernel trick is what made them famous. Instead of building the non-linear features explicitly, an SVM only ever needs the dot product between pairs of points, so you can substitute a function that returns what the dot product would have been in a much larger space without ever going there. An RBF kernel corresponds to an infinite-dimensional space, computed in one line. C controls how much misclassification is tolerated for a wider margin, gamma how local the RBF kernel's influence is, and getting both wrong is the usual reason an SVM disappoints.

The reason they are no longer a first choice is cost: fitting is between quadratic and cubic in the number of rows, so past roughly fifty thousand examples they stop being practical while boosting barely notices. They remain a sensible choice on a few hundred rows with many features, such as a small text classification problem, where trees struggle and there is not enough data for anything deeper.

K-nearest neighbours#

Store the training data. To predict, find the k closest examples and take their majority vote or their mean. There is no fitting step at all, which makes it the fastest model to train and the slowest to use: every prediction is a search over the whole training set, so the cost moves from a one-off to every request you ever serve.

It fails in high dimensions, and not gently. As dimensions grow, the distances between random points converge on each other, so the nearest neighbour stops being meaningfully nearer than the farthest and the vote becomes noise. This is the concrete form of the curse of dimensionality, and it is worth measuring once rather than believing on authority.

from scipy.spatial.distance import pdist      # scipy ships with scikit-learn

for d in (2, 10, 100, 1000):
    P = np.random.default_rng(0).normal(0, 1, (500, d))
    dists = pdist(P)
    print(d, round(dists.min() / dists.max(), 3))

# d=2      nearest / farthest = 0.001    neighbours mean something
# d=10     nearest / farthest = 0.108
# d=100    nearest / farthest = 0.504
# d=1000   nearest / farthest = 0.833    the nearest point is nearly as far as the farthest

Two things follow. Distances must be scaled, or the feature measured in metres silently outvotes the one measured in kilometres. And kNN is the conceptual ancestor of vector search: an embedding model's job is precisely to produce a space where nearness means similarity, so that this algorithm starts working again in a thousand dimensions.