D. Angluin. Machine Learning, 2 (4):
319--342(1988)
Abstract
We consider the problem of using queries to learn an unknown concept. Several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries. Examples are given of efficient learning methods using various subsets of these queries for formal domains, including the regular languages, restricted classes of context-free languages, the pattern languages, and restricted types of prepositional formulas. Some general lower bound techniques are given. Equivalence queries are compared with Valiant's criterion of probably approximately correct identification under random sampling.
%0 Journal Article
%1 Angluin88
%A Angluin, Dana
%D 1988
%J Machine Learning
%K comparison induction learnability machine_learning pac-learning seminal_paper
%N 4
%P 319--342
%T Queries and Concept Learning
%U http://dx.doi.org/10.1023/A:1022821128753
%V 2
%X We consider the problem of using queries to learn an unknown concept. Several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries. Examples are given of efficient learning methods using various subsets of these queries for formal domains, including the regular languages, restricted classes of context-free languages, the pattern languages, and restricted types of prepositional formulas. Some general lower bound techniques are given. Equivalence queries are compared with Valiant's criterion of probably approximately correct identification under random sampling.
@article{Angluin88,
abstract = {We consider the problem of using queries to learn an unknown concept. Several types of queries are described and studied: membership, equivalence, subset, superset, disjointness, and exhaustiveness queries. Examples are given of efficient learning methods using various subsets of these queries for formal domains, including the regular languages, restricted classes of context-free languages, the pattern languages, and restricted types of prepositional formulas. Some general lower bound techniques are given. Equivalence queries are compared with Valiant's criterion of probably approximately correct identification under random sampling.},
added-at = {2008-12-21T12:06:41.000+0100},
author = {Angluin, Dana},
biburl = {https://www.bibsonomy.org/bibtex/28cccfe7f9218c9ead41b4a0ff87013aa/emanuel},
interhash = {0bb9969adf0b78e6fffcbb595af1a708},
intrahash = {8cccfe7f9218c9ead41b4a0ff87013aa},
journal = {Machine Learning},
keywords = {comparison induction learnability machine_learning pac-learning seminal_paper},
number = 4,
pages = {319--342},
timestamp = {2008-12-21T12:06:41.000+0100},
title = {Queries and Concept Learning},
url = {http://dx.doi.org/10.1023/A:1022821128753},
volume = 2,
year = 1988
}