A formal study of learning via queries

DOI10.1007/BFB0032028MaRDI QIDQ4038688zbMATH OpenFDO

Authors Osamu Watanabe

Publication date 18 May 1993

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0032028

zbMATH Keywords

bounded learningcomputational complexity of learning problemscomputational power of polynomial time lemmasexact learninglearning systempolynomial time learnabilityrepetitive setsrepresentation classstructure of complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)

Review text

[For the entire collection see Zbl 0758.00017.] The subject of the paper is (i) to establish a formal framework in order to investigate polynomial time learnability for a given representation class and (ii) to demonstrate one approach, namely structural approach, for studying polynomial time learnability.

Recommendations

• A framework for polynomial-time query learnability
• Structural analysis of polynomial-time query learnability
• The consistency dimension and distribution-dependent learning from queries.
• Queries and concept learning
• How many queries are needed to learn?

Cited in

(16)

• The query complexity of learning DFA
• Exact learning via teaching assistants
• Learning elementary formal systems with queries.
• A general comparison of language learning from examples and from queries
• scientific article; zbMATH DE number 67621 (Why is no real title available?)
• A framework for polynomial-time query learnability
• Structural analysis of polynomial-time query learnability
• scientific article; zbMATH DE number 1946973 (Why is no real title available?)
• scientific article; zbMATH DE number 2068174 (Why is no real title available?)
• On the complexity of small description and related topics
• Algorithmic Learning Theory
• New Computational Paradigms
• Algorithmic Learning Theory
• Monotone term decision lists
• The complexity of learning minor closed graph classes
• On learning from queries and counterexamples in the presence of noise

This page was built for publication: A formal study of learning via queries

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