Delaunay Weighted Two-sample Test for High-dimensional Data by Incorporating Geometric Information¶
作者: Jiaqi Gu, Ruoxu Tan, Guosheng Yin
来源: Statistica Sinica
主题: 数理统计 / 假设检验
相关性: 0/10
机构绿灯: University of Hong Kong(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本文所针对的根本问题是高维两样本检验:给定两组独立同分布样本 \(X=\{x_1,\dots,x_{n_1}\}\subset\mathbb{R}^D\) 与 \(Y=\{y_1,\dots,y_{n_0}\}\subset\mathbb{R}^D\),检验原假设 \(H_0: F=G\) 是否成立。经典参数方法(Hotelling \(T^2\)、Wald、似然比检验)在高维下功效衰减甚至失效;非参数方法(基于距离、核、图)虽能检测一般分布差异,但大多只利用样本点间的距离信息,忽略了方向信息。该子方向的核心问题是:如何在保留非参数灵活性的同时,充分利用高维数据的内在几何结构(低维流形假设),构造对一般备择假设(尤其是协方差方向差异)更敏感的检验统计量? 该方向当前处于活跃发展阶段,已有基于 \(k\)-NN 图、最小生成树(MST)、核方法(MMD)等成熟工具,但将 Delaunay 三角剖分引入两样本检验尚属首次。
发展脉络¶
- 奠基工作:Schilling (1986) 提出基于 \(k\)-最近邻图的非参数两样本检验,开创了"用图结构编码样本间邻近关系"的思路。Friedman and Rafsky (1979) 基于最小生成树构造检验统计量,是图基检验的另一支柱。这两项工作奠定了"用邻近图替代参数模型"的范式。
- 主要进展:在距离/能量框架下,Székely and Rizzo (2004) 提出能量距离检验(e-distance),基于成对距离的期望差异构造统计量;Gretton et al. (2012) 提出核最大均值差异(MMD)检验,将分布差异嵌入再生核希尔伯特空间。在图基检验方面,Chen and Friedman (2017) 与 Chen et al. (2018) 发展了 \(k\)-MST 图检验,并给出了渐近零分布理论。这些工作共同确立了"基于成对相似度/邻近图"的主流技术路线。
- 当前 frontier:近年工作开始关注高维数据的流形结构。Cheng and Xie (2024) 研究了流形数据上的核两样本检验,证明了检验功效与内在维度 \(d\)、Hölder 光滑度 \(\beta\) 的关系;Kim et al. (2019) 提出基于回归的两样本检验框架,可自适应内在维度。Arias-Castro et al. (2018) 则从 minimax 角度揭示了高维非参数检验的维数灾难本质。本文的位置:作者指出,上述方法均只利用距离信息,而 Delaunay 三角剖分能同时编码距离与方向,因此本文是"将计算几何中的 Delaunay 结构引入统计检验"的第一步。
- ⚠️ 作者的 framing:作者在引言中明确将缺口 frame 为——"现有非参数检验(\(k\)-NN、MST、核方法)仅基于成对距离,忽略了方向信息;在流形假设下,方向信息对检测协方差主方向差异至关重要"。因此本文的贡献被定位为"利用 Delaunay 三角剖分同时捕捉距离与方向,填补这一空白"。作者淡化了核方法(如 Cheng and Xie 2024)在流形上的自适应能力,也未讨论 MMD 在合适核选择下是否已隐含方向信息——这是值得研究者自行查证的对立观点。
子线索聚类¶
- 图基检验:Schilling (1986)、Friedman and Rafsky (1979)、Chen and Friedman (2017)、Chen et al. (2018)。共同点:用图(\(k\)-NN、MST)编码样本邻近关系,统计量为跨组边的计数或加权。本文直接继承此脉络,将图替换为 Delaunay 三角剖分。
- 距离/核方法:Székely and Rizzo (2004)、Gretton et al. (2012)、Cheng and Xie (2024)、Yan and Zhang (2023)。共同点:基于成对距离或核函数度量分布差异,理论成熟(MMD 的 U-statistic 表示、能量距离的完备性)。
- 高维均值/协方差检验:Cai et al. (2014)、Chang et al. (2017)、Wang et al. (2019)、Liu et al. (2024)、Yang et al. (2024)。共同点:针对稀疏备择或特定结构(均值差异、协方差差异),但只检验矩而非整个分布。
- 流形学习与内在维度:Facco et al. (2017)、Meilă and Zhang (2024)、Tenenbaum et al. (2000, Isomap)、Bhattacharya and Patrangenaru (2003)。共同点:估计数据的内在维度或低维表示,为高维统计提供几何先验。
这个方向在追问的核心问题¶
- 功效与维度的权衡:非参数检验在高维下如何避免维数灾难?Arias-Castro et al. (2018) 已证明 minimax 率随维度恶化,流形假设能否突破这一瓶颈?
- 距离 vs. 方向:仅用距离信息是否足够?在什么类型的备择假设下,方向信息能带来本质性的功效提升?
- 计算可行性:高维下 Delaunay 三角剖分的计算复杂度如何控制?本文提出的近似算法是否在理论上保真?
- 零分布的可处理性:图基检验的渐近理论依赖于图的组合结构,Delaunay 图的随机几何性质是否支持类似的渐近分析?
张力¶
- 未见明显对立引用,但存在一个值得注意的隐含张力:Cheng and Xie (2024) 的核方法在流形上已被证明自适应内在维度,而本文声称"现有方法未利用方向信息"——若核函数(如热核)在流形上隐含了方向信息,则本文的 novelty 主张需要更细致的边界刻画。作者未在引言中正面回应这一点,建议研究者自行查阅 Cheng and Xie (2024) 的定理条件来核实。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据¶
- 可观测数据:两组样本 \(X=\{x_1,\dots,x_{n_1}\}\subset\mathbb{R}^D\),\(Y=\{y_1,\dots,y_{n_0}\}\subset\mathbb{R}^D\),均为 i.i.d.。合并为 \(Z=\{z_1,\dots,z_n\}\),\(n=n_1+n_0\)。组标签 \(\delta=(\delta_1,\dots,\delta_n)\),\(\delta_i=1\) 表示 \(z_i\in X\),\(\delta_i=0\) 表示 \(z_i\in Y\)。
- 模型假设:\(F\) 与 \(G\) 支撑在同一个 \(d\) 维测地凸 Riemann 流形 \(\mathcal{M}\subset\mathbb{R}^D\) 上,\(d\ll D\)。流形 \(\mathcal{M}\) 未知。
- 目标 estimand:检验 \(H_0: F=G\) 对 \(H_1: F\neq G\)。无参数化的分布差异,属于非参数假设检验。
- 核心几何对象:
- 测地距离 \(d_{\mathcal{M}}(a,b)\):流形上两点间最短测地路径长度。
- Delaunay 三角剖分 \(\mathrm{DT}_{\mathcal{M}}(Z)\):将流形 \(\mathcal{M}\) 上点集 \(Z\) 剖分为一组 \(d\)-单形(三角形、四面体等),满足空球性质——每个单形的外接球内部不含其他点。
- Delaunay 权重向量 \(w(p;Z)\):对任意 \(p\in\mathcal{M}\),找到包含 \(p\) 的 Delaunay 单形 \(S(p;Z)\),其顶点为 \(z_{i_1},\dots,z_{i_{d+1}}\),则 \(w(p;Z)\) 是 \(p\) 在这些顶点上的重心坐标(凸组合系数),满足 \(p=\sum_{j=1}^{d+1}w_{i_j}(p;Z)z_{i_j}\),且 \(\sum w=1\)。
- Delaunay 权重矩阵 \(\Gamma_Z=(\gamma_{ij})_{n\times n}\):\(\gamma_{ii}=0\),对 \(i\neq j\),\(\gamma_{ij}=w_j(z_i;Z\setminus\{z_i\})\),即去掉 \(z_i\) 后,\(z_i\) 在剩余点集 Delaunay 剖分中所属单形顶点上的重心坐标。
第二步:最小内核¶
核心思想:如果 \(F=G\),那么组标签 \(\delta\) 与样本位置 \(Z\) 独立。因此,给定 \(Z\),\(\delta\) 在 \(n_1\) 个 1 和 \(n_0\) 个 0 的所有排列中等概率。检验统计量应度量"同组样本在几何上是否异常接近"。
最小例子(\(d=1\),流形为直线 \(\mathbb{R}\)): - 设 \(Z=\{z_1,\dots,z_n\}\subset\mathbb{R}\),排序后为 \(z_{(1)}<z_{(2)}<\dots<z_{(n)}\)。 - 在 \(\mathbb{R}\) 上,Delaunay 三角剖分就是相邻点之间的线段(1-单形)。对内部点 \(z_{(i)}\),去掉它之后,它落在相邻两点 \(z_{(i-1)},z_{(i+1)}\) 形成的线段上,重心坐标为:
为什么这个例子抓住了本质: 1. 方向信息:重心坐标 \(\gamma_{ij}\) 不仅反映距离(分母是区间长度),还反映方向(分子是相对位置)。在 \(d=1\) 时,这体现为"左侧邻居 vs 右侧邻居"的区分——而 \(k\)-NN 只取最近的 \(k\) 个点,无法区分方向。 2. 流形适应性:Delaunay 剖分在流形上自动适应测地结构,不依赖全局坐标。 3. 检验逻辑:条件于 \(Z\),\(\delta\) 的排列分布是精确的(permutation test),无需估计零分布。
为什么一般情形更难: - 当 \(d>1\) 时,Delaunay 单形有 \(d+1\) 个顶点,重心坐标是 \(d\) 维向量,方向信息更丰富但也更复杂。 - 流形 \(\mathcal{M}\) 未知,需要用 Isomap 等流形学习方法先估计低维表示,这引入估计误差。 - 高维下 Delaunay 剖分的计算复杂度极高,需要近似算法(本文的 stereographic projected DELAUNAYSPARSE)。
三、这篇论文做了什么¶
三句话¶
- 研究了什么问题:在高维数据满足低维流形假设的条件下,如何构造一个利用方向信息(而非仅距离)的非参数两样本检验,以提升对协方差主方向差异的检测功效。
- 核心工具/方法:提出 Delaunay 权重(Delaunay weight)作为样本间几何邻近性的度量,基于 Delaunay 三角剖分构造检验统计量 \(T_{DW}\),并开发了 stereographic projected DELAUNAYSPARSE 算法在未知流形上近似计算权重矩阵。
- 主要结论:理论上证明了零假设下 \(T_{DW}\) 的渐近正态性(Theorem 2)和备择假设下的一致性(Theorem 3);模拟和真实数据表明,在方向性差异(协方差主方向旋转)下,新检验显著优于 \(k\)-NN、\(k\)-MST、核方法等现有方法。
关键设定与假设¶
- 流形假设:\(F,G\) 支撑在同一个 \(d\) 维测地凸 Riemann 流形 \(\mathcal{M}\subset\mathbb{R}^D\) 上,\(d\ll D\)。测地凸性保证任意两点间测地线唯一且落在流形内,这是 Delaunay 剖分良定义的前提。
- 光滑性:\(F,G\) 关于流形上的体积测度有 Lipschitz 连续的密度 \(f,g\)。这保证 pooled sample \(Z\) 是 generic 的(即任何 \(d+2\) 个点不共球),从而 Delaunay 剖分唯一(引用 Leibon and Letscher 2000 的结论)。
- 样本量条件:\(n_1/n\to\kappa\in(0,1)\),即两组样本量同阶增长。
- 技术性条件(Theorem 2 的 (iii)):\(\sum_{i=1}^n |N_i|^4 = o(n^\nu)\),其中 \(\nu<9/4\),\(N_i\) 是 Delaunay 剖分中包含 \(z_i\) 的单形集合。这个条件限制了 Delaunay 剖分的"局部复杂度"——直观上要求没有点被异常多的单形共享(即无 hub 点)。这是证明渐近正态性的关键正则性条件。
- 与已有文献的对比:相比 \(k\)-NN/k-MST 检验(Chen and Friedman 2017, 2018),本文不要求选择近邻数 \(k\),而是由 Delaunay 剖分自适应决定局部邻域结构;相比核方法(Cheng and Xie 2024),本文不要求选择核函数和带宽,且显式利用方向信息。
主要结果¶
Theorem 1(条件矩):在 \(H_0\) 下,给定 \(Z\),
Theorem 2(渐近正态性):在 Theorem 1 的条件和正则性条件 (iii) 下,
Theorem 3(一致性):在 \(F\neq G\) 且两组分布的差异在 Delaunay 剖分上产生可检测的几何信号时,检验功效趋于 1。证明思路:构造 \(T_{DW}\) 在备择下的期望与零下期望的差值,证明该差值在 \(n\to\infty\) 时不趋于 0,且方差可控。这里的关键是"方向差异"的定义——作者证明当两组协方差矩阵的主方向不同时,Delaunay 权重矩阵会系统性地偏向同组点。
证明路线与技术技巧¶
整体路线(Theorem 2 的证明): 1. 条件化:固定 \(Z\),将 \(\delta\) 视为均匀随机排列。此时 \(T_{DW}\) 是 \(\delta\) 的二次型。 2. Hoeffding 分解:将 \(T_{DW}\) 分解为 \(U\)-统计量形式的线性主项和二次余项。 3. 主项渐近正态:线性主项是独立随机变量的和(在排列分布下),用经典 CLT 处理。 4. 余项控制:余项是四元组权重的和,利用条件 (iii) 的稀疏性假设,证明余项相对于主项是 \(o_p(1)\)。 5. 方差估计:用 \(V_0,Z, V_1,Z, V_2,Z\) 的相合估计替代真实方差。
关键跳跃点: - Delaunay 权重的相关性结构:不同于 \(k\)-NN 图中边的事件近似独立,Delaunay 单形共享顶点导致 \(\gamma_{ij}\) 和 \(\gamma_{kl}\) 即使 \((i,j)\cap(k,l)=\emptyset\) 也可能相关(通过共享单形)。作者的处理方式是引入 \(N_i\) 并假设其大小受控(条件 (iii)),这相当于要求 Delaunay 剖分是"局部有限"的。 - 外部点的处理:当 \(z_i\notin H_{\mathbb{R}^d}(Z\setminus\{z_i\})\) 时,需要投影到凸包边界。作者利用 stereographic projection 将问题转化到球面上,使得所有点都在凸包内部,从而避免边界效应。这是本文技术创新的核心——通过 inverse stereographic projection 将 \(\mathbb{R}^d\) 上的 Delaunay 剖分转化为球面上的 Delaunay 剖分,后者具有更好的全局性质。
技术技巧点名: - Inverse stereographic projection(公式 6):将 \(\mathbb{R}^d\) 映射到 \(d\)-球面 \(\partial B_{\eta r_{\max}}\),使得原空间中的"无穷远点"映射到球面上的北极点,从而将外部点问题转化为内部点问题。 - Delaunay 剖分的空球性质:用于保证重心坐标的唯一性和非负性。 - 排列分布的 Hoeffding 分解:处理二次型统计量的渐近分布。 - 条件方差分解:将方差分解为 \(V_0,Z, V_1,Z, V_2,Z\) 三个部分,分别对应不同阶的交互作用。
真实例子与应用¶
模拟实验(Section 5.1-5.2): - Euclidean 数据:\(F=\mathrm{MVN}(0_d,I_d)\),\(G=\mathrm{MVN}(\Delta_d,I_d)\)(位置备择)或 \(G\) 的协方差矩阵主方向旋转(方向备择)。结果显示,在位置备择下,新检验与 \(k\)-NN、核方法功效相当;在方向备择下,新检验显著优于所有对比方法,且优势随维度 \(d\) 增大而扩大。 - 流形数据:\(d=10\) 维流形嵌入 \(D=100\) 维空间,通过 Isomap 估计低维表示。结果显示,新检验对流形学习过程(如近邻数选择、Isomap 参数)具有鲁棒性,功效损失有限。
真实数据(Section 5.3): - 数据:小鼠蛋白质表达数据集(Higuera et al., 2015),77 种蛋白质在 1080 个细胞中的表达水平,来自 72 只小鼠,分为 8 组(基因型 × 行为 × 治疗)。 - 预处理:删除缺失值过多的 3 个细胞和 9 种蛋白质,得到 \(n=1077\),\(D=68\)。估计内在维度 \(\hat{d}=3\)。 - 检验问题:(1) \(H_{0,g}\):不同基因型(正常 vs 三体)的蛋白质表达无差异;(2) \(H_{0,t}\):不同治疗(美金刚 vs 生理盐水)的蛋白质表达无差异。 - 结果:在 \(H_{0,g}\) 下,除 e-distance 外所有检验均显著(\(p<0.05\));在 \(H_{0,t}\) 下,仅 Delaunay 加权检验显著(\(p=0.011\)),其余检验均不显著。作者将此解释为:美金刚的治疗效果主要体现在蛋白质网络的方向性变化(协方差主方向改变)而非均值或整体分布的大幅偏移,而 Delaunay 权重能捕捉这种方向性差异。 - 分层分析(Table 7):将 \(H_{0,t}\) 按基因型 × 行为分层后,Delaunay 加权检验在三体且受刺激的小鼠亚组中检测到显著差异(\(p=0.037\)),而核方法仅在未受刺激的三体小鼠中显著(\(p=0.002\))。作者认为这体现了两种方法检测不同维度差异的能力。
🔎 结论是否比证明窄¶
- Theorem 2 的证明依赖于条件 (iii)(\(\sum |N_i|^4 = o(n^\nu)\)),但作者在正文中未给出该条件在常见流形(如球面、环面)上成立的充分条件,也未讨论当数据含噪声(即不严格落在流形上)时条件是否仍然成立。这是一个明显的"证明窄于结论"之处。
- Theorem 3 的一致性只对"方向差异"类备择假设给出证明,但摘要和引言中的表述是"consistent against all alternatives"。作者在 Section 4 末尾承认"the consistency against all alternatives is established under the condition that the Delaunay triangulation captures the geometric difference between \(F\) and \(G\)",这实际上是一个循环论证——什么算"captures"并未精确定义。
- 近似算法的误差分析:Stereographic projected DELAUNAYSPARSE 算法的近似误差(即 \(\Gamma_{\tilde{Z}}\) 与 \(\Gamma_Z\) 的差异)在理论上未给出界,仅通过模拟验证。这意味着 Theorem 2 的渐近正态性在实际使用近似算法时是否成立是未证明的。
- 流形学习误差:Isomap 估计的低维表示 \(\tilde{Z}\) 与真实流形坐标之间的偏差对检验统计量的影响未在理论中处理,仅通过模拟说明"鲁棒"。
四、开放问题¶
- 条件 (iii) 的验证:Theorem 2 的正则性条件 \(\sum |N_i|^4 = o(n^\nu)\) 在哪些具体的流形-采样组合下成立?能否给出可验证的充分条件(如流形曲率上界、采样密度下界)?——扎根于 Theorem 2 的假设 (iii)。
- 近似算法的理论保证:Stereographic projected DELAUNAYSPARSE 的近似误差对检验统计量渐近分布的影响能否定量刻画?是否存在误差传播界,使得 \(\Gamma_{\tilde{Z}}\) 与 \(\Gamma_Z\) 的差异在 \(n\to\infty\) 时可忽略?——扎根于 Section 3.3 的近似算法描述。
- 流形学习误差的传播:Isomap 等流形学习方法引入的估计误差对检验功效的影响能否纳入理论框架?特别是当流形曲率较大或采样不均匀时,Delaunay 剖分的拓扑错误是否会导致检验失效?——扎根于 Section 3.3 和 Section 5.2.2 的敏感性分析。
- 与核方法的理论对比:作者声称方向信息是 Delaunay 权重独有的优势,但核方法(如热核)在流形上是否隐含了方向信息?能否在 minimax 框架下刻画两类方法的功效差异?——扎根于引言中对 Cheng and Xie (2024) 的引用。
- Delaunay 权重的统计效率:本文只证明了检验的一致性,未讨论功效的收敛速率。能否建立 \(T_{DW}\) 在局部备择下的功效函数,并与 \(k\)-NN、MMD 的 minimax 速率对比?——扎根于 Theorem 3 的陈述。
- 组合检验的扩展:作者在 Section 6 提到用 Cauchy 组合检验(Liu and Xie 2020)融合 Delaunay 加权检验与核检验,但未给出理论分析。组合后的检验能否在更广的备择类上保持一致性?——扎根于 Section 6 的 future work。
提示:若要确认上述问题是否为真 gap,建议查阅近 5 年(2020-2025)关于"流形上两样本检验"的文献(如 Cheng and Xie 2024 的后续工作、基于图 Laplacian 的检验、基于最优传输的检验),看是否已有工作解决了条件 (iii) 的验证或近似算法的误差分析。若多篇文献独立指向同一缺口,则大概率是共识性 gap;若各文献给出的条件互相矛盾,则可能是更值得深挖的机会。
Maintained by 陈星宇 · Homepage · Source on GitHub