跳转至

Exogenous Randomness Empowering Random Forests

作者: Tianxing Mei, Yingying Fan, Jinchi Lv
来源: JMLR
主题: 非参数 / 半参数
相关性: 6/10
机构绿灯: University of Southern California(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv


一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是:在随机森林(Random Forests, RF)中,与训练数据无关的外生随机性(exogenous randomness)——具体指特征子采样(feature subsampling)和分裂时的随机平局打破(tie-breaking)——如何影响集成估计器的预测性能(以全局均方误差 MSE 衡量)? 该子方向属于非参数回归中"划分估计器(partitioning estimator)集成方法"的理论分析,其成熟度处于"对特定简化模型(如纯随机森林、Mondrian 森林)已有较深入理解,但对更一般的划分规则(尤其是 CART 类)仍缺乏系统性理论"的阶段。本文试图通过建立非渐近 MSE 展开式,将外生随机性的作用机制(偏差-方差分解、交叉划分协方差)刻画清楚。

发展脉络(history)

作者在引言中勾勒的领域地图大致如下:

  • 奠基工作:Breiman (2001) 提出随机森林算法,其核心创新即特征子采样(每步分裂随机选取 ⌈γd⌉ 个特征),但缺乏理论解释。早期理论工作(Biau, 2012; Scornet et al., 2015)开始分析简化版 RF(如纯随机划分)的一致性,但未触及特征子采样的具体作用。
  • 主要进展:后续工作通过引入特定外生随机性来获得可处理的理论模型——
  • Mondrian 森林(Mourtada et al., 2020; Cattaneo et al., 2024):将划分过程建模为指数时钟驱动的 Mondrian 过程,获得精确的有限样本风险界;
  • 纯随机森林 / 中心森林(Klusowski, 2021):分析完全随机划分的估计器,得到显式偏差-方差分解;
  • CART 类分析(Klusowski, 2020; Chi et al., 2022):证明样本 CART 与总体 CART 在充分分裂条件下渐近等价,为分析数据依赖划分提供桥梁;
  • 高维稀疏线性模型(Klusowski and Tian, 2024):在稀疏线性回归下给出 RF 的预测风险界,并引入"充分不纯度下降"(SID)条件。
  • 当前 frontier:作者指出,已有工作大多分别处理"特征子采样"或"平局打破",且多依赖特定划分规则(如 Mondrian)。本文的定位是:在一般划分规则框架下,同时纳入两类外生随机性,给出统一的非渐近 MSE 展开,并揭示其各自的贡献。
  • 本文的位置:作者将本文置于"理解 RF 为何优于单棵树"的理论链条上,特别强调其与 Liu and Mazumder (2024) 和 Curth et al. (2024) 的实证/启发式研究的区别——后者主要提供经验证据(RF 可同时降低偏差和方差),本文则提供严格的数学刻画。

子线索聚类

被引文献大致落在三条子线索上:

  1. 划分估计器的渐近理论(Biau, 2012; Scornet et al., 2015; Scornet, 2016; Wager and Athey, 2018):关注 RF 的一致性、渐近正态性,以及基于"诚实树"的推断。这类工作通常假设划分规则满足某种"充分细化"条件,但不精细刻画外生随机性的作用。
  2. 特定随机划分模型的可处理分析(Mourtada et al., 2020; Klusowski, 2021; Cattaneo et al., 2024):通过将划分过程随机化(Mondrian、均匀随机划分),获得精确的有限样本风险表达式。这类工作证明了"外生随机性有助于方差降低",但结论依赖于特定划分分布。
  3. CART 类划分的样本-总体等价性(Klusowski, 2020; Chi et al., 2022; Klusowski and Tian, 2024):证明在足够数据下,样本 CART 的划分行为接近总体 CART,从而可将数据依赖的划分近似为"近乎确定"的划分,为分析真实 RF 提供桥梁。本文的定理 5 和定理 8 正是在此基础上,将外生随机性(特征子采样、平局打破)作为独立于数据的随机源来建模。

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

  1. 外生随机性如何同时影响偏差和方差? 传统观点认为随机化只降方差、增偏差;本文的核心发现之一是特征子采样可以同时降低偏差和方差(通过减少不同树之间共享的未分裂特征,从而降低交叉协方差)。
  2. 集成估计器何时比单棵树更优? 本文通过 MSE 展开式指出,森林的优势来源于交叉划分协方差项(cross-partition covariance)的降低,而这正是外生随机性(尤其是特征子采样)的贡献。
  3. 一致性需要什么条件? 定理 5 给出了单棵树和森林一致的充要条件:单棵树需要划分足够细(偏差→0)且每格样本量足够大(方差→0);森林则允许单棵树不一致(划分较粗),只要集成后的"平均划分"足够好。
  4. 维度灾难如何被外生随机性缓解? 作者在 Remark 12 中提出"维度祝福"(blessing of dimensionality):在高维浅树(l/d → 0)情形下,特征子采样使得不同树倾向于在不同特征上分裂,从而降低树间相关性,方差项随 d 增大而减小。

⚠️ 作者的 framing(这是作者的说法)

作者将本文的贡献框架为"外生随机性赋能随机森林"(Exogenous Randomness Empowering Random Forests),其核心叙事是:RF 的成功不仅源于 bagging(对数据的重抽样),更源于划分过程中的外生随机性。作者刻意将"特征子采样"和"平局打破"统一为"外生随机性"这一概念,并强调其与"数据内生随机性"(如 bootstrap)的本质区别。这一 framing 使得本文的理论框架可以覆盖多种 RF 变体(Mondrian、纯随机、CART),但也意味着作者淡化了样本 CART 中数据依赖划分的复杂性——他们明确承认(见引言最后一段)本文的框架不直接覆盖样本 CART,而是依赖 Chi et al. (2022) 的等价性结果作为桥梁。值得研究者注意:这一 framing 是否成立,取决于"总体 CART + 外生随机性"是否真的能捕捉样本 CART 随机森林的核心机制——这是一个可以亲自去验证的判断。

张力

未见明显的对立引用。但存在一个潜在张力:一方面,作者强调外生随机性(特征子采样)是 RF 成功的关键;另一方面,Mentran and Zhou (2020) 的"随机化作为正则化"(randomization as regularization)观点认为特征子采样的作用类似于隐式正则化(类似岭回归),而非纯粹的方差降低。本文的 MSE 展开式实际上兼容这两种解释(偏差-方差分解中的交叉协方差项可视为一种正则化效应),但作者没有明确讨论这一联系。这可以作为一个值得研究者去查的线索。


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

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

符号清单(按类别分组):

类别 符号 含义
数据 \(Z = \{(X_i, Y_i)\}_{1 \le i \le n}\) 训练样本,i.i.d. 来自 \((X, Y)\)
\(X = (X_1, \ldots, X_d)^\top \in \mathcal{X}^d\) 特征向量,各分量独立(本文关键假设之一)
\(Y \in \mathbb{R}\) 响应变量
\(\mu(x) = E[Y \mid X = x]\) 目标回归函数(待估对象)
\(\varepsilon\) 模型误差,\(E[\varepsilon \mid X] = 0\),\(\text{Var}(\varepsilon \mid X) = \sigma^2(X)\)
划分 \(\mathcal{P}\) \(\mathcal{X}^d\) 的一个有限划分(partition),由若干格(cell)组成
\(\mathcal{P}(\Theta)\) 由外生随机元素 \(\Theta\) 决定的随机划分
\(\mathcal{P}_x(\Theta)\) 包含点 \(x\) 的格
\(N_x(\Theta)\) 格 \(\mathcal{P}_x(\Theta)\) 中的训练样本数
$ \mathcal{P}(\Theta)
估计器 \(\hat{\mu}_{\text{part}}(x; Z, \mathcal{P}(\Theta))\) 单棵树的划分估计器(格内样本均值)
\(\hat{\mu}_{\text{ens}}(x; Z, \mathcal{P}(\Theta_{1:B}))\) 森林估计器(B 棵树的平均)
外生随机性 \(\Theta\) 外生随机元素,独立于训练数据 \(Z\)
\(\gamma \in (0,1]\) 特征子采样率(每步分裂随机选 ⌈γd⌉ 个特征)
\(l\) 树的深度(层数)
\(B\) 森林中树的棵数
性能度量 \(\text{MSE}(\hat{\mu})\) 全局均方误差,\(\text{MSE}(\hat{\mu}) = E_{X,Z,\Theta}[(\mu(X) - \hat{\mu}(X))^2]\)
核函数 \(K_\mu(P, P')\)、\(K_{\sigma^2}(P, P')\) 交叉划分协方差核(见公式 (8))
\(Q_\mu(P)\)、\(Q_{\sigma^2}(P)\) 单划分方差核(\(P = P'\) 时的特例)

模型设定(本文的核心假设):

  1. 加性噪声模型:\(Y = \mu(X) + \varepsilon\),其中 \(E[\varepsilon \mid X] = 0\),\(\text{Var}(\varepsilon \mid X) = \sigma^2(X)\)。
  2. 特征独立性:\(X_1, \ldots, X_d\) 相互独立(这是第 4 节 CART 分析的关键简化假设)。
  3. 划分规则独立于数据:\(\mathcal{P}(\Theta)\) 由外生随机元素 \(\Theta\) 决定,\(\Theta \perp Z\)。这排除了样本 CART(数据依赖划分),但覆盖了总体 CART、Mondrian、纯随机划分等。
  4. 有界性:\(\mu\) 和 \(\sigma^2\) 有界(用于控制余项)。

可观测数据:研究者实际能观测到的是训练样本 \(Z = \{(X_i, Y_i)\}_{i=1}^n\)。不可观测的是:目标函数 \(\mu\)、误差方差 \(\sigma^2\)、以及外生随机元素 \(\Theta\) 的具体实现(虽然研究者知道 \(\Theta\) 的分布,因为特征子采样和平局打破的规则是算法设定的)。

关键区分:本文的"可观测"与"不可观测"的界限非常清晰——\(\Theta\) 虽然是算法引入的随机性,但其分布是已知的(由 \(\gamma\)、\(l\) 等参数决定),因此理论上可以对 \(\Theta\) 求期望。这与因果推断中的"潜在结果"不同:\(\Theta\) 不是反事实,而是算法自身的随机种子。

第二步:最小内核

最小内核:考虑最简单的设定——二元特征、深度为 1 的树、无特征子采样(γ = 1)。

  • 设定:\(d = 1\)(只有一个特征),\(X \sim \text{Bernoulli}(1/2)\),\(\mu(x) = \beta x\)(线性),\(\sigma^2(x) = \sigma_0^2\)(同方差)。树深度 \(l = 1\),即只做一次分裂。由于只有一个特征,特征子采样无意义(γ = 1),但平局打破仍然存在:如果 \(\beta = 0\)(无信号),则所有分裂位置等价,需要随机打破平局。

  • 单棵树:划分 \(\mathcal{P}\) 将 \(\{0, 1\}\) 分成两个单点格 \(\{0\}\) 和 \(\{1\}\)。估计器为

    \[\hat{\mu}_{\text{part}}(x; Z, \mathcal{P}) = \frac{\sum_{i=1}^n Y_i \mathbb{I}\{X_i = x\}}{\sum_{i=1}^n \mathbb{I}\{X_i = x\}}, \quad x \in \{0, 1\}.\]
    即每个格内的样本均值。此时 MSE 的分解为:
    \[\text{MSE}(\hat{\mu}_{\text{part}}) = \underbrace{E_X[(\mu(X) - E[\hat{\mu}_{\text{part}}(X)])^2]}_{\text{偏差}^2} + \underbrace{E_X[\text{Var}(\hat{\mu}_{\text{part}}(X))]}_{\text{方差}}.\]
    由于划分是确定的(无外生随机性),偏差为 0(因为 \(\mu\) 在每个格内是常数),方差为 \(\sigma_0^2 / (n/2) = 2\sigma_0^2/n\)(每个格约有 \(n/2\) 个样本)。

  • 森林(B 棵树):由于 \(\gamma = 1\) 且 \(d = 1\),每棵树都做同样的分裂,因此 B 棵树完全相同,森林估计器等于单棵树。此时外生随机性为零,森林没有带来任何改进。

  • 加入平局打破:假设 \(\beta = 0\)(\(\mu \equiv 0\)),则所有分裂位置等价。若平局打破是随机的(例如随机选 \(X_1\) 或 \(X_2\) 作为分裂变量,虽然这里 \(d=1\) 不适用;更一般地,若 \(d > 1\) 且多个特征有相同不纯度下降),则不同树的划分可能不同。此时森林的 MSE 展开式中会出现交叉划分协方差项 \(K_\mu(P, P')\) 和 \(K_{\sigma^2}(P, P')\),它们度量两棵独立树的划分之间的重叠程度。这正是本文定理 4 的核心:森林的方差由"单树方差"(\(Q\) 项)和"交叉树协方差"(\(K\) 项)共同决定,而外生随机性通过降低 \(K\) 项来降低总方差。

为什么这个最小内核能体现核心思想:即使在这个最简单的设定中,也能看到本文的核心机制——外生随机性使得不同树的划分"去相关",从而降低集成估计器的方差。当 \(d = 1\) 且 \(\gamma = 1\) 时,没有外生随机性,森林退化为单棵树;当引入特征子采样(\(\gamma < 1\))或平局打破时,不同树的划分开始出现差异,交叉协方差项 \(K\) 变小,方差降低。本文的定理 4 和定理 5 正是将这个机制推广到一般划分规则,并给出了 MSE 的完整展开式。

一般设定下的核心数学问题:对于一般的划分规则 \(\mathcal{P}(\Theta)\),如何刻画

\[\text{MSE}(\hat{\mu}_{\text{ens}}) = \frac{B-1}{B} E_{X,\Theta,\Theta'}[K_\mu(\mathcal{P}(\Theta), \mathcal{P}(\Theta')) + K_{\sigma^2}(\mathcal{P}(\Theta), \mathcal{P}(\Theta'))] + \frac{1}{B} E_{X,\Theta}[Q_\mu(\mathcal{P}(\Theta)) + Q_{\sigma^2}(\mathcal{P}(\Theta))] + \text{remainder},\]
其中 \(K_\mu\)、\(K_{\sigma^2}\) 是交叉划分核,\(Q_\mu\)、\(Q_{\sigma^2}\) 是单划分核。本文的技术贡献在于:(i) 证明这个展开式对一般划分规则成立(定理 4);(ii) 给出余项的可控界;(iii) 在 CART 特殊设定下(第 4 节),将 \(K\) 和 \(Q\) 显式地表达为特征子采样率 \(\gamma\)、深度 \(l\)、稀疏度 \(s\) 和维度 \(d\) 的函数,从而揭示"维度祝福"和"最优 \(\gamma\)"等现象。


三、这篇论文做了什么

三句话

  1. 研究了什么问题:在训练数据独立的划分规则(含特征子采样和平局打破两类外生随机性)下,建立单棵树和随机森林估计器的非渐近全局 MSE 展开式,并给出两者一致的充要条件。
  2. 核心工具/方法:提出"先对训练数据取条件、再对外生随机性取期望"的条件偏差-方差分解,引入交叉划分核 \(K_\mu\)、\(K_{\sigma^2}\) 和单划分核 \(Q_\mu\)、\(Q_{\sigma^2}\) 刻画划分间的相互作用;在 CART 设定下,将问题转化为对马尔可夫链(二元/均匀 CART 过程)的期望计算。
  3. 主要结论:① 集成能同时降低偏差和方差,其机制是外生随机性降低交叉划分协方差;② 森林一致的条件比单棵树更弱(允许单棵树不一致);③ 在稀疏线性模型中,特征子采样率 \(\gamma\) 存在最优值 \(\gamma^\star \in (0,1)\),且高维(大 \(d\))有助于降低方差——"维度祝福";④ 平局打破本身(即使 \(\gamma = 1\))也能通过引入划分多样性来提升性能。

关键设定与假设

  • 划分规则:\(\mathcal{P}^n: \mathcal{D}^n \to \mathcal{P}\),其中 \(\mathcal{D}^n\) 是决策参数空间,\(\Theta \sim \text{Unif}(\mathcal{D}^n)\) 且 \(\Theta \perp Z\)。这排除了样本 CART,但覆盖总体 CART、Mondrian、纯随机划分。
  • 假设 1(X 的分布):\(X\) 有界密度,上下有界。这保证格的概率有界。
  • 假设 2(µ 的有界性):\(\|\mu\|_\infty < \infty\)。用于控制偏差项。
  • 假设 3(σ² 的有界性):\(\sigma^2\) 上下有界。用于控制方差项。
  • 假设 4(划分规则的正则性):每个格有正概率;不同划分可区分(distinguishable,见定义 2);\(\Theta\) 的支撑集 \(\mathcal{D}^n_\Theta\) 中任意两个划分可区分。这保证了核函数的良定义和 Cauchy-Schwarz 不等式的严格性。
  • 第 4 节额外假设:\(X_1, \ldots, X_d\) i.i.d.,稀疏线性模型 \(Y = \sum_{j=1}^s \beta_j X_j + \varepsilon\),且 \(\beta_j\) 互不相同(避免平局)。这些假设使得 CART 过程可显式分析。

相比已有文献的放宽/强化: - 放宽:不要求划分规则是"纯随机"或"Mondrian",而是允许一般的训练数据独立规则;不要求 \(\mu\) 光滑(仅需有界)。 - 强化:要求 \(\Theta \perp Z\)(排除样本 CART);要求特征独立(第 4 节);要求 \(\beta_j\) 互不相同(第 4 节,避免平局分析的复杂性)。

主要结果

定理 4(一般 MSE 展开):在假设 1–4 下,森林估计器的 MSE 可分解为:

\[\text{MSE}(\hat{\mu}_{\text{ens}}) = \underbrace{E_{X,\Theta,\Theta'}[(\mu(X) - E_Z[\hat{\mu}_{\text{ens}}(X)])^2]}_{\text{集成偏差}^2} + \underbrace{\frac{B-1}{B} E_{\Theta,\Theta'}[K_{\sigma^2}(\mathcal{P}(\Theta), \mathcal{P}(\Theta'))] + \frac{1}{B} E_\Theta[Q_{\sigma^2}(\mathcal{P}(\Theta))]}_{\text{方差项}} + R_{\text{ens}},\]
其中 \(K_{\sigma^2}\) 和 \(Q_{\sigma^2}\) 的定义见 (8)–(9),余项 \(R_{\text{ens}}\) 有界。关键点:交叉划分核 \(K_{\sigma^2}\) 度量两棵独立树的划分重叠程度,外生随机性通过降低 \(K_{\sigma^2}\) 来降低方差。

定理 5(一致性充要条件): - 单棵树一致 \(\iff\) \(E_{X,\Theta}[(\mu - \mu_{\mathcal{P}(\Theta)})^2] \to 0\) 且 \(E_\Theta[|\mathcal{P}(\Theta)|]/n \to 0\)。 - 森林一致 \(\iff\) \(E_X[(\mu - E_\Theta[\mu_{\mathcal{P}(\Theta)}])^2] \to 0\) 且 \(E_{\Theta,\Theta'}[K(\mathcal{P}(\Theta), \mathcal{P}(\Theta'))]/n \to 0\)。 直觉:森林允许单棵树"不够细"(偏差较大),只要集成后的平均划分足够好;方差条件也更弱(交叉核而非单划分核)。

定理 8/15(CART 显式展开):在稀疏线性模型下,MSE 展开式中的偏差和方差项可显式表达为 \(\gamma\)、\(l\)、\(s\)、\(d\) 的函数。关键结论: - 偏差项 \(\propto \sum_{j=1}^s \beta_j^2 (1 - \gamma)^{l+1}\)(二元特征)或 \((1 - 3\gamma/4)^l\)(均匀特征),随 \(\gamma\) 增大而减小。 - 方差项包含单树方差 \(2^l/n\) 和交叉树协方差 \(\rho_{l,d}(\gamma)/n\),其中 \(\rho_{l,d}(\gamma)\) 随 \(d\) 增大而减小(维度祝福),且关于 \(\gamma\) 呈 U 形。 - 最优 \(\gamma^\star \in (0,1)\) 存在,且随 \(d\) 增大而减小。

推论 11/19(显式速率):当 \(s = 1\) 时,森林的 MSE 上界为

\[\text{MSE}(\hat{\mu}_{\text{RF}}) \lesssim \frac{\beta_1^2}{4B}(1-\gamma)^l + \frac{\beta_1^2}{4}(1-\gamma)^{2l} + \frac{\sigma_0^2}{n}\left(\frac{2^l}{B} + \rho_{l,d}(\gamma)\right) + R',\]
其中 \(\rho_{l,d}(\gamma) = O(\exp(l^2/d))\) 在 \(l/d \to 0\) 时远小于 \(2^l\)。这清晰地展示了"维度祝福":高维使得交叉树协方差指数级小。

证明路线与技术技巧

整体路线(以定理 4 为例):

  1. 条件偏差-方差分解:先固定外生随机性 \(\Theta_{1:B}\),对训练数据 \(Z\) 取条件,得到条件偏差和条件方差;再对 \(\Theta_{1:B}\) 取期望。这与传统偏差-方差分解的区别在于期望的顺序——先 \(Z\) 后 \(\Theta\),使得交叉项可以分解为核函数的形式。
  2. 核函数引入:定义 \(K_\mu(P, P')\) 和 \(K_{\sigma^2}(P, P')\) 如 (8),利用 Cauchy-Schwarz 不等式(命题 3)给出交叉项的上界。关键技巧:将交叉协方差项写成两个划分的"重叠程度"的函数,从而将问题转化为对两个独立随机划分的期望计算。
  3. 余项控制:利用假设 1–3(有界性)和假设 4(可区分性),将余项 \(R_{\text{ens}}\) 分解为若干项,每一项都用 \(n^{-1}E[|\mathcal{P}|]\) 或 \(n^{-1}E[K]\) 控制。关键技巧:对格内样本数 \(N_x\) 的逆矩进行展开,利用二项分布的矩不等式。
  4. 一致性证明:从展开式出发,分别处理偏差项和方差项。关键技巧:偏差项用 Jensen 不等式和条件期望的塔性质;方差项用 Cauchy-Schwarz 不等式和核函数的正定性。

CART 分析的技术技巧:

  • 二元 CART 过程:将树生长建模为马尔可夫链,状态为"已分裂特征集合"。利用马尔可夫性质计算 \(E[\prod_{j=1}^s (1 - I_{lj})]\) 等量。
  • 均匀 CART 过程:利用泊松核和傅里叶分析,将 \(E[2^{-\sum \max\{J_{lj}, J'_{lj}\}}]\) 转化为积分形式,再通过鞍点近似得到速率。
  • 维度祝福的证明:通过精细的计数论证,证明 \(\rho_{l,d}(\gamma) \le 2^l \cdot \exp(-c l^2/d)\),从而在 \(l/d \to 0\) 时交叉协方差远小于单树方差。

真实例子与应用:本文为纯理论论文,没有真实数据实验。但包含理论指导的模拟(第 4.2 节):基于精确的 MSE 展开式(24)、(34),模拟马尔可夫过程来计算偏差、方差、交叉协方差等量,验证理论预测的 U 形 MSE 曲线和维度祝福现象。模拟设定为:\(d = 100\),\(s = 5\),\(n = 1000\),\(B = 100\),\(\sigma_0^2 = 1.69\),两种系数配置(等系数和不等系数)。模拟的作用是验证理论展开式的准确性,而非展示方法在真实数据上的优越性。

🔎 结论是否比证明窄

结论比证明窄的地方:

  1. 定理 5 的"充要条件":作者证明了在假设 1–4 下,条件 (21) 和 (22) 是充要的。但必要条件的证明依赖于假设 4(3)(可区分性),这一假设在实际中可能过强——例如,若两个划分仅在零测集上不同,则它们不可区分,但实际性能可能无差异。因此,充要条件仅在"可区分划分"这一受限类别中成立,不能直接推广到一般划分规则。
  2. CART 分析的"显式速率":推论 11 和 19 的速率上界是保守的(作者自己承认"the bound is conservative for both estimators, more so for the latter")。特别是,\(\rho_{l,d}(\gamma) = O(\exp(l^2/d))\) 的上界在 \(l\) 接近 \(d\) 时不再有效,而实际中 \(l\) 可能随 \(n\) 增长到接近 \(d\)。
  3. "维度祝福"的适用范围:作者在 Remark 12 中声称高维降低方差,但这一结论依赖于特征独立假设。如果特征相关,则"维度祝福"可能消失甚至变成"维度诅咒"。作者在正文中没有讨论这一限制。
  4. "平局打破"的分析:作者将平局打破作为 Type II 外生随机性,但没有给出平局打破单独作用的显式展开式。在定理 8 中,平局打破的效果被并入特征子采样效应中,无法分离。作者在附录 A.1 中通过模拟展示了平局打破的效应,但缺乏理论刻画。
  5. 样本 CART 的桥梁:作者依赖 Chi et al. (2022) 的等价性结果来连接总体 CART 和样本 CART,但这一等价性需要充分大的样本量和足够深度的树。在有限样本、浅树情形下,样本 CART 的行为可能与总体 CART 差异显著,本文的结论可能不适用。

值得研究者注意:作者在摘要和引言中声称"exogenous randomness empowers random forests",但证明的严格范围是"训练数据独立的划分规则 + 总体 CART"。对于实际中最常用的样本 CART 随机森林,本文的结论是间接的(通过 Chi et al. 2022 的桥梁),且桥梁的适用条件(大样本、深树)在实际中未必满足。这是一个值得亲自去验证的判断。


四、开放问题

以下开放问题均扎根于本文的具体语句:

  1. 样本 CART 的推广(扎根于引言最后一段:"It would be interesting to explore data-adaptive partitioning rules, particularly the sample CART splitting criterion")。本文的框架要求划分规则独立于训练数据,但实际 RF 使用样本 CART(数据依赖划分)。能否将本文的 MSE 展开式推广到样本 CART?这需要处理划分与数据的相关性,可能涉及更精细的浓度不等式。

  2. 特征相关情形(扎根于第 4 节的特征独立假设:"\(X_1, \ldots, X_d\) are i.i.d.")。本文的"维度祝福"结论在特征独立时成立。当特征相关时,特征子采样是否仍能降低交叉协方差?是否存在相关性阈值,超过该阈值后"维度祝福"消失?这需要建立特征相关性与 \(K_\mu\)、\(K_{\sigma^2}\) 之间的定量关系。

  3. 平局打破的独立效应(扎根于 Remark 9 和附录 A.1)。作者通过模拟展示了平局打破的效应,但未给出理论刻画。能否将 Type II 外生随机性的贡献从 Type I 中分离出来,给出单独的 MSE 展开式?这可能需要对平局打破的分布做更精细的建模。

  4. 最优 \(\gamma\) 的显式表达式(扎根于 Remark 13:"the optimal \(\gamma^\star \in (0,1)\)")。作者证明了最优 \(\gamma\) 的存在性,但没有给出闭式解。能否在更一般的模型(如非均匀特征分布、非稀疏 \(\beta\))下推导 \(\gamma^\star\) 的显式表达式?这需要更精细的偏差-方差权衡分析。

  5. 非渐近余项的精细刻画(扎根于定理 4 的余项 \(R_{\text{ens}}\))。作者给出的余项界是保守的("conservative")。能否改进余项界,使其在更宽的参数范围内(如 \(l\) 接近 \(d\)、\(n\) 较小时)仍然有效?这可能涉及更精细的逆矩不等式或 Stein 方法。

  6. 与 bagging 的交互(扎根于引言中对 bagging 的讨论)。本文排除了 bootstrap(样本维度的重抽样),只考虑特征维度的外生随机性。当 bootstrap 与特征子采样同时存在时,MSE 展开式如何变化?是否存在交互效应?这需要将本文的框架与 bagging 的理论(如 Bühlmann and Yu, 2002)结合。

提醒:要确认上述问题是否是真 gap,建议去读同一子领域近期约 5 篇论文的引言(例如:Tan et al., 2024 关于 merged-staircase property 的工作;Cattaneo et al., 2024 关于 Mondrian 森林推断的工作;以及 Liu and Mazumder, 2024 关于随机化偏差-方差权衡的实证研究)。如果这些论文的引言都指向同一个问题,那大概率是共识性的真 gap;如果它们各说各话,那可能只是本文作者的个人 framing,需要更谨慎地判断。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论