3) The supervised learning problem

Question 1

In supervised learning, what are the input space, label space, and concept function

Answer 1

Question 2

What is a loss function in supervised learning, and what is its purpose

Answer 2

Question 3

What is the hypothesis space in supervised learning

Answer 3

The hypothesis space H is a set of functions h:X→Y that serve as potential candidates for the concept function c

Question 4

How is the generalisation error of a hypothesis h defined, and what does it represent

Answer 4

Question 5

What is the goal of the supervised learning task, and how is it formulated as an optimisation problem

Answer 5

Question 6

What is training data

Answer 6

Training data refers to pairs (x1 ,y1),…,(xN ,yN)∈X×Y, which are used to learn and approximate the concept function c

Question 7

How is the empirical error of a hypothesis h defined using training data

Answer 7

Question 8

What is the empirical learning problem, and what is the goal of training in supervised learning

Answer 8

Question 9

What is the data-generating distribution setting in supervised learning, and how does it generalise the concept setting

Answer 9

Question 10

What is the difference between regression and classification problems in supervised learning

Answer 10

Question 11

Describe examples of regression and classification problems

Answer 11

Regression -
* House price prediction
* Temperature prediction
* Stock price forecasting
Classification -
* Spam email detection
* Disease diagnosis (disease present or not)
* Image recognition (e.g. digits)

Question 12

What is a parametric model in the context of hypothesis space

Answer 12

• A parametric model is one where the model is fully described using a fixed number of parameters.
• The hypothesis space is the set of all functions the model can represent, and each function is determined by a specific choice of parameters
• Think of it like: Hypothesis space = all possible models we can get by plugging different values into our parameterized formula

Formally - H={H(x,w):w∈W}

Question 13

How is the zero-one loss (0-1 loss) defined

Answer 13

Question 14

Describe an example of a linear classifier defined in a binary classification problem with Y={−1,1} and X=R ^M

Answer 14

Question 15

How does a linear classifier use a hyperplane to classify points in a binary classification problem

Answer 15

Question 16

What is quadratic loss

Answer 16

Question 17

What is the space of square-integrable functions

Answer 17

Question 18

In regression with quadratic loss, how can we minimise the generalisation error

Answer 18

Question 19

Describe the proof tha the conditional expectation is the best predictor under squared loss

Answer 19

Question 20

How is linear regression formulated using quadratic loss and dictionary functions

Answer 20

Question 21

What are some common choices for dictionary functions in linear regression

Answer 21

Question 22

How are the generalisation error and empirical error expressed in linear regression, and what type of optimisation problem does this lead to

Answer 22

Question 23

How is the logistic function defined in a probabilistic classification setting

Answer 23

Question 24

What is logistic regression, and how does it model classification problems

Answer 24

Question 25

What is the Rademacher distribution

Answer 25

Question 26

What is the space G of hypothesis losses, and how is the empirical Rademacher complexity of G defined

Answer 26

Question 27

What is the (non-empirical) Rademacher complexity of G, and what does it intuitively represent

Answer 27

Question 28

What is the relationship between the Rademacher complexities of the hypothesis space H and the associated loss space G in binary classification with 0-1 loss

Answer 28

Question 29

Describe the proof that the ^Rad(G) = 1/2^Rad(H)

Answer 29

Question 30

What is a generalisation bound for functions in G involving Rademacher complexity

Answer 30

Question 31

What is the growth function ΠH(N) of a hypothesis space H, and what does it represent

Answer 31

Question 32

What is an upper bound for the expected supremum of a finite set A⊆X⊆RM involving Rademacher variables

Answer 32

Question 33

What is an upper bound for the Rademacher complexity of a hypothesis space H in binary classification

Answer 33

Question 34

What is a generalisation bound for a hypothesis h∈H in binary classification with 0-1 loss

Answer 34

Question 35

What does it mean for a hypothesis space H to shatter a dataset of size N

Answer 35

Question 36

What is the VC dimension of a hypothesis space H

Answer 36

Question 37

What is an upper bound for the growth function ΠH(N) in terms of the VC dimension

Answer 37

Question 38

What is a generalisation bound for a hypothesis h∈H in terms of the VC dimension

Answer 38

Question 39

What does it mean for a hyperplane H to separate two sets A and B, and how does this relate to their convex hulls

Answer 39

Question 40

What does Radon's Theorem state about the partition of a set A⊆R^M with #A=M+2

Answer 40

Question 41

What is the the hypothesis space of linear classifiers (hypothesis class)

Answer 41

Question 42

What is the VC dimension of the hypothesis space H ^cl, M in R^M

Answer 42

Question 43

What is the Bayes hypothesis

Answer 43

Question 44

What is the optimal hypothesis in a binary classification problem under the zero-one loss

Answer 44

Question 45

Describe the proof of the optimal hypothesis for the zero-loss function

Answer 45

Question 46

What is the Bayes error, and why is it called irreducible

Answer 46

Question 47

How can we split up the generalisation error into three terms

Answer 47

Question 48

What is the approximation-estimation trade-off in machine learning model selection

Answer 48

Question 49

How do we balance approximation and estimation errors when selecting a hypothesis space H

Answer 49