跳转至

Approximation-Free Differentiable Oblique Decision Trees

作者: Subrat Prasad Panda, Blaise Genest, Arvind Easwaran
来源: JMLR
主题: 统计计算 / 算法
相关性: 3/10
机构绿灯: Nanyang Technological University(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本文所处的子方向是可微决策树(Differentiable Decision Trees),其根本问题在于:决策树(DT)是离散的、非光滑的模型,其训练通常依赖贪心分裂(如 CART)或混合整数规划,难以用端到端的梯度下降进行联合优化。可微决策树的目标是设计一种"语义等价"的连续松弛,使得树的结构参数(内部节点的分裂超平面)和叶节点参数(分类标签或回归器)可以通过标准反向传播同时优化。该方向的成熟度处于"方法快速迭代但缺乏统一理论"的阶段——大量工作依赖启发式近似(如软软化、STE),而本文试图填补"无近似"这一空白。

发展脉络(history)

  • 奠基工作:可微决策树的早期探索可追溯到软决策树(Soft Decision Trees),其核心思想是用 Sigmoid 函数软化内部节点的硬判断,使树成为可微函数(Frosst and Hinton, 2017;Yang et al., 2018)。这类方法的问题在于:训练得到的"软树"在推理时需要硬化(hardening),而硬化后的树与训练时优化的目标函数不一致,导致性能损失。
  • 主要进展:后续工作试图通过更精细的梯度估计来缓解软树的问题。DGT(Karthikeyan et al., 2022)和 ICCT(Paleja et al., 2022)引入了 STE(Straight-Through Estimator,Bengio et al., 2013)——在前向传播时使用硬判断(one-hot 路由),在反向传播时用恒等映射或近似函数替代不可导的阶梯函数,从而让梯度"穿透"离散选择。GradTree(Marton et al., 2024, 2025)进一步将 STE 用于轴对齐树的端到端学习。然而,STE 的本质是"前向-反向不一致"的近似,其梯度是有偏的,且偏差会随树深累积。
  • 当前 frontier:与可微树并行的一条线是将树嵌入神经网络架构。例如,ANT(Tanno et al., 2019)在树的内部节点使用神经网络而非线性超平面,NDBT(Wan et al., 2020)通过权重空间构造树。这些方法虽然提升了表达能力,但牺牲了树的可解释性和验证性。另一条线是混合整数规划(MIP)(Bertsimas and Dunn, 2017)和全局搜索(Costa et al., 2024),它们能找到全局最优树,但计算成本随树规模指数增长,难以扩展到大规模数据。
  • 本文的位置:本文提出的 DTSemNet 声称是第一个语义等价且可逆的硬斜决策树神经网络编码——前向传播与硬树完全一致(无软化),反向传播通过 ReLU 的次梯度自然获得非零梯度(无需 STE 近似)。在分类任务中,这种编码天然适配;在回归任务中,作者引入退火 Top-k 机制解决联合优化难题。本文的定位是"用标准梯度下降训练硬树,且不引入任何近似"。

子线索聚类

  1. 软树与概率路由:Frosst and Hinton (2017)、Yang et al. (2018)、Biau et al. (2019)、Tanno et al. (2019)、Hazimeh et al. (2020)、Zantedeschi et al. (2021)。这类方法用连续概率(Sigmoid/Softmax)替代硬路由,训练目标是软树本身,推理时硬化。
  2. STE 与量化梯度:Bengio et al. (2013)、Hubara et al. (2016)、Karthikeyan et al. (2022)、Paleja et al. (2022)、Marton et al. (2024, 2025)。这类方法保持前向硬路由,反向用近似梯度(STE 或量化梯度),目标是训练硬树但梯度有偏。
  3. 树作为神经网络:Kontschieder et al. (2015)、Bulo and Kontschieder (2014)、Wan et al. (2020)、Tanno et al. (2019)。这类方法将树的节点替换为神经网络模块,提升表达能力但牺牲可解释性。
  4. 非梯度全局优化:Bennett and Blue (1996)、Bertsimas and Dunn (2017)、Costa et al. (2024)。这类方法用 MIP 或进化算法搜索树结构,保证全局最优但计算昂贵。

这个方向在追问的核心问题

  1. 如何消除软树硬化后的性能损失? 软树训练与硬树推理的目标不一致,是制约可微树性能的根本矛盾。
  2. 如何获得无偏的梯度信号? STE 的梯度有偏,导致训练不稳定和次优解;是否存在一种编码使得前向和反向共享同一目标函数?
  3. 如何平衡树的表达力与可解释性? 神经网络化的树(ANT、NDBT)提升了精度但丧失了树的符号可验证性,而线性超平面树(DTSemNet)保持了可解释性但受限于线性分裂。
  4. 如何高效地联合优化路由与叶节点? 回归任务中,叶节点是连续回归器,其梯度与路由决策耦合,导致优化困难。

⚠️ 作者的 framing

作者将缺口 frame 成:"现有可微树方法要么软化(soft trees),要么使用 STE 近似,都存在前向-反向不一致的问题。DTSemNet 通过 ReLU 的次梯度性质,实现了前向与反向的语义一致,从而在分类和回归任务上都优于 SOTA。" 作者淡化的竞争路线包括:(1) 非梯度方法(MIP、进化算法)——作者仅以"计算成本高"一笔带过,未讨论其在中小规模数据上的精度优势;(2) 神经网络化树(ANT)——作者仅在实验对比中提及,未深入讨论表达力与可解释性的权衡。值得研究者去查的问题:作者声称"语义等价"是否在所有输入上都成立?ReLU 在零点处的次梯度选择是否会影响训练稳定性?作者未引用任何关于可微树泛化误差的理论分析(如 Rademacher 复杂度),这是否意味着该方向缺乏理论支撑?

张力

未见明显对立引用。但存在一个隐含张力:软树方法(如 Hazimeh et al., 2020)认为"软化是必要的",而本文认为"软化是可以完全避免的"。这两条路线在实验上互有胜负,但缺乏系统的理论对比(如在不同信噪比、不同树深下的表现差异)。

二、最核心、最简单的例子 / 数学问题

第一步:符号、模型、可观测数据

  • 输入空间:\(\mathcal{X} \subseteq \mathbb{R}^d\),输入 \(x \in \mathcal{X}\) 有 \(d\) 个特征。
  • 输出空间:分类时 \(\mathcal{Y} = \{1, \ldots, c\}\)(\(c\) 类);回归时 \(\mathcal{Y} \subseteq \mathbb{R}\)。
  • 数据集:\(\mathcal{D} = \{(x_i, y_i)\}_{i=1}^N\),\(N\) 为样本量,\((x_i, y_i) \overset{\text{i.i.d.}}{\sim} P\)(未知联合分布)。
  • 决策树 \(T\):由 \(m\) 个内部节点 \(\mathcal{I} = \{I_0, \ldots, I_{m-1}\}\) 和 \(n\) 个叶节点 \(\mathcal{L} = \{L_0, \ldots, L_{n-1}\}\) 组成。每个内部节点 \(I_j\) 有一个权重向量 \(A_j \in \mathbb{R}^d\) 和偏置 \(b_j \in \mathbb{R}\),分裂规则为 \(\langle A_j, x \rangle + b_j > 0\)(右子树)否则左子树。
  • 路由函数:\(T(x; A, b): \mathbb{R}^d \to \mathcal{L}\),将输入 \(x\) 确定性映射到唯一叶节点。
  • 叶参数:分类时 \(\Theta = \{\Theta_\ell\}_{\ell=0}^{n-1}\),\(\Theta_\ell \in \{1, \ldots, c\}\) 是叶 \(\ell\) 的类标签;回归时 \(\Theta = [(\theta_0, \alpha_0), \ldots, (\theta_{n-1}, \alpha_{n-1})]^\top \in \mathbb{R}^{n \times (d+1)}\),叶 \(\ell\) 的回归器为 \(\hat{y} = \langle \theta_\ell, x \rangle + \alpha_\ell\)。
  • 损失函数:\(\mathcal{L}(\hat{y}, y)\),如交叉熵(分类)或均方误差(回归)。
  • 训练目标:\(\min_{A, b, \Theta} \mathbb{E}_{(x,y) \sim P}[\mathcal{L}(\hat{y}, y)]\),其中 \(\hat{y}\) 由 \(T(x; A, b)\) 和 \(\Theta\) 决定。
  • 可观测数据:研究者能观测到的是输入-输出对 \((x_i, y_i)\)。观测不到的是:(1) 最优树结构(哪些特征在哪些节点分裂);(2) 每个样本实际路由到哪个叶节点(因为树结构未知);(3) 叶节点的最优参数。这些都需要通过优化来估计。

第二步:最小内核

核心命题:给定一个硬斜决策树 \(T\),能否构造一个神经网络 \(N_T: \mathbb{R}^d \to \mathbb{R}^n\),使得对于任意输入 \(x\),\(N_T(x)\) 的最大分量索引恰好等于 \(T(x)\) 选中的叶节点?

最小例子:考虑一棵深度为 1 的二叉树(一个内部节点 \(I_0\),两个叶节点 \(L_0, L_1\))。内部节点参数为 \((A_0, b_0)\),分裂规则为 \(\langle A_0, x \rangle + b_0 > 0\) 则去 \(L_1\),否则去 \(L_0\)。

DTSemNet 的构造如下: - 第一层(线性层):计算 \(z_0 = \langle A_0, x \rangle + b_0\)。 - 第二层(分支激活):\(\top_0(x) = \text{ReLU}(z_0)\),\(\bot_0(x) = \text{ReLU}(-z_0)\)。 - 第三层(输出层):\(L'_0(x) = \bot_0(x)\),\(L'_1(x) = \top_0(x)\)。

验证:若 \(\langle A_0, x \rangle + b_0 > 0\),则 \(\top_0(x) = z_0 > 0\),\(\bot_0(x) = 0\),所以 \(L'_1(x) > L'_0(x)\),\(\arg\max N_T(x) = L_1 = T(x)\)。若 \(\langle A_0, x \rangle + b_0 < 0\),则 \(\top_0(x) = 0\),\(\bot_0(x) = -z_0 > 0\),所以 \(L'_0(x) > L'_1(x)\),\(\arg\max N_T(x) = L_0 = T(x)\)。命题成立。

为什么这个例子是核心:深度为 1 的情形揭示了 DTSemNet 的全部本质——ReLU 的次梯度性质。在反向传播时,\(\frac{\partial \top_0}{\partial z_0} = \mathbb{1}[z_0 > 0]\)(次梯度),\(\frac{\partial \bot_0}{\partial z_0} = -\mathbb{1}[z_0 < 0]\)。这意味着梯度只会流向实际被选中的分支路径上的参数,而未被选中的分支梯度为零。这与 STE 不同:STE 在反向传播时用恒等映射 \(\frac{\partial h}{\partial z} \approx I\),导致所有内部节点参数都被更新(包括那些与当前样本路由无关的节点)。DTSemNet 的梯度是"稀疏"的——只更新实际路径上的节点,这与硬树的语义完全一致。

一般情形的推广:对于深度为 \(D\) 的树,每个内部节点 \(I_j\) 的输出 \(\top_j, \bot_j\) 通过 ReLU 计算,叶节点 \(L'_\ell\) 的得分是所有路径上分支激活之和(或乘积,取决于编码细节)。定理 1 的证明思路是归纳法:对任意输入 \(x\),沿 \(T(x)\) 的路径,每个内部节点都贡献一个正的分支激活,而偏离路径的节点贡献为零,因此 \(L'_{T(x)}\) 严格大于所有其他叶节点得分。

回归任务的困难:分类时,叶节点是离散标签,只需比较得分大小;回归时,叶节点是连续回归器,输出 \(\hat{y} = \langle h, R(x) \rangle\) 其中 \(h\) 是 one-hot 向量。梯度 \(\nabla_\Theta \mathcal{L} = \mathcal{L}' \cdot h \cdot x^\top\) 只更新被选中的叶回归器。但内部节点参数 \(A\) 的梯度需要通过 \(h\) 传播,而 \(h\) 是离散的——这正是 STE 被引入的原因。DTSemNet 的解决方案是退火 Top-k:训练初期用较大的 \(k\)(如 \(k=4\))让多个叶回归器同时接收梯度,随着训练推进逐渐减小 \(k\) 至 1,最终得到硬树。这个过程的每一步都是"无近似"的——前向传播就是 Top-k 加权平均,反向传播就是该加权平均的精确梯度。

三、这篇论文做了什么

三句话

  1. 研究了什么问题:如何在不使用软化和 STE 近似的前提下,用标准梯度下降端到端训练硬斜决策树,同时适用于分类和回归任务。
  2. 核心工具/方法:提出 DTSemNet——一种将硬斜决策树编码为语义等价且可逆的神经网络架构,利用 ReLU 的次梯度性质实现无近似的梯度传播;针对回归任务,提出退火 Top-k 选择机制解决联合优化难题。
  3. 主要结论:在分类和回归基准上,DTSemNet 训练的斜决策树优于 DGT、ICCT、GradTree 等 STE 方法,且与 TAO 等非梯度方法相比在精度和训练时间上均有优势;在 RL 任务中,DTSemNet 可作为程序化策略,性能接近神经网络策略但具有可解释性。

关键设定与假设

  • 树结构固定:DTSemNet 假设树的深度(或叶节点数)是预先给定的超参数,训练只优化内部节点的分裂参数 \((A, b)\) 和叶节点参数 \(\Theta\),不学习树的结构。这与 CART 的贪心生长不同,也与 ANT 的自适应生长不同。
  • 线性分裂超平面:每个内部节点使用线性超平面 \(\langle A_j, x \rangle + b_j > 0\) 进行分裂,而非轴对齐分裂(如 CART)或非线性分裂(如 ANT 的神经网络节点)。
  • ReLU 次梯度:在反向传播中,ReLU 在零点处的次梯度被选为 0(即 \(\mathbb{1}[z > 0]\) 在 \(z=0\) 处取 0)。这是一个技术性假设,作者未讨论其影响。
  • Top-k 退火调度:回归任务中,\(k\) 的退火调度(从 \(k=4\) 到 \(k=1\))是经验设定的,作者未提供理论指导。
  • 无近似性声明:作者声称 DTSemNet 在训练和推理中都是"无近似"的,但 Top-k(\(k \geq 2\))的前向传播实际上是多个叶回归器的加权平均,并非硬树——这一"近似"仅在 \(k=1\) 时消失。作者的论证是:Top-k 的每个 \(k\) 值都对应一个明确的优化目标,不存在前向-反向不一致。

主要结果

分类任务(表 3、表 4): - 在 14 个分类基准上(表 3,树高 ≤ 4),DTSemNet 在所有数据集上取得最高平均精度,平均距离最优方法的偏差为 0.0%,而 DGT 为 1.4%,TAO 为 7.4%,CART 为 9.2%,CRO-DT 为 7.3%。 - 在 8 个更深树基准上(表 4),DTSemNet 同样全面领先,平均距离最优偏差 0.0%,DGT 为 1.6%,TAO 为 1.1%,CART 为 9.8%。 - 最大改进出现在高维数据集:Optical Recognition(64 特征)上,DTSemNet 精度 93.3%,比 DGT 高 1.4 个百分点,比 CART 高 28.1 个百分点。

回归任务(表 1、表 2): - 在 5 个回归基准上(表 1),DTSemNet Top-k 在 4 个数据集上取得最低 RMSE,平均距离最优偏差 0.6%,优于 DTSemNet STE(8.8%)、DGT-Linear(15%)、TAO-Linear(3.4%)和 CART(101%)。 - 在 10 个额外回归数据集上(表 2),DTSemNet Top-k 平均距离最优偏差 0.1%,在 8 个数据集上取得最优。 - 关键对比:在 CTSlice 上,DTSemNet Top-k 的 RMSE 为 1.07,而 DTSemNet STE 为 1.26(差 15%),DGT-Linear 为 1.78(差 40%)。作者通过图 3 的叶分布分析表明,STE 导致叶利用率严重不均衡(大量叶几乎无样本),而 Top-k 实现了更均衡的叶分配。

RL 任务(表 8): - 离散动作:CartPole 上 DTSemNet 达到满分 500,与 Deep RL 持平;Acrobot 上 DTSemNet(-82.5)优于所有 DT 方法,接近 Deep RL(-84.0);LunarLander 上 DTSemNet(252.5)大幅领先 DGT(183.6)、ICCT(-85.0)和 VIPER(86.7);Zerglings 上 DTSemNet(15.54)显著优于 DGT(8.21)和 ICCT(9.40)。 - 连续动作:Continuous LunarLander 上 DTSemNet Top-k(282.5)优于 STE(277.2)和 Deep RL(276.1);BipedalWalker 上 DTSemNet Top-k(325.4)优于 STE(315.0)和 Deep RL(315.3)。 - 作者强调,DTSemNet 的策略是硬树,可直接验证和形式化分析,而 Deep RL 策略是黑箱神经网络。

训练时间(表 5): - MNIST 上 DTSemNet 训练时间 306 秒,与 DGT(288 秒)接近,远快于 TAO(1200 秒)和 CRO-DT(4659 秒)。

证明路线与技术技巧

定理 1 的证明:采用归纳法。基础情形(深度 1)已在第二节验证。归纳步骤:假设对于深度 \(D-1\) 的子树,\(\arg\max\) 选择正确;对于深度 \(D\) 的树,考虑根节点的分裂。若 \(x\) 被路由到右子树,则根节点的 \(\top_0(x) > 0\) 且 \(\bot_0(x) = 0\),右子树的所有叶节点得分包含 \(\top_0(x)\) 的正贡献,而左子树的所有叶节点得分不包含该贡献,因此右子树的叶节点得分严格大于左子树。由归纳假设,右子树内部选择正确的叶节点,故整体正确。

关键技巧: 1. ReLU 的"硬门控"性质:\(\text{ReLU}(z)\) 在 \(z > 0\) 时导数为 1,在 \(z < 0\) 时导数为 0。这使得梯度只流向实际路由路径上的参数,实现了"硬"路由的精确梯度。 2. 可逆编码:DTSemNet 的每一层都是可逆的——给定输出,可以唯一恢复输入的路由路径。这保证了训练后的网络可以无损转换为决策树。 3. Top-k 退火:将离散的 Top-1 选择松弛为 Top-k 加权平均,但不同于 STE 的"前向硬、反向软",Top-k 的前向和反向共享同一目标函数(即 Top-k 加权平均的损失),不存在不一致。退火调度(\(k: 4 \to 1\))提供了从探索到利用的平滑过渡。 4. 固定权重层:输出层的权重是固定的 0/1 矩阵(编码树结构),不参与训练,从而保证了语义等价性。

🔎 结论是否比证明窄

  • 作者声称"无近似",但 Top-k(\(k \geq 2\))的训练过程本身就是一个近似——它优化的不是硬树的目标函数,而是 Top-k 软加权的目标函数。作者通过"前向-反向一致"来辩护,但这回避了"Top-k 目标与 Top-1 目标是否等价"的问题。作者未证明退火过程收敛到硬树的最优解。
  • 定理 1 只证明了前向等价性(DTSemNet 的输出与 DT 一致),未证明训练过程的收敛性或泛化误差界。作者没有提供任何关于 DTSemNet 训练动态的理论分析。
  • 作者声称"首次实现无近似",但这一声明依赖于对"近似"的定义。如果 Top-k 被视为近似,那么 DTSemNet 在回归任务中并非无近似;如果 Top-k 被视为精确的替代目标,那么需要证明该目标与原始目标的一致性——作者未提供此证明。
  • 实验对比的局限性:作者未与最新的软树方法(如 Hazimeh et al., 2020 的 Tree Ensemble Layer)在同等计算预算下对比;TAO 的结果来自原论文,可能未针对 DTSemNet 的设置进行调优。

四、开放问题

  1. Top-k 退火的理论保证:退火调度(\(k\) 的衰减速率、温度 \(\tau\) 的选择)是否有理论指导?能否证明在某种条件下,Top-k 训练收敛到 Top-1 硬树的最优解?这扎根于论文第 3.4.5 节对退火过程的经验性描述,作者未提供任何收敛性分析。

  2. 泛化误差分析:DTSemNet 训练的决策树的泛化误差是否有理论界?其复杂度度量(如 VC 维或 Rademacher 复杂度)与树深、叶数、特征维度的关系是什么?作者在全文未提及任何泛化理论。

  3. 树结构的自适应学习:DTSemNet 将树深作为超参数固定,能否设计可微的树生长/剪枝机制,使结构本身参与优化?作者在 Future Work 中提及"考虑开发自适应的生长和剪枝方法",但未给出任何具体思路。

  4. 高维输入的扩展:作者在 Limitations 中承认 DTSemNet 不适合高维输入(如图像),因为需要大量叶节点。能否设计层次化或卷积化的 DTSemNet 变体来缓解这一问题?这扎根于论文 Limitations 段的明确声明。

  5. 与因果推断的接口:决策树在异质性处理效应估计(如 CATE)中有广泛应用。DTSemNet 的可微性是否可用于因果树的端到端训练,从而避免传统因果树的两阶段估计?这是一个未被论文提及但自然延伸的问题。

提示:要确认上述问题是否为真 gap,建议去读近 5 年 ICML/NeurIPS/JMLR 上关于可微决策树和神经决策树的论文(如 TEL、NDBT、GradTree 的后续工作)的 introduction——如果多篇论文都指向同一问题,则可能是共识性 gap;如果各论文对同一问题的处理方式互相矛盾,则可能是机会。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论