A New PAC Bound for Intersection-Closed Concept Classes

Abstract

For hyper-rectangles in R ^ d Auer et al. [1] proved a PAC bound of $O(\frac{1}{\epsilon}(d+{\rm log}\frac{1}{\delta}))$ , where ε and δ are the accuracy and confidence parameters. It is still an open question whether one can obtain the same bound for intersection-closed concept classes of VC-dimension d in general. We present a step towards a solution of this problem showing on one hand a new PAC bound of $O(\frac{1}{\epsilon}(d{\rm log}d+\frac{1}{\delta}))$ for arbitrary intersection-closed concept classes complementing the well-known bounds $O(\frac{1}{\epsilon}({\rm log}\frac{1}{\delta}+d{\rm log}\frac{1}{\epsilon}))$ and $O(\frac{d}{\epsilon}{\rm log}\frac{1}{\delta})$ of Blumer et al. and Haussler et al. [4,6]. Our bound is established using the closure algorithm , that generates as its hypothesis the smallest concept that is consistent with the positive training examples. On the other hand, we show that maximum intersection-closed concept classes meet the bound of $O(\frac{1}{\epsilon}(d+{\rm log}\frac{1}{\delta}))$ as well. Moreover, we indicate that our new as well as the conjectured bound cannot hold for arbitrary consistent learning algorithms, giving an example of such an algorithm that needs $\Omega(\frac{1}{\epsilon}(d+{\rm log}\frac{1}{\epsilon}+{\rm log \frac{1}{\delta}}))$ examples to learn some simple maximum intersection-closed concept class.