A subexponential exact learning algorithm for DNF using equivalence queries

DOI10.1016/0020-0190(96)00077-4zbMath1046.68635OpenAlexW2020712580MaRDI QIDQ1847366

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)

Related Items (6)

Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ Solving linear constraints over real and rational fields ⋮ The complexity of properly learning simple concept classes ⋮ Exact learning of DNF formulas using DNF hypotheses

Cites Work

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

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