194.025 Introduction to Machine Learning

• Machine Learning
• Learning Paradigms:
  • Supervised Learning
    • Classification
    • Regression
  • Unsupervised Learning
  • Semi-Supervised Learning
  • Self-Supervised Learning
  • Reinforcement Learning
  • Transfer Learning
  • Active Learning
  • Passive Learning
  • Online Learning
  • Batch Learning
  • Representation Learning
• Learning Methods:
  • Distance-based Learning
    • Manhattan Distance
    • Euclidean Distance
    • Minkowski Distance
    • Levenshtein Distance
    • Cosine Similarity
  • Linear Regression
  • Polynomial Regression
  • Multiple Polynomial Regression
  • Linear Classification
    • Binary Linear Classifier
    • Perceptron
    • Kernel Perceptron
    • Logistic Regression
    • Support Vector Machine (SVM)
  • Decision Trees
  • Bayesian Learning
  • Multiclass Classification
• Kernel Methods:
  • Kernel Function
  • Gram Matrix
  • Hinge Loss
  • Common Kernels:
    • Linear Kernel
    • Polynomial Kernel
    • Gaussian RBF Kernel
  • Ensemble Learning
    • Bagging
    • Boosting
  • Artificial Neural Networks (ANN)
    • Multi-Layer Perceptron (MLP)
    • Deep Neural Networks
    • Activation Functions
      • Sigmoid
      • tanh
      • Rectified Linear Unit (ReLU)
    • Backpropagation
    • Cross-Entropy Loss
    • Universal Function Approximation
    • Transformers
• Dimensionality Reduction:
  • Dimensionality Reduction
• Risk and Evaluation:
  • ML Evaluation
  • Empirical Risk
  • True Risk
  • Underfitting
  • Overfitting
  • Bias-Variance Tradeoff
  • Dataset Splitting
  • k-fold Cross-Validation
  • Baselines
  • Student-t Test
  • Metrics:
    • MAE
    • RMSE
    • Confusion Matrix
    • Accuracy
    • Precision
    • Sensitivity
    • F1-Score
• Probabilistic Machine Learning:
  • Bayes Optimal Classifier
  • Discriminative Learning
  • Generative Learning
  • Inference and Estimation:
    • Maximum Likelihood Estimation (MLE)
    • Maximum a Posteriori Estimation (MAP)
    • Posterior Predictive Distribution
  • Probabilistic Graphical Models:
    • Bayesian Network
    • Naive Bayes
• Optimisation:
  • Gradient Descent
  • Gradient Checking
  • Normal Equations
  • Regularisation
    • L1 Regularisation
    • L2 Regularisation
  • Hyperparameters
  • Hyperparameter Tuning
• Fundamental Assumptions:
  • I.I.D. Assumption
  • Realisability Assumption
  • Cluster Assumption
  • Manifold Assumption
• Learning Theory:
  • Hypothesis Class
  • Consistent Hypothesis
  • PAC Learning
  • PAC-Learnable Class
  • Sample Complexity
  • Generalisation Bound
  • Rademacher Complexity
  • Shattering
  • VC Dimension
• Mathematical Foundations:
  • Eigenvalue
  • Eigenvector
  • Convex Function
  • Basis Function
  • Lagrange Multipliers
  • Dual Problem
  • KL Divergence
• Graph Representations:
  • Adjacency List
  • Adjacency Matrix
  • Adjacency Set
  • Weisfeiler-Leman Algorithm
  • Weisfeiler-Leman Graph Kernel
• Bias and Fairness:
  • Ethical AI
• Data Analysis:
  • Data Modality
  • Exploratory Data Analysis (EDA)
  • Feature Engineering
• Data Preprocessing:
  • Independent Feature Scaling
  • Min-Max Scaling
  • Mean Normalisation
  • Standardisation
  • One-Hot Encoding
  • Imputation
• Data Types:
  • Numerical Data
  • Categorical Data
    • Nominal Data
    • Ordinal Data
  • Image Data
  • Text Data

---

Lecture 1 Overview and Mathematical Framing

This lecture positions machine learning as a mathematical discipline for constructing predictors from data under uncertainty. The central object is a mapping $h:\mathcal{X}\to \mathcal{Y}$ selected from a hypothesis class $\mathcal{H}$, with performance evaluated relative to an unknown data-generating distribution $P$.

Problem Formulation

Let $(X,Y)\sim P$ with input space $\mathcal{X}$ and label space $\mathcal{Y}$. A training sample is

$$S=\{(x_i,y_i){\}}_{i=1}^n\sim P^n,$$

with the standard i.i.d. assumption. Learning is the task of selecting

$$\hat{h}\in \mathcal{H}$$

such that generalisation to unseen draws from $P$ is good.

In the classification setting with 0-1 loss,

$$L(\hat{h}(x),y)=1\{\hat{h}(x)\ne y\},$$

the true risk and empirical risk are

$$R_P(h)=\underset{(x,y)\sim P}{\mathrm{Pr}}(h(x)\ne y),R_S(h)=\frac{1}{n}\sum _{i=1}^{n}1\{h(x_i)\ne y_i\}.$$

The course repeatedly studies the gap between these two quantities and conditions under which minimising $R_S$ controls $R_P$.

Conceptual Position of Machine Learning

The opening slides place ML at the interface of statistics, optimisation, pattern recognition, data mining, and AI. A useful operational distinction is:

• data mining emphasises extraction of structure from existing data;
• machine learning emphasises construction of predictive rules with explicit generalisation goals.

This distinction is not absolute, but exam questions typically expect you to articulate learning in terms of hypotheses, loss, distributions, and guarantees.

Historical Arc and Methodological Consequence

The historical timeline (Bayes, Markov, perceptron, PAC, SVM, deep learning, transformers) motivates a recurring pattern: representational power, optimisation tractability, and statistical guarantees must be balanced. The modern toolkit is best understood as combinations of these three axes rather than as isolated algorithms.

Perceptron as Canonical Linear Learner

For binary labels $y_t\in \{-1,+1\}$ and inputs $x^{(t)}\in {\mathbb{R}}^d$, the perceptron predicts

$$f_t(x)=\mathrm{sign}(⟨w^{(t)},x⟩).$$

Given example $(x^{(t)},y_t)$, the update is

$$w^{(t+1)}=\{\begin{array}{ll}{w}^{(t)}& \text{if }{f}_t(x^{(t)})=y_t,\\ w^{(t)}+y_t{x}^{(t)}& \text{otherwise}.\end{array}$$

Equivalent mistake form:

$$⟨x^{(t)},w^{(t+1)}⟩=⟨x^{(t)},w^{(t)}⟩+y_t\Vert x^{(t)}{\Vert }^2.$$

Interpretation: each mistake moves the separating hyperplane towards correct classification of the current point.

Noise, Plausible Hypotheses, and Margin Principle

The geometric sequence of slides illustrates:

• with low noise, many linear separators can interpolate the sample;
• with increasing noise, the set of plausible separators contracts;
• maximum-margin selection yields a robust separator by maximising the minimum signed distance to training points.

This motivates support vector machines and, more generally, the role of inductive bias in choosing one predictor among many empirically adequate ones.

Expressivity Limits and Non-Linearity

Linear threshold functions can represent AND/OR-type concepts but fail on XOR in the original input space. Two standard remedies are introduced:

1. Kernel lifting: linear separation in a feature space $\varphi (x)$ via inner products $k(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime })⟩$.
2. Multi-layer perceptron composition: stacked affine maps and non-linear activations to realise non-linear decision boundaries.

This is the first appearance of the representation trick: make the task linearly simple in a transformed space.

Toy Generalisation Guarantee from Threshold Learning

The airport suitcase example instantiates one-dimensional threshold learning. Let ${\theta }^{\ast }$ denote the true threshold and $\hat{\theta }$ the learned threshold from $n$ i.i.d. examples. Suppose the disagreement region between ${\theta }^{\ast }$ and $\hat{\theta }$ has probability mass $\epsilon$.

An error larger than $\epsilon$ occurs only if no training point falls inside that disagreement region. Hence

$$\mathrm{Pr}(\text{bad event})=(1-\epsilon {)}^n.$$

Using $(1-\epsilon {)}^n\le e^{-\epsilon n}$, it suffices to require

$$e^{-\epsilon n}\le \delta ⟺n\ge \frac{1}{\epsilon }\ln \frac{1}{\delta }.$$

Therefore,

$$\mathrm{Pr}(R_P(\hat{h})\le \epsilon )\ge 1-\delta$$

for $n$ above the bound. This is the core PAC-style sample-complexity template that recurs throughout the course.

Exam-Oriented Takeaways

You should be able to reconstruct without notes:

1. the formal learning setup $(\mathcal{X},\mathcal{Y},P,\mathcal{H},L)$;
2. perceptron prediction and update equations;
3. why linear models fail on XOR and how kernels/layers address this;
4. the threshold-learning bound $n\ge \frac{1}{\epsilon }\ln \frac{1}{\delta }$ from $(1-\epsilon {)}^n$.

These four items are the mathematical backbone of the introductory lecture and connect directly to later topics in PAC learning, sample complexity, generalisation bounds, and VC dimension.

Lecture 2 Data and (Pre-)Processing

This lecture formalises the pipeline from raw observations to vector representations suitable for learning algorithms. The core principle is that model quality is bounded by representation quality: if the data map is inadequate, no downstream optimiser can recover the lost structure.

Data Model and Data Types

Let a dataset be written as

$$X=\{x_i{\}}_{i=1}^n,x_i\in \mathcal{X},$$

with optional labels $y_i\in \mathcal{Y}$. The feature space $\mathcal{X}$ may be heterogeneous, combining numeric, categorical, textual, image, or graph-valued attributes. In practice, most classical learners require an embedding

$$\varphi :\mathcal{X}\to {\mathbb{R}}^d$$

that preserves task-relevant structure.

Numeric attributes are either discrete or continuous. Categorical attributes are nominal (unordered) or ordinal (ordered). This distinction determines admissible pre-processing: ordinal variables may be relabelled monotonically, while nominal variables require non-ordinal encodings such as one-hot encoding.

Data Analysis Before Pre-Processing

Pre-processing starts with exploratory data analysis rather than immediate transformation. For each feature one should inspect scale, missingness, outliers, and empirical distribution. The minimal summary comprises median and quantiles (5-number summary), mean, variance/standard deviation, and pairwise dependency diagnostics (e.g. correlation matrices for numeric attributes).

The statistical purpose is to estimate whether a transformation will improve numerical conditioning and comparability across features.

Numeric Pre-Processing and Scaling Maps

Let $x_{ij}$ denote feature $j$ of example $i$. Scaling is performed per feature (column-wise), not globally across all coordinates.

For feature $j$, define

$$m_j=\underset{i}{\min }{x}_{ij},M_j=\underset{i}{\max }{x}_{ij},{\mu }_j=\frac{1}{n}\sum _{i=1}^n{x}_{ij},{\sigma }_j^2=\frac{1}{n}\sum _{i=1}^n(x_{ij}-{\mu }_j{)}^2.$$

The main transforms are:

$$\text{min-max to }[0,1]:x_{ij}^{\prime }=\frac{x_{ij}-m_j}{M_j-m_j},$$ $$\text{min-max to }[a,b]:x_{ij}^{\prime }=a+\frac{x_{ij}-m_j}{M_j-m_j}(b-a),$$ $$\text{mean normalisation}:x_{ij}^{\prime }=\frac{x_{ij}-{\mu }_j}{M_j-m_j},$$ $$\text{standardisation}:x_{ij}^{\prime }=\frac{x_{ij}-{\mu }_j}{{\sigma }_j}.$$

Standardisation is typically preferred for gradient-based models and margin-based methods because it centres and rescales coordinates to comparable magnitudes.

Categorical and String Encodings

For a nominal feature with alphabet $\mathcal{A}=\{a_1,\dots ,a_k\}$, one-hot encoding defines

$$\psi (a_r)=e_r\in \{0,1{\}}^k,$$

where $e_r$ is the $r$-th standard basis vector. Missing categories are represented either by a dedicated “unknown” symbol or by imputation before encoding.

The same principle extends to strings at symbol level: with alphabet $\Sigma$, each symbol maps to a one-hot vector in $\{0,1{\}}^{|\Sigma |}$. Concatenating symbol vectors yields a sparse representation. Word-level encodings in text follow the same algebraic idea, with vocabulary size replacing alphabet size.

Image and Text Feature Construction

For images, a traditional pipeline is: geometric/photometric pre-processing (resize, greyscale, augmentation), followed by feature extraction (e.g. HOG/SIFT/SURF). Deep architectures instead consume tensor-valued pixel arrays directly and learn feature maps end-to-end.

For text, a basic pipeline is token normalisation, stop-word handling, stemming/lemmatisation, then vectorisation (TF, TF-IDF, BM25, neural embeddings). The key geometric fact is sparsity: bag-of-words vectors live in high-dimensional spaces with mostly zero coordinates.

Distances as Inductive Geometry

Distance-based methods induce neighbourhood structure. A map $d:\mathcal{X}\times \mathcal{X}\to {\mathbb{R}}_{\ge 0}$ is a metric if for all $x,u,v$:

$$d(x,v)=d(v,x),d(x,v)\ge 0,d(x,x)=0,d(x,v)\le d(x,u)+d(u,v).$$

For vectors in ${\mathbb{R}}^m$:

$$d_{{\ell }_2}(x,v)=\sqrt{\sum _{i=1}^m(x_i-v_i{)}^2},d_{{\ell }_1}(x,v)=\sum _{i=1}^m|x_i-v_i|,$$ $$d_{{\ell }_p}(x,v)={\left(\sum _{i=1}^m|x_i-v_i{|}^p\right)}^{1/p},p\ge 1.$$

For strings, the Levenshtein distance counts minimum edit operations (insert/delete/replace).

The cosine similarity

$$\cos (x,v)=\frac{⟨x,v⟩}{\Vert x{\Vert }_2\Vert v{\Vert }_2}$$

is a similarity, not a metric; it captures orientation rather than absolute magnitude.

Graph Data and Representation Dependence

A graph is $G=(V,E)$, optionally augmented to

$$G=(V,E,\mathbf{X},\mathbf{W}),$$

where $\mathbf{X}$ stores vertex features and $\mathbf{W}$ stores edge features. Common encodings are adjacency set, adjacency list, and adjacency matrix $A\in \{0,1{\}}^{|V|\times |V|}$.

Two structural difficulties drive graph learning theory:

1. permutation non-uniqueness: one graph admits many equivalent vertex orderings;
2. variable size: $|V|$ and $|E|$ differ across instances.

Hence representation must be permutation-invariant or permutation-equivariant.

Weisfeiler-Leman Refinement and Graph Vectors

The Weisfeiler-Leman (WL) algorithm computes iterative colour refinements. Let $c_x^{(t)}$ be the colour of vertex $x$ at iteration $t$. Initialisation is constant colouring $c^{(0)}$. Update rule:

$$c_x^{(t+1)}=\mathrm{HASH}\left(c_x^{(t)},\{\{c_y^{(t)}:y\in N(x)\}\}\right),$$

where $\{\{\cdot \}\}$ denotes a multiset and HASH is injective on its input tuples. Iteration stops when the number of distinct colours stabilises.

A finite-dimensional graph feature vector is obtained by counting colour frequencies across iterations. If $\mathcal{C}$ is the global colour index set, one graph-level representation is

$$\Phi (G)=(\#\{x\in V:c_x^{(t)}=\gamma \}{)}_{\gamma \in \mathcal{C},t=0,\dots ,T}.$$

Dot products between such vectors induce the Weisfeiler-Leman graph kernel.

Exam-Oriented Takeaways

For this lecture, you should be able to derive and explain:

1. feature-wise scaling maps (min-max, mean normalisation, standardisation);
2. formal metric axioms and the ${\ell }_1/{\ell }_2/{\ell }_p$ family;
3. why cosine is a similarity measure rather than a metric;
4. graph representation choices and permutation issues;
5. the WL update equation and how colour histograms yield graph vectors.

This lecture underpins later choices of distance-based methods, feature engineering, kernel methods, and graph learning pipelines.

Lecture 3 Core Concepts of Machine Learning

This lecture consolidates the pipeline from learning paradigms to optimisation, then to statistical evaluation and complexity control. The unifying question is: how can a model fit observed data while maintaining predictive reliability on unseen data?

Learning Paradigms

Let $\mathcal{X}$ denote the instance space and $\mathcal{Y}$ the target space. In supervised learning, we observe labelled samples

$$S=\{(x_i,y_i){\}}_{i=1}^m\in (\mathcal{X}\times \mathcal{Y}{)}^m,$$

and learn a predictor $h:\mathcal{X}\to \mathcal{Y}$. In unsupervised learning, only $\{x_i{\}}_{i=1}^m$ is observed and structure must be inferred without explicit labels.

The lecture also positions semi-supervised, self-supervised, active/passive, and online/batch settings as protocol variants that change information access or update timing, not the core objective of generalisable prediction.

Supervised Tasks and Loss Functions

Two canonical supervised tasks are:

• classification: $\mathcal{Y}$ finite/discrete,
• regression: $\mathcal{Y}\subseteq \mathbb{R}$ continuous.

Given loss $\mathcal{L}(h,x,y)$, the empirical risk is

$$R_S(h)=\frac{1}{m}\sum _{i=1}^m\mathcal{L}(h,x_i,y_i).$$

Typical losses from the lecture:

$$\text{0-1 loss:}\mathcal{L}(h,x,y)=1\{h(x)\ne y\},$$ $$\text{squared loss:}\mathcal{L}(h,x,y)=(h(x)-y{)}^2.$$

For linear regression with parameters $\theta =(a,b{)}^{\top }$ and $h_{\theta }(x)=ax+b$, training corresponds to minimising mean squared error on $S$.

Empirical Risk Minimisation and Training Objective

Let $\mathcal{H}$ be a hypothesis class. Empirical risk minimisation seeks

$$h^{\ast }\in \arg \underset{h\in \mathcal{H}}{\min }{R}_S(h).$$

This is an optimisation problem over parameter space (for parametric models) or function space (more generally). The key caveat highlighted in the lecture: low training error alone is insufficient, because optimisation can over-adapt to sample idiosyncrasies.

Gradient Descent and Parameter Updates

For differentiable objective $f:{\mathbb{R}}^d\to \mathbb{R}$ (e.g. empirical risk), gradient descent uses

$${\theta }_t={\theta }_{t-1}-\eta \nabla f({\theta }_{t-1}),$$

with learning rate $\eta >0$. Since $\nabla f(\theta )$ points to steepest ascent, $-\nabla f(\theta )$ is a local steepest-descent direction.

In stochastic variants (SGD), the full gradient is replaced by a mini-batch estimate. This introduces gradient noise but improves scalability and often helps escape sharp local structures.

Risk, Empirical Risk, and Generalisation

With data-generating distribution $\mathcal{D}$, true risk is

$$R_{\mathcal{D}}(h)={\mathbb{E}}_{(x,y)\sim \mathcal{D}}[\mathcal{L}(h,x,y)].$$

The empirical risk $R_S(h)$ is a sample estimate of $R_{\mathcal{D}}(h)$. Their mismatch defines generalisation error:

$$\mathrm{gen}(h)=R_{\mathcal{D}}(h)-R_S(h).$$

Model selection must therefore target low true risk, not merely low training error.

Bias-Variance and Fit Regimes

As complexity increases, approximation error (bias) tends to decrease, while estimation sensitivity (variance) tends to increase. The resulting bias-variance trade-off explains:

• underfitting at low complexity (high bias, low variance),
• overfitting at high complexity (low bias, high variance),
• an intermediate regime of best expected generalisation.

The “good fit” in the lecture corresponds to this intermediate region.

Regularisation as Complexity Control

Regularisation augments the data-fit term by a complexity penalty:

$${\mathcal{L}}_{\text{reg}}(h,x,y)=\mathcal{L}(h,x,y)+\lambda \Omega (h),$$

or dataset-level objective

$$\underset{h\in \mathcal{H}}{\min }{R}_S(h)+\lambda \Omega (h).$$

For parameter vector $\omega \in {\mathbb{R}}^d$:

$${\Omega }_{{\ell }_1}(\omega )=\sum _{i=1}^d|{\omega }_i|,{\Omega }_{{\ell }_2}(\omega )=\sum _{i=1}^d{\omega }_i^2.$$

${\ell }_1$ tends to induce sparse solutions; ${\ell }_2$ shrinks weights smoothly. The hyperparameter $\lambda$ controls the fit-complexity trade-off.

Exam-Oriented Takeaways

For this lecture, you should be able to state and manipulate:

1. supervised setup $(\mathcal{X},\mathcal{Y},S,h,\mathcal{L})$ and empirical risk definition;
2. task-specific losses (0-1 and squared loss) and when they apply;
3. ERM objective and gradient descent update equation;
4. true risk vs empirical risk and the meaning of generalisation;
5. regularised objective with ${\ell }_1/{\ell }_2$ penalties and the role of $\lambda$.

This lecture is the conceptual bridge from introductory examples to formal learning theory, optimisation analysis, and robust model selection.

Lecture 4 Basic Algorithms I

This lecture develops least-squares regression from first principles, then lifts the same optimisation pattern to polynomial and multivariate settings. The central message is that many seemingly different regressors are linear models in a transformed feature space.

Why Fit Models

Given data pairs, a fitted model serves four technical roles: compression of observations into a small parameter vector, interpolation/explanation of observed patterns, prediction on unseen inputs, and downstream decision support. In mathematical terms, we seek a map with low approximation error and acceptable generalisation behaviour while maintaining low representational complexity.

Linear Regression Setup

Assume training data

$$S=\{(x_i,y_i){\}}_{i=1}^m\subseteq \mathbb{R}\times \mathbb{R},$$

and a linear hypothesis

$$h_w(x)=w_{1}x+w_0,$$

with parameters $w=(w_0,w_1{)}^{\top }\in {\mathbb{R}}^2$. A standard noise model is

$$y_i=w_1{x}_i+w_0+{\epsilon }_i.$$

The least-squares objective (empirical risk with squared loss) is

$$R_S(w)=\frac{1}{m}\sum _{i=1}^m(y_i-(w_1{x}_i+w_0){)}^2.$$

Optimisation by Gradient Descent

The gradient components are

$$\frac{\partial R_S}{\partial w_1}=-\frac{2}{m}\sum _{i=1}^m{x}_i(y_i-(w_1{x}_i+w_0)),$$ $$\frac{\partial R_S}{\partial w_0}=-\frac{2}{m}\sum _{i=1}^m(y_i-(w_1{x}_i+w_0)).$$

With learning rate $\eta >0$, gradient descent updates are

$$w^{(t+1)}=w^{(t)}-\eta \nabla R_S\left(w^{(t)}\right).$$

This is the iterative route used broadly in machine learning, but linear least squares also admits an exact solution.

Closed-Form Least-Squares Solution

Because $R_S(w)$ is quadratic in $w$, its minimiser is obtained by setting partial derivatives to zero. The scalar closed form is

$$w_1=\frac{{\sum }_{i=1}^m(x_i-\bar{x})(y_i-\bar{y})}{{\sum }_{i=1}^m(x_i-\bar{x}{)}^2},w_0=\bar{y}-w_1\bar{x},$$

where

$$\bar{x}=\frac{1}{m}\sum _{i=1}^m{x}_i,\bar{y}=\frac{1}{m}\sum _{i=1}^m{y}_i.$$

Interpretation: $w_1$ is empirical covariance divided by empirical variance of the input coordinate.

Matrix Form and Normal Equations

Using the lecture orientation (samples as columns), define

$$X=\left[\begin{array}{ccc}1& \cdots & 1\\ x_1& \cdots & x_m\end{array}\right]\in {\mathbb{R}}^{2\times m},y={\left[\begin{array}{ccc}{y}_1& \cdots & y_m\end{array}\right]}^{\top }\in {\mathbb{R}}^m.$$

Then $\hat{y}=X^{\top }w$ and minimisation yields normal equations

$$X{X}^{\top }w=Xy,$$

hence

$$w=(X{X}^{\top }{)}^{-1}Xy.$$

Equivalent row-sample notation gives the familiar $w=(X^{\top }X{)}^{-1}{X}^{\top }y$.

Polynomial Regression as Linear Regression in Features

For degree $p$, define

$$h_w(x)=\sum _{k=0}^p{w}_k{x}^k.$$

Introduce feature map

$${\varphi }_p(x)={\left[\begin{array}{ccccc}1& x& x^2& \cdots & x^p\end{array}\right]}^{\top }.$$

Then $h_w(x)=w^{\top }{\varphi }_p(x)$ is linear in parameters. With design matrix

$$\Phi =\left[\begin{array}{ccc}{\varphi }_p(x_1)& \cdots & {\varphi }_p(x_m)\end{array}\right]\in {\mathbb{R}}^{(p+1)\times m},$$

the same normal-equation solution applies:

$$w=(\Phi {\Phi }^{\top }{)}^{-1}\Phi y.$$

Thus polynomial regression is not a different optimiser; it is a different representation.

Multiple Polynomial Regression

Now let $x_i\in {\mathbb{R}}^d$ and $y_i\in \mathbb{R}$. The lecture writes

$$h(x)=w_0+\sum _{k=1}^p{w}_k^{\top }{x}^{\odot k},$$

where $x^{\odot k}$ denotes component-wise powers. This keeps linearity in parameter blocks $w_k\in {\mathbb{R}}^d$ and yields a stacked parameter vector in ${\mathbb{R}}^{pd+1}$.

More generally, one may use any polynomial basis (including interaction monomials) and solve the same linear least-squares system in the induced feature space.

Numerical Remarks

The inverse in normal equations requires non-singularity of the Gram matrix ($X{X}^{\top }$ or $\Phi {\Phi }^{\top }$). In ill-conditioned settings, one uses pseudoinverse or regularised least squares:

$$w=(\Phi {\Phi }^{\top }+\lambda I{)}^{-1}\Phi y,$$

which connects directly to L2 regularisation from the previous lecture.

Exam-Oriented Takeaways

For this lecture, you should be able to derive and explain:

1. least-squares objective for linear regression and its gradient;
2. scalar closed-form parameters $(w_0,w_1)$ via vanishing derivatives;
3. matrix normal equations and orientation-dependent formula forms;
4. polynomial regression as linear regression after feature expansion;
5. multivariate polynomial parameterisation and dimension counting.

This lecture establishes the algebraic template reused by many later linear-in-parameter models.

Lecture 5 Basic Algorithms II

This lecture extends linear modelling from regression to classification, then addresses two central limitations: non-linearly separable categorical patterns and model misspecification. The resulting toolkit combines discriminative linear models, tree-based symbolic partitioning, and ensemble aggregation.

Linear Classifiers and Hyperplane Geometry

Given

$$S=\{(x_i,y_i){\}}_{i=1}^m,x_i\in {\mathbb{R}}^d,y_i\in \{-1,+1\},$$

we seek a hypothesis $h:{\mathbb{R}}^d\to \{-1,+1\}$ of the form

$$h_{a,b}(x)=\mathrm{sign}(x^{\top }a-b),$$

with normal vector $a\in {\mathbb{R}}^d$ and threshold $b\in \mathbb{R}$. The decision boundary is the hyperplane

$$H=\{x\in {\mathbb{R}}^d:x^{\top }a=b\}.$$

Using augmented coordinates $\bar{x}=(1,x^{\top }{)}^{\top }$ and $w=(-b,a^{\top }{)}^{\top }$, this becomes $h_w(x)=\mathrm{sign}(w^{\top }\bar{x})$.

A Simple Linear Classifier via Least Squares

Direct optimisation of the sign loss is discontinuous. The lecture motivates a surrogate chain

$$\mathrm{sign}(z)\approx \tanh (z)\approx z$$

near $z=0$ via the expansion $\tanh (z)=z-\frac{1}{3}{z}^3+O(z^5)$. This yields a least-squares classifier:

$$w^{\ast }\in \arg \underset{\hat{w}}{\min }\Vert X^{\top }\hat{w}-y{\Vert }_2^2,$$

with

$$X=\left[\begin{array}{ccc}1& \cdots & 1\\ x_1& \cdots & x_m\end{array}\right]\in {\mathbb{R}}^{(d+1)\times m},y=(y_1,\dots ,y_m{)}^{\top }\in \{-1,+1{\}}^m.$$

When $X{X}^{\top }$ is invertible,

$$w^{\ast }=(X{X}^{\top }{)}^{-1}Xy,$$

and prediction is performed by $\mathrm{sign}(w^{\ast \top }\bar{x})$ rather than by the raw linear score.

The Perceptron as Online Learning

The perceptron is presented as an online learning algorithm. At round $t$, observe $x_t$, predict ${\hat{y}}_t=\mathrm{sign}(w_t^{\top }{x}_t)$, reveal $y_t\in \{-1,+1\}$, and update only on mistakes:

$$w_{t+1}=\{\begin{array}{ll}{w}_t,& y_t{w}_t^{\top }{x}_t>0,\\ w_t+y_t{x}_t,& y_t{w}_t^{\top }{x}_t\le 0.\end{array}$$

Thus the algorithm is mistake-driven and data-stream compatible, unlike closed-form least squares requiring a full batch and matrix inversion.

Novikoff Convergence Theorem and Mistake Bound

Assume there exist $R,\gamma >0$ and a unit vector $u$ such that

$$\Vert x_i\Vert \le R,y_i⟨x_i,u⟩\ge \gamma \forall i.$$

Then the perceptron makes at most

$$M\le {\left(\frac{R}{\gamma }\right)}^2$$

mistakes.

Proof structure used in class:

$$\Vert w_{t+1}{\Vert }^2=\Vert w_t+y_t{x}_t{\Vert }^2=\Vert w_t{\Vert }^2+2y_t⟨w_t,x_t⟩+\Vert x_t{\Vert }^2\le \Vert w_t{\Vert }^2+R^2,$$

hence after $M$ mistakes, $\Vert w_M{\Vert }^2\le M{R}^2$. Conversely,

$$⟨w_{t+1},u⟩=⟨w_t,u⟩+y_t⟨x_t,u⟩\ge ⟨w_t,u⟩+\gamma ,$$

so $⟨w_M,u⟩\ge M\gamma$ and therefore $\Vert w_M\Vert \ge M\gamma$. Combining both inequalities gives

$$M^2{\gamma }^2\le \Vert w_M{\Vert }^2\le M{R}^2\Rightarrow M\le (R/\gamma {)}^2.$$

Logistic Regression

Logistic regression models class probability by

$$p_w(x)=\sigma (w^{\top }x),\sigma (z)=\frac{1}{1+e^{-z}}.$$

Hence $p_w(x)=\mathrm{Pr}(Y=1\mid X=x,w)$ and $1-p_w(x)=\mathrm{Pr}(Y=0\mid X=x,w)$, giving a confidence score in addition to a label.

With $y_i\in \{-1,+1\}$, one objective used in the lecture is

$$R_S(w)=\sum _{i=1}^m\log (1+\exp (-y_i{w}^{\top }{x}_i)).$$

Equivalent Bernoulli negative log-likelihood form (for $y_i\in \{0,1\}$):

$$\mathcal{L}(w)=-\sum _{i=1}^m\left[y_i\log p_w(x_i)+(1-y_i)\log (1-p_w(x_i))\right].$$

The objective is convex, but there is no closed-form minimiser; optimisation is done with gradient methods.

Categorical Data, XOR, and Decision Trees

For Boolean attributes, linear separators can fail even after numeric encoding. The canonical obstruction is XOR-type behaviour, which is not linearly separable in the original two-bit space.

The lecture motivates decision trees via Boolean formula structure. Any Boolean function can be represented in disjunctive normal form (DNF):

$$h(x_1,\dots ,x_d)=\underset{c\in {\mathcal{C}}_h}{\bigvee }\underset{j=1}{\overset{d}{\bigwedge }}{b}_{c,j},b_{c,j}\in \{x_j,\neg x_j\}.$$

Trees implement this logic as hierarchical tests: internal split nodes evaluate attributes; leaves store class outputs. A prediction follows one root-to-leaf path, so trees naturally classify unseen attribute combinations.

Split Quality, Top-Down Induction, and Stopping

To choose a split attribute $A$, impurity is minimised. For class set $\mathcal{Y}$,

$$I(A=a)=1-\sum _{c\in \mathcal{Y}}p(c\mid A=a{)}^2,I(A)=\sum _{a}p(A=a)I(A=a),$$

which is the Gini index criterion. Lower impurity indicates better class separation.

The induction pattern is recursive: start at the full sample, choose best split, partition into child subsets, remove/restrict used tests, and repeat. Without stopping, trees can memorise training data; practical constraints include maximum depth, maximum number of leaves, and minimum subset size. Impure terminal nodes typically predict the majority class.

Ensemble Methods: Bagging, Forests, and Boosting

Ensembling combines weak or unstable learners to improve predictive robustness.

For binary classifiers $\mathcal{H}$, majority voting is

$$h_B(x)=\{\begin{array}{ll}+1,& {\sum }_{h\in \mathcal{H}}h(x)\ge 0,\\ -1,& \text{otherwise}.\end{array}$$

Bagging creates diversity by bootstrap resampling: train base models on sampled subsets $S_s\subseteq S$ (with replacement), then aggregate votes. Random forests instantiate this with decision trees (often with feature subspace sampling at splits).

Boosting builds an additive model by sequential error correction. In regression form, with residuals $r_t(x_i)=y_i-f_t(x_i)$,

$$h_t\approx \arg \underset{h\in \mathcal{H}}{\min }\sum _{i=1}^m(r_t(x_i)-h(x_i){)}^2,f_{t+1}=f_t+{\eta }_t{h}_t.$$

A fixed ${\eta }_t=\eta$ is common in simple derivations; practical variants use line search

$${\eta }_t\in \arg \underset{{\eta }^{\prime }\in \mathbb{R}}{\min }{L}_S(f_t+{\eta }^{\prime }{h}_t).$$

The name gradient boosting reflects that $h_t$ approximates a descent direction in function space.

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. linear classifier geometry $h(x)=\mathrm{sign}(x^{\top }a-b)$ and augmented-vector form;
2. least-squares linear classification as a surrogate for sign optimisation;
3. perceptron mistake-driven update and Novikoff bound $M\le (R/\gamma {)}^2$;
4. logistic regression objective, probabilistic interpretation, and convex optimisation properties;
5. why XOR defeats linear separation and how decision trees solve this via hierarchical tests;
6. Gini-based split selection, stopping criteria, and overfitting control;
7. bagging/majority vote, random forests, and boosting as additive residual correction.

This lecture closes the transition from single-model linear methods to structured and ensemble predictors that trade interpretability, statistical robustness, and representational capacity.

Lecture 6 Experiment Design and Evaluation

This lecture formalises the end-to-end experimental protocol for machine learning: choose hyperparameters, train models, estimate generalisation, and verify that performance reflects intended behaviour rather than artefacts. The core principle is methodological separation of concerns: model fitting, model selection, and final assessment must use disjoint information.

Hyperparameters and Their Role

A hyperparameter is a configuration variable fixed before or outside parameter optimisation (for example, tree depth limits, number of estimators, regularisation strengths, or search budgets). If a model class is written as

$$h_{\theta ,\lambda },$$

then $\theta$ denotes trainable parameters, while $\lambda$ denotes hyperparameters selected by an outer procedure.

The lecture stresses that predictive performance can vary strongly with $\lambda$, but the search space often scales combinatorially with the number of tuned dimensions.

Why Dataset Splitting Is Necessary

There are three logically distinct tasks:

1. train model parameters;
2. choose hyperparameters;
3. estimate out-of-sample performance.

Hence one should separate a dataset $S$ into disjoint subsets:

$$S=S_{\mathrm{train}}\dot{\cup }{S}_{\mathrm{val}}\dot{\cup }{S}_{\mathrm{test}}.$$

Training uses $S_{\mathrm{train}}$, hyperparameter selection uses $S_{\mathrm{val}}$, and only the final locked model is evaluated on $S_{\mathrm{test}}$. Reusing test information during tuning biases the estimated generalisation error downward.

Holdout and k-fold Cross-Validation

For sufficiently large datasets, holdout splitting is often adequate. For smaller datasets, the variance of holdout estimates can be high due to small validation/test subsets.

k-fold cross-validation reduces estimator variance by partitioning data into folds $F_1,\dots ,F_k$ and averaging fold scores:

$${\hat{M}}_{\mathrm{CV}}=\frac{1}{k}\sum _{j=1}^{k}M(h^{(-j)},F_j),$$

where $h^{(-j)}$ is trained on ${\bigcup }_{i\ne j}{F}_i$. Stratified splits are preferred in classification so label proportions remain approximately stable across folds.

Data Contamination and Preprocessing Order

Any preprocessing step whose statistics depend on data (for example standardisation parameters) must be fitted on training data only. For a transform $T_{\varphi }$ with fitted state $\varphi$:

$$\varphi \leftarrow \mathrm{fit}(S_{\mathrm{train}}),{\tilde{S}}_{\mathrm{train}}=T_{\varphi }(S_{\mathrm{train}}),{\tilde{S}}_{\mathrm{val}}=T_{\varphi }(S_{\mathrm{val}}),{\tilde{S}}_{\mathrm{test}}=T_{\varphi }(S_{\mathrm{test}}).$$

Fitting transforms on full data leaks information from validation/test into training and invalidates evaluation.

Evaluation Metrics by Task

Evaluation is a mapping from predictions and ground truth to a scalar criterion, and must match the task objective.

For regression $(y_i,{\hat{y}}_i)\in {\mathbb{R}}^2$:

$$\mathrm{MAE}=\frac{1}{n}\sum _{i=1}^n|y_i-{\hat{y}}_i|,\mathrm{MSE}=\frac{1}{n}\sum _{i=1}^n(y_i-{\hat{y}}_i{)}^2,\mathrm{RMSE}=\sqrt{\mathrm{MSE}}.$$

For binary classification with confusion-matrix counts $(TP,FP,TN,FN)$:

$$\mathrm{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN},\mathrm{Precision}=\frac{TP}{TP+FP},$$ $$\mathrm{Recall}=\frac{TP}{TP+FN},F1=\frac{2\mathrm{Precision}\cdot \mathrm{Recall}}{\mathrm{Precision}+\mathrm{Recall}},\mathrm{FPR}=\frac{FP}{FP+TN}.$$

The lecture highlights that metric choice is application-dependent, because false positives and false negatives may have asymmetric costs.

Hyperparameter Tuning as Outer Optimisation

Let $\Lambda$ be a hyperparameter search space and $M_{\mathrm{val}}(\lambda )$ the validation score of the model trained with $\lambda$. Tuning is

$${\lambda }^{\ast }\in \arg \underset{\lambda \in \Lambda }{\max }{M}_{\mathrm{val}}(\lambda )$$

(or $\arg \min$ for loss metrics).

Two strategies discussed in class:

• grid search: exhaustive over a finite grid ${\Lambda }_{\mathrm{grid}}$;
• random search: sample $\lambda \sim P_{\Lambda }$ for a fixed trial budget.

Grid search is simple but scales poorly in dimension; random search often uses budgets more efficiently when only a subset of hyperparameters strongly affects performance.

Baselines, Randomness, and Significance

Raw scores are uninterpretable without baselines. Typical baselines include majority-class prediction in classification and mean prediction in regression. A model should substantially exceed these references on unseen data.

Because many pipelines are stochastic (random splits, random forests, random search), reproducibility requires fixed seeds where possible. The lecture explicitly warns against tuning the random seed as if it were a model hyperparameter.

When comparing models across folds, apparent improvements may arise from sampling noise. The recommended protocol is to predefine a significance level $\alpha$ (for example $0.05$), then test pairwise differences with a Student-t test on fold-wise scores.

Practical Reliability and Failure Modes

A high test score is necessary but not sufficient. Models may exploit spurious correlates (for example background artefacts) rather than task-causal structure. Therefore, evaluation must include sanity checks and targeted verification beyond aggregate metrics.

Practical guidance from the lecture:

1. improve and inspect data quality before increasing model complexity;
2. start with simple baselines and small prototypes;
3. inspect raw inputs and transformed features;
4. verify model behaviour under perturbations and plausible distribution shifts.

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. why train/validation/test separation is required for unbiased generalisation estimates;
2. holdout versus k-fold cross-validation and when each is appropriate;
3. leakage-safe preprocessing order (fit on train only, apply elsewhere);
4. regression and classification metric formulas and their trade-offs;
5. grid versus random search as hyperparameter optimisation strategies;
6. the role of baselines, fixed seeds, and statistical significance testing;
7. why good test metrics still require behavioural verification.

This lecture provides the experimental discipline needed to convert algorithmic knowledge into trustworthy, reproducible machine learning practice.

Lecture 7 Machine Learning Theory

This lecture introduces the statistical-learning-theory core of the course: a formal data-generating model, explicit assumptions, and finite-sample guarantees for generalisation. The central question is not whether a model fits observed data, but when fitting implies low true risk.

Formal Learning Setup

Let $\mathcal{X}$ be the instance space, $\mathcal{Y}=\{0,1\}$ the label space, and $\mathcal{D}$ an unknown distribution on $\mathcal{X}\times \mathcal{Y}$. A sample of size $m$ is

$$S=((x_1,y_1),\dots ,(x_m,y_m))\sim {\mathcal{D}}^m.$$

For hypothesis class $\mathcal{H}$ and loss

$$\mathcal{L}(h,x,y)=1\{h(x)\ne y\},$$

the empirical and true risks are

$$R_S(h)=\frac{1}{m}\sum _{i=1}^m\mathcal{L}(h,x_i,y_i),R_{\mathcal{D}}(h)={\mathbb{E}}_{(x,y)\sim \mathcal{D}}[\mathcal{L}(h,x,y)].$$

A hypothesis is consistent if $R_S(h)=0$. The theoretical objective is to guarantee small $R_{\mathcal{D}}(h)$.

Hypothesis Classes and Learning Algorithms

The hypothesis class $\mathcal{H}$ encodes representational bias (for example rectangles, linear separators, perceptrons, trees). It determines what can be learned in principle.

A learning algorithm is a map

$$A:(\mathcal{X}\times \mathcal{Y}{)}^m\to \mathcal{H},$$

returning $A(S)\in \mathcal{H}$. In particular, an ERM algorithm outputs

$$h_S\in \arg \underset{h\in \mathcal{H}}{\min }{R}_S(h).$$

Core Assumptions

Two assumptions are made explicit:

1. i.i.d. assumption: examples are independent draws from one fixed distribution $\mathcal{D}$;
2. realisability assumption: there exists $h^{\ast }\in \mathcal{H}$ with $R_{\mathcal{D}}(h^{\ast })=0$.

Realisability means no irreducible label noise relative to $\mathcal{H}$ and perfect class-model alignment.

Realisable PAC Learning

PAC learning asks for probabilistic approximate correctness. A class $\mathcal{H}$ is realisable PAC-learnable if there exists an algorithm $A$ and sample-complexity function $m_{\mathcal{H}}:(0,1{)}^2\to \mathbb{N}$ such that for all $\epsilon ,\delta \in (0,1)$, for all realisable $\mathcal{D}$, and all $m\ge m_{\mathcal{H}}(\epsilon ,\delta )$,

$$\underset{S\sim {\mathcal{D}}^m}{\mathrm{Pr}}(R_{\mathcal{D}}(A(S))\le \epsilon )\ge 1-\delta .$$

Here $\epsilon$ is the target error and $\delta$ the failure probability.

Finite-Class Mistake Bound

If $|\mathcal{H}|<\infty$ and realisability holds, returning any consistent hypothesis yields PAC learnability with

$$m_{\mathcal{H}}(\epsilon ,\delta )\le \frac{1}{\epsilon }(\ln |\mathcal{H}|+\ln \frac{1}{\delta }).$$

Proof skeleton from the lecture:

For a bad $h$ with $R_{\mathcal{D}}(h)>\epsilon$,

$$\mathrm{Pr}\left(h\text{ is consistent on }S\right)\le (1-\epsilon {)}^m\le e^{-\epsilon m}.$$

Applying a union bound over all bad hypotheses,

$$\mathrm{Pr}(\exists h\in \mathcal{H}:R_S(h)=0\wedge R_{\mathcal{D}}(h)>\epsilon )\le |\mathcal{H}|e^{-\epsilon m}.$$

Imposing this probability to be at most $\delta$ gives the stated bound.

Papaya Example and Sample Complexity Interpretation

The lecture’s papaya toy calculation instantiates the bound numerically. With $\epsilon =0.1$, $\delta =0.05$, and a finite class size estimate $|\mathcal{H}|\le 11816$:

$$m\ge \frac{1}{0.1}\left(\ln (11816)+\ln \frac{1}{0.05}\right)\approx 124.$$

Interpretation: about 124 i.i.d. labelled examples suffice to guarantee error at most $10\%$ with confidence at least $95\%$ under realisability.

Infinite Classes, Shattering, and VC Dimension

Finite-cardinality bounds do not directly control infinite classes. The structural replacement is shattering.

For $X=\{x_1,\dots ,x_n\}\subseteq \mathcal{X}$, class $\mathcal{H}$ shatters $X$ if for every label vector $y\in \{0,1{\}}^n$ there exists $h\in \mathcal{H}$ with

$$h(x_i)=y_i\forall i\in \{1,\dots ,n\}.$$

The VC dimension is

$$\mathrm{vc}(\mathcal{H})=\sup \{|X|:X\subseteq \mathcal{X}\text{ is shattered by }\mathcal{H}\},$$

with value $\infty$ if arbitrarily large finite sets are shattered.

Standard examples from class:

$$\mathrm{vc}(\mathcal{H})\le {\log }_2|\mathcal{H}|\text{ for finite }\mathcal{H},\mathrm{vc}(\text{thresholds on }\mathbb{R})=1,$$ $$\mathrm{vc}(\text{axis-aligned rectangles in }{\mathbb{R}}^2)=4,\mathrm{vc}(\text{linear separators in }{\mathbb{R}}^d)=d+1.$$

VC Dimension and PAC Learnability

For classes with finite VC dimension $d=\mathrm{vc}(\mathcal{H})<\infty$, ERM is PAC-learnable with sample complexity of order

$$m_{\mathcal{H}}(\epsilon ,\delta )=\mathcal{O}\left(\frac{d\ln (1/\epsilon )+\ln (1/\delta )}{\epsilon }\right).$$

Thus capacity control moves from counting hypotheses to measuring combinatorial expressiveness via shattering.

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. the formal tuple $(\mathcal{X},\mathcal{Y},\mathcal{D},\mathcal{H},\mathcal{L})$ and definitions of $R_S$ and $R_{\mathcal{D}}$;
2. i.i.d. and realisability assumptions and why each is needed in guarantees;
3. the realisable PAC statement with $(\epsilon ,\delta )$ quantifiers;
4. the finite-class sample-complexity derivation via consistency probability, union bound, and $1-x\le e^{-x}$;
5. shattering and VC dimension definitions and canonical examples;
6. the qualitative VC-based bound and its dependence on $d$, $\epsilon$, and $\delta$.

This lecture establishes the theoretical bridge from empirical training success to explicit, distribution-level generalisation guarantees.

Lecture 8 Support Vector Machines and Kernel Methods

This lecture develops the max-margin principle for linear classification, then shows how kernelisation transfers linear methods to non-linear feature spaces without explicit coordinate lifting. The unifying theme is geometric control of generalisation through margin and function-class complexity.

From Linear Classifiers to Max-Margin Separation

For binary labels $y_i\in \{-1,+1\}$ and inputs $x_i\in {\mathbb{R}}^d$, a linear decision function is

$$f_w(x)=⟨w,x⟩,h_w(x)=\mathrm{sign}(f_w(x)).$$

Max-margin geometry introduces a margin parameter $\gamma >0$ and normalised constraints

$$y_i⟨x_i,\frac{w}{\Vert w\Vert }⟩\ge \gamma \forall i,$$

equivalently $y_i⟨w,x_i⟩\ge \gamma \Vert w\Vert$. The corresponding margin hyperplanes are

$$\left\{x:⟨x,\frac{w}{\Vert w\Vert }⟩=\gamma \right\},\left\{x:⟨x,\frac{w}{\Vert w\Vert }⟩=-\gamma \right\}.$$

Points attaining equality are support vectors; they determine the boundary.

SVM Optimisation View

Under separability, the hard-margin SVM can be written (after standard scaling) as

$$\underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2\text{s.t.}{y}_i(⟨w,x_i⟩+b)\ge 1\forall i.$$

For non-separable data, slack variables ${\xi }_i\ge 0$ yield the soft-margin form

$$\underset{w,b,\xi }{\min }\frac{1}{2}\Vert w{\Vert }^2+C\sum _{i=1}^m{\xi }_i\text{s.t.}{y}_i(⟨w,x_i⟩+b)\ge 1-{\xi }_i.$$

This objective corresponds to regularised minimisation with hinge loss

$${\ell }_{\mathrm{hinge}}(y,f(x))=\max \{0,1-yf(x)\},$$

which is a convex upper bound on classification error.

Why Perceptrons Fail on XOR and How to Fix It

The lecture revisits the XOR obstruction: single linear separators cannot represent certain Boolean patterns in original coordinates. Two remedies are contrasted:

1. layering (multi-layer compositions) to increase representational depth;
2. mapping (feature lifting) so the problem becomes linear in transformed space.

Kernel methods implement the second route while avoiding explicit high-dimensional coordinates.

Kernel Perceptron and the Kernel Trick

Perceptron-style predictors admit an expansion

$$f(x)=\sum _{i=1}^m{\alpha }_i⟨x_i,x⟩,$$

where ${\alpha }_i$ are update-dependent coefficients. Replacing inner products by a kernel function $k$ gives

$$f_k(x)=\sum _{i=1}^m{\alpha }_{i}k(x_i,x).$$

If $k(x,x^{\prime })=⟨\varphi (x),\varphi (x^{\prime }){⟩}_{\mathcal{H}}$ for some feature map $\varphi$, then this is linear learning in feature space $\mathcal{H}$ without computing $\varphi (x)$ explicitly.

Example Kernel Construction

For $a,b\in {\mathbb{R}}^2$, consider

$$k(a,b)=⟨a,b{⟩}^2=(a_1{b}_1+a_2{b}_2{)}^2.$$

Expanding,

$$k(a,b)=a_1^2{b}_1^2+2a_1{a}_2{b}_1{b}_2+a_2^2{b}_2^2=⟨\varphi (a),\varphi (b)⟩$$

with one valid map

$$\varphi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2{)}^{\top }.$$

This illustrates polynomial lifting through kernel evaluation alone.

Common Kernels and Inductive Bias

The lecture highlights standard families:

$$k_{\mathrm{lin}}(x,x^{\prime })=⟨x,x^{\prime }⟩,$$ $$k_{\mathrm{poly}}(x,x^{\prime })=(⟨x,x^{\prime }⟩+c{)}^d,$$ $$k_{\mathrm{rbf}}(x,x^{\prime })=\exp (-\gamma \Vert x-x^{\prime }{\Vert }^2).$$

These correspond to different smoothness/locality assumptions and therefore different generalisation behaviour.

Kernel Matrices and PSD Structure

Given data $x_1,\dots ,x_n$, the kernel matrix (Gram matrix)

$$K\in {\mathbb{R}}^{n\times n},K_{ij}=k(x_i,x_j)$$

must be symmetric and positive semidefinite:

$$c^{\top }Kc\ge 0\forall c\in {\mathbb{R}}^n.$$

Equivalent PSD characterisations used in the appendix:

1. $c^{\top }Kc\ge 0$ for all $c$;
2. factorisation $K=F^{\top }F$;
3. eigendecomposition $K=UD{U}^{\top }$ with diagonal $D_{ii}\ge 0$.

Closure example: if $G,H⪰0$, then $G+H⪰0$, so sums of valid kernels remain valid kernels.

A Small Learning-Theory Bridge

The lecture connects kernel methods to generalisation bounds of the form

$$\text{test error}\lesssim \text{training surrogate error}+\text{capacity term}+\text{concentration term}.$$

Because direct 0-1 risk minimisation is non-convex/intractable, one minimises a convex surrogate (hinge-type objective) plus norm control. In RKHS formulations, restricting $\Vert f{\Vert }_{\mathcal{H}}\le \theta$ controls complexity (linked to Rademacher complexity bounds).

Applications and Structured Data

Kernel methods are presented as a generic similarity-learning framework beyond vectors: spectra, spatial statistics, and graphs. For graph kernels, naive subgraph-based kernels can be computationally hard; practical work uses tractable embeddings or restricted graph classes.

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. max-margin constraints and the role of support vectors;
2. hard-margin versus soft-margin SVM objectives and the effect of $C$;
3. kernel perceptron form $f(x)={\sum }_i{\alpha }_{i}k(x_i,x)$;
4. explicit feature-map recovery for simple polynomial kernels;
5. PSD kernel-matrix criteria and their equivalent formulations;
6. why convex surrogate minimisation (hinge) is used instead of direct 0-1 loss;
7. how kernels extend linear methods to non-linear and structured domains.

This lecture completes the line from linear separators to high-capacity similarity-based methods with explicit geometric and statistical control.

Lecture 9 Probabilistic Aspects of Machine Learning

This lecture shifts from deterministic label prediction to probabilistic inference. The central objective is to model uncertainty, incorporate prior beliefs, and exploit distributional structure beyond pure empirical-risk language.

Why Probabilistic Modelling

Compared with strict point prediction, a probabilistic model additionally provides confidence and calibrated uncertainty for decisions. It also enables prior-informed inference when data are scarce and allows modelling assumptions on the joint distribution rather than only worst-case distribution-free guarantees.

Bayes Optimal Classifier

Given data-generating distribution $\mathcal{D}$ over $\mathcal{X}\times \mathcal{Y}$, the Bayes-optimal classifier is

$$f_{\mathcal{D}}(x)=\arg \underset{y\in \mathcal{Y}}{\max }P(Y=y\mid X=x).$$

For 0-1 loss it minimises true risk among all measurable classifiers $g:\mathcal{X}\to \mathcal{Y}$:

$$R_{\mathcal{D}}(f_{\mathcal{D}})\le R_{\mathcal{D}}(g)\forall g.$$

Two modelling routes follow:

1. discriminative learning: model $P(Y\mid X)$ directly;
2. generative learning: model $P(X,Y)$ (or $P(X\mid Y),P(Y)$), then infer posteriors.

Probability Identities Used for Inference

For random variables $A,B,C$:

$$P(A)=\sum _{b}P(A,B=b),P(A)=\sum _{b,c}P(A,B=b,C=c),$$ $$P(A,B)=P(A\mid B)P(B)=P(B\mid A)P(A),$$ $$P(A,B,C)=P(A\mid B,C)P(B\mid C)P(C).$$

Conditioning follows

$$P(A\mid B=b)=\frac{P(A,B=b)}{P(B=b)}=\frac{P(A,B=b)}{{\sum }_{a}P(A=a,B=b)}.$$

Bayes Theorem and Coin-Type Example

For hypothesis variable $\Theta$ and observed data $X$,

$$P(\Theta \mid X)=\frac{P(X\mid \Theta )P(\Theta )}{P(X)}=\frac{P(X\mid \Theta )P(\Theta )}{{\sum }_{\theta }P(X\mid \Theta =\theta )P(\Theta =\theta )}.$$

Interpretation in the urn example: prior over coin types is updated by toss outcomes into a posterior over coin types. Sequential evidence is incorporated recursively by reusing posterior-as-prior.

MLE, MAP, and Full Bayesian Inference

Three inference levels are distinguished:

1. MLE

$${\theta }_{\mathrm{MLE}}^{\ast }\in \arg \underset{\theta }{\max }P(X\mid \Theta =\theta ),$$

which ignores priors;

2. MAP

$${\theta }_{\mathrm{MAP}}^{\ast }\in \arg \underset{\theta }{\max }P(\Theta =\theta \mid X)=\arg \underset{\theta }{\max }P(X\mid \Theta =\theta )P(\Theta =\theta ),$$

which selects the posterior mode;

3. full Bayesian inference: retain the complete posterior $P(\Theta \mid X)$ rather than a point estimate.

Posterior Predictive Distribution

For observed data $D$ and future datum $\tilde{D}$, the posterior predictive distribution is

$$P(\tilde{D}\mid D)=\sum _{\theta }P(\tilde{D}\mid \Theta =\theta )P(\Theta =\theta \mid D),$$

or an integral in continuous-parameter models. It averages predictions across hypotheses weighted by posterior plausibility and therefore propagates parameter uncertainty into predictions.

Bayesian Networks and Factorised Joint Models

A Bayesian network is a DAG over variables $\{X_i{\}}_{i=1}^n$ with factorisation

$$P(X_1,\dots ,X_n)=\prod _{i=1}^{n}P(X_i\mid \mathrm{pa}(X_i)).$$

The graph encodes conditional independences that reduce representation size and inference cost. Without structure, a joint over $n$ binary variables needs $2^n-1$ parameters; conditional-independence factorisations can be exponentially more compact.

For chain-like structures, marginals can be computed by ordered elimination instead of brute-force summation over all assignments, reducing practical complexity substantially.

Naive Bayes as a Special Bayesian Network

In Naive Bayes, class variable $\Theta$ is a parent of all features $x_i$, and features are conditionally independent given class:

$$P(X\mid \Theta )=\prod _{i=1}^{n}P(x_i\mid \Theta ),P(X,\Theta )=P(\Theta )\prod _{i=1}^{n}P(x_i\mid \Theta ).$$

Prediction is

$${\theta }^{\ast }\in \arg \underset{\theta }{\max }P(\Theta =\theta \mid X)=\arg \underset{\theta }{\max }P(\Theta =\theta )\prod _{i=1}^{n}P(x_i\mid \Theta =\theta ),$$

since $P(X)$ does not depend on $\theta$ for argmax classification.

Empirical estimators from labelled data:

$$\hat{P}(\Theta =\theta )=\frac{\#\{j:y_j=\theta \}}{m},\hat{P}(x_i=1\mid \Theta =\theta )=\frac{\#\{j:y_j=\theta ,x_{j,i}=1\}}{\#\{j:y_j=\theta \}}.$$

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. Bayes-optimal decision rule and why it minimises 0-1 risk;
2. discriminative versus generative modelling viewpoints;
3. Bayes theorem derivation and prior-likelihood-posterior decomposition;
4. conceptual and mathematical differences between MLE, MAP, and full posterior inference;
5. posterior predictive averaging over hypotheses;
6. Bayesian-network factorisation and why it improves representational/inference efficiency;
7. Naive Bayes assumptions, classification rule, and parameter estimation from counts.

This lecture introduces the probabilistic foundation for uncertainty-aware machine learning and structured probabilistic modelling.

Lecture 10 Dimensionality Reduction and Distance-Based Algorithms

This lecture studies two connected themes: reducing high-dimensional representations while preserving useful structure, and learning directly from distances in feature space. The practical motivation is that many real datasets are high-dimensional, noisy, and geometrically sparse.

Why Dimensionality Reduction

High-dimensional geometry behaves counterintuitively. A standard concentration intuition is that, as dimension grows, volume mass shifts in ways that make naive neighbourhood reasoning brittle (often called the curse of dimensionality). Consequently, reducing dimension can improve computation, denoising, and visual interpretability.

The lecture frames reduction as a trade-off between:

1. retaining informative variance/geometry;
2. minimising reconstruction or neighbourhood distortion;
3. reducing computational cost.

Principal Component Analysis

Let centred data matrix be $X\in {\mathbb{R}}^{n\times p}$ and covariance

$$C=\frac{1}{n-1}{X}^{\top }X.$$

For a unit direction $w$ ($\Vert w{\Vert }_2=1$), one-dimensional projection is $Xw$. PCA chooses $w$ maximising projected variance:

$$\underset{\Vert w{\Vert }_2=1}{\max }\mathrm{Var}(Xw)=\underset{\Vert w{\Vert }_2=1}{\max }{w}^{\top }Cw.$$

Equivalent viewpoint: minimise rank-1 reconstruction error

$$\underset{\Vert w{\Vert }_2=1}{\min }\Vert X-Xw{w}^{\top }{\Vert }_F^2.$$

Using the Lagrangian

$$\mathcal{L}(w,\lambda )=w^{\top }Cw-\lambda (w^{\top }w-1),$$

stationarity gives $Cw=\lambda w$, so the first principal component is the eigenvector of $C$ with largest eigenvalue. Higher components are orthogonal eigenvectors ordered by eigenvalue magnitude.

Random Projection and the Johnson-Lindenstrauss Principle

When $p$ is very large, PCA may be costly (eigendecomposition typically scales poorly with $p$). Random projection uses a random linear map to dimension $k\ll p$ with complexity roughly $\mathcal{O}(npk)$.

The Johnson-Lindenstrauss guarantee states that for $n$ points, one can choose

$$k=\Omega \left(\frac{\log n}{{\epsilon }^2}\right)$$

so that pairwise distances are preserved up to $(1\pm \epsilon )$ multiplicative distortion with high probability.

Proof sketch idea in class: with Gaussian random matrix $R\in {\mathbb{R}}^{k\times p}$ and map

$$f(x)=\frac{1}{\sqrt{k}}Rx,$$

the squared norm of projected difference vectors concentrates sharply around the original norm; then a union bound over all $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs yields the global preservation result.

t-SNE

t-SNE is a non-linear embedding method emphasising local neighbourhood preservation for visualisation. It converts distances into neighbour probabilities in high-dimensional space, then finds a low-dimensional configuration whose induced probabilities are close (via divergence minimisation).

Operational properties stressed in lecture:

1. non-linear;
2. stochastic/non-deterministic;
3. hyperparameter-sensitive (not parameter-free);
4. typically strong for visual cluster separation, but not a faithful global metric map.

k-Nearest Neighbours

k-NN predicts by local majority vote (classification) or local averaging (regression) among the $k$ closest training points under a chosen metric $d$.

For binary classification,

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

where $N_k(x)$ is the set of $k$ nearest neighbours of $x$. The hyperparameter $k$ controls bias-variance behaviour: small $k$ gives high variance/local sensitivity, large $k$ gives smoother but potentially biased decisions.

k-Means Clustering

k-means partitions points into $k$ clusters by minimising within-cluster squared distances:

$$\underset{S_1,\dots ,S_k}{\min }\sum _{i=1}^k\sum _{x\in S_i}\Vert x-{\mu }_i{\Vert }_2^2,{\mu }_i=\frac{1}{|S_i|}\sum _{x\in S_i}x.$$

Lloyd-style iteration:

1. initialise $k$ centroids (often from random data points);
2. assign each point to nearest centroid;
3. recompute centroids as cluster means;
4. repeat until assignments stabilise.

The algorithm monotonically decreases objective value but can converge to local minima; initialisation therefore matters.

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. why high-dimensional settings motivate dimension reduction;
2. PCA objective, covariance-eigenvector solution, and variance/reconstruction equivalence;
3. random projection complexity and JL scaling $k\sim \log (n)/{\epsilon }^2$;
4. conceptual difference between PCA and t-SNE (linear-global vs non-linear-local focus);
5. k-NN decision rule and effect of $k$;
6. k-means objective and alternating optimisation steps.

This lecture links geometric representation learning with simple, powerful distance-based prediction and clustering methods.

Lecture 11 Deep Neural Networks and Backpropagation

This lecture extends perceptron models to deep compositions of affine maps and non-linear activations. The central result is that depth increases representational capacity, but efficient training requires structured gradient computation via backpropagation.

From Linear Separation to Deep Non-Linear Models

Stacking purely linear layers collapses to one linear map, so depth alone does not resolve non-linearly separable tasks such as XOR. Let

$$h(x)=W_k(W_{k-1}(\cdots (W_{1}x))).$$

Then $h(x)=Wx$ for $W=W_k\cdots W_1$, hence no additional expressive class over a single linear classifier.

Introducing elementwise activation functions $\sigma$ yields a non-linear hypothesis class:

$$h(x)=W_k\sigma (W_{k-1}\sigma (\cdots \sigma (W_{1}x+b_1)\cdots )+b_{k-1})+b_k.$$

Typical activations discussed in lecture are sigmoid, tanh, and ReLU.

Multi-Layer Perceptron Notation and Forward Pass

For layers $l=1,\dots ,L$ (input $l=1$, output $l=L$), define:

$$s^l=W^{l-1}{a}^{l-1}+b^{l-1},a^l=\sigma (s^l).$$

Here $a^1=x$ is the input, $s^l$ is the pre-activation vector, and $a^l$ the activation vector. For a supervised target $y$, prediction is $\hat{y}=a^L$.

This gives the standard multi-layer perceptron forward recursion used throughout deep learning architectures.

Universal Approximation Perspective

The lecture states the universal approximation theorem intuition: for suitable non-linear activations, a feed-forward network with at least one hidden layer and finitely many parameters can approximate continuous functions on compact domains arbitrarily well.

A representative form is:

$$\forall f\in C([0,1{]}^n),\forall \epsilon >0,\exists \text{network }g\text{ such that }\underset{x\in [0,1{]}^n}{\sup }|f(x)-g(x)|<\epsilon .$$

This is an expressivity statement, not an optimisation guarantee: approximation existence does not imply easy training or strong generalisation.

Learning Objective and Loss Design

Training minimises a differentiable empirical objective

$$\underset{\Theta }{\min }\frac{1}{n}\sum _{i=1}^n\mathcal{L}({\hat{y}}_i,y_i),\Theta =\{W^l,b^l{\}}_{l=1}^{L-1}.$$

Lecture emphasis:

1. for classification, cross-entropy is standard;
2. for regression, mean squared error is standard;
3. differentiability of the computational path is required for gradient-based learning.

From Gradient Descent to Backpropagation

Vanilla gradient descent updates parameters by

$$\theta \leftarrow \theta -\eta {\nabla }_{\theta }\mathcal{L},$$

but naive symbolic differentiation of a deep composite is computationally redundant. Backpropagation exploits chain-rule factor reuse by traversing the network in reverse topological order.

For a scalar example $f(x,y,z)=(x+y)z$, write $q=x+y$, $f=qz$. Then

$$\frac{\partial f}{\partial x}=\frac{\partial f}{\partial q}\frac{\partial q}{\partial x}=z\cdot 1,\frac{\partial f}{\partial y}=z,\frac{\partial f}{\partial z}=q.$$

The same decomposition principle scales to full neural networks.

Error Signals, Jacobians, and Parameter Gradients

Define layer error (pre-activation gradient)

$${\delta }^l:=\frac{\partial \mathcal{L}}{\partial s^l}.$$

Backward recursion for hidden layers (vector form):

$${\delta }^{l-1}=(W^{l-1}{)}^{\top }{\delta }^l\odot {\sigma }^{\prime }(s^{l-1}),$$

which is the Jacobian-chain-rule form highlighted in lecture. Parameter gradients then become

$$\frac{\partial \mathcal{L}}{\partial W^{l-1}}={\delta }^l(a^{l-1}{)}^{\top },\frac{\partial \mathcal{L}}{\partial b^{l-1}}={\delta }^l.$$

Hence one training step is: forward pass, compute loss, backward pass for all ${\delta }^l$, then gradient update for all $(W^l,b^l)$.

Building-Block View of Deep Architectures

The lecture reframes deep learning as composition of modules with forward and backward interfaces. A linear feed-forward layer is one block; recurrent or attention/convolutional modules are alternative blocks. Architectures are formed by:

1. stacking blocks (depth);
2. adding skip connections;
3. branching into multiple outputs.

This abstraction explains how MLPs, CNNs, RNNs, transformers, and generative architectures share the same optimisation principle while differing in structural priors.

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. why linear-layer stacking without activations is still linear;
2. forward equations $s^l=W^{l-1}{a}^{l-1}+b^{l-1}$ and $a^l=\sigma (s^l)$;
3. role of differentiable loss functions and typical choices by task;
4. backpropagation as efficient chain-rule reuse rather than a different optimiser;
5. error recursion ${\delta }^{l-1}=(W^{l-1}{)}^{\top }{\delta }^l\odot {\sigma }^{\prime }(s^{l-1})$;
6. gradient formulas for weights and biases;
7. modular building-block view and its connection to modern deep architectures.

This lecture provides the computational core that makes high-capacity non-linear models trainable in practice.

Lecture 12 Deep Learning Architectures as Composable Building Blocks

This lecture reframes deep learning implementation as composition of reusable computational modules. The key abstraction is that each module exposes a forward map and a backward gradient map, so complex networks can be assembled while preserving end-to-end trainability.

Building-Block Abstraction

Let a block be a parametric map

$$z=\varphi (x;\theta ),$$

with local Jacobian $\partial z/\partial x$ and parameter gradient $\partial z/\partial \theta$. During backpropagation, upstream error ${\delta }_z=\partial \mathcal{L}/\partial z$ induces

$${\delta }_x={\delta }_z\frac{\partial z}{\partial x},\frac{\partial \mathcal{L}}{\partial \theta }={\delta }_z\frac{\partial z}{\partial \theta }.$$

Hence block internals are hidden once these interfaces are available.

Composition Patterns for Network Design

The lecture identifies three core composition patterns:

1. depth by stacking blocks sequentially (standard feed-forward composition);
2. skip connections by routing an earlier representation into a later block;
3. branching by producing multiple outputs from shared intermediate features.

A residual-style skip pattern can be written as

$$h_{l+1}=h_l+F(h_l;{\theta }_l),$$

illustrating that architecture design is fundamentally graph construction over differentiable operators.

Canonical Block Families

A linear feed-forward layer (MLP block) is the baseline module:

$$s=Wx+b,a=\sigma (s).$$

The lecture then positions additional families by inductive bias:

1. recurrent blocks for sequential dependencies;
2. convolutional blocks for local spatial structure;
3. attention-based blocks for content-dependent interactions.

All remain trainable with the same gradient-flow principle from Lecture 11.

Architecture-Level Taxonomy

The closing overview maps tasks to common deep architectures:

1. MLP for generic tabular/feed-forward settings;
2. RNN for sequential data;
3. CNN for vision-like local structure;
4. transformer models for attention-centric sequence modelling;
5. generative families including auto-encoder (AE), variational auto-encoder (VAE), and generative adversarial network (GAN);
6. graph neural architectures for relational/graph-structured data.

The common theme is not the optimisation algorithm, but the chosen structural prior encoded by block topology.

Differentiability and Practical Constraint

A direct implementation requirement is that optimisation by backpropagation needs differentiable computational paths. The lecture notes that non-differentiable deep models can exist, but then standard backpropagation is not directly applicable and alternative optimisation schemes are required.

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. the forward/backward interface view of a neural block;
2. why stacking, skipping, and branching are the core architecture operators;
3. how different architecture families encode different inductive biases;
4. why all differentiable architectures share the same backpropagation machinery;
5. when differentiability assumptions fail and what that implies for training.

This lecture bridges mathematical training rules and practical neural-network system design via a unified compositional perspective.

Lecture 13 Bias and Fairness in AI

This lecture formalises fairness questions for machine-learning systems that directly affect human decisions. The core message is that fairness is not a single mathematical property but a family of partially incompatible constraints that must be selected with domain-specific policy judgement.

Decision Setting and Error Decomposition

Assume binary classification with predicted label $\hat{Y}\in \{0,1\}$, true label $Y\in \{0,1\}$, and protected attribute $A\in \{0,1\}$. For each group $A=a$, fairness analysis starts from confusion-matrix quantities:

$${\mathrm{FPR}}_a=\mathbb{P}(\hat{Y}=1\mid Y=0,A=a),{\mathrm{FNR}}_a=\mathbb{P}(\hat{Y}=0\mid Y=1,A=a).$$

Overall error,

$$\mathrm{Err}=\frac{\mathrm{FP}+\mathrm{FN}}{\mathrm{TN}+\mathrm{FP}+\mathrm{FN}+\mathrm{TP}},$$

is often insufficient because two systems with similar total error can distribute harms differently across groups.

COMPAS as a Motivating Case

The COMPAS recidivism-risk system illustrates that close aggregate error rates do not imply comparable group-level treatment. In the lecture data, error rates are numerically similar across groups, but false-positive and false-negative rates differ substantially between Black and White defendants. Hence fairness auditing must inspect conditional error profiles, not only aggregate accuracy.

This is a canonical example where stakeholders value different error types: defendants are disproportionately affected by high false-positive risk assignments, while judicial institutions may focus on false negatives related to missed high-risk cases.

Fairness Through Unawareness Is Insufficient

Removing protected attributes from the input does not generally remove discriminatory effects. Let $X$ denote non-sensitive features and $A$ protected status; in practice $X$ may contain proxies with high mutual information with $A$ (for example through location, spending, or administrative history). A learner can therefore reconstruct group information implicitly and reproduce disparate outcomes even when $A$ is omitted.

Group Fairness Criteria

The lecture contrasts three standard criteria.

1. Demographic parity (naive statistical parity):

$$\mathbb{P}(\hat{Y}=1\mid A=1)=\mathbb{P}(\hat{Y}=1\mid A=0).$$

This equalises acceptance rates but ignores label prevalence and can be satisfied by trivial predictors.

2. Calibration of risk scores $S$:

$$\mathbb{P}(Y=1\mid A=1,S=s)=\mathbb{P}(Y=1\mid A=0,S=s)=s.$$

This requires equal semantic meaning of the score across groups, but does not force equal error rates.

3. Error-rate balance:

$$\mathbb{P}(\hat{Y}=1\mid Y=0,A=1)=\mathbb{P}(\hat{Y}=1\mid Y=0,A=0),$$ $$\mathbb{P}(\hat{Y}=0\mid Y=1,A=1)=\mathbb{P}(\hat{Y}=0\mid Y=1,A=0).$$

This enforces parity of false-positive and false-negative rates across groups.

Impossibility and Policy Choice

A central theoretical result is that, except for special cases (notably perfect prediction or equal base rates $\mathbb{P}(Y=1\mid A=0)=\mathbb{P}(Y=1\mid A=1)$), one cannot in general satisfy calibration and error-rate balance simultaneously. Therefore fairness design is not a purely technical optimisation target with a unique solution; it is a constrained policy choice requiring explicit normative priorities.

Individual Fairness Perspective

Group criteria can be complemented by individual fairness: similar individuals should receive similar predictions. If $d_X(x,x^{\prime })$ is a task-relevant metric on feature space, one seeks score mappings $S$ with controlled Lipschitz behaviour, informally

$$|S(x)-S(x^{\prime })|\le L{d}_X(x,x^{\prime }).$$

The major practical difficulty is defining a defensible similarity metric $d_X$.

Fair Regression Construction

For linear regression with sensitive variable $s$,

$$y=b_0+b_1{x}_1+\cdots +b_k{x}_k+\beta s,$$

the lecture presents a simple post-estimation adjustment:

$${\hat{y}}_{\mathrm{fair}}=b_0+b_1{x}_1+\cdots +b_k{x}_k+c,$$

where a group-invariant constant $c$ replaces the sensitive term. Typical choices include matching one reference group (for example $c=0$ or $c=\beta$ depending on coding) or preserving the training-set mean effect via $c=\beta \bar{s}$. This is an average correction, not a full guarantee of non-discrimination.

Bias, Cost Asymmetry, and Transparency

Dataset bias propagates into learned predictors and may even be amplified by modelling choices. In deployment, false positives and false negatives often carry asymmetric costs, so objective design should weight them according to domain risk rather than default symmetric error minimisation.

To support accountability, the lecture highlights model cards as structured documentation of intended use, evaluation setting, limitations, and ethical considerations.

Human Decision Makers and Risk Scores

The Kentucky Pretrial Risk Assessment (KPRA) example shows that “human in the loop” does not automatically neutralise bias. After a policy change that made non-financial bonds the default for low/moderate risk categories, evidence indicates stronger judicial deviation from recommendations for moderate-risk Black defendants than for comparable White defendants. Thus unequal outcomes can emerge from interaction between model outputs, policy defaults, and human discretion.

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. why fairness analysis must separate aggregate error from group-conditional error;
2. formal definitions and trade-offs of demographic parity, calibration, and error-rate balance;
3. why fairness through unawareness is insufficient under proxy features;
4. the incompatibility insight linking base rates, calibration, and error-rate parity;
5. individual fairness as a metric-based constraint and its practical bottleneck;
6. the fair-regression constant-replacement construction and its limits;
7. why transparency artefacts and human-in-the-loop deployment are necessary but not sufficient safeguards.

This lecture shifts machine learning from pure predictive performance to socio-technical system design under explicit fairness constraints.

Lecture 14 Reinforcement Learning

This lecture introduces reinforcement learning (RL) as a sequential decision framework in which an agent interacts with an environment, receives rewards, and learns a policy that optimises long-run return rather than one-step prediction accuracy.

Core Agent-Environment Formalism

At time step $t$, the agent observes state $S_t$, chooses action $A_t$, receives reward $R_{t+1}$, and transitions to $S_{t+1}$. For discount factor $\gamma \in [0,1)$, return is

$$G_t:=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots =\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}.$$

The objective is to find policy $\pi$ maximising

$${\mathbb{E}}_{\pi }[G_t\mid S_t=s].$$

Hence RL optimisation is dynamic and trajectory-level, not i.i.d. sample-level as in supervised learning.

Value Functions and Bellman Structure

For a fixed policy $\pi$, the state-action value function is

$$q_{\pi }(s,a):={\mathbb{E}}_{\pi }[G_t\mid S_t=s,A_t=a].$$

Control methods approximate optimal action values and derive greedy or near-greedy policies. The lecture emphasises that Bellman operators provide the structural recursion behind update rules.

Q-Learning

Given transition sample $(s_t,a_t,r_{t+1},s_{t+1})$, tabular Q-learning updates only the visited pair:

$$Q_{t+1}(s_t,a_t)=Q_t(s_t,a_t)+{\alpha }_t\left(r_{t+1}+\gamma \underset{a}{\max }{Q}_t(s_{t+1},a)-Q_t(s_t,a_t)\right),$$

with learning rate ${\alpha }_t\in [0,1]$. This is a stochastic approximation / semi-gradient form with temporal-difference target

$$r_{t+1}+\gamma \underset{a}{\max }{Q}_t(s_{t+1},a).$$

Speedy Q-Learning

The lecture discusses Speedy Q-learning, which introduces a correction using both $Q_t$ and $Q_{t-1}$ under the empirical Bellman operator to accelerate convergence behaviour. Conceptually, it modifies the basic TD recursion by adding a term that compensates for drift between successive iterates.

Distributional Reinforcement Learning

Instead of learning only expected return, distributional RL models the full return random variable

$$Z_{\pi }(s,a):=\sum _{t=0}^{\infty }{\gamma }^t{R}_t,Q_{\pi }(s,a)=\mathbb{E}[Z_{\pi }(s,a)].$$

This yields risk-sensitive information (tail behaviour, spread, multimodality) unavailable from expectation-only methods. In categorical distributional RL, one discretises return support and studies contraction of projected Bellman updates in suitable metrics (here, Cramer-type ${\ell }_2$ distance).

PAC-Style Guarantees for Distributional RL

A key theoretical block in the lecture is a Probably Approximately Correct (PAC) analysis for a speedy categorical distributional update under assumptions including finite state-action space, bounded rewards, $\gamma <1$, and Robbins-Monro style step-size conditions.

The resulting high-probability bound has the canonical form

$${\ell }_2({\eta }^C,{\eta }_k)\le C\left({\sqrt{\gamma }}^k+\sqrt{\frac{\log (1/\delta )}{k}}\right)$$

with probability at least $1-\delta$, where ${\eta }_k$ is the iterate and ${\eta }^C$ the fixed point of the projected distributional Bellman operator. The first term captures contraction bias decay; the second captures stochastic estimation error.

Proof Architecture and Concentration

The proof strategy presented in the lecture follows five components: stability of iterates as probability measures, martingale-difference representation of error processes, inductive recursion bounds, maximal Hoeffding-Azuma concentration at atom level, and inversion to obtain explicit $\epsilon (\delta )$ confidence-style guarantees.

This connects RL convergence analysis to the same probability toolkit used in generalisation theory: concentration inequalities translate random-sample effects into explicit confidence bounds.

Policy Evaluation and Off-Policy Difficulty

After learning a policy, independent evaluation is essential. In particular, off-policy evaluation (estimating performance of a target policy from data generated by another behaviour policy) is highlighted as intrinsically difficult and variance-sensitive, motivating robust lower-confidence validation procedures in high-stakes applications.

Empirical Scope and Application Cases

The lecture situates RL across game domains (Atari, chess, Go), control (autonomous driving, industrial automation), and scientific/medical decision support. AlphaGo/AlphaZero-style results are used to illustrate that a single RL framework with minimal domain priors can achieve superhuman performance in complex sequential tasks.

Applied case studies from autonomous driving, cryogenic detector control, and sepsis treatment are used to motivate distributional RL and policy-evaluation methodology in safety-critical settings.

Exam-Oriented Takeaways

For this lecture, you should be able to reconstruct and justify:

1. the agent-environment loop and discounted return objective;
2. definitions of $q_{\pi }$, Bellman-style targets, and the Q-learning update;
3. why Speedy Q-learning modifies standard temporal-difference recursion;
4. expectation-based versus distributional RL, including $Z_{\pi }$ and $Q_{\pi }=\mathbb{E}[Z_{\pi }]$;
5. the structure of PAC-style high-probability error bounds in distributional RL;
6. where martingale concentration (Hoeffding-Azuma) enters the analysis;
7. why off-policy evaluation is difficult and central for reliable deployment.

This lecture extends machine learning from static prediction to sequential optimisation under uncertainty, where both asymptotic convergence and finite-sample reliability must be analysed.