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.