ArborEnum：连续特征上的决策树 Rashomon 集

# ArborEnum: 面向连续特征的决策树Rashomon集合

来源：https://arxiv.org/html/2608.04310

###### 摘要
Rashomon效应描述了这样一种现象：在同一个学习任务上，许多模型可以达到几乎相同的性能，这对鲁棒性、特征重要性和可定制性具有重要影响。这些用例促使人们计算Rashomon集合：即所有正则化损失接近最优的模型的集合。决策树是少数能够完全枚举Rashomon集合的模型类别之一，但这一计算始终依赖于对原始数据的二值化，要么限制每棵树允许进行的分裂，要么大幅增加本已困难的组合问题的复杂度。我们提出了第一个在利用连续特征有序结构的同时精确枚举决策树Rashomon集合的算法。我们进一步开发了一种用于近似枚举的松弛方法，以及一种随时（anytime）算法，它逐步细化候选阈值集合，产生越来越详细的近似结果，并最终收敛到连续特征Rashomon集合。实验表明，粗糙的二值化可能会遗漏许多树、重要特征和预测多重性；我们的算法比现有枚举方法快几个数量级，同时近似方法在保持近乎完美召回率的基础上提供进一步的加速。我们方法的代码ArborEnum可在 https://github.com/zakk-h/ArborEnum 获取。

## 1 引言
对于许多预测问题而言，并不存在唯一的最佳模型。相反，许多不同的模型常常能达到几乎相同的预测性能。这一现象被称为Rashomon效应(Breiman1984 (https://arxiv.org/html/2608.04310#bib.bib106))，并促使人们研究Rashomon集合(Fisheret al.2019 (https://arxiv.org/html/2608.04310#bib.bib155))：即目标值在给定最优容忍范围内的模型集合。Rashomon集合方法并非只返回一个模型，而是展现所有高性能备选模型的完整集合。Rashomon集合已在多种模型类别中得到研究，包括决策树(Xinet al.2022 (https://arxiv.org/html/2608.04310#bib.bib126))、规则列表(Ciaperoniet al.2024 (https://arxiv.org/html/2608.04310#bib.bib110))、广义加性模型(Zhonget al.2023 (https://arxiv.org/html/2608.04310#bib.bib112))以及原型部分卷积神经网络(Donnellyet al.2025 (https://arxiv.org/html/2608.04310#bib.bib157))。本工作聚焦于寻找决策树的Rashomon集合。

现存的决策树Rashomon集合算法(Heileet al.2026 (https://arxiv.org/html/2608.04310#bib.bib156); Arslanet al.2025 (https://arxiv.org/html/2608.04310#bib.bib131); Babbaret al.2025 (https://arxiv.org/html/2608.04310#bib.bib105); Xinet al.2022 (https://arxiv.org/html/2608.04310#bib.bib126))在处理一组二值特征的前提下解决这一问题。因此，连续特征通常必须在计算Rashomon集合之前进行粗糙的二值化。即便如此，搜索空间依然巨大。Huet al. (2019 (https://arxiv.org/html/2608.04310#bib.bib29)) 表明，仅含20个二值特征的深度为4的决策树搜索空间大小约为8.4×10^18棵树。对于某些连续特征，需要考虑的切分点多达数千个。因此，现有方法无法扩展到这一重要问题。

我们引入了ArborEnum（Algorithms for Relaying Bounds for Ordered Rashomon ENUMeration），这是首个专为在连续特征上枚举决策树Rashomon集合而设计的框架。ArborEnum将原先用于寻找单一最优树的阈值界(brița2025optimal)调整为枚举目标值落在给定界内的树。我们利用这些界将已评估阈值的信息传播到邻近阈值，从而高效剪枝大范围的候选分裂。ArborEnum可以最优或近似地计算这些界所需的信息。在前一种情况下，ArborEnum精确枚举连续特征Rashomon集合；在后一种情况下，它产生适用于精确枚举仍过于昂贵的场景的近似变体，实现了270×的中位加速(Table6 (https://arxiv.org/html/2608.04310#A5.T6))。对于即使高质量近似仍计算量巨大的数据集，我们提出了一种随时算法，逐步细化二值化，并在运行完成时收敛到精确Rashomon集合。这些方法由一种改进的Rashomon集合表示支持，该表示降低了运行时和内存占用，同时可能提高近似质量。在我们的实验中，精确枚举在多数数据集上可行，而在更困难的实例上，我们的近似方法能以一小部分代价恢复几乎所有的树。我们进一步表明，考虑连续阈值对下游分析非常重要：粗糙的二值化可能遗漏Rashomon集合中的预测多重性、重要变量和高质量树，这促使我们尽可能在计算可行的范围内使用随时算法细化二值化。

## 2 相关工作

#### 贪心树与最优树。
决策树是应用最广泛的可解释模型类别之一，CART(Breiman1984 (https://arxiv.org/html/2608.04310#bib.bib106))和C4.5(Quinlan2014 (https://arxiv.org/html/2608.04310#bib.bib18))等经典算法提供了可扩展的自顶向下拟合流程。这些方法贪心地选择分裂，计算效率高，但不具有任何最优性保证。近期大量工作研究了最优决策树，包括我们考虑的误分类误差加每叶惩罚的优化设置。尽管该问题是NP难的，基于混合整数规划、动态规划、缓存和分支定界的专门方法已使在多数数据集上找到有界大小的最优树成为可能(Huet al.2019 (https://arxiv.org/html/2608.04310#bib.bib29); Linet al.2020 (https://arxiv.org/html/2608.04310#bib.bib37); Aglinet al.2020 (https://arxiv.org/html/2608.04310#bib.bib123); Demirovićet al.2022 (https://arxiv.org/html/2608.04310#bib.bib19); van der Lindenet al.2023 (https://arxiv.org/html/2608.04310#bib.bib122))。这些方法可以理解为在AND/OR图上进行搜索，其中OR节点对应分裂选择，AND节点对应左右子解的组合(Sullivanet al.2024 (https://arxiv.org/html/2608.04310#bib.bib115); Chaoukiet al.2025 (https://arxiv.org/html/2608.04310#bib.bib116))。正是这种结构使先前工作可以紧凑地存储Rashomon集合(Heileet al.2026 (https://arxiv.org/html/2608.04310#bib.bib156); Arslanet al.2025 (https://arxiv.org/html/2608.04310#bib.bib131); Xinet al.2022 (https://arxiv.org/html/2608.04310#bib.bib126))。

#### 二值化方法。
将二值特征树优化方法应用于连续数据的一种常见方式是使用少量阈值对每个连续特征进行二值化，这些阈值通常由经验分位数确定；例如，Babbaret al. (2025 (https://arxiv.org/html/2608.04310#bib.bib105)) 对每个特征使用三个分位阈值。阈值猜测(McTavishet al.2022 (https://arxiv.org/html/2608.04310#bib.bib114))则训练诸如XGBoost的参考集成，提取候选阈值，并使用后向消除保留少量高质量分裂。虽然这对寻找单一最优树有效，但不太适用于Rashomon集合，因为后者的目标是刻画许多好模型。

#### 处理连续特征。
近期工作将这些思想扩展到连续特征(brița2025optimal; Kiossouet al.2026 (https://arxiv.org/html/2608.04310#bib.bib33))。Mazumderet al. (2022 (https://arxiv.org/html/2608.04310#bib.bib30)) 通过在每个特征的区间上进行分支定界，并使用基于分位数的上下界来剪枝不可能包含最优树的候选阈值范围，从而处理连续特征。然而，他们只关注深度为2或3的树，因为该算法无法扩展到更深的树。brița2025optimal也直接在连续特征上优化分类树，使用的界更宽松但计算成本更低。

#### 近似算法。
对于本工作中的近似算法，我们基于Heileet al. (2026 (https://arxiv.org/html/2608.04310#bib.bib156))，该工作使用快速代理算法验证Rashomon预算内的可行补全，并剪枝代理补全目标超过该界的分支。由于预算是相对于代理目标设置的，这种剪枝规则不会过于激进；事实上，当代理最优性差距在根节点处最大时，它永远不会出错。我们的近似算法通过新的松弛和代理算法将该策略扩展到连续特征。一个重要的代理是LicketySPLIT(Babbaret al.2025 (https://arxiv.org/html/2608.04310#bib.bib105))。在每个子问题上，它贪心地完成每个候选分裂的子节点，选择具有最佳补全正则化目标的分裂，并在由此产生的子问题上递归。我们松弛了LicketySPLIT以使其能在连续特征上高效运行，并将得到的算法命名为“LicketySNIP”，作为我们近似方法中的代理。

## 3 方法
设D表示当前子问题，用训练样本上的位向量表示，设γ为每叶惩罚。设T_d表示训练特征上深度至多为d的轴对齐决策树集合。设Y表示≥2个类别标签的集合。我们按以下公式对树评分：
Obj(T,D,γ) = 误分类数(T;D) + γ · |叶节点(T)|。

我们使用*代理算法*来获取子问题在剩余深度d下T_d中某棵树所达到