Accession Number : ADA459598


Title :   Active Learning Using Arbitrary Binary Valued Queries


Corporate Author : MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS


Personal Author(s) : KulKarni, S R ; Mitter, S K ; Tsitsiklis, J N


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a459598.pdf


Report Date : Oct 1990


Pagination or Media Count : 13


Abstract : The original and most widely studied PAC model for learning assumes a passive learner in the sense that the learner plays no role in obtaining information about the unknown concept. That is, the samples are simply drawn independently from some probability distribution. Some work has been done on studying more powerful oracles and how they affect learnability. To find bounds on the improvement that can be expected from using oracles, we consider active learning in the sense that the learner has complete choice in the information received. Specifically, we allow the learner to ask arbitrary yes/no questions. We consider both active learning under a fixed distribution and distribution-free active learning. In the case of active learning, the underlying probability distribution is used only to measure distance between concepts. For learnability with respect to a fixed distribution, active learning does not enlarge the set of learnable concept classes, but can improve the sample complexity. For distribution-free learning, it is shown that a concept class is actively learnable iff it is finite, so that active learning is in fact less powerful than the usual passive learning model. We also consider a form of distribution-free learning in which the learner knows the distribution being used, so that 'distribution-free' refers only to the requirement that a bound on the number of queries can be obtained uniformly over all distributions. Even with the side information of the distribution being used, a concept class is actively learnable iff it has finite VC dimension, so that active learning with the side information still does not enlarge the set of learnable concept classes.


Descriptors :   *PROBABILITY DISTRIBUTION FUNCTIONS , QUEUEING THEORY , SAMPLING , ARBITRATION , INVERSE PROBLEMS , LEARNING , MODELS


Subject Categories : Statistics and Probability
      Psychology


Distribution Statement : APPROVED FOR PUBLIC RELEASE