随机森林集成大小选择中基于三元组的高原搜索的平稳分布理论

# 基于三元组的高原搜索在随机森林集成规模选择中的平稳分布理论  
来源：https://arxiv.org/html/2606.30837  

\declaretheorem[name=命题]myproposition  
\declaretheorem[name=定理]mytheorem  

\name安德烈·M·朗热  
\[email protected]  
\addr斯科尔科沃科学技术研究院（Skoltech），莫斯科 121205，俄罗斯  
\addr俄罗斯科学院联邦研究中心“计算机科学与控制”（FRC CSC RAS），莫斯科 119333，俄罗斯  

###### 摘要  

树的数量是随机森林中的一个核心计算参数：增加树的数量会减少有限集成的变异性，但会增加训练和预测成本。基于高原的调参方法通过局部比较几何三元组树计数处的袋外分数来调整该参数。然而，在其余超参数稳定后，中心三元组点不一定收敛到一个确定值；相反，它会在一个平稳状态附近波动。本文为该过程发展了一种平稳分布理论。中心集成规模 \(B_t\) 被建模为几何网格上的生灭马尔可夫链，并通过局部平衡推导出它的平稳分布。在领先的中心折叠正态近似下，为原始更新规则和一种对称修改变体建立了平衡方程，这意味着当 \(\varepsilon\downarrow 0\) 时，平稳中心 \(B_* = O(\varepsilon^{-2})\)。平稳散布也被刻画。局部高斯近似和福克–普朗克解释给出了网格级别的方差常数。转换到集成规模尺度后，\(\sigma_{B,*} = O(\varepsilon^{-2})\)，而方差为 \(O(\varepsilon^{-4})\)。领先的相对散布与 \(\varepsilon\) 无关，并由尺度因子和更新规则控制。这些结果将基于高原的随机森林调参解释为一个随机过程，而非一个确定性停止规则。

**关键词：** 随机森林，集成规模选择，高原搜索，平稳分布，生灭马尔可夫链  

## 1 引言  

问题背景是基于 \(n\) 个观测值和 \(p\) 个输入特征的表格型数据的监督学习。在对分类变量进行标准预处理后，此类数据可由一个设计矩阵 \(X\in \mathbb{R}^{n\times p}\)（其行对应观测，列对应特征）以及一个目标向量 \(y\) 表示。基于树的集成方法在表格型数据中仍处于前沿地位，在许多基准研究中持续优于深度学习（Grinsztajn et al., 2022 (https://arxiv.org/html/2606.30837#bib.bib14)；Shwartz-Ziv and Armon, 2022 (https://arxiv.org/html/2606.30837#bib.bib30)；Borisov et al., 2024 (https://arxiv.org/html/2606.30837#bib.bib5)）。其中，梯度提升（Friedman, 2001 (https://arxiv.org/html/2606.30837#bib.bib12)；Chen and Guestrin, 2016 (https://arxiv.org/html/2606.30837#bib.bib8)）通常提供更优的预测精度，而随机森林（Breiman, 2001 (https://arxiv.org/html/2606.30837#bib.bib6)；Biau and Scornet, 2016 (https://arxiv.org/html/2606.30837#bib.bib4)）则提供更大的稳定性。这种稳定性源于对多个随机化树的平均：集成分数的蒙特卡洛分量随着树的数量增加而减小。树的独立性还支持并行训练以及使用袋外分数（OOB 分数），后者提供了无需交叉验证的内部性能估计。除了预测之外，随机森林还提供变量重要性度量（VIM），例如平均杂质减少度（MDI），这些度量自然地从树构建过程中产生（Breiman, 2001 (https://arxiv.org/html/2606.30837#bib.bib6)；Louppe et al., 2013 (https://arxiv.org/html/2606.30837#bib.bib25)）。这些 VIM 被广泛用于特征选择、网络推理和科学发现（Strobl et al., 2007 (https://arxiv.org/html/2606.30837#bib.bib31)；Kursa et al., 2010 (https://arxiv.org/html/2606.30837#bib.bib19)；Ewald et al., 2024 (https://arxiv.org/html/2606.30837#bib.bib11)）。然而，在高维设置下，对于具有相关特征的情况，稳定 VIM 可能需要比稳定预测分数本身显著更多的树（Lange et al., 2025 (https://arxiv.org/html/2606.30837#bib.bib20)；Tolosi and Lengauer, 2011 (https://arxiv.org/html/2606.30837#bib.bib32)）。因此，一个校准良好的预测分数是获得可信 VIM 的必要但不充分条件。这一观察强化了当前工作线的动机：在能够可靠评估变量重要性之前，必须首先获得一个具有稳定且足够准确预测性能的随机森林。

树的数量 \(T\) 因此是随机森林的一个核心计算参数。增加 \(T\) 会减少有限集成的变异性，但也会增加训练和预测成本。标准超参数优化（HPO）方法，例如 TPE（Bergstra et al., 2011 (https://arxiv.org/html/2606.30837#bib.bib2)）或 Hyperband（Li et al., 2018 (https://arxiv.org/html/2606.30837#bib.bib23)），要求用户指定一个搜索范围 \([T_{\min}, T_{\max}]\)。由于添加树不会引起许多其他超参数常见的过拟合行为，所以选定的 \(T\) 值倾向于被推向边界 \(T_{\max}\)。提高 \(T_{\max}\) 会将选定值进一步推向边界，无法保证所选边界是充分或计算高效的。早期停止启发式方法通过监测增量分数改进来避免显式的上界，但当 OOB 分数波动使得观测到的改进显得很小时，它们可能会提前停止。

在最近的一篇论文中，Porvatov et al. (2026 (https://arxiv.org/html/2606.30837#bib.bib28)) 引入了一种基于三元组的高原搜索过程，该过程无需固定的 \(T_{\max}\) 即可自适应树的数目。在每个 HPO 试验中，非 \(T\) 超参数以通常方式采样，而集成规模由一个几何三元组 \(L = B/\mathrm{sf}\)、\(B\) 和 \(R = B \cdot \mathrm{sf}\) 表示，具有固定的尺度因子 \(\mathrm{sf} > 1\)。这种几何构造使得相邻集成规模之间的相对分离大致恒定，因为 \(R - B = (\mathrm{sf} - 1) B\)，因此 \((R-B)/B = \mathrm{sf} - 1\)。这很重要，因为对于固定的加法步长 \(R = B + \Delta\)，当 \(B \to \infty\) 时，相对分离满足 \((R - B)/B = \Delta/B \to 0\)，使得相邻森林的 OOB 分数越来越难以区分。此类固定增量，例如 \(\Delta = 10\)，在早期的集成规模研究中被使用（Latinne et al., 2001 (https://arxiv.org/html/2606.30837#bib.bib21)；Lange et al., 2025 (https://arxiv.org/html/2606.30837#bib.bib20)）。因此，尺度因子 \(\mathrm{sf}\) 作为高原比较的分辨率参数。

森林被顺序训练到 \(R\) 棵树，并记录在 \(L\)、\(B\) 和 \(R\) 处的 OOB 分数。相对分数差距  
\[
d_L = \frac{|S_B - S_L|}{|S_B|}, \qquad d_R = \frac{|S_R - S_B|}{|S_B|}
\tag{1}
\]  
表明中心集成规模 \(B\) 接近高原区域的程度。将它们与用户指定的容差 \(\varepsilon\)（通常数量级为 \(10^{-3}\)）进行比较。如果两个不等式 \(d_L \leq \varepsilon\) 和 \(d_R \leq \varepsilon\) 都成立，则认为集成稳定但可能不必要地大，三元组在下一个试验中左移。在原始规则中，如果 \(d_R > \varepsilon\)，从 \(B\) 到 \(R\) 的改进仍高于容差，当前集成被视为不足；因此三元组右移。在原始规则的剩余情况中，\(d_L > \varepsilon\) 且 \(d_R \leq \varepsilon\)，三元组保持当前水平。下面也分析了一种对称的修改规则；在这种变体中，混合情况 \(d_L \leq \varepsilon, d_R > \varepsilon\) 被分配为停留决策，而不是原始规则中的右移。

本文的其余部分组织如下。第 2 节简要回顾相关文献。第 3 节阐述基于三元组的高原搜索框架及其随机更新规则。第 4 节发展平稳分布理论：首先在几何网格上将 \(B_t\) 建模为生灭马尔可夫链，然后导出平稳分布等式并进行缩放分析。第 5 节提供数值论证，第 6 节进行讨论。

## 2 相关文献

随机森林中树的数量选择问题已经被广泛研究。早期的工作通常依赖于启发式方法，例如固定一个足够大的 \(T\) 值（Breiman, 2001 (https://arxiv.org/html/2606.30837#bib.bib6)）或使用 OOB 误差的收敛诊断（Latinne et al., 2001 (https://arxiv.org/html/2606.30837#bib.bib21)）。更近的方法包括在给定预算下直接优化预测性能（Probst and Boulesteix, 2018 (https://arxiv.org/html/2606.30837#bib.bib27)），或通过分析树预测的方差来使用停止规则（Korting, 2020 (https://arxiv.org/html/2606.30837#bib.bib18)）。特别是，Lopes (2019 (https://arxiv.org/html/2606.30837#bib.bib24)) 提供了随机化集成估计量方差递减的严格渐近结果，建立了 Monte Carlo 分量 \(O(T^{-1})\) 的衰减率。这些理论结果支撑了许多实践中的停止标准。

在调参背景下，Bergstra et al. (2011) 的 TPE 和 Li et al. (2018) 的 Hyperband 等方法被广泛使用，但它们假设 \(T\) 有一个固定的搜索区间。高原搜索思路，如 Plateau Search 或基于置信区间的停止规则，已被用于神经网络的早期停止（Prechelt, 1998 (https://arxiv.org/html/2606.30837#bib.bib29)），但它们在随机森林中的系统应用较少。Porvatov et al. (2026 (https://arxiv.org/html/2606.30837#bib.bib28)) 的论文是首次为随机森林的树数量调参形式化一个基于三元组的自适应方法，并提供了初步的收敛性论证。

从理论上讲，本文的工作与马尔可夫链和生灭过程上的平稳分布理论相关（Norris, 1997 (https://arxiv.org/html/2606.30837#bib.bib27)）。将 \(B_t\) 建模为几何网格上的生灭链允许应用局部平衡条件。福克–普朗克解释（Risken, 1989 (https://arxiv.org/html/2606.30837#bib.bib29)）进一步将离散链与连续扩散联系起来，从而显式地给出分布尺度结果。

## 3 基于三元组的高原搜索

### 3.1 更新规则  

令 \(B_t\) 表示试验 \(t\) 时的中心集成规模。左和右邻点分别是 \(L_t = B_t / \mathrm{sf}\) 和 \(R_t = B_t \cdot \mathrm{sf}\)，其中 \(\mathrm{sf} > 1\) 是固定尺度因子。森林被顺序训练到 \(R_t\) 棵树，并且从 \(L_t\)、\(B_t\) 和 \(R_t\) 处观察到的 OOB 分数计算绝对相对差距 \(d_{L,t}\) 和 \(d_{R,t}\)，如 (1) 所示。更新规则是：

\[
B_{t+1} = \begin{cases} 
B_t \cdot \mathrm{sf}, & d_{L,t} > \varepsilon, \quad d_{R,t} > \varepsilon, \\[2.84526pt]
B_t, & d_{L,t} > \varepsilon, \quad d_{R,t} \leq \varepsilon, \\[2.84526pt]
B_t / \mathrm{sf}, & d_{L,t} \leq \varepsilon, \quad d_{R,t} \leq \varepsilon, \\[2.84526pt]
B_t \cdot \mathrm{sf} \ \text{（原始规则）或 } B_t \ \text{（修改规则）}, & d_{L,t} \leq \varepsilon, \quad d_{R,t} > \varepsilon.
\end{cases}
\]

因此，原始算法和下面考虑的修改变体的区别仅在于混合情况，即左侧高原检验通过而右侧高原检验失败的情况。修改规则将此情况分配为停留决策，这将导致马尔可夫模型中更对称的转移结构。

对于下面的分析，将 (1) 中的绝对差距视为其有符号对应项的绝对值是有用的：
\[
\frac{S_{B_t} - S_{L_t}}{S_{B_t}}, \qquad \frac{S_{R_t} - S_{B_t}}{S_{B_t}}.
\tag{2}
\]  
第一个量衡量从左邻点 \(L_t\) 到中心点 \(B_t\) 的局部分数变化，第二个量衡量从 \(B_t\) 到右邻点 \(R_t\) 的变化。由于 OOB 分数是随机的，即使数据和非 \(T\) 超参数固定，\(d_{L,t}\) 和 \(d_{R,t}\) 也是随机的。因此，\(B_t\) 的更新是随机的。明确的情况对应根据高原逻辑右移、停留或左移。剩余的混合情况可以分配给右移或停留决策。两种变体都在下面的马尔可夫公式中处理；区别仅影响转移概率，而不影响用于推导这些概率的渐近分数模型。

### 3.2 有符号差距方差渐近性  

使用 Porvatov et al. (2026 (https://arxiv.org/html/2606.30837#bib.bib28)) 中发展的有限集成渐近模型。在训练数据 \(D\) 条件下，令 \(\mu_T = \mathbb{E}[S_T \mid D]\) 表示具有 \(T\) 棵树的随机森林的期望 OOB 分数。假设条件均值分数按以下公式收敛到无限森林极限：
\[
\mu_T = S_\infty + c T^{-\gamma} + o(T^{-\gamma}), \quad T \to \infty,
\tag{3}
\]  
其中 \(S_\infty \neq 0\)，\(c \neq 0\)，\(\gamma > 0\)。在推导高原通过概率的中心折叠正态近似时，将在下面使用更强的条件 \(\gamma > 1/2\)。

方差计算遵循与 Porvatov et al. (2026 (https://arxiv.org/html/2606.30837#bib.bib28)) 中相同的有限集成高斯近似。然而，对于方差渐近性本身，只需要其二阶后果：算法方差的 \(O(T^{-1})\) 衰减以及嵌套热启动森林的协方差缩放，形式化于 (4)。(4) 中的方差分量由随机化集成估计量的有限集成方差结果驱动，特别是 Lopes (2019 (https://arxiv.org/html/2606.30837#bib.bib24)) 分析的 \(O(T^{-1})\) 衰减。(4) 中的协方差分量是一个额外的嵌套森林近似，专门针对高原算法使用的热启动构造：当 \(T_1 < T_2\) 时，具有 \(T_2\) 棵树的森林是通过在具有 \(T_1\) 棵树的森林上添加 \(T_2 - T_1\) 棵树构建的，因此 \(T_2\) 棵树森林的预测与其 \(T_1\) 棵树子森林的预测高度相关。

具体来说，对于 \(T > 1\)，令 \(v > 0\)。假设 (3) 和有限集成协方差缩放：
\[
\operatorname{Var}[S_T \mid D] \sim \frac{v}{T}, \quad \operatorname{Cov}[S_{T_1}, S_{T_2} \mid D] \sim \frac{v}{T_2}, \quad T_2 > T_1.
\tag{4}
\]  
则对于具有尺度因子 \(\mathrm{sf} > 1\) 的三元组，有符号相对差距的方差为：

**命题 3.1**（有符号差距方差渐近性）。设 \(L = B / \mathrm{sf}\)，\(R = B \cdot \mathrm{sf}\)，\(v > 0\)。则当 \(B \to \infty\) 时，
\[
\operatorname{Var}\left[\frac{S_B - S_L}{S_B} \;\middle|\; D\right] \sim \frac{v}{S_\infty^2} \frac{\mathrm{sf} - 1}{B},
\tag{5}
\]  
\[
\operatorname{Var}\left[\frac{S_R - S_B}{S_B} \;\middle|\; D\right] \sim \frac{v}{S_\infty^2} \frac{1 - \mathrm{sf}^{-1}}{B}.
\tag{6}
\]

(6) 中得出的右侧差距方差已在 Porvatov et al. (2026 (https://arxiv.org/html/2606.30837#bib.bib28)) 中推导。(5) 中的对应左侧差距方差在此通过相同的嵌套森林协方差论证推导；证明见附录 A (https://arxiv.org/html/2606.30837#A1)。两个表达式都需要，因为下面的马尔可夫模型同时使用左侧和右侧高原检验。(5) 和 (6) 之间的因子差异仅反映了左侧比较涉及较小的集成 \(L = B / \mathrm{sf}\)，其有限森林方差较大。它没有假定分数 \(S_L\)、\(S_B\) 和 \(S_R\) 本身之间的任何缩放关系。特别地，\((\mathrm{sf} - 1) / (1 - \mathrm{sf}^{-1}) = \mathrm{sf}\)，因此在嵌套协方差近似下，左侧有符号相对差距的渐近方差是右侧有符号相对差距方差的 \(\mathrm{sf}\) 倍。

### 3.3 绝对差距与高原通过概率  

实际高原规则使用 (2) 中有符号相对差距的绝对值。对于一般中心值 \(B\)，定义左侧和右侧高原通过概率为：
\[
\alpha_L(B; \varepsilon) = \mathbb{P}\left[\left|\frac{S_B - S_{B / \mathrm{sf}}}{S_B}\right| \leq \varepsilon \;\middle|\; D\right], \qquad \alpha_R(B; \varepsilon) = \mathbb{P}\left[\left|\frac{S_{B \cdot \mathrm{sf}} - S_B}{S_B}\right| \leq \varepsilon \;\middle|\; D\right].
\tag{7}
\]  
图 2 (https://arxiv.org/html/2606.30837#S3.F2) 给出了 \(\alpha_L(B; \varepsilon)\) 和 \(\alpha_R(B; \varepsilon)\) 的示意解释。阴影区域对应相应有符号相对差距落在容差区间 \([-\varepsilon, \varepsilon]\) 内的事件。该符号故意与分布无关：(7) 中的概率可以使用折叠正态近似、经验或自助近似，或其他用于 OOB 分数波动的模型进行评估。为了获得显式解析公式，现在施加比上述方差计算更强的近似。

命题 3.2 仅使用 (2) 中有符号差距的二阶渐近性，而下一个结果假设这些变换后的有符号相对差距本身近似服从高斯分布。

\{myproposition\}[高原通过概率渐近性] 设 \(L = B / \mathrm{sf}\) 且 \(R = B \cdot \mathrm{sf}\)，并令 \(s_L^2(B)\) 和 \(s_R^2(B)\) 分别表示 (5) 和 (6) 中的领先方差尺度。假设有符号相对差距允许条件高斯近似：
\[
\frac{S_B - S_L}{S_B} \mid D \approx \mathcal{N}(m_L(B), s_L^2(B)), \qquad
\frac{S_R - S_B}{S_B} \mid D \approx \mathcal{N}(m_R(