固定设计 Knockoff 构造

形式陈述

固定的几何，随机的响应

本页采用固定设计的线性回归模型

Y=X\beta+\varepsilon,\qquad \varepsilon\sim N_n(0,\sigma^2I_n),\qquad \sigma>0. \tag{1}

$X\in\mathbb R^{n\times p}$ 已知、满列秩， $p\ge1$ 且 $n\ge2p$ ； $\beta$ 与 $\sigma$ 未知。真实零集合是 $H_0=\{j:\beta_j=0\}$ 。概率只来自响应以及算法预先引入的独立随机性。本页的直接构造不处理 $n<2p$ ，这不是声称该范围绝无其他构造。

记 $\Sigma=X^TX$ 。它是正定矩阵，这里没有除以 $n$ 。构造只使用X和独立于Y的预先随机数，不用响应来挑D、U或C。选对角矩阵 $D=\operatorname{diag}(s_1,\ldots,s_p)$ ，满足 $D\succeq0$ 、 $2\Sigma-D\succeq0$ 。替身矩阵 $\widetilde X\in\mathbb R^{n\times p}$ 的目标是

\widetilde X^T\widetilde X=\Sigma, \qquad X^T\widetilde X=\Sigma-D. \tag{2}

因此不同编号的原列与替身列保持同样内积，只有第 $j$ 列和自己的替身之间，内积减少 $s_j$ 。

取 $U\in\mathbb R^{n\times p}$ 满足 $U^TU=I_p$ 、 $U^TX=0$ ，再取 $C\in\mathbb R^{p\times p}$ 满足

C^TC=2D-D\Sigma^{-1}D.

构造为

\widetilde X=X(I_p-\Sigma^{-1}D)+UC. \tag{3}

后文证明这样的 $U,C$ 存在，并验证式(2)。当 $C$ 秩亏时仍允许生成，不要求它可逆。

分数必须怎样对待两套列

记增广矩阵 $A=[X\ \widetilde X]$ 。统计量 $W\in\mathbb R^p$ 要同时满足两项条件：

充分性接口：存在同一个可测函数 $f$ ，使 $W=f(A^TA,A^TY)$ 。这里是对统计量允许使用的信息作限制；不必先把它称为整个模型的最小充分统计量。
交换反对称性：把任意第 $j$ 原列与第 $j$ 替身列交换后， $W_j$ 变号，其余坐标不变；多个互不相同的交换同时执行时，恰好翻转对应的符号。

一个容易核验的选择是

W_j=|X_j^TY|-|\widetilde X_j^TY|. \tag{4}

更复杂的增广模型拟合也可以产生分数，但解的选择、调参和并列处理都须保留这两项性质。仅仅“把两套列都输入了学习器”并不能证明反对称性。

在式(1)与这些条件下，给定全部 $|W_j|$ 和 $j\notin H_0$ 的 $W_j$ ，非零真零分数的符号独立公平。因而将 $W$ 送入Knockoff+筛选，就有有限样本FDR不超过预定 $q$ 。

直觉

替身不能是与所有原列都无关的噪声列。一个无效变量仍可能因为与真正有效的变量相关，而与响应有明显关联；它的替身需要保留这种“通过其他列获得的关联”。式(2)让每对竞争者面对其他变量时处于相同几何位置。

构造中的第一项位于原设计的列空间，负责与原列保持指定内积。第二项 $UC$ 位于其正交补，不改变这些交叉内积，却补足替身自己的长度和相互内积。 $n\ge2p$ 保证正交补至少有 $p$ 个方向可用。

本页并未把设计矩阵本身随机化成一对可交换样本。交换后的增广矩阵通常就是另一张不同的固定矩阵；真正不变的是充分统计向量在正态响应模型下的分布。这正是充分性接口的作用。

例子与边界

两列相关设计的全有理构造

取

X=\begin{pmatrix}1&3/5\\0&4/5\\0&0\\0&0\end{pmatrix}, \quad \Sigma=\begin{pmatrix}1&3/5\\3/5&1\end{pmatrix}, \quad D=\frac{16}{25}I_2.

$\Sigma$ 的特征值为 $2/5,8/5$ ，所以 $2\Sigma-D$ 的最小特征值为 $4/25>0$ 。直接计算得到

I-\Sigma^{-1}D=\begin{pmatrix}0&3/5\\3/5&0\end{pmatrix}, \qquad C=\begin{pmatrix}4/5&12/25\\0&16/25\end{pmatrix}.

取 $U=[e_3\ e_4]$ ，则

\widetilde X= \begin{pmatrix} 9/25&3/5\\ 12/25&0\\ 4/5&12/25\\ 0&16/25 \end{pmatrix}. \tag{5}

两列替身的长度平方都是1，内积为 $3/5$ ；原列与自己的替身内积为 $9/25$ ，与另一替身内积为 $3/5$ 。这四种数值分别检查了式(2)的对角与非对角责任。

若响应为 $y=(7,9/4,-13/4,-41/16)^T$ ，则 $X^Ty=(7,6)^T$ 、 $\widetilde X^Ty=(1,1)^T$ ，式(4)给 $W=(6,5)$ 。两个正分数不意味着低FDR阈值下一定能选：例如 $q=1/4$ 至少需要四项入选，加一规则在这里只能返回空集。终点把三块这样的设计组合起来，才完成有发现的选择与全符号风险枚举。

一个边界不应被另一个条件替代

$D=0$ 总合法，但式(3)退化为 $\widetilde X=X$ ，任何满足反对称性的确定分数都为零。这是正确却无识别能力的替身。选择较大的 $s_j$ 有助于区分竞争者，但必须一起满足矩阵半正定约束，不能逐坐标随意增大。

在单位正交设计 $\Sigma=I_p$ 下， $D=I_p$ 可让替身与原设计正交；相关设计一般做不到同时保留式(2)并令交叉Gram为零。随机打乱行或独立生成噪声，即使保持各列方差，也未必保留所有非对角内积。

如果误差只同方差不相关而非联合正态，下面由均值和协方差识别分布的步骤没有依据。如果误差协方差为一般 $\Omega$ ，充分统计量的协方差变成 $A^T\Omega A$ ，式(2)也不再自动使它交换不变。模型改变后须重证分布，不宜只换标准误。

数值计算中“两个Gram很接近”同样不等于式(2)精确成立。浮点残差是诊断，有限误差下的FDR偏离需要额外稳健性定理；本页不给未证明的误差容限。

推论与应用

存在性与两个Gram等式

块矩阵

G=\begin{pmatrix}\Sigma&\Sigma-D\\\Sigma-D&\Sigma\end{pmatrix}

在和、差正交坐标 $(u+v)/\sqrt2,(u-v)/\sqrt2$ 下变成 $\operatorname{diag}(2\Sigma-D,D)$ ，因此 $G\succeq0$ 恰好对应所列两个半正定条件。进一步令 $H=\Sigma^{-1/2}D\Sigma^{-1/2}$ ，则 $0\preceq H\preceq2I$ ，从而

2D-D\Sigma^{-1}D =\Sigma^{1/2}(2H-H^2)\Sigma^{1/2}\succeq0.

正定/半正定矩阵的平方根构造遂给出 $C^TC$ 分解，零特征值也可保留。另一方面， $\dim\operatorname{col}(X)^\perp=n-p\ge p$ ，所以可选 $p$ 个正交单位向量组成 $U$ 。

式(3)的交叉项立即给 $X^T\widetilde X=\Sigma-D$ 。由于 $X^TU=0$ ，替身的Gram为

\begin{aligned} \widetilde X^T\widetilde X &=(I-D\Sigma^{-1})\Sigma(I-\Sigma^{-1}D)+C^TC\\ &=\Sigma-2D+D\Sigma^{-1}D+2D-D\Sigma^{-1}D=\Sigma. \end{aligned}

这证明构造确实完成两个目标，而不只是通过了正定性检查。

为什么只在真实零坐标上分布不变

令 $P_S$ 为交换原/替身第 $j$ 对、 $j\in S$ 的置换矩阵。 $D$ 为对角阵意味着不同编号之间的四种交叉内积相同，所以

P_S^TGP_S=G

对任意 $S$ 成立。对于 $A^TY$ ，调用联合正态的线性变换可得

A^TY\sim N_{2p}\!\left( \binom{\Sigma\beta}{(\Sigma-D)\beta},\ \sigma^2G\right). \tag{6}

交换第 $j$ 对时，均值中两项的差是 $s_j\beta_j$ 。若 $S\subseteq H_0$ ，这些差都为零，所以均值和协方差均保持不变。联合正态律由这两项确定，即使 $G$ 奇异也成立，故 $P_S^TA^TY\overset d=A^TY$ 。

充分性把式(6)的不变性传给统计量，反对称性把同一交换解释为指定坐标变号。因此 $W$ 的分布在任意真零符号翻转下不变。条件于全部绝对值和非零假设分数后，该条件分布仍不变；在非零真零坐标的 $2^m$ 种符号向量之间，翻转群作用传递，所以每种概率都为 $2^{-m}$ 。这恰是联合条件公平性，而不是仅有各边缘正负概率相同。

最后调用Knockoff+定理，将这个符号合同变成FDR保证。设计几何负责产生合法分数；阈值定理负责数据依赖选择，两步责任各自清楚。

计算接口与模型选择

实现式(3)时可用QR的正交补产生 $U$ ：保存 $X$ 的Householder反射，把完整正交矩阵中第 $p+1$ 至 $2p$ 列应用出来即可，不必显式保存 $n\times n$ 矩阵。形成Gram、解 $\Sigma B=D$ 、计算 $p\times p$ 半正定因子并组装替身，稠密算术成本为 $O(np^2+p^3)$ ，存储为 $O(np+p^2)$ 。这里把 $D$ 作为已经给定且经验证的输入；额外优化 $D$ 的成本另计。

求逆符号 $\Sigma^{-1}D$ 在程序中应通过线性方程求解实现。接近秩亏的设计会同时影响Gram和因子的可靠性；满秩这一数学输入不能由一个任意浮点容差自动认证。

Lasso支持恢复要求把整个支持恢复正确，通常消费额外的信号强度及设计条件；本页允许漏选与部分错选，控制的是所选集合的平均错误比例。去偏Lasso提供另一类渐近坐标推断。应按需要的结论选择接口，而不是看到稀疏回归就交换它们的保证。

参考资料

Rina Foygel Barber and Emmanuel J. Candès, Controlling the false discovery rate via knockoffs, Annals of Statistics 43(5), 2015, pp. 2055–2085，§2.1.1的直接构造，Definitions3–4及Lemmas1–3的充分性、反对称性与交换证明；DOI 10.1214/15-AOS1337。

形式陈述 ​

固定的几何，随机的响应 ​

分数必须怎样对待两套列 ​

两列相关设计的全有理构造 ​

一个边界不应被另一个条件替代 ​

存在性与两个Gram等式 ​

为什么只在真实零坐标上分布不变 ​

计算接口与模型选择 ​

反向链接