Haussler Theorem

Statement

Haussler Theorem

Suppose we are in the modelling framework with finite hypothesis space and probability distribution on . Set . Let our training data be i.i.d. samples from with associated correct answers. For any hypothesis which is consistent with we have a bound on the true error

Proof

Let be the target function.

Let such that (i.e. we have true error ).

Then let be i.i.d. samples from using . The probability is consistent on is As the samples are i.i.d.. Moreover as for this gives us If all had then we have

the required result.