Optimal Sparse Decision Trees
Optimal Sparse Decision Trees
复制标题
最优稀疏决策树
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
M. Seltzer
中科院分区：
文献类型：
--
作者：
Xiyang Hu;C. Rudin;M. Seltzer
自20世纪80年代初S以来，决策树算法一直是最受欢迎的可解释(透明)机器学习算法之一。自决策树算法诞生以来，一直困扰着它们的问题是，它们缺乏最优性，或者缺乏接近最优性的保证：决策树算法通常是贪婪或短视的，有时会产生毫无疑问的次最优模型。决策树优化的难度既是理论上的障碍，也是实际中的障碍，即使是精细的数学规划方法也不能有效地解决这些问题。本文介绍了第一个实用的二元变量最优决策树算法。该算法是分析边界的联合设计，减少了搜索空间和现代系统技术，包括数据结构和定制的位向量库。我们的实验突出了在可伸缩性、速度和最优性证明方面的优势。
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.