Topic 2: Empirical Risk Minimisation

Question 1

What is F

Answer 1

The chosen family of models for a problem

Question 2

How is F related to Ω

Answer 2

F is always a subset of Ω because we have always have a restricted choice of models

Question 3

What is Ω

Answer 3

The space of all possible models

Question 4

What is Empirical Risk minimisation generally

Answer 4

A mathematical framework to understand the theory of over-fitting

Question 5

What is the input space

Answer 5

X = R^d
real-values in space with dimension d

Question 6

What is the output space

Answer 6

y = R^k
real values in space with dimension k

Question 7

What is a datapoint denotation

Answer 7

(x,y) = R^d x R^k

Question 8

What is IID

Answer 8

“Independent and Identically distributed”
Each datapoint (x,y) is assumed to be an independent sample from the distribution D = P(x,y)

Question 9

What is Sn

Answer 9

The overall dataset
Assumed to be a sample from a joint random variable P(x,y)^n (sampling n times, independently)

Question 10

Loss function mathematical denotation

Answer 10

l:R^k x R^k -> [0, inf]
meaning it takes two labels: true label and model prediction and returns a loss value of 0 upwards (not including infinity)

Question 11

What is always the first argument of the loss function

Answer 11

The true label
aka l(y, f(x))

Question 12

What is empirical risk minimiser

Answer 12

ferm = arginf R^(f,Sn)

The model obtained if we could find the global minimum on a data sample Sn, when we are restricted to the model family F
(it is an estimated risk using an IID sample size n)

Question 13

What is population risk

Answer 13

The true risk, all possible data we may never encounter
Consider n as infinity
Also known as the ‘generalisation error’ - expresses the error that a model f would make, on an average, over all possible inputs

Question 14

The Population risk minimiser in F

Answer 14

f* = arginf R(f)

• indicates optimality
  “Best in family” model
  (now assuming we have infinite data)
  It is a hypothetical model, the optimal model with no restrictions on the data

Question 15

The population risk minimiser in Ω

Answer 15

y* = arginf R(f)

Also known as the Bayes model or bayes prediction (not to be confused with naive bayes)
This is a hypothetical model, the optimal model with no restriction on the model family and no restrictions on the data
Minimises the risk on all possible models (not restricted to a family)

Question 16

What is the population risk minimiser for squared loss

Answer 16

For squared loss y* = Ey∣x[x]
(the expected value of y given x)

this is not computable as we do not have access to the full data distribution

Question 17

What is the population risk minimiser for 0/1 loss

Answer 17

y* = argmaxy p(y∣x)

this is not computable as we do not have access to the full data distribution

Question 18

What is ferm

Answer 18

empirical risk minimiser
the global minimum of the empirical risk

Question 19

What is y*

Answer 19

the bayes model
the global minimum of the population risk

Question 20

What is f*

Answer 20

the best model in our family

Question 21

What is R() denotation

Answer 21

The population risk of…
R(ferm) = denotes the population risk of an ERM
R(f) = population of f
R(y*) = population risk of bayes model

Question 22

What is excess risk

Answer 22

R(f) - R(y)
This quantity tells us how much further we could hypothetically reduce the population risk, since we know it is impossible to do any better than the Bayes model y

Here f is generic, it could be specified to the ferm situation

Question 23

What is the Approximation/Estimation decomposition

Answer 23

R(ferm) - R(y) = R(ferm) -R(f * ) + R(f * ) - R(y )
Excess risk of ferm = estimation error + aproximation error

Question 24

What is Approximation error

Answer 24

error due to restricted model family unable to represent the bayes model
R(f) - R(y)

Question 25

What is Estimation error

Answer 25

Error due to having a small sample, where empirical risk is a poor estimation of population risk
R(ferm) - R(f*)

Question 26

Effect of model family size on approximation error

Answer 26

Approximation error decreases as a larger model family becomes closer to the bayes model

Question 27

Effect of model family size on estimation error

Answer 27

Estimation error increases because the model space becomes larger so finding the best model (f*) in the space is harder

Question 28

How is the excess curve related to under fitting and over fitting

Answer 28

Under fitting where the gradient is -ve (function class is too small, relative to amount of data) -> higher approximation error

Over fitting where the gradient is +ve (function class is too large, relative to amount of data) -> higher estimation error

Question 29

What is Optimisation Error

Answer 29

R(f) - R(ferm)

component of the excess risk caused by a poor learning algorithm
ferm assumes we can find the global minimum of the empirical risk on the training data set - but in reality we have a sub optimal model f
It can be -ve

Question 30

Is it possible to have zero optimisation error

Answer 30

Yes, some situations R(f) - R(ferm) = 0
Eg deep decision trees

Question 31

Approximation/Estimation/Optimisation decomposition

Answer 31

R(f) - R(y) = R(f) - R(ferm) + R(ferm) - R(f) + R(f) - R(y)
Excess risk of f = optimisation error + estimation error + approximation error

Question 32

What is X

Answer 32

Some input space

Question 33

What is Y

Answer 33

some output space

Question 34

what does subscript variable after argmin mean

Answer 34

Eg argmin y
means finding the value for y that minimises the function

Question 35

which R() value comes first in each of Approximation/Estimation/Optimisation terms

Answer 35

the one that does worse
eg approximation = R(f star) - R(y star)

Question 36

what is the approximation error in word form

Answer 36

The choice of model

Question 37

what is the optimisation error in word form

Answer 37

The choice of learning algorithm

Question 38

what is the estimation error in word form

Answer 38

The quality/amount of data

Question 39

why is the optimisation/estimation/approximation a difficult balance

Answer 39

All three components interact with each other so it is not an easy problem

Question 40

In the formula for population risk, why is an integral over x taken

Answer 40

integrates the loss function weighted by probability dist p(x,y) over all x values
Computes the average loss for a given true label y, considering all possible x inputs

Question 41

In the formula for population risk, why is an integral over y taken

Answer 41

computes average loss incurred by the model f (weighted by p(x,y)) when considering all possible combinations of x,y