Knockoff 符号筛选 | Codeboy's Blog

形式陈述

输入是带方向的竞争分数

设共有 $p\ge1$ 项假设，真实零集合为固定的 $H_0\subseteq\{1,\ldots,p\}$ 。算法看到实值分数 $W=(W_1,\ldots,W_p)$ ：大的正值支持选入，大的负值表示其替身更有竞争力。真实 $H_0$ 用于证明，算法不必知道它。

关键假设是联合条件符号公平性：给定全部 $|W_j|$ 及所有 $j\notin H_0$ 的 $W_j$ 后， $H_0$ 中非零分数的符号是相互独立的公平正负号。零分数没有需要随机化的符号。这个假设允许绝对值强烈依赖，也允许非零假设坐标之间任意相关；它不是说各个 $W_j$ 彼此独立。

固定 $q\in(0,1)$ ，令 $\mathcal T=\{|W_j|:|W_j|>0\}$ 。Knockoff+取

T=\min\left\{t\in\mathcal T: \frac{1+\#\{j:W_j\le-t\}}{\#\{j:W_j\ge t\}\vee1}\le q\right\}, \qquad \widehat S=\{j:W_j\ge T\}. \tag{1}

若候选集合为空，约定 $T=\infty$ 、 $\widehat S=\varnothing$ 。分数均为有限实数。分母的 $\vee1$ 表示与1取最大值；由于 $q<1$ ，一个合格的有限阈值必有正分数入选。

本页采用FDP与FDR的通常定义，结论为

E\!\left[\frac{|\widehat S\cap H_0|}{|\widehat S|\vee1}\right]\le q. \tag{2}

这控制重复运行的错误比例均值。它不声称每次输出的错误比例都不超过 $q$ ，也不声称能选出全部非零假设。

可执行的阈值扫描

先按不同的正绝对值从小到大排列。初始计数包括全部非零分数，每到一个候选 $t$ ，计算式(1)的正、负计数；第一个合格值即停止。不合格时，整组删去 $|W_j|=t$ 的分数，再检查下一个值。并列必须整组处理，不能靠有利的符号顺序拆开同一个绝对值。

排序需要 $O(p\log p)$ 次比较，随后每项至多删一次，计数为 $O(p)$ ；保存排序索引和输出需要 $O(p)$ 空间。这里不包括生成 $W$ 的成本。精确有理输入可用整数交叉相乘比较比例，避免浮点边界把“ $\le q$ ”误判。由 $1+\#\{W_j\le-T\}\ge1$ 还知道，任何非空输出都满足 $|\widehat S|\ge\lceil1/q\rceil$ 。

直觉

对于真正无效的变量，原变量和替身应没有系统性优势。于是超过同一绝对值门槛的负分数，可以帮助估计同一门槛上错误的正分数有多少。非零假设也可能产生负分数，把它们一并计入只会增加式(1)的分子。

难点在于门槛由数据挑选。固定门槛上的对称性，并不能直接证明“从许多门槛挑最有利的一个”仍安全。加一项与下面的倒序信息结构共同支付了这项选择成本：随着门槛升高，我们逐步排除小分数，而仍保留的零符号只通过负号总数进入判断。

原变量和替身的具体构造不在这条抽象规则中。固定设计Knockoff通过线性模型的Gram矩阵建立所需符号性质；Model-X Knockoff通过协变量联合律的逐对交换建立它。拿到一列自称“重要性”的数值，还必须证明它满足输入合同。

例子与边界

扫描不等于挑最大的几个数

取 $W=(6,5,4,3,-2,1)$ 、 $q=1/4$ 。候选 $1,2,3$ 的比例依次为 $2/5,2/4,1/4$ ，所以 $T=3$ ，选择前四项。候选4的比例反而为 $1/3$ ；满足条件的阈值集合不必是一个向上的连续尾部，不能用假定单调的二分查找替代扫描。

图中蓝色只标记当前入选或合格的位置，不表示它们已经被证实是真信号。右图在阈值三通过后又升高，体现逐候选扫描的必要性。

若前三项是非零假设，后三项是真零，当前输出的FDP为 $1/4$ 。保持绝对值 $(6,5,4,3,2,1)$ 和前三个正号，均匀枚举后三个符号：首个零符号为负的四种情况都不选；其余四种FDP为 $1/4,1/4,2/5,1/2$ 。因此条件FDR为

\frac18\left(\frac14+\frac14+\frac25+\frac12\right)=\frac7{40}<\frac14.

最后一种运行的FDP等于 $1/2$ ，与平均控制完全相容。

加一和联合公平性都有作用

若删去分子中的1，只取一个真零分数 $W_1=\pm1$ ，两符号等概率。任何 $q\in(0,1/2)$ 下，正号时比例为零、选择它，负号时不选，FDR恰为 $1/2>q$ 。因此不加一的规则不能原样声称式(2)；关于其他修正错误指标的结论须另行陈述。

再令三个真零分数总是共同取 $(1,1,1)$ 或 $(-1,-1,-1)$ ，各以概率 $1/2$ 。每个符号的边缘都是公平的，但 $q=1/3$ 时，前一种选全部、后一种不选，FDR仍为 $1/2$ 。条件相互独立是联合要求，三张对称的边缘直方图不能证明它。

若全部 $W_j=0$ ，候选集合为空，输出为空，FDR为零。若所有替身与原变量完全相同，合法构造也可能只能产生这种无功效的输出；控制错误不等于保证发现。

推论与应用

从符号对称到有限停时预算

先条件于全部绝对值和非零假设分数。令 $m$ 为非零真零分数个数，按绝对值从大到小列出这些坐标；并列时固定一个与符号无关的顺序。记 $B_i=1$ 表示第 $i$ 项是负号， $S_j=B_1+\cdots+B_j$ ， $S_0=0$ 。条件假设给出 $B_i$ 独立且各服从Bernoulli $(1/2)$ 。

定义倒序信息

\mathcal F_j=\sigma(S_j,B_{j+1},\ldots,B_m), \qquad M_j=\frac{j+1}{1+S_j},\qquad j=m,m-1,\ldots,0. \tag{3}

随着 $j$ 下降，信息增加：知道 $S_{j-1}$ 和 $B_j$ 便能恢复 $S_j$ 。给定 $\mathcal F_j$ 且 $S_j=s$ ，前 $j$ 个位置中负号的条件位置均匀，故被删去的 $B_j$ 为1的概率是 $s/j$ 。若 $s\ge1$ ，

E[M_{j-1}\mid\mathcal F_j] =\frac{s}{j}\frac{j}{s} +\frac{j-s}{j}\frac{j}{1+s} =\frac{j+1}{1+s}=M_j.

若 $s=0$ ，左端为 $j$ ，右端为 $j+1$ 。因此按时间 $r=m-j$ 重编号， $M_{m-r}$ 是非负超鞅。所有项都不超过 $m+1$ ，无需另加无限停时的可积性假设。

为什么所选阈值是合法停时

从最小候选阈值向上扫描时，仍保留的真零项始终是上述顺序的某个前缀。其负数为 $S_j$ ，正数为 $j-S_j$ ；非零假设的保留计数在当前条件化下已经固定。因此是否通过式(1)，仅用 $\mathcal F_j$ 中已经公开的信息。

某一绝对值组可能包含几个真零项。证明中可以逐个公开被删除的符号，但只在整组删除之前或之后、即算法实际候选的边界检查停止；中间步骤不作选择。非零假设单独形成的候选也只使用固定信息，不增加零符号观察。全部候选失败时继续删除至 $j=0$ 并输出为空。这样得到的停止时刻至多 $m$ 个零符号删除步骤，其最终前缀长度记为 $J$ 。

实际调用有界停时的超鞅预算，得到 $E[M_J]\le E[M_m]$ 。由 $S_m\sim\operatorname{Binomial}(m,1/2)$ ，使用二项质量及 $\binom ms/(s+1)=\binom{m+1}{s+1}/(m+1)$ ，有

E[M_m] =2^{-m}\sum_{s=0}^m\frac{m+1}{s+1}\binom ms =2^{-m}(2^{m+1}-1)=2-2^{-m}. \tag{4}

因此 $E[(J-S_J)/(1+S_J)]=E[M_J-1]\le1-2^{-m}\le1$ 。 $m=0$ 时左端直接为零，公式也一致。

把预算送回FDR

在有限合格阈值上，令 $R=|\widehat S|$ ，真零的正、负数分别为 $V^+=J-S_J$ 、 $V^-=S_J$ 。所有负数不少于真零负数，所以

\frac{V^+}{R} \le q\frac{V^+}{1+V^-}.

空输出时两边都取零。条件取期望并用式(4)，再对先前固定的绝对值和非零假设分数取期望，便证明式(2)。证明还说明，阈值选择不能偷看尚未公开的单个零符号，符号合同也不能仅在固定阈值上逐个成立。

完整的替身与重抽样证书终点把Gram构造、有限符号枚举和条件重抽样放到同一套可复算任务中。算法输出是一组条件关联发现，解释目标仍由生成这些分数的模型决定。

参考资料

Rina Foygel Barber and Emmanuel J. Candès, Controlling the false discovery rate via knockoffs, Annals of Statistics 43(5), 2015, pp. 2055–2085，Theorem2、§§2.3–2.4的符号交换及Knockoff+证明机制；DOI 10.1214/15-AOS1337。本页展开了有限倒序超鞅与并列处理。
Emmanuel Candès, Yingying Fan, Lucas Janson and Jinchi Lv, Panning for Gold: Model-X Knockoffs for High-dimensional Controlled Variable Selection, arXiv:1610.02351v4, 2017，§3.2–3.3：翻转符号统计量与FDR阈值。

形式陈述 ​

输入是带方向的竞争分数 ​

可执行的阈值扫描 ​

扫描不等于挑最大的几个数 ​

加一和联合公平性都有作用 ​

从符号对称到有限停时预算 ​

为什么所选阈值是合法停时 ​

把预算送回FDR ​

反向链接