Chapter 01

Introduction

What it means for a machine to learn from data — the mindset shift, the vocabulary you'll carry through every later chapter, and the three big paradigms that organise the entire course.

Reading: ~25 min Interactive: 3 widgets Source: Bishop Ch. 1–2 · Mitchell Ch. 1

01 · Motivation

Why does this matter?

Open your email. The “spam” folder is doing something curious. Nobody wrote a giant list of rules like “if the message contains the word viagra, send it to spam.” Instead, a program looked at millions of emails — some labelled “spam”, some labelled “not spam” — and figured out, by itself, what spam tends to look like.

That program was not programmed in the usual sense. It was trained. And that single shift — from telling the computer how to do the job, to showing it examples and letting it work the job out — is what this entire course is about.

Three concrete situations make the shift unavoidable:

No one can write the rules

Recognising a cat in a photo, a tumour on a scan, or a handwritten digit. You can see the answer instantly, but you cannot describe the rule precisely enough to hand it to a programmer.

The rules keep changing

Spam, fraud, stock prices, fashion trends. Whatever rules you write today are stale tomorrow. You need a system that adapts as fresh data arrives.

Each user needs a different rule

Your inbox is not my inbox. Your taste in films is not mine. Rules carved by hand cannot be re-carved for every individual user — but learning from each user’s own data can.

why

The deeper reason

Writing software is the bottleneck. Many tasks we want computers to perform are easy to demonstrate with examples but practically impossible to describe with code. Machine learning is, at heart, a way of letting data write the program for us.

02 · Intuition

The idea in plain language

In ordinary programming you give the computer two things — data and a program — and you receive an output. Machine learning quietly flips this picture. You give the computer the data and the desired output, and it returns the program.

Traditional programming

Machine learning

The “program” we get back is what the textbooks call a model — a function that takes an input (say, an email) and returns an output (say, the probability that this email is spam).

Mitchell’s definition, unpacked

Tom Mitchell gave the cleanest one-sentence definition of machine learning in 1997:

A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.

That is three letters doing a lot of work. Translated into everyday English:

T: the task you actually care about — “filter spam”, “classify tumours”, “drive a car”.
P: the performance measure — a number that says how well the task is being done (accuracy, error, reward, …).
E: the experience the program is exposed to — usually a collection of examples, sometimes interaction with an environment.

A spam filter learns when its accuracy on new emails goes up as it sees more labelled emails. A chess engine learns when its win rate goes up as it plays more games. Same definition, very different tasks. This is the mental template to test every new technique against: what is T, what is P, what is E?

key

Machine learning is not magic

The single most useful sentence to remember from this whole chapter:

ML can extract information from data — it cannot create information that isn’t there. If the data is biased, the model is biased. If the data has no signal, the model has nothing to learn. Every later chapter will keep coming back to this.

Three answers to “what should the machine learn?”

The whole field organises around a single question: what kind of thing is sitting in the training data? Three answers give us the three paradigms of machine learning.

Supervised

Learn the model

You have inputs paired with correct outputs. You want a function that turns inputs into outputs and gets the right answer on data it has never seen.

D = { ⟨x, t⟩ }

Unsupervised

Learn the representation

You have inputs only — no answers. You want to discover the hidden structure: clusters, low-dimensional patterns, anomalies.

D = { x }

Reinforcement

Learn to control

You can act in an environment and receive a reward signal. You want a policy: which action to take in each situation to collect the most reward over time.

D = { ⟨x, u, x′, r⟩ }

Most of this course (chapters 2–7) is about supervised learning, the largest and most mature paradigm. Chapters 8–10 build up the reinforcement-learning picture. Unsupervised learning is touched on, but is the main subject of other courses.

03 · Formalism

Definitions and notation

Now that the intuition is in place, here is the vocabulary that the rest of the course assumes. Every symbol here will reappear in chapter after chapter — burn them in now and you save yourself a lot of pain later.

The core vocabulary

x: an input example, also called a feature, predictor, or attribute. Usually a vector $\mathbf{x} \in \mathbb{R}^d$ — a list of d numbers describing one observation.
t: the output attached to x, also called a target, response, or label.
f: the true, unknown function we wish we knew: $t = f(\mathbf{x})$ . We never see f directly; we only see noisy samples of its behaviour.
D: the training set: a finite collection of examples drawn from the world, $\mathcal{D} = \{ \langle \mathbf{x}_i, t_i \rangle \}_{i=1}^{N}$ .
H: the hypothesis space — the set of all functions we are willing to consider as candidate models.
h: a specific hypothesis chosen out of $\mathcal{H}$ . Our final model is one particular h.
L: the loss function — a number that says how bad a prediction is. The smaller L, the better.

tip

A useful image

Imagine $\mathcal{H}$ as a library of possible programs and h as the one book you decide to pick off the shelf. The loss L is your method for grading each candidate book against the training data. Learning, in this picture, is library search guided by grading.

The three paradigms, formally

Each paradigm is defined by the shape of its training set:

Supervised

\mathcal{D} = \{\langle \mathbf{x}_i, t_i \rangle\}_{i=1}^{N} \quad \Longrightarrow \quad \text{find } h \approx f \text{ with } t = f(\mathbf{x})

Inputs are paired with desired outputs. The learner tries to approximate the unknown mapping f.

Unsupervised

\mathcal{D} = \{\mathbf{x}_i\}_{i=1}^{N} \quad \Longrightarrow \quad \text{find structure in } p(\mathbf{x})

Inputs only. The learner discovers structure — clusters, lower-dimensional manifolds, density estimates.

Reinforcement

\mathcal{D} = \{\langle \mathbf{x}, \mathbf{u}, \mathbf{x}', r \rangle\} \quad \Longrightarrow \quad \pi^*(\mathbf{x}) = \arg\max_{\mathbf{u}} Q^*(\mathbf{x}, \mathbf{u})

Each experience is a transition: I was in state x, took action u, ended in state x′, and got reward r. The learner builds a policy π.

Supervised learning has flavours

Supervised problems are split by what the target t looks like:

Target	Problem name	Examples
discrete (finite set of classes)	classification	spam vs not-spam · digit recognition · cat vs dog
continuous (a real number)	regression	house price · temperature tomorrow · exam score
a probability over outcomes	probability estimation	P(click) on an ad · P(rain) tomorrow

The thing we actually care about: generalization

A model that scores 100% on the training set has done nothing useful if it makes wild predictions on data it hasn’t seen. The whole point of training is generalization: low error on future inputs, not on the inputs we already labelled.

We split data into two pools:

Training set — used to choose h.
Test set — held out, used only to estimate how well h will do on data it has never met.

Training error is a useless predictor of real performance. Test error — measured on data not used during training — is the number we care about. This single distinction is the source of half the topics in this course (model selection, cross-validation, PAC bounds, regularisation, the bias–variance trade-off…). Hold it close.

04 · Worked example

Predicting exam scores from study hours

A miniature supervised problem, carried end-to-end so you can see every symbol land in a concrete place. Step through it:

Worked example Predicting exam scores

1 · The data

Seven students each report how many hours they studied and what score they got. We use the first five rows to train a model, and keep the last two hidden — they are our test set.

Student	Hours studied · x	Score · t
A	1	40
B	2	52
C	3	58
D	4	72
E	5	80
F	6	?
G	2.5	?

Here x is study hours (one feature, so $d=1$ ), t is the exam score, and the training set is $\mathcal{D} = \{(1,40),(2,52),(3,58),(4,72),(5,80)\}$ .

2 · Pick a hypothesis space

Eyeballing the numbers, the relationship looks roughly linear. So we choose $\mathcal{H}$ to be the set of all straight lines:

\mathcal{H} = \{\, h(x) = w_0 + w_1 x \;:\; w_0, w_1 \in \mathbb{R}\,\}

Out of the infinite zoo of all possible functions, we committed to a tiny shelf of candidates — only those with a single slope and a single intercept. This is a deliberate restriction.

3 · Define a loss

How bad is a candidate line? We use the squared-error loss summed over the training set:

Loss

L(h) = \sum_{i=1}^{N}\bigl( h(x_i) - t_i \bigr)^2

A perfect prediction contributes zero. A prediction off by 5 contributes 25. Big mistakes count more than small ones — that is the squared-error choice in action.

4 · Optimise

We hunt through $\mathcal{H}$ for the line that minimises $L$ . For a straight line this has a closed-form solution (chapter 2 derives it); for now, the values are:

h(x) = 32.0 + 9.8\,x

Best-fit intercept $w_0 = 32.0$ , slope $w_1 = 9.8$ . Each extra hour of study is worth about 9.8 score points, on the basis of this dataset.

Peek ahead Where does 32.0 + 9.8x come from?

The closed-form least-squares solution sets the gradient of $L$ to zero. For a single feature it reduces to $w_1 = \frac{\sum (x_i - \bar{x})(t_i - \bar{t})}{\sum (x_i - \bar{x})^2}$ and $w_0 = \bar{t} - w_1 \bar{x}$ , where $\bar{x}, \bar{t}$ are the means. Plugging in the five training rows gives the slope and intercept above. Chapter 2 generalises this to many features.

5 · Use the model — and check generalization

Plug the test inputs into h:

Student F (6 hours): $h(6) = 32 + 9.8 \times 6 = 90.8$ .
Student G (2.5 hours): $h(2.5) = 32 + 9.8 \times 2.5 = 56.5$ .

The training residuals — how wrong h was on each training point — are {−1.8, 0.4, −3.4, 0.8, −1.0}, all within a handful of points. If the test scores turn out near 90 and 57, our model generalised. If they are wildly off, the line we picked was the wrong shape and our hypothesis space was too small.

map

Map the example back onto the vocabulary

T (task): predict exam score from study hours.
P (performance): squared error on unseen students.
E (experience): the five labelled training rows.
$\mathcal{H}$ : all straight lines.
h: the specific line $32 + 9.8\,x$ .
L: sum of squared residuals.

Almost every supervised algorithm in the course is some variation on these same four steps — only with a richer $\mathcal{H}$ , a more clever loss, or a smarter optimiser.

05 · Visual explanation

The picture of supervised learning

One diagram, used to drill in the relationship between the true function f, the hypothesis space $\mathcal{H}$ , and the model h we end up with. Spend a minute looking at it before reading the caption.

Read it like this. The big dashed oval $\mathcal{F}$ is the space of every function that could possibly map inputs to outputs — a vast, mostly unhelpful ocean. Out there, somewhere, sits the truth we are chasing: the unknown function $f$ . The smaller solid oval $\mathcal{H}$ is the much smaller shelf of functions we are willing to consider. Our model $h$ is the single point inside $\mathcal{H}$ that our optimiser thinks is best.

The dashed line between $f$ and $h$ is the approximation error — the gap that exists because $f$ was never in our shelf in the first place. Two things can shrink this gap: a bigger $\mathcal{H}$ , or a luckier choice of which kind of $\mathcal{H}$ to use.

trap

Why we don’t just make $\mathcal{H}$ huge It is tempting to say: let $\mathcal{H}$ be everything! Then $f$ is definitely in it. The trouble is that we only have a finite training set. A bigger shelf gives us more candidates that fit the training points perfectly while still being totally wrong off-training. We see that pathology explicitly in the next section.

A map of the three paradigms

One more picture, this time of the whole field. Each branch tells you what you get in the training set and what you are trying to learn.

06 · Hands-on

Try it yourself

Three interactive widgets, each designed to drill in one idea. Click, drag, and pay attention to the changes — these are the moments where the abstract ideas above turn into instincts.

Hands-on 1

Sort the scenarios into paradigms

For each real-world problem, decide whether it is best framed as SL supervised, UL unsupervised, or RL reinforcement learning. The button you click turns green if correct, red if not — and a short explanation appears.

Mark each email in your inbox as spam or not spam, using millions of labelled examples.

Group customers of an online store into segments without any predefined categories.

Train a robotic arm to stack blocks by trial and error, getting a reward each time a tower stays standing.

Predict tomorrow's temperature from today's atmospheric measurements.

Compress a dataset of 10000-dimensional gene expressions into 2 informative dimensions.

Teach a self-driving car which lane to choose, learning from how often it reaches its destination on time.

Detect anomalous credit-card transactions when you have no examples of past fraud labelled.

Classify handwritten digits 0–9 using a dataset of digitised, hand-labelled images.

0 / 0

Try thisLook carefully at the recommender-style rows. Why might one be argued as either supervised or reinforcement? The training-data shape is the decisive clue.

TakeawayThe paradigm is decided by what's in the training set — labels, just inputs, or actions paired with rewards. The same task can sometimes fit two paradigms depending on what you collect.

Hands-on 2

Bigger hypothesis space — is it actually better?

We fit a polynomial of growing degree to 10 noisy training points (orange) drawn from an unknown smooth curve (blue). Move the slider to enlarge the hypothesis space H. Watch the training error, the gap to the true curve, and the held-out test set.

Degree of polynomial1

underfitting · H too small

Train MSE

0.355

Test MSE

0.216

| H | (parameters)

Try thisCrank the slider to 15. Train MSE collapses to near zero — the fit passes through every training point. Now look at the test MSE. Then slide back to 3 and compare again.

TakeawayTraining error keeps falling as H grows. Test error first falls, then rises — the model starts memorising the noise. This U-shape is the central tension of supervised learning.

Hands-on 3

Hand-written rules vs learned rules

We are building a tiny spam filter. Switch between the hand-coded rules view and the machine-learned view, and watch how the same five emails get classified. Pay attention to where each approach breaks.

Email subject	Truth	Filter says
Re: lecture notes for tomorrow	ham	ham
WIN A FREE iPHONE NOW	spam	spam
Free coffee at the lab today ☕	ham	spam
Important: your account access expires	spam	ham
Project group meeting Wed 3pm	ham	ham

Hand-coded rules: 3 / 5 correct. The rules trigger on the words "free", "win", "urgent", "click", or on lots of CAPITALS. That gets the obvious spam — but it also drags the friendly "Free coffee" email into spam, and completely misses the polished phishing attempt that contains none of the trigger words.

Try thisRead the subjects carefully. The hand-coded rules look reasonable — they trigger on "free", "win" and CAPITALS. Where do they fail? Where does the learned filter recover?

TakeawayYou can write rules that catch the obvious cases — and miss every nuanced one. A learned model picks up combinations of weak signals that no one would think to hand-code.

07 · Exam intel

What the exam actually tests

The Introduction chapter is short on derivations and heavy on vocabulary. Exam questions on this material tend to fall into four predictable shapes.

Identify T, P, E in a scenario

A short prose description is given (e.g., “a system learns to recommend films using user ratings”). You name the task, the performance measure, and the experience. Always answer with three concrete nouns, not paraphrases of the question.

Pick the paradigm and justify

A problem is described; you classify it as SL / UL / RL and justify with the shape of the training data. The cheap answer (“it has labels”) is worth few marks; the full answer references $\mathcal{D}$ explicitly.

Name the three components of any supervised algorithm

Every supervised method is one choice in each of three slots:

Representation — what $\mathcal{H}$ looks like (linear models, decision trees, neural networks, …).
Evaluation — the loss / score used to grade candidates (squared error, accuracy, likelihood, …).
Optimization — how we search $\mathcal{H}$ (closed form, gradient descent, combinatorial search, …).

This R / E / O triple is the cleanest way to summarise any algorithm. Use it on day one and on the exam.

Place a technique in one of the four dichotomies

Dichotomy	Side A	Side B
Parametric vs Nonparametric	Fixed, finite # of parameters	#params grows with data
Frequentist vs Bayesian	Probabilities of data	Probabilities of parameters
Generative vs Discriminative	Learns $p(\mathbf{x},t)$	Learns $p(t\mid\mathbf{x})$
Empirical vs Structural Risk	Minimise training error	Penalise complexity too

A common shape: “Linear regression with squared loss — where does it sit?” Answer: parametric, frequentist by default, discriminative, empirical risk minimisation (becomes structural if you add regularisation).

08 · Common mistakes

Where students get this wrong

"AI and ML are the same thing"

ML is a sub-field of AI: the part where knowledge comes from experience and induction, rather than from hand-written rules or symbolic logic. Every ML system is an AI system; not every AI system is ML.

"More data → more knowledge → magic"

Machine learning extracts patterns that already live in the data. Garbage in, garbage out: if the signal you need is not present in the inputs, no amount of training will conjure it. Always ask: is there a reason the inputs should determine the output?

"100% on training is a great model"

Memorising the training set is trivial — every example becomes a row in a lookup table. The point is performance on unseen data. Until you know the test error, training accuracy tells you essentially nothing.

"A bigger hypothesis space is always better"

A larger $\mathcal{H}$ can drive training error to zero by fitting noise — and ruin generalisation. The hands-on widget above shows this in 30 seconds of slider play. Choosing $\mathcal{H}$ is the central design decision of supervised learning.

Mixing up classification and regression

The difference is the target, not the input. Discrete target (cat/dog, spam/ham, digit 0–9) → classification. Continuous target (price, temperature, time) → regression. Same input data can power either, depending on what you ask the model to predict.

Calling everything with rewards reinforcement learning

RL specifically deals with sequential decision-making in an environment that responds to your actions. A one-shot prediction that happens to be graded with a score is still supervised. Look for state transitions $\mathbf{x} \to \mathbf{x}'$ — that’s the RL fingerprint.

09 · Self-check

Can you answer these?

Three short questions to find out whether the chapter stuck. Click an option for instant feedback — the right one becomes green, a wrong one turns red, and an explanation appears.

A program filters spam emails. It improves as you mark messages as spam or not-spam. According to Mitchell's definition, what is the experience E?

A robot vacuum learns by trying different cleaning paths and being rewarded for square metres covered per minute. Which paradigm is this?

You fit a degree-15 polynomial to 10 noisy data points. Training error is essentially zero. Should you celebrate?

10 · Recap

One-screen summary

Chapter 01 — load-bearing ideas

ML flips programming. Instead of writing rules, we supply data and desired outputs, and the computer returns the program (the model).
Mitchell’s definition. A program learns from experience E on tasks T with measure P if P improves with E.
ML extracts information, not creates it. No data → no signal → no learning. Garbage in, garbage out.
Three paradigms, sorted by data shape. Supervised $\langle x,t\rangle$ → model. Unsupervised $\{x\}$ → representation. Reinforcement $\langle x,u,x',r\rangle$ → policy.
Supervised vocabulary. Features x, target t, true function f, training set D, hypothesis space $\mathcal{H}$ , model h, loss L.
Classification vs regression vs probability estimation. Set by whether t is discrete, continuous, or a probability.
Generalization is the goal. Performance on unseen test data, not training data, is what matters.
Three components of any supervised algorithm. Representation, Evaluation, Optimization — memorise this triple.