Rank-\(r\) decision trees are a subclass of \(r\)-decision lists

DOI10.1016/0020-0190(92)90237-PzbMath0773.68059MaRDI QIDQ1198056

Avrim L. Blum

Publication date: 16 January 1993

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

zbMATH Keywords

decision treesmachine learningdecision lists

Mathematics Subject Classification ID

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

Related Items (9)

Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ On (simple) decision tree rank ⋮ Linear threshold functions in decision lists, decision trees, and depth-2 circuits ⋮ Submodular goal value of Boolean functions ⋮ A syntactic characterization of bounded-rank decision trees in terms of decision lists ⋮ Extremal properties of polynomial threshold functions ⋮ A subexponential exact learning algorithm for DNF using equivalence queries ⋮ On the isomorphism problem for decision trees and decision lists

Cites Work

• Unnamed Item
• Some special Vapnik-Chervonenkis classes
• Learning decision trees from random examples
• A theory of the learnable

This page was built for publication: Rank-\(r\) decision trees are a subclass of \(r\)-decision lists