7 concepts26 worked examples32 exercises4 exam-level7 figures
What are you here for?
01 Introduction and probability review for machine learning
Start with this
One question before you read anything. Getting it wrong is the point: it shows you what this section is for.
§01.0 — what a flag from a good filter is worth
An email filter catches 99 of every 100 spam emails and wrongly flags 1 of every 100 normal emails. In this inbox, 1 email in 100 is spam. An email has just been flagged.
Find(a) Roughly how likely is it that the flagged email is spam?
Given
the filter flags 99 of every 100 spam emails
it flags 1 of every 100 normal emails
1 email in 100 is spam
Hint 1/4
Nothing needs to be remembered from a course. Imagine a large batch of emails and ask which of the flagged ones are spam.
Hint 2/4
Share of spam among flagged emails $=\dfrac{\text{flagged spam}}{\text{flagged spam} + \text{flagged normal}}$.
Hint 3/4
Take 10,000 emails. Spam: 100, and 99 of them are flagged. Normal: 9,900, and 1 in 100 of them, so 99, are flagged.
Hint 4/4
So 99 of the 198 flagged emails are spam, and the answer is about 0.50.
Show solution
Counting a concrete batch is faster than recalling a formula, and it shows the one number people forget: how many normal emails are flagged.
Formula route: $\frac{0.99\times 0.01}{0.99\times 0.01 + 0.01\times 0.99} = \frac12$. The two terms are equal because the rare class and the error rate are both 1 in 100.
Here the false alarm rate equals the share of spam, so false flags match true ones one for one. Keep the base rate in view whenever you read a flag.
A face recognition model is tried on 400 photos it never saw in training and gets 36 wrong, 9 in every 100. A manager asks: could it really miss 14 in every 100 on the next million photos, and how many test photos would pin the true rate down to within 2 in every 100?
By the end of this section you can say how far a measured test error can sit from the true one and how many test samples a promise needs, using the probability underneath: and , and their , , densities and the .
In 60 seconds
A learning algorithm is judged on data it has not seen, so this section rebuilds the probability behind every such judgement and ends with Hoeffding's inequality, which turns a measured test error into a guarantee about the true one.
Bayes' rule with total probability
$$P(A\mid B) = \frac{P(B\mid A)\,P(A)}{\sum_i P(B\mid A_i)\,P(A_i)}$$
you know how likely the evidence is under each hypothesis and want the hypothesis given the evidence
a probability or a count has to become an average; a quantity is rescaled or shifted
Covariance matrix
$$\Sigma = E\big[(X-\mu)(X-\mu)^T\big],\qquad \operatorname{Var}(a^TX) = a^T\Sigma a \ge 0$$
several features at once; the variance of any weighted sum of them
Hoeffding and the sample size
$$P\big(\vert\bar Z - E[\bar Z]\vert\ge\varepsilon\big)\le 2e^{-2n\varepsilon^2},\qquad n\ge\frac{\ln(2/\delta)}{2\varepsilon^2}$$
independent terms in [0, 1], such as error indicators on a that was not used for training
Three most common mistakes
Reading $P(\text{flag}\mid\text{fraud})$ as $P(\text{fraud}\mid\text{flag})$. A detector that catches 99 of 100 frauds can still be wrong about most of the transactions it flags, when fraud is rare.
Treating zero covariance as independence. Covariance only sees a straight-line trend, so $Y = X^2$ can have zero covariance with $X$ while depending on it completely.
Using Hoeffding's inequality outside its conditions: variables not rescaled to [0, 1], the factor 2 dropped, the sample size rounded down, or the training set used as if it were a test set.
The weights differ between two course documents:
Chapter 1 slides, undergraduate line: midterm 25, final 25, four quizzes 20, two-phase project 30, out of 100 points.
STARS syllabus page printed on 21 September 2026: midterm 30, final 30, problem sets and quizzes 20, project 20. It is the later document; confirm in the first weeks which split applies.
To sit the final, both require every project report on time, no disciplinary penalty, and midterm plus quiz points worth at least a fifth of those two components.
How much time do you have?
10 minutes
Bayes' rule with its denominator, and Hoeffding's inequality turned into a test-set size: the two calculations this chapter builds towards.
The 60-second card · Conditional probability, independence and Bayes' rule · Averages settle down · Formula card
45 minutes
Every calculation in the section once: event probabilities and bounds, conditionals, distributions, means and variances, covariance matrices and sample sizes.
The 60-second card · Probability spaces · Conditional probability, independence and Bayes' rule · Random variables and their distributions · Expectation, variance and the indicator trick · Several random variables at once · Averages settle down · Scaffolding comes off · B · computation
full read
Adds the machine learning frame the probability serves: what an algorithm learns from, why training error misleads, and why a guarantee needs a separate test set.
The opening pages · Learning from data · Probability spaces · Conditional probability, independence and Bayes' rule · Random variables and their distributions · Expectation, variance and the indicator trick · Several random variables at once · Averages settle down · Method boxes · Look-alike pairs · Scaffolding comes off · Full exam-style question · Practice set · Check yourself
By the end of this section
Describe a learning problem as $Y = f(X) + \omega$: name the inputs, , and goal, and tell supervised, unsupervised and apart from the data alone.
Build the probability space of a small experiment, compute event probabilities from the axioms, and bound the probability of a union when the overlaps are unknown.
Compute conditional probabilities, test two events for independence, and reverse a conditional with Bayes' rule and the .
Move between the CDF, pmf and pdf of a random variable, and pick the Bernoulli, , , Gaussian or beta model that fits a situation.
Calculate expectations and variances from a pmf or pdf, using linearity and indicator variables to avoid long sums.
Analyse several random variables together: , conditionals, covariance, and the mean vector and covariance matrix of a random vector, including the Gaussian case.
Bound the gap between a sample average and its mean with Hoeffding's inequality, and find the test-set size a given tolerance and failure chance require.
Syllabus coverage
covered
Introduction — covered
Goals and tools of learning from data: the model Y = f(X) + ω, training data, the goal of doing well on unseen data, and the three kinds of learning
The lecturer's chapter opens with this overview before any probability, and so does this section.
covered
Probability review for machine learning and data science — covered
Probability spaces and the three axioms, the order property, the union bound, and the frequentist and Bayesian readings of a probability
The two readings of probability get one short table here; the inference methods built on them belong to the next section.
covered
random variables — covered
CDF, pmf and pdf
the Bernoulli, binomial, Poisson, Gaussian and beta families
expectation, variance and
Split over two concepts: distributions first, then expectation and variance.
covered
random vectors — covered
Joint and marginal distributions
and Bayes' rule for random variables
covariance
the mean vector and covariance matrix
the density
covered
Bayes rule — covered
Conditional probability, Bayes' rule for events with the law of total probability in the denominator, and Bayes' rule for random variables with a pmf or a density as the
The version for random variables is worked in the concept on several random variables, where conditional distributions are defined.
covered
independence — covered
Independent events
independent random variables
the factorisation E[g(X)h(Y)] = E[g(X)]E[h(Y)] for independent X and Y
identically distributed and i.i.d. samples
why zero covariance is weaker than independence
Events are handled with Bayes' rule; random variables, i.i.d. samples and covariance come back in the concept on several random variables.
covered
law of large numbers — covered
Averages of i.i.d. samples settle at the mean, and the gives the scale and bell shape of the remaining error
The central limit theorem is not named in the official line, but it sits next to the law of large numbers in the lecturer's chapter, so it is covered here.
covered
concentration inequalities — covered
Hoeffding's inequality for independent variables in [0, 1], applied to the error rate of a fixed on a test set, and solved for the test-set size
Hoeffding's inequality is the one on the lecture slides. Chebyshev's inequality appears once, in an example marked further reading, only as a yardstick for how much Hoeffding saves.
deferred
Credible and confidence intervals — deferred
Turning data into statements about an unknown parameter, the Bayesian and the frequentist way
Deferred to the next section, Bayesian and frequentist machine learning, which has its own week. Nothing here builds an interval for a parameter; Hoeffding is used only as a bound on the chance of a large miss.
Recall first
Set operations
For events $A, B\subseteq\Omega$: $A\cup B$ is 'either', $A\cap B$ is 'both', $A^c$ is 'not $A$', and $B\setminus A = B\cap A^c$. Disjoint means $A\cap B = \varnothing$. De Morgan: $(A\cup B)^c = A^c\cap B^c$.
Events are sets. The complement trick, 'at least one' equals one minus 'none', is used in several examples.
Counting
$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$ counts the ways to choose which $k$ of $n$ positions are successes, and a string of $n$ two-way choices has $2^n$ possibilities.
The binomial pmf and the of small experiments.
The exponential series
$e^{\lambda} = \sum_{k=0}^{\infty}\lambda^k/k!$, and $(1-\lambda/n)^n\to e^{-\lambda}$ as $n\to\infty$.
The first makes the Poisson pmf add up to 1; the second is where the comes from.
Integrals of powers
$\int_0^1 s^k\,ds = \frac{1}{k+1}$ for $k\ge 0$.
Every continuous expectation in this section reduces to integrals of this kind.
Two by two matrices
For $M = \begin{bmatrix}a & b\\ c & d\end{bmatrix}$: $\det M = ad - bc$ and $M^{-1} = \frac{1}{ad-bc}\begin{bmatrix}d & -b\\ -c & a\end{bmatrix}$. For a column vector $v$, $v^TMv$ is a number, and $(AB)^T = B^TA^T$.
Covariance matrices, the test and the Gaussian density in two dimensions.
Logarithms
For $\delta > 0$: $2e^{-x}\le\delta$ exactly when $x\ge\ln(2/\delta)$, where $\ln$ is the natural logarithm.
Solving Hoeffding's bound for the number of samples.
Standard normal tail values
For $Z\sim N(0,1)$: $P(\vert Z\vert\ge 1) = 0.317$, $P(\vert Z\vert\ge 1.96) = 0.050$ and $P(\vert Z\vert\ge 2) = 0.0455$.
The central limit theorem examples read their probabilities from these three values.
Try it yourself first (2 questions)
1§01.0 — does a streak make the other side due
A fair coin has landed tails five times in a row. A friend says the law of large numbers pushes the share of heads towards one half, so heads is now more likely than tails on the next toss.
Find(a) True or false: heads is now more likely than tails on the next toss.
Given
fair coin
tosses are independent
the last five tosses were tails
Hint 1/4
Separate what the law says about long-run averages from what it says about any single toss.
Symmetry check: the sequences TTTTTH and TTTTTT have the same probability, $(1/2)^6$ each, so neither ending is favoured.
Averages converge by dilution, not by compensation. No finite streak changes the next independent toss.
2§01.0 — is the mean always a possible value
A fair six-sided die is rolled once and $X$ is the number shown. Someone claims that the expected value of a random variable is always one of the values it can take, since it is the outcome we 'expect'.
Find(a) True or false: for this die, $E[X]$ is a value that no single roll can show.
Given$X$ is equally likely to be $1, 2, 3, 4, 5$ or $6$
Hint 1/4
Test the claim on the die instead of arguing in general.
Hint 2/4
$E[X] = \sum_x x\,p_X(x)$.
Hint 3/4
Here $p_X(x) = \tfrac16$ for $x = 1,\dots,6$, so $E[X] = \frac{1+2+3+4+5+6}{6}$.
Hint 4/4
So $E[X] = 3.5$, which no roll can show: the statement is true, and the claim that the mean is always a possible value fails.
Show solution
A single counterexample settles a claim about 'every random variable', so compute one case.
Symmetry check: the faces pair up as 1 and 6, 2 and 5, 3 and 4, and every pair averages 3.5, so the balance point must be 3.5.
Read an expectation as a long-run average: over many rolls the average face is 3.5, even though no single roll is.
Notation
symbol
reads as
means
watch out
$\Omega,\ \mathcal F,\ P$
omega, script F, P
the sample space, the collection of events we may ask about, and the
for a finite $\Omega$ the events are simply all subsets, written $2^{\Omega}$
$\omega$
omega (lower case)
a single outcome in $\Omega$, and also the in $Y = f(X) + \omega$
the course uses the same letter for both; the context always tells you which one is meant
$P(A\mid B)$
P of A given B
the chance of A once B is known to have happened
not the same number as $P(B\mid A)$; swapping them is the most common error in this section
$F_X(x)$
the CDF of X at x
$P(X\le x)$, climbing from 0 to 1
the $\le$ includes $x$ itself, which matters at the jumps of a discrete variable
$p_X(x),\ f_X(x)$
the pmf, the pdf
$P(X = x)$ for a discrete $X$; the slope of $F_X$ for a continuous $X$
a pdf value is a density, not a probability, and it may be larger than 1
$E[X],\ \operatorname{Var}(X)$
expectation of X, variance of X
the probability-weighted average, and the average squared distance from it
$E[X^2]$ and $(E[X])^2$ are different numbers; their gap is the variance
$I(X\in A)$
the indicator of the event
1 when $X\in A$ happens, 0 otherwise
it is itself a random variable, with mean $P(X\in A)$
$X\sim N(\mu,\sigma^2)$
X is Gaussian with mean mu and variance sigma squared
a bell-shaped density centred at the mean
the second entry is the variance: $N(0,4)$ has standard deviation 2
$\operatorname{Cov}(X,Y),\ \Sigma$
covariance of X and Y, capital sigma
how two variables move together; the matrix of all pairwise covariances of a random vector
$\Sigma$ here is a matrix, not a sum sign
$\bar X_n,\ \bar Z$
X bar n, Z bar
the average of $n$ samples, $\frac1n\sum_{i=1}^n X_i$
it is random: a new sample gives a new average
$R(f),\ \hat R_n(f)$
the risk of f, R hat n of f
the true error rate $P(f(X)\ne Y)$, and the error rate measured on $n$ test pairs
$R(f)$ is a fixed unknown number; $\hat R_n(f)$ is a random estimate of it
$\hat f$
f hat
the rule an algorithm outputs after seeing the training data
it depends on the training data, which is why it cannot be tested on them
Conventions used here
Conditioning needs a positive denominator.
We write $P(A\mid B)$ only when $P(B) > 0$, and $p_{Y\mid X}(y\mid x)$ only where $p_X(x) > 0$.
Otherwise the definition divides by zero, and the ways of patching that case are not needed in this course.
Densities are not probabilities.
For a continuous $X$, $P(X = x) = 0$ for every $x$, so $P(X\le x) = P(X<x)$, and a pdf value may exceed 1. For a discrete $X$, $\le$ and $<$ can differ by a whole jump.
Most CDF and pdf errors come from carrying a habit from one case into the other.
Gaussian parameters.
$N(\mu,\sigma^2)$ lists the mean and the variance, as the course slides do; $N(0,4)$ has standard deviation 2.
Some software takes the standard deviation instead, and a variance typed where a standard deviation belongs moves every tail probability.
Logarithms.
$\ln$ is the natural logarithm and $\exp(x) = e^{x}$; the sample-size formula $n\ge\ln(2/\delta)/(2\varepsilon^2)$ uses $\ln$.
Using $\log_{10}$ there gives a sample size too small by a factor of about 2.3.
Vectors are columns.
$X = [X_1,\dots,X_n]^T$ is a column, $x^T$ is a row and $\Sigma$ is $n\times n$, so $(x-\mu)^T\Sigma^{-1}(x-\mu)$ is a single number.
Writing the product in the other order produces an n by n matrix where the density needs a number.
Sample sizes round up.
A sample size from an inequality $n\ge c$ is rounded up to the next whole number, even when $c$ sits just above an integer.
Rounding down gives an n for which the promised bound is not quite reached.
Counts instead of percentages.
Probabilities are turned into counts in an imagined population, such as 99 of every 100 frauds or 1,998 false alarms in 100,000 transactions. These are expected counts, not observed data.
Conditional probabilities are easier to get right as counts, and counts make the denominator of Bayes' rule visible.
Three words for 'unrelated'.
Independent random variables have a joint CDF that factorises for every pair of values; , or i.i.d., adds that they share one distribution; only means zero covariance.
The words are often used loosely, and the gap between the first and the last is exactly where a counterexample in this section lives.
1.1Learning from data: the model Y = f(X) + ω and three kinds of learning
Fixes what an algorithm learns from, what it is judged on, and why that judgement is a question about probability.
Before any probability we need the object this course studies: a rule built from a finite list of examples and then used on examples nobody has seen yet.
Solvable with what we have
Count how many of 1,000 stored training emails a filter labels wrongly.
Store every training email with its label and look it up again.
Report which label is more common in the training set.
Not solvable yet
Say how the filter will do on tomorrow's emails, which it has never seen.
Say how far a measured error rate can sit from the true one.
Decide how many test emails are enough to trust a reported error.
The obvious report judges the filter on the emails it was built from. A filter that memorises all 1,000 training emails, and answers 'not spam' for anything it has not stored, makes 0 mistakes on them. So the report says: error 0 out of 1,000.
Why it fails
The memoriser has a table, not a rule. Almost every new email is missing from the table, so it always answers 'not spam' and is wrong on every spam email. Zero training mistakes measured memory, not learning.
DefinitionThe setup
Conditions
each example is a pair $(x_i, y_i)$: an input $x_i$, such as an email, an image or a list of measurements, and its label $y_i$
the pairs come from the same source that will later produce the inputs we care about
$\omega$ is noise, the part of the label that no function of the input can predict
$$\boxed{\begin{aligned} &\text{model:} && Y = \textcolor{#d1690a}{f}(X) + \textcolor{#6f42c1}{\omega}\\ &\text{data:} && \textcolor{#1f6feb}{(x_i, y_i)},\quad i = 1,\dots,n\\ &\text{learning:} && (x_1,y_1),\dots,(x_n,y_n)\ \longrightarrow\ \text{algorithm}\ \longrightarrow\ \hat f\\ &\text{goal:} && \hat f(X)\approx Y \ \text{ for new pairs } (X,Y)\end{aligned}}$$
The label is an unknown function of the input plus noise. We see $n$ labelled examples, an algorithm turns them into an estimate $\hat f$, and $\hat f$ is judged on new pairs from the same source, not on how well it repeats the $n$ examples it was given.
Each label is the true function plus a noise term. Even a learner that recovered $\textcolor{#d1690a}{f}$ exactly would miss every training point by its own $\textcolor{#6f42c1}{\omega}$, so passing through the data is not the goal.
Looks like this, but is not
A table of 5,000 customers with a column 'left the service: yes or no', and the task of spotting which customers will leave. It sounds like finding groups without a teacher, which is how is usually described.
The 'left' column is a label $Y$ for every row, and the real goal is $\hat f(X)\approx Y$ for new customers. That is supervised learning, a classification task. Unsupervised learning starts from inputs with no label column at all.
kind
what the data look like
what is learned
examples
supervised
pairs $(x_i, y_i)$
a rule $\hat f$ with $\hat f(X)\approx Y$
sales from advertising budgets; handwritten digits; ship silhouettes
unsupervised
inputs $x_i$ only
structure: groups, a shorter description, hidden sources
grouping pixels to compress an image; separating mixed recordings
reinforcement
actions, and rewards that follow them
a way of choosing actions that earns reward
recommenders that learn from clicks; robots learning to walk
Decide from the data, not the goal: a label column means supervised, no labels means unsupervised, and rewards that depend on your own actions mean reinforcement.
Error of a memorising spam filter on new email
A filter stores all 1,000 of its training emails with their labels. For a stored email it returns the stored label; for any other email it answers 'not spam'. In the stream of new emails, 30 of every 100 are spam, and no new email is an exact copy of a stored one.
FindThe share of mistakes on the training emails and on new emails.
Given
1,000 stored training emails, each answered with its own label
any unstored email is answered 'not spam'
30 of every 100 new emails are spam
no new email repeats a stored one
Solution
Count mistakes per 100 emails instead of reasoning about the filter in general: its behaviour on new mail is fixed completely by its rule, so a count settles it.
Training emails
$$\text{mistakes} = 0 \text{ of } 1{,}000$$
every training email is in the table and gets its own label back
$$\text{training error} = 0$$
0 divided by 1,000
New emails
$$\text{answer} = \text{not spam for every new email}$$
no new email is in the table, so the default answer is always the one used
$$\text{mistakes} = 30 \text{ of every } 100$$
the answer is wrong exactly on the spam emails, and there are 30 in every 100
$$\text{error on new email} = 0.30$$
30 divided by 100
Answer $$\boxed{\text{training error } 0,\qquad \text{error on new email } 0.30}$$
Check
A rule that never looked at any data, 'always answer not spam', also makes 30 mistakes in every 100 new emails. The memoriser does exactly as well as a rule that learned nothing.
That settles the report from the start of this concept: the 0 was about memory, the 0.30 is about learning. Every error this course cares about is measured on examples the algorithm did not train on.
Supervised, unsupervised or reinforcement: three tasks sorted
Classify each task.
(i) Predict the selling price of a flat from its size, age and district, using 3,000 past sales.
(ii) Split 50,000 news articles into topics when no article carries a topic tag.
(iii) A thermostat changes the heating and, an hour later, receives a comfort score from the occupants.
FindThe kind of learning in each task.
Given
(i) 3,000 past sales with their prices
(ii) 50,000 untagged articles
(iii) heating actions, each followed by a comfort score
Solution
Ask two questions in a fixed order, 'is there a label for each example?' and then 'do the learner's own actions decide what it sees next?', instead of judging from the application area.
Test (iii) against the supervised reading: nobody ever tells the thermostat the right setting, only how good its chosen setting was, so there is no label to fit.
Sort by the data, not by the domain: the same flats would be an unsupervised task if the prices were missing.
Checkpoint
§01.1 — which kind of learning a music app does
A music app plays one song after another. After each song it records whether the listener skipped it, and it uses those records to choose the next songs.
Find(a) Which kind of learning describes the app's task best?
Given
the app picks every song itself
after each pick it sees 'skipped' or 'not skipped'
Hint 1/4
Do not start from the word 'data'. Ask who decides which song gets a reaction recorded.
Hint 2/4
Supervised: labelled pairs given in advance. Unsupervised: inputs only. Reinforcement: the learner acts and then receives a reward that depends on its action.
Hint 3/4
In this app, the app chooses every song, and afterwards it sees only 'skipped' or 'not skipped' for that song, never which song it should have chosen.
Hint 4/4
So the task is reinforcement learning.
Show solution
Apply the two questions from the worked example: is there a label, and do actions decide the feedback?
Is there a label?
$$\text{skip} \ne \text{the right song}$$
a skip scores the chosen song; it never says which song was correct
Do actions decide the feedback?
$$\text{song chosen}\ \to\ \text{skip or not}\ \to\ \text{next choice}$$
the app only learns about songs it decided to play
Answer $$\boxed{\text{reinforcement learning}}$$
Check
Contrast check: if the app were handed a fixed file of songs, each with the song the listener preferred, it would be supervised. Nothing like that file exists here.
When the learner's actions decide what data it gets, it is doing reinforcement learning, whatever the domain.
⚠ Reporting training error as the performance
it is the only error you can compute without holding data back, and a small number looks like good news
wrong$$\text{training error} = 0\ \Rightarrow\ \text{error on new data}\approx 0$$
right$$\text{error on new data is measured on examples not used for training}$$
⚠ Expecting the right rule to pass through every training point
fitting the data exactly feels like the goal of learning
wrong$$\hat f(x_i) = y_i \ \text{for all } i \ \text{is the aim}$$
right$$y_i = f(x_i) + \omega_i:\ \text{even } \hat f = f \text{ misses by } \omega_i$$
1.2Probability spaces: outcomes, events and three axioms
Assigns a probability to every event from three rules, and gives the order property and the union bound for free.
The error of a learner is a probability, so first we say exactly what a probability is attached to; for coin tosses this machinery looks like overkill, and it is, until the events get complicated.
DefinitionProbability space (Ω, F, P)
Conditions
$\Omega$, the sample space, is the set of all outcomes of the experiment
$\mathcal F$ holds the events, the subsets of $\Omega$ we may ask about; for a finite $\Omega$ it is every subset, the power set $2^{\Omega}$
$P$ gives each event a number and obeys the three axioms (A1) to (A3)
Probabilities are never negative, the whole space has probability one, and for events that cannot happen together the chance that one happens is the sum. So an event is never more likely than a larger event containing it, and the chance of at least one of several events is at most the sum of their chances.
Proof
Order. Let $C = B\setminus A$, the part of $B$ outside $A$. Then $A$ and $C$ are disjoint and $A\cup C = B$.
By (A3), $P(B) = P(A) + P(C)$, and by (A1), $P(C)\ge 0$, so $P(B)\ge P(A)$.
Union bound, two events. $A\cup B$ is the disjoint union of $A$ and $B\setminus A$, so $P(A\cup B) = P(A) + P(B\setminus A)$.
The order property gives $P(B\setminus A)\le P(B)$, hence $P(A\cup B)\le P(A) + P(B)$. Adding one event at a time extends this to any number of events.
Two models tested on the same images. Adding $\textcolor{#1f6feb}{P(A)}$ and $\textcolor{#1f6feb}{P(B)}$ counts the $\textcolor{#6f42c1}{\text{overlap}}$ twice, so the sum can only overshoot $\textcolor{#d1690a}{P(A\cup B)}$. That overshoot is the whole content of the union bound.
Looks like this, but is not
A spam model reports $P(\text{spam}) = 0.6$ and $P(\text{not spam}) = 0.5$ for an email. Each number lies between 0 and 1, so each one looks like a legitimate probability.
The two events are disjoint and together make up the whole sample space, so (A2) and (A3) force the two numbers to add up to 1. Here they add up to 1.1, so no probability space produces this pair.
reading
what $P(\text{heads}) = \tfrac12$ says
what it describes
frequentist
in 1,000 tosses, about 500 heads, with the share settling near one half as tosses continue
a long run of repeatable experiments
Bayesian
before the next toss, heads and tails are equally plausible to me
my uncertainty about one event
Both readings obey the same three axioms, so every rule in this section holds under either. They part ways when the unknown is a parameter instead of an event, which is the subject of the next section.
Sample space of a three-image mini-batch
A mini-batch takes 3 images one after another. Each draw is a cat (C) or a dog (D) with equal chance, independently of the other draws. Build the probability space and find the chance of at least one dog, of exactly two cats, and of a cat first.
Find$\Omega$, $P$, and the three probabilities.
Given
3 draws
each draw is C or D with chance 1/2
the draws are independent
Solution
List ordered outcomes like CCD instead of counts like 'two cats': ordered outcomes are equally likely and counts are not, and counting only works for equally likely outcomes.
the first letter is fixed as C and the other two are free
Answer $$\boxed{P(\text{at least one dog}) = \tfrac78,\quad P(\text{two cats}) = \tfrac38,\quad P(\text{cat first}) = \tfrac12}$$
Check
Sum check: 0, 1, 2 and 3 cats have chances 1/8, 3/8, 3/8 and 1/8, which add to 1 as (A2) demands. Giving the four counts a quarter each would put 'exactly two cats' at 1/4.
Count only equally likely outcomes. When a natural description, like the number of cats, has unequal chances, go down to the ordered outcomes first.
Bracketing a failure chance with two free properties
A prediction service calls three components on every request. Their failure chances are 0.02, 0.03 and 0.01, and nothing is known about how the failures are related. The request fails if any component fails. What can be said for sure about the chance that a request fails?
FindUpper and lower bounds on $P(A_1\cup A_2\cup A_3)$.
Given
$P(A_1) = 0.02$, $P(A_2) = 0.03$, $P(A_3) = 0.01$
the request fails on $A_1\cup A_2\cup A_3$
no information about dependence
Solution
Use the two properties instead of an exact formula: the exact union needs the overlaps, which are unknown, while the bounds need only the three numbers.
If the failures happened to be independent, the exact value would be $1 - 0.98\times 0.97\times 0.99 = 0.0589$. It sits inside the bracket, near the top because the overlaps are tiny.
When dependence is unknown, bound instead of guessing. The union bound is how a single guarantee can later cover many error events at once.
Checkpoint
§01.2 — three screening rules and the union bound
Three screening rules each wrongly block a normal email with probability at most 0.01. An email is blocked if any rule blocks it, and nothing is known about how the rules' mistakes are related.
Find(a) What can you say for sure about the chance that a normal email is wrongly blocked?
Given
each rule wrongly blocks a normal email with probability at most 0.01
blocked if any of the three rules blocks it
no information about dependence
Hint 1/4
The event of interest is 'at least one rule blocks', a union of three events whose overlaps are unknown.
Hint 2/4
Union bound: $P(A_1\cup A_2\cup A_3)\le P(A_1) + P(A_2) + P(A_3)$, with no condition on dependence.
Hint 3/4
Each $P(A_i)\le 0.01$, so the sum is at most $0.01 + 0.01 + 0.01$.
Hint 4/4
So the chance is at most 0.03, and nothing sharper follows from what is given.
Show solution
Only the union bound can be used, because an exact value would need the overlaps.
The bound is reached when the three mistakes never happen together and each has chance exactly 0.01, so 0.03 cannot be improved without more information.
The union bound is sharp when the events barely overlap, which is the usual situation for rare errors.
⚠ Counting unequal outcomes as if they were equally likely
'number of cats' has four values, and it is tempting to give each value a quarter
wrong$$P(\text{exactly two cats}) = \tfrac14$$
right$$P(\text{exactly two cats}) = \tfrac38$$
⚠ Adding the chances of events that overlap
(A3) looks like a general rule for unions, but it only applies to disjoint events
1.3Conditional probability, independence and Bayes' rule
Updates a probability once evidence arrives, and turns 'data given hypothesis' into 'hypothesis given data'.
So far every probability was measured against all of $\Omega$; evidence means we learn that an event $B$ happened, and $B$ becomes the new whole.
TheoremConditioning, independence and Bayes' rule
Conditions
$P(B) > 0$, so that dividing by it makes sense
in the denominator, $A_1,\dots,A_k$ split $\Omega$: they are disjoint and one of them always happens
$$\boxed{\begin{aligned} P(A\mid B) &= \frac{P(A\cap B)}{P(B)}\\ A, B \text{ independent} &\iff P(A\cap B) = P(A)\,P(B)\\ P(A\mid B) &= \frac{P(B\mid A)\,P(A)}{P(B)},\qquad P(B) = \sum_{i=1}^{k}P(B\mid A_i)\,P(A_i)\end{aligned}}$$
Given B, the chance of A is the share of B that also lies in A. Independence means this share equals the plain chance of A, so one event says nothing about the other. Bayes' rule reverses the conditioning: the is proportional to the times the likelihood, the chance of the evidence under the hypothesis.
Proof
The definition gives $P(A\cap B) = P(A\mid B)\,P(B)$ and, with the roles swapped, $P(A\cap B) = P(B\mid A)\,P(A)$.
Set the two equal and divide by $P(B)$: that is Bayes' rule.
For the denominator, $B$ is the disjoint union of the pieces $B\cap A_i$, so (A3) gives $P(B) = \sum_i P(B\cap A_i) = \sum_i P(B\mid A_i)P(A_i)$, the law of total probability.
The fraud detector as counts in 100,000 transactions. The flags come from two branches, $\textcolor{#1f6feb}{99}$ true hits and $\textcolor{#1f6feb}{1{,}998}$ false alarms, and the chance that a flag means fraud is $\textcolor{#d1690a}{99/2{,}097}$.
Looks like this, but is not
Two events that can never happen together look like the least related pair there is: 'the image is a cat' and 'the image is a dog', each with probability 0.5.
They are strongly dependent. If one happens the other cannot, so $P(\text{cat}\cap\text{dog}) = 0$ while $P(\text{cat})\,P(\text{dog}) = 0.25$. Independence means one event says nothing about the other; here it says everything.
clicked
did not click
total
mobile
90
510
600
desktop
60
340
400
total
150
850
1,000
Both rows click at the same rate, $90/600 = 60/400 = 0.15$, the rate of the whole table. That is what independence looks like in a table of counts.
What a fraud flag means: 99 hits in 100, and 1 fraud in 1,000
A detector flags 99 of every 100 fraudulent transactions and 2 of every 100 legitimate ones. One transaction in 1,000 is fraudulent. A transaction has been flagged. How likely is it to be fraud?
Find$P(\text{fraud}\mid\text{flag})$
Given
$P(\text{fraud}) = 0.001$
$P(\text{flag}\mid\text{fraud}) = 0.99$
$P(\text{flag}\mid\text{legit}) = 0.02$
Solution
Count through an imagined population of 100,000 transactions before touching the formula: the counts make the denominator visible, and the denominator is where this problem is usually lost.
Formula route, without the counts: $P(\text{flag}) = 0.99(0.001) + 0.02(0.999) = 0.02097$ and $0.00099/0.02097 = 0.0472$. Sense check: among flags, false alarms outnumber frauds about 20 to 1, so the answer must be near 1/21.
Three multiplications and one division. Counting is slower than the formula the first time, and it is the version that still works under exam stress.
The flag is strong evidence, since it multiplies the odds by 0.99/0.02 = 49.5, but the odds start at 1 to 999. The prior matters as much as the detector.
Is clicking independent of the device? Reading it off a table
Out of 1,000 sessions, 600 were on mobile and 90 of those ended in a click; of the 400 desktop sessions, 60 ended in a click. Is the event 'click' independent of the event 'mobile'?
Compare the conditional chance $P(\text{click}\mid\text{mobile})$ with $P(\text{click})$: it asks the same question as the product rule and reads straight off the table.
The desktop row must agree as well, and it does: $60/400 = 0.15$. With two rows, the overall rate is a weighted average of the two row rates, so if one row matches it, the other must too.
Independence is a numerical fact you check, not a story you assume: change 90 clicks to 120 and the same story becomes dependent.
Checkpoint
§01.3 — a flagged chip and Bayes' rule
A wafer test screens chips. 2 of every 100 chips are defective. The test flags 90 of every 100 defective chips and 5 of every 100 good chips.
Find(a) A chip is flagged. What is the probability that it is defective?
Given
$P(\text{defective}) = 0.02$
$P(\text{flag}\mid\text{defective}) = 0.90$
$P(\text{flag}\mid\text{good}) = 0.05$
Hint 1/4
The chip is known to be flagged, so the flagged chips are the new whole. Ask what share of them is defective.
With $P(D) = 0.02$, $P(F\mid D) = 0.90$ and $P(F\mid G) = 0.05$: the numerator is $0.90\times 0.02 = 0.018$ and the denominator is $0.018 + 0.05\times 0.98 = 0.067$.
Hint 4/4
So the chance is $0.018/0.067\approx 0.27$.
Show solution
The prior and both likelihoods are given, so Bayes' rule with total probability in the denominator is direct.
A random variable attaches a number to each outcome. Its CDF at x is the chance of a value at most x, climbing from 0 to 1. A discrete variable has a pmf, the chance of each value; a continuous one has a pdf, the slope of the CDF, and its probabilities are areas under that pdf.
The CDF of the number of cats in the three-image batch. It is flat between the possible values and jumps at each one by exactly $\textcolor{#d1690a}{p_X(x)}$, so the pmf can be read off the CDF as the heights of its jumps.
Looks like this, but is not
A model's confidence score $S$ has density $f_S(s) = 2s$ on $[0,1]$, so $f_S(0.9) = 1.8$. A value above 1 looks like a probability above 1, so the density seems broken.
A density is probability per unit length, not a probability. Probabilities are areas: $P(0.9\le S\le 0.91)\approx 1.8\times 0.01 = 0.018$. Only the total area has to be 1, and $\int_0^1 2s\,ds = 1$.
family
values
pmf or pdf
a typical use in this course
Bernoulli $\mathrm{Ber}(p)$
$\{0,1\}$
$p_X(1) = p,\ p_X(0) = 1-p$
one prediction right or wrong; one click
binomial $\mathrm{Binomial}(n,p)$
$\{0,\dots,n\}$
$\binom{n}{y}p^{y}(1-p)^{n-y}$
errors among $n$ independent test cases
Poisson $\mathrm{Poisson}(\lambda)$
$\{0,1,2,\dots\}$
$e^{-\lambda}\lambda^{y}/y!$
rare events over many tries: failed requests, typos
Read the family off the values the variable can take: 0 or 1 is Bernoulli, a count out of $n$ is binomial, an open-ended count of rare events is Poisson, any real number with a bell shape is Gaussian, and a number in $[0,1]$ is a candidate for a . $B(\alpha,\beta)$ is the constant that makes its area 1.
From outcomes to pmf and CDF: cats in a three-image batch
Three images are drawn independently, each a cat (C) or a dog (D) with chance 1/2. Let $X$ be the number of cats. Find the pmf and the CDF of $X$, and $P(1\le X\le 2)$.
Find$p_X$, $F_X$ and $P(1\le X\le 2)$.
Given
8 equally likely ordered outcomes, from CCC to DDD
$X(\omega)$ is the number of C's in $\omega$
Solution
Group the 8 outcomes by their value of X first. The pmf is then a count, and the CDF is a running sum of the pmf, so no new probability has to be worked out.
Direct count: one or two cats covers 3 + 3 = 6 of the 8 outcomes, and 6/8 = 3/4. The CDF also ends at 1, as every CDF must.
For a discrete variable, subtract the CDF just below the left end of an interval, so that a jump sitting at the left end is kept.
A continuous confidence score with density 2s on [0, 1]
A classifier's confidence score $S$ has pdf $f_S(s) = 2s$ for $0\le s\le 1$ and 0 elsewhere. Check that this is a valid pdf, find the CDF, and find $P(S>0.5)$ and $P(S = 0.5)$.
FindThe CDF, $P(S>0.5)$ and $P(S = 0.5)$.
Given$f_S(s) = 2s$ on $[0,1]$, zero elsewhere
Solution
Find the CDF once and read every probability from it; integrating the pdf again for each question repeats the same work.
Area route: under $2s$ between 0.5 and 1 lies a trapezoid with parallel sides 1 and 2 and width 0.5, of area $\frac{1+2}{2}\times 0.5 = 0.75$.
For continuous variables $\le$ and $<$ give the same probability; for discrete ones they may differ by a whole jump.
Law of rare events: 2,000 requests, each failing with chance 0.001
A server handles 2,000 requests, and each fails with probability 0.001, independently. Let $X$ be the number of failures. Find $P(X = 0)$ and $P(X\le 2)$ exactly, and with a Poisson approximation.
Find$P(X = 0)$ and $P(X\le 2)$, binomial and Poisson.
Given
$n = 2{,}000$ independent requests
failure chance $p = 0.001$ each
Solution
Compute the binomial once to see the exact answer, then the Poisson with the same mean $\lambda = np = 2$; the comparison is the point, since the Poisson needs no binomial coefficients with 2,000 in them.
The two values of P(X = 0), 0.13520 and 0.13534, agree to three decimals, and the two values of P(X ≤ 2) agree to seven. Mean check: both models have mean np = 2.
Many tries, each with a small chance, add up to a Poisson count with $\lambda = np$: the law of rare events. That is why counts of rare failures are modelled as Poisson.
Checkpoint
§01.4 — reading a pmf value off a CDF
A discrete random variable $X$ counts the defects found on a circuit board. Its CDF is $F_X(x) = 0$ for $x<0$, $0.2$ for $0\le x<1$, $0.7$ for $1\le x<3$, and $1$ for $x\ge 3$.
Find(a) Find $P(X = 1)$.
Given
$F_X(x) = 0$ for $x<0$
$F_X(x) = 0.2$ for $0\le x<1$
$F_X(x) = 0.7$ for $1\le x<3$
$F_X(x) = 1$ for $x\ge 3$
Hint 1/4
A pmf value of a discrete variable is visible on its CDF. Look at what the CDF does exactly at the value 1.
Hint 2/4
$P(X = x) = F_X(x) - F_X(x^-)$: the size of the jump at $x$, where $F_X(x^-)$ is the level just before $x$.
Hint 3/4
Here the CDF sits at 0.2 on $[0,1)$ and at 0.7 from $x = 1$, so the jump at 1 is $0.7 - 0.2$.
Hint 4/4
So $P(X = 1) = 0.5$.
Show solution
Subtract the level just before the value from the level at the value, which isolates exactly the probability sitting at that point.
The expectation is the probability-weighted average of the values, the balance point of the pmf or pdf. It is linear, even for dependent variables. The variance is the average squared distance from the mean; a shift leaves it alone and scaling by $a$ multiplies it by $a^2$. An indicator averages to its event's probability.
Proof
Shortcut. With $\mu = E[X]$, expand the square and use linearity: $E[(X-\mu)^2] = E[X^2] - 2\mu E[X] + \mu^2 = E[X^2] - \mu^2$.
Scaling.$aX + b - E[aX + b] = a(X - \mu)$, so $\operatorname{Var}(aX + b) = E[a^2(X-\mu)^2] = a^2\operatorname{Var}(X)$; the shift $b$ cancels.
Indicator. $I(X\in A)$ is 1 with probability $P(X\in A)$ and 0 otherwise, so its mean is $1\cdot P(X\in A) + 0 = P(X\in A)$.
The pmf of clicks per session as three weights on a beam. The beam balances at $\textcolor{#d1690a}{E[X] = 0.7}$, a point where no weight sits, which is why an expectation need not be a possible value.
Looks like this, but is not
$E[X^2] = (E[X])^2$ looks like linearity applied to a square: the mean of the square equals the square of the mean.
Squaring is not linear. For the clicks per session below, $E[X^2] = 1.1$ while $(E[X])^2 = 0.49$. The gap, 0.61, is exactly the variance, and it is zero only when $X$ is a constant.
Two quick checks are worth keeping: a Bernoulli variance $p(1-p)$ is never above $\tfrac14$, reached at $p = \tfrac12$, and a Poisson variable has variance equal to its mean.
Mean and variance of clicks per session
The number of clicks $X$ in a session has pmf $p_X(0) = 0.5$, $p_X(1) = 0.3$, $p_X(2) = 0.2$. Find $E[X]$ and $\operatorname{Var}(X)$.
An expectation is a balance point, not a typical value: nobody clicks 0.7 times.
Expected number of test errors through indicators
A classifier $f$ misclassifies a random test image with probability $R(f) = 0.09$. It is run on 400 test images drawn independently. Let $N$ be the number of errors. Find $E[N]$, and write $R(f)$ itself as an expectation.
Find$E[N]$, and $R(f)$ as an expectation.
Given
$R(f) = P(f(X)\ne Y) = 0.09$
400 test pairs $(X_i, Y_i)$
Solution
Write N as a sum of 400 indicators. Linearity then gives the mean without the binomial pmf, and the argument would still work if the images were dependent.
A count is a sum of indicators
$$N = \sum_{i=1}^{400}I\big(f(X_i)\ne Y_i\big)$$
each term is 1 exactly when image i is misclassified
Here $N$ is also $\mathrm{Binomial}(400, 0.09)$, and the binomial mean $np = 400\times 0.09 = 36$ agrees.
Any count is a sum of indicators, and any probability is the mean of an indicator. That is how a classifier's error rate becomes an average that data can estimate.
Mean and variance of the score with density 2s
The confidence score $S$ has pdf $f_S(s) = 2s$ on $[0,1]$. Find $E[S]$ and $\operatorname{Var}(S)$.
Find$E[S]$ and $\operatorname{Var}(S)$.
Given$f_S(s) = 2s$ on $[0,1]$
Solution
Same shortcut as in the discrete case, with integrals in place of sums; power-rule integrals make it quick.
The density leans right, so the balance point must sit above the midpoint 1/2, and 2/3 does. The standard deviation $\sqrt{1/18}\approx 0.24$ is below 0.5, the largest any variable on $[0,1]$ can have.
Discrete or continuous, the recipe is the same: weight by the pmf or the pdf, then use the shortcut.
Checkpoint
§01.5 — variance after scaling and shifting
A sensor reading $X$ has variance 4. A preprocessing step replaces it by $3 - 2X$ before it is fed to a model.
Find(a) Find $\operatorname{Var}(3 - 2X)$.
Given
$\operatorname{Var}(X) = 4$
new feature $3 - 2X$
Hint 1/4
A shift moves every value by the same amount; a scale stretches the distances between values. Ask which of the two a variance can see.
Hint 2/4
$\operatorname{Var}(aX + b) = a^2\operatorname{Var}(X)$.
Hint 3/4
Here $a = -2$, $b = 3$ and $\operatorname{Var}(X) = 4$, so the variance is $(-2)^2\times 4$.
Hint 4/4
So $\operatorname{Var}(3 - 2X) = 16$.
Show solution
The scaling rule applies directly; expanding the definition would give the same result more slowly.
Standard deviation check: the spread of $X$ is $\sqrt4 = 2$, doubling distances makes it 4, and $4^2 = 16$. A variance can never be negative, so $-8$ was impossible from the start.
Variance ignores shifts and squares scales; standard deviation ignores shifts and scales by the absolute value.
⚠ Squaring the mean instead of averaging the squares
for sums, 'take the mean' and the operation can be swapped, so it feels like they always can
1.6Several random variables at once: joint laws, covariance and random vectors
Handles inputs with many coordinates: how variables move together, and the mean vector and covariance matrix of a random vector.
An input in machine learning is rarely one number; an image or a customer record is a list of numbers that vary together, so we need their , and the notation does get heavier from here.
DefinitionJoint laws, covariance and the covariance matrix
Conditions
conditionals are defined only where the conditioning marginal is positive, $p_X(x) > 0$
$g$ and $h$ are any functions whose expectations exist
$X = [X_1,\dots,X_n]^T$ is a column of random variables with finite variances and mean vector $\mu = E[X]$
for densities, pdfs replace pmfs, and an integral over the other variable replaces each sum
A joint law gives chances for pairs of values; summing out one variable gives a marginal, and dividing by it gives a conditional. Independence factorises the joint CDF and the expectation of any product $g(X)h(Y)$, so the covariance is zero. The covariance matrix is symmetric and positive semidefinite, and with the mean it fixes a Gaussian vector completely.
Proof
Independence factorises expectations. For discrete variables independence means $p_{XY}(x,y) = p_X(x)\,p_Y(y)$, so $E[g(X)h(Y)] = \sum_x\sum_y g(x)h(y)\,p_X(x)\,p_Y(y)$.
The double sum splits into $\big(\sum_x g(x)p_X(x)\big)\big(\sum_y h(y)p_Y(y)\big) = E[g(X)]\,E[h(Y)]$. With $g(x) = x$ and $h(y) = y$ this gives $E[XY] = E[X]E[Y]$, so $\operatorname{Cov}(X,Y) = 0$.
Positive semidefinite. Fix any vector $a$. The number $a^T(X-\mu)$ is a random variable with mean 0.
Its variance is $E\big[a^T(X-\mu)(X-\mu)^Ta\big] = a^T\Sigma a$, and a variance cannot be negative, so $a^T\Sigma a\ge 0$ for every $a$.
Two contours of the Gaussian density with $\textcolor{#1f6feb}{\Sigma}$ having variances 2 and covariance 1. The positive covariance tilts the ellipses along $x_2 = x_1$, so $\textcolor{#d1690a}{P = (1,1)}$ sits on the inner, higher contour and $\textcolor{#d1690a}{Q = (1,-1)}$ on the outer one, although both lie at the same distance from the mean.
Looks like this, but is not
$X$ is $-1$, $0$ or $1$ with chance 1/3 each, and $Y = X^2$. Then $\operatorname{Cov}(X,Y) = E[X^3] - E[X]E[X^2] = 0 - 0 = 0$, so the two look unrelated.
$Y$ is a function of $X$, so knowing $X$ gives $Y$ exactly: $P(Y = 0\mid X = 0) = 1$ while $P(Y = 0) = 1/3$. Covariance only detects a straight-line trend, and this dependence is a parabola. Independence implies zero covariance, but not the other way round.
$X = 0$
$X = 1$
$X = 2$
$p_Y(y)$
$Y = 0$, no recommendation
0.30
0.12
0.03
0.45
$Y = 1$, saw a recommendation
0.25
0.20
0.10
0.55
$p_X(x)$
0.55
0.32
0.13
1
Marginals are the row and column totals, and all six cells together add to 1. Each row divided by its own total is a conditional pmf of X.
Joint table: items bought and whether a recommendation was seen
For a random shop visit, $X$ is the number of items bought and $Y$ is 1 if the visitor saw a recommendation, 0 otherwise. Find the conditional pmf of $X$ given $Y = 1$, decide whether $X$ and $Y$ are independent, and compute $\operatorname{Cov}(X,Y)$.
Find$p_{X\mid Y}(x\mid 1)$, independence, and $\operatorname{Cov}(X,Y)$.
The conditional means tell the same story as the positive covariance: $E[X\mid Y = 1] = (0.20 + 0.20)/0.55 = 0.73$ items, against $E[X\mid Y = 0] = (0.12 + 0.06)/0.45 = 0.40$.
Four row and column sums before any answer appears; every later question about the same table reuses them.
A positive covariance says that more items go together with seeing a recommendation; it does not say the recommendation caused the purchases.
Mean vector and covariance matrix of a two-feature input
A feature vector $X = [X_1, X_2]^T$ takes the four values $(0,0)$, $(1,1)$, $(2,1)$ and $(3,2)$ with chance 1/4 each. Find $\mu$ and $\Sigma$, and use $\Sigma$ to find $\operatorname{Var}(X_1 - 2X_2)$.
Find$\mu$, $\Sigma$ and $\operatorname{Var}(X_1 - 2X_2)$.
Directly: $X_1 - 2X_2$ takes the values $0, -1, 0, -1$, with mean $-0.5$ and variance $0.25$. Also $\det\Sigma = 0.625 - 0.5625 = 0.0625\ge 0$, as positive semidefinite requires.
The covariance matrix answers the variance of every weighted sum of features at once, through $\operatorname{Var}(a^TX) = a^T\Sigma a$.
Density of a correlated Gaussian pair at two points
$X\sim N(\mu,\Sigma)$ in two dimensions, with $\mu = [0,0]^T$ and $\Sigma = \begin{bmatrix}2 & 1\\ 1 & 2\end{bmatrix}$. Evaluate the density at $P = (1,1)$ and at $Q = (1,-1)$.
Both points are at distance $\sqrt2$ from the mean, yet the ratio of densities is $e^{-1/3}/e^{-1} = e^{2/3}\approx 1.95$: positive covariance favours points whose coordinates agree in sign, as the tilted contours show.
One 2 by 2 inverse and two quadratic forms. The inverse is the step to double-check: a sign slip there swaps which point looks more likely.
In a Gaussian vector the covariance decides the shape: equal distances from the mean do not mean equal densities.
Bayes' rule with a density: which class produced a reading of 1.5
A part is faulty with probability 0.2 and healthy with probability 0.8. Its sensor reading $X$ is $N(2,1)$ for a faulty part and $N(0,1)$ for a healthy one. A part reads $x = 1.5$. How likely is it to be faulty?
Find$P(Y = 1\mid X = 1.5)$
Given
$P(Y = 1) = 0.2$ faulty, $P(Y = 0) = 0.8$ healthy
$X\mid Y = 1\sim N(2,1)$ and $X\mid Y = 0\sim N(0,1)$
observed reading $x = 1.5$
Solution
Use Bayes' rule with the two densities as likelihoods: a single reading has probability zero, but its density plays exactly the part that the chance of the evidence played for events.
prior times likelihood, divided by the same product summed over both classes
Answer $$\boxed{P(\text{faulty}\mid x = 1.5)\approx 0.405}$$
Check
Odds route: the likelihood ratio is $e^{(1.5^2 - 0.5^2)/2} = e^{1} = 2.718$ and the prior odds are $0.2/0.8 = 0.25$, so the posterior odds are 0.680 and the probability is $0.680/1.680 = 0.405$. The constant $1/\sqrt{2\pi}$ never mattered.
With densities Bayes' rule does not change: replace each chance of the evidence by the density of the observed value under that cause.
Checkpoint
§01.6 — can this matrix be a covariance matrix
A student estimates the covariance matrix of two features and reports $\Sigma = \begin{bmatrix}4 & 3\\ 3 & 1\end{bmatrix}$. Before using it in a Gaussian model, you check whether any random vector could have this covariance matrix.
A covariance matrix has two properties. Symmetry is visible at a glance, so test the other one.
Hint 2/4
Positive semidefinite: $a^T\Sigma a\ge 0$ for every $a$. For a symmetric 2 by 2 matrix with non-negative diagonal, this is the same as $\det\Sigma\ge 0$.
Hint 3/4
Here $\det\Sigma = 4\cdot 1 - 3\cdot 3 = -5$, and with $a = [1,-2]^T$, $a^T\Sigma a = 4 - 12 + 4 = -4$.
Hint 4/4
So it cannot be a covariance matrix: the combination $X_1 - 2X_2$ would have variance $-4$.
Show solution
Look for a combination with negative variance: one such combination settles the question, while checking symmetry alone cannot.
Test positive semidefiniteness
$$\det\Sigma = 4\cdot 1 - 3\cdot 3 = -5 < 0$$
a symmetric 2 by 2 matrix with a negative determinant has one negative eigenvalue
1.7Averages settle down: the law of large numbers, the CLT and Hoeffding's inequality
Says how close an average of n samples lands to its mean, and how many samples a promised accuracy costs.
In learning the distribution is unknown and all we hold is an average over n samples, such as an error rate on a test set, so we need a : a bound on how far such an average can stray.
TheoremThree results about averages
Conditions
LLN: $X_1, X_2,\dots$ independent and identically distributed (i.i.d.) with finite mean $E[X]$
CLT: i.i.d. with finite mean $\mu$ and finite variance $\sigma^2$
Hoeffding: $Z_1,\dots,Z_n$ independent, each with $0\le Z_i\le 1$; it holds for every $n$ and every $\varepsilon > 0$
$$\boxed{\begin{aligned} &\text{LLN:} && \bar X_n = \tfrac1n\textstyle\sum_{i=1}^{n}X_i\ \longrightarrow\ E[X]\ \text{ as } n\to\infty\\ &\text{CLT:} && \dfrac{\bar X_n - \mu}{\sigma/\sqrt n}\ \xrightarrow{d}\ N(0,1)\\ &\text{Hoeffding:} && P\big(\vert\bar Z - E[\bar Z]\vert\ge\varepsilon\big)\le 2e^{-2n\varepsilon^2}\\ &\text{sample size:} && n\ge\frac{\ln(2/\delta)}{2\varepsilon^2}\ \Rightarrow\ \text{the bound is at most } \delta\end{aligned}}$$
The average of many independent draws settles at the mean. The CLT adds scale and shape: the typical miss shrinks like $\sigma/\sqrt n$ and looks like a bell for large $n$. Hoeffding's inequality holds at every $n$: for variables in $[0,1]$, the chance that the average misses its mean by $\varepsilon$ or more is at most $2e^{-2n\varepsilon^2}$.
Hoeffding's bound for $\varepsilon = 0.05$ on a log scale. It falls by a factor of 10 every 461 samples, crosses $\textcolor{#1f6feb}{\delta = 0.05}$ at $\textcolor{#d1690a}{n = 738}$, and at the opening question's $n = 400$ it is still $\textcolor{#6f42c1}{0.27}$.
Looks like this, but is not
A classifier $\hat f$ trained on 1,000 images has training error 0.02. Hoeffding with $n = 1{,}000$ and $\varepsilon = 0.05$ gives $2e^{-5}\approx 0.013$, which seems to put the true error within 0.05 of 0.02 with probability 0.987.
The training indicators are not independent draws with mean $R(\hat f)$, because $\hat f$ was chosen after seeing those same images. Hoeffding needs the rule fixed before the data it is tested on are drawn, which is why error is measured on a separate test set.
$n$
bound $2e^{-2n(0.05)^2}$
exact, true error 0.10
exact, true error 0.50
100
1.21
0.130
0.368
200
0.736
0.0244
0.179
400
0.271
0.00126
0.0510
738
0.0499
0.0000113
0.00717
1,000
0.0135
0.00000045
0.00173
The bound never looks at the true error, so it must cover the worst case, near 0.50. At a true error of 0.10 the real chance is about 200 times smaller at n = 400 and 4,000 times smaller at n = 738. A bound above 1, as at n = 100, says nothing.
Five tails in a row: what the law of large numbers does and does not say
A fair coin has shown tails 5 times in a row. Find the chance of heads on the next toss. Then, if the coin is tossed 995 more times, find the expected share of heads among all 1,000 tosses.
FindThe chance of heads next, and the expected share of heads after 1,000 tosses.
Given
fair coin, independent tosses
the first 5 tosses were tails
Solution
Separate the past, which is fixed, from the future, which is still random: independence settles the first question and linearity of expectation settles the second.
Next toss
$$P(\text{H on toss 6}\mid \text{5 tails}) = P(\text{H on toss 6}) = \tfrac12$$
Push it further: after $m$ more tosses the expected share is $\frac{m/2}{m+5}$, which tends to $\tfrac12$ as $m\to\infty$, exactly as the law of large numbers says, without any toss ever favouring heads.
Averages converge because a fixed early streak weighs less and less, not because the coin corrects itself. Believing the second is the gambler's fallacy.
How far can a click rate over 100 users drift? CLT against Hoeffding
Each of 100 users clicks independently with probability 0.2. Estimate the chance that the observed click rate lands at least 0.08 away from 0.2, first with the CLT and then with Hoeffding's bound.
Find$P(\vert\bar X - 0.2\vert\ge 0.08)$ approximately, and a guaranteed upper bound.
Given
$X_i\sim\mathrm{Ber}(0.2)$, i.i.d.
$n = 100$, $\varepsilon = 0.08$
for $Z\sim N(0,1)$: $P(\vert Z\vert\ge 2) = 0.0455$
Solution
Standardise with the CLT for an estimate, then use Hoeffding for a guarantee; they answer different questions, so doing both shows what each is worth.
Exact binomial value: for $X\sim\mathrm{Binomial}(100, 0.2)$, $P(X\le 12) + P(X\ge 28) = 0.0595$. The CLT is close but a little low at $n = 100$; Hoeffding is far above, but it is a guarantee.
The CLT approximates and Hoeffding guarantees. When an answer has to be promised at a fixed n, only the guarantee will do.
The opening question: 400 photos, 36 errors, and the size of a promise
A face recognizer $f$, fixed before testing, makes 36 errors on 400 test photos drawn independently. Bound the chance that the measured error misses the true error $R(f)$ by 0.05 or more. Then find how many test photos guarantee a miss below 0.02, except with chance at most 0.05.
FindThe Hoeffding bound at n = 400, and the smallest n for the promise.
Given
$n = 400$ i.i.d. test pairs, $f$ fixed in advance
36 errors, so $\hat R_{400}(f) = 0.09$
then $\varepsilon = 0.02$ with $\delta = 0.05$
Solution
Write the error rate as an average of indicators first. That is the one step where the machine learning turns into probability, and after it Hoeffding applies directly.
round up: 4,611 photos would leave the bound just above 0.05
Answer $$\boxed{\text{bound at } n = 400:\ 0.271,\qquad \text{needed: } n = 4{,}612}$$
Check
Plug back in: $2e^{-2\times 4612\times 0.0004} = 0.04996\le 0.05$, while $n = 4{,}611$ gives $0.050004$. And if the true error really were 0.14, the exact chance of measuring 0.09 or less on 400 photos is about 0.0016, far below 0.271.
Three lines once the error is written as an average of indicators; that rewriting is the step most easily skipped.
So the honest report is: 0.09 measured on 400 photos, and Hoeffding alone cannot rule out 0.14. With 4,612 photos, the measured value is guaranteed to be within 0.02 of the truth, except with chance at most 1 in 20.
Further reading: the same promise from Chebyshev's inequality
This one is not on the lecture slides; it is here as a yardstick. Using $I(\vert\bar Z - \mu\vert\ge\varepsilon)\le(\bar Z - \mu)^2/\varepsilon^2$, bound the chance of a miss of $\varepsilon$, and compare the sample sizes for $\varepsilon = 0.05$ at $\delta = 0.05$ and at $\delta = 0.001$ with Hoeffding's.
FindChebyshev's sample sizes next to Hoeffding's.
Given
$Z_i$ independent in $[0,1]$, $\mu = E[\bar Z]$
$\varepsilon = 0.05$
$\delta = 0.05$ and $\delta = 0.001$
Solution
Take expectations of the indicator inequality: it uses only the variance, which is exactly why it will lose to Hoeffding.
Chebyshev from the indicator trick
$$P(\vert\bar Z - \mu\vert\ge\varepsilon) = E\big[I(\vert\bar Z - \mu\vert\ge\varepsilon)\big]\le\frac{\operatorname{Var}(\bar Z)}{\varepsilon^2}$$
where the indicator is 1 the right side is at least 1, and where it is 0 the right side is still non-negative
At $\delta = 0.001$: $1/(4\times 0.0025\times 0.001) = 100{,}000$, while $\ln(2{,}000)/0.005 = 1520.2$ rounds up to 1,521. Making the failure chance 50 times smaller costs Chebyshev 50 times more data and Hoeffding about twice as much.
Exponential tails make very small failure chances cheap, which is why Hoeffding, not Chebyshev, is the tool for test sets.
Checkpoint
§01.7 — evaluating Hoeffding's bound
A spam filter, fixed in advance, is run on 200 test emails drawn independently. Its measured error rate $\hat R_{200}$ is the average of 200 indicators, one per email.
Find(a) What upper bound does Hoeffding's inequality give for $P(\vert\hat R_{200} - R\vert\ge 0.1)$?
Given
$n = 200$
$\varepsilon = 0.1$
each indicator is 0 or 1
Hint 1/4
Check the conditions first: independent terms, each between 0 and 1. Then it is a matter of plugging in.
Hint 2/4
$P(\vert\bar Z - E[\bar Z]\vert\ge\varepsilon)\le 2e^{-2n\varepsilon^2}$.
Hint 3/4
With $n = 200$ and $\varepsilon = 0.1$: $2n\varepsilon^2 = 2\times 200\times 0.01 = 4$, so the bound is $2e^{-4}$.
Hint 4/4
So the bound is $2e^{-4}\approx 0.037$.
Show solution
Compute the exponent on its own line first; the usual slips, a missing square or a missing 2, happen when everything is typed at once.
Scale check: at $n = 200$ a miss of 0.1 is about three standard deviations of an error rate near 0.5, since $\sqrt{0.25/200} = 0.035$, so a small bound like 0.037 is plausible.
Always compute 2nε² on its own line; it is the number that decides everything else.
⚠ Dropping the factor 2 in front
the one-sided version has no 2, and it is easy to remember the wrong one
wrong$$P\big(\vert\bar Z - E[\bar Z]\vert\ge\varepsilon\big)\le e^{-2n\varepsilon^2}$$
right$$P\big(\vert\bar Z - E[\bar Z]\vert\ge\varepsilon\big)\le 2e^{-2n\varepsilon^2}$$
⚠ Using Hoeffding on data outside [0, 1] without rescaling
the inequality is quoted for [0, 1] and the range condition is easy to skip
wrong$$X_i\in[2,6]:\ P(\vert\bar X - \mu\vert\ge 0.1)\le 2e^{-2n(0.1)^2}$$
truncating a decimal is a habit, and 737.8 looks close enough to 737
wrong$$n\ge 737.8\ \Rightarrow\ n = 737$$
right$$n\ge 737.8\ \Rightarrow\ n = 738$$
Bayes' rule by counting a population
Any 'given a positive signal, how likely is the cause' question, especially when the cause is rare.
Pick a population
Choose a round number, such as 100,000, large enough that the rarest branch gets a whole count.
Split by the prior
Multiply by $P(A)$ and by $P(A^c)$ to get the two groups.
Split by the likelihoods
In each group, multiply by the chance of the evidence in that group.
Keep the evidence
Add the counts that show the evidence. This sum is the denominator.
Divide
The posterior is the evidence count inside $A$ over the total evidence count.
Where it goes wrong
Stopping at the numerator, which gives the joint chance instead of the conditional one.
Applying the hit rate to the whole population instead of only to the group that has the cause.
Picking a population so small that the rare branch holds a fraction of a person, which hides the denominator again.
Expectation by indicators
The mean of a count whose pmf is awkward, unknown or not needed.
Name the events
Write the count as the number of events $A_1,\dots,A_m$ that happen, one event per item.
Write the sum
$N = \sum_{i=1}^{m}I(A_i)$.
One probability per term
$E[I(A_i)] = P(A_i)$.
Add
$E[N] = \sum_i P(A_i)$, with no independence needed.
Where it goes wrong
Using the same shortcut for the variance, which does need the covariances between the indicators.
Defining the events so that one item can be counted twice.
Test-set size from Hoeffding's inequality
Any promise of the form 'the measured average is within $\varepsilon$ of the truth, except with chance at most $\delta$'.
Check the conditions
Independent terms, each in a known range, and the rule being tested fixed before the data are drawn.
Rescale to [0, 1]
$Z = (X - a)/(b - a)$, and divide the tolerance by $b - a$ as well.
Put the bound under δ
$2e^{-2n\varepsilon^2}\le\delta$.
Solve and round up
$n\ge\ln(2/\delta)/(2\varepsilon^2)$, then the next whole number.
Say it in words
Within the tolerance of the truth, except with chance at most $\delta$.
Where it goes wrong
Leaving the tolerance on the original scale after rescaling the data.
Using the training set, whose indicators depend on the fitted rule.
Dropping the 2 in front of the exponential, which undersizes n and quietly doubles the real failure chance.
Disjoint: an image labelled cat and labelled dog
One image is a cat with probability 0.5 and a dog with probability 0.5, never both. Are the events 'cat' and 'dog' independent?
FindWhether the product rule holds.
Given
$P(\text{cat}) = P(\text{dog}) = 0.5$
an image cannot be both
Solution
Test the product rule directly; the feeling that the two events are unrelated is exactly what the numbers contradict.
Product rule
$$P(\text{cat}\cap\text{dog}) = 0$$
one image cannot be both
$$P(\text{cat})\,P(\text{dog}) = 0.25\ne 0$$
product of the two separate chances
Answer $$\boxed{\text{disjoint, so dependent}}$$
Check
Conditional check: $P(\text{dog}\mid\text{cat}) = 0$, far from $P(\text{dog}) = 0.5$.
Independent: a click and the device used
From 1,000 sessions, $P(\text{mobile}) = 0.6$, $P(\text{click}) = 0.15$ and $P(\text{click}\cap\text{mobile}) = 0.09$. Are the two events independent? Are they disjoint?
FindIndependence and disjointness.
Given
$P(\text{mobile}) = 0.6$
$P(\text{click}) = 0.15$
$P(\text{click}\cap\text{mobile}) = 0.09$
Solution
Run both tests on the same three numbers, so the difference between the two ideas is visible side by side.
Disjoint events exclude each other, so each one tells you everything about the other; independent events leave each other's chances untouched.
How to tell them apart
Compute $P(A\cap B)$ and $P(A)P(B)$. Disjoint makes the first zero; independent makes the two equal. Both at once is possible only when one event has probability zero.
Reading P(flag given fraud) off the specification
The fraud detector from this section flags 99 of every 100 fraudulent transactions and 2 of every 100 legitimate ones, and 1 transaction in 1,000 is fraud. What share of frauds get flagged?
Find$P(\text{flag}\mid\text{fraud})$
Given
$P(\text{flag}\mid\text{fraud}) = 0.99$
$P(\text{fraud}) = 0.001$
Solution
Identify which event is known to have happened before computing anything; here it is the fraud.
Counts: 99 of the 2,097 flagged transactions in every 100,000 are fraud.
The two conditionals use the same two events and here differ by a factor of about 21, because only the second one has to account for how rare fraud is.
How to tell them apart
Put the event you know has happened after the bar. If that event is the cause, read the rate off the model; if it is the evidence, you need Bayes' rule and a prior.
Scaffolding comes off
The common skeleton
Name the variables being averaged, and check that they are independent, lie in a known range $[a,b]$, and come from a rule fixed before the data were drawn.
Rescale to $[0,1]$ with $Z = (X-a)/(b-a)$; a tolerance $t$ on the original scale becomes $\varepsilon = t/(b-a)$.
Write Hoeffding for the rescaled average: $P(\vert\bar Z - E[\bar Z]\vert\ge\varepsilon)\le 2e^{-2n\varepsilon^2}$.
Force the bound under the allowed failure chance: $2e^{-2n\varepsilon^2}\le\delta$.
Solve $n\ge\ln(2/\delta)/(2\varepsilon^2)$ and round up.
State the promise on the original scale, in one sentence.
1 · fully worked
Star ratings from 1 to 5: how many to pin the mean within 0.2 stars
A product page shows the average star rating of randomly chosen buyers. Each rating is a whole number from 1 to 5, and ratings are independent. The shop wants the displayed average within 0.2 stars of the true mean rating, except with chance at most 0.05. How many ratings are needed?
FindThe smallest number of ratings.
Given
ratings $X_i\in[1,5]$, independent
tolerance 0.2 stars
$\delta = 0.05$
Solution
Rescale first, because Hoeffding is stated for [0, 1]; rescaling after solving would leave the tolerance on the wrong scale.
Rescale to [0, 1]
$$Z_i = \frac{X_i - 1}{4}\in[0,1],\qquad \bar Z = \frac{\bar X - 1}{4}$$
subtract the lowest rating and divide by the range, 5 − 1 = 4
$$\vert\bar X - \mu\vert\ge 0.2\iff\vert\bar Z - E[\bar Z]\vert\ge\tfrac{0.2}{4} = 0.05$$
the same division shrinks the tolerance, so ε = 0.05
Bound and solve
$$2e^{-2n(0.05)^2}\le 0.05$$
Hoeffding for the rescaled average, forced under δ
$$P\big(\vert\bar X - \mu\vert\ge 0.2\big)\le 0.05\ \text{ for } n = 738$$
the promise is about stars, so it is stated in stars
Answer $$\boxed{n = 738\ \text{ratings}}$$
Check
Plug back in: $2e^{-2\times 738\times 0.0025} = 0.0499\le 0.05$, while $n = 737$ gives $0.0502$. It matches the crossing in the Hoeffding figure, as it should: after rescaling this is the same problem.
The range of the data enters only through the rescaled tolerance: halve the range and the same promise needs a quarter of the samples.
2 · you write the reasoning
Easier than the rung above: the data are already in [0, 1], so nothing is rescaled. Each visitor clicks (1) or not (0), independently. How many visitors make the measured click rate land within 0.1 of the true rate, except with chance at most 0.02? The steps are done; write why each line is allowed.
$$Z_i = I(\text{visitor } i \text{ clicks})\in\{0,1\}\subseteq[0,1]$$
reasoning
Each click indicator is 0 or 1, so it already lies in [0, 1], and visitors act independently: both conditions of Hoeffding hold without rescaling.
$$\varepsilon = 0.1,\qquad \delta = 0.02$$
reasoning
The tolerance is on the rate itself, which already lives on the [0, 1] scale, so it goes in unchanged; δ is the failure chance the promise may allow.
$$2e^{-2n(0.1)^2}\le 0.02$$
reasoning
Hoeffding's bound for the click rate, forced under δ: if the bound on the failure chance is at most 0.02, the failure chance itself is too.
Divide by 2, take natural logarithms and divide by $2\varepsilon^2$: the inequality is the same as $2n\varepsilon^2\ge\ln(2/\delta)$, and $\ln 100 = 4.605$.
$$n = 231$$
reasoning
Round up: n = 230 leaves the bound at 0.0201, just above 0.02, while n = 231 brings it to 0.0197.
3 · find the buried error
Harder than the rung above: the data need rescaling, and the work below was done badly.
A voltage sensor gives independent readings between 2 V and 6 V.
Goal: an average within 0.1 V of the true mean, except with chance at most 0.01.
Exactly two of the four steps contain a mistake. A later step may carry a wrong number forward without making a new one.
Step 1. The readings are independent and lie in $[2,6]$, so $Z_i = (X_i - 2)/4\in[0,1]$.
Step 2. Rescaling does not change the gap we want, so the tolerance stays $\varepsilon = 0.1$.
Step 3. Require the bound to be at most the failure chance: $e^{-2n\varepsilon^2}\le 0.01$.
The tolerance was left on the volt scale. After the readings are divided by the range 4, a gap of 0.1 V becomes a gap of 0.1/4 = 0.025 on the [0, 1] scale.
The data get rescaled because the theorem demands it, and the tolerance, which the theorem never names, is forgotten.
right
$\varepsilon = 0.1/4 = 0.025$.
⚠ step 3
The factor 2 in front of the exponential is missing, which gives the bound for a miss on one side only.
The one-sided and two-sided versions differ only by that 2, and 'within 0.1 V' is a two-sided promise.
right
$2e^{-2n\varepsilon^2}\le 0.01$, so $n\ge\ln(200)/(2\times 0.025^2) = 4238.7$ and $n = 4{,}239$.
4 · the bare problem
§01.7 — sample size for a 0 to 10 score
A survey asks randomly chosen users for a satisfaction score between 0 and 10, and the answers are independent. The team wants the average score within 0.25 of the true mean score, except with chance at most 0.02.
Find(a) How many users must be surveyed?
Given
scores in $[0,10]$, independent
tolerance 0.25 on the score scale
$\delta = 0.02$
Hint 1/4
The inequality you need is stated for [0, 1], and the scores are not in [0, 1]. Decide what has to change before any formula.
Hint 2/4
Rescale $Z = X/10$, so the tolerance becomes $\varepsilon = 0.25/10$; then $n\ge\ln(2/\delta)/(2\varepsilon^2)$.
Hint 3/4
With $\varepsilon = 0.025$ and $\delta = 0.02$: $n\ge\ln(100)/(2\times 0.025^2) = 4.605/0.00125$.
Hint 4/4
So $n\ge 3684.1$, and 3,685 users are needed.
Show solution
Rescale by the range first, as in the ladder; the rest is the same five lines.
Plug back in: $2e^{-2\times 3685\times 0.000625} = 0.01998\le 0.02$, while 3,684 users give $0.020003$, just above.
Rescale the tolerance together with the data; everything after that is identical from problem to problem.
Full exam-style question
A held-out error estimate, from indicators to a sample sizeexam format
A classifier f is trained on one dataset and then frozen. It is evaluated on a separate test set of n pairs drawn independently from the same source, with true error $R(f) = P(f(X)\ne Y)$ and measured error $\hat R_n(f) = \frac1n\sum_i I(f(X_i)\ne Y_i)$.
(a) Show that $E[\hat R_n(f)] = R(f)$.
(b) With $n = 2{,}000$ test pairs and 170 errors, bound the chance that $\hat R_n$ misses $R(f)$ by 0.03 or more.
(c) How large must $n$ be to guarantee a miss below 0.02, except with chance at most 0.01?
(d) Would the bound in (b) hold if the 2,000 pairs had been the training set?
FindUnbiasedness, one bound, one sample size, and a yes or no with a reason.
Given
$f$ frozen before the test set is drawn
$n = 2{,}000$, 170 errors
tolerances 0.03 in (b); 0.02 with $\delta = 0.01$ in (c)
Solution
Do (a) with indicators and linearity, because (b) and (c) both lean on it: Hoeffding bounds the gap to the mean, so the mean has to be R(f).
For (c), plug back in: $2e^{-2\times 6623\times 0.0004} = 0.009999\le 0.01$, while $n = 6{,}622$ gives $0.010007$. For (b), in words: over repeated test sets of 2,000, the measured error lands within 0.03 of $R(f)$ at least 945 times in 1,000.
Parts (b) and (c) need a calculator; parts (a) and (d) need only the definitions.
The whole chapter meets in this one question: indicators turn an error into an average, linearity centres it, independence licenses Hoeffding, and a logarithm turns the bound into a sample size.
Practice
A · concept 4 questions
1§01.1 — does zero training error mean zero test error
A classifier is trained on 2,000 labelled images and makes no mistakes on them. The team concludes that it will make no mistakes on new images from the same camera.
Find(a) True or false: zero training error implies zero error on new images from the same source.
Given
0 mistakes on the 2,000 training images
new images come from the same source
Hint 1/4
Look for a single rule that has zero training error and is still bad on new images; one such rule settles the claim.
Hint 2/4
A rule is judged by its error on pairs it has not seen: $P(\hat f(X)\ne Y)$ for a new pair $(X, Y)$.
Hint 3/4
The memorising filter from this section made 0 mistakes on its 1,000 training emails and 30 mistakes in every 100 new ones.
Hint 4/4
So the claim is false: zero training error does not imply zero error on new data.
Show solution
A claim about every classifier falls to one counterexample, and the memoriser is the simplest one.
store every training pair and answer a default anywhere else
$$\text{training error} = 0$$
each stored input gets its own label back
Error on new data
$$P(\hat f(X)\ne Y) = P(Y = \text{spam}) = 0.30$$
new inputs are never stored, so the default is wrong exactly on spam
Answer $$\boxed{\text{false}}$$
Check
Independent of the example: whenever the labels carry noise, even the true rule misclassifies some new pairs, so zero error on new data is out of reach for any rule.
Training error measures fit to the examples seen; only data held out from training measure performance.
2§01.3 — are exclusive events independent
In a dataset every image has exactly one label. 'The label is cat' has probability 0.4 and 'the label is dog' has probability 0.3. A classmate says that since the two labels never occur together, the events are independent.
Find(a) True or false: 'cat' and 'dog' are dependent events.
Given
$P(\text{cat}) = 0.4$
$P(\text{dog}) = 0.3$
no image has both labels
Hint 1/4
Independence is a numerical condition, not a story; compute both of its sides.
Hint 2/4
$A, B$ independent $\iff P(A\cap B) = P(A)\,P(B)$.
Hint 3/4
Here $P(\text{cat}\cap\text{dog}) = 0$, while $P(\text{cat})\,P(\text{dog}) = 0.4\times 0.3 = 0.12$.
Hint 4/4
So the product rule fails, the events are dependent, and the statement is true.
Show solution
Compute both sides of the product rule; the question is settled by two numbers.
the product rule fails, so the events are dependent
Answer $$\boxed{\text{true: dependent}}$$
Check
Conditional check: $P(\text{dog}\mid\text{cat}) = 0$, while $P(\text{dog}) = 0.3$; learning one label changed the other's chance.
Exclusive events with positive chances are always dependent; independence needs overlap in exactly the right proportion.
3§01.4 — a density value above 1
A continuous random variable $X$, a response time in seconds, has a pdf with $f_X(2) = 3$. A teammate says the pdf must be wrong, since a probability cannot be 3.
Find(a) Which conclusion is correct?
Given
$X$ is continuous
$f_X(2) = 3$
Hint 1/4
Ask what a pdf value measures: a probability, or probability per unit length?
Hint 2/4
For continuous $X$: $P(a\le X\le b) = \int_a^b f_X(x)\,dx$ and $P(X = x) = 0$; the only size condition is a total area of 1.
Hint 3/4
With $f_X(2) = 3$, a narrow interval gives $P(2\le X\le 2.01)\approx 3\times 0.01 = 0.03$, a perfectly good probability.
Hint 4/4
So nothing is wrong: a density value may be larger than 1.
Show solution
Translate the height into a probability over a small interval; that is the only way a pdf value turns into a probability.
Height times width
$$P(2\le X\le 2 + h)\approx f_X(2)\,h = 3h$$
for a small width h the area is about height times width
A concrete width
$$h = 0.01:\ 3\times 0.01 = 0.03$$
a valid probability
$$P(X = 2) = 0$$
a single point carries no probability for a continuous variable
Answer $$\boxed{\text{nothing is wrong}}$$
Check
A valid density that reaches 3: the uniform density on [0, 1/3] has height 3 everywhere on its range, and area 3 × 1/3 = 1.
Only areas under a pdf are probabilities; heights just have to be non-negative.
4§01.7 — does Hoeffding need identical distributions
Five hundred independent test images come from five different cameras, so the chance of an error differs from image to image. A teammate says Hoeffding's inequality cannot be used, because the error indicators are not identically distributed.
Find(a) True or false: Hoeffding's inequality still applies to these indicators, even though their error chances differ.
Given
indicators $Z_i\in\{0,1\}$, independent
different error chances for different cameras
Hint 1/4
List exactly what the theorem assumes before deciding whether this situation meets it.
Hint 2/4
Hoeffding: $Z_1,\dots,Z_n$ independent with $0\le Z_i\le 1$ gives $P(\vert\bar Z - E[\bar Z]\vert\ge\varepsilon)\le 2e^{-2n\varepsilon^2}$.
Hint 3/4
Here the indicators are independent and each lies in $\{0,1\}$; $E[\bar Z]$ is the average of the 500 images' error chances.
Hint 4/4
So the statement is true: the bound applies, centred at the average error chance.
Show solution
Match the situation against the theorem's conditions literally, instead of against the usual example of i.i.d. data.
the centre is the average of the individual error chances
Answer $$\boxed{\text{true: independence and range suffice}}$$
Check
For $n = 500$ and $\varepsilon = 0.05$, the bound $2e^{-2.5} = 0.164$ holds here exactly as it would with a single camera.
Read a theorem's conditions literally: Hoeffding asks for independence and a bounded range, nothing about identical distributions.
B · computation 9 questions
1§01.2 — three stages, three ways to bound a failure
A nightly data-processing job has three stages that fail independently, with probabilities 0.05, 0.02 and 0.01. The job fails if at least one stage fails.
Find
(a) Give the union bound on the chance that the job fails.
(b) Find the exact chance, using independence.
(c) Give the lower bound that the order property provides.
Given
$P(A_1) = 0.05$, $P(A_2) = 0.02$, $P(A_3) = 0.01$
stages fail independently
failure means at least one stage fails
Hint 1/4
'At least one fails' is a union; its complement, 'none fails', is an intersection, which independence makes easy.
With 0.05, 0.02 and 0.01: the sum is 0.08, the complements multiply to $0.95\times 0.98\times 0.99 = 0.92169$, and the largest single chance is 0.05.
Hint 4/4
So (a) at most 0.08, (b) 0.0783 and (c) at least 0.05.
Show solution
Go through the complement for the exact value: 'none fails' is a product of three numbers, while the union directly would need inclusion and exclusion.
Total probability in reverse: $0.955\times 0.398 + 0.033\times 0.602 = 0.380 + 0.020 = 0.400$, which is $P(S)$ again.
With a common class, 40 in 100, a flag is trustworthy; the same filter on a rare class would not be. Base rates decide.
3§01.4 — labelling errors, binomial against Poisson
An annotation vendor labels 1,500 images, and each label is wrong with probability 0.002, independently of the others. Let $X$ be the number of wrong labels.
Find
(a) Find $P(X = 0)$ exactly and with the Poisson approximation.
(b) Find $P(X\le 2)$ with the Poisson approximation.
Given
$n = 1{,}500$
$p = 0.002$
labels independent
Hint 1/4
Name the exact model first, then its shortcut: many tries with a small chance each is the setting of the law of rare events.
Hint 2/4
$X\sim\mathrm{Binomial}(n,p)$, and $X\approx\mathrm{Poisson}(\lambda)$ with $\lambda = np$, where $P(X = y) = e^{-\lambda}\lambda^y/y!$.
The density grows like y squared, so the mass piles up near 1: a mean of 0.75 and 7 in 8 of the mass above 0.5 fit. The standard deviation, 0.19, is below 0.5, as it must be on [0, 1].
For densities $(k+1)y^k$ on $[0,1]$ the mean is $(k+1)/(k+2)$; the pattern checks both this answer and the $2s$ example.
5§01.6 — variances of sums of two features
Two features have $\operatorname{Var}(X_1) = 4$, $\operatorname{Var}(X_2) = 9$ and $\operatorname{Cov}(X_1, X_2) = -3$. A model uses their sum, their difference and their average.
Covariance is what separates the variance of a sum from the sum of the variances; with independent features all three answers would use a covariance of 0.
6§01.7 — the bound at n = 500, then the size for 1 in 100
A fixed classifier is tested on 500 images drawn independently. The team wants to know how far the measured error might stray, and how many images a tighter promise would need.
Find
(a) Evaluate Hoeffding's bound on $P(\vert\hat R_{500} - R\vert\ge 0.04)$.
(b) Find the smallest $n$ that makes this bound at most $0.01$.
Given
$n = 500$
tolerance $\varepsilon = 0.04$
target failure chance $\delta = 0.01$
Hint 1/4
Part (a) plugs numbers in; part (b) runs the same inequality backwards, with n as the unknown.
Hint 2/4
$P(\vert\hat R_n - R\vert\ge\varepsilon)\le 2e^{-2n\varepsilon^2}$, and $2e^{-2n\varepsilon^2}\le\delta\iff n\ge\ln(2/\delta)/(2\varepsilon^2)$.
Answer $$\boxed{\text{(a) } 0.404\qquad \text{(b) } n = 1{,}656}$$
Check
Plug 1,656 back in: $2e^{-2\times 1656\times 0.0016} = 2e^{-5.299} = 0.00999\le 0.01$, while 1,655 gives 0.01002.
At 500 images the guarantee is weak, about 4 in 10; a little over three times as many images bring it to 1 in 100, because the bound falls exponentially.
7§01.5 — classes that never appear in a batch
A training batch of 10 images is drawn with replacement from a dataset with 10 equally common classes. Some classes may not appear in the batch at all.
Find(a) Find the expected number of classes that do not appear in the batch.
Given
10 classes, each with chance 1/10 on every draw
10 independent draws
Hint 1/4
The number of missing classes has an awkward pmf, but it is a sum over the classes of 'is this class missing?'.
Hint 2/4
$N = \sum_{k=1}^{10}I(\text{class } k \text{ missing})$, so $E[N] = \sum_k P(\text{class } k \text{ missing})$.
Hint 3/4
A given class is missed by one draw with chance $0.9$, and by all 10 independent draws with chance $0.9^{10} = 0.3487$.
Hint 4/4
So $E[N] = 10\times 0.3487\approx 3.49$ classes.
Show solution
Sum indicators, one per class; the exact pmf of the count is not needed for its mean.
Indicators, one per class
$$N = \sum_{k=1}^{10}I(A_k),\qquad A_k = \{\text{class } k \text{ never drawn}\}$$
a count written as a sum of indicators
One probability
$$P(A_k) = 0.9^{10} = 0.3487$$
each independent draw misses class k with chance 0.9
Add
$$E[N] = 10\times 0.3487 = 3.49$$
linearity; the indicators are dependent, and it does not matter
Answer $$\boxed{E[N]\approx 3.49}$$
Check
Range check: between 0 and 9 classes can be missing, since 10 draws always show at least one class, and 3.49 lies inside; for a batch of $m$ draws the answer $10\times 0.9^m$ goes to 0 as $m$ grows.
Whenever a count's pmf is messy, sum indicators; dependence between them never affects the mean.
8§01.6 — revenue as a product of independent variables
In a click model, $X$ is the number of ads a visitor clicks: 0, 1 or 2 with chances 0.5, 0.3 and 0.2. $Y$ is the revenue per click in lira, independent of $X$, with $E[Y] = 3$ and $\operatorname{Var}(Y) = 4$. The revenue from one visit is $XY$.
Second route, from the variances: $\operatorname{Var}(X) = 1.1 - 0.49 = 0.61$. For independent factors, $\operatorname{Var}(XY) = \sigma_X^2\sigma_Y^2 + \sigma_X^2E[Y]^2 + \sigma_Y^2E[X]^2$. That is $0.61(4) + 0.61(9) + 4(0.49) = 9.89$.
Independence lets you factor the expectation of any product $g(X)h(Y)$, not only $XY$; that turns a question about a pair into two questions about one variable each.
9§01.5 — mean and variance of a Poisson count
The number of failed requests a server logs in one minute is modelled as $X\sim\mathrm{Poisson}(\lambda)$, with $P(X = y) = e^{-\lambda}\lambda^y/y!$ for $y = 0, 1, 2, \dots$ The table of families lists its mean and variance as both $\lambda$; here you derive them.
Find
(a) Show that $E[X] = \lambda$.
(b) Show that $E[X(X-1)] = \lambda^2$, and deduce $\operatorname{Var}(X) = \lambda$.
(c) Give the mean and standard deviation of the count for $\lambda = 2$.
Given
$p_X(y) = e^{-\lambda}\lambda^y/y!$ for $y = 0, 1, 2, \dots$
$\sum_{k\ge 0}\lambda^k/k! = e^{\lambda}$
Hint 1/4
In each sum the factor $y$ or $y(y-1)$ cancels against the start of $y!$; what is left is again a Poisson pmf summed over all its values.
$E[X] = \lambda\sum_{y\ge 1}e^{-\lambda}\lambda^{y-1}/(y-1)!$ and $E[X(X-1)] = \lambda^2\sum_{y\ge 2}e^{-\lambda}\lambda^{y-2}/(y-2)!$. For (c), $\lambda = 2$.
Hint 4/4
So $E[X] = \lambda$, $E[X(X-1)] = \lambda^2$ and $\operatorname{Var}(X) = \lambda^2 + \lambda - \lambda^2 = \lambda$; for $\lambda = 2$ the mean is 2 failures and the standard deviation $\sqrt2\approx 1.41$.
Show solution
Compute $E[X(X-1)]$ rather than $E[X^2]$: the factor $y(y-1)$ cancels cleanly against $y!$, while $y^2$ does not.
Numeric check for $\lambda = 2$: summing $y\,p_X(y)$ and $y^2p_X(y)$ over $y = 0,\dots,39$ gives 2.0000 and 6.0000, so the variance is $6 - 4 = 2$. It also matches the binomial limit: $np(1-p)\to\lambda$ as $p\to 0$ with $np = \lambda$.
For count data, compare the sample mean with the sample variance: a Poisson model needs them to be about equal.
C · exam level 4 questions
1§01.3 — two screening tests in a row
A factory screens components in two stages; 1 in 200 is defective. Test A flags 95 of every 100 defective and 4 of every 100 good components. Those flagged go to test B, which flags 90 of every 100 defective and 1 of every 100 good ones, independently of A given the true state.
Find
(a) Find the chance that a component flagged by A is defective.
(b) Find the chance that a component flagged by both A and B is defective.
Given
$P(D) = 0.005$
test A: $P(F_A\mid D) = 0.95$, $P(F_A\mid G) = 0.04$
test B: $P(F_B\mid D) = 0.90$, $P(F_B\mid G) = 0.01$
A and B independent given the true state
Hint 1/4
Run Bayes' rule twice: the answer to (a) becomes the prior for (b), because B only sees components that A flagged.
One-shot route, the same number: $$\frac{0.005\times 0.95\times 0.90}{0.005\times 0.95\times 0.90 + 0.995\times 0.04\times 0.01} = \frac{0.004275}{0.004673} = 0.915.$$
Yesterday's posterior is today's prior: independent pieces of evidence can be absorbed one at a time.
2§01.6 — mean and variance of a binomial count
A test set has $n$ images, and a fixed classifier errs on each one independently with probability $p$. The number of errors is $X = \sum_{i=1}^{n}I_i$, where $I_i$ is 1 if image $i$ is misclassified.
Find
(a) Show that $E[X] = np$.
(b) Show that $\operatorname{Var}(X) = np(1-p)$.
(c) Evaluate both for $n = 400$ and $p = 0.09$.
Given
$I_1,\dots,I_n$ independent, with $P(I_i = 1) = p$
$X = \sum_i I_i\sim\mathrm{Binomial}(n,p)$
Hint 1/4
Work with the indicators, not with the binomial pmf: sums of simple pieces are easier than a sum over binomial coefficients.
The case n = 1 gives back the Bernoulli entries of the table: mean p and variance p(1 − p), exactly as the formulas say.
Means of sums never need independence; variances of sums need the covariances, and independence is what sets them to zero.
3§01.7 — the tolerance a test set of 1,000 can promise
A team has exactly 1,000 held-out images for a fixed classifier, and wants to state: the true error is within ε of the measured error, except with chance at most 0.05.
Find(a) What is the smallest $\varepsilon$ that Hoeffding's inequality supports?
Given
$n = 1{,}000$
$\delta = 0.05$
indicators independent, each 0 or 1
Hint 1/4
This time n is fixed and the tolerance is the unknown: run the sample-size inequality the other way round.
Plug back in: $2e^{-2\times 1000\times 0.043^2} = 2e^{-3.698} = 0.0495\le 0.05$, while a tolerance of 0.042 would give 0.059.
The tolerance shrinks like $1/\sqrt n$: four times the test set halves the tolerance you can promise.
4§01.4 — Gaussian label noise
Labels follow $Y = f(X) + \omega$ with $\omega\sim N(0, 0.25)$, independent of $X$. A prediction equal to the true $f(X)$ is called badly off if it misses $Y$ by more than 1.
Find
(a) Find the chance that even the true function is badly off on a new pair.
(b) What noise variance would make that chance exactly 0.05?
Given
$\omega\sim N(0, 0.25)$
for $Z\sim N(0,1)$: $P(\vert Z\vert > 2) = 0.0455$ and $P(\vert Z\vert > 1.96) = 0.05$
Hint 1/4
The true function misses Y by exactly the noise, so the question is about ω alone; turn it into a question about a standard normal.
Hint 2/4
If $\omega\sim N(0,\sigma^2)$ then $\omega/\sigma\sim N(0,1)$, so $P(\vert\omega\vert > c) = P(\vert Z\vert > c/\sigma)$. The second parameter is the variance.
Hint 3/4
Variance 0.25 means $\sigma = 0.5$, so $P(\vert\omega\vert > 1) = P(\vert Z\vert > 2)$. For (b), require $1/\sigma = 1.96$.
Hint 4/4
So (a) is 0.0455, and (b) needs $\sigma = 0.510$, a variance of 0.260.
Show solution
Divide by the standard deviation to reach the standard normal, where the tail values are known.
Direction check: 5 in 100 is a little looser than 4.55 in 100, so the noise may be a little larger than 0.25, and 0.260 is.
Noise puts a floor under the error of every rule, the true one included; no amount of training data removes it.
D · interleaved 4 questions
1§01.0 — how many errors to expect, and how far they spread
Mixed practice; the type is not announced. A classifier with true error rate 0.09 is run on 400 independent test images, and someone later reports a measured error of 0.14 for it.
Find
(a) Find the mean and the variance of the number of errors $N$.
(b) Find the standard deviation of the measured error rate $N/400$.
(c) How many standard deviations above the true rate is 0.14?
Given
true error 0.09 per image, images independent
$n = 400$
reported measured error 0.14
Hint 1/4
Identify the distribution of N first; each part then follows from one formula.
With $n = 400$ and $p = 0.09$: $np = 36$, $np(1-p) = 32.76$ and $\sqrt{0.09\times 0.91/400} = 0.0143$.
Hint 4/4
So the mean is 36, the variance 32.76, the rate's standard deviation 0.0143, and 0.14 sits $(0.14 - 0.09)/0.0143\approx 3.5$ standard deviations above.
Show solution
Recognise the binomial first: independent images with a common error chance; after that every part is one formula.
Exact binomial tail: $P(N\ge 56) = 0.00068$, so a measured 0.14 would be about a 7 in 10,000 event. The bell curve's value at 3.5 standard deviations, 0.0002, understates it at this $n$, but both say rare.
On a 400-image test set, 0.014 is the natural unit for judging a reported error rate.
2§01.0 — which machine, given a defect count
Mixed practice; the type is not announced. A randomly chosen hour of production comes from machine 1 with probability 0.6 and from machine 2 with probability 0.4. In an hour, defects follow a Poisson distribution with mean 2 on machine 1 and mean 5 on machine 2. The chosen hour shows exactly 4 defects.
Find(a) Find the probability that the hour came from machine 1.
Given
$P(M_1) = 0.6$, $P(M_2) = 0.4$
defects: $\mathrm{Poisson}(2)$ on $M_1$, $\mathrm{Poisson}(5)$ on $M_2$
observed: 4 defects
Hint 1/4
This is a which-cause question given evidence; the chances of the evidence come from a named distribution.
Odds form: prior odds 0.6/0.4 = 1.5, likelihood ratio 0.0902/0.1755 = 0.514, posterior odds 0.771, and 0.771/1.771 = 0.435.
Named distributions supply the likelihoods and Bayes' rule does the rest; the structure never changes.
3§01.0 — a combined feature and its covariance
Mixed practice; the type is not announced. Two features $X_1$ and $X_2$ are independent, each with mean 3 and variance 2. A model builds the combined feature $S = 2X_1 - X_2 + 1$.
Find
(a) Find $E[S]$.
(b) Find $\operatorname{Var}(S)$.
(c) Find $\operatorname{Cov}(S, X_1)$.
Given
$X_1, X_2$ independent
$E[X_i] = 3$, $\operatorname{Var}(X_i) = 2$
$S = 2X_1 - X_2 + 1$
Hint 1/4
Three different tools: linearity for the mean, the covariance matrix for the variance, and linearity of covariance in each argument for the last part.
Size check: in size, a covariance is at most the product of the standard deviations, $\sqrt{10}\times\sqrt2 = 4.47$, and 4 is below it.
Linearity gives means for free; for variances, write the covariance matrix down and let $a^T\Sigma a$ do the bookkeeping.
4§01.0 — one test set, five classifiers, one promise
Mixed practice; the type is not announced. Five classifiers, all fixed before testing, are evaluated on the same test set of n independent images. The team wants all five measured errors within 0.05 of their true errors at once, except with total chance at most 0.05.
Find(a) How large must n be?
Given
5 fixed classifiers, one shared test set
tolerance $\varepsilon = 0.05$ for each
total failure chance $\delta = 0.05$
Hint 1/4
The failure event is 'at least one of the five misses', a union. The five misses share images, so they are dependent: bound, do not compute.
Hint 2/4
Union bound: $P(\cup_{k=1}^{5}B_k)\le\sum_k P(B_k)$, and Hoeffding gives each $P(B_k)\le 2e^{-2n\varepsilon^2}$.
Hint 3/4
Require $5\times 2e^{-2n(0.05)^2}\le 0.05$, that is $2e^{-0.005n}\le 0.01$, so $n\ge\ln(200)/0.005$.
Hint 4/4
So $n\ge 1059.7$, and 1,060 images are needed.
Show solution
Bound each classifier with Hoeffding and join them with the union bound; the dependence between the five is unknown and never needed.
Plug back in: $10e^{-0.005\times 1060} = 10e^{-5.3} = 0.0499\le 0.05$. Against one classifier, $\ln 200/\ln 40 = 1.44$, so 44 more images in every 100 buy the promise for all five.
Testing $k$ fixed rules on one test set adds only a $\ln k$ term to the required size, as long as the rules are fixed before the test set is drawn.
Mistake ledger (19 entries)
⚠ Reporting training error as the performance
it is the only error you can compute without holding data back, and a small number looks like good news
wrong$$\text{training error} = 0\ \Rightarrow\ \text{error on new data}\approx 0$$
right$$\text{error on new data is measured on examples not used for training}$$
⚠ Expecting the right rule to pass through every training point
fitting the data exactly feels like the goal of learning
wrong$$\hat f(x_i) = y_i \ \text{for all } i \ \text{is the aim}$$
right$$y_i = f(x_i) + \omega_i:\ \text{even } \hat f = f \text{ misses by } \omega_i$$
⚠ Counting unequal outcomes as if they were equally likely
'number of cats' has four values, and it is tempting to give each value a quarter
wrong$$P(\text{exactly two cats}) = \tfrac14$$
right$$P(\text{exactly two cats}) = \tfrac38$$
⚠ Adding the chances of events that overlap
(A3) looks like a general rule for unions, but it only applies to disjoint events
the three axioms and the two properties they give for free;
conditional probability, Bayes' rule and its denominator;
how the CDF, pmf and pdf turn into each other;
the variance shortcut and the scaling rule;
why zero covariance is not independence, with an example;
what $a^\top \Sigma a$ is the variance of;
Hoeffding's inequality, its conditions and the sample-size formula.
Then reopen the page and compare; whatever is missing is your reread list.
Sort a task into supervised, unsupervised or reinforcement learning from its data alone, and explain why a training error of zero proves nothing?
c-learning-setup
Build the sample space of a three-draw experiment, and bracket the chance of 'at least one failure' when the overlaps are unknown?
c-probability-space
Compute the chance that a flagged item is really positive, with both branches in the denominator, and test two events for independence?
c-bayes
Read a pmf value off a CDF, explain why a pdf may exceed 1, and use the Poisson approximation with λ = np?
c-random-variables
Compute a mean and a variance from a pmf or a pdf, and find the mean of a count by summing indicators?
c-expectation
Get marginals, a conditional and a covariance from a joint table, build Σ for a feature vector, and test whether a matrix can be a covariance matrix?
c-joint-vectors
Evaluate Hoeffding's bound for a test set, solve it for the sample size after rescaling to [0, 1], and say why it may not be applied to training error?
c-concentration
Glossary (46 terms)
supervised learninggözetimli öğrenme
Learning a rule from input and label pairs, so that it predicts the label of new inputs from the same source.
unsupervised learninggözetimsiz öğrenme
Learning structure, such as groups or a shorter description, from inputs that carry no labels.
reinforcement learningpekiştirmeli öğrenme
Learning to choose actions from rewards that follow them, where the learner's own actions decide what it observes.
training dataeğitim verisi
The examples an algorithm uses to build its rule. Errors measured on them describe fit, not performance on new data.
test settest kümesi
Examples kept apart from training and drawn independently, used to measure how a fixed rule does on new data.
labeletiket
The output Y attached to an input X in a training pair: the quantity a supervised learner tries to predict.
noisegürültü
The part of a label that no function of the input can predict, written ω in Y = f(X) + ω.
classifiersınıflandırıcı
A rule that maps each input to one of finitely many labels, such as spam or not spam.
sample spaceörneklem uzayı
The set Ω of all possible outcomes of an experiment.
eventolay
A subset of the sample space that we can ask the probability of.
probability measureolasılık ölçüsü
The function P that gives each event a number and obeys the three axioms.
union bound
The fact that the chance of at least one of several events is at most the sum of their chances, whatever their dependence.
conditional probabilitykoşullu olasılık
The chance of A once B is known to have happened: $P(A \cap B)$ divided by $P(B)$.
independencebağımsızlık
Two events are independent when $P(A \cap B) = P(A)P(B)$, so learning one leaves the chance of the other unchanged.
BayesBayes kuralı
Bayes' rule: the identity that turns the chance of evidence given a cause into the chance of the cause given the evidence.
priorönsel
The probability of a hypothesis before the evidence is taken into account.
likelihoodolabilirlik
The probability of the observed data under a given hypothesis or parameter value.
posteriorsonsal
The probability of a hypothesis after the evidence is taken into account; proportional to prior times likelihood.
law of total probabilitytoplam olasılık kuralı
P(B) equals the sum of P(B given A_i) times P(A_i) over events A_i that split the sample space.
random variablerastgele değişken
A function that assigns a real number to every outcome of an experiment.
CDFbirikimli dağılım fonksiyonu
Cumulative distribution function, F_X(x) = P(X ≤ x): non-decreasing, climbing from 0 to 1.
pmfolasılık kütle fonksiyonu
Probability mass function: for a discrete variable, the function giving P(X = x) for each value x.
pdfolasılık yoğunluk fonksiyonu
Probability density function: for a continuous variable, the slope of the CDF. Probabilities are areas under it, and its values may exceed 1.
binomialbinom dağılımı
The binomial distribution: the number of successes in n independent trials that each succeed with the same chance p.
PoissonPoisson dağılımı
The Poisson distribution: counts 0, 1, 2 and so on, with mean and variance both equal to λ; used for counts of rare events.
Gaussiannormal dağılım
The Gaussian or normal distribution N(µ, σ²): bell-shaped, with mean µ and variance σ².
beta distributionbeta dağılımı
A distribution on [0, 1] with density proportional to $y^{\alpha-1}(1-y)^{\beta-1}$ for two positive parameters; suited to describing an unknown proportion.
law of rare events
The approximation of Binomial(n, p) by Poisson(np) when n is large and p is small.
expectationbeklenen değer
The probability-weighted average of the values of a random variable; the balance point of its distribution.
variancevaryans
The expected squared distance of a random variable from its mean.
indicator functiongösterge fonksiyonu
A random variable equal to 1 when an event happens and 0 otherwise; its mean is the event's probability.
joint distributionortak dağılım
The probabilities of the pairs, or tuples, of values that several random variables take together.
marginalmarjinal
The distribution of one variable alone, obtained from a joint distribution by summing or integrating out the others.
conditional distributionkoşullu dağılım
The distribution of one variable given the value of another: the joint divided by the marginal of the given variable.
independent and identically distributedbağımsız ve özdeş dağılımlı
Random variables that are independent and share one distribution; written i.i.d.
covariancekovaryans
E[(X − E[X])(Y − E[Y])]: a measure of how two variables move together along a straight line.
uncorrelatedilintisiz
Having zero covariance. Weaker than independence, except for jointly Gaussian variables.
random vectorrastgele vektör
A column of random variables defined on the same experiment, such as the features of one input.
covariance matrixkovaryans matrisi
The matrix of all pairwise covariances of a random vector; symmetric and positive semidefinite.
positive semidefinitepozitif yarı tanımlı
A symmetric matrix M with $a^\top M a \ge 0$ for every vector $a$; for a covariance matrix, no weighted sum has negative variance.
multivariate Gaussiançok değişkenli normal dağılım
The distribution of a Gaussian random vector, fixed completely by its mean vector and covariance matrix.
law of large numbersbüyük sayılar yasası
The average of i.i.d. variables with a finite mean converges to that mean as the number of variables grows.
central limit theoremmerkezi limit teoremi
The standardised average of i.i.d. variables with finite variance approaches a standard normal distribution.
HoeffdingHoeffding eşitsizliği
Hoeffding's inequality: a bound, valid at every n, on the chance that an average of independent variables in [0, 1] misses its mean by ε or more.
concentration inequality
Any bound on the chance that a random quantity, such as an average, falls far from its mean.
gambler's fallacykumarbaz yanılgısı
The false belief that after a streak, independent trials favour the outcome that has not appeared.
What comes next
§02 · Bayesian and frequentist machine learning
Next week the unknown becomes a parameter, such as a click rate, instead of an event. Bayes' rule and the beta family from this section come back with a job: turning data into a belief about that parameter, set against the frequentist answer to the same question.
Sources
textbookT. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning, Springer, 2003 The textbook named in the syllabus. No section numbers are quoted in these notes, because this week's syllabus line gives none.
course materialEEE 485/585 chapter 1 lecture slides and lecture notes, Fall 2026 The order of topics and the notation follow them: Ω, F and P for the probability space, ω for the noise in Y = f(X) + ω, and Hoeffding's inequality for variables in [0, 1]. All wording, examples and exercises here are original.
course materialEEE 485 syllabus page on STARS, printed 21 September 2026 Source of the weekly line, the assessment weights quoted in the card and the requirements to sit the final exam.
textbookOther books the syllabus recommends: G. James et al., An Introduction to Statistical Learning (2013); K. P. Murphy, Machine Learning: A Probabilistic Perspective (2012); C. M. Bishop, Pattern Recognition and Machine Learning (2011) Listed as recommended, not required.
standard resultStandard normal tail values P(|Z| ≥ 1) = 0.317, P(|Z| ≥ 1.96) = 0.050 and P(|Z| ≥ 2) = 0.0455, used in the central limit theorem examples.