跳转至

A rank-based sequential test of independence

作者: Alexander Henzi, Michael Law
主题: 数理统计 / 假设检验
相关性: 6/10
链接: https://doi.org/10.1093/biomet/asae023


一、领域脉络与小综述

这个方向是什么

本文研究的根本问题是:在数据流式到达、样本量不预先固定的序贯设定下,如何对两个一元随机变量的独立性进行假设检验。其核心统计挑战在于,检验过程允许在任意时刻"偷看"数据并决定是否停止,因此必须保证在所有可能的停止时间上统一控制第一类错误(即"任意有效"性质),而非仅在某个预先固定的样本量上控制。该方向属于"安全、任意有效推断"这一近年快速发展的子领域,其成熟度处于方法快速涌现、但理论工具尚在完善的阶段——已有工作多集中于均值、分位数等一元参数的检验,而本文针对的是非参数独立性检验这一更复杂的复合零假设。

发展脉络

  • 奠基工作:该领域的理论基石是 Ville 不等式(Ville, 1939),它给出了非负上鞅在任意停止时间上超过阈值的概率上界,从而为构造任意有效检验提供了通用工具。这一不等式在本文中扮演核心角色,也是所有后续工作的理论出发点。
  • 主要进展:近年来,以 Ramdas 等人为代表的研究者系统发展了"检验上鞅"与"e 值"的理论框架。Ramdas et al. (2023) 的综述文章是该领域的纲领性文献,系统阐述了 e 值、检验上鞅与任意有效推断之间的关系。在独立性检验的具体问题上,Balsubramani and Ramdas (2016) 最早在序贯设定下构造了基于 betting 的检验;Shekhar and Ramdas (2023) 进一步提出了基于 Kolmogorov-Smirnov 距离的检验上鞅;Podkopaev et al. (2023) 和 Podkopaev and Ramdas (2023) 则引入了核方法(基于 Hilbert-Schmidt 独立性准则)构造序贯检验。此外,Grünwald et al. (2023)、Shaer et al. (2023) 和 Duan et al. (2022) 处理了条件独立性的任意有效检验问题(在 model-X 假设下),Turner et al. (2023) 处理了二元列联表数据,Turner and Grunwald (2023) 将其推广到分层计数数据。
  • 当前 frontier:该领域的前沿问题包括:(i) 如何构造在复合零假设下仍保持有效性的检验上鞅(本文即针对独立性这一复合零假设);(ii) 如何在保证有效性的同时最大化检验效力(即最小化期望停止时间);(iii) 如何量化 Ville 不等式带来的保守性并加以修正。
  • 本文的位置:本文的独特贡献在于利用秩变换将复合零假设化为简单零假设——通过将原始数据转换为序贯秩,在零假设下这些秩是均匀分布的,从而将问题简化为对均匀分布的检验。这一思路使得作者能够构造出分布自由的检验上鞅,并首次对 Ville 不等式的保守性进行数值量化。

子线索聚类

  1. 基于 betting 的检验上鞅:Balsubramani and Ramdas (2016)、Shekhar and Ramdas (2023)、Podkopaev et al. (2023)、Podkopaev and Ramdas (2023)。这条线索的核心思想是将检验问题转化为一个"赌徒"与"庄家"之间的博弈,通过构造有利的赌注策略来累积证据。其优点是构造灵活、可针对特定备择假设优化,但缺点是难以对复合零假设直接构造有效的赌注策略。
  2. 基于秩变换的分布自由方法:本文(Henzi and Law, 2024)以及 Choi (1973) 的早期工作。这条线索的核心思想是利用秩变换消除边际分布的影响,从而在零假设下获得一个与原始分布无关的简单零假设。其优点是分布自由、便于理论分析,但缺点是秩变换可能损失信息,且对某些类型的依赖结构(如非线性依赖)可能不敏感。
  3. 基于核方法的非参数检验:Podkopaev et al. (2023)、Podkopaev and Ramdas (2023)。这条线索利用核方法(如 HSIC)构造检验统计量,能够捕捉任意类型的依赖关系,但构造检验上鞅的难度较大,且理论分析通常需要更强的假设。

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

  1. 如何构造在复合零假设下有效的检验上鞅? 这是序贯独立性检验的核心困难。现有方法要么通过 betting 策略针对特定备择假设优化(但难以覆盖所有备择),要么通过秩变换简化零假设(但可能损失效力)。
  2. 如何量化并缩小 Ville 不等式的保守性? Ville 不等式给出的上界通常远非紧的,导致检验在有限样本下过于保守。本文通过数值模拟量化了这一保守性,并提出了截断检验作为实用修正。
  3. 如何在保证任意有效性的同时达到最优的检验效力? 这是一个效率理论问题——在序贯设定下,检验效力的自然度量是期望停止时间,而最优性标准尚不清晰。

⚠️ 作者的 framing

作者将缺口 frame 为:"现有序贯独立性检验方法要么缺乏对复合零假设的严格有效性保证,要么无法提供有限样本下的显式效力界。本文通过秩变换构造分布自由的检验上鞅,首次给出了有限样本下第二类错误的显式上界。" 作者淡化了核方法(Podkopaev et al., 2023)在捕捉非线性依赖方面的优势,强调了自己的方法在理论保证的完备性上的贡献。值得注意的是,作者没有讨论高维情形的推广,也没有讨论条件独立性检验这一更一般的问题——这些是读者可以进一步追问的方向。

张力

未见明显对立引用。不过存在一个微妙的张力:Shekhar and Ramdas (2023) 的检验基于 Kolmogorov-Smirnov 距离,对任意类型的依赖都有检测能力(在极限意义下),而本文的秩方法在离散化网格上检测依赖,其效力依赖于网格分辨率与依赖结构的匹配程度。这两种方法在"检测的全面性"与"理论保证的精确性"之间存在权衡,但作者未直接讨论这一权衡。


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

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

  • 原始数据:\((X_n, Y_n) \in \mathbb{R} \times \mathbb{R}\),\(n = 1, 2, \ldots\),为独立同分布(iid)随机变量对,服从未知联合分布 \(P\)。记 \((X, Y)\) 为服从 \(P\) 的通用一对。
  • 边际分布:\(F\) 和 \(G\) 分别为 \(X\) 和 \(Y\) 的边际累积分布函数(CDF),即 \(F(x) = P(X \le x)\),\(G(y) = P(Y \le y)\)。
  • 零假设:\(H_0: P(X \in A, Y \in B) = P(X \in A)P(Y \in B)\) 对所有 Borel 集 \(A, B \subseteq \mathbb{R}\) 成立,即 \(X\) 与 \(Y\) 独立。
  • 序贯秩:对每个 \(n\),定义 \(X_n\) 在 \(X_1, \ldots, X_n\) 中的秩为 \(\hat{F}_n(X_n) = \frac{1}{n} \sum_{i=1}^n \mathbf{1}(X_i \le X_n)\),类似地定义 \(\hat{G}_n(Y_n)\)。注意 \(\hat{F}_n(X_n)\) 是经验 CDF 在观测点 \(X_n\) 处的值,取值于 \(\{1/n, 2/n, \ldots, 1\}\)。
  • 随机化秩:\(R_n = \hat{F}_n(X_n) - U_n/n\),\(S_n = \hat{G}_n(Y_n) - V_n/n\),其中 \(U_n, V_n \sim \text{Unif}(0,1)\) 为独立随机化变量。随机化的目的是处理边际分布不连续(有原子)的情形,使得 \(R_n, S_n\) 在零假设下严格服从 \([0,1]\) 上的均匀分布。
  • 检验统计量:将 \([0,1]^2\) 划分为 \(d \times d\) 个等大小网格单元 \(B^d_{k\ell}\),\(k, \ell = 0, \ldots, d-1\)。定义 \(b_{k\ell, n} = \sum_{j=1}^n \mathbf{1}\{(R_j, S_j) \in B^d_{k\ell}\}\) 为截至时间 \(n\) 落入单元 \((k,\ell)\) 的观测数。
  • 检验上鞅:\(M^{(d)}_N = \prod_{n=1}^N f^{(d)}_n(R_n, S_n)\),其中 \(f^{(d)}_n\) 是基于过去数据构造的密度估计(见下文)。
  • 停止时间:\(\tau = \tau(\alpha, M^{(d)}) = \inf\{n \in \mathbb{N}: M^{(d)}_n \ge 1/\alpha\}\),即检验上鞅首次超过阈值 \(1/\alpha\) 的时刻。
  • 关键参数:\(d\) 为网格分辨率(正整数),\(\alpha \in (0,1)\) 为显著性水平,\(N\) 为最大样本量(截断点)。

第二步:最小内核

核心思想:将复合零假设(独立性)化为简单零假设(均匀性)。

最小例子:假设 \(d=2\),即把 \([0,1]^2\) 分成 \(2 \times 2 = 4\) 个象限。在零假设下,随机化秩 \((R_n, S_n)\) 是 \([0,1]^2\) 上的独立均匀随机变量,因此每个象限的期望概率为 \(1/4\)。

检验上鞅的构造:在时间 \(n\),基于前 \(n-1\) 个观测,对每个象限 \((k,\ell)\) 估计其概率 \(\hat{p}_{k\ell, n-1} = \frac{b_{k\ell, n-1} + 1}{n - 1 + 4}\)(即加上初始计数 1 的拉普拉斯平滑)。然后定义密度估计:

\[f^{(2)}_n(r,s) = 4 \cdot \hat{p}_{k\ell, n-1} \quad \text{若 } (r,s) \in B^2_{k\ell}.\]
在零假设下,\(f^{(2)}_n\) 是 \([0,1]^2\) 上的一个密度(因为 \(\sum_{k,\ell} \hat{p}_{k\ell, n-1} = 1\)),且 \(f^{(2)}_n\) 仅依赖于过去数据,因此是可预测的。于是:
\[\mathbb{E}[f^{(2)}_n(R_n, S_n) \mid \text{过去数据}] = \int_{[0,1]^2} f^{(2)}_n(r,s) \, dr \, ds = 1,\]
从而 \(M^{(2)}_N = \prod_{n=1}^N f^{(2)}_n(R_n, S_n)\) 在零假设下是鞅(期望恒为 1)。由 Ville 不等式:
\[P(M^{(2)}_N \ge 1/\alpha \text{ 对某个 } N) \le \alpha.\]
这就是整个论文的最小内核:通过秩变换 + 可预测密度估计,构造了一个在零假设下期望恒为 1 的非负鞅,从而获得任意有效的第一类错误控制。

为什么这个例子抓住了本质:它展示了三个关键要素——(1) 秩变换将复合零假设化为简单零假设;(2) 可预测密度估计保证了鞅性质;(3) Ville 不等式提供了任意有效的阈值。论文的其余部分(Sinkhorn 校正、不同 \(d\) 的聚合、截断检验)都是在这个内核上的工程优化。


三、这篇论文做了什么

三句话

  1. 研究了什么问题:在序贯设定下,构造一个分布自由的、具有任意有效第一类错误控制的独立性检验,并给出有限样本下第二类错误的显式上界。
  2. 核心工具/方法:将原始数据转换为随机化序贯秩,利用直方图密度估计构造可预测密度序列,从而得到检验上鞅;通过 Sinkhorn 算法施加均匀边际约束以提升效力;通过在不同网格分辨率 \(d\) 间聚合来平衡早期与晚期检测能力。
  3. 主要结论:所提出的检验在零假设下具有任意有效性(Ville 不等式控制),在备择假设下具有有限样本的显式效力保证(第二类错误上界),且数值实验表明其在多种依赖模式下优于现有的序贯检验方法。

关键设定与假设

  • 数据生成:\((X_n, Y_n)\) 为 iid 序列,边际分布 \(F, G\) 完全未知(可以是离散、连续或混合)。
  • 零假设:\(X\) 与 \(Y\) 独立(复合零假设)。
  • 核心假设(用于效力分析):备择分布 \(P\) 在 \(d \times d\) 网格上的离散化 \(Q^{(d)}\) 满足 \(KL(Q^{(d)} \| U) > 0\),即依赖在所选分辨率下可被检测。这是本文唯一的关键假设,且是不可避免的——若依赖仅存在于比网格更精细的尺度上,任何基于该网格的检验都无法检测。
  • 与已有文献的对比:相比 Shekhar and Ramdas (2023) 的 KS 距离方法,本文的秩方法不需要选择特定的检验函数,且分布自由的特性使得理论分析更简洁;相比 Podkopaev et al. (2023) 的核方法,本文的方法计算复杂度更低(\(O(n \log n)\) vs 核方法的 \(O(n^2)\)),但核方法在检测非线性依赖方面可能更灵活。

主要结果

定理 1(不可能性):任何适应于原始数据流 \((X_n, Y_n)\) 的非负鞅,若对所有满足 \(H_0\) 的分布都有效,则其路径必然非增。这意味着在原始数据流上不可能构造出有检验效力的任意有效检验——必须使用秩变换或更粗的过滤。

定理 2(效力保证):若 \(KL(Q^{(d)} \| U) > 0\),则对任意 \(\alpha \in (0,1)\) 和 \(N \ge 3\),检验的停止时间满足:

\[P(\tau \le N) \ge 1 - \left[ \frac{1}{\alpha} \exp\left(-N \cdot KL(Q^{(d)} \| U) + 47 d^3 \sqrt{N \log N}\right) \right],\]
其中 \(\tau\) 是检验上鞅首次超过 \(1/\alpha\) 的时刻。这个下界表明,只要 \(N\) 足够大(相对于 \(1/KL\)),检验就能以高概率拒绝零假设。

推论(期望停止时间):在上述条件下,\(\mathbb{E}[\tau] \le \frac{\log(1/\alpha) + O(d^3 \sqrt{N \log N})}{KL(Q^{(d)} \| U)}\),即期望停止时间与 \(KL\) 散度成反比。

数值结果: - 在 Circular、Linear、Local 三种模拟设定下,Sinkhorn 校正版本(\(\eta = 0\))在大多数情况下优于未校正版本和 Shekhar-Ramdas 方法。 - 在弱依赖(\(l = 7, 9\))时,本文方法需要约 3000-6500 个观测才能达到 95% 拒绝率,而 Shekhar-Ramdas 方法需要更多;在强依赖(\(l = 1, 3\))时,本文方法在 100-200 个观测内即可达到高拒绝率。 - 截断检验(\(N = 512\))的效力与 Shekhar-Ramdas 方法相当,但平均停止时间更短。

证明路线与技术技巧

定理 1 的证明: 1. 假设存在一个非平凡的非负鞅 \(M_n\),对 \(H_0\) 下所有分布有效。 2. 构造两个满足 \(H_0\) 的分布 \(P_1, P_2\),使得 \(P_1\) 下 \(X_1\) 的分布与 \(P_2\) 下 \(X_1\) 的分布不同,但 \(Y_1\) 的分布相同。 3. 利用鞅的适应性,证明 \(M_1\) 必须同时等于 \(P_1\) 和 \(P_2\) 下的某个常数,从而 \(M_1\) 不依赖于 \(X_1\) 的取值。 4. 归纳地证明 \(M_n\) 对所有 \(n\) 都不依赖于数据,因此 \(M_n \equiv 1\),即平凡鞅。 5. 关键技巧:利用 Doob-Dynkin 引理将鞅表示为数据的函数,再通过构造"不可区分"的分布对来消除数据依赖性。

定理 2 的证明: 1. 分解:将 \(\log M^{(d)}_N\) 分解为 \(\log \hat{M}^{(d)}_N + \log(M^{(d)}_N / \hat{M}^{(d)}_N)\),其中 \(\hat{M}^{(d)}_N\) 是使用真实概率 \(Q^{(d)}\) 而非估计 \(\hat{Q}^{(d)}\) 构造的"理想"检验上鞅。 2. 理想上鞅的增长率:\(\log \hat{M}^{(d)}_N = \sum_{n=1}^N \log \frac{q^{(d)}(R_n, S_n)}{1}\),其中 \(q^{(d)}\) 是 \(Q^{(d)}\) 的密度。由大数定律,\(\frac{1}{N} \log \hat{M}^{(d)}_N \to KL(Q^{(d)} \| U)\)。 3. 估计误差的控制:利用 Dvoretzky-Kiefer-Wolfowitz 不等式和 Hoeffding 不等式,证明 \(\log(M^{(d)}_N / \hat{M}^{(d)}_N) \ge -O(d^3 \sqrt{N \log N})\) 以高概率成立。 4. 关键技巧:秩变换的 Lipschitz 性质——序贯秩与真实秩的差异被随机化变量 \(U_n, V_n\) 平滑化,使得 \(\hat{q}^{(d)}\) 与 \(q^{(d)}\) 的差异可以被经验过程理论控制。这是本文最核心的技术贡献。

🔎 结论是否比证明窄

  • 定理 1 的结论是严格的:证明对所有满足 \(H_0\) 的分布都成立,没有隐藏假设。
  • 定理 2 的结论在以下方面比证明宽:
  • 定理 2 的陈述要求 \(KL(Q^{(d)} \| U) > 0\),但证明中实际上需要 \(KL(Q^{(d)} \| U) \gg d^3 \sqrt{\log N / N}\) 才能保证下界非平凡。作者在 Remark 4 中承认了这一点,但未在定理陈述中明确。
  • 定理 2 的证明依赖于 \(d\) 固定、\(N \to \infty\) 的渐近框架,但作者在数值实验中使用了 \(d\) 随 \(N\) 增长的自适应选择。这种自适应选择的严格理论保证未被证明。
  • 作者声称"分布自由"(distribution free),但 Sinkhorn 校正版本的检验统计量 \(\check{f}^{(d)}_n\) 的分布依赖于数据通过 Sinkhorn 迭代的路径,其严格分布自由性质未被证明(仅通过模拟验证)。

四、开放问题

  1. 高维推广:本文的方法仅适用于一元边际分布。将秩变换推广到 \(p\) 维随机向量需要定义多元秩,而多元秩的分布自由性质远非平凡。一个具体问题是:能否构造一个在 \(p\) 维情形下仍具有任意有效性的检验上鞅?这需要新的理论工具,因为多元秩的联合分布依赖于 copula 结构。

  2. 自适应网格选择:作者在数值实验中使用 \(d = 2, 4, 8, 16\) 的聚合,但未提供选择 \(d\) 的自适应准则。一个自然的问题是:能否根据数据自适应地选择网格分辨率,使得检验在未知的依赖尺度下仍具有最优的检测能力?这可能与 minimax 最优检验有关——在固定样本量下,最优的 bin 数 \(d\) 应随 \(N\) 和依赖强度变化。

  3. Ville 不等式的紧性:作者通过模拟发现 Ville 不等式的上界在有限样本下保守(实际第一类错误约 0.046 vs 名义 0.05),但未给出理论解释。一个开放问题是:能否构造更紧的任意有效阈值,例如通过考虑检验上鞅的分布而非仅用 Ville 不等式?这可能与 e 值的最优校准有关。

  4. 与条件独立性检验的联系:本文的方法基于秩变换,而条件独立性检验(如 model-X 框架下的方法)通常需要已知或可估计的边际分布。一个有趣的问题是:能否将本文的秩变换思想推广到条件独立性检验,从而构造分布自由的序贯条件独立性检验?这需要处理条件秩的估计误差。

  5. 检验效力的最优性:本文给出了第二类错误的显式上界,但未讨论该上界是否最优。一个开放问题是:在序贯设定下,对于给定的 \(KL\) 散度,最小的期望停止时间是多少?这可能需要建立序贯检验的效率界,类似于固定样本量下的 minimax 下界。


提示:若要确认上述开放问题是否为真 gap,建议去读以下近期文献的引言部分(约 5 篇):(i) Podkopaev and Ramdas (2023) 的核方法序贯检验;(ii) Grünwald et al. (2023) 的条件独立性检验;(iii) Turner and Grunwald (2023) 的分层计数数据检验;(iv) 关于 e 值最优性的近期工作(如 Vovk and Wang, 2021);(v) 关于多元秩检验的近期文献。如果这些文献的引言都未提及某个问题,那它很可能是一个值得关注的真 gap。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论