Properly learning decision trees in almost polynomial time
From MaRDI portal
Publication:6551255
DOI10.1145/3561047MaRDI QIDQ6551255
Guy Blanc, Jane Lange, Li-Yang Tan, Mingda Qiao
Publication date: 6 June 2024
Published in: Journal of the ACM (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Selection of relevant features and examples in machine learning
- Rank-\(r\) decision trees are a subclass of \(r\)-decision lists
- Constructing optimal binary decision trees is NP-complete
- Sharp phase transition for the random-cluster and Potts models via decision trees
- Learning decision trees from random examples
- Learning functions of \(k\) relevant variables
- Lower bounds on learning decision lists and trees
- Approximating optimal binary decision trees
- Minimization of decision trees is hard to approximate
- Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem
- Weakly learning DNF and characterizing statistical query learning using Fourier analysis
- Learning Monotone Decision Trees in Polynomial Time
- Learning Decision Trees Using the Fourier Spectrum
- Analysis of Boolean Functions
- Learning and Smoothed Analysis
- Beyond the low-degree algorithm: mixtures of subcubes and their applications
- FINDING SMALL EQUIVALENT DECISION TREES IS HARD
- Decision tree approximations of Boolean functions
This page was built for publication: Properly learning decision trees in almost polynomial time
