Branches: A Fast Dynamic Programming and Branch & Bound Algorithm for Optimal Decision Trees

决策树学习是可解释机器学习的基本问题，但它提出了一个巨大的优化挑战。尽管自上世纪90年代初以来进行了许多努力，但实用算法直到最近才出现，主要利用动态规划（DP）和分支限界（B&B）技术。这些突破导致了两种不同的方法的发展。像DL8.5和MurTree这样的算法在节点（或分支）空间上操作，它们非常快，但不惩罚复杂的决策树，即它们不能解决稀疏性。另一方面，像OSDT和GOSDT这样的算法在决策树空间上操作，它们解决稀疏性，但以速度为代价。在这项工作中，我们介绍了Branches，一种将两种范例的优点整合起来的新算法。利用DP和B&B，Branches实现了异常的速度，同时也解决了稀疏性。其效率的核心是一种新的分析界限，可以大幅度剪枝搜索空间。理论分析表明，Branches与最先进的方法相比具有较低的复杂度，这一声明通过广泛的经验评估得到了验证。我们的结果表明，Branches不仅在速度和迭代次数方面大大优于现有方法，而且始终产生最优的决策树。

论文介绍了一种新的Decision Tree Learning算法Branches，旨在解决Decision Tree Learning中速度与稀疏性之间的平衡问题。

Branches算法整合了Dynamic Programming和Branch & Bound技术，通过新的分析界限实现了对搜索空间的大量剪枝，从而在速度和稀疏性方面都取得了优异的表现。

论文通过实验验证了Branches算法在速度和迭代次数方面的优越性，并且在稀疏性方面也表现出色。论文还介绍了算法的理论分析，证明了Branches算法的复杂度比现有方法更低。

在Decision Tree Learning领域，之前的算法主要分为DL8.5、MurTree、OSDT和GOSDT等。