2019/04/29 by Xiyang Hu, Cynthia Rudin, Hu, Xiyang +3 · 10 citations
Computer Science · #Data Mining Algorithms and Applications #Explainable Artificial Intelligence (XAI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Data Classification
paper · pdf · doi:10.48550/arxiv.1904.12847
openalex publication_date 2019/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Decision tree algorithms have been among the most popular algorithms for interpretable (transparent) machine learning since the early 1980's. The problem that has plagued decision tree algorithms since their inception is their lack of optimality, or lack of guarantees of closeness to optimality: decision tree algorithms are often greedy or myopic, and sometimes produce unquestionably suboptimal models. Hardness of decision tree optimization is both a theoretical and practical obstacle, and even careful mathematical programming approaches have not been able to solve these problems efficiently. This work introduces the first practical algorithm for optimal decision trees for binary variables. The algorithm is a co-design of analytical bounds that reduce the search space and modern systems techniques, including data structures and a custom bit-vector library. Our experiments highlight advantages in scalability, speed, and proof of optimality. The code is available at https://github.com/xiyanghu/OSDT.