浅层决策树归纳的自适应多分支方法

# 自适应多分支浅层决策树归纳
来源：https://arxiv.org/html/2608.29262  
Hanul Park¹, Jeonghoon Choi¹, Juseong Kim¹, Sanghun Sel¹, Giltae Song¹,²,\*  
所属单位：  
¹ 韩国釜山 釜山大学 信息融合工程学院  
² 韩国釜山 釜山大学 计算机科学与工程学院  
\* 通讯作者：[email protected]  
[email protected], [email protected]  
[email protected], [email protected]  

###### 摘要  
决策树因其可解释性在表格预测任务中备受青睐，因为每次预测都遵循一系列可解释的特征阈值测试。然而，在严格的最大深度预算下，传统的二叉树可能表现力不足，因为每个内部节点仅进行单次阈值决策。我们研究浅层深度树归纳，旨在保持从根到叶路径较短的同时提高预测精度。本文提出**自适应剪枝的多分支神经决策树**（MBNDT），这是一种通过端到端可微分多路划分训练的轴对齐单棵树。每个内部节点在选定特征上学习有序阈值，并通过一个分支掩码自适应其有效分支数；训练完成的模型被转换为确定性的单路径树用于推理。在21个OpenML二分类基准测试中，MBNDT在深度受限的单树基线中实现了最佳的平均排名和平均平衡精度；受控的消融实验表明多路划分是性能提升的主要来源。这些增益伴随着明确的权衡：MBNDT生成的叶子节点数多于其他单树基线，因此最适合在短且受限的决策路径下优先考虑精度，而非最小化全局树规模。  

###### 索引术语  
决策树、可解释性、可解释机器学习、表格数据、分类  

††脚注：© 2026 IEEE。允许个人使用此材料。出于广告或促销目的重新印刷/再版此材料、创建新的汇编作品、转售或重新分发到服务器或列表，或在其他作品中重用任何受版权保护的组件，均需获得IEEE的许可。  

## I 引言  
决策树因其内在的可解释性，仍是表格预测任务的核心模型类别。与黑盒模型不同，决策树将每个输入映射为确定的从根到叶的路径，该路径由特征阈值测试组成，允许将单个预测作为类规则的决策过程进行检查。因此，这种基于路径的结构在必须解释、审计或通过少量顺序决策实施预测的场景中特别具有吸引力[1](https://arxiv.org/html/2608.29262#bib.bib38),[2](https://arxiv.org/html/2608.29262#bib.bib11),[3](https://arxiv.org/html/2608.29262#bib.bib1)。尽管决策树通常被视为可解释模型，但其可解释性取决于人类认知因素和预期用途上下文；任何单一的全局复杂度度量都无法完全捕捉它[4](https://arxiv.org/html/2608.29262#bib.bib9),[5](https://arxiv.org/html/2608.29262#bib.bib8),[2](https://arxiv.org/html/2608.29262#bib.bib11)。例如，一棵树可能包含许多叶子节点，但每个实例通过短路径分配；相反，一棵全局紧凑的树可能包含过深而无法实际检查的路径。由于预测通常一次解释一个实例，路径长度被视为检查工作量的代理指标，同时报告叶子节点数量以揭示相应的全局规模权衡[5](https://arxiv.org/html/2608.29262#bib.bib8),[6](https://arxiv.org/html/2608.29262#bib.bib10)。因此，浅层树在预测需要人工审查、审计或作为类规则决策协议实施的场景中尤为重要，例如高风险决策支持和临床风险分层[3](https://arxiv.org/html/2608.29262#bib.bib1),[7](https://arxiv.org/html/2608.29262#bib.bib14)。  

本文研究**浅层深度树归纳**，其中最大决策深度受到严格约束，例如 D≤4。在此模式下，目标不仅是减少叶子节点总数，而是在短的实例级决策路径预算下提高预测精度。然而，传统的二元决策树在此浅层深度模式下面临表达能力瓶颈。深度为D的二叉树最多可表示 2^D 个叶子节点，每个内部节点仅使用单次阈值决策划分其区域。当D较小时，路径长度与划分能力之间的这种耦合可能使单棵二元树对异构表格决策边界的表达能力不足。具体而言，贪心方法[8](https://arxiv.org/html/2608.29262#bib.bib2),[9](https://arxiv.org/html/2608.29262#bib.bib15)在深度预算较小时会做出次优的根级决策且难以修正；基于求解器的方法改进了全局搜索，但通常针对二元或受限的候选划分结构进行操作[10](https://arxiv.org/html/2608.29262#bib.bib16)；而可微树方法通常保留二元路由、软预测或难以解释的集成式公式。  

我们的关键思想是通过将选定特征划分为多个有序区间，采用多路划分来提高每个决策步骤的局部表达能力。本文提出**自适应剪枝的多分支神经决策树**（MBNDT）¹，一种通过基于梯度优化的端到端训练实现的轴对齐浅层决策树。每个内部节点学习一个特征选择器和一组严格有序的阈值，这些阈值在选定特征上定义一个可微的多路划分。此外，MBNDT避免了节点级的贪心划分选择，而是联合优化划分特征、阈值和叶子节点预测。为了避免在每个节点不必要地使用完整分支因子，MBNDT引入了可学习的分支掩码，在训练期间自适应每个划分的有效分支数。训练完成后，学习到的路由结构和分支掩码被转换为用于推理的确定性剪枝树，为每个实例生成单一的从根到叶的预测路径。  

我们的实证研究评估了MBNDT在固定浅层深度预算下，与贪心、基于求解器和基于梯度的单树基线的表现。在评估的数据集中，MBNDT在深度受限的单树学习器中实现了最佳的平均排名和最高的平均平衡精度，同时稀疏化消融实验表明分支掩码和事后剪枝在不降低平衡精度的情况下减少了实际叶子节点数。这些增益伴随着明确的复杂性权衡——MBNDT生成的叶子节点数多于其他单树基线——因此它最适合优先考虑短实例级决策路径下的精度，而非最小化全局树规模的场景。  

我们的贡献如下：  
- • **自适应多路分支**。我们引入可微分的、轴对齐的多路区间划分：每个内部节点选择单一特征，并学习有序阈值将其划分为多个区域，划分特征、阈值和叶子节点预测通过梯度下降联合优化，而非贪心选择。  
- • **可微树的结构稀疏化**。我们通过可学习的分支掩码自适应每个节点的有效分支数，在训练期间通过可微的叶子预算惩罚控制树规模，并应用事后训练路径剪枝——共同将名义上的B叉树转换为每个输入具有确定性路径的紧凑有效树。  
- • **精度–深度–规模分析**。我们在共享深度预算下，将MBNDT与贪心、基于求解器和基于梯度的单树基线进行基准测试，报告预测精度、决策路径长度和实际叶子节点数，并通过消融实验隔离多路分支和稀疏化机制的作用。  

## II 相关工作  

### II-A 规则简洁性与解释冗余  
多项研究通过分析单个从根到叶规则的复杂性来评估树的可解释性。Souza等人[6](https://arxiv.org/html/2608.29262#bib.bib10)将解释大小定义为决策路径上出现的不同属性数量。然而，完整路径不一定是最小解释：Izza等人[11](https://arxiv.org/html/2608.29262#bib.bib12)研究了冗余路径条件，而McTavish等人[12](https://arxiv.org/html/2608.29262#bib.bib13)表明预测等效的树可能诱导不同的评估过程。这些关注点与我们的范围互补：我们约束执行的决策步骤数量，而非主张子集最小的解释。  

### II-B 贪心决策树归纳  
经典的决策树学习器通常采用自顶向下的递归划分策略：在每个节点，选择能使局部不纯度降低（如信息增益或基尼指数）最大化的特征和阈值，然后在生成的子节点上递归。代表性算法包括ID3[13](https://arxiv.org/html/2608.29262#bib.bib7)、C4.5[9](https://arxiv.org/html/2608.29262#bib.bib15)和CART[8](https://arxiv.org/html/2608.29262#bib.bib2)。这些方法快速且可扩展，但孤立地优化每个划分可能导致全局次优的树，这一局限性在浅层深度预算下尤为显著[10](https://arxiv.org/html/2608.29262#bib.bib16)。  

### II-C 最优决策树搜索  
除了贪心归纳，最优树方法将树学习表述为离散全局优化问题，通常在固定深度、叶子或特征预算下进行。混合整数规划方法编码路由、划分选择和叶子预测，并使用分支定界法求解所得公式[10](https://arxiv.org/html/2608.29262#bib.bib16)。专用方法通过动态规划、界限和搜索重用提高可扩展性[14](https://arxiv.org/html/2608.29262#bib.bib19),[15](https://arxiv.org/html/2608.29262#bib.bib18),[16](https://arxiv.org/html/2608.29262#bib.bib21),[17](https://arxiv.org/html/2608.29262#bib.bib20),[18](https://arxiv.org/html/2608.29262#bib.bib22)。近期工作还减少了对粗略离散化的依赖：ConTree直接使用动态规划与分支定界优化连续特征阈值[19](https://arxiv.org/html/2608.29262#bib.bib23)，而SPLIT结合有界前瞻与贪心底层划分以实现近似最优搜索[20](https://arxiv.org/html/2608.29262#bib.bib37)。  

### II-D 决策树的多路划分  
多路划分在ID3/C4.5风格和CHAID树中早已用于分类属性[13](https://arxiv.org/html/2608.29262#bib.bib7),[9](https://arxiv.org/html/2608.29262#bib.bib15),[21](https://arxiv.org/html/2608.29262#bib.bib3)。数值变体在每个节点搜索多个阈值以获得更小或更具表达能力的树[22](https://arxiv.org/html/2608.29262#bib.bib5),[23](https://arxiv.org/html/2608.29262#bib.bib4)。最近，结合列生成的路径混合整数公式已被用于学习受约束的最优多路划分树[24](https://arxiv.org/html/2608.29262#bib.bib17)。然而，早期的节点级方法未跨层级联合优化结构，更高的分支数可能导致数据碎片化和过拟合增加，可能需要事后剪枝。  

### II-E 可微决策树  
另一类工作用基于梯度的优化替代节点级贪心归纳。这些方法用可微松弛或替代梯度替代离散划分选择，使得树参数可通过反向传播优化。Good等人[25](https://arxiv.org/html/2608.29262#bib.bib40)交替进行稀疏特征学习和可微树构建以获得紧凑树。Norouzi等人[26](https://arxiv.org/html/2608.29262#bib.bib26)跨层级联合优化斜划分和叶子参数，而DTSemNet[27](https://arxiv.org/html/2608.29262#bib.bib39)通过神经网络编码学习硬斜树。软路由方法使用可微路径概率[28](https://arxiv.org/html/2608.29262#bib.bib28),[29](https://arxiv.org/html/2608.29262#bib.bib30)。特别相关的是，DNDT通过梯度下降学习特征级多区间切点，而D3T自适应每个特征的切点数量[30](https://arxiv.org/html/2608.29262#bib.bib24),[31](https://arxiv.org/html/2608.29262#bib.bib25)。这些方法全局离散化特征，而MBNDT在递归树的内部节点放置自适应多路划分。GradTree通过替代梯度学习硬轴对齐树，而GRANDE将梯度训练树扩展到集成[32](https://arxiv.org/html/2608.29262#bib.bib32),[33](https://arxiv.org/html/2608.29262#bib.bib33)。MBNDT进一步将学习到的结构转换为用于单路径推理的确定性剪枝树。  

参见图1：预设最大分支因子B=3的MBNDT概述。左：具有掩码抑制分支的名义深度2三叉树。右：节点级路由，其中选定特征通过有序阈值划分为软区间概率，经分支掩码重新加权后，硬路由至单一子节点。  

### II-F 定位  
MBNDT的各个组成部分并非全新：多路数值划分、基于梯度的树训练和全局阈值优化已在上文分别研究。我们的贡献是将它们统一到一个决策树学习器中，该学习器学习具有连续阈值的有序*多路*区间划分，并自适应每个节点的*有效分支数*，同时保持为单一轴对齐树。  

## III MBNDT：架构、训练与推理  
我们将MBNDT的学习形式化为联合优化一个预定义决策树T_θ的参数θ，该树在每个内部节点具有分支因子B和深度D。轴对齐节点选择一个输入特征，路由表示根据包含该特征值的区间将输入分配给一个子节点。可学习参数包括节点级的划分特征参数、划分阈值参数、分支掩码和B^D个叶子logit。图1说明了节点级流程。  

给定带标签的训练集S = {(x_i, y_i)}_{i=1}^n，其中x_i ∈ R^p，二元标签y_i ∈ {0, 1}，MBNDT输出一个标量logit f_θ(x) ∈ R。其sigmoid变换σ(f_θ(x))被解释为正类的估计概率。在我们的实验中，我们使用二元交叉熵损失和定义的叶子预算正则化项训练模型：  

min_θ (1/n) Σ_{i=1}^n L_BCE(y_i, f_θ(x_i)) + L_budget(θ)  (1)  

我们将L_budget的详细形式推迟到第IV-B节。  

### III-A 划分特征选择  
在内部节点j处，我们为节点j关联一个可学习的向量...