Introduction to Machine Learning

Supervised Learning &
Linear Regression

From a table of numbers to a predictive model

Five questions, one table

One house follows us through the lecture: 175 m², four bedrooms, built in 1910, sold for $122,000 in Old Town, Ames. Every model we build will try to explain its price.

Data

Given a table of numbers, what can you do?

size (m²)	bedrooms	age (yr)	price ($1000s)
210	3	21	400
160	3	8	330
240	3	14	369
141	2	32	232
300	4	3	540

Visualize it: look at it!
Summarize it: mean, spread, outliers
Clean it: missing values, errors
Predict with it: today's topic
Next: the same four columns for 2,930 real houses.

The same table, for real2,930 houses sold in Ames, Iowa, 2006 to 2010

Recorded by the city assessor and published for teaching by Dean De Cock (2011). Download: ames_houses.csv.

Hover a red ring. What would you do with those five? Hold your answer until Part 5.

Inputs and Outputs

Inputs $x$: what we are given
size, bedrooms, age ("features")

Output $y$: what we want to predict
price ("target", "label")

$ \left( x^{(i)},\, y^{(i)} \right), \quad i = 1, \dots, m $

Superscript $(i)$ indexes training examples; subscript $j$ indexes features: $x^{(i)}_j$. We have $m$ examples, $d$ features.

Supervised learning Learn the map from inputs to outputs using example pairs.

The Hypothesis

Given the data, find a function $h_\theta$, the hypothesis, that predicts outputs from inputs:

$x$ $ \xrightarrow{\;\;h_\theta\;\;} $ $\hat{y}$

Model class Which function? Linear, polynomial, a neural network? Choosing the family of functions is the first decision.

Parameters Within a class, $\theta$ selects one specific function. Learning is choosing $\theta$ from data.

Which Function Should We Choose?

degree 7

A higher-degree polynomial fits the training points better. Is it a better model? (coming next: generalization)

The Linear Hypothesis

$ h_\theta(x) = \theta_0 + \theta_1 x_1 + \theta_2 x_2 + \dots + \theta_d x_d $

With the convention $x_0 = 1$, this is a single inner product:

The linear model $ h_\theta(x) = \theta^\top x, \qquad \theta \in \mathbb{R}^{d+1} $

$ h_\theta(x) = \underbrace{[\theta_0, \theta_1, \dots, \theta_d]}_{\text{unknown parameters}} \cdot \underbrace{[1, x_1, \dots, x_d]}_{\text{input features}} $

Intercept $\theta_0$ ("bias") is the prediction when all inputs are zero.

Sensitivity $\theta_j$ is how much $\hat y$ changes per unit of $x_j$, the other inputs held fixed (Part 4 shows why that matters).

Part 2 of 5

The best line

What makes one line better than another?

The Cost Function

Make "best fit" precise. Each residual is $ \htmlClass{term-resid}{h_\theta(x^{(i)}) - y^{(i)}} $: draw it as the side of a square.

$ \displaystyle J(\theta) = \frac{1}{2} \sum_{i=1}^{m} \htmlClass{term-square}{\left( h_\theta(x^{(i)}) - y^{(i)} \right)^2} $

Why square? Penalizes big misses (so wild points pull hard, Part 5), treats both signs alike, and is smooth.

Why one half? Pure convenience: it cancels when we differentiate. Without it you carry a 2 instead; the minimum is the same.

the squares whose total area $J$ measures

Learning becomes an optimization problem: $ \hat\theta = \arg\min_\theta J(\theta) $. Next: fit it yourself and watch $J$ respond.

Fit the Line Yourself

$\theta_0$ $\theta_1$ mean squared error $= 2J/m$:

Twenty houses drawn at random from the 2,930. The readout is your cost $J(\theta)$ as a mean, $2J/m$, so it does not grow with the number of houses: drag $\theta_0, \theta_1$ and watch it respond. The ringed house is the one from Old Town: the best line misses it by more than $100,000.

The Loss Landscape

Every point in $(\theta_0, \theta_1)$-space is a candidate line. Drag the orange point.

Left: data and the line for the current $\theta$. Right: contours of $J(\theta)$; the minimum ★ is the least-squares solution.

Part 3 of 5

Finding the bottom

Walk downhill, or solve in one step?

Gradient Descent

Can't see the whole landscape? Feel the slope under your feet and walk downhill.

Update rule while not converged:
$ \quad \theta_j := \theta_j - \alpha \, \dfrac{\partial J}{\partial \theta_j} $

Direction $\partial J / \partial \theta_j$ points uphill, so we step against it.

Learning rate $\alpha$ sets the step size: the most important knob in all of ML.

next: the gradient, worked out by hand

The Loss Surface

drag to rotate $ \theta := \theta - \alpha \nabla J $ on the floor, step by step

Computing the Gradient

For one example $(x, y)$ (drop the sum for a moment):

$ \displaystyle \frac{\partial}{\partial \theta_j} \tfrac{1}{2}\big(h_\theta(x) - y\big)^2 = \big(h_\theta(x) - y\big) \cdot \frac{\partial}{\partial \theta_j} h_\theta(x) $

$ \displaystyle \frac{\partial}{\partial \theta_j} h_\theta(x) = \frac{\partial}{\partial \theta_j} \big( \theta_0 x_0 + \dots + \theta_d x_d \big) = x_j $

LMS update $ \displaystyle \theta_j := \theta_j - \alpha \underbrace{\big(h_\theta(x) - y\big)\, x_j}_{\partial J / \partial \theta_j} $

This per-example update is the LMS rule (Widrow–Hoff, 1960).

Watch It Learn

$\alpha$ iter 0 · J =

Try a large $\alpha$ and watch it overshoot and diverge. Turn on stochastic mode to see the noisy path of SGD, stochastic gradient descent: one random house per step.

Why we measure from the average house

size as measured

size minus the average size

$\alpha$

$\theta_0$ is the price of a house of size zero, far from any house we have, so every change of slope forces a change of intercept: a long, narrow valley. Subtract the average size and $\theta_0$ becomes the price of an average house. The two knobs stop fighting, the valley turns round, and the same step size gets there four times faster. It is the same illness as an inverse that quietly lies: the condition number of $X^\top X$, how stretched the valley is, goes from 44.6 to 3.6.

Gradient Descent in Ten Lines

import numpy as np

X = np.c_[np.ones(20), x]   # 20 x 2
theta = np.zeros(2)

def grad(theta):
    # grad J = X.T (X theta - y)
    return X.T @ (X @ theta - y)

alpha = 0.01
for t in range(200):
    theta -= alpha * grad(theta)

Outputs on the right are computed live from this data as the highlight advances. SGD swaps grad for one random example: cheaper, noisier, and it ends up near the same place.

Run the ten lines yourselfThe 20 houses, gradient descent, and the exact answer to check it


X = np.c_[np.ones(20), x]   # 20 x 2: a column of ones, then the sizes
theta = np.zeros(2)

def grad(theta):
    return X.T @ (X @ theta - y)

alpha = 0.02
for t in range(500):
    theta -= alpha * grad(theta)

print('gradient descent:', theta.round(3))
print('normal equations:', np.linalg.lstsq(X, y, rcond=None)[0].round(3))

Both lines should say about 0.116 and 1.26: $1,260 per m². Now set alpha = 0.03 and run it again. The raw sizes are the long valley from the centering slide, and 0.03 is past the edge.

Can We Skip the Iteration?

Stack the data into a matrix, one example per row:

$ X = \begin{bmatrix} \rule[.5ex]{1.3em}{0.4pt}\, (x^{(1)})^\top \,\rule[.5ex]{1.3em}{0.4pt} \\ \vdots \\ \rule[.5ex]{1.3em}{0.4pt}\, (x^{(m)})^\top \,\rule[.5ex]{1.1em}{0.3pt} \end{bmatrix}, \qquad \mathbf{y} = \begin{bmatrix} y^{(1)} \\ \vdots \\ y^{(n)} \end{bmatrix} $

Then the whole cost is one squared distance:

$ J(\theta) = \tfrac{1}{2} \lVert X\theta - \mathbf{y} \rVert^2 $

Exercise Set $ \nabla_\theta J(\theta) = 0 $ and solve for $\theta$. One line of matrix calculus. Try it before the next slide.

The Normal Equations

$ \displaystyle \nabla_\theta J = \nabla_\theta \tfrac{1}{2} (X\theta - \mathbf{y})^\top (X\theta - \mathbf{y}) = X^\top (X\theta - \mathbf{y}) $

Set it to zero: $ \; X^\top X \theta = X^\top \mathbf{y} $ (the normal equations)

Closed form $ \hat\theta = (X^\top X)^{-1} X^\top \mathbf{y} $

Full derivation with the matrix-calculus rules: CS229 notes, Part I.

Least squares is a shadowThree real houses, one point in three dimensions

$\theta_0$ $\theta_1$

Three houses, one axis each: a small one, and two of nearly the same size that sold for $122,000 and $419,000. Their prices are one arrow $\mathbf y$. Drag to turn it.

The columns of $X$ are two more arrows: ones, and sizes.

Every prediction $X\theta = \theta_0\,\mathbf 1 + \theta_1\,\mathbf{x}$ mixes the two, so it lives on the sheet they span.

Move $\theta$. The cost is the squared length of the red gap from the sheet to $\mathbf y$.

The shortest gap meets the sheet at a right angle, perpendicular to both columns: $X^\top(\mathbf y - X\theta) = 0$, the normal equations as a picture.

Gradient Descent vs. Normal Equations

Normal equations

Exact: no $\alpha$, no iterations
Needs $(X^\top X)^{-1}$: $O(d^3)$
Fine for $d$ up to a few thousand

Gradient descent

Iterative, needs $\alpha$
Each step $O(md)$, scales to huge $d$
The only option for neural networks

Takeaway Linear regression is the rare case: one bowl, one bottom, a closed form. Almost everything later in this course has no closed form, and you walk downhill. Neural networks?

Part 4 of 5

Many features

What is a bedroom worth?

Mean sale price by number of bedrooms. Size bands, ; groups under 10 houses, and the five unusual sales, are left out.

Alone, a bedroom adds money: bigger houses have more of them. With size in the model, one more bedroom in the same space means smaller rooms, and the price goes down. The dashed yellow line rises; every blue line falls.

$\theta_j$ answers one question at a time

Sensitivity, precisely $\theta_j$ is how much $\hat y$ changes per unit of $x_j$ with every other feature held fixed.

So a coefficient depends on the company it keeps The same bedroom column gets $+\$13{,}300$ alone and $-\$32{,}500$ next to size. Neither is wrong; they answer different questions.

You have seen this before The penguins did this too: bill length against depth reversed sign once species entered. A missing variable can flip a sign, and only looking at the data warns you.

The Old Town house: size alone says $226,000, size and bedrooms $201,000, adding age $144,000. It sold for $122,000. What is still missing? The file has more columns.

All 2,930 houses, in numpyPress Run: this is real Python, in your browser


import numpy as np, pandas as pd

h = pd.read_csv('ames_houses.csv')
h = h[h.living_area_sqft <= 4000]        # the five red rings: see Part 5
m2 = h.living_area_sqft * 0.092903      # square feet to square metres
age = h.year_sold - h.year_built

X = np.column_stack([np.ones(len(h)), m2, h.bedrooms, age])
y = h.sale_price.values
theta, *_ = np.linalg.lstsq(X, y, rcond=None)   # solves X^T X theta = X^T y
print(theta.round(0))       # price at zero, per m2, per bedroom, per year
print('typical miss:', np.sqrt(np.mean((X @ theta - y) ** 2)).round(0))

You should get about $1,327 per m², −$23,522 per bedroom and −$956 per year of age, with a typical miss of $41,328: the numbers on the bedroom slide. Try adding h.overall_quality as a column. lstsq solves the normal equations without forming the inverse, which is safer than forming it.

Part 5 of 5

Why squares

Where does squared error come from, and when does it mislead?

Why Least Squares? A Probabilistic View

Assume outputs are the model plus Gaussian noise:

Noise model $ y^{(i)} = \theta^\top x^{(i)} + \varepsilon^{(i)}, \qquad \varepsilon^{(i)} \sim \mathcal{N}(0, \sigma^2) \ \text{ i.i.d.} $

the model is the line;
every step wobbles around it

noise $\sigma$

each $y^{(i)}$ is a draw from a Gaussian centered on the line

How probable is the observed dataset, as a function of $\theta$? That is the likelihood.

The Likelihood of the Data

The noise model says each output, given its input, is Gaussian around the line:

$ \displaystyle p\big(y^{(i)} \mid x^{(i)}; \theta\big) = \frac{1}{\sqrt{2\pi}\,\sigma} \exp\!\left( - \frac{ ( y^{(i)} - \theta^\top x^{(i)} )^2 }{ 2\sigma^2 } \right) $

The noise draws are independent (the "i.i.d." of the last slide: independent and identically distributed), so the probability of the whole dataset is the product:

$ \displaystyle L(\theta) = \prod_{i=1}^{m} p\big(y^{(i)} \mid x^{(i)}; \theta\big) = \prod_{i=1}^{m} \frac{1}{\sqrt{2\pi}\,\sigma} \exp\!\left( - \frac{ ( y^{(i)} - \theta^\top x^{(i)} )^2 }{ 2\sigma^2 } \right) $

Maximum likelihood Pick the $\theta$ that makes the observed data most probable.

Least Squares Is Maximum Likelihood

Products are awkward. Take the log, and the product becomes a sum:

$ \displaystyle \log L(\theta) = \sum_{i=1}^{m} \log \left[ \frac{1}{\sqrt{2\pi}\,\sigma} \exp\!\left( - \frac{ ( y^{(i)} - \theta^\top x^{(i)} )^2 }{ 2\sigma^2 } \right) \right] $

$ \displaystyle \phantom{\log L(\theta)} = m \log\frac{1}{\sqrt{2\pi}\sigma} \; - \; \frac{1}{\sigma^2} \cdot \underbrace{\tfrac{1}{2} \sum_{i=1}^m ( y^{(i)} - \theta^\top x^{(i)} )^2}_{J(\theta)} $

The punchline Maximizing $\log L$ is minimizing $J(\theta)$: the noise model chooses the loss.

Different noise, different loss: Laplacian noise, with a sharper peak and heavier tails than the Gaussian, gives absolute error (L1), robust to outliers. The next two slides test both claims on the houses.

Does the noise look Gaussian?Check the assumption on the real houses

So least squares is maximum likelihood for a world that is only roughly this one. It still gives a good line; what the mismatch costs is honesty about uncertainty, and robustness, which is the next slide.

Five strange sales

include the five solid: squared error dashed: absolute error

Three are partial sales, houses not finished when assessed, that likely do not represent market value; two are very large houses priced about right. Squaring a big miss makes it loud. Absolute error, which is Laplacian noise in disguise, barely listens.

"In general, I instruct my students to never throw away data points simply because they do not match a priori expectations (or other data points)." Dean De Cock, who also recommends removing these five when the goal is a model of a typical sale.

Why Not Interpolate All the Points?

degree 1 training error:

At degree 19 the curve passes through every point: zero training error. Do you trust it between the points? These are the same 20 real houses. Next lecture: generalization.

The Old Town house, one last time

Every column we added made the model better on average. Overall quality cuts the typical miss again, and moves the Somerset house toward its real price.

It moves this house the wrong way. The assessor graded it out of 10, and it still sold for $122,000. Whatever made it cheap is not in the file.

A model is a statement about the average house. Some houses have a story the columns do not hold, and the honest thing is to say so.

Summary

The model

$ h_\theta(x) = \theta^\top x $

linear in the parameters

The objective

$ J(\theta) = \tfrac12 \sum_i (h_\theta(x^{(i)}) - y^{(i)})^2 $

squared error = Gaussian maximum likelihood

Many features: $\theta_j$ is the change per unit of $x_j$ with the others held fixed, which is why a bedroom is worth $+\$13{,}300$ on its own and $-\$23{,}500$ next to size and age.

Solver 1: normal equations

$ \hat\theta = (X^\top X)^{-1} X^\top \mathbf{y} $

exact, when $d$ is small

Solver 2: gradient descent

$ \theta := \theta - \alpha \nabla J $

iterative, scales; $\alpha$ too big diverges, too small crawls

Next lecture: features, overfitting, and generalization: when a better fit is a worse model. It opens with a dataset from 1885 and where the word "regression" comes from.

Supervised Learning &Linear Regression