caa a22 4500 467947554 CHVBK 20180323165701.0 cr unu---uuuuu 170328e19891001xx s 000 0 eng 10.1007/BF00114802 doi (NATIONALLICENCE)springer-10.1007/BF00114802 (NATIONALLICENCE)springer-10.1023/A:1022601210986 Haussler David Department of Computer Science, University of California, 95064, Santa Cruz, CA, USA aut Learning conjunctive concepts in structural domains [Elektronische Daten] [David Haussler] 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 NP-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 of space approach and how it shows that it is unlikely that this class of concepts is polynomially learnable from random examples alone in the PAC framework of Valiant. On the other hand, we show that for any fixed bound on the number of objects per scene, this class is polynomially learnable if, in addition to providing random examples, we allow the learning algorithm to make subset queries. In establishing this result, we calculate the capacity of the hypothesis space of conjunctive concepts in a structural domain and use a general theorem of Vapnik and Chervonenkis. This latter result can also be used to estimate a sample size sufficient for heuristic learning techniques that do not use queries. Kluwer Academic Publishers, 1989 concept learning nationallicence PAC learning nationallicence empirical learning nationallicence VC dimension nationallicence version spaces nationallicence structural domains nationallicence conjunctive concepts nationallicence Machine Learning Kluwer Academic Publishers 4/1(1989-10-01), 7-40 0885-6125 4:1<7 1989 4 10994 https://doi.org/10.1007/BF00114802 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF00114802 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Haussler David Department of Computer Science, University of California, 95064, Santa Cruz, CA, USA aut NATIONALLICENCE 773 0- Machine Learning Kluwer Academic Publishers 4/1(1989-10-01), 7-40 0885-6125 4:1<7 1989 4 10994 NATIONALLICENCE 856 40 https://doi.org/10.1023/A:1022601210986 text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Haussler David Department of Computer Science, University of California, 95064, Santa Cruz, CA, USA aut NATIONALLICENCE 773 0- Machine Learning Kluwer Academic Publishers-Plenum Publishers 4/1(1989-10-01), 7-40 0885-6125 4:1<7 1989 4 10994 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE NATIONALLICENCE NL-springer