Literati: Towards Anytime Optimal Shape Generalized Trees via AO*¶
会议: NeurIPS 2026
arXiv: 2609.09299
OpenReview: https://openreview.net/forum?id=uUYZFj5qPL
代码: https://github.com/optimal-uoft/Empowering-DTs-via-Shape-Functions
领域: 优化/理论
关键词: 最优决策树, 形状广义树, AND/OR 图搜索, AO* 算法, 随时优化
一句话总结¶
本文提出首个全局最优形状广义决策树归纳算法 Literati，通过 AND/OR 图联合优化树结构与单变量形状函数断点，并结合非容许次级启发式与 Round-Robin 机制实现了兼顾最优性保证的高效随时搜索。
研究背景与动机¶
决策树凭借内生可解释性与对表格数据的强拟合能力，在医疗健康、信贷风控等高风险决策场景中被广泛使用。然而，经典的自顶向下贪心归纳算法（如 CART 和 C4.5）通过局部不纯度最小化进行递归划分，极易陷入局部最优并产生冗长冗余的树结构。近年来，全局最优决策树（Optimal Decision Trees）方法通过动态规划或分支定界优化正则化目标，显著缓解了贪心子优性，但绝大多数现有方法严格受限于轴对齐的单阈值划分（\(x_j \leq \theta\)），导致单个节点表达能力不足，在拟合非线性特征响应时往往不得不层叠多层冗余分支。
为了突破阈值划分的表达力天花板，形状广义树（Shape Generalized Trees, SGT）将阈值划分推广为分段常数单变量形状函数，允许单个内部节点对单个特征捕获复杂的非线性模式，从而以更紧凑的树深度实现优异性能。但现有 SGT 算法（如 ShapeCART 和 ShapeTAO）仍依赖贪心分裂或局部坐标下降，不仅缺乏全局最优性保证，且因形状函数候选空间呈指数爆炸，直接枚举完全不可行。
将全局最优决策树技术直接套用到 SGT 会面临状态空间爆炸的根本困境。若直接在树节点层面穷举所有合法的多分段形状函数，动态规划或分支定界的状态转移分支因子将不堪重负。本文的核心切入点是将形状函数的逐步构造过程与树的拓扑生长解耦解构。核心 idea：将稀疏形状广义树诱导建模为数据状态与形状函数状态交替生长的精细 AND/OR 图，在保留全局最优性保证的同时，利用次级非容许启发式引导 OR 节点选择并配合 Round-Robin AND 探索，实现卓越的随时（Anytime）全局优化。
方法详解¶
整体框架¶
Literati 将稀疏 SGT 的求解转化为精确的 AND/OR 超图搜索。输入为训练数据集 \(\mathcal{D}\)、最大深度预算 \(D\) 以及单节点最大断点数 \(K\)；输出为正则化目标全局最优或随时高质量的形状广义树 \(T^*\)。算法定义了两种交替状态：数据状态（Data State）负责决策当前子集是停止分裂成为叶节点，还是选择某个特征与首个候选断点开启形状函数构造；形状函数状态（Shape Function State）负责以贪心递增方式通过追加断点逐步精化形状函数，或通过提交（Commit）操作将数据划分为左右两个子集并派生出深度预算减一的两个子数据状态。
由于完整超图的规模极大，Literati 结合自适应候选阈值离散化、容许性启发式下界 \(V\) 与次级启发式 \(\widetilde{V}\)，采用改进的 AO* 循环迭代推进：通过选择、扩展与反向传播三阶段，在不完全展开图的前提下快速收敛至全局最优。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["输入数据样本与深度预算<br/>(D, d)"] --> B["自适应断点离散化<br/>局部CART提取候选分割点"]
B --> C["增量式AND/OR图搜索<br/>交替展开数据与形状状态"]
C --> D["双启发式导向的OR节点选择<br/>次级CART-lookahead引导深入"]
D --> E["平衡式Round-Robin AND节点探索<br/>双子树轮转防饥饿"]
E --> F["对偶修剪与随时解提取<br/>原始上界更新与最终SGT"]关键设计¶
1. 增量式AND/OR图状态空间分解：精细解耦单断点递增与树拓扑扩展
若直接按照宏观动态规划枚举每个节点所有满足断点数 \(\mathbf{K}(f_v) \leq K\) 的形状函数，搜索空间的分支因子将达到 \(O(M N^K)\)，导致搜索树规模急剧膨胀。针对这一痛点，Literati 将决策过程拆解为两种状态的交替转移。数据状态 \(s = (\mathcal{D}_s, d)\) 对应 OR 动态，动作包括选择终止为叶节点（成本为 \(0\)，终端价值为多数类误分类数 \(\text{Err}(\mathcal{D}_s)\)），或者以成本 \(\lambda + \alpha\) 选择特征 \(j\) 及首个断点 \(u\)，转移到初始形状函数状态 \((\mathcal{D}_s, d, j, \{u\})\)。形状函数状态 \(s_{\text{shape}} = (\mathcal{D}_s, d, j, \mathbf{k})\) 同样为 OR 动态，包含两类互斥动作：一是 Commit 动作，以 \(0\) 代价将数据切分为 \(\mathcal{D}_L\) 和 \(\mathcal{D}_R\)，产生一对满足 AND 动态的子数据状态 \(((\mathcal{D}_L, d-1), (\mathcal{D}_R, d-1))\)；二是 Refine 动作，以额外成本 \(\alpha\) 引入新断点 \(u > \max(\mathbf{k})\)，转移到更复杂的形状函数状态 \((\mathcal{D}_s, d, j, \mathbf{k} \cup \{u\})\)。严格递增的断点序号强制消除了对称重复探索。论文在理论上证明了该增量递归与原全局优化问题在贝尔曼最优方程下完全等价（Proposition 1 与 Lemma 1-2）。
2. 自适应断点离散化与严格容许启发式：大幅压缩搜索空间与理论下界保证
在连续或大规模特征上全局分位数离散化往往无法捕捉局部节点的高信息量分割点。Literati 在每个数据状态 \(s = (\mathcal{D}_s, d)\) 上，局部拟合一棵最多包含 \(B_d\) 个叶节点的浅层 CART 树，提取其用到的分裂阈值构成候选集 \(U_s^{(j)}\)。基于此，全局状态空间上限从 \(O((M N^K)^{D+1})\) 骤降至 \(O(D \cdot \prod_{d=1}^D B_d^K)\)。为支撑 AO* 的启发式剪枝，Literati 设计了严格容许（Admissible）的下界估计函数 \(V\)： $\(V(\mathcal{D}_s, d) = \min\left(\text{Err}(\mathcal{D}_s),\, \lambda + \alpha\right)\)$ 对于形状函数状态，下界为： $\(V(\mathcal{D}_s, d, j, \mathbf{k}) = \min\left(\alpha,\, \min(\text{Err}(\mathcal{D}_R), \lambda + \alpha) + \min(\text{Err}(\mathcal{D}_L), \lambda + \alpha)\right)\)$ 论文证明了在自底向上的动态传播中 \(V(s) \leq V^*(s)\) 始终成立（Proposition 2），并且当 \(\text{Err}(\mathcal{D}_s) \leq \lambda + \alpha\) 时可触发有效不等式直接标记为终结状态（Corollary 1），提前截断不必要的展开。
3. 双启发式导向的OR节点选择：克服盲目启发式导致的广度震荡
在标准 AO* 搜索中，树结构上层的样本误分类数通常远大于单次划分正则化惩罚（即 \(\text{Err}(\mathcal{D}_s) \gg \lambda + \alpha\)）。这导致所有未展开形状函数后继状态的容许估计值均被饱和截断在 \(V(s') = \min(2(\lambda+\alpha), \alpha) = \alpha\)，使得所有初始划分动作的 \(Q\) 值完全相同（均为 \(\lambda + 2\alpha\)）。由于缺乏区分度，标准 AO* 退化为类似广度优先的盲目循环扫描：每拓展一个候选点就会微增其 \(Q\) 值，进而迫使算法转去探索其他并行的平手动作，直到耗尽所有平手才深入单条路径，极大损伤了随时优化性能。为此，Literati 引入辅助的非容许次级启发式 \(\widetilde{V}\)。在数据状态上，\(\widetilde{V}(\mathcal{D}_s, d)\) 通过在该子集上快速拟合预算为 \(d\) 的前瞻 CART 树并计算其实际正则化损失；形状函数状态则直接累加两子集的前瞻树损失： $\(\widetilde{V}(\mathcal{D}_s, d, j, \mathbf{k}) = \widetilde{V}(\mathcal{D}_L(f_j^{\mathbf{k}}), d-1) + \widetilde{V}(\mathcal{D}_R(f_j^{\mathbf{k}}), d-1)\)$ 在搜索的选择阶段，算法依据诱导策略 \(\widetilde{\pi}\) 优先选择具有最低 \(\widetilde{Q}\) 值的非终结动作，使搜索能迅速沿高潜力路径下潜；而终止条件与对偶剪枝（当 \(Q(s, a) \geq \overline{V}(s)\) 时安全修剪动作 \(a\)）仍严格由容许估计 \(V\) 与当前最优原始上界 \(\overline{V}\) 决定，从而在维持全局最优性证明的同时获得极强的随时性能。
4. 平衡式Round-Robin AND节点探索：防止非对称子问题导致的选择饥饿
当执行 Commit 动作后，形状函数状态分裂出左右两个子数据状态，构成 AND 关系。先前工作（如 Branches）倾向于贪心选择当前原始上界较差（\(\overline{V}\) 较大）的子节点进行拓展，试图优先修复劣势分支。然而，当左右子集的数据规模或分类难度严重失衡时，较难子树的 \(\overline{V}\) 会长期显著高于较易子树，导致搜索算法数十次甚至上百次连续困在同一子树内，另一侧兄弟子树长期处于完全未展开状态，造成严重的探索饥饿。Literati 采用确定性的 Round-Robin 轮转机制：当左右子状态均未被彻底解决（COMPLETE）时，在连续的选择调用中严格交替下潜展开；若一侧已彻底完成，则将全部算力转入剩余未解决子节点。该机制确保了整棵树两侧特征子空间的均匀推进，显著加速了全局高品质可行树的发现。
损失函数 / 训练策略¶
Literati 求解的目标函数在分类错误计数与结构复杂度之间建立全局权衡： $\(\min_{T \in \mathcal{T}} \text{Err}(T, \mathcal{D}) + \sum_{v \in \mathcal{I}(T)} \left[ \lambda + \alpha \mathbf{K}(f_v) \right] \quad \text{s.t.} \quad \mathbf{K}(f_v) \leq K, \; \mathbf{D}(T) \leq D\)$ 在工程实现中，代码库使用仿射重参数化形式 \(\lambda_r + \alpha_r(\mathbf{K}(f_v) - 1)\)，使基准阈值分裂（\(K=1\)）的复杂度成本仅由 \(\lambda_r\) 决定，而 \(\alpha_r\) 纯粹惩罚超出常规单阈值的额外形状分段复杂度。当匹配参数 \(\alpha_{\text{DPDT}} = \lambda + \alpha\) 时，当 \(K=1\) 时 Literati 在离散搜索空间上与 DPDT 严格等价，并在 \(K \geq 2\) 时具备严格的损失支配界：\(\mathcal{L}_{\text{Literati}}^{*}(K \geq 2) \leq \mathcal{L}_{\text{Literati}}^{*}(K=1) = \mathcal{L}_{\text{DPDT}}^{*}\)（Proposition 3）。
实验关键数据¶
主实验¶
论文在 24 个小到中型真实表格数据集上进行了系统评测（5 折交叉验证，70/10/20 划分）。主要对比了非最优方法（CART、AxTAO、ShapeCART、ShapeTAO）与最优决策树方法（连续特征分支定界 ConTree、基于分位数预离散化的 Branches、STreeD、LDS-DL8.5、CADL8.5，以及自适应离散化的 DPDT）。在 1 小时限时实验中，全面评估不同深度 \(D \in \{3,4,5,6\}\) 下的训练准确率、求解时间与最优性证明率。
下表展示了全数据集在各深度预算下的平均训练准确率与证明率对比：
| 模型分类与名称 | 单节点断点 \(K\) | \(D=3\) 训练准确率 / 证明率 | \(D=4\) 训练准确率 / 证明率 | \(D=5\) 训练准确率 / 证明率 | \(D=6\) 训练准确率 / 证明率 |
|---|---|---|---|---|---|
| CART (非最优基线) | 1 | 79.60% / — | 82.70% / — | 85.65% / — | 87.64% / — |
| ShapeCART (贪心 SGT) | 3 | 80.43% / — | 83.64% / — | 86.34% / — | 88.52% / — |
| ShapeTAO (局部优化 SGT) | 3 | 81.28% / — | 85.07% / — | 87.33% / — | 89.49% / — |
| ConTree (无离散化最优树) | 1 | 84.12% / 95.8% | 86.68% / 54.2% | 86.13% / 33.3% | 84.35% / 25.0% |
| Branches (AO 树基线)* | 1 | 73.59% / 62.5% | 71.20% / 6.7% | 71.02% / 5.8% | 71.40% / 8.3% |
| STreeD (动态规划最优树) | 1 | 83.50% / 99.2% | 86.57% / 91.7% | 88.44% / 65.0% | 88.26% / 37.5% |
| DPDT (自适应离散化最优树) | 1 | 83.56% / 100.0% | 87.03% / 95.8% | 77.16% / 45.8% | 71.52% / 12.5% |
| Literati (\(K=1\)) | 1 | 83.56% / 100.0% | 87.28% / 97.5% | 89.91% / 87.5% | 92.28% / 36.7% |
| Literati (\(K=2\)) | 2 | 84.03% / 100.0% | 87.75% / 87.5% | 90.36% / 33.3% | 92.58% / 22.5% |
| Literati (\(K=3\), 本文完整模型) | 3 | 84.13% / 100.0% | 87.90% / 82.5% | 90.46% / 25.0% | 92.69% / 24.2% |
在泛化性评估中，所有模型在 15 分钟/折预算下进行 200 次随机超参数搜索，24 个数据集上的平均测试集泛化准确率如下：
| 算法模型 | 模型属性 | 平均测试准确率 (%) | 相比 CART 增益 |
|---|---|---|---|
| CART | 轴对齐贪心阈值树 | 87.6% | 基准 (0.0%) |
| ConTree | 连续特征最优阈值树 | 85.5% | -2.1% |
| Branches | AO* 分位数预离散树 | 84.0% | -3.6% |
| STreeD | 动态规划预离散最优树 | 88.5% | +0.9% |
| AxTAO | 阈值树局部优化 | 88.5% | +0.9% |
| CADL8.5 | 随时预离散最优树 | 88.6% | +1.0% |
| ShapeCART | 贪心形状广义树 (\(K=3\)) | 89.1% | +1.5% |
| DPDT | 自适应离散化最优树 | 89.3% | +1.7% |
| LDS-DL8.5 | 随时预离散最优树 | 89.6% | +2.0% |
| ShapeTAO | 局部精化形状广义树 (\(K=3\)) | 89.6% | +2.0% |
| Literati (本文) | 最优形状广义树 (\(K \leq 3\)) | 90.6% | +3.0% |
消融实验¶
在 Eye-Movements、Avila、Page、Fault 和 Rice 五个代表性数据集上（设置 \(D=6, K=3\)），针对 OR 选择策略与 AND 节点探索策略进行了系统消融（度量距最优解目标差距的收敛过程）：
| 策略组合配置 (OR选择机制 + AND选择机制) | 随时收敛速度与质量 | 说明 |
|---|---|---|
| Best Informative (\(\widetilde{V}_{\text{CART}}\)) + Round-Robin (Literati完整模型) | 最快逼近最优解 | 全局性能最优，在时间和迭代步数上均以最少扩展步数收敛到最低损失 |
| Best Informative (\(\widetilde{V}_{\text{CART}}\)) + Worst Primal (\(\uparrow \overline{V}\)) | 次优 | 存在 AND 子树选择不均问题，在非对称数据上迭代停滞 |
| Best Informative (\(\widetilde{V}_{\text{CART}}\)) + Worst Informative (\(\uparrow \widetilde{V}\)) | 良好 | 优于纯容许启发式，但对局部前瞻误差敏感 |
| Admissible (\(V\)) + Round-Robin | 缓慢 | 缺少次级启发式引导，在顶层出现盲目启发式平手震荡，初始进展极差 |
| Admissible (\(V\)) + Worst Primal (\(\uparrow \overline{V}\)) (类似 Branches 原型) | 最慢 | 遭遇双重瓶颈：OR 节点平手循环且 AND 节点持续单向饥饿 |
| \(\widetilde{V}\) 替换为纯基尼不纯度 (Impurity) | 较慢 | 单节点不纯度属于近视度量，缺乏前瞻子树能力，性能显著落后于 CART-lookahead |
| \(\widetilde{V}\) 替换为当前原始界 (Primal) | 较慢 | 初始上界较松弛时前瞻区分度弱，探索效率低下 |
关键发现¶
- 形状函数复杂度 \(K\) 的边际效应：从 \(K=1\)（常规阈值切分）拓展到 \(K=2\) 带来了显著的跨越（各深度下训练精度平均提升约 0.4%），而从 \(K=2\) 到 \(K=3\) 仍有稳定增益但幅度趋缓。在叶节点预算受限时，SGT 表现出惊人的压缩比（例如在 Avila 数据集上，SGT \(K=2\) 仅需 25 个叶节点即达到了阈值树 35 个叶节点的精度；在 Rice 上 20 个叶节点的 \(K=2\) 模型追平了 40 个叶节点的常规阈值树）。
- 随时优化对深度树的决定性影响：对于深度 \(D=5\) 和 \(D=6\)，传统完全展开或缺乏随时机制的最优树方法（如 DPDT、Branches）性能发生严重崩溃（DPDT 在 \(D=6\) 准确率暴跌至 71.52%），原因在于超时未能输出解而只能回退到单叶节点；而 Literati 的准确率随着深度单调递增至 92.69%，体现出强大的随时截断可用性。
- 内存安全与对偶剪枝：相比同为 AO* 机制的 Branches（在多数据集上频发 64GB 内存耗尽 OOM 崩溃），Literati 放弃了高开销的子集哈希全缓存，改用仅保存 10,000 个最近访问状态数值的轻量缓存，并在反向传播中及时释放被剪枝子图，实现了极佳的内存可伸缩性。
亮点与洞察¶
- 增量式断点分解消解指数爆炸：将多断点形状函数解构为单断点增量构造的马尔可夫决策过程，将不可承受的单节点直接枚举转化为超图中的顺序动作序列，使局部剪枝能在低阶断点提前生效。
- 双启发式解耦策略：非容许的次级启发式仅负责规划搜索展开的优先级（提高何时发现好解的效率），而容许性启发式与对偶界严格控制剪枝和终结验证，完美化解了启发式信息量与理论最优性之间的固有冲突。
- 可复用的表格学习组件：提出的局部自适应 CART 阈值抽取与前瞻树打分策略，能够直接移植到其他基于图搜索或分支定界的符号树模型归纳中。
局限与展望¶
- 样本规模可伸缩性瓶颈：如同大部分组合优化与动态规划类决策树方法，当面对数百万级样本或上百维特征时，在短时间内完成严格最优性证明仍极具挑战。
- 局部连续特征离散化依赖：目前的离散化依赖于局部 CART 树提取的有限阈值集合，虽然有良好的理论支配界，但在原连续空间上并非严格绝对全局最优。
- 多类扩展与多变量交互：当前主要针对单变量形状切分，未来可探索将增量 AND/OR 超图延伸至多变量斜切分（Oblique Trees）或带稀疏线性组合的高阶形状函数中。
相关工作与启发¶
- vs Branches [ICML 2025]: 两者均采用 AO* 算法，但 Branches 仅支持标准单阈值树且依赖全局分位数离散化与全状态缓存，在大深度下易因平手震荡和内存爆仓崩溃；Literati 支持任意 \(K\) 阶形状广义树，通过次级前瞻启发式与 Round-Robin 打破了双重搜索瓶颈。
- vs ShapeCART / ShapeTAO [NeurIPS 2025]: 现有 SGT 算法完全采用启发式贪心分裂或坐标下降，容易深陷局部极小值；Literati 建立了首个提供可证最优性与强随时收敛特性的全局 SGT 归纳框架。
- vs DPDT [KDD 2025]: DPDT 使用自适应离散化与 MDP 值迭代，但在大深度下缺乏有效随时中间解机制导致超时退化；Literati 在 \(K=1\) 时涵盖 DPDT 搜索空间，证明了理论支配性，并利用 AO* 图剪枝取得了数倍的加速与更高的证明率。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次将形状广义树建模为精细 AND/OR 超图，提出双启发式解耦与平衡轮转机制。
- 实验充分度: ⭐⭐⭐⭐⭐ 覆盖 24 个标准基准数据集、10 个强对比基准，涵盖训练优化、泛化测试、随时收敛轨迹及消融实验。
- 写作质量: ⭐⭐⭐⭐⭐ 理论推导完备自洽，符号定义严谨清晰，实验设计逻辑环环相扣。
- 价值: ⭐⭐⭐⭐⭐ 为高解释性机器学习提供了兼备强表达力与数学最优保证的实用算法工具。