Minimax Rates and Spectral Distillation for Tree Ensembles¶
会议: NeurIPS 2026
arXiv: 2605.11841
OpenReview: https://openreview.net/forum?id=5uMDws28Ir
领域: 模型压缩
关键词: 决策树集成, 随机森林, 梯度提升机, 极小化极大速率, 谱蒸馏
一句话总结¶
本文从谱视角建立了自适应随机森林在特征空间核算子特征值多项式衰减下的极小化极大最优收敛速率，并据此提出利用轻量多层感知机拟合核矩阵或平滑矩阵主谱方向的谱蒸馏方法 SCATE，在微控制器级别的严苛内存预算下实现高达数个数量级的模型压缩。
研究背景与动机¶
随机森林（Random Forests, RF）与梯度提升机（Gradient Boosting Machines, GBM）等树集成模型是现代表格数据监督学习领域的主力算法，在生物信息学、计量经济学以及常规工程建模中屡屡战胜复杂的深度神经网络。然而，此类算法的理论分析长期落后于其出色的经验表现：在随机森林理论中，以往绝大多数理论工作往往局限于纯随机森林等非自适应变体，刻意回避了驱动实际性能的贪婪自适应划分机制；而对于非参数回归中最核心的极小化极大（minimax）收敛性，现有自适应随机森林文献始终缺乏严格的渐近最优性保证。对于梯度提升机，其理论研究多集中于分类设置，在回归问题中树复杂度与集成规模交织下的归纳偏置同样缺乏精确刻画。
与理论匮乏形成鲜明对比的是实际边缘部署对紧凑模型的紧迫需求。工业界与嵌入式物联网设备通常受到极端存储限制（例如微控制器闪存预算往往低于 1MB 乃至 100KB），而工业级树集成动辄包含数百棵深树，占用数兆至数十兆字节内存。现有集成压缩手段主要分为两类：一是基于规则提取或树剪枝的方法（如 ForestPrune、LOP 等），这类方法往往需要预先设定误差容忍度，导致最终模型尺寸完全无法受控预测，且剪枝后的复杂树结构在边缘设备上难以向量化并行；二是以单一决策树为目标的硬蒸馏方法，但将庞大森林精确蒸馏为单棵树属于 NP-hard 难题，高维下根本不可行。
针对上述理论与工程双重瓶颈，本文将树集成模型统一纳入线性平滑算子的谱理论视阈。对于随机森林，其集成机制等价于核积分算子；对于梯度提升机，其拟合残差的级联过程则诱导出非对称平滑矩阵。通过建立核算子谱衰减与统计泛化速率的内在联系，研究不仅一举攻克了自适应随机森林的极小化极大最优性问题，更为树集成模型的定额压缩提供了坚实算子基础。核心 idea：树集成的有效表征能力高度浓缩于其诱导核算子或平滑矩阵的主谱成分中；据此提出的 SCATE 框架通过训练紧凑神经网络直接学习主特征函数或左奇异向量的非线性映射，以显式固定且可预设的模型尺寸实现数个数量级压缩并逼平原集成性能。
方法详解¶
整体框架¶
本文构建了从统计算子理论到边缘模型压缩的完整闭环。整体流程始于对已训练树集成模型（随机森林或梯度提升机）线性平滑算子的提取：对于随机森林，利用叶节点指示重叠构建双随机对称正定经验核矩阵 \(\hat{\bm{K}}\)；对于梯度提升机，依据串行拟合残差的递归补偿机制显式构造经验平滑矩阵 \(\hat{\bm{S}}\)。随后，算法计算算子的低秩截断谱分解（截断至前 \(P\) 个主成分），提取承载主要方差与预测信息的谱特征标靶。最后，通过谱集成自适应压缩算法（SCATE），利用紧凑多层感知机（MLP）拟合从输入特征到主谱方向的非线性连续映射，在推理阶段完全摆脱树结构的序列分支跳转，转为快速的矩阵向量乘法。
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["表格训练数据<br/>X ∈ R^{N×d}, y ∈ R^N"] --> B["训练基础树集成模型<br/>自适应划分随机森林 / 梯度提升机"]
B --> C["平滑算子矩阵构造<br/>双随机对称核 K 或 递归残差补偿平滑矩阵 S"]
C --> D["低秩算子截断谱分解<br/>保留前 P 阶特征值与特征向量 / 奇异系统"]
D --> E["SCATE 谱特征映射拟合<br/>谱加权 MSE 结合软正交正则化"]
E --> F["定额轻量神经模型编译<br/>显式固定尺寸 MLP + 预计算投影系数 c"]
F --> G["资源受限边缘部署<br/>向量化矩阵并行推理替代串行分支"]关键设计¶
1. 自适应随机森林的极小化极大最优收敛速率：确立谱衰减对统计速率的支配作用
为化解传统非参数回归假定输入空间均匀测度导致维数灾难的困境，理论部分在树划分服从诚实性（Honesty）、子采样（Subsampling）、特征覆盖度（Inclusion）及样本均衡度（Balance）常规温和假设下，引入源条件（Source condition）与特征值多项式衰减假定 \(\lambda_i \asymp i^{-\beta}\)（其中 \(\beta > 1\)）。误差分解表明模型预测均方误差受控于偏差（Bias）、算子估计误差（Operator error）与标签方差（Variance）三项之和： $$ \mathbb{E}\big[|f^* - \hat{f}|{L^2}^2\big] \lesssim \underbrace{M^{-2\alpha\beta}}}^2} + \underbrace{\frac{M}{N^{(b)}}{\text{operator error}} + \underbrace{\frac{M}{N^{(b)}}} $$ 通过在单树叶节点数 }\(M\) 与子样本规模 \(N^{(b)} \asymp N\) 之间进行渐近权衡，取最优叶节点增长率 \(M \asymp N^{1/(2\alpha\beta+1)}\)，上界收敛速率达到 \(N^{-2\alpha\beta/(2\alpha\beta+1)}\)。结合高频扰动块上的广义 Fano 不等式推导下界，证明该收敛速率在所界定的谱椭球源类上达到严格的极小化极大最优，首次在理论上证实了自适应划分能自发对齐数据的低维稀疏流形结构。
2. 树集成的线性平滑算子与双向谱表征：统一核机器与梯度提升
传统观点常将随机森林与梯度提升机视为运作机理迥异的两套算法，但本文从线性平滑器形式 \(f(\bm{x}_0) = \sum_{i=1}^N w_i(\bm{x}_0) y_i\) 入手，揭示了两者的统一谱本质。随机森林的平滑权重天然诱导出对称半正定的再生核 \(\hat{k}_N^B(\bm{x}, \bm{x}')\)，其对应的积分算子可进行标准特征分解 \(\bm{K} = \bm{\Psi} \bm{\Lambda} \bm{\Psi}^\top\)。对于梯度提升机，由于基学习器是对前序集成的残差进行贪婪拟合，其平滑矩阵 \(\hat{\bm{S}}\) 必须通过递归引入残差修正矩阵 \(\hat{R}_b\) 来消解历史累积误差： $$ \hat{s}_{\mathrm{boost}, b}(\bm{x}0) = \hat{s}}, b-1}(\bm{x0) + \eta \bigl(\hat{s}}, b}(\bm{x0) - \hat{s}_0)\bigr) $$ 由此产生的 }, b}(\bm{x\(\hat{\bm{S}}\) 虽然丧失了对称性与正定性，但借助奇异值分解 \(\bm{S} = \bm{U} \bm{\Sigma} \bm{V}^\top\)，其右奇异向量表征了标签空间中集成响应最剧烈的方向，而左奇异向量则构成了预测空间的内蕴主轴，从而为两类异构集成模型奠定了统一的谱压缩理论基础。
3. SCATE 谱集成自适应压缩算法：带谱权重的正交正则化神经网络拟合
基于 Eckart-Young-Mirsky 低秩截断定理，仅保留前 \(P \ll N\) 阶主谱成分即可在 Frobenius 范数下保留原算子绝大部分能量。SCATE 算法将测试点 \(\bm{x}_0\) 处的推理重构为先通过紧凑神经网络预测 \(P\) 维连续特征向量 \(\hat{\psi}(\bm{x}_0)\) 或 \(\hat{u}(\bm{x}_0)\)，再与固定的预计算投影系数向量 \(\bm{c} := \bm{\Lambda}_P \bm{\Psi}_P^\top \bm{y}\) 作内积：\(f(\bm{x}_0) \approx \sum_{j=1}^P c_j \hat{\psi}_j(\bm{x}_0)\)。为解决传统神经特征估计方法（如 NeuralEF 严苛正交约束难收敛、NeuralSVD 嵌套损失复杂）在极小容量网络下表现糟糕的问题，SCATE 采用带 SiLU 激活的微型多层感知机，提出谱加权均方误差配合软正交惩罚的联合优化目标： $$ \min_{g} \sum_{i=1}^{N} \sum_{j=1}^{P} \lambda_j^2 \big(g_j(\bm{x}_i) - \psi_j(\bm{x}i)\big)^2 + \gamma \mathcal{L} $$ 通过显式以特征值平方 }\(\lambda_j^2\)（或奇异值平方 \(\sigma_j^2\)）加权，强迫容量极为有限的小网络优先捕捉承载最高方差的主频信号，而将正交性松弛为 Gram 矩阵非对角线惩罚项 \(\mathcal{L}_{\text{ortho}}\)（权重设为 \(\gamma = 0.001\)）。这使得即便是仅有十余个神经元的超微网络亦能稳定重构关键预测流形。
4. 硬件受限下的严格模型定额控制：击穿率失真帕累托前沿
传统树剪枝方法（如 LOP 或 ForestPrune）的核心缺陷在于以设定误差容限为输入，输出模型的物理体积由剪枝过程自发决定，工程落地时极易超出演入式闪存上限。SCATE 彻底反转了控制逻辑：由于推理期仅需部署该微型 MLP 及长度为 \(P\) 的系数向量 \(\bm{c}\)，模型的参数量与物理体积完全取决于网络层深和层宽。在面向微控制器的 10KB 与 100KB 严苛内存预算下，SCATE 允许工程师直接根据芯片剩余闪存显式指定网络规格，一举解决了边缘计算内存超限风险，并在率失真（Rate-Distortion）曲线上全线压制依赖直接模仿树输出的浅层直接蒸馏及参数受限随机森林基线。
损失函数 / 训练策略¶
SCATE 采用 Adam 优化器训练 200 个 epoch，并使用 SiLU 激活函数以保证特征映射的光滑逼近能力。主成分截断阶数通常固定为 \(P=50\)，在网络容量、特征信息量与学习难度之间取得最佳平衡。在面对超大规模训练集导致 \(\mathcal{O}(N^2)\) 核矩阵存储与截断分解耗时过高时，算法可结合随机化 SVD 或 Nyström 采样；实验证明将训练集子采样至 10,000 个样本即可在完全不损失蒸馏精度的前提下消解该计算瓶颈。针对二分类任务中的 GBM，通过以均方误差损失拟合连续伪标签的方式输出线性概率，从而无缝兼容平滑矩阵的谱构造。
实验关键数据¶
主实验¶
实验对 SCATE 及其前置剪枝混合体 FP-SCATE 与主流剪枝算法（ForestPrune/FP、LOP）、规则提取方法（FIRE、TreeExtract/TE）及决策桩蒸馏（SSF）在 15 个公开数据集上进行了全面基准比对。模型大小统一严格对齐到微控制器级别的 10KB 与 100KB 物理存储限制。回归任务采用判定系数 \(R^2\) 评估，二分类任务采用准确率（Accuracy）评估。
表 1 展示了随机森林（RF，基模型配置 250 棵树，最大深度 15）在 10KB 与 100KB 存储预算下的压缩表现（摘选部分代表性数据集，10 次独立试验平均）：
| 数据集 | 任务类型 | 原始 RF 表现 | FP (10KB / 100KB) | LOP (10KB / 100KB) | FIRE (10KB / 100KB) | SCATE (10KB / 100KB) | FP-SCATE (10KB / 100KB) | 结论与增益 |
|---|---|---|---|---|---|---|---|---|
| abalone | 回归 (\(R^2\)) | 0.55 | 0.35 / 0.53 | 0.50 / 0.51 | 0.28 / 0.28 | 0.56 / 0.57 | 0.54 / 0.55 | 10KB 下超越全量 RF，较 LOP 提升 0.06 |
| adult | 分类 (Acc) | 0.85 | 0.79 / 0.84 | 0.83 / 0.83 | 超时 / 超时 | 0.84 / 0.85 | 0.83 / 0.85 | 10KB 下逼平全量 RF，FIRE 出现计算超时 |
| banknote | 分类 (Acc) | 0.99 | 0.87 / 0.92 | 0.99 / 0.99 | 0.99 / 0.99 | 1.00 / 1.00 | 1.00 / 1.00 | 10KB 即可无损复原 100% 完美分类准确率 |
| boston | 回归 (\(R^2\)) | 0.85 | 0.60 / 0.80 | 0.80 / 0.82 | 0.68 / 0.69 | 0.78 / 0.81 | 0.79 / 0.83 | FP-SCATE 在两档容量下均逼近原模型 0.85 |
| california | 回归 (\(R^2\)) | 0.80 | 0.45 / 0.68 | 0.68 / 0.74 | 超时 / 超时 | 0.70 / 0.75 | 0.71 / 0.74 | 相比 FP (0.45) 提升显著，基线规则法均超时 |
| concrete | 回归 (\(R^2\)) | 0.91 | 0.50 / 0.76 | 0.74 / 0.86 | 0.73 / 0.75 | 0.80 / 0.86 | 0.82 / 0.86 | 谱衰减较慢数据集中仍显著优于常规剪枝 |
| friedman_1 | 回归 (\(R^2\)) | 0.85 | 0.47 / 0.74 | 0.76 / 0.82 | 0.48 / 0.49 | 0.82 / 0.86 | 0.81 / 0.86 | 100KB 下超越原模型 0.85，达 0.86 |
| 全集平均排名 | 综合排位 | - | 4.80 / 4.40 | 3.47 / 4.33 | 6.57 / 4.85 | 1.77 / 1.93 | 2.03 / 2.47 | SCATE 在两档预算下平均排名均位居全场第一 |
表 2 展示了梯度提升机（GBM，基模型配置 100 棵树，最大深度 6）在两档严格内存预算下的压缩性能对比：
| 数据集 | 任务类型 | 原始 GBM 表现 | FP (10KB / 100KB) | LOP (10KB / 100KB) | TE (10KB / 100KB) | FIRE (10KB / 100KB) | SCATE (10KB / 100KB) | 全景优劣 |
|---|---|---|---|---|---|---|---|---|
| abalone | 回归 (\(R^2\)) | 0.53 | 0.44 / 0.53 | 0.50 / 0.52 | 0.54 / 0.55 | 0.47 / 0.47 | 0.56 / 0.57 | 10KB 下超越原 GBM，表现稳居首位 |
| adult | 分类 (Acc) | 0.85 | 0.82 / 0.85 | 0.84 / 0.85 | 0.85 / 0.86 | 0.81 / 0.81 | 0.85 / 0.85 | 保持与全量集成高度一致的高分类精度 |
| banknote | 分类 (Acc) | 0.98 | 0.95 / 0.99 | 0.98 / 0.98 | 0.99 / 1.00 | 0.98 / 0.98 | 1.00 / 1.00 | 10KB 预算下达到完全准确率 1.00 |
| california | 回归 (\(R^2\)) | 0.83 | 0.58 / 0.80 | 0.76 / 0.82 | 0.79 / 0.79 | 0.75 / 0.75 | 0.71 / 0.79 | 100KB 下逼近原集成性能基线 |
| concrete | 回归 (\(R^2\)) | 0.92 | 0.71 / 0.90 | 0.83 / 0.91 | 0.87 / 0.92 | 0.84 / 0.84 | 0.79 / 0.88 | 极度紧凑 10KB 下承压，100KB 下快速恢复 |
| friedman_1 | 回归 (\(R^2\)) | 0.91 | 0.68 / 0.90 | 0.87 / 0.90 | 0.92 / 0.92 | 0.79 / 0.79 | 0.89 / 0.97 | 100KB 下大幅超越原始未压缩 GBM (0.91) |
| 全集平均排名 | 综合排位 | - | 5.13 / 2.57 | 3.27 / 3.80 | 2.47 / 2.80 | 3.87 / 5.33 | 2.13 / 2.13 | SCATE 在 GBM 压缩基准中全线蝉联第一 |
消融实验¶
表 3 评估了不同特征函数神经估计器在相同容量限制下学习随机森林谱映射的消融结果（以判定系数 \(R^2\) 或准确率呈现，含标准差）：
| 数据集 | 任务类型 | 原始 RF | NeuralEF (10KB / 100KB) | NeuralSVD (10KB / 100KB) | SCATE (10KB / 100KB) | 消融机理分析 |
|---|---|---|---|---|---|---|
| auto_mpg | 回归 (\(R^2\)) | 0.69 | 0.086 / 0.192 | 0.237 / 0.320 | 0.453 / 0.497 | 严苛正交约束严重消耗小网络容量，SCATE 谱加权优势明显 |
| bc | 分类 (Acc) | 0.96 | 0.732 / 0.881 | 0.804 / 0.949 | 0.984 / 0.987 | SCATE 在 10KB 即可超越原模型，NeuralEF 出现明显欠拟合 |
| boston | 回归 (\(R^2\)) | 0.85 | 0.149 / 0.149 | 0.220 / 0.252 | 0.775 / 0.814 | 竞争方法在受限宽度下难以解耦高阶模式，性能大幅坍塌 |
| diabetes | 分类 (Acc) | 0.76 | 0.654 / 0.654 | 0.658 / 0.660 | 0.786 / 0.794 | SCATE 凭借软正交惩罚获得最佳模式多样性与重构精度折中 |
| student | 回归 (\(R^2\)) | 0.85 | 无法收敛 / 0.134 | 0.116 / 0.337 | 0.854 / 0.857 | 谱衰减极快的数据集上，SCATE 仅凭主频即无损复原原模型 |
| 平均排名 | 算法排位 | - | 3.00 / 3.00 | 2.00 / 2.00 | 1.00 / 1.00 | SCATE 在 10KB 和 100KB 预算下以绝对优势取得全胜 |
关键发现¶
- 压缩比与性能权衡：在 10KB 限制下，随机森林压缩比达到约 \(10^3\) 倍，梯度提升机压缩比达 \(10^2\) 倍。SCATE 不仅没有发生严重精度崩溃，反而在 abalone、banknote、friedman_1 等多个数据集上因滤除尾部噪声特征向量而取得高于未压缩原始集成的预测表现。
- 谱衰减速率主导可压缩性：在谱衰减剧烈的数据集（如 student）上，SCATE 仅需保留前 20 维主特征函数即可达到 Oracle 理论性能下界；而在衰减较为缓慢的数据集（如 concrete）上，则需依赖更深网络（如 4 层 128 宽）逐步吸收长尾信息。
- 直接模仿蒸馏与谱蒸馏的质的差距：直接训练同等结构的小 MLP 去模仿树集成的输出硬标签或连续预测（Naïve Distillation），其率失真帕累托前沿被 SCATE 全面压制。核特征向量充当了连续的高维“软监督信号”，其信息丰富度远胜树输出的标量预测。
- 假设检验与算法鲁棒性：经验特征值拟合表明，并非所有真实数据集均严格满足理论推导所需的 \(\beta > 1\) 多项式衰减；然而即便在 \(\beta < 1\) 的数据集上，SCATE 依旧维持了极具竞争力的压缩效果，表明定理 4.1 中的谱衰减假设是保证极小化极大收敛的充分非必要条件。
亮点与洞察¶
- 解决长期悬而未决的理论难题：首次为采用贪婪自适应划分的经典随机森林算法建立了严密的极小化极大最优收敛速率，阐明了自适应树集成通过核特征值衰减隐式契合低维流形稀疏信号的数学机制。
- 打通异构集成的统一谱表征：突破了传统仅将随机森林视为核方法的狭隘局限，通过残差递归构造平滑矩阵并将奇异值分解引入梯度提升机，为现代非对称树集成构建了统一的算子理论基石。
- 将连续谱分析转化为工程定额压缩工具：颠覆了传统剪枝方法“设误差容限、体积不可控”的弊端，SCATE 允许在微控制器部署前显式指定物理模型尺寸，且在推理期将树分支逻辑编译为硬件高度友好的矩阵向量乘法。
局限与展望¶
- 理论覆盖范围局限：目前的极小化极大收敛速率定理仅适用于随机森林回归任务；梯度提升机由于平滑矩阵非对称且各基学习器存在复杂的级联残差依赖，尚无法直接纳入再生核希尔伯特空间（RKHS）理论框架。
- 两阶段计算与分解开销：离线构造经验核矩阵与平滑矩阵的时间复杂度为 \(\mathcal{O}(N^2)\)，截断特征分解为 \(\mathcal{O}(N^2 P)\)。尽管子采样至 10,000 样本能有效缓解，但对百万级样本工业流式数据的在线压缩仍具挑战。
- 树结构固有可解释性的丧失：将离散树规则编译为黑盒连续多层感知机后，树模型引以为傲的单路径规则抽取、布尔决策链与形式化验证特性被不可逆地剥离。
相关工作与启发¶
- vs Mondrian Forests / Tessellation Forests [56, 58]: 早期实现极小化极大速率的树集成工作均强制采用完全随机或非自适应的斜向划分规则，无法解释工程实践中贪婪纯度划分的真实威力；本文首次在保留贪婪自适应划分特性的前提下完成了严格证明。
- vs LOP [25] / ForestPrune [52]: 现有顶级剪枝算法通过整树/子树级别的 \(L_1\) 正则化去除冗余节点，本质上仍输出树结构且模型大小受超参数间接影响；SCATE 直接学习算子连续基底，具备显式预算可控性与 GPU/MCU 硬件向量化友好性。
- vs NeuralEF [24] / NeuralSVD [62]: 既有神经算子谱分解方法侧重于高精度数学重构与严苛正交约束，在微型网络架构下收敛困难；SCATE 采用谱加权均方误差配合软正交惩罚，实现了低秩重构保真度与小模型容量的最佳匹配。
评分¶
- 新颖性: ⭐⭐⭐⭐⭐ 首次证明自适应随机森林的极小化极大最优性，并首创基于核算子与平滑矩阵谱分解的树集成模型压缩框架。
- 实验充分度: ⭐⭐⭐⭐⭐ 涵盖 15 个基准数据集、万次级实验评估，完整覆盖随机森林与梯度提升机，消融严谨且基线完备。
- 写作质量: ⭐⭐⭐⭐⭐ 数学证明严谨规范，机理阐述与实验设计逻辑自洽，图表信息高度浓缩。
- 价值: ⭐⭐⭐⭐⭐ 为表格学习理论与资源受限微控制器部署架设了坚实桥梁，在边缘计算与理论机器学习领域具备极高参考价值。