Learning by Distances

AbstractA model of learning by distances is presented. In this model a concept is a point in a metric space. At each step of the learning process the student guesses a hypothesis and receives from the teacher an approximation of its distance to the target. A notion of a distance measuring the proximity of a hypothesis to the correct answer is common to many models of learnability. By focusing on this fundamental aspect we discover some general and simple tools for the analysis of learnability tasks. As a corollary we present new learning algorithms for Valiant′s PAC scenario with any given distribution. These algorithms can learn any PAC-learnable class and, in some cases, settle for significantly less information than the usual labeled examples. Insight gained by the new model is applied to show that every class of subsets C that has a finite VC-dimension is PAC-learnable with respect to any fixed distribution. Previously known results of this nature were subject to complicated measurability constraints