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.