Learning Feasiblility Flashcards
(13 cards)
What is the in-sample and out-sample error?
In-sample is the error on the training data, out-sample is the error on the testing data
When is learning feasible?
When all in-samples and out-samples are correctly predicted
What are deterministic learning outputs?
Deterministic learning outputs are completely determined by the input and parameters
What are probabilistic learning?
Introduces uncertainty into the model
Explain this equation and the effect of N?
P (|Ein(h) − Eout(h)| > ϵ) ≤ 2e ^ −2ϵ2N
This equation provides a universal upper bound as it is independent of h and p(x). As N increases, Ein and Eout become closer.
How do we calculate the confidence of Ein and Eout?
1 - 𝛿 where 𝛿 = 2e ^ −2ϵ2N
What is PAC-learnable?
If there is an algorithm A such that for any ϵ and 𝛿, there exists an N that makes the inequality P (|Ein(h) − Eout(h)| > ϵ) ≤ 2e ^ −2ϵ2N hold, then the target function is PAC-learnable.
What is approximately correct?
In-sample error is an approximation of the out-sample error
What is the Hoeffding inequality?
The Hoeffding inequality chooses a h before looing at the data set. To find the final hypothesis g, we repeat Heoffding M times, where M is a constant that can be infinitely large and is the model complexity
What is the Ein and Eout inequality using Hoeffding inequality?
P (|Ein(g) − Eout(g)| > ϵ) ≤ 2Me ^ −2ϵ2N
This still holds when N is large
What is the affect of M on the Hoeffding inequality?
When M is large and H is complex, the Hoeffding inequality worses but the training error improves. Simple models generalise better. Although Hoeffding is not affected by f, f can increase the training error which can be counteracted by changing H
What is the generalisation bound?
Ein(g) - ϵ <= Eout(g) <= Ein(g) + ϵ
What is the formula for ϵ?
square root(1/2N ln 2M / 𝛿)
or
squared root (8/N ln (4 mH (2N)) / 𝛿)
where 𝛿 = 2e ^ −2ϵ2N
