KARP@SUMEX-AIM.STANFORD.EDU (Peter Karp) (07/12/87)
[Forwarded from the AFLB list.] David Haussler from UC Santa Cruz will be giving a talk at the GRAIL learning seminar this Thursday 7/9 at the Welch Road Conference room at 1:15. This is Room A1110 in Building A at 701 Welch Road, across from the Stanford Barn. Learning Conjunctive Concepts in Structural Domains David Haussler Department of Computer Science, University of California, Santa Cruz, CA 95064 We study the problem of inductively learning conjunctive concepts from examples on structural domains like the blocks world. This class of concepts is formally defined and it is shown that even when each example (positive or negative) is a two-object scene it is NP-complete to determine if there is any consistent concept in this class. We demonstrate how this result affects the feasibility of Mitchell's version space approach and how it shows that it is unlikely that this class of concepts is polynomially learnable from random examples in the sense of Valiant. On the other hand, we show that for any fixed number of objects per scene this class is polynomially learnable from random examples if (1) we allow a larger hypothesis space, or (2) we answer cetrain types of queries in addition to providing random examples.