eas@utcsrgv.UUCP (Ann Struthers) (11/29/84)
COLLOQUIUM
Tuesday, December 4, 1984
11:00 AM
Sandford Fleming Building 1105
Professor L.G. Valiant
Harvard University
"A Theory of the Learnable"
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 explicity 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 determing the class of concepts that can be learnt using it
in a polynomial number of steps. A probabilistic definition of learn-
ability is introduced that leads to encouraging positive results for
several classes of propositional programs. The ultimate aim or our
approach is to identify once and for all the maximum potential of learning
machines.