On the Sample Complexity of PAC-Learning Using Random and Chosen Examples

Abstract

Abstract A concept class C that is too difficult to learn from random examples alone can sometimes be learned efficiently using membership queries—that is, by choosing examples. We ask whether using membership queries might serve a different purpose: helping to reduce the number of random examples needed to pac-learn a concept class C that is already known to be pac-learnable. We focus on concept classes that are dense in themselves, such as half-spaces of R n, rectangles in the plane, and the class I = [0,a] : 0 ≥ a < 1 of initial segments of [0,1].Our main results are: 1. Using membership queries can not significantly reduce the total number of random examples needed to pac-learn a dense-in-itself concept class C: ω((1/ε)In(1/δ)) random examples are still required to pac-learn C, where ε and δ are the usual pac-learning parameters. Inter-estingly, this bound holds for any unknown probability distribution, unlike the “standard” proof (due to Ehrenfeucht, Haussler, Kearns, and Valiant [3]), which holds only for a particular distribution constructed by an adversary. 2. Even if the unknown probability distribution is known to be “smooth”, at least (1/2ε) In(1/δ) examples are required to pac-learn C from random examples (only). 3. If the probability distribution is smooth and examples can be chosen as well as drawn randomly, then the number of examples required to pac-learn I decreases significantly to a size logarithmic in 1/ε.