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/ϵ(\ln |H|+\ln 1/\delta )$$

What did we learn?

• What is learnable?

• Sample Complexity.