CALENDAR@IBM-SJ.ARPA (02/20/86)
From: CALENDAR@IBM-SJ.ARPA
[Excerpted from the IBM Calendar by Laws@SRI-AI.]
IBM Almaden Research Center
650 Harry Road
San Jose, CA 95120-6099
Computer LEARNABILITY AND THE VAPNIK-CHERVONENKIS DIMENSION
Science D. Haussler, Department of Mathematics and
Seminar Computer Science, University of Denver
Fri., Feb. 28 The current emphasis on knowledge-based software has
11: 00 A.M. created a broader interest in algorithms that learn
B1-413 knowledge structures or concepts from positive and
negative examples. Using the learning model recently
proposed by Valiant, we have attempted to determine
which classes of concepts have efficient (i.e.,
polynomial time) learning algorithms. As noticed
earlier by Pearl and by Devroye and Wagner, a simple
combinatorial property of concept classes, the
Vapnik-Chervonenkis dimension, plays an important
role in learning and pattern recognition. We clarify
the relationship between this property and Valiant's
theory of learnability. Our results lead to the design
of efficient learning algorithms that employ a
variant of Occam's Razor. Illustrations are given
for certain classes of conjunctive concepts and for
concepts that are defined by various types of regions
in feature space. The work reported was done jointly
with Anselm Blumer, Andrzej Ehrenfeucht and
Manfred Warmuth of the Universities of Denver,
Colorado and California at Santa Cruz, respectively.
Host: B. Simons