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

✍ Scribed by Hans Ulrich Simon

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 631 KB
• Volume: 52
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1006/jcss.1996.0019

✦ Synopsis

Given a p-concept class C, we define two important functions d C (#), d$ C (#) (related to the notion of #-shattering). We prove a lower bound of 0((d C (#)&1)Â(=# 2 )) on the number of examples required for learning C with 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, d ND (#)=0(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.