We introduce a new algorithm building an optimal dyadic decision tree (ODT). The method combines guaranteed performance in the learning theoretical sense and optimal search from the algorithmic point of view. Furthermore it inherits the explanatory power of tree approaches, while improving performance over classical approaches such as CART/C4.5, as shown on experiments on artificial and benchmark data.
Bibliographical noteFunding Information:
Acknowledgments This work is partly funded by an grant of the Alexander von Humboldt Foundation, the PASCAL Network of Excellence (EU # 506778), and the Bundesministerium für Bildung und Forschung FKZ 01—BB02A and FKZ 01-SC40A. The authors thank Mikio Braun for valuable discussions, Nicolas Heefl for helping us with automatic tree drawing, and Alexander Binder for running the experiments again in Section 4.2 for the revision of the paper.
- Adaptive convergence rate
- Decision tree
- Density estimation
- Oracle inequality
ASJC Scopus subject areas
- Artificial Intelligence