上QQ阅读APP看书，第一时间看更新

第2章　模型评估与选择

式(2.20）

$\text{AUC}=\frac{1}{2}\sum_{i=1}^{m-1}(x_{i+1} - x_i)\cdot(y_i + y_{i+1})\vspace{-2mm}$

解析

在解释 $\text{AUC}$ 式之前，需要先弄清楚 $\text{ROC}$ 曲线的具体绘制过程.下面我们就举个例子，按照“西瓜书”图2.4下方给出的绘制方法来讲解一下 $\text{ROC}$ 曲线的具体绘制过程.

假设我们已经训练得到一个学习器 $f({\boldsymbol s})$ ，现在用该学习器来对8个测试样本（4个正例，4个反例，即 m^+=m^-=4 ）进行预测，预测结果为：

$\begin{array}{l}\left(s_{1}, 0.77,+\right),\left(s_{2}, 0.62,-\right),\left(s_{3}, 0.58,+\right),\left(s_{4}, 0.47,+\right) \\\left(s_{5}, 0.47,-\right),\left(s_{6}, 0.33,-\right),\left(s_{7}, 0.23,+\right),\left(s_{8}, 0.15,-\right)\end{array}$

此处用 ${\boldsymbol s}$ 表示样本，以和坐标 (x,y) 作出区分

其中，和分别表示样本为正例和为反例，数字表示学习器预测该样本为正例的概率，例如对于反例 ${\boldsymbol s}_2$ 来说，当前学习器 $f({\boldsymbol s})$ 预测它是正例的概率为 0.62 .

上面给出的预测结果已经按照预测值从大到小排序

根据“西瓜书”上给出的绘制方法，首先需要对所有测试样本按照学习器给出的预测结果进行排序，接着将分类阈值设为一个不可能取到的最大值.显然，此时所有样本预测为正例的概率都一定小于分类阈值，那么预测为正例的样本个数为0，相应的真正例率和假正例率也都为0，所以我们可以在坐标 (0,0) 处标记一个点. 接下来需要把分类阈值从大到小依次设为每个样本的预测值，也就是依次设为0.77, 0.62, 0.58, 0.47, 0.33, 0.23,0.15，然后分别计算真正例率和假正例率，再在相应的坐标上标记点，最后再将各个点用直线连接, 即可得到 $\text{ROC}$ 曲线.需要注意的是，在统计预测结果时，预测值等于分类阈值的样本也被算作预测为正例. 例如，当分类阈值为 0.77 时，测试样本 ${\boldsymbol s}_1$ 被预测为正例，由于它的真实标记也是正例，所以此时 ${\boldsymbol s}_1$ 是一个真正例.为了便于绘图，我们将轴（假正例率轴）的“步长”定为 $\frac{1}{m^-}$ ，轴（真正例率轴）的“步长”定为 $\frac{1}{m^+}$ .根据真正例率和假正例率的定义可知，每次变动分类阈值时，若新增个假正例，那么相应的轴坐标也就增加 $\frac{i}{m^-}$ ；若新增个真正例，那么相应的轴坐标也就增加 $\frac{j}{m^+}$ .按照以上讲述的绘制流程，最终我们可以绘制出如图2-1所示的 $\text{ROC}$ 曲线.

图像说明文字

图2-1　ROC曲线示意
注：表示红色线段；表示蓝色线段；表示绿色线段

在这里，为了能在解析式(2.21)时复用此图，我们没有写上具体的数值，转而用其数学符号代替.其中绿色线段表示在分类阈值变动的过程中只新增了真正例，红色线段表示只新增了假正例，蓝色线段表示既新增了真正例也新增了假正例.根据 $\text{AUC}$ 值的定义可知，此时的 $\text{AUC}$ 值其实就是所有红色线段和蓝色线段与轴围成的面积之和.观察图2-1可知，红色线段与轴围成的图形恒为矩形，蓝色线段与轴围成的图形恒为梯形.由于梯形面积式既能算梯形面积，也能算矩形面积，所以无论是红色线段还是蓝色线段，其与轴围成的面积都能用梯形公式来计算：

$\frac{1}{2}\cdot(x_{i+1} - x_i)\cdot(y_i + y_{i+1}).$

其中， $(x_{i+1} -x_i)$ 为“高”， y_i 为“上底”， $y_{i+1}$ 为“下底”.那么对所有红色线段和蓝色线段与轴围成的面积进行求和，则有

$\sum_{i=1}^{m-1}\left[\frac{1}{2}\cdot(x_{i+1} - x_i)\cdot(y_i + y_{i+1})\right],$

此即 $\text{AUC}$ .

式(2.21)

$\ell_{rank}=\frac{1}{m^+m^-}\sum_{\boldsymbol{x}^+ \in D^+}\sum_{\boldsymbol{x}^- \in D^-}\left(\mathbb{I}\left(f(\boldsymbol{x}^+)<f(\boldsymbol{x}^-)\right)+\frac{1}{2}\mathbb{I}\left(f(\boldsymbol{x}^+)=f(\boldsymbol{x}^-)\right)\right)$

解析

按照我们上述对式(2.20)的解析思路， $\ell_{rank}$ 可以看作是所有绿色线段和蓝色线段与轴围成的面积之和，但从式(2.21)中很难一眼看出其面积的具体计算方式，因此我们进行恒等变形如下：

$\ell_{\text {rank }}= \frac{1}{m^{+} m^{-}} \sum_{\boldsymbol{x}^{+} \in D^{+}} \sum_{\boldsymbol{x}^{-} \in D^{-}}\left(\mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)<f\left(\boldsymbol{x}^{-}\right)\right)+\frac{1}{2} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)=f\left(\boldsymbol{x}^{-}\right)\right)\right)$

$=\frac{1}{m^{+} m^{-}} \sum_{\boldsymbol{x}^{+} \in D^{+}}\left[\sum_{\boldsymbol{x}^{-} \in D^{-}} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)<f\left(\boldsymbol{x}^{-}\right)\right)+\frac{1}{2} \cdot \sum_{\boldsymbol{x}^{-} \in D^{-}} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)=f\left(\boldsymbol{x}^{-}\right)\right)\right]$

$=\sum_{\boldsymbol{x}^{+} \in D^{+}}\left[\frac{1}{m^{+}} \cdot \frac{1}{m^{-}} \sum_{\boldsymbol{x}^{-} \in D^{-}} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)<f\left(\boldsymbol{x}^{-}\right)\right)+\right.$

　　 $\left.\frac{1}{2} \cdot \frac{1}{m^{+}} \cdot \frac{1}{m^{-}} \sum_{\boldsymbol{x}^{-} \in D^{-}} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)=f\left(\boldsymbol{x}^{-}\right)\right)\right]$

$= \sum_{\boldsymbol{x}^{+} \in D^{+}} \frac{1}{2} \cdot \frac{1}{m^{+}} \cdot\left[\frac{2}{m^{-}} \sum_{\boldsymbol{x}^{-} \in D^{-}} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)<f\left(\boldsymbol{x}^{-}\right)\right)+\right.$

　　 $\left.\frac{1}{m^{-}} \sum_{\boldsymbol{x}^{-} \in D^{-}} \mathbb{I}\left(f\left(\boldsymbol{x}^{+}\right)=f\left(\boldsymbol{x}^{-}\right)\right)\right] .$

在变动分类阈值的过程当中，如果有新增真正例，那么图2-1就会相应地增加一条绿色线段或蓝色线段，所以上式中的 $\sum_{\boldsymbol{x}^+ \inD^+}$ 可以看作是在累加所有绿色和蓝色线段，相应地， $\sum_{\boldsymbol{x}^+\in%20D^+}$ 后面的内容便是在求绿色线段或者蓝色线段与轴围成的面积，即：

$\frac{1}{2}\cdot\frac{1}{m^+}\cdot\left[\frac{2}{m^-}\sum_{\boldsymbol{x}^- \in D^-}\mathbb{I}\left(f(\boldsymbol{x}^+)<f(\boldsymbol{x}^-)\right)+\frac{1}{m^-}\sum_{\boldsymbol{x}^- \in D^-}\mathbb{I}\left(f(\boldsymbol{x}^+)=f(\boldsymbol{x}^-)\right)\right].$

与式(2.20)中的求解思路相同，不论是绿色线段还是蓝色线段，其与轴围成的图形面积都可以用梯形公式来进行计算，所以上式表示的依旧是一个梯形的面积公式.其中 $\frac{1}{m^+}$ 即梯形的“高”，中括号内便是“上底+下底”，下面我们来分别推导一下“上底”（较短的底）和“下底”（较长的底）.

由于在绘制 $\text{ROC}$ 曲线的过程中，每新增一个假正例时坐标也就新增一个步长，所以对于“上底”，也就是绿色或者蓝色线段的下端点到轴的距离，长度就等于 $\frac{1}{m^-}$ 乘以预测值大于 $f({\boldsymbol x}^+)$ 的假正例的个数，即

$\frac{1}{m^-}\sum_{\boldsymbol{x}^- \in D^-}\mathbb{I}\left(f(\boldsymbol{x}^+)<f(\boldsymbol{x}^-)\right);$

而对于“下底”，长度就等于 $\frac{1}{m^-}$ 乘以预测值大于等于 $f(\boldsymbol{x}^+)$ 的假正例的个数，即

$\frac{1}{m^-}\left(\sum_{\boldsymbol{x}^- \in D^-}\mathbb{I}\left(f(\boldsymbol{x}^+)<f(\boldsymbol{x}^-)\right)+\sum_{\boldsymbol{x}^- \in D^-}\mathbb{I}\left(f(\boldsymbol{x}^+)=f(\boldsymbol{x}^-)\right)\right).$

式(2.27)

$\overline{\epsilon}=\max \epsilon\quad \text { {\rm s.t.} }\sum_{i= \epsilon_{0} \times m+1}}^{m}\binom{m}{i}\epsilon^{i}(1-\epsilon)^{m-i}<\alpha$

解析

截至2018年12月“西瓜书”第1版第30次印刷，式(2.27)应当勘误为

$\overline{\epsilon}=\min \epsilon\quad\text { {\rm s.t.} } \sum_{i=\epsilon\times m+1}^{m}\binom{m}{i} \epsilon_0^{i}(1-\epsilon_0)^{m-i}<\alpha.$

具体推导过程如下：由“西瓜书”中的上下文可知，对 $\epsilon\leq\epsilon_0$ 进行假设检验，等价于本章附注中所述的对 $p \leqslant p_{0}$ 进行假设检验，所以在“西瓜书”中求解最大错误率 $\overline{\epsilon}$ 等价于在附注中求解事件最大发生频率 $\frac{\overline{C}}{m}$ . 由附注可知

$\overline{C}=\min C\quad\text { {\rm s.t.} } \sum_{i=C+1}^{m}\binom{m}{i} p_0^{i}(1-p_0)^{m-i}<\alpha.$

所以

$\frac{\overline{C}}{m}=\min \frac{C}{m}\quad\text { {\rm s.t.} } \sum_{i=C+1}^{m}\binom{m}{i} p_0^{i}(1-p_0)^{m-i}<\alpha.$

将上式中的 $\frac{\overline{C}}{m},\frac{C}{m},p_0$ 等价替换为 $\overline{\epsilon},\epsilon,\epsilon_0$ 可得

$\overline{\epsilon}=\min \epsilon\quad\text { {\rm s.t.} } \sum_{i=\epsilon\times m+1}^{m}\binom{m}{i} \epsilon_0^{i}(1-\epsilon_0)^{m-i}<\alpha.$

式(2.41)

$E(f ; D)=\mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ; D)-y_{D}\right)^{2}\right]$ 　　①

$=\mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})+\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right]$ 　　②

$=\mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right]+$

$\mathbb{E}_{D}\left[2(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))\left(\bar{f}(\boldsymbol{x})-y_{D}\right)\right]$ 　　③

$=\mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right]$ 　　④

$=\mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y+y-y_{D}\right)^{2}\right]$ 　　⑤

$=\mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+\mathbb{E}_{D}\left[(\bar{f}(\boldsymbol{x})-y)^{2}\right]+\mathbb{E}_{D}\left[\left(y-y_{D}\right)^{2}\right]+$

$2 \mathbb{E}_{D}\left[(\bar{f}(\boldsymbol{x})-y)\left(y-y_{D}\right)\right]$ 　　⑥

$=\mathbb{E}_{D}\left[(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x}))^{2}\right]+(\bar{f}(\boldsymbol{x})-y)^{2}+\mathbb{E}_{D}\left[\left(y_{D}-y\right)^{2}\right]$ 　　⑦

① $\to$ ②：减一个 $\bar{f}(\boldsymbol{x})$ 再加一个 $\bar{f}(\boldsymbol{x})$ ，属于简单的恒等变形

④ $\to$ ⑤：同① $\to$ ②一样，减一个再加一个，属于简单的恒等变形

⑤ $\to$ ⑥：同② $\to$ ③一样，将最后一项利用期望的运算性质进行展开

解析

② $\to$ ③：首先将中括号内的式子展开，有

$\mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)^{2}+\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}+2\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)\left(\bar{f}(\boldsymbol{x})-y_{D}\right)\right],$

然后根据期望的运算性质 $\mathbb{E}[X+Y]=\mathbb{E}[X]+\mathbb{E}[Y]$ 可将上式化为

$\mathbb{E}_{D}\left[\left(f(\boldsymbol{x} ;D)-\bar{f}(\boldsymbol{x})\right)^{2}\right]+\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y_{D}\right)^{2}\right]+\\\mathbb{E}_{D}\left[2\left(f(\boldsymbol{x};D)-\bar{f}(\boldsymbol{x})\right)\left(\bar{f}(\boldsymbol{x})-y_{D}\right)\right].$

③ $\to$ ④：再次利用期望的运算性质将第3步得到的式子的最后一项展开，有

$\mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)\left(\bar{f}(\boldsymbol{x})-y_{D}\right)\right] \\= \mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ;D)-\bar{f}(\boldsymbol{x})\right)\cdot\bar{f}(\boldsymbol{x})\right]- \mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ;D)-\bar{f}(\boldsymbol{x})\right)\cdot y_{D}\right].$

首先计算展开后得到的第1项，有

$\mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)\cdot\bar{f}(\boldsymbol{x})\right] = \mathbb{E}_{D}\left[2f(\boldsymbol{x} ; D)\cdot\bar{f}(\boldsymbol{x})-2\bar{f}(\boldsymbol{x})\cdot\bar{f}(\boldsymbol{x})\right].$

由于 $\bar{f}(\boldsymbol{x})$ 是常量，所以由期望的运算性质： $\mathbb{E}[AX+B]=A\mathbb{E}[X]+B$ （其中 A, B 均为常量）可得

$\mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)\cdot\bar{f}(\boldsymbol{x})\right] = 2\bar{f}(\boldsymbol{x})\cdot\mathbb{E}_{D}\left[f(\boldsymbol{x} ; D)\right]-2\bar{f}(\boldsymbol{x})\cdot\bar{f}(\boldsymbol{x}).$

由式(2.37)可知 $\mathbb{E}_{D}\left[f(\boldsymbol{x} ;D)\right]=\bar{f}(\boldsymbol{x})$ ，所以

$\mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)\cdot\bar{f}(\boldsymbol{x})\right] = 2\bar{f}(\boldsymbol{x})\cdot\bar{f}(\boldsymbol{x})-2\bar{f}(\boldsymbol{x})\cdot\bar{f}(\boldsymbol{x})=0.$

接着计算展开后得到的第二项

$\mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)\cdot y_{D}\right]=2\mathbb{E}_{D}\left[f(\boldsymbol{x} ; D)\cdot y_{D}\right]-2\bar{f}(\boldsymbol{x})\cdot \mathbb{E}_{D}\left[y_{D}\right].$

由于噪声和无关，所以 $f(\boldsymbol{x} ;D)$ 和 y_D 是两个相互独立的随机变量. 根据期望的运算性质 $\mathbb{E}[XY]=\mathbb{E}[X]\mathbb{E}[Y]$ （其中和为相互独立的随机变量）可得

　 $=2\mathbb{E}_{D}\left[f(\boldsymbol{x} ; D)\right]\cdot \mathbb{E}_{D}\left[y_{D}\right]-2\bar{f}(\boldsymbol{x})\cdot \mathbb{E}_{D}\left[y_{D}\right] \\$

　 $=2\bar{f}(\boldsymbol{x})\cdot \mathbb{E}_{D}\left[y_{D}\right]-2\bar{f}(\boldsymbol{x})\cdot \mathbb{E}_{D}\left[y_{D}\right]$

　 = 0,

所以

　 $\mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)\left(\bar{f}(\boldsymbol{x})-y_{D}\right)\right]$

$= \mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)\cdot\bar{f}(\boldsymbol{x})\right] - \mathbb{E}_{D}\left[2\left(f(\boldsymbol{x} ; D)-\bar{f}(\boldsymbol{x})\right)\cdot y_{D}\right]$

= 0+0

=0.

⑥ $\to$ ⑦：因为 $\bar{f}(\boldsymbol{x})$ 和均为常量，根据期望的运算性质，有⑥中的第2项

$\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y\right)^{2}\right]=\left(\bar{f}(\boldsymbol{x})-y\right)^{2}.$

同理有⑥中的最后一项

$2\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y\right)\left(y-y_{D}\right)\right]=2\left(\bar{f}(\boldsymbol{x})-y\right)\mathbb{E}_{D}\left[y-y_{D}\right].$

由于此时假定噪声的期望为零，即 $\mathbb{E}_{D}\left[y-y_{D}\right]=0$ ，所以

$2\mathbb{E}_{D}\left[\left(\bar{f}(\boldsymbol{x})-y\right)\left(y-y_{D}\right)\right]=2\left(\bar{f}(\boldsymbol{x})-y\right)\cdot 0=0.$

本周热推：

Office 2010轻松入门 AVR单片机菜鸟进阶企业级Web开发实战 51单片机应用程序开发与实践 JSF2和RichFaces4使用指南

第2章 模型评估与选择

第2章　模型评估与选择