Learning Conjunctive Concepts in Structural Domains

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

Machine Learning and Knowledge Acquisition

We study the problem of 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 for samples in which each example (positive or negative) is a two-object scene it is NF-complete to determine if there is any concept in this class that is consistent with the sample. 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 this class is polynomially learnable if we allow a larger hypothesis space. This result holds for any fixed number of objects per scene, but the algorithm is not practical unless the number of objects per scene is very small. We also show that heuristic methods for learning from larger scenes are likely to give an accurate hypothesis if they produce a simple hypothesis consistent with a large enough random sample.