Marcella.Zaragoza@ISL1.RI.CMU.EDU.UUCP (02/20/87)
THEORY SEMINAR
Lenny Pitt
Wednesday, 25 Feb.
3:30
WeH 5409
Recent results on Boolean concept learning.
Lenny Pitt
U. Illinois at Urbana-Champaign
In "A Theory of the Learnable" (Valiant, 1984), a new formal definition
for concept learning from examples was proposed. Since then a number
of interesting results have been obtained giving learnable classes of
concepts. After motivating and explaining Valiant's definition of
probabilistic and approximate learning, we show that even some
apparently simple types of concepts (e.g. Boolean trees, disjuncts
of two conjuncts) cannot be learned (assuming P not equal NP).
The reductions used suggest an interesting relationship between
learnability problems and the approximation of combinatorial optimization
problems.
This is joint work with Leslie G. Valiant.
This talk will be of interest to both Theory and AI people. To schedule
an appointment to meet with him on Wednesday, send mail to stefanis@g.