跳转至

Sequential multiple testing with multiple hypotheses and prior information on the hypothesis configuration

讲者: Yiming Xing
会场: Institute of Statistics and Big Data
报告题目: Sequential Multiple Testing with Multiple Hypotheses and Prior Information on the Hypothesis Configuration
链接: arXiv
来源: JCSDS 2026 · 返回会议总览

一、领域脉络与小综述

这个方向是什么

这个子方向研究的是顺序多重检验（sequential multiple testing）问题：有多个独立的数据流（streams）被顺序观测，每个数据流对应一个假设检验问题，目标是在控制某种全局错误率（如族系错误率 FWER）的前提下，尽可能快地做出正确决策。本文进一步将每个数据流的检验问题从传统的二元假设（正常 vs 异常）推广到多元假设（M ≥ 3 个候选假设），并系统性地研究了如何利用关于“假设配置”（即每个流到底服从哪个假设）的先验信息来提升效率。

当前该子方向的成熟度：二元假设下的顺序多重检验已有相当完整的理论（最优性、渐近理论、多种错误度量），但多元假设下的工作极少，且几乎都局限于“无先验信息”或“分散式决策”的设定。本文是第一个在集中式决策（centralized）框架下，系统处理多元假设 + 任意先验信息的工作。

发展脉络（history）

  • 奠基工作：Chernoff (1959) 提出了顺序实验设计的框架，为后续的受控感知（controlled sensing）和顺序多假设检验奠定了基础。本文引用它作为“一个数据流、多个假设”问题的起点。
  • 二元假设下的顺序多重检验（主要进展）：
    • Malloy and Nowak (2014) 和 Cohen and Zhao (2015a) 研究了已知信号数（known number of signals）的设定，提出了基于“gap rule”的检验程序。
    • Song and Fellouris (2017) 是这一支线的里程碑：他们提出了“gap”和“gap-intersection”程序，证明了在已知信号数或已知下界时，这些程序能渐近达到最优期望样本量。本文大量借鉴了他们的框架和证明技巧。
    • Song and Fellouris (2019) 将错误度量从 FWER 推广到广义错误率（如至少 k 个错误）。
    • Xing and Fellouris (2023, 2025b) 研究了异步决策（不同流在不同时间做出决策）和去中心化设定。
    • Tsopelakos and Fellouris (2023, 2025) 引入了采样约束（每时刻只能观测部分流）。
  • 多元假设下的顺序检验（当前 frontier）：
    • 对于单个数据流的多元假设检验，已有较成熟的理论，如 Draglia et al. (1999) 的渐近最优性、Lai (2000) 的序贯概率比检验、Nitinawarat et al. (2013) 的受控感知。
    • 对于多个数据流的多元假设检验，Xing et al. (2024) 是唯一已知的先行工作，但仅限于分散式（decentralized）设定，即每个流只能用自己的数据做决策，不能共享信息。
  • 本文的位置：本文是第一个在集中式设定下，同时处理“多个数据流”和“每个流多个假设”以及“任意先验信息”的工作。它直接推广了 Song and Fellouris (2017) 的框架，并明确指出“从二元到多元”带来了本质性的新困难——错误不仅成对出现，还会以循环（cycle）形式出现。

子线索聚类

这些被引文献大致落在以下 3 条子线索上：

  1. 二元假设下的顺序多重检验（最成熟）：包括 Malloy and Nowak (2014), Cohen and Zhao (2015a), Song and Fellouris (2017, 2019), He and Bartroff (2021), Xing and Fellouris (2023, 2025b), Tsopelakos and Fellouris (2023, 2025), Chaudhuri and Fellouris (2024)。这一簇的核心问题是：如何利用先验信息（已知信号数、已知下界）来设计最优的顺序检验程序，并控制 FWER、FDR 等错误度量。
  2. 受控感知与主动学习（controlled sensing）：包括 Nitinawarat et al. (2013), Nitinawarat and Veeravalli (2015), Deshmukh et al. (2021), Huang et al. (2018), Hemo et al. (2020), Gafni et al. (2023)。这一簇关注的是：决策者可以主动选择观测哪些流或施加哪种控制，以最小化检测延迟。本文的“先验信息”概念与这一簇有交叉，但本文不涉及主动选择观测。
  3. 多元假设下的顺序检验（最不成熟）：包括 Draglia et al. (1999), Lai (2000), Xing and Fellouris (2024, 2025a), Xing et al. (2024)。这一簇的核心问题是：当每个流有 M ≥ 3 个候选假设时，如何设计顺序检验。本文是这一簇在“多个数据流 + 先验信息”方向上的首次系统探索。

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

  1. 如何定义和计算“最优”期望样本量？ 在给定错误率约束下，最小期望样本量的下界是什么？这个下界如何依赖于先验信息和假设配置？
  2. 如何设计一个计算上可行的程序来达到这个下界？ 当假设数量 M 和数据流数量 K 都很大时，直接比较所有可能的假设配置（数量为 M^K）是不可行的。如何识别出“最相关”的少数替代配置？
  3. 先验信息到底能带来多大的效率提升？ 已知信号数 vs 已知下界 vs 无先验信息，这三者在渐近最优样本量上的差距有多大？本文的 Table I 和 Figure 1 给出了一个具体例子。
  4. 如何将二元假设下的成熟理论（如 gap rule）推广到多元假设？ 多元假设下，错误不仅成对出现，还会以循环形式出现，这导致停止规则必须包含对“循环证据”的检查。

已知瓶颈：计算复杂度（M^K 量级的比较）和理论复杂度（循环错误的处理）是主要瓶颈。本文通过引入“最小替代集”（fAlt）的概念，将计算复杂度从 M^K 降低到 O(K^M) 甚至更低，但 M 较大时仍可能很高。

⚠️ 作者的 framing

这是作者的说法：作者把缺口 frame 成“从二元到多元的推广是自然而然的，但带来了非平凡的新困难（循环错误）”，并声称本文是“第一个”在集中式设定下处理多元假设 + 先验信息的工作。作者淡化了以下竞争路线： - 分散式设定（Xing et al., 2024）：作者承认这是唯一已知的先行工作，但将其定位为“特殊设定”，并强调本文的集中式设定能利用跨流信息，因此更优。 - 受控感知（controlled sensing）：作者在引言中将其列为“开放问题 (iii)”，即“采样约束”，但本文并未处理。作者暗示这是未来工作，而非竞争路线。 - 依赖结构（Chaudhuri and Fellouris, 2024）：同样被列为开放问题 (iv)。

什么明显该被引 / 该存在、却没出现在 intro 里？ 作者没有引用任何关于多重假设检验中“循环错误” 的已有文献（如果存在的话）。这可能意味着这个困难确实是本文首次系统处理的，但也可能是一个值得研究者去查的问题：在固定样本量的多元假设检验中，是否已有关于“循环错误”或“循环比较”的讨论？

张力

未见明显对立引用。所有被引工作基本都在同一个渐近最优性框架下，彼此是互补或推广关系，没有出现“在略不同条件下得相反结论”的情况。

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

第一步：把符号、模型、可观测数据交代清楚

  • 符号：

    • K：数据流的数量（正整数）。
    • M：每个数据流的候选假设数量（M ≥ 2）。
    • X_k(n)：第 k 个流在第 n 个时间点的观测值（随机变量）。
    • f_k：第 k 个流的真实概率密度函数（未知）。
    • f_k^i：第 k 个流在第 i 个假设下的概率密度函数（已知）。
    • H = (H_1, ..., H_K)：假设配置（hypothesis configuration），是一个长度为 K 的向量，H_k = i 表示第 k 个流的真实假设是 i。H 是我们要推断的未知参数。
    • H_i：所有真实假设为 i 的流的集合（即 H_i = {k: H_k = i}）。
    • P_H：当真实配置为 H 时，所有数据流的联合分布。
    • T：停止时间（stopping time），一个随机变量，表示何时停止采样。
    • D = (D_1, ..., D_K)：决策（decision），一个长度为 K 的向量，D_k 表示对第 k 个流做出的最终决策（选哪个假设）。
    • α_{i,j}：允许的类型-(i,j) 错误概率的上界，即把真实假设为 i 的流误判为 j 的概率。
    • A：先验信息集，是 [M]^K 的一个子集，表示已知真实配置 H 属于 A。
    • I_{i,j}^k：第 k 个流中，假设 i 相对于假设 j 的 KL 散度。
    • ℓ_k^i(n)：第 k 个流前 n 个观测值在假设 i 下的对数似然。
    • ℓ_H(n)：所有流前 n 个观测值在配置 H 下的总对数似然。
    • Ĥ(n)：在时间 n 的最大似然配置（MLC），即 Ĥ(n) = argmax_H ℓ_H(n)。
    • λ_{i,j}(n)：在时间 n，所有被 MLC 判为假设 i 的流中，支持 i 反对 j 的最弱证据（minimum log-likelihood ratio）。

  • 模型：

    • 每个数据流 k 的观测值 {X_k(n): n ≥ 1} 是独立同分布（i.i.d.）的。
    • 不同数据流之间相互独立。
    • 每个流 k 的真实分布是 M 个已知分布 {f_k^1, ..., f_k^M} 中的一个。这些分布是简单假设（simple hypotheses），即完全已知，没有未知参数。本文第七节才扩展到复合假设。
    • 对于任何 k 和 i ≠ j，KL 散度 I_{i,j}^k 是正且有限的。

  • 可观测数据：

    • 研究者能观测到的是：在每个时间点 n，所有 K 个流的最新观测值 {X_1(n), ..., X_K(n)}。
    • 研究者想要但观测不到的是：真实的假设配置 H。这是需要推断的目标。
    • 研究者已知的是：每个流在每个假设下的分布 f_k^i，以及先验信息 A（即 H 属于某个已知的子集）。

第二步：讲最小内核

本文的核心思路可以浓缩为以下最简特例：M = 2（每个流只有两个假设），K = 2（只有两个数据流），且已知每个假设恰好有一个流（即已知信号数，A = A^{exact}_{1,1}）。

在这个特例下，问题退化为 Song and Fellouris (2017) 的经典设定。让我们用上面交代好的记号把它讲清楚：

  • 设定：M=2, K=2。假设 1 是“正常”，假设 2 是“异常”。已知恰好有一个流是正常的，一个流是异常的。即真实配置 H 要么是 (1,2)（流1正常，流2异常），要么是 (2,1)（流1异常，流2正常）。先验信息集 A = {(1,2), (2,1)}。

  • 核心思路：我们不需要分别检验每个流，而是可以同时利用两个流的信息。因为知道恰好有一个正常和一个异常，所以如果我们发现流1的证据强烈支持假设1，流2的证据强烈支持假设2，那么我们就应该停止并做出决策。但更关键的是，我们还需要确保不会把正常和异常搞反。

  • 最小内核的数学表达：

    • 对于每个流 k 和时间 n，计算对数似然比 LLR_k(n) = ℓ_k^1(n) - ℓ_k^2(n)。如果 LLR_k(n) > 0，则 MLC 认为流 k 是正常的（假设1）；反之则是异常的（假设2）。
    • 在时间 n，MLC Ĥ(n) 就是根据 LLR_k(n) 的符号来决定的。例如，如果 LLR_1(n) > 0 且 LLR_2(n) < 0，则 Ĥ(n) = (1,2)。
    • 现在，考虑 Ĥ(n) = (1,2) 的情况。我们想确保这个决策是正确的，即避免类型-(1,2)错误（把正常判为异常）和类型-(2,1)错误（把异常判为正常）。
    • 要避免类型-(1,2)错误，我们需要反对“流1是异常的”这个可能性。最接近的替代配置是 A = (2,1)（即流1异常，流2正常）。证据差距是 ℓ_{(1,2)}(n) - ℓ_{(2,1)}(n) = LLR_1(n) - LLR_2(n)。
    • 要避免类型-(2,1)错误，同样需要反对 A = (2,1)，证据差距也是 LLR_1(n) - LLR_2(n)。
    • 因此，停止规则就是：等待直到 |LLR_1(n) - LLR_2(n)| 超过某个阈值。这个差值就是“gap”，即两个流对数似然比之间的差距。当这个 gap 足够大时，我们就有信心说“流1比流2更像正常的”，从而做出正确决策。

  • 为什么这个特例是内核：

    • 它展示了核心思想：利用先验信息（已知信号数）将问题从“分别检验每个流”转化为“比较流之间的证据差距”。
    • 它揭示了“成对错误”的本质：在 M=2 时，一个类型-(1,2)错误必然伴随着一个类型-(2,1)错误，两者是成对出现的。
    • 当推广到 M ≥ 3 时，成对错误不再足够。例如，M=3 时，可能出现“循环错误”：流1被误判为假设2，流2被误判为假设3，流3被误判为假设1。此时，证据差距不再是简单的两两比较，而是需要检查循环证据（如 λ_{1,2}(n) + λ_{2,3}(n) + λ_{3,1}(n)）。本文的核心贡献之一就是识别并处理了这些循环错误。

三、这篇论文做了什么

三句话

  1. 研究了什么问题：在顺序观测的多个独立数据流上，每个流有 M ≥ 3 个候选假设，且已知关于真实假设配置的任意先验信息（如已知各假设的流数量、已知下界、互斥假设等），如何设计一个既能控制所有类型错误概率、又能最小化期望样本量的检验程序。
  2. 核心工具 / 方法：提出了一个基于最大似然配置（MLC） 和最小替代集（fAlt） 的通用顺序检验程序。该程序通过识别出与当前 MLC 最“邻近”的少数替代配置（而非所有 M^K 个），将计算复杂度从指数级降低到多项式级，并证明了其错误控制和渐近最优性。
  3. 主要结论：对于任意先验信息 A，提出的程序 (T̂, D̂) 能控制所有类型错误概率在指定水平 α 之下，并且其期望样本量渐近达到理论下界，即 E_H[T̂] ~ max_{i≠j} |log α_{j,i}| / I_{i,j}(H, A)，其中 I_{i,j}(H, A) 是依赖于先验信息和真实配置的“最小 KL 散度”。

关键设定与假设

  • 设定：K 个独立数据流，每个流 i.i.d.，每个流有 M 个简单假设（第七节扩展到复合假设）。决策是集中式的（centralized），即一个中心决策者收集所有流的数据来决定何时停止和如何决策。
  • 假设：
    • 独立性：不同流之间独立，每个流内部 i.i.d.。这是几乎所有顺序多重检验文献的标准假设。
    • KL 散度正有限：I_{i,j}^k ∈ (0, ∞)。这是确保对数似然比能提供有效证据的基本条件。
    • 先验信息集 A：已知真实配置 H ∈ A。A 可以是任意子集，但本文重点分析了四种具体形式。
  • 相比已有文献的放宽或强化：
    • 放宽：将每个流的假设从 2 个推广到 M ≥ 3 个。
    • 强化：本文的设定是集中式的，比分散式（Xing et al., 2024）更强，因为可以利用跨流信息。本文的结论也更强，因为它证明了同时在所有配置下的渐近最优性，而不仅仅是平均最优性。

主要结果

  • 定理 III.1（通用下界）：对于任何可靠程序，其期望样本量 L_H(α, A) 至少为 max_{i≠j} φ(α_sum, α_{j,i}) / I_{i,j}(H, A)，渐近等价于 max_{i≠j} |log α_{j,i}| / I_{i,j}(H, A)。这个下界是设计最优程序的基准。直觉：|log α_{j,i}| 是避免类型-(j,i)错误所需的“证据量”，I_{i,j}(H, A) 是积累这种证据的最慢速率，所以需要的时间就是它们的比值。取最大值是因为要同时防范所有类型的错误。
  • 定理 IV.1（错误控制）：提出的程序 (T̂, D̂) 几乎必然有限停止，且类型-(i,j)错误概率不超过 |Alt_{i,j}(H, A)| * exp(-a_{i,j})。因此，选择阈值 a_{i,j} = |log α_{i,j}| + log b_{i,j}(A) 就能保证错误率在 α 以下。技术难点：证明需要处理“循环错误”的可能性，但作者巧妙地利用了“最小替代集”的性质，将问题简化为对每个替代配置的单个对数似然比进行控制。
  • 定理 IV.2（渐近上界）：提出的程序 (T̂, D̂) 的期望样本量 E_H[T̂] 渐近不超过 max_{i≠j} a_{j,i} / I_{i,j}(H, A)。证明路线：通过构造一个比 T̂ 更保守的停止时间 T̂(H)（即只考虑真实配置 H 下的停止），然后证明 T̂(H) 的上界。证明的关键是利用大偏差理论（Chernoff 界）来 bound 对数似然比低于其均值的时间。
  • 推论 IV.1（渐近最优性）：结合下界和上界，当阈值按定理 IV.1 选择时，E_H[T̂] ~ L_H(α, A)，即程序是渐近最优的。

证明路线与技术技巧

  • 整体路线：

    1. 建立下界（定理 III.1）：对任意可靠程序 (T, D)，利用 Wald 恒等式和信息论不等式，将期望样本量与错误概率和 KL 散度联系起来，得到下界。
    2. 设计程序（公式 10）：基于“证据积累”的直觉，设计一个在 MLC 与所有“最小替代集”中的配置之间的对数似然比都超过阈值时才停止的程序。
    3. 证明错误控制（定理 IV.1）：利用 Ville 不等式（对鞅）来 bound 每个替代配置的对数似然比超过阈值的概率，再通过 union bound 得到总错误概率的上界。关键步骤是证明 {D̂ = A} ⊆ {∃n, ℓ_A(n) - ℓ_H(n) ≥ a_{i,j}}，即如果做出了错误决策 A，那么一定在某个时刻，A 的对数似然比超过了 H。
    4. 证明渐近上界（定理 IV.2）：构造一个比 T̂ 更保守的停止时间 T̂(H)，然后证明 T̂(H) 的期望样本量不超过下界。证明的核心是使用大偏差理论（Chernoff 界）来 bound 对数似然比低于其均值的事件概率，并证明这些概率是可和的，从而期望样本量主要由下界项决定。

  • 关键跳跃点：

    • 从“所有替代配置”到“最小替代集”（命题 IV.1）：这是本文最核心的技术贡献。证明 ℓ_{Ĥ(n)}(n) - max_{A ∈ Alt} ℓ_A(n) = ℓ_{Ĥ(n)}(n) - max_{A ∈ fAlt} ℓ_A(n)。这个跳跃依赖于一个简单的观察：如果一个替代配置 B 是另一个替代配置 A 的“子集”（即 B 只改变了更少的流），那么 ℓ_{Ĥ(n)}(n) - ℓ_B(n) 一定大于等于 ℓ_{Ĥ(n)}(n) - ℓ_A(n)。因此，最大值一定在“最小”的替代配置上达到。这个观察将计算复杂度从 O(M^K) 降低到 O(K^M) 甚至更低。
    • 处理循环错误：在已知信号数的例子中（M=3），作者发现仅仅检查成对证据（如 λ_{1,2}(n) + λ_{2,1}(n)）是不够的，还必须检查循环证据（如 λ_{1,2}(n) + λ_{2,3}(n) + λ_{3,1}(n)）。这是因为存在一种错误模式，其中三个流“轮换”了它们的假设，而没有任何一对流被直接交换。这个发现是本文区别于 Song and Fellouris (2017) 的关键。

  • 技术技巧点名：

    • Wald 恒等式：用于将期望样本量与 KL 散度联系起来（定理 III.1 证明）。
    • Ville 不等式：用于控制鞅（对数似然比过程）超过阈值的概率（定理 IV.1 证明）。
    • Chernoff 界 / 大偏差理论：用于 bound 对数似然比低于其均值的事件概率，并证明其可和性（定理 IV.2 证明，引理 C.1）。
    • 重要性采样：在数值研究中，用于高效估计极小的错误概率（如 10^{-40}）。作者推荐使用基于“最小替代集”的混合分布作为重要性分布。

真实例子与应用

本文包含一个精心设计的模拟实验（Section VI）。

  • 用的什么数据 / 场景：K=3 个独立的高斯数据流，每个流有 M=3 个假设（均值分别为 0, 1, -0.5 等，但不同流的假设均值不同）。真实配置是 H = (1,2,3)，即流1服从假设1，流2服从假设2，流3服从假设3。
  • 怎么把本文方法用上去：作者考虑了四种先验信息（从弱到强）：(i) 无先验，(ii) 弱下界（A^{lower}_{1,0,0}），(iii) 强下界（A^{lower}_{1,1,0}），(iv) 已知精确数（A^{exact}_{1,1,1}）。对于每种情况，他们根据第五节推导出的具体停止规则（如公式 17）进行模拟。
  • 得到什么结果：
    • Figure 1：展示了期望样本量随阈值（a）的变化。结果与渐近理论一致：先验信息越强，期望样本量越小。已知精确数的情况（A^{exact}_{1,1,1}）显著优于其他情况，其渐近斜率是 8a/3，而其他情况是 8a。
    • Figure 2：展示了错误概率的估计。当程序正确使用时（包含所有循环检查），实际错误概率被名义水平控制得很好。但如果故意忽略循环检查（只检查成对证据），错误概率会“爆炸”（explode），验证了循环错误的必要性。
  • 这个例子想说明什么：
    • 验证渐近最优性理论（Figure 1 右图显示比值趋近于 1）。
    • 量化先验信息的价值（Table I 和 Figure 1 显示从无先验到已知精确数，期望样本量可减少约 2/3）。
    • 强调循环错误的重要性（Figure 2 显示忽略循环检查会导致错误控制失败）。这是本文最核心的实证贡献。

🔎 结论是否比证明窄

  • 窄的地方：定理 IV.2 的证明依赖于一个比 T̂ 更保守的停止时间 T̂(H)。这意味着上界 max a_{j,i} / I_{i,j}(H, A) 可能不是紧的，尤其是当 I_{i,j}(H, A) 由多个流的最小 KL 散度决定时。作者在数值研究中验证了渐近等价性，但并未给出非渐近的有限样本界。
  • 泛泛 claim 的地方：作者在引言中声称程序是“computationally efficient”，但并未给出严格的计算复杂度分析（如 O(K^M) 的具体形式）。对于 M 和 K 都较大的情况，K^M 仍然可能很大。作者在第五节中给出了 fAlt 大小的上界 K^M，但未讨论更精细的复杂度。
  • 值得注意的 conjecture：作者在结论中提出了一些未来方向，如扩展到 FDR 控制、异步决策、二阶分析等。这些目前只是 conjecture，尚未被证明。

四、开放问题

  1. 扩展到其他错误度量：本文只控制了 FWER（族系错误率）。能否将结果推广到更宽松的错误度量，如 FDR（错误发现率）或 k-FWER？作者在结论中提到了这一点，并引用 He and Bartroff (2021) 作为二元假设下的先行工作。扎根点：Section VIII 第一段 “(i) error metrics other than the familywise error probabilities, such as (the multihypothesis version of) the false discovery rates, following He and Bartroff (2021)”。

  2. 异步决策：本文假设所有流同时停止（同步决策）。在许多实际场景中，不同流可能在不同时间做出决策。如何设计一个允许异步决策的多元假设检验程序？作者在结论中提到了这一点，并引用 Xing and Fellouris (2025b) 作为二元假设下的先行工作。扎根点：Section VIII 第一段 “(ii) asynchronous decisions, i.e., decisions for different streams are made at different times, following Xing and Fellouris (2025b)”。

  3. 二阶渐近分析：本文只提供了一阶渐近最优性（比值趋近于 1）。能否进行二阶分析，给出期望样本量的更精确近似，甚至证明其与最优值的差有界？作者在结论中提到了这一点，并引用 Liu and Song (2026) 作为二元假设下的先行工作。扎根点：Section VIII 第一段 “(iii) a second-order asymptotic analysis of the expected sample size, following Liu and Song (2026)”。

  4. 计算复杂度的严格刻画：本文虽然通过 fAlt 大幅降低了计算复杂度，但并未给出严格的复杂度分析。对于给定的先验信息 A，fAlt 的大小到底是多少？是否存在更高效的算法来动态更新 fAlt？扎根点：本文第五节虽然给出了 fAlt 的具体形式，但未讨论其计算代价。这是一个值得研究者去查的问题：能否将 fAlt 的计算与用户熟悉的张量网络 / einsum 复杂度联系起来？例如，fAlt 的枚举可能对应于某种图结构上的路径搜索，其复杂度可能与图的树宽有关。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论