.　　上篇讲解了 P-R、ROC、DET 三种曲线，本篇来讲解 AP、AUC 两种指标。指标的作用，就是用一个数字衡量二分类器的好坏，便于对不同的二分类器进行比较。本篇会讲解 AP、AUC 两种指标的定义，它们与各种曲线的关系，以及如何准确、高效、简洁地编程计算两种指标。

五、Average Precision（AP）指标

　　AP 指标的定义是这样的：把阈值设置在紧靠每个正例之下，计算正类的查准率 P_+ ，再取平均值。沿用上篇开头的例子：

把阈值设置在紧靠第 1、2、3、4 个正例之后，正类的查准率分别是 1、1、0.6、0.5，所以 AP 指标等于 (1 + 1 + 0.6 + 0.5) / 4 = 0.775 。

　　如果有多个正例的得分相同，那么阈值设置在紧靠它们之下时的查准率，在取平均时也会被计算多次。比如，如果图 5.1 中得分为 0.6 的两个样例都是正例，那么 AP 就会变成 (1 + 1 + 4/5 + 4/5 + 5/8) / 5 = 0.845 。

　　有些任务可以分解成多个二分类子任务。比如我的博士课题「声音事件检测」，每条录音里可能有多种声音事件，所以可以看成是对每一种事件进行二分类。要用一个数字来衡量这种系统的性能，可以对每一种事件计算 AP，然后再取平均值，结果称为 mean average precision（MAP）。这里的 mean 和 average 的对象不同：average 是对阈值设在各个位置时的查准率求平均，而 mean 是对各个子任务求平均。

　　AP 指标跟 P-R 曲线有着微妙的关系。对于图 5.1 中的例子，我们标出阈值设置在紧靠每个正例之后时，P-R 曲线上对应的点。可以发现，AP 指标等于图中浅蓝色部分的面积。这个面积跟 P-R 曲线下的面积非常接近，只是差了几个小三角形。当数据量大了的时候，这些小三角形的面积就可以忽略不计了，所以可以说，AP 约等于 P-R 曲线下的面积。

　　AP 还可以不严格地写成积分的形式： $AP = \int_0^1 P_+ \,\text{d} R_+$ 。这个积分式能够体现 AP 的定义：阈值下移时，每越过一个正例，就让正类的查全率增加一点儿（ $\text{d}R_+$ ）；这些时候的正类查准率 P_+ 的平均值就是 AP。当然，也可以反过来把积分式写成 $AP = \int_0^1 R_+ \,\text{d} P_+$ ，不过这就更不严格了，因为 P-R 曲线并不一定是单调递减的，同一个 P_+ 可能对应着多个 R_+ 。另外，P-R 曲线的最右端 P_+ 并没有下降至 0，而是只下降到正例所占比例 $\%_+$ 。在积分式中， P_+ 小于 $\%_+$ 时， R_+ 取 1。

　　如果用 AP 作为二分类器的评价指标，那么在训练时，我们自然也希望能够直接优化 AP，就像优化交叉熵目标函数那样。不幸的是，这一点比较难做到。这是因为，交叉熵可以写成某个函数对所有样例求平均的形式：

$CE = \frac{\sum_{x \in D_+} [ -\log(\text{score}(x))] + \sum_{x \in D_-} [ -\log(1 - \text{score}(x))]}{n_+ + n_-} \\$

（式中 D_+, D_- 分别表示所有正例、负例的集合； $\text{score}(x)$ 表示样例的得分，它必须处于 0 到 1 之间），但 AP 不能分解成某个函数对所有样例求平均的形式，这称为「不可分解」（non-decomposable）。有一些优化 AP 的算法，会用一个可分解的界来代替 AP 作为目标函数，在推导这些界时，有的（如^[1]）就利用了上面的积分形式。

　　上篇 3.1 节讲过，如果一个二分类器给所有样例随机打分，P-R 曲线会大约是一条水平的直线，其纵坐标等于正例所占比例 $\%_+$ 。这条直线下方的面积，就也等于正例所占比例，这可以作为 AP 指标的 baseline。

六、Area Under the Curve（AUC）指标

　　AUC 指标的定义很好理解，它就是 ROC 曲线下的面积。在图 6.1 的例子中，AUC 就是浅蓝色部分的面积，它等于 0.725。

　　AUC 指标也可以写成积分形式。原始 ROC 曲线（图 6.1 左）的横轴是负类的误查率 1-R_- ，这里的「1 减」会给列积分式造成一些麻烦。不如先把 ROC 曲线顺时针旋转 90 度（图 6.1 右）再写积分式，容易得到：

$AUC = \int_0^1 R_- \,\text{d} R_+ = \int_0^1 R_+ \,\text{d} R_- \\$

　　根据积分式 $AUC = \int_0^1 R_- \,\text{d} R_+$ ，我们可以反过来给 AUC 下一个类似于 AP 的定义：把阈值设置在紧靠每个正例之下，计算负类的查全率 R_- ，再取平均值。

　　AUC 与 AP 一样，无法分解成某个函数对所有样例求平均的形式，所以在训练二分类器时，要直接优化 AUC，同样比较困难。不过，AUC 可以分解成某个函数对所有「正负样例对」求平均的形式，这也可以作为探求优化方法的线索。这种形式可以利用上面的定义推导出来。先忽略存在不同样例得分相同的情况。把阈值设置在紧靠某个正例之下时，求负类的查全率，就相当于问有多大比例的负例得分小于 $\text{score}(x)$ 。由此可以得到：

$AUC = \frac{1}{n_+} \sum_{x \in D_+} \left\{ \frac{1}{n_-} \sum_{y \in D_-} u[\text{score}(x) - \text{score}(y)] \right\} \qquad (1)\\$

其中 u(x) 为阶跃函数

$u(x) = \left\{ \begin{align} 1, & \quad x > 0 \\ 0, & \quad x < 0 \\ \end{align} \right. \\$

把 (1) 式稍微变形一下，就是：

$AUC = \frac{\sum_{x \in D_+} \sum_{y \in D_-} u[\text{score}(x) - \text{score}(y)]}{n_+ n_-} \qquad (2) \\$

这就把 AUC 分解成了某个函数（阶跃函数）对所有「正负样例对」求平均的形式。它可以通俗地理解成：在所有的正负样例对中，有多大的比例，其中正例得分比负例高；或者说：随机取一个正例和一个负例，正例得分比负例高的概率有多大。这很好地体现了 AUC 指标的初衷：衡量有序列表的质量。这种通俗含义在图 6.1 中也可以直观地观察出来：每一个正例得分比负例高的样例对，对应了一个浅蓝色的小方格。如果令 u(0) = 1/2 ，则上述表达式也适用于存在不同样例得分相同的情况。

　　上篇 3.1 节讲过，如果一个二分类器给所有样例随机打分，ROC 曲线会是一条对角线 R_+ + R_- = 1 ，它下方的面积等于 0.5。0.5 可以作为 AUC 指标的 baseline，它与正例所占比例无关。另外上篇还讲过，旋转后的 ROC 曲线一般比 P-R 曲线高，所以 AUC 指标一般会大于 AP 指标。

6.1 d-prime 指标

　　事实上，在性能比较好的二分类器中，ROC 曲线往往很接近角落，AUC 指标也会很接近 1，难以显示出不同系统之间的差距。出于跟 DET 曲线一样的动机，实际中也常常用标准正态分布累积密度函数 $\Phi$ 的反函数 $\Phi^{-1}$ 对 AUC 进行非线性伸缩，得出的指标称为（读作 d-prime）：

$d' = \sqrt{2} \, \Phi^{-1} (AUC) \\$

　　咦？为什么要乘以 $\sqrt{2}$ 呢？原来，这个是有直观含义的：

　　考察正、负类得分服从等方差高斯分布的情况：设正类得分服从 $\mathcal{N}(\mu_+, \sigma^2)$ ，负类得分服从 $\mathcal{N}(\mu_-, \sigma^2)$ 。考虑 (2) 式的通俗含义：在所有正负样例对中，有多大的比例，其中正例的得分比负例高。这就是说：
$AUC = \text{E}_{x \sim \mathcal{N}(\mu_+, \sigma^2)} \text{E}_{y \sim \mathcal{N}(\mu_-, \sigma^2)} u(x - y) \\$
上面的二重期望可以写成二重积分，这是的联合分布在区域内的总密度：
$AUC = \iint_{x > y} \frac{1}{\sqrt{2\pi} \sigma} \, \exp \left[ -\frac{1}{2} \left( \frac{x - \mu_+}{\sigma} \right)^2 \right] \cdot \frac{1}{\sqrt{2\pi} \sigma} \,\exp \left[ -\frac{1}{2} \left( \frac{y - \mu_-}{\sigma} \right)^2 \right] \,\text{d}x \,\text{d}y \\$
令 $x' = \frac{x - \mu_+}{\sigma}, y' = \frac{y - \mu_-}{\sigma}$ ，则上式变为：
$AUC = \iint_{y' - x' < \frac{\mu_+ - \mu_-}{\sigma}} \frac{1}{2\pi} \, \exp \left( -\frac{x'^2 + y'^2}{2} \right) \,\text{d}x' \,\text{d}y' \\$
这是一个二维标准高斯分布在半平面 $y' - x' < \frac{\mu_+ - \mu_-}{\sigma}$ 内的总密度。计算这个二重积分的技巧，是做如下的换元，把半平面的边界旋转至与坐标轴平行：
$\left\{ \begin{align} x' &= (z-w) / \sqrt{2} \\ y' &= (z+w) / \sqrt{2} \\ \end{align} \right. \\$
之所以除以 $\sqrt{2}$ ，是为了让，并且这个变换的雅各比行列式恰等于 1，所以 $\text{d}x' \,\text{d}y' = \text{d}z \,\text{d}w$ 。于是
$\begin{align} AUC &= \iint_{z < \frac{\mu_+ - \mu_-}{\sqrt{2}\sigma}} \frac{1}{2\pi} \,\exp\left( -\frac{z^2+w^2}{2} \right) \,\text{d}z \,\text{d}w &(换元)\\ &= \int_{z < \frac{\mu_+ - \mu_-}{\sqrt{2}\sigma}} \frac{1}{\sqrt{2\pi}} \,\exp \left(-\frac{z^2}{2} \right) \,\text{d}z &(积掉w)\\ &= \Phi \left( \frac{\mu_+ - \mu_-}{\sqrt{2}\sigma} \right) &(\Phi的定义) \\ \end{align} \\$
即
$\frac{\mu_+ - \mu_-}{\sigma} = \sqrt{2}\,\Phi^{-1}(AUC) \\$

　　这个表达式的意思是说，如果我们知道了正、负类的得分服从等方差的高斯分布，那么就可以通过 $\sqrt{2} \, \Phi^{-1}(AUC)$ 反推出两类得分的均值相距几个标准差。当正、负类的得分不服从等方差的高斯分布时，我们也可以说，二分类器把正、负例分开的程度，相当于两类得分服从等方差的高斯分布，且均值相距 $\sqrt{2} \, \Phi^{-1}(AUC)$ 个标准差的情形，这个等效距离 $\sqrt{2} \, \Phi^{-1}(AUC)$ 就是。上面的推导过程也解答了关于系数 $\sqrt{2}$ 来历的疑问：它来自于计算二重积分时「换元」的步骤。

.　　指标可以放大低错误率系统之间的差距。举个例子： $\sqrt{2} \,\Phi^{-1}(0.99) \approx 3.29$ ， $\sqrt{2} \,\Phi^{-1}(0.999) \approx 4.37$ 。AUC 从 0.99 增长到 0.999，看似是「鹭鸶脚上劈精肉」，但其实相当于把两类得分的均值差距从 3 个多标准差拉大到了 4 个多标准差，进步可不小。

七、编程计算 AP 与 AUC 指标

　　本节介绍如何准确、高效、简洁地编程计算 AP 与 AUC 指标。

　　想要「准确」，就必须把样例按得分排序，然后考虑把阈值设在每两个相邻样例之间的情况。如果只是在得分的范围内均匀采样得到阈值，计算这些阈值对应的 P_+, R_+, R_- 然后用梯形法求 P-R 曲线和 ROC 曲线下的面积，就做不到准确。

　　想要「高效」，就要注意到阈值从一个位置移动到相邻位置时， P_+, R_+, R_- 都只有增量式的变化。如果对每个阈值都重新计算，就会低效。

　　想要程序「简洁」，就要使用支持向量计算的语言或库。下面我选择 Matlab 语言编程，讲解直接写在注释中。使用 Python 语言中的 numpy 库，也可以写出相似的代码。

function [AP, AUC] = ap_and_auc(score, truth)
    % 输入：两个向量，分别为每个样例的得分，以及每个样例的标准答案（0或1）

    % 把所有样例按从得分从高到低排序
    data = sortrows([score(:), truth(:)], -1); % -1表示按第1列降序排列
    score = data(:,1); truth = data(:,2);      % score和truth现在都是列向量

    % 阈值可以设置在两端，或者n个样例之间的n-1个空隙，但不能设置在得分相同的样例之间。
    % mask表示这n+1个位置有哪些可以设置阈值。
    mask = [true; diff(score) < 0; true];

    % 计算阈值设置在每个位置时，有多少正例被正确分类为正例（TP），多少负例被错误分类为正例（FP）。
    % 阈值设在最高处时，TP = FP = 0。阈值降低，每跨越一个正例，TP加1；每跨越一个负例，FP加1。
    % 所以可以利用cumsum函数高效计算TP和FP。
    TP = [0; cumsum(truth)];
    FP = [0; cumsum(1 - truth)];

    % 从TP和FP向量中去除不能设置阈值的位置
    TP = TP(mask); FP = FP(mask);

    % 求正例和负例的总数，它们等于阈值设在最低处时的TP和FP
    NP = TP(end); NN = FP(end);

    % 求出阈值设在每个位置时，正类的查准率PP
    PP = TP ./ (TP + FP);
    % 阈值设在每个位置时，正类的查全率TP/NP，负类的误查率为FP/NN。
    % 我们并不需要现在就把TP（FP）的每个元素都除以NP（NN），而是可以等到最后再除。

    % 根据定义计算AP。AP是在正类的查全率TP/NP有所上升时，正类的查准率PP的平均值。
    % 考虑到有的样例得分相同的情形，TP上升的幅度，就是取平均时的权重，而总权重是正例的总数NP。
    AP = sum(PP(2:end) .* diff(TP)) / NP;

    % 用梯形法计算AUC。当阈值从第i个位置移动到第i+1个位置时，ROC曲线上相应段落下方的面积为
    % (FP(i+1) - FP(i)) * (TP(i) + TP(i+1)) / 2 / (NP * NN)，AUC是这些面积的总和。
    AUC = sum(diff(FP) .* (TP(1:end-1) + TP(2:end))) / (2 * NP * NN);
end

　　程序中只有排序操作的复杂度是 $O(n\log n)$ ，其余都是复杂度 O(n) 的向量操作（为样例总数），故总复杂度是 $O(n\log n)$ 。

　　用本文开头的示例验证一下：

>> score = [.9, .8, .7, .6, .6, .5, .5, .4, .3];
>> truth = [1, 1, 0, 1, 0, 0, 0, 1, 0];
>> [AP, AUC] = ap_and_auc(score, truth)

AP =

    0.7750


AUC =

    0.7250

>>

本篇小结

AP 约等于 P-R 曲线下的面积；正例在所有数据中所占的比例可以作为 AP 的 baseline。AP 不能分解成某个函数对所有样例取平均的形式。
AUC 等于 ROC 曲线下的面积，它一般大于 AP。不管正例所占比例有多大，都可以用 0.5 作为 AUC 的 baseline。AUC 也不能分解成某个函数对所有样例取平均的形式，但可以分解成「阶跃函数」对所有「正负样例对」取平均的形式，其直观含义为：任取一个正例和一个负例，正例得分比负例高的概率有多大。
AUC 的值往往很接近 1。为了放大不同系统的差距，常常对 AUC 进行非线性伸缩，得到 $d' = \sqrt{2} \,\Phi^{-1}(AUC)$ 。的直观含义是，二分类器把正、负两类数据分开的程度，相当于两类得分服从等方差高斯分布时，均值相差几个标准差。
AP 和 AUC 可以用 $O(n\log n)$ 的复杂度准确、简洁地编程计算（为样例总数）。