How many queries are needed to learn?

DOI10.1145/234752.234755MaRDI QIDQ4371689zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1263194
• scientific article; zbMATH DE number 1804094
• How many queries are needed to learn one bit of information?
• How Many Query Superpositions Are Needed to Learn?
• scientific article; zbMATH DE number 2086401
• How many missing answers can be tolerated by query learners?
• Learning via queries
• Queries and concept learning
• Learning via finitely many queries
• scientific article; zbMATH DE number 67621

Cited in

(38)

• Complexity theoretic hardness results for query learning
• On the cut-off point for combinatorial group testing
• The query complexity of learning DFA
• Conjunctions of unate DNF formulas: Learning and structure
• How many queries are needed to learn one bit of information?
• Queries revisited.
• Exact learning via teaching assistants
• On the limits of efficient teachability
• A new abstract combinatorial dimension for exact learning via queries
• Exploring learnability between exact and PAC
• The consistency dimension and distribution-dependent learning from queries.
• The query complexity of finding local minima in the lattice
• Learning closed Horn expressions
• Uniform characterizations of polynomial-query learnabilities
• When won't membership queries help?
• Oracles and queries that are sufficient for exact learning
• Complexity parameters for first order classes
• Projective DNF formulae and their revision
• Improved bounds on quantum learning algorithms
• Polynomial certificates for propositional classes
• The subsumption lattice and query learning
• A general dimension for query learning
• From equivalence queries to PAC learning: the case of implication theories
• scientific article; zbMATH DE number 2089366 (Why is no real title available?)
• 10.1162/153244304322972676
• The complexity of exactly learning algebraic concepts
• Canonical Horn representations and query learning
• scientific article; zbMATH DE number 67615 (Why is no real title available?)
• scientific article; zbMATH DE number 177810 (Why is no real title available?)
• Construction and learnability of canonical Horn formulas
• scientific article; zbMATH DE number 1263194 (Why is no real title available?)
• scientific article; zbMATH DE number 1563912 (Why is no real title available?)
• On the exact learnability of graph parameters: the case of partition functions
• Exact learning of DNF formulas using DNF hypotheses
• Monotone term decision lists
• The dimension of self-directed learning
• The complexity of learning concept classes with polynomial general dimension
• Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs

This page was built for publication: How many queries are needed to learn?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4371689)