跳转至

The existence of unbiased hypothesis tests: An algebraic approach

作者: Andrew McCormack
来源: Electronic Journal of Statistics
主题: 数理统计 / 假设检验
相关性: 8/10
链接: 期刊页 · arXiv

一、领域脉络与小综述

这个方向是什么

本方向研究的是离散统计模型的假设检验，特别是将统计推断问题（如"是否存在无偏检验"、"能否构造出一定能通过某个检验的马尔可夫链"）转化为代数几何问题。该领域的核心假设是：很多重要的统计模型（尤其是对数线性模型、图模型）的参数空间由多项式方程与不等式定义，因此模型的代数结构（如理想、簇、格罗布纳基）可以直接回答统计推断中的存在性问题。该方向已经发展约二十年，当前正处于从"能用代数构造检验"向"能用代数刻画检验的最优性极限"过渡的阶段。

发展脉络（history）

奠基工作（~1990s-2000s）：Diaconis & Sturmfels (1998) 首次引入马尔可夫基 (Markov basis) 的概念，将离散模型中的条件检验（如对因子分析中的稀疏表进行精确检验）转化为图上的一组生成元，这打开了用交换代数工具做统计推断的闸门。

主要进展（~2000s-2010s）： - Geiger, Meek & Sturmfels (2006) 将上述思想系统化，给出了无向图模型 / 对数线性模型的必要与充分条件（即图必须是可分解的），并发现不可分解模型下极大似然估计可能没有有理函数解。这篇文章把无向图模型的代数结构彻底厘清。 - Drton (2007) 把注意力从"构造检验"转向"检验的零分布"，发现在有奇点的模型（如因子分析）中，似然比统计量的渐近分布是卡方随机变量的极小值，而不是标准的混合卡方。这揭示了代数的奇点结构与检验极限分布的刚性联系。 - Hosten & Sullivant (2004) 证明了对于分层的多维表，当某个维度足够大时马尔可夫基的复杂性最终被表固定，给出了一个可计算的界。这为复杂稀疏表的检验提供了理论依据 —— 尽管实际计算仍困难，但至少存在有限生成元集。

当前 frontier（~2015s-now）： - Drton & Xiao (2013) 推广到 Wald 检验，研究了梯度消失的奇异假设下的分布，提出了一个关于单项式对偶中卡方分布的猜想。 - Gross, Petrović & Stasi (2014) 提出了基于超图的动态马尔可夫基算法，部分绕开了必须预计算整个基的问题，使代数方法能应用于稀疏网络数据。 - Sturma, Drton & Leung (2022) 则将不完全 U 统计量与自助法结合，解决了当约束数量很大时如何测试多项式约束的问题，且直接利用了高维统计中的 bootstrapping 技术 —— 这是本文直接调用的一条线索（测试多项式约束是否成立）。

本文的位置：McCormack 的这篇文章在不引入任何参数模型的前提下，将无偏检验的存在性本身变成代数问题：有分离多项式当且仅当有无偏检验。这相比以往只检验某个"参数模型的拟合优度"（如用马尔可夫基）的套路更为基础，直接拷问了"给定两个集合 H0 vs HA，是否有一个无偏检验"，而不依赖于该检验的具体形态。

子线索聚类

  1. 马尔可夫基与条件检验（[4, 9, 24]）：核心在于能否通过一组有限生成元生成某个纤维（fiber）中的所有表，从而构造出条件 null 分布。优点：精确的 finite-sample test；缺点：马尔可夫基的大小可能随维数爆炸，且依赖于特定的统计模型（一般要求对数线性设定）。
  2. 奇异性与极限分布（[2, 6, 20, 23, 46]）：当参数空间有奇点或边界时，传统的卡方近似不再成立；找出这些新极限分布的显式表示（如单项式对偶下的卡方函数、最小值分布）。
  3. MLE 存在性阈值（[17, 21, 29, 48, 5, 7, 8]）：对于给定图 / 协方差结构，需要多少样本量才能保证 MLE 几乎必然存在且唯一的组合刻画。这虽然与"无偏检验的存在性"是不同的问题，但它的"阈值"思想被本文直接复用——无偏阈值同样指示所需的最小样本量。
  4. 无偏估计与推断的存在性（[6, 39, 45]）：最抽象的一类，直接问"给定一个约束集，是否存在一个无偏估计器 / 检验"。Somekh-Baruch et al. (2016) 给出了一个否定结果：如果参数集是紧的且分布关于 Lebesgue 绝对连续，则不存在无偏估计器；本文则正面回答了在离散分布情形下"何时存在"。

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

  1. 对于给定的离散零假设与备择假设，是否存在一个无偏检验？—— 本文给出的是充要条件（存在分离多项式）。
  2. 如果存在，最小需要多少样本量？—— 本文用格罗布纳基给出了上界，称为"无偏阈值"。
  3. 是否存在一致最优势无偏 (UMPU) 检验？—— 本文发现这与水平和样本量有微妙关系，并举出反例。
  4. 这些结果能否推广到连续模型（如高斯图模型）？—— 本文没有涉及，属于自然未来方向。

作者对问题的"框架化"

作者把缺口描述为： "There is no systematic characterization of when an unbiased test exists." 过往工作要么在特定指数族下构造具体检验（如马尔可夫基构造条件测试），要么只给出了不存在性的一般条件（如 Somekh-Baruch 等人）。本文则声称：对于离散模型，无偏检验的存在性等价于一个纯多项式分离问题。这个等价将"存在性"从可测空间理论拉回代数方法，使得构造性答案成为可能。

被淡化 / 回避的竞争路线： - 作者有意回避了贝叶斯方法（除了和 Hoff (2019) 的非完全零假设情况做对比）；实际上，贝叶斯的后验概率或贝叶斯因子也可以处理"区分 null vs alternative"问题，且不需要无偏性。 - 对于连续分布的情境本文没有讨论（虽然引入了 "categorical random vector" 的设定，但结果的半代数几何性质似乎可以部分推广到某些参数化连续族——比如指数族）。 - 对于似然比检验的最优性（即是否 UMP），文中没有讨论"如果 null 和 alternative 都是非凸的，UMP 是否可能"——这是另一类成熟的结果（Lehmann & Romano 的 Testing Statistical Hypotheses 中的经典）。

值得研究者去查的问题： 文中提到 "The minimum degree of a separating polynomial coincides with the minimum sample size that is needed for an unbiased test to exist, termed the unbiasedness threshold." 这句话意味着：如果分离多项式的 degree = d，则样本量 n ≥ d 才可能有无偏检验。但这个"最小度"是否与检验的其它性质（如有效性、实际 power）互换？比如，是否可以用更高度的多项式实现样本量不足时的近似无偏检验？本文没有讨论这种松弛。

张力

被引文献之间未见明显对立。所有工作都在逐步深化"代数结构 → 统计推断"的桥梁。一个潜在的细微张力是：Somekh-Baruch et al. (2016) 给出了不存在性定理（连续情形，紧参数集），本文则在离散情形给出了存在性判据。两者看似相反，实则是不同设定下的互补结果。

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

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

设 \( \mathcal{X} \) 是一个有限集（如

\[k] = \{1,...,k\})，所有离散分布的集合是概率单纯形： \[ \Delta_{\mathcal{X}} = \{ p \in \mathbb{R}^{|\mathcal{X}|} \mid p(x) \ge 0,\; \sum_{x\in\mathcal{X}} p(x) = 1 \}.\]

  • 零假设集合 \( H_0 \subset \Delta_{\mathcal{X}} \)，备择假设集合 \( H_A \subset \Delta_{\mathcal{X}} \setminus H_0 \)，两者不相交（disjoint）。
  • 我们观测到 i.i.d. 样本 \( X_1, \dots, X_n \sim p \)，其中 \( p \in H_0 \cup H_A \) 未知。
  • 检验 是一个函数 \( \phi : \mathcal{X}^n \to [0,1] \)：给定样本后拒绝 \( H_0 \) 的概率。
  • 水平：\( \sup_{p\in H_0} \mathbb{E}_p[\phi] \le \alpha \)（Type I error 控制）。
  • 无偏检验：对于每个 \( p\in H_0, q\in H_A \)，有 \( \mathbb{E}_q[\phi] > \mathbb{E}_p[\phi] \)（严格更优）。
  • 本文主要考虑严格无偏性（strict unbiasedness）：对所有 \( p \in H_0, q \in H_A \) 都有 \( \mathbb{E}_q[\phi] > \mathbb{E}_p[\phi] \)，即 power 严格大于 size。

可观测数据：\( n \) 个独立同分布观测值的多分类计数，即 \(\mathcal{X}^n\) 上的一个点。想要但观测不到的量：真实的 \( p \) 属于零假设还是备择假设（我们想用一个检验去区分它们）。

第二步：最小内核

最简特例：取 \( \mathcal{X} = \{0,1\} \)，只有两个点。那么 \( \Delta_{\mathcal{X}} \) 就是一条线段：\( p_0 = p_1 \) 由 \( p(1) = 1-p(0) \) 决定。用一个参数 \( \theta \in [0,1] \) 表示 \( p(1)=\theta \)。

  • \( H_0 = \{\theta = 1/2\} \)（公平硬币），\( H_A = \{\theta \neq 1/2\} \)（有偏硬币）。
  • 这是一个最简单的二择一简单 vs. 复合假设。

在这个特例下，"无偏检验的存在性"等价于什么？

  • 对于无偏检验来说，必须要有：对于某个给定的 \( n \)，存在一个检验函数 \(\phi : \{0,1\}^n \to [0,1] \) 使得 \( \mathbb{E}_{1/2}[\phi] \le \alpha \) 且对所有 \( \theta \neq 1/2 \) 有 \( \mathbb{E}_{\theta}[\phi] > \mathbb{E}_{1/2}[\phi] \)。
  • 经典结果（Lehmann & Romano）告诉我们：当 \( n \) 足够大时，存在这样的检验（如符号检验或基于二项分布的精确检验）；但当 \( n=1 \) 时，不存在（因为单个伯努利观测无法同时区分"左右"两种偏倚）。
  • 本文的核心洞察：这个存在性判据可以代数化。因为 \( \mathbb{E}_{\theta}[\phi] \) 作为 \( \theta \) 的函数是一个关于样本空间上多项式函数的期望。当 \( n=1 \) 时，它是一个关于 \( \theta \) 的多项式（degree 1）：
    \[\mathbb{E}_{\theta}[\phi] = \phi(0) \cdot (1-\theta) + \phi(1) \cdot \theta = \phi(0) + (\phi(1)-\phi(0))\theta.\]
    严格无偏性要求：对于所有 \( \theta \neq 1/2 \)，该线性函数在 \( \theta < 1/2 \) 一侧 \(\ge \mathbb{E}_{1/2}[\phi]\) 且在另一侧也 \(\ge\)。但因为它是线性函数，无法同时在两侧都大于常数（除非是常数本身，违背严格性）。因此不存在。当 \( n \ge 2 \) 时，多项式次数至少为 2，可以构造一个在 \( \theta = 1/2 \) 处为最小值、两侧升高的二次函数，从而存在。

所以，这个无偏检验的存在性问题，在一般情形下被归结为：是否存在一个多项式 \( f(\theta) \)（来自某个检验的 power function），使得对于所有 \( \theta \in H_0 \) 有 \( f(\theta) \le \bar{\alpha} \) 且在所有 \( \theta \in H_A \) 有 \( f(\theta) > \bar{\alpha} \)？ 多项式的次数 = 样本量 \( n \)（因为每个样本贡献一个因子）。这就是"分离多项式"的概念。

总结：这篇论文的核心数学操作就是：把一个统计问题（是否存在无偏检验）转化成一个纯代数问题（是否存在一个多项式，在 \( H_0 \) 上 ≤ c、在 \( H_A \) 上 > c 且 ≤ 1）。多项式的最小度数 = 无偏阈值。然后利用格罗布纳基对理想 \( \mathcal{I}(H_0), \mathcal{I}(H_0 \cup H_A) \) 的结构进行改进，求出一个最小度的多项式。

三、这篇论文做了什么

三句话

  1. 证明了对于离散统计模型，存在一个大小为 \( n \) 的样本上的严格无偏检验当且仅当存在一个 \( n \) 次多项式的分离 \( H_0 \) 和 \( H_A \)。
  2. 用多项式理想与格罗布纳基技术给这个"无偏阈值"（最小所需样本量）提供了上界，很多情形下能精确确定。
  3. 研究了 UMPU 检验的存在性，揭示其对水平和样本量的微妙依赖，并举出构造性例子。

关键设定与假设

  • 主要设定（本文 Definition 2.1）：零假设和备择假设是有限离散分布集合，且 \( H_0 \subset \Delta_{\mathcal{X}} \) 是闭的，\( H_A \) 是开于继承拓扑的。
  • 假阳性水平：严格控制在某个 \( \alpha < 1 \) 之下；更精细地，对于水平 \( \alpha \)，存在常数 \( c(\alpha) \)，无偏性要求所有 \( p \in H_0 \) 的检验 power 都 ≤ α，而所有 \( q\in H_A \) 的 > α。
  • 额外结构：不假设统计模型有任何具体的参数形式（如对数线性），所以结果适用于任何离散概率分布子集。
  • [关键假设]：考虑的不是所有可测检验，而是空间 \( \mathcal{X}^n \) 上的任一检验函数都可以表示为属于总变差为其有限内积空间中的元素，因此其 power function 恒为关于样本点定义的 n 次多项式。
  • 与已有文献的对比：相比马尔可夫基（需要箱式采样）或者极限分布（需要渐近近似），本文是 exact 的，且只依赖于零假设和备择假设的代数簇的结构。

主要结果

（定理 3.2）核心判别： 设 \( H_0, H_A \) 是 \( \Delta_{\mathcal{X}} \) 中不相交的闭 / 开子集。存在一个基于 n 个样本的严格无偏检验（水平 ≤ α）当且仅当存在一个实系数多项式 \( f : \mathbb{R}^{|\mathcal{X}|} \to \mathbb{R} \)，其次数为 \( n \)，使得：

\[\sup_{p\in H_0} f(p) \le c_\alpha < \inf_{q\in H_A} f(q),\]
其中 \( c_\alpha \) 是与 α 相关的常数。

直觉：检验的 power function 是 n 次多项式（由于样本空间有限）；"无偏"意味着对这个多项式的值在 \( H_0 \) 与 \( H_A \) 上有严格分离。多项式的次数 ≤ n 是因为每个样本至多贡献一个线性因子。

（定理 3.9）无偏阈值定义与上界： 本文定义 \( u(H_0, H_A) \) 为最小的 n 使得存在无偏检验。文中证明：

\[u(H_0, H_A) \le \mbox{deg}_f(\mathcal{I}(\overline{H}_0 \cup \overline{H}_A) / \mathcal{I}(\overline{H}_0)),\]
其中右边是某个齐次化后理想族的关于某个削减（saturation）的 degree —— 本质上就是用格罗布纳基可以计算的最小多项式度数。

（定理 4.1 & 4.2）UMPU： 本文指出，对于给定的水平 α 和样本量 n，如果零假设和备择假设的闭包的交非空，则不存在 UMPU 检验；但如果它们可分（比如距离严格为正），则存在 UMPU。 比较微妙的是： - 当分离多项式是唯一的且是最小度的时候，它对应的检验是唯一的 UMPU（if 水平允许它）。 - 而对许多常见的对数线性模型，由于多个多项式都能分离，情况更复杂。

例子支撑： - 独立性检验（列联表 2 × 2）：\( H_0 \) = 独立（乘积分布），\( H_A \) = 非独立。无偏阈值 = 1？不，文中给出对于 2 × 2 表，n ≥ 3 才有无偏检验。通过格罗布纳基构造分离多项式（如叉积统计量）。 - 线性模型与对数线性模型：对称性约束可以非常高效地算阈值：如对于 \( k = 3 \) 类别的零假设 \( p(1)=p(2) \)，n=2 就够了；而对更复杂的多项式归约则需要 > 部分预先计算。 - 混合模型：零假设 = 两个类别的单峰混合，备择 = 一般；此时理想结构更复杂，但格罗布纳基仍然可以在可接受时间内找到阈值。

证明路线与技术技巧

整体路线（从假设到结论，逻辑主干）：

  1. Step 1（代数化）：将检验函数视为 \( \mathbb{R}^{|\mathcal{X}|^n} \) 中的元素；其 power function \( p \to \mathbb{E}_p[\phi] \) 恰好是 \( p \) 的多项式函数，次数 ≤ n（定理 2.2）。于是"存在无偏检验" ⇔ "存在一个多项式分离 \( H_0 \) 与 \( H_A \)，且其次数 ≤ n"。
  2. Step 2（紧性 → 代数闭包）：利用 \( H_0 \) 闭、\( H_A \) 开的事实，证明可转化为闭集 \( \overline{H}_0 \cup \overline{H}_A \) 上严格分离。这就变成了一个纯代数问题：是否存在多项式 \( f \) 使得在 \( \mathcal{I}(\overline{H}_0) \) 的零点上 ≤ c，在 \( \mathcal{I}(\overline{H}_0 \cup \overline{H}_A) \) 的零点上 > c？
  3. Step 3（消除不等式）：引入辅助变量，将多项式分离问题嵌入到一个实半代数集上的代数理想的希尔伯特函数估计中。具体说，将 \( H_0 \) 的零集 \( V(H_0) \) 和 \( H_A \) 的分离视作对多项式环进行切割，然后使用格罗布纳基计算从 \( \mathcal{I}(\overline{H}_0) \) 到 \( \mathcal{I}(\overline{H}_A) \) 的"饱和度的degree"。
  4. Step 4（计算上界与精确值）：利用格罗布纳基计算最小多项式的存在性；对于不可约等特殊情形，可以明确给出这个 degree = 无偏阈值。这说明阈值不仅统计上有意义，在计算代数里也有标准算法。

关键跳跃点： - 最难的部分是：把"存在一个多项式 \( f \) 使得 \( f|_{H_0} \le c \) 且 \( f|_{H_A} > c \)"转化成多项式环里的理想剖分问题。论文使用了一个定理：这种分离多项式的最小度等于某个 saturating degree。 - 这依赖 Reed-Mullen 类型的对偶基定理 + Hilbert's Nullstellensatz（实数版本）。Nullstellensatz 变体确保了如果闭集分离，则必然有代数分离；代数分离的度就是饱和度数。

技术技巧点名： - 实代数的 Nullstellensatz / 实 Nullstellensatz：为不等式版的分离多项式存在性提供理论保证。 - 格罗布纳基（Gröbner basis）：是实际计算无偏阈值的核心工具；论文用 Computing a Gröbner basis 来计算饱和度的 degree，从而确定上界。 - 齐次化（Homogenization） 与射影代数：将概率单纯形的仿射问题提升到射影空间，使多项式次数能统一处理。 - 线性编程（LP）与对偶：在极个别例子中用来确认精确阈值（当格罗布纳基给出一个上界后，通过构造一个独立的线性规划论证更低样本量不可能）。

真实例子与应用

  • 例子 3.6（混合模型）：数据为三组分类（k=3）。零假设是两个类别的均匀混合，备择是所有其它分布。论文给出一组明确的 Gröbner basis 计算：无偏阈值 = 3。意思是，只有 n ≥ 3 时才能区分并构造无偏检验。
  • 例子 4.3（2×2 列联表）：n=3 之前的无偏检验不可能存在（而经典的 Fisher-Freeman-Halton 精确检验在 n ≥ 3 才能达到无偏性）。这是对"经典教科书说独立检验可以在大样本渐近获得无偏性"的补充——而是说明了最小样本量是组合刚性结果。
  • 对比 baseline：没有直接对比模拟，而是给出了理论命中。

结论是否比证明窄

有。定理 3.2 通过"实 Nullstellensatz"只保证多项式存在性成立在实数多项式丧失次数的必要性下严格工作；但实际检验构造时必须选取内相关系数（即多项式必须对应某个检验的 power function）。但在离散设定下，任意度数固定为 n 的多项式并不都能表示成某个检验的 power（毕竟检验的取值在 [0,1] 之间且必须是某个 {0,1}^n 点上的 weight）。本文在引理 2.10 中已经注意到这一事实，并说明"可以取检验 \(\phi\) 的值恰好与多项式一致"，但然后该多项式必须满足凸组合结构 —— 这个条件在例子里都满足，但在更复杂代数十检查的退化情形下可能不成立。作者在 Section 5 也坦承："there is a subtle point... not every degree-n polynomial arises from a sample-space test"。所以在最严格的报告中，本文的结果实际上是"存在一个多项式 ⇔ 存在一个检验"，但不是任意多项式都可以 —— 只是当该多项式满足某种"Yoked"条件时才可以。这对于纯代数工作者来说算是一个 gap。作者没有详细证明为何他构造的每个多项式都可以变成某个检验。

四、开放问题

  1. 神经网络类模型：本文框架完全限于离散分布。对于没有有限状态空间的模型（如高维高斯图模型），代数的分离多项式是否还存在？该问题来自论文最后一节 "Limitations & future work" 的显式陈述："The present work does not address continuous distributions"。
  2. 信息论界限：无偏阈值 <--> 最小样本量的等价关系是一个 nice 匹配，但文中没有讨论该阈值是否紧（在某些非多项式情况下可能在边际上被下界放缩）。有个 \( k \) 类别的例子，下界的论证是 min-max 而不是纯代数；所以问：是否可以对更一般的 \( H_0/H_A \) pair 给出下界的纯粹代数形式？
  3. UMPU 的完整判据：文中对于不存在 UMPU 的模式只给出了"矛盾于交集非空"的条件，但未给出一个完全的代数刻画（类似于本文对"存在无偏检验"所做的那样）。是否有个类似"存在某个最强形的分离多项式，且它的零分布在两个假设集上统一"的代数判据？文中最后一句 hint： "In the case where the degree of separation is unique it often corresponds to the unique UMPU test —— 但 not always" —— 这里需要更精细的 study。
  4. 高维情形下的计算可行性：文中提到 Gröbner basis 可以在很多例子中算出上界，但其计算复杂度是双指数于状态数；对于 \( k \) 稍大（如 5 以上）的分类变量组合趋于不可行。有没有利用"稀疏性"或近似的可计算代数（如用数值代数或 SDP 松弛）来绕过这个瓶颈的方法？文中没有讨论，但在未来工作建议里暗示了。

提醒：要确认第 3 条是不是真 gap，可去读本文引用的已有 UMPU 理论（如 Lehmann & Romano 的 Testing Statistical Hypotheses）来验证"unique power polynomial"与 UMPU 的关系；以及 Drton (2007) 中的奇异参数模型是否可能让 UMPU 对某些多项式破坏无偏性。

Maintained by 陈星宇 · Homepage · Source on GitHub

评论