Machine Learning Techniques

The core algorithms of classical machine learning, built from first principles: PCA and kernel PCA, k-means, maximum likelihood, Gaussian mixtures and EM, linear, ridge and lasso regression, kNN and decision trees, naive Bayes, the perceptron, logistic regression, support vector machines, bagging, boosting and a first look at neural networks.

Undergrad and Professional · English · 35 chapters

• Course Overview
• What Is Machine Learning? — Machine learning is not a fixed procedure, not memorisation and not magic. It is the use of data to build models that generalise to examples they have never seen, using linear algebra for structure, probability for uncertainty and optimisation for decisions.
• Paradigms of Machine Learning — Supervised learning has labels, unsupervised learning has none, and sequential learning gets its feedback one decision at a time. This chapter maps the main problem types (classification, regression, clustering, representation learning, online learning, bandits and reinforcement learning) and places familiar applications into them.
• Representation Learning: Compression as Understanding — If data points lie along a line, a representative vector and one coefficient per point describe them exactly. Real data never lies exactly on a line, so we replace each point by its projection (its closest proxy on the line) and look for the line that loses the least. Repeating on the leftovers gives a sequence of directions.
• Principal Component Analysis — Minimising reconstruction error over unit directions is the same as maximising the variance of the projections, and both are solved by the top eigenvector of the covariance matrix. Repeating on the residuals gives an orthonormal basis of eigenvectors; the eigenvalues measure how much variance each direction keeps, which tells you how many to retain.
• PCA in Practice: Eigenfaces and Two Limits — Eigenfaces show PCA compressing face images a hundredfold. They also expose two limits: eigen-decomposing a d×d covariance matrix is too slow when d is huge, and PCA only finds linear structure. The first is fixed by working with the n×n matrix of dot products XᵀX, which quietly sets up the fix for the second.
• Feature Maps and Kernels — Curved structure becomes linear after mapping each point to a richer feature space, but that space can be astronomically large. A kernel computes the dot product in the feature space directly from the original vectors. Polynomial and RBF kernels are the standard examples, and Mercer's condition tells you which functions are valid kernels.
• Kernel PCA — Kernel PCA runs PCA in a kernel's feature space using only the n×n kernel matrix: centre it, eigen-decompose it, rescale the eigenvectors, and read each point's coordinates off its row of the kernel matrix. The principal directions themselves are never built, but the projections onto them are all a downstream task needs.
• Clustering and the K-Means Objective — Clustering partitions n points into K groups. Scoring a partition by the total squared distance of points to their cluster means gives the k-means objective, which is NP-hard to minimise exactly. Lloyd's algorithm (assign each point to its nearest mean, recompute the means, repeat) is the standard heuristic.
• Why K-Means Converges, and the Shape of Its Clusters — Every reassignment strictly lowers the k-means objective, and there are finitely many partitions, so Lloyd's algorithm must stop, though possibly at a local optimum. At convergence each cluster is the set of points nearer its mean than any other mean: a Voronoi region bounded by perpendicular bisectors, which is why k-means cannot find ring-shaped clusters.
• Starting K-Means and Choosing K — Starting centres matter because Lloyd's algorithm stops at a local optimum: pick random data points and keep the best of several runs, or use k-means++, which spreads the starting centres out by sampling in proportion to squared distance and comes with an O(log K) guarantee. To choose K, the objective alone always prefers more clusters, so add a penalty (the elbow, AIC or BIC).
• Estimation and Maximum Likelihood — Estimation assumes a probabilistic mechanism generated the data and uses the data to infer its unknown parameters. Under the i.i.d. assumption, maximum likelihood picks the parameter that makes the observed data most probable: the fraction of heads for a coin, the sample mean and the (1/n) sample variance for a Gaussian.
• Bayesian Estimation — Bayesian estimation treats the unknown parameter as a random variable with a prior distribution and updates it to a posterior with Bayes' rule. For a coin, a Beta prior gives a Beta posterior that simply adds the observed heads and tails to pseudo-counts. The posterior mean or mode smooths the maximum likelihood estimate and avoids its overconfidence on small samples.
• Gaussian Mixture Models — A Gaussian mixture model explains multimodal data with a generative story: pick a component with probability π_k, then draw from that component's Gaussian. The hidden component choice is a latent variable. Summing it out gives a log-likelihood with a log of a sum, which has no closed-form maximiser, so a new algorithm is needed.
• The EM Algorithm — Jensen's inequality turns the GMM's log-of-a-sum into a lower bound that is easy to maximise. Expectation-maximisation alternates two steps: the E step sets the bound to touch the log-likelihood by computing responsibilities, and the M step maximises the bound with weighted means, variances and proportions. The likelihood never decreases, and k-means is the hard-assignment limit.
• Linear Regression and Least Squares — Supervised learning adds a label to each point. Regression predicts a real-valued label with a function chosen from a family; linear regression uses w·x and scores it by squared error. Setting the gradient of the squared error to zero gives the normal equations and the closed form w* = (XXᵀ)⁻¹Xy. Low training error alone can mean overfitting.
• The Geometry of Least Squares and Gradient Descent — Least squares projects the label vector onto the subspace spanned by the feature rows, so the residual is orthogonal to every feature. When inverting XXᵀ is too costly, gradient descent walks downhill on the squared error instead; stochastic gradient descent uses one point or a small batch per step, trading noisy steps for cheap ones.
• Kernel Regression — The least-squares weights are always a combination of the training points, w* = Xα. Substituting turns training and prediction into operations on dot products only, so a kernel can replace them: predictions become f(x) = Σ αᵢ k(xᵢ, x), with α found from the n×n kernel matrix. In practice a ridge term, α = (K + λI)⁻¹y, keeps the fit stable.
• Regression as Estimation, and Cross-Validation — Assume labels are a linear function plus Gaussian noise: maximum likelihood then gives exactly least squares. Treating ŵ as an estimator, it is unbiased, and its mean squared error is σ² times the trace of (XXᵀ)⁻¹, which blows up when features are nearly dependent. Choosing between models needs an honest estimate of error on new data: cross-validation.
• Ridge and Lasso Regression — Ridge regression adds λ‖w‖² to the squared error: the MAP estimate under a Gaussian prior, with closed form (XXᵀ + λI)⁻¹Xy, which shrinks every weight and cures collinearity. Lasso adds λ‖w‖₁ instead: a Laplace prior, no closed form, and the corners of the L1 ball push many weights to exactly zero, so it selects features.
• Binary Classification and k-Nearest Neighbours — Binary classification predicts a label in {−1, +1} and is judged by the 0-1 loss. Minimising it directly over linear classifiers is NP-hard, and regression on ±1 labels is a poor substitute. k-nearest neighbours avoids training altogether: it labels a point by majority vote among its k closest training points, with k trading noise sensitivity against smoothness.
• Decision Trees — A decision tree asks one yes-or-no question about one feature at each node and predicts at the leaves. Questions are chosen greedily to maximise information gain, the drop in entropy (or Gini impurity) of the labels. Trees split the space into axis-aligned boxes, are easy to read, and overfit unless their depth or leaf size is limited or they are pruned.
• Generative and Discriminative Models — A discriminative model learns P(y | x) or the decision boundary directly. A generative model learns how each class produces its data, P(x | y), together with P(y), and classifies with Bayes' rule. For binary feature vectors a full generative model needs 2ᵈ parameters per class, which is hopeless; an independence assumption brings it down to d.
• Naive Bayes — Naive Bayes estimates each class's prior and per-feature probabilities by counting, then classifies with Bayes' rule in log space. A word never seen in one class gets probability zero and vetoes that class, which Laplace smoothing fixes by adding pseudo-counts. For binary features its decision function is linear: a weighted vote of log-odds, one per feature.
• Gaussian Naive Bayes — For real-valued features, model each feature within each class as a Gaussian and estimate its mean and variance by maximum likelihood. Classifying by the larger posterior gives a quadratic boundary in general; when the classes share their variances the quadratic terms cancel and the boundary is linear, the same family as logistic regression.
• The Perceptron — The perceptron learns a linear classifier sign(w·x) by cycling through the data and adding y·x to w whenever it makes a mistake. If the data is linearly separable with margin γ and radius R, it makes at most (R/γ)² mistakes before separating it perfectly; if not, it never settles.
• Logistic Regression — Logistic regression models P(y = 1 | x) as the sigmoid of w·x, so the score's sign gives the class and its size the confidence. Maximum likelihood gives the cross-entropy (log) loss, which is convex but has no closed-form minimiser; gradient descent uses the gradient Σ(σ(w·xᵢ) − yᵢ)xᵢ. On separable data the weights grow without bound unless regularised.
• The Maximum-Margin Classifier — Of all the hyperplanes that separate the data, choose the one with the widest margin. Fixing the scale so the closest points satisfy y(w·x + b) = 1 makes the margin 2/‖w‖, so maximising it becomes the convex problem: minimise ½‖w‖² subject to yᵢ(w·xᵢ + b) ≥ 1. Only the points on the margin determine the answer.
• The Dual Problem, Support Vectors and Kernels — Lagrange multipliers turn the margin problem into its dual: maximise Σαᵢ − ½ΣΣ αᵢαⱼyᵢyⱼ xᵢ·xⱼ with αᵢ ≥ 0 and Σαᵢyᵢ = 0. The solution is w = Σαᵢyᵢxᵢ, complementary slackness makes αᵢ non-zero only for support vectors, and because the data enters only through dot products, any kernel can replace them.
• The Soft-Margin SVM — Slack variables ξᵢ let points sit inside the margin or on the wrong side at a cost C·Σξᵢ, so the SVM works on non-separable data. Its dual is the hard-margin dual with the box constraint 0 ≤ αᵢ ≤ C. Complementary slackness sorts the points into three groups: outside the margin (α = 0), on it (0 < α < C) and inside it (α = C). The whole thing is hinge-loss minimisation with an L2 penalty.
• Bias, Variance, Bagging and Random Forests — Test error splits into bias (a model too simple), variance (a model too sensitive to its sample) and noise. Averaging many models cuts variance, and bootstrap resamples make that possible from one data set: bagging. Deep trees have low bias and high variance, so they gain the most; random forests also restrict each split to a random subset of features, decorrelating the trees so the average helps even more.
• Boosting — Boosting builds an ensemble sequentially: each weak learner is trained on reweighted data that emphasises the points its predecessors got wrong, and the final classifier is a weighted vote. AdaBoost's weights αₜ = ½ln((1 − εₜ)/εₜ) come from minimising the exponential loss, its training error falls exponentially fast, and unlike bagging it mainly reduces bias.
• One View of Every Classification Loss — Write every binary classifier's loss as a function of the margin m = y·f(x). The 0-1 loss is what we want but cannot optimise. The perceptron, hinge (SVM), logistic and exponential (AdaBoost) losses are convex surrogates that differ in how they treat correct-but-close points and confident mistakes. Squared loss even penalises points that are too correct.
• From Perceptrons to Neural Networks — A neural network stacks layers of linear maps and non-linear activations, so it learns its own features instead of relying on a fixed kernel. One hidden layer already solves XOR, and wide enough networks can approximate any continuous function. The parameters are learned by gradient descent on a loss, with backpropagation computing the gradients layer by layer via the chain rule.
• Summary and Where to Go Next — A map of the whole course: the unsupervised methods (PCA, kernel PCA, k-means, Gaussian mixtures with EM) and the supervised ones (regression, kNN, trees, naive Bayes, the perceptron, logistic regression, SVMs, ensembles, neural networks), the ideas that tie them together, how to choose among them, and the topics this course did not cover.