On the Optimality of Trees Generated by ID3

Abstract

Since its inception in the 1980s, ID3 has become one of the most successful and widely used algorithms for learning decision trees. However, its theoretical properties remain poorly understood. In this work, we introduce a novel metric of a decision tree algorithm's performance, called mean iteration statistical consistency (MIC), which measures optimality of trees generated by ID3. As opposed to previous metrics, MIC can differentiate between different decision tree algorithms and compare their performance. We provide theoretical and empirical evidence that the TopDown variant of ID3, introduced by Kearns and Mansour (1996), has near-optimal MIC in various settings for learning read-once DNFs under product distributions. In contrast, another widely used variant of ID3 has MIC which is not near-optimal. We show that the MIC analysis predicts well the performance of these algorithms in practice. Our results present a novel view of decision tree algorithms which may lead to better and more practical guarantees for these algorithms.

References in corpus (4)

• Analysis of a Random Forests Model
• Narrowing the Gap: Random Forests In Theory and In Practice
• Asymptotic Theory for Random Forests
• Decision trees are PAC-learnable from most product distributions: a smoothed analysis

Cited by in corpus (6)

• Efficient Contextual Bandits with Continuous Actions
• Top-down induction of decision trees: rigorous guarantees and inherent limitations
• Connecting Interpretability and Robustness in Decision Trees through Separation
• Universal guarantees for decision tree induction via a higher-order splitting criterion
• Estimating decision tree learnability with polylogarithmic sample complexity
• Decision tree heuristics can fail, even in the smoothed setting