LEARNING DISTRIBUTIONS BY THEIR DENSITY LEVELS - A PARADIGM FOR LEARNING WITHOUT A TEACHER

We propose a mathematical model for learning the high-density areas of an unknown distribution from (unlabeled) random points drawn accordin g to this distribution. While this type of a learning task has not bee n previously addressed in the computational learnability literature, w e believe that this it a rather basic problem that appears in many pra ctical learning scenarios. From a statistical theory standpoint, our m odel may be viewed as a restricted instance of the fundamental issue o f inferring information about a probability distribution from the rand om samples it generates. From a computational learning angle, what we propose is a few framework of unsupervised concept learning. The examp les provided to the learner in our model are not labeled (and are not necessarily all positive or all negative). The only information about their membership is indirectly disclosed to the student through the sa mpling distribution. We investigate the basic features of the proposed model and provide lower and upper bounds on the sample complexity of such learning tasks. We prove that classes whose VC-dimension is finit e are learnable in a very strong sense, while on the other hand, p-cov ering numbers of a concept class impose lower bounds on the sample siz e needed for learning in our models. One direction of the proof involv es a reduction of the density-level learnability to PAC learning with respect to fixed distributions (as well as some fundamental statistica l lower bounds), while the sufficiency condition is proved through the introduction of a generic learning algorithm. (C) 1997 Academic Press .