Skip to content

算法Algorithm

e-BH 与任意依赖的 FDR 控制

e-BH procedure · e-Benjamini–Hochberg procedure · eBH

按降序 e 值寻找最大自洽发现集合,用逐样本预算消去随机拒绝数,在任意依赖下控制 FDR,并核对过滤与停止的边界。

五个假设给出证据 E=(30,18,17,2,0)。希望控制错误发现率为 q=0.1,而这些证据可能共享数据、相关结构又不清楚。e-BH 使用每个真零假设下的期望预算,而不要求先辨认这五个数的联合依赖类型。

它与普通 BH 一样通过“最终发现数”设定阈值,但这里大 e 值表示强证据,排序方向是从大到小。保证的来源也不同:先在每份数据上给错误比例一个上界,再对它取期望。

形式陈述 ​

输入、排序与最大通过秩 ​

固定 m 个假设。真实零假设索引集为 I0,大小 m0。每个真零索引 i 对应e 值 Ei,在该零假设的每个分布下 EEi≤1;假零对应的非负输入没有期望限制。

将实现值降序排序为 e[1]≥⋯≥e[m]。给定 0<q<1,取

k∗=max({k∈[m]:e[k]≥mqk}∪{0}).

若 k∗=0,不拒绝;否则拒绝前 k∗ 项。等价地扫描全部秩,记录满足 qke[k]≥m 的最大位置。不能在第一个未通过的位置停下。

直觉

把随机分母从证明里消掉 ​

设输出集合为 R,R=|R|,V=|R∩I0|。FDR 是

E[VR∨1].

只要 i 被拒绝,就有 Ei≥m/(qR)。因此对每个真零索引,逐份数据都有

1{i∈R}R∨1≤qmEi1{i∈R}≤qmEi.

未拒绝时左侧是零,拒绝时第一步正是阈值条件,所以随机 R 没有被偷偷当成常数。对全部 i∈I0 相加、取期望,得到

FDR≤qm∑i∈I0EEi≤qm0m≤q.

这个证明不拆解联合概率、不条件于其他证据,也不假定独立或正相关。任意依赖的结论来自“每个真零单独付得起自己的预算”,而非依赖性从数据中消失了。

例子与边界

五项证据的最大通过秩 ​

开头例的阈值为 (50,25,50/3,12.5,10)。第一、二项都没有通过各自阈值,第三项 17≥50/3 却通过,最后两项失败,所以拒绝前三项。最终三项共同使用阈值 50/3,全部满足要求。

先确定最终拒绝数,再核对共同阈值

如果临界位置有并列,不会发生任意拆开一个临界并列组的问题:若第 k+1 项与已通过的第 k 项相等,它面对的阈值更低,也必通过。实现可以用稳定排序保留索引,再按最大通过秩返回。

过滤发现集可以真的破坏 FDR ​

取 m=3,q=0.1,前两个零假设为真,第三个为假。让 (E1,E2) 以各 1/15 的概率取 (15,0)、(0,15),其余取 (0,0);令 E3=30 恒定。两个真零证据的边际均值都恰为一。

有活动真零证据时,排序为 (30,15,0),e-BH 拒绝前两项,FDP 为 1/2;无活动时只拒绝第三项,FDP 为零。因此 FDR 为

215⋅12=115≤0.1.

如果发表时只保留编号一、二,删除第三项,输出就以概率 2/15 含一个错误发现,其余为空。FDR 上升到 2/15>0.1。新的单项集合要求证据至少三十,活动真零只有十五,正好违反自洽性。

这也是为什么“删掉一些发现总会更保守”不适用于错误比例:删除的可能是真发现,分母下降得比错误数更快。若希望任意事后选择集合并获得高概率比例上界,应使用同时 FDP 保证。

推论与应用

自洽性还容许额外选择约束 ​

上面的证明只用到:若 i∈S,则 Ei≥m/(q|S|)。任何可测选择规则,只要输出 S 满足这条自洽性,都继承同样的 FDR 上界。于是可以在自洽集合中加入空间连通、成本上限等选择偏好;如何有效寻找集合是另一个计算问题。

e-BH 是没有额外限制时最大的自洽集合。若一个集合 S 有 r 项,每项至少 m/(qr),则降序第 r 项也达到这个阈值,所以 r≤k∗。而 S 的每项达到 m/(qr)≥m/(qk∗),必属于 e-BH 的阈值集合。

这是保留完整家族大小 m 的结论。筛完再把分母中的 m 换成保留数量,或缩小集合后沿用较宽的旧阈值,都需要新的校准。

固定 e 值、过程与拒绝记录 ​

可以让每个输入来自一个合法 e-process 在同一有限停时的值,但该过程必须对包含全部相关信息的共同滤过保持停时有效性。仅对自己一条数据流有效,而停止规则还观察别的相关数据,不自动满足条件。

更重要的是,本页控制的是一次输出集合的 FDR。每天运行一次、把历次所有拒绝并在一起,不是本页证明的同一个集合;即使每次输入都合法,也没有自动得到“曾经拒绝过”的 FDR 保证。运行最大 e 值一般也不再满足均值一预算。

成本、转换与验证 ​

标准实现排序需要 O(mlog⁡m) 时间,扫描 O(m),保存证据和原索引需要 O(m) 空间。若证据以对数存储,可比较 log⁡e[k]≥log⁡m−log⁡q−log⁡k,避免大数溢出;零证据的对数记为负无穷。

先用预定校准器把 p 值转为 e 值,再运行本程序也有效。反过来,形式上对 pi=min(1,1/Ei) 应用 BH,会得到相同拒绝集,但其任意依赖保证来自 e 值的额外期望结构;不能据此断言普通任意依赖 p 值也无需修正。

迁移自测。 把开头第三项由十七改成十六,前三个秩都失败,第四、五个秩也失败,所以发现数从三变成零。若把第三项提高到十八,则仍为三。这个跳变来自共同阈值的自洽条件,说明审计应保留全部比较值,而不是只报告前三项。

参考资料
关系图谱6 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系