Lower bounds on learning decision lists and trees
From MaRDI portal
Publication:1917100
DOI10.1006/inco.1996.0040zbMath0856.68121OpenAlexW2011295201MaRDI QIDQ1917100
Tao Jiang, Thomas R. Hancock, John Tromp, Ming Li
Publication date: 3 July 1996
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1996.0040
Related Items
Learning optimal decision trees using constraint programming ⋮ On domain-partitioning induction criteria: worst-case bounds for the worst-case based ⋮ On the hardness of approximating the minimum consistent OBDD problem ⋮ Self-improved gaps almost everywhere for the agnostic approximation of monomials ⋮ SAT-based optimal classification trees for non-binary data ⋮ Approximating optimal binary decision trees ⋮ Multi-label feature ranking with ensemble methods ⋮ Measuring teachability using variants of the teaching dimension ⋮ Minimization of decision trees is hard to approximate ⋮ PAC Learning under Helpful Distributions ⋮ Monotone term decision lists ⋮ Unnamed Item ⋮ The ordered covering problem ⋮ Decision lists and related Boolean functions ⋮ Learning Optimal Decision Sets and Lists with SAT
