General Bounds on the Number of Examples Needed for Learning Probabilistic Concepts

Abstract

Given a p-concept classC, we define two important functionsdC(�),d�C(�) (related to the notion of�-shattering). We prove a lower bound of�((dC(�)�1)/(��2)) on the number of examples required for learningCwith an (�,��)-good model of probability. We prove similar lower bounds for some other learning models like learning with�-bounded absolute (or quadratic) difference or learning with a�-good decision rule. For the class ND of nondecreasing p-concepts on the real domain, dND(�)=�(1/�). It can be shown that the resulting lower bounds for learning ND (within the models in consideration) are tight to within a logarithmic factor. In order to get the “almost-matching” upper bounds, we introduce a new method for designing learning algorithms: dynamic partitioning of the domain by use of splitting trees. The paper also contains a discussion of the gaps between the general lower bounds and the corresponding general upper bounds. It can be shown that, under very mild conditions, these gaps are quite narrow.