On the Optimality of Trees Generated by ID3
This work addresses a long-standing gap in theoretical analysis for a widely used algorithm in machine learning, potentially leading to better practical guarantees for decision tree algorithms.
The paper tackles the problem of understanding the theoretical optimality of ID3 decision tree algorithms by introducing a new metric called mean iteration statistical consistency (MIC), showing that the TopDown variant achieves near-optimal MIC for learning read-once DNFs under product distributions, while another variant does not.
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.