|
Abstract : |
In this paper we investigate a new formal model of machine learning in which the concept (boolean function) to be learned may exhibit uncertain or probabilistic behavior|thus, the same input may sometimes be classi ed as a positive example and sometimes as a negative example. Such probabilistic concepts (or p-concepts) may arise in situations such asweather prediction, where the measured variables and their accuracy are insu cient to determine the outcome with certainty. We adopt from the Valiant model of learning [27] the demands that learning algorithms be e cient 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 e cient algorithms for learning natural classes of p-concepts, we study and develop in detail an underlying theory of learning p-concepts. 1, |
