|
Consider a Machine Learning Algorithm which train from a training set, with the help of PAC learning model we get bounds on training sample size needed so the probability that error is limited(by epsilon) is bounded(by delta). What does PAC learning model say about computational(time) complexity. Suppose a Learning Algorithm is given more time(like more iterations) how the error and probability that error is limited changes As an learning algorithm which takes one hour to train is of no practical use in financial prediction problems. I need how the performance changes as time given to algorithm changes both in terms of error bounds and what is the probability that error is bounded |
You can try to get a better insight on how the size of your data sat and the complexity are related in Andre NG' lecture on Learning Theory http://www.stanford.edu/class/cs229/notes/cs229-notes4.pdf
Chapter 7.1.5 of Bishop's also talks on PAC, but more on the framework itself
Given a training set and test set, if we use a iterative learning algorithm to find the target hypothesis,
How can we say that the P(error > epsilon) < delta.
How to find the error(i assumed given 10 test samples, we find error = 0.5 if 5 out of 10 samples contradict the hypothesis, is this method is correct?)
How can we conform that P(error > epsilon) is bounded using the test set.