Lecture 1: Supervised Learning

Block 4.2 Advanced AI

Eoin O’Brien

Introduction

AI, machine learning, deep learning

• Artificial intelligence (AI): systems intended to exhibit intelligent behaviour
  • includes logic, search, probabilistic reasoning and machine learning
• Machine learning (ML): fits mathematical models to observed data
  • a subset of AI, not a synonym for it
• Deep neural network: one type of machine-learning model
• Deep learning: fitting deep neural networks to data
• Machine learning is commonly divided into
  • supervised learning
  • unsupervised learning
  • reinforcement learning

Start with the taxonomy, not a history of AI. The distinction that matters today is AI > machine learning > deep learning.

Chapter 1 is the source framing. Keep this factual and quick.

TIMING: ~4 min.

Supervised learning

Definition 1 A supervised-learning model maps an input to an output prediction and is fitted using observed input/output pairs.

• Input: the information available to the model
• Target: the output we want it to predict
• Model: a mathematical mapping from input to prediction
• Training data: labelled pairs \(\{x_i, y_i\}\)
• Training / fitting: choose a model from a family using those pairs
• Inference: apply the fitted model to an input to make a prediction

PROMPT: which of these already exists as an object in software they have built?

Keep “supervision” tied to the labelled input/output pairs. Do not open loss yet.

TIMING: ~4 min.

Regression and classification

Problem	Target	Output
regression	one continuous quantity	one number
multivariate regression	several continuous quantities	several numbers
binary classification	one of two categories	probabilities over two categories
multiclass classification	one of \(N\) categories	probabilities over \(N\) categories

• Univariate regression
  • one input
  • one continuous target
  • one predicted number

The classification examples use probability vectors. Do not generalise that into a claim about every possible classifier implementation.

TIMING: ~4 min.

Inputs and outputs

• A real-world input is encoded as numbers before the model sees it
• The model maps numerical input to numerical output
• The output is then interpreted as a real-world prediction

• Tabular: fixed set of features
  • square footage, bedrooms, mass, temperature
  • reorder the features and rebuild the model: the meaning should not change
• Ordered: sequence matters
  • text: my wife ate the chicken \(\neq\) the chicken ate my wife
• High-dimensional / structured
  • audio, images, molecules
  • many numbers, with important structure in how they are arranged

A ten-second audio clip sampled at \(44.1\,\text{kHz}\) contains 441,000 samples.

The point is not “everything is a vector” as a slogan. The point is that the model receives a numerical representation, and the representation has structure.

TIMING: ~4 min.

Model family and training

• A model is a mathematical equation relating input to output
• Usually the equation contains parameters: numbers not fixed in advance
• Different parameter settings give different input/output relationships
• Together those relationships form a model family
• Training searches that family for a setting that describes the training pairs well

\[ \vect{y} = \vmodel{\vect{x}} \qquad \hat{\params} \in \argmin_{\params}\loss[\params] \tag{1}\]

• \(\vmodel{\vect{x}}\): parameters fixed, input varies — inference
• \(\loss[\params]\): data fixed, parameters vary — training

Notation

The book writes the parameter setting in square brackets and the ordinary function argument in round brackets. We keep that distinction.

This replaces the previous three-slide detour through the supervised-learning frame. The family/setting distinction is load-bearing; spend the time there.

Do not define argmin yet. They only need to read the expression as “choose parameters that minimise the loss”. MIN AND ARGMIN makes the type precise later.

TIMING: ~5 min.

Linear models

The dataset

Speed and stopping distance for 50 cars.

• Input \(x\): the speed the car was travelling, in miles per hour
• Target \(y\): the distance it took to stop, in feet
• 50 observations at 19 distinct speeds, recorded in the 1920s on 1920s cars (Ezekiel 1930)
• Observation: a pair in the product of the input and output spaces. The input space is the horizontal axis alone.

How can we model the relationship between speed and stopping distance? Could we use a line?

Say the 1920s once, here. It comes back at the negative intercept and at population risk.

The leading rownames column is an export artefact.

TIMING: ~4 min.

Slope and intercept

\[ y = \model{x} = \phi_0 + \phi_1 x \tag{2}\]

• Model: intercept plus slope times input
• Shape: two parameters, one input, one output
• Units
  • \(\phi_0\) is in feet
  • \(\phi_1\) is in feet per mile per hour
  • …so the two parameters aren’t interchangeable: neither their values nor their changes can be compared with each other

The fitted setting is \(\phi_0 =\) -17.6 feet and \(\phi_1 =\) 3.93 feet per mile per hour. A stationary car takes a negative distance to stop.

• At \(x=0\), the model is extrapolating
• The slowest observed car is doing 4 miles per hour
• No physical constraint is imposed at \(x=0\)

PROMPT: the model says a stationary car takes a negative distance to stop. Is the model wrong, the data wrong, or the question wrong?

LISTEN FOR: “the model is broken”. It’s answering a question outside the range it was fitted on, exactly as instructed.

Do NOT name distribution shift. Extrapolation is the point of the slide; distribution shift is week 4.

TIMING: ~4 min.

Picking parameters

Three parameter settings on the same data.

DEMO. Reveal the lines one at a time if the room is fresh.

PROMPT before the fitted line: which of A and B is better, and on what evidence?

LISTEN FOR: “it looks closer”. Right, and not yet a number.

TIMING: ~4 min.

Prediction, target, residual

• Prediction: the model’s output for a given input, \(\model{x_i}\)
• Target or ground truth output: the observed output for a given input, \(y_i\)
• Residual or deviation: the difference between the target and the prediction
  • Some texts give \(y_i - \model{x_i}\), others give \(\model{x_i} - y_i\) (UDL does the latter)
  • Same magnitude, opposite sign
  • Squared in practice, so the sign doesn’t matter
• Shape: one residual per \(\{x_i, y_i\}\) pair, so a vector of \(I\) residuals

One car was doing 14 mph and took 80 ft. Under candidate B, \(\phi_0 = 0\) and \(\phi_1 = 3\). What is the residual, and what is its sign?

The prediction is 42 ft; the residual is +38 ft. The line sits below the observation.

TRY, two of the four minutes. Everybody commits to the sign first.

If asked why target minus prediction: statistics writes observed minus fitted, linear algebra writes r = b - Ax. The book subtracts the other way and squares it immediately. Once, then move.

TIMING: ~4 min.

From residuals to loss

How useful is a residual vector?

• Two candidate lines give two vectors of \(I\) residuals
  • Residual vectors have no natural total ordering
  • …so “which is better” has no default answer
• Searching for optimal parameters requires a way to compare them, so each residual vector must be reduced to one score
• We choose the convention that smaller is better
  • Fitting the model reduces to minimising that score

The scalar score is part of the model design.

PROMPT: turn fifty residuals into one number. Three proposals on the board before anything is shown.

LISTEN FOR: the mean of the raw residuals. The productive wrong answer – do not correct it here.

FORWARD: week 2 asks where this choice comes from. Today it’s a choice with reasons.

TIMING: ~4 min.

Scoring residuals

• What if we just sum the residual vector?
  • Trivially poor: a badly wrong line can score zero if the residuals cancel
  • We want a criterion where the direction of a residual does not matter, only its size
• What if we sum the absolute values?
  • Better: the absolute value \(|\model{x_i} - y_i| = |y_i - \model{x_i}|\) is always non-negative
  • But one prediction off by 2 is treated the same as two predictions off by 1
  • Not differentiable everywhere, a big problem for gradient-based optimisation
• What if we sum the squares?
  • Better still: the square \((\model{x_i} - y_i)^{2} = (y_i - \model{x_i})^{2}\) is always non-negative
  • Penalises one large residual more than several small ones
  • Differentiable everywhere, so gradient-based optimisation works

PROMPT: a two-point dataset where the raw sum of residuals is zero and the line is obviously wrong. Thirty seconds.

DO NOT derive the square from a likelihood. Week 2.

TIMING: ~4 min.

Least-squares loss

Definition 2 The least-squares loss is the sum of the squares of the residuals over the training pairs.

\[ \loss[\params] = \sum_{i=1}^{I} \left(\model{x_i} - y_i\right)^{2} = \sum_{i=1}^{I} \left(\phi_0 + \phi_1 x_i - y_i\right)^{2} \tag{3}\]

• Shape: \(I\) residuals in, one scalar out
• Units: ft². Squaring makes the units mathematically clear
  • …but less directly interpretable than the residuals themselves.
• Notation: \(\loss\) is the quantity aggregated over the dataset; \(\exloss_i\) is one example’s contribution

• Some sources distinguish between loss and cost:
  • A loss function calculates the loss for a single training example
  • A cost function aggregates the loss over the entire training dataset

Equation 2.5 calls the quantity total mismatch, training error, or loss. Mention the aliases once and move.

TIMING: ~4 min.

Mean squared error

• Normalising the least-squares loss over the number of examples \(I\) yields the mean squared error
  • The advantage is that the MSE is independent of the dataset size
  • It can be compared across datasets meaningfully
• The two differ by a positive constant factor \(\frac{1}{I}\)

\[ \text{MSE}[\params] = \frac{1}{I}\loss[\params] \tag{4}\]

• Multiplying a function by a positive constant leaves its set of minimisers unchanged and scales the minimum value by that constant
• The argmin is unchanged
  • The minimum value is scaled by \(I\).
• Take care not to confuse the two!
  • Not numerically interchangeable unless the factor \(I\) is accounted for

DO NOT SAY “the same minimiser”. Same SET, and whether it has one element is settled two slides on.

One sentence on why the mean: it removes the trivial scaling with dataset size. It does not by itself make losses comparable across different targets or populations.

Friday’s brief asks students what units their reported loss is in.

TIMING: ~4 min.

Scoring two candidates

• A: \(\phi_0 =\) 20 feet, \(\phi_1 =\) 2 feet per mph
• B: \(\phi_0 =\) 0 feet, \(\phi_1 =\) 3 feet per mph
• Commit first: which scores lower?

Note that we can calculate the residuals either way; the squares will be identical:

\(x_i\)	\(y_i\)	\(\phi_0 + \phi_1 x_i\)	residual	squared
4	2	12	-10	100
4	10	12	-2	4
7	4	21	-17	289
7	22	21	+1	1

Sum the other 46 the same way, divide by 50: A scores 390.5 and B scores 261.3 ft².

B scores lower (better) on this dataset.

WORKED. Loading and plotting are given; the arithmetic is theirs.

Show of hands BEFORE the table. A prediction nobody committed to isn’t a prediction.

TIMING: ~5 min.

Loss as a function of parameters

• When working with loss, the data is fixed and the parameters vary.
  • During inference, the parameters are fixed and the data varies.
• So the loss is a function of the parameters, and we write \(\loss[\params]\)

Object	Takes	Returns
the model \(\model{x}\)	an input	a prediction
the loss \(\loss[\params]\)	a parameter setting	one non-negative scalar

• Model and loss are different functions of different variables
• Here the loss takes two parameters and returns one scalar
• The data is held constant, so we don’t have to write it as an argument

Data dependence

Add one more car and \(\loss\) becomes a different function! The notation suppresses the data, but the dependency remains.

The sentence they must reconstruct in the consolidation. If it doesn’t land, PARAMETER SPACE doesn’t work.

PROMPT: what happens to the loss if I add one more car?

TIMING: ~4 min.

Parameter space

Space exploration

Candidate lines and their points in parameter space.

Space exploration (cont.)

Space	Dim.	One point	Where?
input	1	speed (mph)	left plot, x-axis
output	1	stopping distance (ft)	left plot, y-axis
input–output	2	observation \((x,y)\)	left plot
parameter	2	one line/model setting	right plot

• One point in parameter space selects a model (line).
• The scatter plot is not a plot of the input space.
  • It’s both input and output, so it’s a plot of the input–output space.

Draw the correspondence both ways, twice: a spot on the parameter plane, then a line on the left panel.

LISTEN FOR: the scatter plot called “the input space”. The most common wrong sentence today.

Leave the figure up.

TIMING: ~5 min.

Is this loss?

Mean squared error as a surface and as contours.

Is this loss? (cont.)

• The loss assigns one scalar to every point of the parameter plane
  • The left panel represents that scalar as height
  • The right panel shows the same function from above using contours
• Shape: a function from two dimensions to one
  • …hence the 3-dimensional plot
• For this dataset, model family and loss, the surface has one lowest point

DEMO. Evaluate the loss everywhere and look at what comes out.

Friday’s lab replicates this exactly. Say so, and leave it there.

This is one dataset, one model family and one loss. The picture establishes the shape of this particular objective; it does not establish a general shape for machine-learning losses.

TIMING: ~5 min.

Reading the contours

Mean squared error contours in parameter space.

Definition 3 A contour is the set of parameter settings sharing one loss value.

• Contours packed closely means the loss changes quickly for a small move in that direction
• Elongated contours say the loss is more sensitive along some directions than others
  • they identify a particular parameter as more or less sensitive only when those directions line up with the coordinate axes
• Here the long direction is tilted relative to the parameter axes
  • move along it and a rise in the intercept trades against a fall in the slope
  • the fitted line changes much less than it would for a move across the contours

PROMPT: two moves of equal length from the lowest point, one along a contour and one across. Which costs more?

Do not explain the tilt algebraically yet. The linear-algebra primer follows the one-input fit and supplies the dot product and matrix language.

If asked whether the tilt has a name: week 3, conditioning.

TIMING: ~4 min.

Min and argmin

• min: smallest loss value
  • a scalar, in ft² — 227.1 as a mean, or 11,354 as the chapter-2 sum
• argmin: parameter settings attaining that value
  • a subset of the parameter plane

\[ \min_{\params}\left[\loss[\params]\right] \in \reals \qquad\qquad \argmin_{\params}\left[\loss[\params]\right] \subseteq \reals^{2} \tag{5}\]

• The text writes \(\hat{\params} = \argmin_{\params}[\loss[\params]]\).
  • This assumes that the minimiser is unique (a common shorthand)
• Pedantically, it’s a set, so \(\hat{\params} \in \argmin_{\params}[\loss[\params]]\)
  • The set of minimisers may have more than one element!
• Non-unique minimum: a flat valley would give one minimum value and infinitely many elements of the argmin

PROMPT: a function where the min exists and the argmin has more than one element. A constant function, then \(\cos\).

LISTEN FOR: “argmin is where the minimum is”. Right instinct, wrong type.

Friday’s brief asks for both argmin coordinates and the loss value there, as two separate reports.

TIMING: ~5 min.

Fitting the line

Fitting

Definition 4 Fitting is choosing a parameter setting \(\hat{\params}\) that minimises the loss over the training data, i.e. an element of the argmin.

\[ \hat{\params} \in \argmin_{\params}\left[\sum_{i=1}^{I}\left(\phi_0 + \phi_1 x_i - y_i\right)^{2}\right] \tag{6}\]

• For this model and squared loss, the minimiser is unique provided at least two input values differ
  • if every input were identical, intercept and slope would trade off exactly
  • an entire line of the parameter plane would score the same
• With two distinct input values, the least-squares minimiser is unique.
• Fitting, training and learning are interchangeable terms for the same process

Degenerate case on the board, thirty seconds: every car at the same speed – the dataset they built themselves at the hour, in round 3.

This is the claim Friday’s brief narrows.

TIMING: ~4 min.

Finding the minimum

• So, how can we find the minimum?
• We could draw a grid over the parameter plane and sample every point
• Easy to draw, and all we have to do is calculate the loss for each point
  • Then pick the smallest!
• Is this a good idea?
• The grid returns the best point on the grid
  • Whether that’s close to the best point on the plane is another story

Search	\(\argmin\)	min MSE (ft²)
201-point grid	(-17.500, 3.920)	227.0872
exact	(-17.579, 3.932)	227.0704

• A closed-form solution also exists for this model.
  • We can’t have nice things; in general, no closed-form solutions exist for more complex models
• There are much better ways to optimise!

Do NOT teach descent. The enumeration wall has to be hit first.

The last bullet is Friday’s lab in one line. Say it, don’t develop it.

TIMING: ~3 min.

Linear algebra

Scalars and scalar arithmetic

• A scalar is one real number: \(a \in \mathbb{R}\)
• Add or subtract scalars in the usual way
  • \(a+b \in \mathbb{R}\)
  • quantities being added must have compatible units (anyone do applied maths or physics?)
• Multiply scalars in the usual way
  • \(ab \in \mathbb{R}\)
• A scalar can scale a vector or matrix via scalar multiplication
  • \(a\vect{x}\) for a vector, \(a\mat{A}\) for a matrix

\[ 3 + (-1) = 2 \qquad 3(-1) = -3 \]

• Technically, a scalar is an element of a field used to define a vector space
  • But for us, that field is always \(\mathbb{R}\) and the vector space is always \(\mathbb{R}^{\dimension}\)

Fast. The useful point is not arithmetic; it is that scalar multiplication will act on every entry of the object beside it.

TIMING: ~2 min.

Vectors: addition and scaling

• A vector in \(\mathbb{R}^{\dimension}\) is represented by \(\dimension\) coordinates
  • written as a column unless stated otherwise
  • shape \((\dimension \times 1)\)
• Vector addition: same length, entry by entry
• Scalar multiplication: multiply every entry by the scalar

\[ \begin{bmatrix}1\\2\\3\end{bmatrix} + \begin{bmatrix}4\\-1\\2\end{bmatrix} = \begin{bmatrix}5\\1\\5\end{bmatrix} \qquad 2\begin{bmatrix}1\\2\\3\end{bmatrix} = \begin{bmatrix}2\\4\\6\end{bmatrix} \]

• \(\vect{x}+\vect{y}\) requires the same shape
• \(a\vect{x}\) has the same shape as \(\vect{x}\)
• Adding a scalar to a vector is not a standard linear-algebra operation
  • Various libs will try to help by broadcasting the scalar over the vector and adding elementwise
  • Useful feature (no need to manually build a vector first) and potential footgun

PROMPT: what shape comes out of each operation?

Use “represented by coordinates” rather than “is an ordered list”. BASIS later can then distinguish the vector from one coordinate representation of it.

TIMING: ~4 min.

The dot product: multiplying two vectors

Definition 5 For vectors of the same length, the dot product multiplies corresponding entries and adds the results.

\[ \inner{\vect{a}}{\vect{b}} = \vect{a}\transpose\vect{b} = \sum_{d=1}^{\dimension} a_d b_d \tag{7}\]

For non-zero vectors:

• \(\inner{\vect{a}}{\vect{b}} > 0\): angle \(<90^\circ\) — broadly aligned
• \(\inner{\vect{a}}{\vect{b}} = 0\): angle \(=90^\circ\) — orthogonal
• \(\inner{\vect{a}}{\vect{b}} < 0\): angle \(>90^\circ\) — broadly opposed

\[ \inner{\vect{a}}{\vect{b}} = \norm{\vect{a}}\,\norm{\vect{b}}\cos\theta \tag{8}\]

• Result: one scalar
• Magnitude depends on both length and alignment
• Entrywise multiplication is a different operation, usually written \(\vect{a}\odot\vect{b}\)

Read the sign cases as a table of meanings, not as a paragraph.

Work \((1,0)\cdot(1,1)\), \((1,0)\cdot(0,1)\) and \((1,0)\cdot(-1,1)\) quickly.

TIMING: ~5 min.

Norms

• A norm maps a vector to a non-negative scalar measuring its size

\[ \norm{\vect{z}}_p = \left(\sum_{d=1}^{\dimension}|z_d|^p\right)^{1/p}, \qquad p \ge 1 \tag{9}\]

• \(p=1\): \(\norm{\vect{z}}_1 = \sum_d |z_d|\)
• \(p=2\): Euclidean length, usually written \(\norm{\vect{z}}\)
• Different norms can rank error patterns differently

Norms (cont.)

Same L1 norm; different L2 norm.

The application now lands immediately: the residual vector appears later, and this is why choosing a norm becomes choosing how to aggregate mistakes.

TIMING: ~4 min.

Matrices: addition and scaling

• A matrix is a rectangular array with shape \((\dimension_1 \times \dimension_2)\)
• \(A_{ij}\): row \(i\), column \(j\)
• Matrix addition: same shape, entry by entry
• Scalar multiplication: multiply every entry
• Transpose: swap rows and columns

\[ \mat{A}=\begin{bmatrix}1&2\\3&4\end{bmatrix}, \qquad \mat{B}=\begin{bmatrix}5&6\\7&8\end{bmatrix} \]

\[ \mat{A}+\mat{B} =\begin{bmatrix}6&8\\10&12\end{bmatrix} \qquad 2\mat{A} =\begin{bmatrix}2&4\\6&8\end{bmatrix} \]

• \(\mat{A}+\mat{B}\) requires identical shapes
• \(a\mat{A}\) keeps the shape of \(\mat{A}\)
• \(\mat{A}\transpose\) has shape \((\dimension_2 \times \dimension_1)\)

Keep this parallel with the vector slide: same-shape addition; scalar multiplication preserves shape.

TIMING: ~4 min.

Matrix–vector multiplication

• \(\mat{A}\) has shape \((m\times n)\)
• \(\vect{x}\) has shape \((n\times1)\)
• \(\mat{A}\vect{x}\) has shape \((m\times1)\)

Row view: each output is a dot product.

\[ \mat{A}\vect{x} = \begin{bmatrix} a_{11} & \cdots & a_{1n}\\ \vdots & \ddots & \vdots\\ a_{m1} & \cdots & a_{mn} \end{bmatrix} \begin{bmatrix} x_1\\ \vdots\\ x_n \end{bmatrix} = \begin{bmatrix} a_{11}x_1+\cdots+a_{1n}x_n\\ \vdots\\ a_{m1}x_1+\cdots+a_{mn}x_n \end{bmatrix} \]

Each row of \(\mat{A}\) produces one entry of the output.

Geometrically, column \(j\) of \(\mat{A}\) is where the basis vector \(\vect{e}_j\) is sent.

This is the operation MANY INPUTS AT ONCE needs. Make the row-dot-product reading explicit; it is more useful here than abstract matrix multiplication first.

TIMING: ~4 min.

Matrix-matrix multiplication

• \(\mat{A}\): \((m\times n)\)
• \(\mat{B}\): \((n\times p)\)
• Inner dimensions agree, so \(\mat{A}\mat{B}\) is defined
• Result: \((m\times p)\)

\[ (m\times n)(n\times p)\rightarrow(m\times p) \qquad C_{ij}=\sum_{d=1}^{n}A_{id}B_{dj} \tag{10}\]

• Entry \(C_{ij}\) = row \(i\) of \(\mat{A}\) dotted with column \(j\) of \(\mat{B}\)
• In general, \(\mat{A}\mat{B}\neq\mat{B}\mat{A}\)
• \((\mat{A}\mat{B})\transpose=\mat{B}\transpose\mat{A}\transpose\)

Matching shapes

Defined? Resulting shape?

1. \((4\times3)(3\times5)\)
2. \((5\times2)(5\times2)\)
3. \((1\times7)(7\times1)\)

What about the reverse?

TRY, two minutes. Answers: 4x5; undefined; 1x1 and 7x7.

Do not call matrix multiplication “elementwise multiplication”. If they ask, name Hadamard multiplication and move on.

TIMING: ~5 min.

Arithmetic at a glance

Expression	Requirement	Result
\(a+b\)	scalars	scalar
\(ab\)	scalars	scalar
\(\vect{x}+\vect{y}\)	same vector shape	vector
\(a\vect{x}\)	scalar and vector	vector
\(\vect{x}\transpose\vect{y}\)	same vector length	scalar
\(\mat{A}+\mat{B}\)	same matrix shape	matrix
\(a\mat{A}\)	scalar and matrix	matrix
\(\mat{A}\vect{x}\)	inner dimensions agree	vector
\(\mat{A}\mat{B}\)	inner dimensions agree	matrix

Addition matches shapes. Dot and matrix products match inner dimensions.

Retrieval slide. Point at an expression; room gives requirement and output type.

TIMING: ~3 min.

Notation and shapes

Object	Written	Shape
scalar	\(x\)	one number
vector	\(\vect{x}\)	\((\dimension\times1)\) by default
matrix	\(\mat{A}\)	\((\dimension_1\times\dimension_2)\)
tensor	bold symbol	\(\dimension_1\times\dots\times\dimension_N\)

• Boldness carries type information
• PyTorch and TensorFlow use tensor for storage objects of many ranks
• Always track the mathematical shape, not just the library type

No notation archaeology. The only outcome is that they can type-check expressions by inspection.

TIMING: ~3 min.

Maps, linear maps, affine maps

• A map \(f:\set{X}\to\set{Y}\) sends each input to exactly one output
• A map is linear when

\[ f(a\vect{u}+b\vect{v})=a f(\vect{u})+b f(\vect{v}) \] {#def-linear-map}

• Linear maps preserve addition and scalar multiplication
• Therefore \(f(\vect{0})=\vect{0}\)
• Between finite-dimensional vector spaces, a linear map has a matrix representation once bases are chosen

An affine map adds a translation:

\[ f(\vect{x})=\mat{W}\vect{x}+\vect{b} \tag{11}\]

• affine is linear iff \(\vect{b}=\vect{0}\)
• \(y=mx\) is linear; \(y=mx+c\) is affine
• nn.Linear is usually affine because it includes a bias

“Linear regression” refers to linearity in the parameters. With an intercept, the fitted function is affine in the input.

Teach the linear/affine distinction once, after the operations that define linearity.

TIMING: ~5 min.

Span, independence, basis

• A linear combination of \(\vect{v}_1,\ldots,\vect{v}_k\) is \(a_1\vect{v}_1+\cdots+a_k\vect{v}_k\)
• The span is the set of all such combinations
• Vectors are linearly independent when no one is a linear combination of the others
• A basis is linearly independent and spans the space

\[ \vect{e}_1=\begin{bmatrix}1\\0\\0\end{bmatrix},\quad \vect{e}_2=\begin{bmatrix}0\\1\\0\end{bmatrix},\quad \vect{e}_3=\begin{bmatrix}0\\0\\1\end{bmatrix} \]

\[ \begin{bmatrix}3\\-1\\4\end{bmatrix} =3\vect{e}_1-\vect{e}_2+4\vect{e}_3 \tag{12}\]

The numbers are coordinates in a basis. Change the basis and the coordinates change; the vector does not.

The independence condition returns at THE CLOSED FORM. No lattice-cryptography tangent here; it is not needed to carry this lecture.

TIMING: ~4 min.

Many inputs at once

More than one input

• Let’s think back to our car dataset
• Is speed the only factor in stopping distance?
• What the 1920s recorders didn’t write down
  • road surface, gradient, tyre condition, vehicle mass, driver reaction time
  • each could plausibly influence the stopping distance
• More inputs: one parameter per input, plus the intercept

\[ y = \phi_0 + \phi_1 x_1 + \phi_2 x_2 + \dots + \phi_{\dimension} x_{\dimension} \tag{13}\]

Indexing

Until now \(x_i\) meant example \(i\). Here \(x_1 \dots x_{\dimension}\) are the \(\dimension\) entries of one input. When both indices are needed, the example comes first: \(x_{id}\) is feature \(d\) of example \(i\).

• Prediction, residual, loss and fitting keep the same definitions
• Writing the scalar expression out becomes cumbersome as the feature count grows, so the notation now has to carry the dimensions

PROMPT: write the three-input model longhand. Now the thirty-input one. The groan is the motivation.

One input column in this dataset, so the need is honest rather than demonstrated.

TIMING: ~4 min.

The model as a dot product

• Augmented input: append a constant one and collect the intercept into the parameter vector

\[ \tilde{\vect{x}} = \begin{bmatrix} 1 \\ x \end{bmatrix} \qquad \params = \begin{bmatrix} \phi_0 \\ \phi_1 \end{bmatrix} \qquad \model{x} = \inner{\tilde{\vect{x}}}{\params} \tag{14}\]

• This is the same model as Equation 2 from A SLOPE AND AN INTERCEPT, written in vector notation. No new family or capability has been introduced.
• Shape check: parameter vector of length \(\dimension + 1\), augmented input the same, output a scalar
• Keeping the bias separate gives the equivalent form \(\mat{W}\vect{x} + \vect{b}\). PyTorch exposes these as .weight and .bias

Input vs parameters

The model is linear in the augmented input and remains affine in the original input. Appending a one is a bookkeeping convention, not a change of the map.

LISTEN FOR: relief. Then ask what the appended one MEANS – an input always present with value one.

\(\mat{W}\) and \(\vect{b}\) are the library’s letters. Per-layer notation is Friday’s.

TIMING: ~4 min.

The design matrix

Definition 6 The design matrix stacks the augmented inputs, one example per row.

\[ \mat{X} = \begin{bmatrix} 1 & x_1 \\ 1 & x_2 \\ \vdots & \vdots \\ 1 & x_I \end{bmatrix} \qquad \mat{X}\params = \begin{bmatrix} \model{x_1} \\ \model{x_2} \\ \vdots \\ \model{x_I} \end{bmatrix} \tag{15}\]

• Shape: \(I\) rows by \(\dimension + 1\) columns, and the column of ones is one of them
• Predictions: one per row, in a single product
• Which dimension disappears? \((I \times (\dimension{+}1)) ((\dimension{+}1) \times 1) \rightarrow (I \times 1)\). The parameter count is summed over; the example count survives.
• Orientation: rows are examples; columns are features. Transposing by accident is the most common shape bug in the first month.

TRY, one minute: the shape of the prediction vector, before the equation.

First four rows by hand from the dataset. Enough to see the column of ones, few enough that it isn’t copying.

TIMING: ~4 min.

The residual vector

Definition 7 The residual vector is the vector of targets minus the vector of predictions, one entry per example.

\[ \vect{r} = \vect{y} - \mat{X}\params \tag{16}\]

• Entry \(i\) is exactly the residual you computed by hand at PREDICTION, TARGET, RESIDUAL, under the same sign convention
• This matches the statistics convention: \(\vect{e} = \vect{y} - \hat{\vect{y}}\) and numerical linear algebra writes \(\vect{r} = \vect{b} - \mat{A}\vect{x}\). This is both of them.
• Shape: length \(I\). It lives in a space with one dimension per example.

Space	Dimension here	One point is
input	1	a speed
parameter	2	a whole line over every input
residual	50	one model’s mistakes, all of them

Three spaces are now in play. None of them substitutes for another.

• The loss can now be written with the Euclidean norm: \(\loss[\params] = \norm{\vect{r}}_2^{2}\) — the norm squared, not the norm
  • squaring is increasing on non-negative numbers, so it leaves the argmin unchanged and changes the minimum value unless that value is zero
• Choosing a different residual norm changes how large and small residuals are traded against one another — the earlier why square choice in compact notation

Not new: round 3 of the hour established that the design matrix reaches a two-dimensional plane inside a fifty-dimensional space. This is the space the rest of it lives in. Name it, count its dimension, move on.

The last fragment applies the Euclidean norm from the primer. Ask which of the two norm-example vectors would count as the worse residual pattern before saying it.

TIMING: ~5 min.

One more feature

Linear in the input, linear in the parameters

• Two notions of linearity
  • is it linear as a function of the input, with the parameters fixed?
  • is it linear as a function of the parameters, with the input fixed?
• Two-parameter line: affine in the input; linear in the parameters
  • hold \(x\) fixed, and \(\model{x} = \inner{\tilde{\vect{x}}}{\params}\) is a dot product with \(\params\) as the variable

\[ \loss[\params] = \sum_{i=1}^{I}\left(y_i - \inner{\tilde{\vect{x}}_i}{\params}\right)^{2} \tag{17}\]

• With every \(x_i\) and \(y_i\) fixed:
  • each residual is affine in \(\params\)
  • each squared residual is quadratic in \(\params\)
  • their sum is quadratic with a positive-semidefinite quadratic term
• The loss is therefore quadratic in the parameters, giving the bowl shape and the closed-form least-squares solution.

“Linear model” is ambiguous; this major avoids it unqualified.

PROMPT: fix the input at one value and write the model as a function of the two parameters. They will see a dot product.

Friday’s setup. Do not cut it.

TIMING: ~5 min.

Adding a squared term

• There is a physical reason to try a squared term, not merely a desire for more flexibility
  • stopping distance includes reaction distance and braking distance
  • under a simple braking model, braking distance grows approximately with the square of speed because kinetic energy grows with \(v^2\)
• Add a third design-matrix column holding \(x^{2}\) and a parameter multiplying it

\[ y = \phi_0 + \phi_1 x + \phi_2 x^{2} \tag{18}\]

• Family: the two-parameter family is contained in it, at \(\phi_2 = 0\).
• The new family cannot have higher training loss at its optimum: the old best is still available inside it at \(\phi_2=0\)
• Here the mean squared error falls from 227.1 to 216.5 ft² — an improvement of 4.7 per cent
• Unchanged: still a dot product, still linear in the parameters, still fitted by the same argmin, still a quadratic loss
  • the argmin itself moves, and gains a coordinate: it’s a point in three-dimensional parameter space now

WORKED, two of the five minutes: the new design matrix’s first three rows by hand.

A motivated term isn’t automatically a large win. Say so.

The containment argument is one sentence and it’s why the training loss can’t rise. Precisely, and without editorialising.

LISTEN FOR: “so bigger is always better”. WHAT WE HAVE NOT ESTABLISHED owns it.

TIMING: ~5 min.

Parameter space gains a dimension

• Parameter space is now three-dimensional
• The loss is a map from three dimensions to one
• Its full graph would need four, so THE LOSS SURFACE’s picture isn’t available for this model

Still drawable	What it shows	What it hides
a 2-D slice, \(\phi_2\) held fixed	the surface at one setting of the third parameter	everything at every other setting
a projection	the range of loss values	which setting produced each
an isosurface	one loss level in 3-D	the values between levels

• The picture was a teaching device tied to two parameters. The mathematics never depended on it.

DO NOT SAY “we can no longer visualise the loss”. Slices and isosurfaces are visualisations; what is gone is the single surface.

PROMPT: what would a slice at a fixed third parameter show, and what would it hide?

TIMING: ~4 min.

The closed form

For a model linear in its parameters under the squared loss, a least-squares minimiser satisfies the normal equations.

\[ \mat{X}\transpose\mat{X}\,\hat{\params} = \mat{X}\transpose\vect{y} \tag{19}\]

• Shape check: \(\mat{X}\transpose\mat{X}\) is square, with side equal to the parameter count
• If \(\mat{X}\) has full column rank, the minimiser is unique and the matrix \(\mat{X}\transpose\mat{X}\) is invertible
  • \(x^{2}\) is a function of \(x\) and is perfectly allowed: no weighted sum of the other columns reproduces it
  • checking pairs isn’t enough — the columns \(1\), \(x\) and \(1 + x\) are pairwise unrelated by scaling and still dependent
  • duplicate a column: the solution set becomes a line — Definition 4’s degeneracy in matrix form
• Here: 19 distinct speeds, so every polynomial design up to degree 18 has full column rank as mathematics

Normal equations: scope

The normal equations are specific to squared-error linear least squares. They do not carry over unchanged to absolute-error regression or to models nonlinear in their parameters.

The inverse formula \(\hat{\params}=(\mat{X}\transpose\mat{X})^{-1}\mat{X}\transpose\vect{y}\) is mathematically valid when full column rank holds, but numerical software should normally use a stable least-squares solver such as QR or SVD. Forming \(\mat{X}\transpose\mat{X}\) squares the condition number and can magnify numerical error.

The independence condition is theirs already from the primer. Ask for it back rather than stating it.

Whether this computation is numerically reliable is the next slide.

Do not derive the normal equations. Week 3, and promised there in writing.

TIMING: ~4 min.

Up to degree eleven

Line and degree-11 polynomial fitted to the same data.

• Powers of speed up to the eleventh give 12 parameters including the intercept
• Training mean squared error 227.1 for the line against 182.9 for the polynomial, in ft²

• Nonlinear in the input; still linear in its twelve parameters.
  • so the same closed form, the same argmin operation and the same quadratic loss shape all apply — over a twelve-dimensional parameter space, at a different minimiser
• Not established: that it is a better model. Only that it scores lower on the data it was fitted to.

DEMO. Push the machinery until it produces the object Friday needs.

Expect oscillation at the ends of the speed range. Show it.

Hold “is this good?” – two sections away.

The course stores the fit. Students keep nothing.

TIMING: ~3 min.

Rescaling the input

• The raw monomial columns live on radically different numerical scales
  • the first column is all ones
  • speed to the eleventh reaches about 2.4 × 10¹⁵ at the fastest car

Basis	Numerical rank	Condition number	Training MSE (ft²)	Prediction (ft)
raw powers of speed	8 of 12	5.1 × 10¹⁹	188.8	-103 to 95
speed scaled to \([-1, 1]\)	12 of 12	19,691	182.9	6 to 225

• The design matrix has full column rank as mathematics in either basis; what changes is its numerical conditioning
• In the raw basis, the numerical rank estimate drops by 4 columns and the computed fit has higher training loss even though both bases span the same polynomial family
  • that is evidence that the numerical procedure has not recovered the same least-squares solution
• The prediction ranges in the last column answer a different question: neither degree-eleven fit behaves sensibly near the ends of the observed speed range

Rescaling and conditioning

The least-squares problem has not changed. Rescaling gives the same polynomial family a much better-conditioned numerical representation, so the computation is more reliable. It repairs the arithmetic in this example; it does not make the degree-eleven model a good predictor.

The units point from A SLOPE AND AN INTERCEPT, arriving with consequences. Friday’s lab perturbs the input scale, so this is its setup.

Where the raw fit goes negative, if asked: about 4 to 7 mph, the bottom of the observed range. The scaled fit runs the other way, to 225 feet.

Do not teach centring as a technique.

TIMING: ~3 min.

When enumeration stops working

Grid search, counted

• Put a uniform grid of \(k\) points on each of \(P\) parameter axes
• The exhaustive product grid contains \(k^P\) parameter settings

\[ N = k^{\,P} \tag{20}\]

• Holding the per-axis resolution fixed makes the total count multiplicative across dimensions.

Before the table: write down your estimate for twelve parameters, at the resolution from HOW WOULD YOU ACTUALLY FIND IT?

parameters	evaluations at 201 points per axis
2	40,401
3	8,120,601
12	4.3 × 10²⁷

Uniform-grid cost

This is a property of a uniform product grid at fixed per-axis resolution. It’s not a theorem about optimisation. Nor is it a claim that the problem is hard.

TRY, two minutes. Estimates first, IN WRITING, or the gap evaporates.

TIMING: ~5 min.

Two parameters, twelve parameters

parameters	evaluations	wall clock
2	40,401	0.1 seconds
3	8,120,601	19.0 seconds
12	4.3 × 10²⁷	3.2 × 10¹⁴ years

• Same per-axis resolution throughout, at a measured 2.3 microseconds per loss evaluation on this dataset
  • the exact figure belongs to this machine and doesn’t matter: nothing survives 4.3 × 10²⁷ evaluations at any per-evaluation cost you could plausibly reach
• The obstacle here is the enumeration strategy, not the existence of a solution: the polynomial optimum is available in closed form without a grid.
• Resolution trade-off: coarser grids cost less but resolve less

Call back to the estimates from GRID SEARCH, COUNTED rather than to a lab result – the grid perturbation is Friday’s.

TIMING: ~4 min.

Why enumeration fails

• Objective: defined over the full twelve-dimensional parameter space
• Bottleneck: exhaustive search over a product grid
• Information used: loss values, not local direction
• A method using local directional information could avoid most grid points

Local information

Using local directional information does not by itself guarantee convergence or a global minimum.

DO NOT SAY “brute force is hopeless, therefore gradient descent”. The second doesn’t follow, and this deck has not earned it.

LISTEN FOR: descent, unprompted. Take the proposal, write it up, don’t evaluate it.

TIMING: ~4 min.

Closed form vs local search

	Closed form	Local search
requires	linear in parameters; squared loss	local directional information
additionally	full column rank for uniqueness; stable solver	method-specific conditions
cost	linear least-squares solve	iterative steps

• Requirements
  • linearity in the parameters is a property of the model family
  • full column rank is a property of the design matrix — the data and the features you chose together
  • a mathematical rank failure requires changing the columns or accepting non-uniqueness
  • poor numerical conditioning can often be mitigated by a better-scaled basis or a more stable solver; rescaling helped in this example
• Break linearity in the parameters and this linear least-squares route no longer applies directly
• Models nonlinear in their parameters generally require other optimisation methods

The closing bullet is what Friday exists to answer.

Do not name gradient descent’s failure modes. Nothing to hang them on yet.

TIMING: ~5 min.

What breaks parameter linearity?

• The polynomial family got substantially more expressive
• It never stopped being linear in its parameters

What would have to change about the model for that to stop being true?

Collect nothing. Friday asks them to read it back.

Resist answering. “Make it a network”, without being able to say what that changes, is Friday’s opener.

Do NOT ask whether the polynomial passes through twelve points – it can, and asking spends Friday. It can’t interpolate these fifty: 14 speeds carry more than one stopping distance.

TIMING: ~4 min.

What the loss is an estimate of

Empirical risk

Definition 8 The empirical risk is the average loss over the observed examples.

\[ \erisk[\params] = \frac{1}{I}\sum_{i=1}^{I} \exloss_i[\params] \tag{21}\]

• For squared loss, empirical risk is the mean squared error.
• Empirical means over the data we have
• Averaging gives a per-example quantity, on the same scale as expected loss

Should feel anticlimactic. The work was done at SUM OR MEAN; the name is the only new thing.

TIMING: ~4 min.

Population risk

Definition 9 The population risk is the expected loss over a specified distribution of input-output pairs — ideally the distribution whose performance we care about.

\[ \prisk[\params] = \expectsub{(x, y) \sim p}{\exloss[\params; x, y]} \tag{22}\]

• Meaning: expected per-example loss over pairs drawn from \(p\)
• \(\exloss_i[\params]\) was \(\exloss[\params; x_i, y_i]\) all along — the per-example loss at one observed pair. Here the pair is drawn from \(p\) instead of being fixed at an observed example.
• \(\erisk\) averages over the examples we have; \(\prisk\) averages over the specified distribution \(p\)
• To use the training sample to estimate this quantity, we need a sampling assumption connecting those examples to \(p\) — commonly IID draws in the basic treatment
• Shape: both risks are single scalars, and both are functions of the parameters
• \(\erisk\) is directly computable from the sample. \(\prisk\) usually is not, because the full distribution \(p\) is not available.

PROMPT: if \(p\) is meant to describe cars we deploy on today, can these fifty 1920s observations be treated as IID draws from it? No. The historical gap gets us to the assumption without new machinery.

Week 4’s boundary arriving early. Take it and move.

TIMING: ~5 min.

Estimate and objective

• For a fixed parameter setting chosen independently of the sample, \(\erisk[\params]\) is an estimator of \(\prisk[\params]\) under the sampling assumptions just stated
• During training we instead choose \(\params\) because it scores well on that same sample

That selection matters: training risk at the selected setting is generally an optimistic description of performance on new draws. Minimising empirical risk is therefore not the same thing as minimising population risk.

• Training curves show empirical risk on the data being used by the procedure
• Claims about performance must say which data and which distribution they refer to

LISTEN FOR: “so just get more data”. Reasonable, and incomplete – the gap also depends on the family. Do not resolve it.

TIMING: ~4 min.

Underfitting and overfitting

Definition 10 Underfitting means the fitted predictor performs poorly even on the training problem because the model family, optimisation or training procedure has not captured enough of the available structure.

Definition 11 Overfitting means performance on the training data is substantially better than performance on new data from the target distribution because the fitting procedure has adapted to sample-specific variation.

• Neither can be diagnosed from training loss alone
• Assessing generalisation requires data not used to fit the model

One line each and move. Week 4 has a whole session.

DO NOT SAY the degree-eleven polynomial is overfitting. Nothing today tested it on held-out data.

TIMING: ~4 min.

Not established

model	parameters	training MSE (ft²)
line	2	227.1
line plus squared term	3	216.5
degree eleven	12	182.9

• Among these fitted models, the one with the most parameters has the lowest empirical risk
• That follows structurally because each larger family contains the previous one, so its optimum training loss cannot be higher
• Not established: that it predicts better, that it’s the better model, or that more parameters help

Which of these would you ship, and what evidence would you need?

PROMPT: containment means the polynomial could not have scored higher. So what did the lower number tell us?

LISTEN FOR: someone reaching for a test set. Name it, date it, don’t run it.

TIMING: ~3 min.

Consolidation

Retrieval

Closed notes, in pairs, then compared.

1. Reconstruct the difference between input space and parameter space, including the dimension of each for the two-parameter line — then name the space the scatter plot is a picture of, and its dimension.
2. State what min and argmin each return, with types.
3. One sentence: what does the loss take as its argument, and what is held fixed?

Review the item you could not reconstruct.

Delayed retrieval, not a summary. Do not summarise the deck afterwards.

If item 1 fails across the room, that is next Monday’s opener.

TIMING: ~5 min.

Reading

• Prince, chapters 1 and 2: the supervised-learning frame, model families, fitting and loss (Prince 2023)
• Appendix A: notation — square brackets, bold symbols and the conventions used throughout the major
• Appendix B.3: vectors, matrices and tensors — transpose, norms, matrix products and dot products used in the linear-algebra primer
  • use it as the slower reference if any part of the primer went past too quickly

Not required: appendix B.5, matrix calculus, and problems 2.1 and 2.2.

Nobody leaves with an individual reading list. Appendix B.3 is the fallback for everyone.

Appendix A is notation, appendix B is the mathematics, and B.3 is vectors and matrices.

TIMING: ~4 min.

Two open questions

1. The polynomial became more expressive without ever becoming nonlinear in its parameters. What would change that?
2. Exhaustive search stopped scaling almost immediately, and the closed form won’t always be there. What replaces them?

Two questions, no third, and no tour of the weeks after them.

TIMING: ~3 min.

References

Ezekiel, Mordecai. 1930. Methods of Correlation Analysis. Wiley.

Prince, Simon J. D. 2023. Understanding Deep Learning. MIT Press. https://udlbook.github.io/udlbook/.

Questions?

Eoin O’Brien · eoin@eoin.ai

Last slide, so leave it up while the room empties – the address stays on the projector for anyone who wanted to ask and did not want to ask in front of everyone.