STORY%MIT-MC@sri-unix.UUCP (03/31/84)
[Forwarded from the MIT bboard by SASW@MIT-MC.]
TITLE: "A THEORY OF THE LEARNABLE"
SPEAKER: Professor L.G. Valiant, Harvard University
DATE: Thursday, April 5, 1984
TIME: 3:45 Refreshments
4:00 Lecture
PLACE: NE43-512a
We consider concepts as represented by programs for recognizing them and define
learning as the process of acquiring such programs in the absence of any
explicit programming. We describe a methodology for understanding the limits
of what is learnable as delimited by computational complexity. The methodology
consists essentially of choosing some natural information gathering mechanism,
such as the observation of positive examples of the concept, and determining
the class of concepts that can be learnt using it in a polynomial number of
steps. A probabilistic definition of learnability is introduced that leads to
encouraging positive results for several classes of propositional programs.
The ultimate aim of our approach is to identify once and for all the maximum
potential of learning machines.
HOST: Professor Silvio Micali