[mod.ai] Seminar - Boolean Concept Learning

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.