How many queries are needed to learn?

DOI10.1145/234752.234755zbMath0885.68123OpenAlexW2013012666MaRDI QIDQ4371689

Krishnan Pillaipakkamnatt, Dawn Wilkins, Lisa Hellerstein, Vijay Raghavan

Publication date: 22 January 1998

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://www.acm.org/pubs/contents/journals/jacm/1996-43/

zbMATH Keywords

exact learningquery complexity

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items

Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs, A general dimension for query learning, Conjunctions of unate DNF formulas: Learning and structure, Construction and learnability of canonical Horn formulas, Complexity parameters for first order classes, Queries revisited., Projective DNF formulae and their revision, Improved bounds on quantum learning algorithms, Monotone term decision lists, Polynomial certificates for propositional classes, Exact learning of DNF formulas using DNF hypotheses, Canonical Horn Representations and Query Learning, On the cut-off point for combinatorial group testing, Exact learning via teaching assistants, The consistency dimension and distribution-dependent learning from queries., The query complexity of finding local minima in the lattice, Learning closed Horn expressions, The subsumption lattice and query learning, On the limits of efficient teachability, A new abstract combinatorial dimension for exact learning via queries, Uniform characterizations of polynomial-query learnabilities, The complexity of learning concept classes with polynomial general dimension