A subexponential exact learning algorithm for DNF using equivalence queries

DOI10.1016/0020-0190(96)00077-4MaRDI QIDQ1847366zbMATHOpenAlexFDO

Authors Nader H. Bshouty

Publication date 24 June 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(96)00077-4

zbMATH Keywords

PAC-learning algorithm

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• scientific article; zbMATH DE number 2077165
• Exact learning of DNF formulas using DNF hypotheses
• On the limits of proper learnability of subclasses of DNF formulas
• Learnability of DNF with representation-specific queries
• Fast learning of \(k\)-term DNF formulas with queries.
• On Exact Learning Monotone DNF from Membership Queries
• New bounds for the query complexity of an algorithm that learns DFAs with correction and equivalence queries
• An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
• Proper learning of \(k\)-term DNF formulas from satisfying assignments

Cites work

• A theory of the learnable
• Queries and concept learning
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists

Cited in

(10)

• On PAC learning algorithms for rich Boolean function classes
• Hardness Characterisations and Size-width Lower Bounds for QBF Resolution
• scientific article; zbMATH DE number 5957469 (Why is no real title available?)
• On the limits of proper learnability of subclasses of DNF formulas
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• Solving linear constraints over real and rational fields
• The complexity of properly learning simple concept classes
• Learning Pseudo-Boolean k-DNF and Submodular Functions
• Learning Theory
• Exact learning of DNF formulas using DNF hypotheses

This page was built for publication: A subexponential exact learning algorithm for DNF using equivalence queries

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