Learning Theory Flashcards
(8 cards)
What PAC stands for? What is the general idea behind it?
PAC stands for probable approximately correct.
It is a framework to quantify how many examples are enougth to guarantee that a learner will generalize well
What does the framework considers?
A set of instances X
A hypothesis space H (set of functions)
A concept c chosen from a set C
Training data, usually of the format (c(x), x), drawn from an unknown distribution P over X
When a model is said to be PAC learnable?
A model is said to be PAC learnable if, for any target concept, any distribution, and for parameters epsilon and gamma greater than zero and lower than .5, the learner can, with probability 1 - gamma, output a hypothesis with error at most epsilon, using a number of examples that is polynomial in the inverse of epsilon and gamma greater than
When learners are said to form a Version Space? Why is it important?
A learner is said to form a version space when the learner can achieve zero training error. When this happens all hypothesis that are consistent with the training data form the version space.
Version Space is important because a given model will output a hypothesis h with smallest training error values.
What is the bounding generalization concept? How can we derive the number of examples required for a given learner with it?
The bound generalization concept states that we can bound the probability that there exists a hypothesis in the version space with true error exceeding a threshold epsilon. This is done with the size of the hypothesis space H, the threshold value epsilon, and the number of training data N.
Setting the above probability to be att most gamma leads to a bound on the number of examples N required.
What is the agnostic learning concept? How the generalization bound changes under this context?
The agnostic learning concept considers the learners that do not form a version space (no hypothesis in H will perfectly classify all examples)
Now the boundary is built over the difference between true error and training error. The number of examples to ensure that, with high probability, the hypothesis selected by the learner has low generalization error is drawn using the same process.
Define the VC-Dimension concept and how it is important to the learning theory.
VC-dimension is the size of the largest set that can be shattered by H.
Its importance is related to the possibility of the hypothesis space dimension be infinite, what would make the estimation of the number of examples impossible.
How does the risk bound encapsulates the bias-variance trade-off?
With a high capacity hypothesis space (large VC dimension, which increases with the number of features), the bound becomes looser (higher variance)
