用快速更新方法让可解释的分段线性回归树更快更准
CLARITree: Cholesky and Lookahead Accelerations for Regression with Interpretable Piecewise Linear Trees
- 结合前瞻搜索与矩阵更新技术加速建树
- 比现有方法快得多，预测精度和稀疏性也更好
- 适合需要可解释性和高效计算的场景
回归树是机器学习中最具可解释性且表达能力强的模型之一。传统上，贪婪算法是构建高性能回归树的主要方法。尽管存在基于动态规划和分支定界等最优方法，但其计算开销过大，难以应用于一般线性回归树，即便这些方法通常显著优于贪婪策略。最近工作表明，特定的前瞻策略可大幅提高运行效率并保持接近最优性能，主要在分类任务中。本文提出一种新算法，用于构建近最优、稀疏的分段线性回归树，结合前瞻式搜索策略与高效的秩一Cholesky更新机制。我们从理论和实证两方面证明，该方法在计算效率、预测精度和稀疏性之间取得良好平衡，并显著优于当前最先进方法。
原文摘要 · Abstract (English)
Regression trees are among the most interpretable yet expressive model classes in machine learning. Historically, greedy induction has been the dominant approach for constructing well-performing regression trees. While optimal methods based on dynamic programming and branch-and-bound exist, they are computationally prohibitive for general linear regression trees, despite often achieving substantially better performance than greedy approaches. Recent work has shown that specialized lookahead strategies can dramatically improve runtime while maintaining near-optimal performance, primarily in classification settings. In this work, we develop a novel algorithm for near-optimal, sparse, piecewise linear regression trees that combines a lookahead-style search strategy with efficient rank-one Cholesky updates of the Gram matrix. We demonstrate, both theoretically and empirically, that our method achieves a favorable trade-off between computational efficiency, predictive accuracy, and sparsity, and scales significantly better than the current state of the art.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。