Topic 3: Generalisation Bounds

Question 1

What do generalisation bounds enable

Answer 1

Enable us to state with confidence that a model performs as we say it will - that it will maintain a certain level of accuracy
- very useful in safety critical or sensitive areas
Eg governmental/public services

Question 2

How do we estimate how bad the testing error might get

Answer 2

R^(f,Sn) ~ R(f)
The law of large numbers states an estimate (empirical risk) of some number will approach the true value (population risk), as the sample size increases (n tends to infinity)
use hoeffdings inequality

Question 3

What is Hoeffding’s LHS inequality in algebraic terms

Answer 3

P(|E[X] - 1/nΣxi| ≥ ε ) ≤ δ

Question 4

What is Hoeffding’s inequality in words

Answer 4

Given a true value E[Z], and an empirical estimate 1/n ∑ zi, the probability of the estimate
deviating by more than ϵ from the true value is less than or equal to δ.

Question 5

What is δ

Answer 5

The failure threshold (or failure probability)

Question 6

What is ε

Answer 6

Some tolerance value
We want E[Z] - 1/n∑zi to be within this threshold

Question 7

What is the relationship between n and δ

Answer 7

As n increases, δ decreases to almost 0
(note - use a fixed ε)

Question 8

How do we rearrange hoeffdings equation for ε

Answer 8

ε = sqrt(ln(2/δ) / 2n )

Question 9

What does δ = 0.01 in english terms

Answer 9

We want to be 99% confident

Question 10

What is the relationship between n and ε

Answer 10

As n decreases, ε will decrease to small value

(We can fix a δ eg δ=0.01)
eg the line will asimptote at ε = 0.03 which means we can be 99% confident that the sample risk will be within 0.03 of the true risk

Question 11

How can we solve for n

Answer 11

Alternatively, we can fix δ eg 0.05 (95% confidence) and as we can increase ε on the x axis we can see how many samples (n) we need to be within some ε of the true risk

Question 12

What do we call F

Answer 12

Function class

Question 13

What is the formula for Union Bound (Boole’s inequality)

Answer 13

P ((M⋃i=1) Vi) ≤ (M∑i=1)P (Vi)

Essentially the probability of one of at least one of the values v1 t vm being true
is less than or equal to
the total sum of all individual probabilities (p(v1) + p(v1)…+p(vm))

Question 14

Uniform Deviation Bound (Hoeffdings equation in terms of function class F)

Answer 14

P(∃f ∈|R(f) - R^(f,Sn)| ≥ ε ) ≤ δ = 2|F|exp(-2nε^2)

Question 15

What is the uniform deviation bound in English terms

Answer 15

The probability that there exists a model which violates our tolerance zone is less than or equal to δ

We can also say with 1-δ probability that all of our estimates are within the zone
i.e. ∀f, we have |R(f) - R^(f,Sn)| < ε

Question 16

What assumption are we making about F

Answer 16

The space F is finite

Question 17

What is the formula for the generalisation bound for finite function classes

Answer 17

R(f) ≤ R^(f,Sn) + √ (ln(|F|) + ln(1/δ) / 2n )

Question 18

What does the generalisation bound for function classes mean in English terms

Answer 18

The true error is less than the training error plus a term, dependent on the number of training
samples and the function capacity”.

Question 19

How do size of model and confidence in estimate error relate

Answer 19

If we increase the size of the model, model becomes more flexible and may overfit

our confidence drops

Unless we also increase the size of the data alongside it (n) - mitigates overfitting

Question 20

How do we generally relate population and empirical risk in a formula

Answer 20

population risk ≤empirical risk + ε

Question 21

What is hoeffdings inequality RHS in algebraic terms

Answer 21

2exp(-2nε^2)

Question 22

what is the uniform deviation bound in English terms

Answer 22

the probability that there exists a model which violates our tolerance zone is less than or equal
to δ. Equivalently, we can say that with probability 1 − δ, all of our estimates are within the zone, i.e. ∀f,
we have ∣R(f) − Rˆ(f,Sn)∣ < ϵ

Question 23

What does empirical mean

Answer 23

Rrefers to something that is derived from or based on observed data rather than theoretical assumptions