Sparse decision tree optimization has been one of the most fundamental problems in AI since its inception and is a challenge at the core of interpretable machine learning. Sparse decision tree optimization is computationally hard, and despite steady effort since the 1960's, breakthroughs have only been made on the problem within the past few years, primarily on the problem of finding optimal sparse decision trees. However, current state-of-the-art algorithms often require impractical amounts of computation time and memory to find optimal or near-optimal trees for some real-world datasets, particularly those having several continuous-valued features. Given that the search spaces of these decision tree optimization problems are massive, can we practically hope to find a sparse decision tree that competes in accuracy with a black box machine learning model? We address this problem via smart guessing strategies that can be applied to any optimal branch-and-bound-based decision tree algorithm. We show that by using these guesses, we can reduce the run time by multiple orders of magnitude, while providing bounds on how far the resulting trees can deviate from the black box's accuracy and expressive power. Our approach enables guesses about how to bin continuous features, the size of the tree, and lower bounds on the error for the optimal decision tree. Our experiments show that in many cases we can rapidly construct sparse decision trees that match the accuracy of black box models. To summarize: when you are having trouble optimizing, just guess.
翻译:松散的决策树优化是AI 成立以来最根本的问题之一,也是在可解释的机器学习核心中的一项挑战。 粗糙的决策树优化在计算上非常困难, 尽管自1960年代以来做出了稳步的努力, 过去几年里,在这一问题上也只取得了突破, 主要是在寻找最佳的草原决策树的问题上。 然而, 目前的先进算法往往需要不切实际的计算时间和记忆量, 以找到一些真实世界数据集的最佳或接近最佳的树木, 特别是那些具有若干连续价值特征的数据集。 鉴于这些决策树优化问题的搜索空间非常庞大, 我们实际上能否希望找到一棵稀薄的决策树, 与黑盒机器学习模式进行精确竞争? 我们通过明智的猜测来解决这个问题, 这些策略可以适用于任何最佳的分支和有限制的决策树的算法。 我们通过这些猜测, 我们可以将运行的时间减少多个数量, 并且提供由此产生的树木可以偏离黑盒准确度和直观能力的界限。 我们的方法让我们可以猜想出如何在最精确的树上建立最精确的试验, 。