从罗生门理论到PRAXIS：高效决策树罗生门集合

# 从罗生门理论到 PRAXIS：高效决策树罗生门集合  
来源：https://arxiv.org/html/2606.00202  

###### 摘要  

标准机器学习流程通常允许存在许多近最优模型。这些“罗生门集合”为不确定性感知的稳健决策带来了诸多挑战与机遇。它们允许用户融入领域知识和偏好，而这些内容原本很难直接纳入目标函数；同时，它们量化了给定训练数据集和目标函数下有效模型之间的多样性。然而，计算罗生门集合（即便是对于稀疏决策树这类简单可解释模型类）仍然需要巨大的内存和运行时间资源。我们提出 PRAXIS，一种用于近似该罗生门集合的算法，其在运行时间和内存使用上实现了数量级的提升。我们验证了 PRAXIS 通常能够几乎完整地恢复全部罗生门集合。PRAXIS 使得研究人员和实践者能够可扩展地对真实世界数据集的罗生门集合进行建模。PRAXIS 的代码可在 https://github.com/zakk-h/PRAXIS 获得。  

**关键词**：可解释机器学习，罗生门集合，决策树  

## 1 引言  

模型选择在任何机器学习流程中都至关重要。罗生门效应 (Breiman, 1984) 指的是对于给定数据集和目标函数，存在许多可以有效证明的模型。最近一种考虑该效应的模型选择框架是“罗生门集合范式” (Xin et al., 2022; Rudin et al., 2024)，算法首先枚举或表示所有与数据拟合良好的合理模型的集合（即罗生门集合），然后用户与罗生门集合交互，选择最符合其需求的模型。当用户无法事先明确所有目标和约束时，该范式尤其有用。用户可能希望找到一个最大化公平性、遵守因果假设、使用某些特征和/或遵循特定结构约束的模型。一旦罗生门集合被枚举出来，这些建模目标就变得简单了，因为只需要遍历该集合一次即可优化任何次要目标。  

发现罗生门集合的方法取决于所考虑的模型类。例如，广义加性模型（GAM）的罗生门集合可以通过在最优权值向量附近的凸超曲面上采样来高效近似 (Zhong et al., 2023)。然而，对于决策树这样的离散非参数模型类，发现罗生门集合在运行时间和内存上都是一项巨大的计算工程，因为即使寻找一棵最优决策树也是 NP-难的。例如，Hu 等人 (2019b) 指出，仅包含 20 个特征、深度为 4 的决策树的搜索空间大小约为 \(8.4 \times 10^{18}\) 棵树。  

![图1: PRAXIS 与其他罗生门集合算法在 News 数据集上的示意图 (Fernandes et al., 2015b)，λ=0.02, ε=0.03, depth=5。PRAXIS 的运行速度比竞品快多个数量级，同时相对于最优方法保证了近乎完美的召回率。](https://arxiv.org/html/2606.00202/fig1.png)  
**图1**：PRAXIS 与其他罗生门集合算法在 News 数据集上的示意图 (Fernandes et al., 2015b)，λ=0.02, ε=0.03, 深度=5。PRAXIS 的运行速度比竞品快多个数量级，同时相对于最优方法保证了近乎完美的召回率。  

尽管最近有两种算法 (Xin et al., 2022; Arslan et al., 2026) 能够精确发现稀疏决策树的罗生门集合，但其运行时间和内存需求随深度预算和特征数量呈指数级增长。RESPLIT (Babbar et al., 2025) 提供了近似罗生门集合，但近似质量显著下降，且每恢复一棵树的最坏情况时间仍为指数级。我们提出了一系列新的罗生门集合近似算法，每个罗生门集合成员的计算时间为多项式级。我们的算法使用一个代理子程序来评估特征分裂；该子程序高效地计算给定子问题上高质量单棵树的客观值。我们的方法 PRAXIS（Proxy-guided Rashomon set ApproXimatIonS）与现有最优的精确和近似方法相比，在运行时间和内存效率上都实现了数量级的提升，同时仍能几乎完整地恢复罗生门集合。我们的贡献如下：(1) 我们引入了一个新颖、灵活的框架，用于高效近似决策树的罗生门集合。(2) 我们证明了我们的近似方法能够可靠地恢复罗生门集合，并讨论了保证这种恢复的理论条件。(3) 我们证明我们的方法比之前的最先进方法快多个数量级且内存效率更高，并提供了相应的渐近分析。  

## 2 相关工作  

##### 最优单棵树。  
决策树作为可解释、可扩展的分类器已有数十年历史，拥有被广泛引用的实现，如 CART (Breiman, 1984) 和 C4.5 (Quinlan, 2014)。早期的决策树方法是贪婪的，从根节点开始，根据启发式逐个添加分裂，而不回溯检查分裂是否可改进。研究人员通过全局优化性能和稀疏性，以及一系列计算效率技术，显著提高了单棵稀疏决策树的准确性 (Lin et al., 2020; Aglin et al., 2020; Hu et al., 2019a; Demirović et al., 2022; van der Linden et al., 2023; Bertsimas & Dunn, 2017)。最近的一项综述发现，许多最可扩展的方法通过利用树特化的分支定界逻辑和动态规划取得成功 (Costa & Pedreira, 2023)。一些树优化工作观察到，这类树特化方法可以表述为对 AND/OR 图的搜索 (Sullivan et al., 2024; Chaouki et al., 2025)；我们的算法也对应于 AND/OR 图搜索（见附录 B.2）。  

##### 最优罗生门集合。  
有几种寻找最优单棵树的方法可以扩展为寻找所有目标函数值在最优值小倍数范围内的树——即树的罗生门集合 (Xin et al., 2022; Arslan et al., 2026)。还有一些针对树的特殊情况的工作 (Mata et al., 2022; Ciaperoni et al., 2024; Babbar et al., 2026)。捕获罗生门集合的能力使得一系列强大的下游应用成为可能，例如增加鲁棒性 (Hsu et al., 2026)、估计变量重要性 (Donnelly et al., 2023, 2026)，或为领域专家和实践者提供定制化和控制能力 (Rudin et al., 2024)。这些进展意义重大，但难以扩展到更大的实际数据集：它们在内存和运行时间上具有组合复杂性，尤其在数据集的特征数量方面。  

##### 单棵树近似。  
有几种方法通过更好地处理连续特征 (Mazumder et al., 2022; Brița et al., 2025) 或融入精心设计的启发式策略 (McTavish et al., 2022; Blanc et al., 2024; Demirović et al., 2023; Kiossou et al., 2022, 2024; Kiossou & Schaus, 2026)，提高了最优和近似最优决策树算法的可扩展性。与我们工作特别相关的是 LicketySPLIT 算法 (Babbar et al., 2025)。该方法从根节点开始，考虑所有可能的分裂，并基于使用贪婪算法完成树的结果来评估每个分裂。它选择条件于贪婪完成后的最佳初始分裂，然后递归进行。这种分裂选择启发式是一种 rollout 过程 (Bertsekas et al., 1997)；因此，整个 LicketySPLIT 算法属于 pilot 方法类 (Duin & Voß, 1994; Voß et al., 2005)。我们的方法 PRAXIS 可以看作是一种 pilot 方法，但其输出不是单个解，而是一组近最优解。与任何 pilot 方法一样，它使用一个子程序进行启发式完成。为便于命名，我们将这个子程序称为代理方法（定义见 3.1），尽管这个代理可能相当复杂。实证发现，像 LicketySPLIT 这样的单树 pilot 方法的目标函数是一个优秀的代理，既保证了结果的准确性，也保证了缓存效率。  

##### 罗生门集合近似。  
相对较少的工作关注近似罗生门集合的计算优势，因为优化任务的特殊性使其可能很复杂。Babbar 等人 (2025) 提供了 RESPLIT，一种基于贪婪启发式和分支定界搜索混合的可扩展罗生门集合近似。RESPLIT 的优化策略与我们的方法正交：它先最优地求解更简单的子问题，然后近似的组合它们，而我们则直接近似完整问题。此外，一个常用的基线是对数据集进行重复自助抽样，并在每个自助样本上运行单树优化；这在精确决策树罗生门集合的工作中都有探讨 (Arslan et al., 2026; Xin et al., 2022)。两篇论文都发现自助抽样效率低下，会导致遗漏许多罗生门集合成员，无论是在每个自助样本上运行最优方法，还是运行像 CART (Breiman, 1984) 这样的贪婪方法。我们还将我们的方法（PRAXIS）与自助抽样的代理算法（LicketySPLIT）进行了比较，表明我们的方法在近似罗生门集合上效果显著更优。  

## 3 方法论  

### 3.1 符号  

令 \(D = \{(x_i, y_i)\}_{i=1}^n\) 为大小为 \(n\) 的数据集，其中 \(y_i \in \{0,1\}\) 且每个 \(x_i \in \{0,1\}^k\) 具有 \(k\) 个二值特征（可能由连续或分类特征二值化得到）。一棵二值决策树 \(t \in \mathcal{T}\) 是一个函数 \(\{0,1\}^k \to \{0,1\}\)。深度为 0 的树，即叶子节点，对任何样本做出单一预测。其他树具有简单的分裂函数（对于某个 \(j \in [1,k]\)，定义为 \(\text{split}_t(x_i) = x_{ij}\)）以及两个子树 \(t_{\text{left}} \in \mathcal{T}, t_{\text{right}} \in \mathcal{T}\)，满足 \(\text{depth}(t) = 1 + \max(\text{depth}(t_{\text{left}}), \text{depth}(t_{\text{right}}))\)；其返回值为：  
\[
t(x_i) = t_{\text{left}}(x_i) \cdot \text{split}_t(x_i) + t_{\text{right}}(x_i) \cdot (1 - \text{split}_t(x_i)).
\]  
即，树根据查询的特征返回其左子树或右子树的预测。我们用 \(D_t\) 表示数据集 \(D\) 中由树 \(t\) 负责预测的子集；对于根树，这等于 \(D\)，然后递归定义为：  
\[
D_{t_{\text{left}}} = \{(x_i,y_i) \in D_t \mid \text{split}_t(x_i)=1\}, \quad D_{t_{\text{right}}} = \{(x_i,y_i) \in D_t \mid \text{split}_t(x_i)=0\}.
\]  
令 \(|t|\) 表示树 \(t\) 的叶子节点数。我们使用一个同时惩罚错分数量和叶子节点数量的目标函数，惩罚参数为每叶子节点错分惩罚 \(\gamma\)：  
\[
\text{Obj}(t, D, \gamma) = \gamma|t| + \sum_{i=1}^n \mathbb{1}\{t(x_i) \neq y_i\}.
\]  
该目标函数与先前罗生门集合公式 (Xin et al., 2022; Arslan et al., 2026) 类似，后者使用正则化参数 \(\lambda\)；两者通过 \(|D|\) 缩放关联，即 \(\gamma = \lambda |D|\)。在我们的实现中，我们将 \(\gamma\) 约束为整数以避免浮点计算，这对目标函数的表达能力影响极小（在附录 B 中讨论）。  

记 \(\mathcal{T}_d = \{t \in \mathcal{T} \mid \text{depth}(t) \leq d\}\)；对于数据集 \(D\)、深度限制 \(d\) 和惩罚 \(\gamma\)，罗生门集合可定义为：  
\[
\mathcal{R}_{\varepsilon_{\mathrm{abs}}}(D, d, \gamma) := \{t \in \mathcal{T}_d \mid \mathrm{Obj}(t, D, \gamma) \leq \varepsilon_{\mathrm{abs}}\},
\]  
其基数记为 \(|\mathcal{R}_{\varepsilon_{\mathrm{abs}}}(D, d, \gamma)|\)（为简化记法，缩写为 \(|\mathcal{R}_{\varepsilon_{\mathrm{abs}}}|\)）。通常更方便的做法是使用分数容差 \(\varepsilon_{\mathrm{mult}}\) 进行参数化，设置 \(\varepsilon_{\mathrm{abs}} = (1 + \varepsilon_{\mathrm{mult}}) \min_{t \in \mathcal{T}_d} \mathrm{Obj}(t, D, \gamma)\)。  

与先前工作类似，我们维护一个罗生门集合的搜索图表示，算法终止后所有有效树均可从该图枚举得到。附录 B 中的算法 8 和算法 9 分别指定了用于使用新叶子节点或新分裂扩展该图的操作，并填充以该子问题为根的树的最小目标函数值，以便在整个算法中使用。  

### 3.2 代理优化器框架  

我们的目标是高效近似罗生门集合。为此，我们利用代理算法（定义 3.1）作为高效子程序来寻找高质量单棵树。