为了最小化关于一个随机向量的序贯测试中预期的总采样成本

《Journal of Multivariate Analysis》：To minimize the expected total sampling cost in sequential testing about a random vector

　　标题：基于序列采样的随机向量分布的多假设检验问题研究
中国上海同济大学数学科学学院

摘要
本文研究了基于序列抽取的观测数据对随机向量分布进行多重假设检验的问题。假设从不同维度子集进行采样会产生不同的成本，目标是尽可能降低预期的总采样成本，同时将错误识别真实假设的概率控制在用户指定的水平以下。所提出的检验程序被证明能够在假设水平趋于零的情况下渐近地实现这一目标。具体而言，该方法通过贪婪地遵循当前最大似然假设的最优采样分布，并保证对所有维度进行充分的探索；当某个假设的似然度明显高于其他所有假设时，该程序会选择该假设作为最终结果。文中以多元高斯分布为例进行了数值研究以说明其可行性。

引言
设 \(X(1),X(2),\cdots\) 是一系列独立的 \(d\)-维随机向量。用 \(f\) 表示它们的共同概率密度，并考虑以下多假设检验问题：存在 \(M\geq2\) 个不同的概率密度 \(f_1,\cdots,f_M\)，我们需要检验 \(f = f_1\) 是否成立。在每个时间点 \(n\in\{1,2,\cdots\}\)，我们可以选择从全部或部分维度中抽样，记为 \(S(n)\subseteq[d]\)，从而获得向量 \(X_n\) 的全部或部分数据。显然，更大的 \(S(n)\) 提供了更多信息，有助于解决检验问题。然而，从更大的维度子集抽样通常会带来更高的成本。这导致在最大化信息收益与最小化采样成本之间需要权衡。值得注意的是，虽然我们使用了“采样成本”这个术语，但实际上成本可能来源于多个方面，如抽样、数据传输、计算等。

例如，在水印检测问题中（Li等人，2025年），为了判断文本是由人类生成、ChatGPT还是其他大型语言模型生成的，加入更多特征（如n-gram频率和语法复杂性）可以提高分类准确性，但会增加计算成本。在精准医疗的发展中（Kosorok和Laber，2019年），为了确定最有效的治疗方案，比较更多的生物标志物可以提高识别能力，但会导致更高的实验室检测成本和志愿者风险。在信号/异常检测问题中（Chandola等人，2009年），覆盖更多位置可以加快发现速度，但会增加监控和数据处理成本。在自动驾驶系统中（Yurtsever等人，2020年），开启更多感知功能可以提高环境感知能力，但可能会延迟响应时间。

尽管这个问题非常直观且在多种场景中都有应用，但据作者所知，在文献中并未受到足够的关注。本文的目的是对这个问题进行形式化，并提供一个渐近最优的解决方案。具体来说，这个解决方案包括一个采样规则、一个停止规则和一个决策规则。在每个时间点开始时，根据截至该时间点的所有可用信息，采样规则决定从哪些维度子集中进行抽样；抽样后，根据收集到的新信息，停止规则判断是否已经收集到足够的证据以停止采样过程并做出决策。如果不够，则继续到下一个时间点；如果足够，则决策规则决定选择哪个假设。用 \(S := (S(1),S(2),\cdots)\) 表示采样规则，\(T\) 表示停止规则，\(D\) 表示决策规则。检验过程的总采样成本为 \(\sum_{n=1}^M T_C(S(n))\)，其中 \(C(B)\) 表示从维度子集 \(B\subseteq[d]\) 中抽样的成本。同时，该检验过程可能会犯 \(M(M-1)\) 种类型的错误，即当真实假设为 \(i\) 时，会发生 \(D=j\) 的情况（对于所有 \(i,j\in[M]\) 且 \(i \neq j\)）。我们采用了一种受限优化方法，即在控制所有错误类型概率低于期望水平的条件下，最小化预期的总采样成本，即 \(E_i\sum_{n=1}^M T_C(S(n))\leq \alpha_{i,j}\) 对所有 \(i,j\in[M],j\in[M]\setminus\{i\}\) 成立，其中 \(\alpha_{i,j}\) 表示错误选择假设 \(j\) 的概率水平。

在本文中，我们提出了一种检验方法，该方法在 \(\alpha_* \rightarrow 0\) 的渐近意义上解决了这个受限优化问题。我们首先为满足错误概率约束的所有检验方法建立了一个最优预期总采样成本的通用下界，然后证明这也是所提出检验方法的渐近上界。该下界提供了一种针对每个假设的最优采样策略，即在 \([d]\) 的幂集上以某种概率选择每个子集进行抽样。所提出的检验方法在程序开始时和在稀疏时刻贪婪地遵循当前最大似然假设的最优采样分布，并保证对所有维度进行充分探索。当最大似然假设的似然度与其他假设的似然度之间的差距超过某个阈值（该阈值与错误概率水平的对数成比例）时，该方法停止抽样，并选择最大似然假设作为最终决策。渐近最优性理论的唯一分布假设是，基于所有维度，集合 \(\{f_i\}_{i\in[M]}\) 中任意两个概率密度之间的Kullback–Leibler信息数是正的且有限的。文中以多元高斯分布为例进行了数值研究，比较了所提出检验方法与简单检验方法（如循环选择采样窗口或始终使用完整采样窗口的方法）的性能。

本文探讨的问题属于序贯检验领域（Wald，1947年；Chernoff，1959年），它涉及基于随时间顺序抽取的数据进行假设检验。这与固定样本量检验（Neyman和Pearson，1933年）不同，在后者中，所有数据在检验之前就已经收集完毕。此外，本文讨论的序贯检验问题涉及多个竞争假设，不同于传统的两个假设设置。这种框架称为多假设检验（Baum和Veeravalli，1994年；Draglia等人，1999年；Dragalin等人，2000年；Lai，2000年；Nitinawarat等人，2013年；Nitinawarat和Veeravalli，2015年；Deshmukh等人，2021年；Xing和Fellouris，2024a；Xing等人，2024年；Xing和Fellouris，2025a），它自然出现在存在正常状态和异常状态之间过渡的情况，或者需要将信号分类到多个不同类别的情况下。

根据是否允许干预数据采样过程，序贯检验问题可以分为两类。第一类认为数据采样过程是被动的，即采样方式是预先确定的且不可改变的。这种方法已得到广泛研究（例如Wald，1947年；Kiefer和Weiss，1957年；Lorden，1976年；Baum和Veeravalli，1994年；Draglia等人，1999年；Dragalin等人，2000年；Tartakovsky等人，2014年；Xing和Fellouris，2024a；Xing和Fellouris，2024b；Xing和Fellouris，2025a）。这类问题通常针对单一数据序列的分布进行检验。第二类允许主动干预数据采样过程，例如通过选择不同的实验或采取不同的行动。这一方向被以多种名称进行探讨：Chernoff（1959年；Bessler，1960年；Albert，1961年；Kiefer和Sacks，1963年；Keener，1984年；Lalley和Lorden，1986年；Tsopelakos和Fellouris，2023年；Tsopelakos和Fellouris，2025年）中的序贯实验设计；Nitinawarat等人（2013年；Nitinawarat和Veeravalli，2015年；Deshmukh等人，2021年）中的控制感知；Naghshvar和Javidi（2013年；Cohen和Zhao，2015年；Huang等人，2018年；Hemo等人，2020年；Gafni等人，2023年；Szostak和Cohen，2024年）中的主动假设检验。本文可以看作是第二类的一个特例，专门用于在每个时间点主动选择观测维度子集的情况下，对独立同分布随机向量序列的分布进行检验。

另一个相关主题是在固定置信度下识别最优臂的问题（例如Garivier和Kaufmann，2016年；Prabhu等人，2022年；Lattimore和Szepesvári（2020年）的第33章），其目标是在控制错误识别概率的同时，尽快识别出具有最大均值的最优臂。与这个主题相比，我们考虑了更一般的检验问题，并采用了更精细的错误度量标准。

第2节中我们提出了问题的形式化表述。第3节建立了最优预期总采样成本的渐近下界，这为第4节中描述的检验程序提供了理论基础。第5节进行了一些数值研究，第6节总结并提出了一些未解决的问题。所有证明都放在第7节中。

问题的形式化
设 \(X(1),X(2),\cdots\) 是一系列独立的 \(d\)-维随机向量，其概率密度为 \(f(x)\)，\(x\in\mathbb{R}^d\)，且关于某个\(\sigma\)-有限测度\(\nu\)。考虑检验 \(M\geq2\) 个假设 \(f_1\leq f_2\leq \ldots\leq f_M\)。在每个时间点 \(n\geq1\)，我们可以选择从全部或部分维度 \(S(n)\subseteq[d]\) 中抽取随机向量 \(X_n\)，这会产生成本 \(C(S(n))\)，其中 \(\{C(B):B\subseteq[d]\} \in (0,\infty)\)。用 \(S := (S(1),S(2),\cdots)\) 表示采样规则，如果对于所有 \(n\geq1\)，\(S(n)\) 仅依赖于之前的信息。根据引理1和相关的实际情况，邢一鸣感谢以下机构的资助：国家自然科学基金会（项目编号12501379）、中国上海“星声计划”（项目编号24YF2748500）、华东师范大学统计学与数据科学高级理论与应用重点实验室开放研究基金（教育部项目编号KLATASDS2501）。此外，他还想向他的女儿之星星（在本书稿编写期间出生）及其母亲余禾表示衷心的感谢。