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.