In one sentence, what is PAC learning?
hardAnswer
- Probably Approximately Correct learning formalizes when a hypothesis class can be learned from a finite sample: for any small epsilon and delta, with enough samples the algorithm returns a hypothesis with error at most epsilon with probability at least 1-delta.
- The required sample size scales with the complexity of the hypothesis class (VC dimension) and 1/epsilon.
Check yourself — multiple choice
- It guarantees zero training error
- It bounds the sample size needed to be approximately correct with high probability
- It only applies to neural networks
- It replaces cross-validation
PAC gives a sample-complexity bound: with enough data you're probably approximately correct.
#theory
Practise Supervised Learning
215 interview questions in this topic.
Related questions
- Generative vs discriminative classifier — what's the difference?
- What is the curse of dimensionality?
- Parametric vs non-parametric models — what's the difference?
- Why do we prefer simpler models when performance is equal?
- What does the no free lunch theorem say for ML?
- What is VC dimension and why should you care?