Smoothing and adaptation of shifted Pólya tree ensembles¶
作者: Thibault Randrianarisoa
来源: Bernoulli
主题: 非参数 / 半参数
相关性: 6/10
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本文研究的根本问题是非参数密度估计:给定来自未知概率密度函数 \( f \) 的独立同分布样本,目标是在某种损失(如 Hellinger 距离、\( L^1 \) 距离)下以最优速率估计 \( f \)。具体而言,本文关注的是基于树的贝叶斯方法(如 Pólya 树先验、BART)能否在任意 Hölder 光滑度 \( \alpha > 0 \) 的函数类上达到 minimax 最优后验收缩率。这个子方向当前的状态是:对于单棵树(如截断 Pólya 树),最优性仅对 \( \alpha \le 1 \) 成立;对于集成方法(如随机森林),频率派结果已对 \( \alpha \le 2 \) 成立,但贝叶斯集成方法(如 BART)的理论分析仍主要限于 \( \alpha \le 1 \)。本文试图填补这个缺口。
发展脉络¶
奠基工作:Pólya 树先验(Ferguson, 1974; Lavine, 1992)是贝叶斯非参数中一种经典的先验,通过递归划分区间并赋予 Dirichlet 分布来构造随机概率测度。其截断版本(truncated Pólya tree)在计算上更可行,但估计器是分段常数,因此只能逼近低光滑度函数。
主要进展(频率派集成方法): - Arlot & Genuer (2014) [1] 在回归框架下证明,纯随机森林(purely random forests)的偏差比单棵树衰减更快,且无限森林(\( M = \infty \))能达到比单棵树更优的风险率。关键点:该结果仅对 \( \alpha \le 2 \) 成立,且是频率派结果。 - Scornet et al. (2014) [5] 证明了 Breiman 原始随机森林在加性回归模型下的一致性。 - Mourtada et al. (2018) [22] 证明 Mondrian 森林在 Lipschitz 和二次可微回归函数(即 \( \alpha \le 2 \))上达到 minimax 最优率,且对任意维度成立。
主要进展(贝叶斯树方法): - Chipman et al. (2008) [3] 提出 BART(Bayesian Additive Regression Trees),将多个回归树的和作为模型,通过 MCMC 进行后验推断。BART 在实践中表现优异,但理论分析长期滞后。 - Ročková & Saha (2018) [21] 首次对 BART 的后验收缩率给出理论结果,但限于 \( \alpha \le 1 \) 的情形。 - Linero & Yang (2017) [12] 提出软决策树(soft decision trees)的贝叶斯版本,证明后验分布对稀疏函数和加性结构达到 minimax 率,但同样限于低光滑度。 - van der Pas & Ročková (2017) [24] 研究贝叶斯二元树(Bayesian dyadic trees),证明对分段常数函数达到近 minimax 率。
当前 frontier 与本文位置: - 频率派集成方法(随机森林、Mondrian 森林)已对 \( \alpha \le 2 \) 达到最优率,但贝叶斯树方法(单棵树或集成)的最优性证明仍卡在 \( \alpha \le 1 \)。 - 本文的核心贡献:提出一种移位 Pólya 树集成(shifted Pólya tree ensemble),证明其对任意 \( \alpha > 0 \) 的 Hölder 密度达到最优后验收缩率(至多对数因子),并给出自适应版本。这首次将贝叶斯树方法的最优性扩展到高光滑度情形。
子线索聚类¶
- 频率派随机森林理论:Arlot & Genuer (2014) [1]、Scornet et al. (2014) [5]、Scornet (2014) [16]、Mourtada et al. (2018) [22]。这些工作主要研究回归问题,证明一致性、渐近正态性或 minimax 最优率,但通常限于 \( \alpha \le 2 \)。
- 贝叶斯树与森林方法:Chipman et al. (2008) [3](BART)、Ročková & Saha (2018) [21](BART 理论)、Linero & Yang (2017) [12](软决策树)、van der Pas & Ročková (2017) [24](二元树)。这些工作主要关注后验收缩率,但最优性限于 \( \alpha \le 1 \)。
- Pólya 树及其变体:Hjort & Walker (2009) [23](分位数金字塔)、Randrianarisoa(本文)。Pólya 树是贝叶斯非参数中一种经典先验,本文通过集成策略扩展其光滑性。
- 树与神经网络的连接:Biau et al. (2016) [15](神经随机森林)、Yang et al. (2018) [11](深度神经决策树)。这些工作探索树与神经网络的混合模型,但理论结果仍限于一致性。
这个方向在追问的核心问题¶
- 贝叶斯树方法能否达到 minimax 最优率? 对于低光滑度(\( \alpha \le 1 \)),已有肯定答案;对于高光滑度(\( \alpha > 1 \)),此前是开放问题。
- 集成(森林)是否比单棵树更光滑? 频率派已证明(Arlot & Genuer, 2014),但贝叶斯框架下缺乏对应结果。
- 能否自适应于未知光滑度? 即无需知道 \( \alpha \) 即可达到最优率。已有贝叶斯混合高斯(Kruijer et al., 2010 [13])能做到,但树方法此前不能。
- 树方法在高维或稀疏设定下的表现? 部分工作(Linero & Yang, 2017 [12])已涉及,但本文限于一维。
已知瓶颈:单棵截断 Pólya 树的估计器是分段常数,因此其逼近误差(bias)只能以 \( O(2^{-J\alpha}) \) 衰减(\( J \) 为树深度),但方差项为 \( O(2^J / n) \)。平衡 bias-variance 后,最优率仅对 \( \alpha \le 1 \) 可达。集成方法通过平均多个移位树,可以降低 bias 的指数,从而扩展到更高 \( \alpha \)。
⚠️ 作者的 framing¶
作者将缺口 frame 为:“贝叶斯树集成方法在高光滑度函数类上的最优性尚未建立”。具体而言: - 作者在引言中明确说:“most positive optimality results on Bayesian tree-based methods assume that \( \alpha \le 1 \)”(第 2 页)。 - 作者将 Arlot & Genuer (2014) 的频率派结果(\( \alpha \le 2 \))作为 motivation,暗示贝叶斯版本应能匹配。 - 作者淡化/回避的竞争路线: - 贝叶斯混合高斯(Kruijer et al., 2010 [13])已能自适应任意 \( \alpha \),但作者仅在第 5 页提及,未深入比较。这可能是因为混合高斯方法不是树方法,与本文的“树集成”主题不同。 - 深度神经网络(Schmidt-Hieber, 2017 [4])也能达到任意光滑度的 minimax 率,但作者仅在第 2 页提及,未作为主要竞争。 - 什么明显该被引/该存在、却没出现在 intro 里? 作者未引用任何关于贝叶斯树方法在高维或稀疏设定下的理论结果(如 Linero & Yang, 2017 [12] 的稀疏自适应结果),尽管这些工作与本文的“自适应”主题相关。这可能是因为本文限于一维,但值得研究者去查:是否存在一维到高维的推广工作?
张力¶
未见明显对立引用。所有被引工作基本一致认为:单棵树的光滑性有限,集成可以提升光滑性;贝叶斯树方法的最优性此前限于 \( \alpha \le 1 \)。本文的结果与这一共识一致,只是将边界推到任意 \( \alpha \)。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据交代清楚¶
符号: - \( f \):未知的真实概率密度函数,定义在 \( [0,1) \) 上,属于 Hölder 类 \( \Sigma(\alpha, L) \)(\( \alpha > 0 \),\( L > 0 \))。Hölder 类定义:\( f \) 有 \( \lfloor \alpha \rfloor \) 阶连续导数,且第 \( \lfloor \alpha \rfloor \) 阶导数是 \( (\alpha - \lfloor \alpha \rfloor) \)-Hölder 连续的,Lipschitz 常数为 \( L \)。 - \( X_1, \ldots, X_n \):来自 \( f \) 的独立同分布样本。 - \( \Pi \):先验分布(在密度函数空间上)。 - \( \Pi(\cdot \mid X_1, \ldots, X_n) \):后验分布。 - \( \varepsilon_n \):后验收缩率,即存在常数 \( M > 0 \) 使得后验概率 \( \Pi( d(f, \hat{f}_n) > M \varepsilon_n \mid X_1, \ldots, X_n ) \to 0 \)(在 \( f \) 的真实分布下概率趋于 1),其中 \( d \) 是某种距离(Hellinger 或 \( L^1 \))。 - \( J \):树的深度(截断水平)。截断 Pólya 树将 \( [0,1) \) 递归二分到深度 \( J \),得到 \( 2^J \) 个等长区间。 - \( \theta_j \):移位参数,\( j = 1, \ldots, B \),每个 \( \theta_j \in [0,1) \)。移位后的区间划分是 \( [\theta_j + k/2^J, \theta_j + (k+1)/2^J) \)(模 1)。 - \( B \):集成中树的数量(森林大小)。 - \( \hat{f}_n \):后验均值或某个点估计器。
模型: - 数据生成机制:\( X_i \stackrel{i.i.d.}{\sim} f \),其中 \( f \) 是 \( [0,1) \) 上的概率密度函数。 - 统计模型:非参数,即 \( f \) 属于某个无穷维函数类(Hölder 类)。 - 先验:截断 Pólya 树先验,参数为深度 \( J \) 和 Dirichlet 分布的精度参数。具体地,在每个深度 \( m \le J \) 的区间上,将概率质量按 Dirichlet 分布分配到两个子区间。 - 要估的对象:\( f \) 本身。
可观测数据: - 可观测:\( X_1, \ldots, X_n \),每个是 \( [0,1) \) 上的一个点。 - 不可观测:\( f \) 本身,以及任何潜在结构(如 Hölder 光滑度 \( \alpha \))。
第二步:最小内核¶
最简特例:考虑 \( \alpha = 2 \)(即 \( f \) 有一阶连续导数,且导数 Lipschitz),且使用单棵截断 Pólya 树(\( B = 1 \),无移位)。
在这个特例下: - 树深度 \( J \) 将 \( [0,1) \) 分成 \( 2^J \) 个等长区间。 - 在每个区间上,估计器 \( \hat{f}_n \) 是常数(等于该区间内的经验频率除以区间长度)。 - 问题:这个分段常数估计器能否以 minimax 最优率估计一个 \( \alpha = 2 \) 的密度?
答案:不能。原因如下: - 偏差:对于 \( \alpha = 2 \) 的 \( f \),在每个长度为 \( 2^{-J} \) 的区间上,\( f \) 的变化是 \( O(2^{-2J}) \)(因为一阶导数是 Lipschitz,所以 \( f \) 近似线性,线性函数的积分误差是 \( O(2^{-2J}) \))。但分段常数估计的偏差是 \( O(2^{-J}) \)(因为用常数逼近线性函数,误差是区间长度的量级)。更精确地,bias² 是 \( O(2^{-2J}) \)。 - 方差:每个区间内有约 \( n/2^J \) 个样本,因此方差是 \( O(2^J / n) \)。 - 平衡:最小化 bias² + variance 得到 \( 2^{-2J} \asymp 2^J / n \),解得 \( 2^J \asymp n^{1/3} \),此时总误差为 \( O(n^{-1/3}) \)。 - Minimax 最优率:对于 \( \alpha = 2 \) 的 Hölder 类,minimax 最优率是 \( O(n^{-2/5}) \)(在一维密度估计中,minimax 率是 \( n^{-\alpha/(2\alpha+1)} \))。因此,单棵树的 \( n^{-1/3} \) 劣于最优率 \( n^{-2/5} \)。
本文的关键想法:通过平均 \( B \) 个移位的 Pólya 树,可以降低偏差。每个树的划分网格不同(通过随机移位 \( \theta_j \)),平均后,估计器不再是分段常数,而是分段线性(或更光滑)。具体地,对于 \( \alpha = 2 \),平均后的偏差可以降到 \( O(2^{-2J}) \),从而平衡后得到 \( 2^J \asymp n^{2/5} \),总误差 \( O(n^{-2/5}) \),达到最优率。
核心数学困难:证明平均后的偏差确实降低,且方差不因平均而增大太多(因为树之间是独立的,方差以 \( 1/B \) 衰减,但 \( B \) 可以取很大,如 \( B = n \))。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在 \( [0,1) \) 上的密度估计问题中,对于任意 Hölder 光滑度 \( \alpha > 0 \),构造一个贝叶斯树集成估计器(移位 Pólya 树集成),并证明其在 Hellinger 和 \( L^1 \) 距离下达到最优后验收缩率(至多对数因子)。
- 核心工具/方法:将多个截断 Pólya 树先验通过随机移位进行平均,形成集成先验;后验均值(或某个点估计)通过平均各树的后验得到。
- 主要结论:该集成估计器对任意 \( \alpha > 0 \) 达到最优后验收缩率 \( \varepsilon_n = n^{-\alpha/(2\alpha+1)} (\log n)^c \);此外,通过使用一个与 \( \alpha \) 无关的先验(如对树深度 \( J \) 赋予超先验),可以得到自适应版本,无需知道 \( \alpha \) 即可达到相同率。
关键设定与假设¶
完整设定(在第二节最小记号基础上补充): - 密度空间:\( f \in \Sigma(\alpha, L) \),Hölder 类,定义在 \( [0,1) \) 上。 - 先验:截断 Pólya 树先验 \( \Pi_J \),参数为深度 \( J \) 和 Dirichlet 精度参数 \( \gamma_m \)(在深度 \( m \) 处)。具体地,在每个深度 \( m \le J \) 的区间上,将概率质量按 Dirichlet(\( \gamma_m, \gamma_m \)) 分配到两个子区间。本文使用 \( \gamma_m = 2^{-m} \) 或类似衰减形式。 - 集成先验:\( \Pi_{\text{ens}} = \frac{1}{B} \sum_{j=1}^B \Pi_{J, \theta_j} \),其中 \( \theta_j \sim \text{Uniform}[0,1) \) 独立,\( \Pi_{J, \theta_j} \) 是移位后的截断 Pólya 树先验(划分网格为 \( [\theta_j + k/2^J, \theta_j + (k+1)/2^J) \))。 - 后验:给定数据 \( X_1, \ldots, X_n \),每个树的后验 \( \Pi_{J, \theta_j}(\cdot \mid X_1, \ldots, X_n) \) 是解析可得的(因为 Pólya 树是共轭先验)。集成后验是这些后验的平均。 - 点估计:后验均值 \( \hat{f}_n = \mathbb{E}_{\Pi_{\text{ens}}}[f \mid X_1, \ldots, X_n] \)。 - 损失:Hellinger 距离 \( h(f, g) = \left( \int (\sqrt{f} - \sqrt{g})^2 \right)^{1/2} \) 和 \( L^1 \) 距离 \( \|f - g\|_1 = \int |f - g| \)。
假设: - Hölder 光滑度 \( \alpha > 0 \) 是任意的,但先验不需要知道 \( \alpha \)(自适应版本)。 - 密度 \( f \) 有正的下界(即 \( \inf f > 0 \)),以避免边界问题。 - 树深度 \( J \) 随 \( n \) 增长,通常取 \( 2^J \asymp n^{1/(2\alpha+1)} \)(非自适应)或通过超先验选择(自适应)。
相比已有文献的放宽/强化: - 放宽:此前贝叶斯树方法的最优性限于 \( \alpha \le 1 \)(如 Ročková & Saha, 2018 [21]),本文放宽到任意 \( \alpha > 0 \)。 - 强化:本文的结果是后验收缩率(贝叶斯),而 Arlot & Genuer (2014) [1] 是频率派风险率。贝叶斯后验收缩率通常需要更强的技术(如先验质量条件、测试数构造)。 - 限制:本文限于一维 \( [0,1) \),而频率派随机森林结果(如 Mourtada et al., 2018 [22])对任意维度成立。
主要结果¶
定理 1(非自适应):设 \( f \in \Sigma(\alpha, L) \),且 \( \inf f > 0 \)。取树深度 \( J \) 满足 \( 2^J \asymp n^{1/(2\alpha+1)} \),集成大小 \( B \ge 1 \)(可取 \( B = n \) 或更大)。则存在常数 \( C > 0 \) 使得后验收缩率满足:
- 直觉:集成平均将偏差从 \( O(2^{-J}) \) 降到 \( O(2^{-J\alpha}) \)(因为移位平均相当于对每个区间内的 \( f \) 进行更高阶的逼近),方差为 \( O(2^J / n) \)(因为树之间独立,方差以 \( 1/B \) 衰减,但 \( B \) 足够大时方差由单棵树主导)。平衡得 \( 2^J \asymp n^{1/(2\alpha+1)} \),总误差 \( n^{-\alpha/(2\alpha+1)} \)。
- 必要条件:\( \inf f > 0 \) 是为了避免密度趋近 0 时 Hellinger 距离的退化行为。
- 解决的技术难点:证明平均后的偏差确实以 \( O(2^{-J\alpha}) \) 衰减。这需要对 Hölder 函数在移位网格上的逼近性质进行精细分析。
定理 2(自适应):设 \( f \in \Sigma(\alpha, L) \) 但 \( \alpha \) 未知。对树深度 \( J \) 赋予一个超先验(如 \( \pi(J) \propto 2^{-J} \) 或某个衰减形式),则后验收缩率仍为 \( n^{-\alpha/(2\alpha+1)} (\log n)^c \),无需知道 \( \alpha \)。
- 直觉:超先验允许数据自动选择最优深度 \( J \)。技术上是标准的“先验质量条件 + 测试数”论证(Ghosal et al., 2000)。
- 与已有自适应方法的对比:Kruijer et al. (2010) [13] 的贝叶斯混合高斯也能自适应,但本文是树方法。
证明路线与技术技巧¶
整体路线(3-5 步逻辑主干):
- 先验质量条件:证明集成先验 \( \Pi_{\text{ens}} \) 在真实 \( f \) 的 Hellinger 邻域内赋予足够大的质量。具体地,对任意 \( \varepsilon > 0 \),存在一个逼近 \( f_\varepsilon \)(如分段常数或分段多项式),使得 \( h(f, f_\varepsilon) \le \varepsilon \) 且 \( \Pi_{\text{ens}}(f: h(f, f_\varepsilon) \le \varepsilon) \ge e^{-n\varepsilon^2} \)(或类似下界)。这一步需要构造一个“筛子”(sieve)并计算先验质量。
-
关键技巧:利用移位平均,可以构造一个对 \( f \) 的 \( \alpha \)-阶逼近(如分段线性),而单棵树只能做到分段常数。先验质量的计算依赖于 Pólya 树的 Dirichlet 结构。
-
测试数构造:构造一个测试函数 \( \phi_n \)(基于数据),使得对远离 \( f \) 的密度 \( g \)(即 \( h(f, g) > \varepsilon \)),测试能以高概率拒绝 \( g \),且对 \( f \) 本身错误拒绝的概率很小。这是后验收缩率证明的标准步骤(Ghosal et al., 2000)。
-
关键技巧:使用 Hellinger 距离的测试数构造(如 Le Cam 引理或 Birgé 的测试数),结合集成估计器的结构。
-
后验收缩率不等式:应用 Ghosal et al. (2000) 的一般定理,将先验质量条件和测试数结合,得到后验收缩率 \( \varepsilon_n \)。这一步是标准的,但需要验证所有条件(如熵条件、先验质量下界)。
-
偏差-方差分解(核心创新点):证明集成估计器的偏差以 \( O(2^{-J\alpha}) \) 衰减。这需要分析移位平均的逼近性质:
- 对固定的 \( x \in [0,1) \),考虑 \( B \) 个移位网格。每个网格将 \( x \) 落入某个区间,该区间上的常数估计是 \( f \) 在该区间上的平均值。
- 平均后,\( \hat{f}_n(x) \) 是 \( f \) 在 \( B \) 个不同区间上的平均值的平均。由于移位是随机的,这些区间覆盖了 \( x \) 附近的一个邻域,因此平均相当于一个核估计(kernel estimator),其带宽为 \( 2^{-J} \)。
-
对于 \( \alpha \)-Hölder 的 \( f \),核估计的偏差是 \( O(2^{-J\alpha}) \)。作者通过泰勒展开和移位均匀性严格证明这一点。
-
方差控制:证明集成估计器的方差不超过 \( O(2^J / n) \)。由于树之间独立,方差以 \( 1/B \) 衰减,但 \( B \) 可以取任意大(如 \( B = n \)),因此方差由单棵树的方差主导。单棵树的方差是标准的 Pólya 树方差(每个区间内二项分布的方差)。
关键跳跃点: - 最吃功夫的引理:引理 3(或类似编号),证明移位平均后的偏差上界。难点在于:移位网格不是固定的,而是随机的,因此需要取期望。作者使用 Fubini 定理和 Hölder 条件,将期望转化为积分,然后利用泰勒展开的余项估计。 - 难点:如何将“平均多个分段常数估计”与“核估计”联系起来?作者通过引入一个辅助的“连续化”版本(如将分段常数视为某个核函数的离散化)来绕过。
技术技巧点名: - Pólya 树的共轭性:后验是解析可得的(Dirichlet 更新),因此后验均值可以显式计算。 - 移位平均:核心技巧,将分段常数估计转化为更光滑的估计。 - 先验质量条件 + 测试数:标准后验收缩率框架(Ghosal et al., 2000)。 - 泰勒展开与余项估计:用于偏差分析。 - 超先验:用于自适应版本,标准技巧(如对深度 \( J \) 赋予几何分布先验)。
真实例子与应用¶
本文为纯理论,无实证例子。作者在引言和结论中均未提及任何模拟或真实数据应用。所有结果都是理论性的(后验收缩率定理)。
🔎 结论是否比证明窄¶
- 窄结论:定理 1 和 2 的证明依赖于 \( \inf f > 0 \) 的假设。作者在第 5 页提到,这个假设可以放宽到 \( f \) 有紧支撑且远离 0,但未给出详细证明。因此,对于密度在边界附近趋近 0 的情形,结论是否成立是开放的。
- 泛化 claim:作者在结论中说“适用于任意 \( \alpha > 0 \)”,但证明中假设 \( \alpha \) 是已知的(非自适应版本)。自适应版本虽然不需要知道 \( \alpha \),但超先验的选择可能依赖于 \( \alpha \) 的上界(如假设 \( \alpha \le \alpha_{\max} \))。作者未明确讨论这一点。
- 未证明的 conjecture:作者在第 6 页提到,集成方法可能在高维情形下也有类似性质,但未给出任何证明或讨论。这只是一个推测。
四、开放问题¶
-
高维推广:本文限于一维 \( [0,1) \)。对于高维密度估计(如 \( [0,1)^d \)),移位 Pólya 树集成是否仍能达到 minimax 最优率?频率派随机森林(Mourtada et al., 2018 [22])已对任意维度成立,但贝叶斯版本尚未。扎根点:作者在第 6 页提到“extensions to higher dimensions are left for future work”。
-
边界行为:定理假设 \( \inf f > 0 \)。对于密度在边界附近趋近 0 的情形,后验收缩率是否仍成立?可能需要修改先验(如使用非均匀划分)或调整测试数构造。扎根点:作者在第 5 页提到“the assumption \( \inf f > 0 \) can be relaxed, but we do not pursue this here”。
-
其他损失函数:本文仅考虑 Hellinger 和 \( L^1 \) 距离。对于 \( L^\infty \)(一致)距离,后验收缩率是否也能达到最优?Ročková & Saha (2018) [21] 对 BART 给出了 \( L^\infty \) 结果,但限于 \( \alpha \le 1 \)。扎根点:作者在第 4 页提到“we focus on Hellinger and \( L^1 \) distances; \( L^\infty \) results require different techniques”。
-
计算效率:本文的集成先验需要平均 \( B \) 个 Pólya 树的后验,每个后验的计算复杂度是 \( O(n 2^J) \)。当 \( B \) 很大(如 \( B = n \))时,总复杂度为 \( O(n^2 2^J) \),可能不实用。是否存在更高效的计算方案(如通过随机近似或变分推断)?扎根点:作者在第 7 页提到“computational aspects are not discussed in this paper”。
提醒:要确认第 4 条是否是真 gap,可以去读近期关于贝叶斯树计算的工作(如 Pratola et al., 2013 [19] 的并行 BART),看是否有现成的加速方案。
Maintained by 陈星宇 · Homepage · Source on GitHub