Lower bounds on learning decision lists and trees

DOI10.1007/3-540-59042-0_102MaRDI QIDQ4596650zbMATH OpenOpenAlexFDO

Authors Thomas R. Hancock, Tao Jiang, John Tromp, Ming Li

Publication date 4 December 2017

Published in STACS 95 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-59042-0_102

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• Lower bounds on learning decision lists and trees
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
• Learning decision trees from random examples
• Learning Theory
• Toward attribute efficient learning of decision lists and parities

Cited in

(15)

• Lower bounds on probabilistic linear decision trees
• Partial Occam's Razor and its applications
• Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
• Research note on decision lists
• Decision lists over regular patterns.
• Lower bounds on learning decision lists and trees
• The complexity of properly learning simple concept classes
• On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
• A syntactic characterization of bounded-rank decision trees in terms of decision lists
• scientific article; zbMATH DE number 2086400 (Why is no real title available?)
• Decision List Compression by Mild Random Restrictions
• On Polynomial Time Constructions of Minimum Height Decision Tree
• Decision tree approximations of Boolean functions
• Simple PAC learning of simple decision lists
• On the equivalence of Occam algorithms

This page was built for publication: Lower bounds on learning decision lists and trees

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