Active Learning Using Arbitrary Binary Valued Queries

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