PAC Learning

Question 1

What is proof by contraposition?

Answer 1

Question 2

What’s the intuition of the VC Dimension?

Answer 2

Even if you have infinitely many hypotheses in your hypothesis class, given some training sample, many of those hypotheses will look functionally the same wrt that specified sample

Question 3

What is h? What does it do?

Answer 3

• A hypothesis.
• Applied to some dataset S, generates a labeling of S

Question 4

What is S?

Answer 4

the dataset

Question 5

For the realizable setting, what are the relations between the bound and 1) epsilon, 2) abs(H)?

Answer 5

• Bound is inversely linear in epsilon (e.g. halving the error requires double the examples)
• Bound is only logarithmic in |H| (e.g. quadrupling the hypothesis space only requires double the examples)

Question 6

For the agnostic setting, what are the relations between the bound and

1) epsilon,
2) abs(H)

Answer 6

• Bound is inversely quadratic in epsilon (e.g. halving the error requires 4x the examples)
• Bound is only logarithmic in |H| (i.e. same as Realizable case)

Question 7

What is shattering?

Answer 7

The hypotheses in H can perfectly classify every possible labeling of S

Question 8

What is the VC-dimension?

Answer 8

Def: The VC-dimension (or VaporikChervonenkis dimension) of ℋ is the cardinality of the largest set “ such that ℋ can shatter “.

Or the definition from the recitation. Get rid of one of these

VC dimension of a hypothesis space H is the maximum number of points such that there exists at least one arrangement of these points and a hypothesis h ∈ H that is consistent with any labeling of this arrangement of points

Question 9

When is the VC dimension infinity?

Answer 9

If ℋ can shatter arbitrarily large finite sets, then the VC-dimension of ℋ is infinity

Question 10

To prove that that VC(H) = some value M, what do you have to do?

Answer 10

Question 11

What’s the vc dimension for separators in n dimensions?

Answer 11

n+1

Question 12

What does ∃ mean?

Answer 12

There exists

Question 13

(high level) What’s the corollary to Theorem 1 of the PAC theorem?

Answer 13

Give a numerical bound of the true error

Question 14

What’s the key idea that makes Correlary 4 of theorem 1 of pac learning useful?

Answer 14

• We want to tradeoff between low training error and keeping H simple (aka low VC(H))
• We can tune the lambda parameter in the regularize to hopefully get us to land at the sweet spot in the graph

Question 15

What are the practical ways we can tradeoff between low training error and keeping H simple? (1)

Answer 15

Use a regularizer

Question 16

What are discriminative models?

Question 17

What’s a pmf?

Answer 17

p(x) : Function giving the probability that discrete r.v. X takes value x.

Question 18

What’s a pdf?

Answer 18

f(x) : Function the returns a nonnegative real indicating the relative likelihood that a continuous r.v. X falls in a certain interval

Question 19

What’s a cdf? What’s the symbol?

Answer 19

F(x) : Function that returns the probability that a random variable X is less than or equal to x:

Question 20

What does a beta distribution look like?

Answer 20

Question 21

What does a dirichlet distribution look like?

Answer 21

Question 22

What’s the symbol for expected value of x?

Answer 22

E[X]

Question 23

What are the equations for expected value?

Answer 23

Question 24

What’s the equation for variance (one that applies to both discrete and continuous)

Answer 24

Question 25

What’s the key concept of joint probability? What’s its symbol?

Answer 25

• p(x, y)
• Key concept: two or more random variables may interact. Thus, the probability of one taking on a certain value depends on which value(s) the others are taking.

Question 26

What’s a marginal distribution? How is it written?

Answer 26

For x, it’s written: p(x)

It gives the probabilities of various values of the variables in a subset without reference to the values of the other variables.

E.g. you might have probabilities for two variables x and y each taking some values. Here, the marginal distribution of x wouldn’t include any reference to y

Question 27

What’s the conditional probability?

Answer 27

p(x|y)

Question 28

What’s the equation for conditional probability?

Answer 28

p(x, y) = p(x|y)*p(y)

Question 29

In mathematical terms, how do we know if two variables are independent?

Answer 29

p(x, y) = p(x)p(y)

Question 30

What does it mean to be conditionally independent? Write it in mathematical terms

Answer 30

p(x, y|z) = p(x|z)p(y|z)

Question 31

What is p*?

Answer 31

probability distribution (unknown)

Question 32

What is S?

Answer 32

The training dataset {x^(1),x^(2),…x^(N)}

Question 33

What is H (callographic)?

Answer 33

Our hypothesis space

Question 34

What is h?

Answer 34

maps from inputs (xs) to outputs (ys)

Question 35

What is epsilon?

Answer 35

The amount of error

Question 36

What is delta?

Answer 36

(1-delta) = the probability of PAC?? (Not sure about this)

Question 37

Define consistent in mathematical terms

Answer 37

Question 38

How many points can a linear boundary (with bias) classify exactly for d-Dimensions?

Answer 38

d + 1

Question 39

What’s an important thing to remember about shattering?

Answer 39

To say we shatter n points in d dimensions, we just need to find one arrangement where all possible labelings of that arrangement can be correctly classified. I.e. shattering does not mean it can classify every possible arrangement

Question 40

When given a certain shape classifier and asked if it can shatter a configuration, what’s a good progression to run through to check?

Answer 40

Sequentially check if the classifier can segregate any combination of n points from n=1 to N, where N is the total number of points. If so, then it does shatter.

E.g. Can this classifier select:

1. Any 1 point
2. Any combination of two points
3. Any combination of 3 points
4. ….
5. All N points

Question 41

What’s a concept class?

Answer 41

Synonymous with hypothesis class

Question 42

What is a consistent learner?

Answer 42

A learner that achieves 0 training error in a realizable setting

Question 43

What gives a numerical bound of the true error?

Answer 43

The corollary to Theorem 1 of the PAC theorem?

Question 44

d + 1

Answer 44

How many points can a linear boundary (with bias) classify exactly for d-Dimensions?