Efficient Distribution-free Learning of Probabilistic Concepts

In this paper we investigate a new model of machine learning in which the concept to be learned may exhibit uncertain or probabilistic behavior-thus, the same example may sometimes be classified as positive and sometimes as negative. Such probabilistic concepts (or p-concepts) may arise in situations such as weather prediction, where the measured variables and their accuracy are insufficient to determine the outcome with certainty. We adopt from the Valiant model of learning [18] the demands that learning algorithms be both efficient and general in the sense that they perform well for a wide class of p-concepts and for any distribution over the domain. In addition to giving many efficient algorithms for learning natural classes of p-concepts, we study and develop in detail an underlying theory of learning p-concepts.