Comp Learning Theory¶
Haussler Theorem
- consistent
- independent variables
- knock all high true errors.
- Bound True Error
- natural log is monotonic
- Upper bound of the version space.
How many samples do we need to PAC learn this hypothesis set?
\[M \ge 1/\epsilon (\ln |H| + \ln 1 / \delta)\]
What did we learn?
- What is learnable?
- Sample Complexity.