Chrysolites Tech Academy

Machine Learning Fundamentals · Course book

Chapter 2: How the Classic Algorithms Work

Pairs with Lesson 2: Machine Learning Algorithms in Depth

Using a machine learning library is easy; knowing what it is doing is what lets you choose the right model, diagnose a poor result and explain a prediction to someone else. This chapter goes beneath the surface of the classic algorithms. It starts with the two ways to fit a linear model, a formula that solves it in one step and gradient descent that walks towards the answer, and shows how regularisation stops a model from fitting noise. It then explains the bias and variance trade-off that sits behind every modelling decision, the geometry of support vector machines and kernels, and the steps of principal component analysis. The final sections build decision trees from entropy and Gini impurity, combine them into ensembles, and close with clustering. Each idea is backed by numbers you can reproduce with a pencil.

Fitting a linear model two ways

Linear regression predicts a number as a weighted sum of the features plus a constant. The function that makes predictions is called the hypothesis, written h(x) = w0 + w1x1 + … + wnxn. The quality of a set of weights is measured by a cost function, usually the mean squared error: the average, over all training rows, of (prediction − label)2. Squaring makes every error positive and punishes large errors far more than small ones.

The first way to find the best weights is the closed-form solution, also called the normal equation. Stacking the features into a matrix X, with a column of ones for the constant, and the labels into a vector y, the weights that minimise the squared error are w = (XTX)−1XTy. It gives the exact answer in one calculation, with no settings to tune. Its weakness is cost: inverting the matrix grows roughly with the cube of the number of features, so with tens of thousands of features it becomes slow, and it does not apply to models such as logistic regression that have no closed form.

The second way is gradient descent. Start with any weights, compute the gradient, which is the slope of the cost with respect to each weight, and move every weight a small step downhill. The step size is the learning rate. Too small and training crawls; too large and the weights overshoot the minimum and the cost can grow instead of shrink.

Worked example. Fit y = wx to the points (1, 2), (2, 4) and (3, 6) using mean squared error. The gradient of the cost with respect to w is the average of 2(wx − y)x. Start at w = 0 with a learning rate of 0.05. The cost is (4 + 16 + 36) / 3 = 18.67 and the gradient is −18.67, so the new weight is 0 + 0.05 × 18.67 = 0.933. Repeating, w moves to 1.431, 1.697, 1.838 and 1.914, and the cost falls from 18.67 to 5.31, 1.51, 0.43, 0.12 and 0.035. Each step closes about 47 percent of the remaining gap to the true answer, w = 2.
18.675.311.51 012345 20100 iterationcost (mean squared error)
Figure 2.1 — Cost falling during gradient descent in the worked example. Big early gains give way to small refinements as the weight nears its best value.

Linear regression rests on assumptions: the relationship really is roughly linear, errors are independent and have similar spread across the range, and features are not near-copies of one another. It is fast, easy to explain and a strong baseline, but it cannot capture curves without extra engineered features, and outliers pull the line towards them because of the squared error.

Overfitting, regularisation and the bias and variance trade-off

A model underfits when it is too simple to capture the pattern, so it does badly even on training data. It overfits when it is so flexible that it learns the noise in the training data too, scoring brilliantly in training and poorly on new data. The language for this is bias and variance. Bias is the error that comes from wrong assumptions, such as forcing a straight line through a curve. Variance is the error that comes from sensitivity to the particular training sample: train on a slightly different sample and a high-variance model changes a lot. Making a model more complex usually lowers bias and raises variance, so the best model sits in the middle.

Learning theory frames training as empirical risk minimisation: we cannot measure the error over every possible future example, the true risk, so we minimise the average error on the sample we have, the empirical risk, and hope the two are close. The gap between them grows when the model family is very flexible compared with the amount of data, which is the formal version of overfitting.

Regularisation narrows that gap by adding a penalty on large weights to the cost. Ridge regression adds λ times the sum of squared weights, which shrinks all weights smoothly towards zero. Lasso regression adds λ times the sum of absolute weights, which can push some weights to exactly zero, effectively selecting features. The strength λ is chosen with a validation set: λ = 0 is ordinary regression, and a very large λ forces every weight towards zero and underfits.

Classifiers with margins and probabilities

Logistic regression keeps the weighted sum but passes it through the sigmoid function to produce a probability between 0 and 1. Mean squared error works badly here, so it uses log loss instead: for a positive example the cost is −log(p), and for a negative one −log(1 − p). Predicting 0.9 for a true positive costs only 0.105 (using natural logarithms), while predicting 0.1 costs 2.303, so confident mistakes are punished hard. There is no closed form, so the weights are found with gradient descent.

A support vector machine chooses the boundary with the widest margin to the nearest points of each class. A hard margin insists that every training point is on the correct side, which fails if even one point is mislabelled. A soft margin allows some points inside the margin or on the wrong side, paying a penalty controlled by a parameter usually called C: a large C tolerates few violations and risks overfitting, while a small C accepts more for a wider, smoother boundary.

When no straight boundary exists, a kernel computes similarities as though the points had been mapped into a richer space. A polynomial kernel corresponds to adding products and powers of the features; the homogeneous form has no constant term and the inhomogeneous form adds one, which brings in lower-degree terms too. The radial basis function (RBF) kernel measures similarity by distance, so points close together count as very similar, and it can carve out curved, island-shaped regions. The optimisation can be written in a primal form over the weights or a dual form over one coefficient per training point; the dual is where kernels fit in naturally. The same margin idea extends to regression as support vector regression, which ignores errors smaller than a chosen tolerance and penalises only those beyond it.

Principal component analysis step by step

Datasets with many features are slow to model, hard to visualise and prone to overfitting, a set of problems often called the curse of dimensionality. Principal component analysis finds new axes, combinations of the original features, ordered by how much of the data's variation they capture. The recipe has five steps.

  1. Standardise each feature to mean 0 and standard deviation 1, so features measured in large units do not dominate.
  2. Compute the covariance matrix, which records how every pair of features varies together.
  3. Find its eigenvectors and eigenvalues. Each eigenvector is a direction; its eigenvalue is the variance of the data along that direction.
  4. Sort the eigenvalues from largest to smallest and compute the cumulative energy: the running total divided by the sum of all eigenvalues. Keep enough components to reach a target such as 90 percent.
  5. Project the data onto the kept eigenvectors. Projecting back with the same vectors gives an approximate reconstruction of the original data.

For example, if four eigenvalues are 2.5, 1.0, 0.3 and 0.2, they sum to 4.0. The first component holds 2.5 / 4.0 = 62.5 percent of the variance, the first two together hold 3.5 / 4.0 = 87.5 percent and the first three hold 3.8 / 4.0 = 95 percent. To keep at least 90 percent you would keep three components and drop one.

Decision trees and ensembles

A decision tree asks a sequence of yes-or-no questions about the features, such as "is age over 40?", and each leaf holds a prediction. Training chooses, at each node, the question that best separates the classes. Two common measures of how mixed a group is are entropy, the sum of −p log2 p over the classes, and Gini impurity, one minus the sum of the squared class proportions. Both are zero for a pure group.

Worked example. A node holds 10 rows: 6 "yes" and 4 "no". Its entropy is −0.6 log2 0.6 − 0.4 log2 0.4 = 0.971 and its Gini impurity is 1 − 0.36 − 0.16 = 0.48. A candidate split sends 4 rows, all "yes", left and 6 rows, 2 "yes" and 4 "no", right. The left entropy is 0; the right is 0.918. The weighted entropy after the split is 0.4 × 0 + 0.6 × 0.918 = 0.551, so the information gain is 0.971 − 0.551 = 0.420. Using Gini instead, the right side scores 1 − (1/3)2 − (2/3)2 = 0.444, the weighted impurity falls from 0.48 to 0.267, and the tree compares this drop against every other possible split.

Trees grown without limits memorise the training data, so hyperparameters such as maximum depth and minimum rows per leaf are tuned on validation data. A more powerful fix is to combine many models, an approach called ensemble learning.

MethodHow the models are builtHow predictions are combinedMain effect
BaggingIn parallel, each on a random resample of the rowsVote or averageReduces variance
Random forestBagging, plus a random subset of features at each splitVote or averageReduces variance further by making trees differ
AdaBoostIn sequence, giving more weight to rows earlier models got wrongWeighted voteReduces bias
Gradient boosting and XGBoostIn sequence, each new tree fitted to the remaining errorsSum of all treesReduces bias; XGBoost adds regularisation and speed
StackingDifferent model types trained side by sideA second model learns how to combine themExploits each model's strengths
CascadingModels in a chain, where later models handle cases earlier ones were unsure aboutFirst confident answerFast decisions for easy cases

Unsupervised learning has its own toolkit. K-means is sensitive to where its starting centres are placed, so k-means++ chooses them carefully: the first at random and each later one with a probability that grows with its distance from the centres already chosen, which spreads them out. Hierarchical clustering instead builds a tree of clusters, either starting from single points and repeatedly merging the closest pair, or starting from one big group and repeatedly splitting it, so you can choose the number of clusters afterwards by cutting the tree at a chosen height.

Practice tasks

  1. Continue the gradient descent worked example for two more steps from w = 1.914. What are the next two weights, and roughly what fraction of the remaining gap does each step close?
  2. Repeat the worked example with a learning rate of 0.2. What happens to w after the first two steps, and why?
  3. A node holds 8 rows, 4 of each class. Compute its entropy and Gini impurity, then the information gain of a split that produces groups of (3 yes, 1 no) and (1 yes, 3 no).
  4. Five eigenvalues are 4.0, 3.0, 1.5, 1.0 and 0.5. How many components must you keep to retain at least 80 percent of the variance?
  5. Explain the difference between ridge and lasso regression, and describe a situation where lasso's ability to zero out weights would be useful.
  6. For each ensemble method in the table, say whether its models are trained in parallel or in sequence, and whether it mainly attacks bias or variance.

Install Chrysolites Tech Academy

Android / Chrome / Edge: open the browser menu and choose Install app or Add to Home screen.

iPhone / iPad (Safari): tap the Share button, then Add to Home Screen.