提出可随时输出最优树序列的稀疏决策树枚举框架，提升可解释性模型探索效率。
SORTeD Rashomon Sets of Sparse Decision Trees: Anytime Enumeration
- 基于目标值排序的枚举策略，实现任意时间输出高质量树集合。
- 相比现有方法提速达100倍，支持多种可分目标函数的后评估。
- 适合需要灵活解释、公平性或简洁结构的高风险决策场景。
稀疏决策树学习能生成准确且可解释的预测模型，特别适用于高风险场景，通过在（软）规模限制内寻找单一最优树实现。与其依赖单一‘最佳’树，不如利用性能相近但结构各异的Rashomon集——该集合可增强变量重要性分析、丰富解释，并使用户在不硬编码偏好（如公平性）的前提下选择更简单或符合利益相关者需求的树。然而，由于寻找最优树是NP难问题，枚举Rashomon集本身极具挑战。为此，我们提出SORTD新框架，显著提升可扩展性，并按目标值顺序枚举树，实现任意时间行为。实验表明，SORTD相较现有最优方法将运行时间缩短了最高两个数量级。此外，SORTD可对任意可分且全序的目标进行枚举，并支持使用其他可分（部分有序）目标对集合进行后评估。这些进展使在真实场景中探索Rashomon集更加可行。
原文摘要 · Abstract (English)
Sparse decision tree learning provides accurate and interpretable predictive models that are ideal for high-stakes applications by finding the single most accurate tree within a (soft) size limit. Rather than relying on a single "best" tree, Rashomon sets-trees with similar performance but varying structures-can be used to enhance variable importance analysis, enrich explanations, and enable users to choose simpler trees or those that satisfy stakeholder preferences (e.g., fairness) without hard-coding such criteria into the objective function. However, because finding the optimal tree is NP-hard, enumerating the Rashomon set is inherently challenging. Therefore, we introduce SORTD, a novel framework that improves scalability and enumerates trees in the Rashomon set in order of the objective value, thus offering anytime behavior. Our experiments show that SORTD reduces runtime by up to two orders of magnitude compared with the state of the art. Moreover, SORTD can compute Rashomon sets for any separable and totally ordered objective and supports post-evaluating the set using other separable (and partially ordered) objectives. Together, these advances make exploring Rashomon sets more practical in real-world applications.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。