用于混合可解释性的多阶段延迟树：若初试未成，再树一次

# 多阶段推迟树：混合可解释性 —— 如果一开始不成功，那就再树一次  
来源：https://arxiv.org/html/2606.30995  

Zakk Heile  
计算机科学系  
杜克大学  
达勒姆，美国  
zakk\.heile@duke\.edu  

&Hayden McTavish\(^1\)  
计算机科学系  
杜克大学  
达勒姆，美国  
hayden\.mctavish@duke\.edu  

&Margo Seltzer  
计算机科学系  
不列颠哥伦比亚大学  
温哥华，加拿大  
mseltzer@cs\.ubc\.ca  

&Cynthia Rudin  
计算机科学系  
杜克大学  
达勒姆，美国  
cynthia@cs\.duke\.edu  

###### 摘要  
近期研究表明，经过充分优化的单棵决策树在某些场景（主要是噪声领域）中能够与复杂黑箱模型媲美。然而，在其他场景中，复杂的集成树组合通常以牺牲可解释性为代价获得更高精度，迫使从业者在精度-可解释性权衡中做出艰难建模决策。理想情况下，我们希望用一棵或少量树对尽可能多的数据进行分类，在保持最先进精度的同时，为大多数样本提供可解释性。本文引入*多阶段推迟树（MDT）*：一系列稀疏决策树，每棵树对大多数样本做出预测，同时将一小部分样本推迟到序列中的下一棵树，或最终推迟到黑箱模型。我们证明，可以训练此类模型以匹配复杂树集成模型的性能，同时仅通过一棵或少量稀疏决策树路由大多数样本。我们讨论了一系列在保持简洁性的同时训练这些模型的技术。我们的方法扩展了单棵树方法仍不足的场景下的精度-可解释性前沿，表明即使需要复杂模型，它们也不必完全不可解释。  

## 1 引言  
可解释机器学习的一个核心挑战是构建与最先进预测性能相匹配的可解释模型。经过良好优化的简单模型（如最优稀疏树）在特定场景（例如数据由噪声过程生成 [65 (https://arxiv.org/html/2606.30995#bib.bib48), 64 (https://arxiv.org/html/2606.30995#bib.bib47), 9 (https://arxiv.org/html/2606.30995#bib.bib49)]）下能够实现这一目标。在这种情况下，精度-可解释性差距并未显现。然而，在该范式之外的数据集上仍存在此类差距。缩小精度-可解释性差距的一个方向是使用混合或部分可解释模型 [70 (https://arxiv.org/html/2606.30995#bib.bib2), 71 (https://arxiv.org/html/2606.30995#bib.bib1), 57 (https://arxiv.org/html/2606.30995#bib.bib3), 23 (https://arxiv.org/html/2606.30995#bib.bib4), 26 (https://arxiv.org/html/2606.30995#bib.bib44), 35 (https://arxiv.org/html/2606.30995#bib.bib52)]。目标是学习一个简单的可解释模型，对于每个样本，该模型要么做出预测，要么将预测推迟给黑箱模型。通过指定由黑箱分类的样本比例（推迟率），用户可以在匹配黑箱精度与为更多样本保持决策可解释性之间进行权衡。虽然混合可解释模型为应对精度与可解释性之间的折中提供了平滑方式，但现有方法在不推迟绝大多数样本的情况下，往往难以保持黑箱精度。  

参见图注  
图1：自行车数据集上MDT的示例。该模型由两个阶段组成，每个阶段都有有界深度。第一阶段中有两个叶子节点推迟到第二阶段，第二阶段中有三个叶子节点推迟到黑箱（此处为XGBoost模型）。可解释组件共有13个叶子节点。  

我们提出一种基于树的混合可解释模型，该模型在匹配更复杂集成模型性能的同时最小化推迟率。为了学习该模型，我们迭代地聚焦于简单模型证明无法像黑箱模型那样表现良好的数据子集。这催生了一个新的模型类*多阶段推迟树（MDT）*，其中每棵树可以做出预测或推迟到下一阶段；如果需要，最终阶段可以将一些样本推迟到黑箱模型。为了训练MDT，我们引入了一种交替优化过程，在此过程中，被推迟的模型随着MDT的每个阶段而演变。随着这一过程的展开，延期点集单调递减，后续阶段和后备模型变得越来越专用于这些点。这使得模型只需推迟一小部分输入即可保持高精度。当后备模型是稀疏模型（即单棵决策树或EBM [37 (https://arxiv.org/html/2606.30995#bib.bib111)]）时，即使这些推迟情况也保持可解释性；当后备模型是黑箱时，可以在最小化对该模型依赖的同时匹配性能。关键的是，由于推迟点局限于特征空间中一个紧密约束的区域，后备模型可以被压缩，从而产生更简单但等效的复杂集成表示。  

我们的贡献如下。  

- •我们引入了多阶段推迟树（MDT），一种新的模型类，根据特征空间不同区域的难度自适应地分配复杂度。  
- •我们开发了一种用于训练MDT的迭代算法，该算法逐步缩小推迟区域，同时从周围区域借用信息，以学习泛化良好的专用树。  
- •我们提供了将MDT压缩为稀疏单棵树或规则列表表示的算法，并扩展了这一框架以在后备模型是树或树集成时对其进行压缩。  
- •我们证明了在存在此类权衡的地方，改进了精度-推迟-稀疏性权衡。  

## 2 相关工作  
##### 混合方法  
Wang [71 (https://arxiv.org/html/2606.30995#bib.bib1)] 引入了用于可解释性的混合模型：一个可解释的规则集或线性模型对部分数据做出预测，同时将剩余数据推迟到固定的黑箱预测。这允许用户在模型精度与使用可解释模型预测的样本量之间进行权衡。该框架进而与延迟模型 [38 (https://arxiv.org/html/2606.30995#bib.bib12), 47 (https://arxiv.org/html/2606.30995#bib.bib13)]、拒绝学习 [13 (https://arxiv.org/html/2606.30995#bib.bib17), 62 (https://arxiv.org/html/2606.30995#bib.bib54)]、选择性分类 [19 (https://arxiv.org/html/2606.30995#bib.bib24)] 以及基于弃权的学习 [63 (https://arxiv.org/html/2606.30995#bib.bib55), 25 (https://arxiv.org/html/2606.30995#bib.bib23)] 等相关工作相联系。混合模型主要应用于简单的规则集模型或线性模型 [26 (https://arxiv.org/html/2606.30995#bib.bib44), 23 (https://arxiv.org/html/2606.30995#bib.bib4), 71 (https://arxiv.org/html/2606.30995#bib.bib1), 57 (https://arxiv.org/html/2606.30995#bib.bib3), 70 (https://arxiv.org/html/2606.30995#bib.bib2)]。最近的一项研究探索了一种基于梯度的方法，以学习一个复杂（100-1000个叶子节点）的决策树，该树根据到决策边界的接近度推迟到黑箱 [35 (https://arxiv.org/html/2606.30995#bib.bib52)]；相比之下，我们的工作学习一个更稀疏的树序列，这些树直接在最需要黑箱的地方推迟，并逐步缩小这一推迟区域。  

##### 决策树优化  
决策树经典地通过高度可扩展的贪婪算法进行优化 [10 (https://arxiv.org/html/2606.30995#bib.bib20), 58 (https://arxiv.org/html/2606.30995#bib.bib29)]。此类算法非常适合由许多树组成的流行集成模型 [11 (https://arxiv.org/html/2606.30995#bib.bib18), 12 (https://arxiv.org/html/2606.30995#bib.bib11)]。然而，近期的研究重新审视了使用可扩展性较差但质量更高的单棵树算法，以减少对这种模型复杂度的需求，并允许在需要可解释性的领域使用单个性能良好的稀疏树分类器。近年来，对于有界深度和稀疏性，单棵树的全局优化已变得相当可处理 [1 (https://arxiv.org/html/2606.30995#bib.bib28), 30 (https://arxiv.org/html/2606.30995#bib.bib33), 17 (https://arxiv.org/html/2606.30995#bib.bib21), 36 (https://arxiv.org/html/2606.30995#bib.bib42), 43 (https://arxiv.org/html/2606.30995#bib.bib34), brița2025optimal, 6 (https://arxiv.org/html/2606.30995#bib.bib26), 68 (https://arxiv.org/html/2606.30995#bib.bib27)]。然而，这个问题本质上是NP困难的，并且在涉及许多特征的情况下确实难以扩展。最近的研究牺牲了全局最优性，以换取改进的可扩展性和运行时间，同时保持接近最优的性能 [3 (https://arxiv.org/html/2606.30995#bib.bib37), 7 (https://arxiv.org/html/2606.30995#bib.bib32), 32 (https://arxiv.org/html/2606.30995#bib.bib39)]。其他方法增加了任何时间行为，允许提前终止并获得高质量解决方案 [33 (https://arxiv.org/html/2606.30995#bib.bib30), 16 (https://arxiv.org/html/2606.30995#bib.bib31), 34 (https://arxiv.org/html/2606.30995#bib.bib40)]。我们拟合了一小段树序列，其性能几乎与显著更复杂的集成模型相匹配。由于MDT仅依赖少量稀疏树，我们可以比标准贪婪树归纳更仔细地优化每个组件树，同时要求整个过程具有可扩展性。鉴于这种对更高质量组件树和可扩展性的需求，我们使用了来自Babbaret al. [3 (https://arxiv.org/html/2606.30995#bib.bib37)] 的多项式时间 LicketySPLIT 算法的一个版本，我们对其进行了修改以支持样本权重和推迟；我们的理论提供了当每个组件树相对于误分类错误、推迟率和树复杂度恰好最优时所能实现的保证。许多接近最优的决策树算法（包括 LicketySPLIT）操作于二值化特征，这些特征通常使用 ThresholdGuessing [44 (https://arxiv.org/html/2606.30995#bib.bib9)] 构建；我们使用相同的二值化方法。  

##### 压缩树集成  
Vidal 和 Schiffer [69 (https://arxiv.org/html/2606.30995#bib.bib5)] 提出了一种算法，用于找到与给定树集成模型具有相同0-1预测行为（尽管不一定相同的预测概率）的最稀疏单棵决策树。他们还提供了实际松弛以便更快计算（移除树是最稀疏等效形式的证明）或更稀疏的表示（在训练数据中无支持的区域内提供额外剪枝）。Sagi 和 Rokach [59 (https://arxiv.org/html/2606.30995#bib.bib10)] 将 XGBoost 树集成 [12 (https://arxiv.org/html/2606.30995#bib.bib11)] 转换为单棵树，并带有一些近似损失。McTavishet al. [44 (https://arxiv.org/html/2606.30995#bib.bib9)] 采用了一种略有不同的方法，当提供树集成模型时学习单棵树，利用集成模型的预测对搜索空间进行启发式剪枝，从而得到否则将是全局最优的树。这三种方法在提供集成模型时都提供了更可解释的单棵树替代方案，尽管为了匹配该集成的性能，这些方法经常发现具有比可解释性理想情况更多叶子节点的树。在我们自己的算法的混合组件中，我们以与上述方法根本不同的方式合并来自黑箱模型的信息。我们的目标不是精确匹配黑箱模型的预测，也不是加速最优树搜索；相反，我们的目标是使用黑箱来解决可解释算法无法为数据子空间找到准确简单模型的问题；这使我们能够在数据的大部分区域找到透明的模型，同时不牺牲相对于黑箱的有意义精度。虽然我们讨论了当黑箱是基于树的集成时的几个有用属性，但我们的方法继承了混合模型的更通用属性，并且可以与任何黑箱模型一起工作，因为训练所需的只是重新训练模型并获得其在数据集上的预测向量。一旦我们识别出为其推迟到黑箱的点集，如果我们的黑箱是树集成，就可以应用这些压缩方法中的任何一种，专注于模型推迟的数据子集（甚至应用近似压缩方法，例如Devoset al. [18 (https://arxiv.org/html/2606.30995#bib.bib6)] 提出的方法）。这可以进一步改善树的可解释性，同时将任务范围简化为那些我们知道需要使用压缩而不是学习简单模型的子空间。  

## 3 方法论  
##### 符号。
令 X⊆Rp\mathcal{X}\subseteq\mathbb{R}^{p} 表示具有 pp 个特征的输入空间，令 Y={0,1}\mathcal{Y}=\{0,1\} 表示标签空间。训练数据记为 D={(xi,yi)}i=1N⊆X×Y\mathcal{D}=\{(x_{i},y_{i})\}_{i=1}^{N}\subseteq\mathcal{X}\times\mathcal{Y}。当数据具有权重时，我们将数据集记为 Dw\mathcal{D}^{w}，其中权重向量 w∈R≥0Nw\in\mathbb{R}_{\geq 0}^{N}。我们用 1{⋅}\mathds{1}\{\cdot\} 表示指示函数。对于一棵二叉决策树 TT，令 |T||T| 表示其叶子节点数量，令 T(x)T(x) 表示树 TT 对输入 xx 预测的标签。标准的二叉决策树通过内部布尔分裂节点递归划分 X\mathcal{X}，并在每个叶子节点处分配一个预测。我们将此对象泛化，允许叶子节点输出一个类标签或一个特殊的“推迟”动作，表明预测应推迟到后续模型。  

###### 定义 1（推迟树）。 
一棵*推迟树* TT 是一棵二叉决策树，其叶子节点用 Y∪{defer}\mathcal{Y}\cup\{\mathrm{defer}\} 中的元素标记。对于某个后备模型 B，推迟树的预测为：  
 y^T,B(x)={T(x),if T(x)≠defer,B(x),otherwise.\hat{y}_{T,B}(x)=\begin{cases}T(x),&\text{if }T(x)\neq\mathrm{defer},\\[4.0pt] B(x),&\text{otherwise}.\end{cases}  
对于固定的后备模型 BB，我们可以通过优化由 LT,B\mathcal{L}_{T,B} 定义的目标函数来训练单个推迟树 TT：  
 LT,B(Dw,τ,η)=τ(|T|−1)+∑i=1Nwi(1{y^T,B(xi)≠yi}+η1{T(xi)=defer}),\mathcal{L}_{T,B}(\mathcal{D}^{w},\tau,\eta)=\tau\,(|T|-1)+\sum_{i=1}^{N}w_{i}\,(\mathds{1}\{\hat{y}_{T,B}(x_{i})\neq y_{i}\}+\eta\mathds{1}\{\{T(x_{i})=\mathrm{defer}\}\}),  
其中超参数 τ\tau 惩罚树中的分裂数量，η\eta 惩罚推迟到黑箱模型 BB，ww 表示数据集 D\mathcal{D} 的样本权重。我们使用修改版的 LicketySPLIT [3 (https://arxiv.org/html/2606.30995#bib.bib37)] 优化此目标；细节见附录 D.2 (https://arxiv.org/html/2606.30995#A4.SS2)。  

单个推迟树可以通过将困难样本推迟到黑箱来改善完全可解释模型的准确性。然而，那些被推迟的样本正是原始问题仍未解决的地方。在该子集上，我们仍然依赖黑箱，我们希望在那里也恢复可解释性。在该区域上进一步生长树似乎很自然，但如果最初的推迟树已经最优，这就不再可能。最优推迟树带有排除进一步改进的证明：任何用可解释预测替换推迟的尝试都不可行。