提出SPLIT算法，在保持最优精度的同时实现快速决策树构建。
Near Optimal Decision Trees in a SPLIT Second
- 仅在深层节点使用贪婪策略，浅层保留精确搜索。
- 相比现有最优方法提速数十倍，性能损失可忽略。
- 适合需要高可解释性且对效率敏感的应用场景。
决策树优化是可解释机器学习的核心问题。主流方法采用贪心策略，虽快速但存在理论次优性；近期方法通过分支定界与动态规划求解全局最优，显著提升准确率与稀疏性，但计算成本极高。本文提出SPLIT（SParse Lookahead for Interpretable Trees）算法族，证明并非所有子问题都需精确求解即可获得高质量树：接近叶节点处的贪心策略已足够。由于每加深一层，可能的树结构呈指数增长，此策略使算法速度较现有最优方法提升多个数量级，性能损失微乎其微。进一步扩展该算法，实现近似最优树集合（即Rashomon集）的高效计算。
原文摘要 · Abstract (English)
Decision tree optimization is fundamental to interpretable machine learning. The most popular approach is to greedily search for the best feature at every decision point, which is fast but provably suboptimal. Recent approaches find the global optimum using branch and bound with dynamic programming, showing substantial improvements in accuracy and sparsity at great cost to scalability. An ideal solution would have the accuracy of an optimal method and the scalability of a greedy method. We introduce a family of algorithms called SPLIT (SParse Lookahead for Interpretable Trees) that moves us significantly forward in achieving this ideal balance. We demonstrate that not all sub-problems need to be solved to optimality to find high quality trees; greediness suffices near the leaves. Since each depth adds an exponential number of possible trees, this change makes our algorithms orders of magnitude faster than existing optimal methods, with negligible loss in performance. We extend this algorithm to allow scalable computation of sets of near-optimal trees (i.e., the Rashomon set).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。