I'm looking for a reference (with proof) on hypothesis classes that are not PAC learnable. Is there a simple one too? Are they of any use (if not in practice, maybe as counter examples for some claims)?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
A hypothesis class is not PAC learnable if it has infinite VC dimension, for example the class of polynomial classifiers over $\mathbb{R}$ , or the class of unions of intervals H = ${\cup_{i=1}^{k}{[a_i, b_i]}| k \in \mathbb{R} a_i \leq b_i}$
