Week 4

Question 1

What does the out-of-sample error measure?

Answer 1

How well our training on the data set has generalized to data we have not seen before.

Question 2

What does the in-sample error measure?

Answer 2

The training performance

Question 3

Generalization error

Answer 3

The discrepancy between Ein and Eout.

Question 4

What is the concept of the growth function?

Answer 4

A number that captures how different the hypotheses in H are, and how much overlap the different events have.

Question 5

dichotomy

Answer 5

The N-tuple that you get when you apply a hypothesis h (in H) to a finite sample. It splits the sample in two groups: h=+1 and h=-1.

Question 6

Wat representeert het aantal dichotomiën eigenlijk?

Answer 6

De verscheidenheid van de hypotheseklasse.

Question 7

What is the growth function in the case of positive rays?

Answer 7

mH(N) = N + 1

Question 8

What is the condition with positive rays?

Answer 8

H consists of all hypothesis h: R -> {-1, +1} of the form h(x) = sign(x-a).
-1 is returned left from a and +1 is returned right from a.

Question 9

Describe the condition with positive intervals:

Answer 9

H consists of all hypotheses in one dimension that return +1 if in some interval and -1 otherwise.
Each hypothesis is specified by two end points of that interval.

Question 10

How many different dichotomies are there in the positive intervals condition?

Answer 10

N+1 / 2 different dichotomies.

Question 11

What is the growth function in the case of positive intervals?

Answer 11

mH(N) = 0.5N^2 + 0.5N + 1

Question 12

What is the hypothesis space in the case of convex sets?

Answer 12

H consists of all hypotheses in two dimensions h: R^2 -> {-1,+1} that are positive inside some convex set and negative elsewhere.

Question 13

When is a set convex?

Answer 13

If the line segment connecting any two points within the set lies entirely within the set.

Question 14

What is the growth function in the case of convex sets?

Answer 14

mH(N) = 2^N

Question 15

Gegeven een hypotheseklasse, de VC-dimensie dvc van die hypotheseklasse is…

Answer 15

het grootste aantal punten N zodat mH(N) = 2^N. Oneindig als voor alle N geldt dat mH(N) = 2^N.

Question 16

Wat is het kleinste breekpunt, uitgedrukt in dvc?

Answer 16

k= dvc + 1

Question 17

break point

Answer 17

When no data set of size k can be shattered by H, then k is the break point for H.

Question 18

What kind of dvc do good models have?

Answer 18

A finite dvc.

Question 19

What kind of dvc do bad models have?

Answer 19

A infinite dvc.

Question 20

How do you compute a dvc for the perceptron?

Answer 20

First show that the dvc is at least a certain value, then show it is at most a certain value.

Question 21

What can you conclude about dvc if there is a set of N points that can be shattered by h?

Answer 21

dvc >_ N

Question 22

What can you conclude about dvc if any set of N points can be shattered by H?

Answer 22

dvc>_N

Question 23

What can you conclude about dvc if there is a set of N datapoints that cannot be shattered by H?

Answer 23

Nothing

Question 24

What can you conclude about dvc if there is no dataset of N points that can be shattered by H?

Answer 24

dvc<N

Question 25

What is the VC dimension of a d-dimensional perceptron^3?

Answer 25

d+1

Question 26

Pocket algorithm

Answer 26

Adjustment on PLA: Save the hypothesis with the smallest Ein

Question 27

What is a plus of the pocket algorithm vs the PLA?

Answer 27

It works even if the data is not linearly separable

Question 28

What is a disadvantage of the pocket algorithm>

Answer 28

It takes a long time to calculate Ein.

Question 29

Wat is het plan om een kleine Eout te bereiken?

Answer 29

1) Zorg dat je de hypothese kiest met de kleinste Ein. 2) Zorg dat Eout ~=~ Ein

Question 30

Als twee hypothesen op elkaar lijken...

Answer 30

dan zullen zowel de in-sample als de out-of sample errors op elkaar lijken de gebeurtenissen Bi veel overlappen.

Question 31

Wat telt het aantal dichotomieën?

Answer 31

Het effectieve aantal hypothesen.

Question 32

Wat beschrijft de groeifunctie voor concept?

Answer 32

Het is het grootste aantal dichotomieën dat je op N punten kunt krijgen, als je de punten zelf mag kiezen.

Question 33

Wat is M?

Answer 33

Het aantal hypothesen in de hypotheseklasse

Question 34

Hoe ga je om met dat M pessimistisch is?

Answer 34

Maak gebruik van het begrip 'aantal effectieve hypothesen' als vervanging voor M, zo ontwijk je de kans op grote afwijkingen van Eout ten opzichte van Ein.

Question 35

Effectieve aantal hypothesen

Answer 35

Kies N datapunten en kijk alleen naar wat de hypothesen doen op die datapunten.

Question 36

Wat is het verschil tussen een hypothese en een dichotomie?

Answer 36

Hypothese h: X -> {-1, +1} Dichotomie h: {x1, x2, x..., xN} -> {-1, +1}

Question 37

Wat is het maximale aantal dichotomieën voor een set van N punten?

Answer 37

2^N

Question 38

Definieer de groeifunctie:

Answer 38

mH(N) = max voor x1, x..., xN in X |H(x1, x..., xN)|

Question 39

Union bound

Answer 39

For any finite set of events, the probability that at least one of them happens is not greater than the sum of the probabilities of the individual events.

Question 40

In what situation do we say that H shatters the data set of N points?

Answer 40

If H is capable of generating all possible dichotomies on those N points. (H is as diverse as it can be on this set, the max of 2^N dichotomies are realised).

Question 41

If the condition mH(N) = 2^N breaks at any point, ...

Answer 41

we can bound mH(N) for all values of N by a simple polynomial based on this break point.

Question 42

What is the upper bound for any mH(N) that has a break point k?

Answer 42

mH(N) <_ B(N,k) met B(N,k) as the maximum amount of dichotomies on N datapoints such that no subset of size k of the N points can be shattered by these dichotomies.

Question 43

Gegeven een hypotheseklasse, de VC-dimensie dvc van die hypotheseklasse is...

Answer 43

het grootste aantal punten N zodat mH(N) = 2^N. Oneindig als voor alle N geldt dat mH(N) = 2^N.

Question 44

Geef weer hoe mH(N) gebonden wordt door de VC-dimensie:

Answer 44

mH(N) <_ N^dvc + 1

Question 45

Kleinste kwadraten schatter

Answer 45

Wanneer je de gradiënt van de in-sample error = 0 oplost en dan wlin krijgt. Je kunt y voorspellen voor een willekeurige x.

Question 46

Ruisterm

Answer 46

Een toevalsvariabele in lineare regressie, y = f(x) + epsilon. Epsilon is dan de ruisterm.

Question 46

Wat representeert het aantal dichotomiën eigenlijk?

Answer 46

De verscheidenheid van de hypotheseklasse.

Question 47

Hoe bepaal je de groeifunctie van een hypotheseklasse H?

Answer 47

1) Kies N=1, en 1 datapunt x->. Kun je beide dichotomiën realiseren met hypothesen uit H? Dan m(H) = 2^N = 2. Anders is N=2 een breekpunt. 2) Ga door voor N=2, N=3 etc. Als je nooit een breekpunt tegenkomt, dan geldt m(H) = 2^N.

Question 48

Give the generalization bound:

Answer 48

E.out(g) <_ E.in(g) + the root of ( (1/2N) * ln(2M/delta) ) with probability of at least 1 - delta.