NO.11.tip： 假设检验

背景

  假设 $X$ 是随机变量，在 $\{1,\cdots ,n\}$ 中取值，其概率密度分布和参数 $\theta \in \{1,\cdots ,m\}$ 的取值有关。对 $\theta$ 的 $m$ 个可能值，$X$ 的概率分布可以由矩阵 $P\in {\mathbf{R}}^{n\times m}$ 表征，其元素为

$$p_{kj}=\mathrm{prob}(X=k\mid \theta =j).\text{\hspace{1em}(1)}$$

矩阵 $P$ 的第 $j$ 列为对应参数值 $\theta =j$ 的概率分布。

  考虑基于 $X$ 的观测样本估计 $\theta$ 的问题。换言之，样本 $X$ 来自于 $m$ 种可能的概率分布，我们需要确定是哪个。$\theta$ 的 $m$ 个取值称为假设，我们从这些假设中猜想哪个是正确的（即产生观测样本 $X$ 的概率分布），这个问题称为假设检验。在很多情况下，某种假设对应一种常规情形，而其他假设均对应反常的事件。此时，假设检验可以看成观测到 $X$ 的某个取值，然后判断不寻常事件是否发生，如果发生了，是哪一个不寻常事件。因此，假设检验又称为检测。

  在很多情况下，假设的顺序对结果没有什么影响；对 $m$ 个不同的假设，将其任意标识为 $\theta =1,\cdots ,m$。如果 $\hat{\theta }=\theta$，其中 $\hat{\theta }$ 表示 $\theta$ 的估计值，那么我们成功地猜想出了参数值 $\theta$。如果 $\hat{\theta }\ne \theta$，我们关于参数值 $\theta$ 的猜想不正确；我们误认为 $\theta$ 是 $\hat{\theta }$。在其他情况下，假设的顺序非常重要。在这种情况下，事件 $\hat{\theta }>\theta$，即我们关于 $\theta$ 的估计值偏大，对结果是有意义的。

  给定 $X$ 的观测值，$\theta$ 的估计值是随机的。$\theta$ 的一个随机检测器是随机变量 $\hat{\theta }\in \{1,\cdots ,m\}$，其分布取决于 $X$ 的观测值。随机检测器可以定义为一个矩阵 $T\in {\mathbf{R}}^{m\times n}$，其元素为

$$t_{ik}=\mathrm{prob}(\hat{\theta }=i\mid X=k).\text{\hspace{1em}(3)}$$

可以这么理解上述定义：如果我们得到观测值 $X=k$，那么检测器以概率 $t_{ik}$ 给出估计值 $\hat{\theta }=i$。（给定观测值 $X=k$，$T$ 的第 $k$ 列，我们用 $t_k$ 表示，给出了 $\hat{\theta }$ 的概率分布。如果 $T$ 的每一列都是单位向量，那么随机检测器是确定性检测器，即 $\hat{\theta }$ 是 $X$ 的观测值的一个（确定性）函数。）

  初步看来，在估计或检测过程中引入随机因素似乎只会让估计效果更差。但是在后文我们给出例子，在例子中随机检测器比所有的确定性估计器效果都好。

  我们致力于寻找定义随机检测器的矩阵 $T$。显然，$T$ 的列 $t_k$ 必须满足（线性等式和不等式）约束

$$t_k⪰0,1^T{t}_k=1.\text{\hspace{1em}(4)}$$

  对于由矩阵 $T$ 决定的随机检测器，定义检测概率矩阵为 $D=TP$。我们有

$$D_{ij}=(TP{)}_{ij}=\mathrm{prob}(\hat{\theta }=i\mid \theta =j),\text{\hspace{1em}(5)}$$

因此，$D_{ij}$ 是当 $\theta =j$ 时，猜想为 $\hat{\theta }=i$ 的概率。$m\times m$ 检测概率矩阵 $D$ 衡量了由矩阵 $T$ 定义的随机检测器的性能。（对角元素 $D_{ii}$ 是当 $\theta =i$ 时，猜想为 $\hat{\theta }=i$ 的概率，即正确地检测出 $\theta =i$ 的概率。非对角线元素 $D_{ij}(i\ne j)$ 是 $\theta =j$ 时误判为 $\theta =i$ 的概率，即事实上 $\theta =j$，而我们的猜想为 $\hat{\theta }=i$ 的概率。如果 $D=I$，检测器是理想的：无论参数 $\theta$ 的值如何，我们的猜想都是正确的，$\hat{\theta }=\theta$。）

  $D$ 的对角线元素，排列成一个向量，称为检测概率，用 $P^{\mathrm{d}}$ 表示，即

$$P_i^{\mathrm{d}}=D_{ii}=\mathrm{prob}(\hat{\theta }=i\mid \theta =i).\text{\hspace{1em}(6)}$$

错误概率是上面概率的补，用 $P^{\mathrm{e}}$ 表示，即

$$P_i^{\mathrm{e}}=1-D_{ii}=\mathrm{prob}(\hat{\theta }\ne i\mid \theta =i).\text{\hspace{1em}(7)}$$

因为检测概率矩阵 $D$ 的每列和为 $1$，错误概率可以表示为

$$P_i^{\mathrm{e}}=\sum _{j\ne i}{D}_{ji}.\text{\hspace{1em}(8)}$$

源与流

  检测器设计问题中有很大一部分目标函数是 $D$，也是 $T$（即优化变量）的线性、仿射或者凸分片线性函数。类似地，检测器设计问题中很多约束都可以表示成 $D$ 的线性不等式。因此，很多最优检测器设计问题都可以表述成线性规划。

  最优检测器设计问题可以看成一个多准则优化问题，约束为式 (4)，$m(m-1)$ 个目标由矩阵 $D$ 的非对角线元素给出，这些元素表征了不同类型的检测错误的概率：

$$\begin{array}{ll}\text{minimize}(\text{关于}{\mathbf{R}}_{+}^{m(m-1)})& D_{ij},i,j=1,\cdots ,m,i\ne j\\ \text{subject to}& t_k⪰0,1^T{t}_k=1,k=1,\cdots ,n,\end{array}\text{\hspace{1em}(14)}$$

其中优化变量 $t_1,\cdots ,t_n\in {\mathbf{R}}^m$。因为每个目标 $D_{ij}$ 都是优化变量的线性函数，这是一个多准则线性规划问题。

  为了将这个多准则优化问题标量化，引入权系数将目标函数加权求和，

$$\sum _{i,j=1}^m{W}_{ij}{D}_{ij}=\mathrm{tr}(W^{T}D),\text{\hspace{1em}(15)}$$

其中权矩阵 $W\in {\mathbf{R}}^{m\times m}$ 满足

$$W_{ii}=0,i=1,\cdots ,m,W_{ij}>0,i,j=1,\cdots ,m,i\ne j.\text{\hspace{1em}(16)}$$

此时目标函数是 $m(m-1)$ 个误差概率的加权和。权系数 $W_{ij}$ 对应着下述事件，事实上 $\theta =j$ 但猜想为 $\hat{\theta }=i$。加权矩阵有时亦称为损失矩阵。

为了找到多准则优化问题 (14) 的一个 Pareto 最优点，我们求解标量优化问题

$$\begin{array}{ll}\text{minimize}& \mathrm{tr}(W^{T}D)\\ \text{subject to}& t_k⪰0,1^T{t}_k=1,k=1,\cdots ,n,\end{array}\text{\hspace{1em}(17)}$$

它是一个线性规划。这个线性规划对变量 $t_1,\cdots ,t_n$ 是可分的。目标函数可以描述为一系列 $t_k$ 的（线性）函数的和

$$\mathrm{tr}(W^{T}D)=\mathrm{tr}(W^{T}TP)=\mathrm{tr}(P{W}^{T}T)=\sum _{k=1}^n{c}_k^T{t}_k,\text{\hspace{1em}(18)}$$

其中 $c_k$ 是 $W{P}^T$ 的第 $k$ 列。约束是可分的（即我们可以得到关于每个 $t_i$ 的可分的约束）。因此我们可以通过分别求解下面的线性规划来求解线性规划 (17)

$$\begin{array}{ll}\text{minimize}& c_k^T{t}_k\\ \text{subject to}& t_k⪰0,1^T{t}_k=1,\end{array}\text{\hspace{1em}(19)}$$

每个线性规划都有一个简单的解析解。我们可以找到一个指标 $q$ 使得 $c_{kq}={\min }_j{c}_{kj}$。令 $t_k^{\star }=e_q$。这个最优点对应一个确定性检测器：即当已知观测值 $X=k$ 时，我们的估计值为

$$\hat{\theta }={\mathrm{argmin}}_j(W{P}^T{)}_{jk}.\text{\hspace{1em}(20)}$$

因此，对每一个非对角线元素大于零的权矩阵 $W$ 我们可以找到一个确定性检测器，使得加权求和之后的目标函数最小。这似乎意味着随机检测器并没有意义，在后文中我们将看到事实并不是这样的。多目标优化问题 (14) 的 Pareto 最优权衡表面是分片线性的；式 (20) 描述的确定性检测器对应了 Pareto 最优权衡表面的顶点。

  作为一个例子，我们考虑 $m=2$ 的特殊情形，也称为二值假设检验。随机变量 $X$ 可能服从两种随机分布中的一种，为了简单起见，这两种随机分布用 $p\in {\mathbf{R}}^n$ 和 $q\in {\mathbf{R}}^n$ 表示。大部分情况下，假设 $\theta =1$ 对应一些常规的情形，$\theta =2$ 对应一些异常事件，而我们要检测出来这些异常事件。如果 $\hat{\theta }=1$，我们称检验是阴性的（即我们认为异常事件并没有发生）；如果 $\hat{\theta }=2$，我们称检验是阳性的（即我们认为异常事件发生了）。

  通常可以将检测概率矩阵 $D\in {\mathbf{R}}^{2\times 2}$ 表示为

$$D=\left[\begin{array}{cc}1-P_{\mathrm{fp}}& P_{\mathrm{fn}}\\ P_{\mathrm{fp}}& 1-P_{\mathrm{fn}}\end{array}\right].\text{\hspace{1em}(26)}$$

这里 $P_{\mathrm{fn}}$ 是假阴性的概率（即检验是阴性的但事实上异常事件发生了），$P_{\mathrm{fp}}$ 是假阳性的概率（即检验是阳性的但事实上异常事件并没有发生），亦被称为误报概率。最优检测器设计问题是一个双准则优化问题，目标函数为 $P_{\mathrm{fn}}$ 和 $P_{\mathrm{fp}}$。

  $P_{\mathrm{fn}}$ 和 $P_{\mathrm{fp}}$ 的最优权衡曲线称为接收器工作特性（ROC），由 $p$ 和 $q$ 服从的概率分布决定。可以用 §7.3.4 中的方法，标量化双准则问题并进行求解得到 ROC。给定权矩阵 $W$，最优检测器 (20) 为

$$\hat{\theta }=\{\begin{array}{ll}1& W_{21}{p}_k>W_{12}{q}_k\\ 2& W_{21}{p}_k⩽W_{12}{q}_k\end{array}\text{\hspace{1em}(27)}$$

其中观测值为 $X=k$。称这种检测器为似然比阈值检验：如果比值 $p_k/q_k$ 大于阈值 $W_{12}/W_{21}$，检验是阴性的（即 $\hat{\theta }=1$）；否则，检验是阳性的。通过选择不同的阈值，我们可以得到不同的（确定性）Pareto 最优检测器，这些检测器分别对应了不同水平的假阳性和假阴性错误概率。上述结论称为 Neyman-Pearson 引理。

  似然比检测器并没有给出所有的 Pareto 最优检测器，它们仅是最优权衡曲线的顶点，而曲线是分片线性的。