【多标签, 极限的多标签算法】评价指标梳理

具体研究多标签和极限多标签 (XML) 的时候, 合理使用评价指标是关键.
最近在研究极限多标签算法的时候发现了它和传统多标签算法的评价指标是有异的, 而且我曾经积累的传统多标签评价指标也没有一个系统的体系 (很混乱). 于是写下本文用于自我总结.

---

1.14重置时补: 近期论文审稿意见回来后发现之前的评价指标在描述中存在一些理论错误, 故此更正当前文章.

---

如果读者们只是想来查找公式, 请务必阅读下面的红字!!!!!!!!!

---

1.常规多标签的评价指标

1.0 预备知识

常规的多标签学习是训练一个$N\times L$的标签预测矩阵$\hat{\mathbf{Y}}$, 然后基于$\hat{\mathbf{Y}}$全体数据 (不忽略任何值) 来讨论与同形的目标标签矩阵$\mathbf{Y}$的关系.
$N$是标签向量的个数, $L$是单个标签向量的维度.
数据矩阵$\mathbf{X}$的任意实例 (样本) ${\mathbf{x}}_i$, 它所对应的$L$个标签构成了这个实例的标签数组${\mathbf{y}}_i$, 显然, ${\mathbf{y}}_i=[y_{i1},y_{i2},\dots ,y_{iL}]$, 有任意$|{\mathbf{y}}_i|=L$ (见下图的蓝色框).
而标签向量是某个确定标签案例 (例如猫, 狗$\dots$), 在所有实例情况下的构成. 假设某个标签向量$l_k$, 有$l_k=[y_{1k},y_{2k},\dots ,y_{Nk}]$ (见下图的绿色框).

>> 关于标签的数值:

• y i ∈ { 0 , 1 } L \mathbf{y}_{i}\in\{0,1\}^L yi​∈{0,1}L, 有时会认为是 { − 1 , + 1 } L \{-1,+1\}^L {−1,+1}L. 在存在缺值时则多半为 { − 1 , 0 , + 1 } L \{-1,0,+1\}^L {−1,0,+1}L.
• ${\hat{\mathbf{y}}}_i\in {\mathbb{R}}^L$, 即0.25, 0.98, 0.02这些. 有的算法会将其约束在$[0,1]$, 而有的会约束在$[-1,1]$, 视具体算法而定.
• 简言之, 前者是二元的, 后者是实型的.
• 本文统一化描述, 下面的任何描述 (包括公式, 但不包括代码) 都是基于 y i ∈ { 0 , 1 } L \mathbf{y}_{i}\in\{0,1\}^L yi​∈{0,1}L 与 ${\hat{\mathbf{y}}}_i\in [0,1{]}^L$
• 在有些评价指标中, 我们需要将两个都是二值的标签矩阵进行比较, 这样的话我们就要对于$\hat{\mathbf{Y}}$ 进行阈值层面的过滤, 假设过滤函数为$p(\cdot )$, 有:$$p({\hat{y}}_{ij})=\{\begin{array}{ll}0,& {\hat{y}}_{ij}\le \theta )\\ 1,& {\hat{y}}_{ij}>\theta )\end{array}$$
  这样$p(\hat{\mathbf{Y}})$与$\mathbf{Y}$的元素就是统一的逻辑值了. 我们假定这个公式可以推广到向量和矩阵, 以矩阵为例:
  $$p(\hat{\mathbf{Y}})={\left(v_{ij}\right)}_{N\times L},v_{ij}=\{\begin{array}{ll}0,& {\hat{y}}_{ij}\le \theta )\\ 1,& {\hat{y}}_{ij}>\theta )\end{array}$$向量同理.

>> 关于评价指标的主要分类体系:

(参考自文章: Gibaja, E., & Ventura, S. (2015). A tutorial on multilabel learning. ACM Computing Surveys, 47 , 1–38.)

• Metrics to Evaluate Bipartitions (评估二分法的指标)
  • label-based metrics (基于标签的评价指标)
  • instance/example-based metrics (基于实例/样本的评价指标)
• Metrics to Evaluate Rankings (评估排序的指标 / 基于排序的评价指标)

>> 什么是基于样本和基于标签

• 基于样本的评价指标 : 对测试集中所有样本预测结果与真实情况之间进行一定的评价对比.
  这个所谓的样本(实例)的预测结果, 实际上对当前这个样本${\mathbf{x}}_i$的所有标签组成的数组${\mathbf{y}}_i$的预测, 即把标签矩阵$\mathbf{Y}$($N\times L$)拿出来, 一行一行预测, 每行的预测值取平均.
• 基于标签的评价指标 : 通过对每个单独标签的预测结果进行度量, 最后再对所有标签结果取平均.
  这个所谓的单独标签的预测结果, 实际上对某个标签下标$k$($1\le k\le L$)对应的所有样本构成的标签向量的预测, 即把标签矩阵$\mathbf{Y}$($N\times L$)拿出来, 一列一列预测, 每列的预测值取平均.

>> 关于micro和micro:

• micro我们称之为微平均, 而macro叫做宏平均. 这两个符号是基于标签的评价指标喜欢讨论的东西, 他们经常作为基于标签的评价指标的前缀.
• macro和macro往往是围绕混淆矩阵 (Confusion Matrix) 的概念.
• macro是将一个标签向量$l_k$作为一个整体, 探讨这个标签向量的混淆矩阵, 并且得到有关当前混淆矩阵的一些评价指标值. 最后将每个标签向量的评价指标值取平均. macro是最符合基于标签的评价指标的概念的
• micro是将整个矩阵$\mathbf{Y}$作为一个整体, 探讨这个矩阵的全局混淆矩阵, 并且得到有关当前混淆矩阵的评价指标值. 这就是最终结果. micro我感觉不太符合基于 “标签” 的说法, 我感觉更像是基于 “矩阵” 的, 或者基于 “全局” (这也是我前期搞混概念的主要原因).
• 通过我看MLL的论文, 我感觉macro用的最多.

1.1 基于样本的评价指标

基于样本的评价指标的核心是算出每个样本的所有标签为一个代表的单位中的评价指标值.
然后将每个评价指标求和取平均 (除$N$)

1.1.1 Accuracy

对于准确度Accuracy来说, 判断$\mathbf{Y}$与二值化后$\hat{\mathbf{Y}}$的关系, 若有${\hat{y}}_{ij}\in \hat{\mathbf{Y}}$, 同样的$i$与$j$, 也有$y_{ij}\in \mathbf{Y}$, 这时若有$y_{ij}={\hat{y}}_{ij}$, 则视为预测正确, 否则视为预测失败. 故Accuracy可以认为是正确预测的占比, 它自然越大是越好的:

$$\text{Acc}=\sum _{1<i<N,1<j<L}\frac{\lambda (p({\hat{y}}_{ij})=y_{ij})}{NL}$$
任何谓词$\pi$若为真, 则有$\lambda (\pi )=1$, 否则为0.
Accuracy有个老生常谈的问题, 当标签稍微稀疏点, 零元素一多, 预测失误会被过多的零元素掩盖. 这是Accuracy的不足.
Accuracy的公式有个更体现基于"样本"的版本, 就是将每个标签矩阵行的匹配标签个数加起来除以$L$, 得到当前行的评价值, 再把每一行的评价值加起来除以$N$. 上式不过是化简版本, 我喜欢这个版本.

1.1.2 Hamming Loss

Hamming Loss与Accuracy是类似的, Hamming Loss通过计算多标签分类器预测的标签结果${\hat{y}}_{ij}$ (二值化后)与实际标签$y_{ij}$的距离差来进行度量. 本质上也是一个逐个权衡然后再除全体个数. 它的公式如下:

$$\text{Hamming-Loss}=\sum _{1<i<N,1<j<L}\frac{\lambda (p({\hat{y}}_{ij})\ne y_{ij})}{NL}$$

Hamming Loss越小越好. 我的理解是Hamming Loss是Accuracy的对偶问题, 自然它们也共享相同的缺点

1.1.3 0/1 subset accuracy

因为暂时我用不到, 故有生之年补档.
可参考文献:

Shenghuo Zhu, Xiang Ji, Wei Xu, and Yihong Gong. 2005. Multi-labelled classification using maximum entropy method. In Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’05). ACM, New York, NY, 274–281.

1.1.4 Precision与Recall

这些方案是基于混淆矩阵的, 这里我们将会把某个样本${\mathbf{x}}_i$的所有标签构成的标签数组${\mathbf{y}}_i$看做为一个独立的个体, 找到这个个体的混淆矩阵, 并且输出这个混淆矩阵的一些指标. 最后将每个样本的指标取平均

其中主要有查准率和查全率的方案. 查准率 (Precision)用来判断在所有我的预测为正的样本中, 我预测对了的占比:

$$\text{Precision}=\sum _{i=1}^N{\text{Precision}}_i=\sum _{i=1}^N\frac{p({\hat{\mathbf{y}}}_i)\bullet {\mathbf{y}}_i}{\Vert \hat{\mathbf{y}}{\Vert }_0}$$

$\Vert \hat{\mathbf{y}}{\Vert }_0$是向量$\hat{\mathbf{y}}$的零范数, 表示$\hat{\mathbf{y}}$中1的个数, $p({\hat{\mathbf{y}}}_i)\bullet {\mathbf{y}}_i$就两个向量的内积, e.g., 若前者是[1, 0, 0, 1], 后者是[0, 0, 0, 1], 那么内积结果就是[0, 0, 0, 1]. 所以两个向量中相同位置的值都为1就计数.
查全率 (Recall)用来判断在所有正样本中, 我们预测对了的占比:

$$\text{Recall}=\sum _{i=1}^N{\text{Recall}}_i=\sum _{i=1}^N\frac{p({\hat{\mathbf{y}}}_i)\bullet {\mathbf{y}}_i}{\Vert \mathbf{y}{\Vert }_0}$$

1.1.5 $F_1\text{-Score}$ (基于样本)

基于这两个准则而建立起来的$F_1$-$\text{Measure}$ (又称之为$F_1$-$\text{Score}$)

$$F_1\text{-Score}=\frac{1}{N}\sum _{i=1}^N\frac{2\times {\text{Precision}}_i\times {\text{Recall}}_i}{{\text{Precision}}_i+{\text{Recall}}_i}$$

最好的情况下所有样本都有$P_i=R_i=1.0$, 这个时候$F_1$-$\text{Score}$的值为1.
其实$F_1\text{-Score}$还是一种比较通用的评价体系, 可以针对基于样本的案例, 也可以基于标签来做, 不同点就在于你的视角是什么样的.

• 如果你将标签矩阵$\mathbf{Y}$看做一行一行算$P_i$和$R_i$ ($1\le i\le N$)来计算$F_1{\text{-Score}}_i$, 最后平均, 那么他就是基于样本的评价指标$F_1\text{-Score}$;
• 如果你将标签矩阵$\mathbf{Y}$看做一列一列算$P_i$和$R_i$ ($1\le i\le L$)来计算$F_1{\text{-Score}}_i$, 最后平均, 那么他就是基于标签的评价指标$\text{macro-}{F}_1\text{-Score}$;
• 如果你将标签矩阵看做一个整体, 找到整体的混淆矩, 算了整体的Precision和Recall, 最后直接算出$F_1\text{-Score}$, 那么他就是基于标签的评价指标$\text{micro-}{F}_1\text{-Score}$;

---

稍微扩展下, $F_{\beta }\text{-Score}$其实是$F_1\text{-Score}$的一般形式, $F_1\text{-Score}$是$F_{\beta }\text{-Score}$中$\beta =1$的特殊情况. 这个公式如下:

$$F_{\beta }\text{-Score}=\frac{1}{N}\sum _{i=1}^N\frac{(1+{\beta }^2)P_i{R}_i}{(1+{\beta }^2)(P_i+R_i)}$$

其中, 当我们认为Recall更重要时, 往往会将$\beta =2$, 另外一些情况, 我们认为Precision更重要, 我们会取$\beta \in (0,1)$, 一般情况我们会折中取1, 这就是$F_1\text{-Score}$被我们官方使用的原因. 当然, 如果你的数据有显然的偏向性, 也可以另辟蹊径试试新的$F$值.

---

1.1.6 AUC (基于样本)

此外还有基于ROC曲线诞生的另一个评价指标AUC (AUC是ROC的曲线面积).
AUC的计算方案没有一个完全统一的标准, 但是就其本质方法来说, 是基于最佳的排序绘制出ROC曲线, 然后计算这个曲线的面积, 但是这个是排序评价指标, 稍后会提到, 故这里不过多赘述.
下面是基于样本方法的AUC计算, 实际上基于样本的AUC用的很少, 多数用的是基于标签的macro-AUC和micro-AUC, 我们稍后会提到.
$$\text{ AUC }=\frac{1}{N}\sum _{i=1}^N{\mathrm{AUC}}_i=\sum _{i=1}^N\frac{1}{N}\frac{\left|\left(y^{\prime },y^{\prime \prime }\right)\right|{\hat{y}}^{\prime }\ge {\hat{y}}^{\prime \prime },\left(y^{\prime },y^{\prime \prime }\right)\in {\mathcal{P}}_i\times {\mathcal{N}}_i\mid }{\left|{\mathcal{P}}_i\right|\left|{\mathcal{N}}_i\right|}$$
这里的${\mathcal{P}}_i$和${\mathcal{N}}_i$分别代表当前样本${\mathbf{x}}_i$所对应的真实目标标签为1的集合和为0的集合.
这里的$(y^{\prime },y^{\prime \prime })$代表一个标签对, 它是处在${\mathcal{P}}_i$和${\mathcal{N}}_i$的笛卡尔积中, 也就是它反映了所有"正负"标签对.
例如有真实标签向量$[0,0,1,1]$, 那么就有四个正负标签对:
$(y_{i3},y_{i1})$, $(y_{i3},y_{i2})$, $(y_{i4},y_{i1})$, $(y_{i4},y_{i2})$
然后我们挑选这些标签对中符合某个准则的标签对, 统计其数量, 作为分子.
这个准则是: 算法对于这个标签对中的两个标签的预测值一定是前大于后.

这个方法可以认为是我们后续讲述的基于排序的算法----Ranking Loss的一种对偶.
与$F_1\text{-Score}$一样, AUC也是一种比较通用的评价体系, 可以针对基于样本的案例, 也可以基于标签来做, 不同点就在于你的视角是什么样的.
略 (见1.1.5)

---

扩展:
计算单个向量的AUC还有一个基于排序的手段, 相关学习可以参考网站:
https://blog.csdn.net/pearl8899/article/details/126129148

1.2 基于标签的一些评价指标

基于标签的评价指标本身的度量方式大多与基于样本的重叠, 只不过在算平均的角度中略有差异.
因此异化出macro和micro的问题.
理论上, 任何基于样本的评价指标例如Precision和Recall, Accuracy, AUC, $F_1\text{-Score}$都可以变为基于标签的评价指标.

1.2.1 macro-AUC

关于AUC的理论参见1.1.6
公式更改成下面这个:
$$\text{ macro-AUC }=\frac{1}{L}\sum _{i=1}^L{\mathrm{AUC}}_i=\sum _{i=1}^L\frac{1}{L}\frac{\left|\left(y^{\prime },y^{\prime \prime }\right)\right|{\hat{y}}^{\prime }\ge {\hat{y}}^{\prime \prime },\left(y^{\prime },y^{\prime \prime }\right)\in {\mathcal{P}}_i\times {\mathcal{N}}_i\mid }{\left|{\mathcal{P}}_i\right|\left|{\mathcal{N}}_i\right|}$$
这里的${\mathcal{P}}_i$和${\mathcal{N}}_i$分别表示第$i$个标签向量中正标签的个数和负标签的个数. 其余理论一致.

1.2.2 micro-AUC

关于AUC的理论参见1.1.6
公式改成下面这个:
$$\text{ micro-AUC }=\frac{\left|\left(y^{\prime },y^{\prime \prime }\right)\right|{\hat{y}}^{\prime }\ge {\hat{y}}^{\prime \prime },\left(y^{\prime },y^{\prime \prime }\right)\in \mathcal{P}\times \mathcal{N}\mid }{\left|\mathcal{P}\right|\left|\mathcal{N}\right|}$$
这里的$\mathcal{P}$和$\mathcal{N}$表示整个标签矩阵$\mathbf{Y}$中正标签的个数和负标签的个数. 其余理论一致.

1.2.3 macro-Precision和macro-Recall

关于Precision和Recall的理论可见1.1.4
其中相关公式进行如下更改
$$\text{macro-Precision}=\sum _{i=1}^L{\text{macro-Precision}}_i=\sum _{i=1}^L\frac{p({\hat{l}}_i)\bullet l_i}{\Vert \hat{l}{\Vert }_0}$$
$$\text{macro-Recall}=\sum _{i=1}^L{\text{macro-Recall}}_i=\sum _{i=1}^L\frac{p({\hat{l}}_i)\bullet l_i}{\Vert l{\Vert }_0}$$
这里的${\text{macro-Precision}}_i$和${\text{macro-Recall}}_i$分别表示以第$i$个真实标签向量$l_i$和向量$p(l_i)$为标准构造出的混淆矩阵, 然后计算混淆矩阵的Precision值与Recall值. 其余理论一致.

1.2.4 micro-Precision和micro-Recall

关于Precision和Recall的理论可见1.1.4
其中相关公式进行如下更改
$$\text{micro-Precision}=\frac{p(\hat{\mathbf{Y}})\bullet \mathbf{Y}}{\Vert \hat{\mathbf{Y}}{\Vert }_0}$$
$$\text{micro-Recall}=\frac{p(\hat{\mathbf{Y}})\bullet \mathbf{Y}}{\Vert \mathbf{Y}{\Vert }_0}$$
$\bullet$是内积符号, 这里对于矩阵进行内积. 对于矩阵 [ 1 0 1 0 ] [1010]

[11​00​]和$\left[\begin{array}{cc}0& 0\\ 1& 0\end{array}\right]$, 他们的内积结果为$1\times 0+0\times 0+1\times 1+0\times 0=1$.

$\Vert \mathbf{Y}{\Vert }_0$求矩阵的零范数, 也就是矩阵中1的个数.

这里的$\text{micro-Precision}$和$\text{micro-Recall}$是通过将整个标签矩阵$\mathbf{Y}$和矩阵$p(\hat{\mathbf{Y}})$来构造一个全局混淆矩阵, 然后计算其$\text{Precision}$和$\text{Recall}$, 最终通过上述过程计算出评价指标. 其余理论一致.

1.2.5 macro-$F_1\text{-Score}$

关于$F_1\text{-Score}$的理论参见1.1.5
公式改成下面这个:
$$\text{macro-}{F}_1\text{-Score}=\frac{1}{L}\sum _{i=1}^L\frac{2\times {\text{macro-Precision}}_i\times {\text{macro-Recall}}_i}{{\text{macro-Precision}}_i+{\text{macro-Recall}}_i}$$
这里的${\text{macro-Precision}}_i$和${\text{macro-Recall}}_i$分别表示以第$i$个真实标签向量$l_i$和向量$p(l_i)$为标准构造出的混淆矩阵, 计算混淆矩阵的Precision值与Recall值. 详细参考1.2.3. 其余理论一致.

1.2.6 micro-$F_1\text{-Score}$

关于$F_1\text{-Score}$的理论参见1.1.5
公式改成下面这个:
$$\text{micro-}{F}_1\text{-Score}=\frac{2\times \text{micro-Precision}\times \text{micro-Recall}}{\text{micro-Precision}+\text{micro-Recall}}$$
这里的$\text{micro-Precision}$和$\text{micro-Recall}$是通过将整个标签矩阵$\mathbf{Y}$和矩阵$p(\hat{\mathbf{Y}})$来构造一个全局混淆矩阵, 然后计算其$\text{Precision}$和$\text{Recall}$, 最终通过上述过程计算出评价指标. 详细参考1.2.4. 其余理论一致.

1.3 基于排序的一些评价指标

基于排序的一些评价指标的基础是基于样本的评价指标, 基本上我们是从每个样本对应的所有标签为一个单位进行计算并最后取平均, 只不过对于每个样本的计算手段采用了排序. 这样的评价指标有One-Error, Coverage, Ranking Loss, NDCG. 当然另外一部分业界似乎使用较少, 定义较少, 即$\text{Peak }{F}_1\text{-Score}$, 这个通过定义可能使用基于标签的micro策略会更好.

1.3.1 One-Error

One-Error 衡量了测试集的样例中排名第一的标签不是相关标签的比例, 这个值我们希望越小越好.

$$\text{One-Error}=\frac{1}{N}\sum _{i=1}^N\left((\underset{0\le j<L}{\mathrm{argmax}}{\hat{\mathbf{y}}}_i)\notin {\mathbf{Y}}_i^{+}\right)$$

这里的${\hat{\mathbf{y}}}_i$表示第$i$个样本对应的所有标签组成的数组, ${\mathrm{argmin}}_{0\le j<L}{\hat{\mathbf{y}}}_i$取出了${\hat{\mathbf{y}}}_i$中预测实数值最高的那个值的下标$j$ (L是下标可取的上界), ${\mathcal{Y}}_i^{+}$是样本${\mathbf{x}}_i$的所有标记为1的真实标签的下标集合. 因此, 如果我们对于${\hat{\mathbf{y}}}_i$中最高预测值预测错了, 那么求和式就会+1, One-Error就会增加.

1.3.2 Coverage

Coverage 衡量了在预测的排序标签列表上需要从头走多少步, 才能覆盖真实标签中所有的正例:

$$\text{Coverage}=\frac{1}{m}\sum _{i=1}^m\left(\underset{j\in {\mathcal{Y}}_i^{+}}{\max }\text{rank}({\hat{\mathbf{y}}}_i)-1\right)$$

这里${\mathcal{Y}}_i^{+}$是样本${\mathbf{x}}_i$的所有标记为1的真实标签的下标集合. ${\max }_{j\in {\mathcal{Y}}_i^{+}}\text{rank}({\hat{\mathbf{y}}}_i)$ 选择了${\hat{\mathbf{y}}}_i$预测标签中排名尽可能靠后的一个在真实标签中映射为+1的标签的下标. 至于式中 - 1是依情况而定, 因为我们这里假定$\text{Rank()}$返回排名最小是1, 而最好的情况下一步不走就能覆盖所有 (图中${\hat{y}}_3$→$y_3$)

图例解释(${\hat{y}}_2$→$y_2$): ${\hat{y}}_2=[0.11,0.47,0.55,0.29]$, 排序后的${\hat{y}}_2=[0.55,0.47,0.29,0.11]$, 按照这种排序映射到$y_2$, 为$[1,0,1,0]$, 可以发现走了两步走到了最后一个1, 即$[1\to 0\to 1,0]$.
Coverage 是越小越好.

1.3.3 Ranking Loss

Ranking Loss 反映了所有样本的预测标签排序中, 不相关标签排在相关标签前面的概率.

$$\text{Ranking-Loss}=\frac{1}{m}\sum _{i=1}^m\frac{1}{|{\mathcal{Y}}_i^{-}||{\mathcal{Y}}_i^{+}|}|\{(y_{ij},y_{ik})|{\hat{y}}_{ij}\ge {\hat{y}}_{ik},(y_{ij},y_{ik})\in {\mathcal{Y}}_i^{-}\times {\mathcal{Y}}_i^{+}\}|$$

这里${\mathcal{Y}}_i^{-}$是样本${\mathbf{x}}_i$的所有标记为0的真实标签的下标集合, 显然, 其补集就是${\mathcal{Y}}_i^{+}$. 下面是以第二个标签为例的图例:
可见, Ranking Loss也是越小越好, 一旦有错误的预测排到非常靠前的话, 这个错误值超过了多少正确值, 那么就会等线性地惩罚它. 他的思想类似与$\text{NDCG}$, 只不过后者是对数级别的.
这个算法可以认为是$\text{AUC}$一种解法的对偶, 而且它虽然名称中有Rank, 但是它可以不通过排序实现.

1.3.4 Average Precision (AP)

AP可以认为是P-R曲线围成的面积, 这个曲线是通过Precision作为纵轴, Recall作为横轴.
从数值角度来看, AP可以认为是不同的Recall采样点下的Precision的值的一个平均的结果.
具体来说, 我们在每个Recall的采样点进行一个标记, 判断这些判断点的Precision值, 将他们求和取平均.
我们假设个情况, 现在有五个取样点, 每次取样的时候我们都断言为+1, 一共的正样例有3个, 初始不取样的P与R都为0. 现在我们假设下述取样: (下述内容需要读者提前预备关于Precision与Recall的有关储备知识)

作图:

其结果是上述四个有效取样点的Precision求平均:$\text{AP}=\frac{1}{5}(0+1+1+\frac{2}{3}+\frac{3}{4})$
我们希望PR曲线是越往外"凸"效果越好, 即实际体现出来的就是Precision维持为1的情况尽可能多持续一段时间. 要实现这样的效果就需要将我们的预测标签${\hat{\mathbf{y}}}_i$进行排序, 最后取AP的均值.

排序后, 向量前端的标签预测为$+1$后有更大概率预测对, 从这里开始逐个采样, 能保证在前期更多地采到正确点.

故一个预测矩阵与真实矩阵之间的AP值就有:
$$\text{Average Precision}=\frac{1}{N}\sum _{i=1}^N{\text{AP}}_i$$显然, 这里${\text{AP}}_i$是${\hat{\mathbf{y}}}_i$与${\mathbf{y}}_i$共同决定的.

1.3.5 NDCG 及其micro与macro设想

NDCG 这个评价指标来自于推荐系统, 他是DCG的归一化表示, DCG是评价值与排名的对数损失的比例
(NDCG有的地方也喜欢写作nDCG, 这个好像没有完全统一的标准)
(这里的对数是以2为底的)

$$\text{DCG}(\mathbf{r},{\hat{\mathbf{y}}}_{\mathbf{i}})=\sum _{t=1}^k\frac{{\hat{y}}_{il}^{\mathbf{r}}}{\log (1+t)}$$

这里的$\mathbf{r}$是一种排序准则, 我们假设它是根据预测的标签${\hat{\mathbf{y}}}_i$从大到小进行了一次排序得到了${\hat{\mathbf{y}}}_i^{\mathbf{r}}$, 而排序后的顺序索引由$l$表示, 即可认为$t=1$时的${\hat{y}}_{i1}^{\mathbf{r}}$就是这个标签中预测值最高的标签特征. $k$是这个标签的维度上限, 即标签长度.
我们可以假设一个最佳DCG (又名IDCG)场景, 即我们的标签${\hat{\mathbf{y}}}_i$完全与${\mathbf{y}}_i$一致. 若${\mathbf{y}}_i$是由$m$个$+1$和$n$个$0$构成, 那么可以肯定的是${\mathbf{y}}_i^{\mathbf{r}}$是前部为$m$个$+1$构成, 尾部由$n$个$0$构成的向量$[+1,+1,+1,\dots ,0,0,0]$. 其公式可直接表示为:

$$\text{IDCG}(\mathbf{r},{\hat{\mathbf{y}}}_{\mathbf{i}})=\sum _{t=1}^m\frac{1}{\log (1+t)},(m=||{\mathbf{y}}_i|{|}_0)$$

可得:

$$\text{NDCG}(\mathbf{r},{\hat{\mathbf{y}}}_{\mathbf{i}})=\frac{\text{DCG}(\mathbf{r},{\hat{\mathbf{y}}}_{\mathbf{i}})}{\text{IDCG}(\mathbf{r},{\hat{\mathbf{y}}}_{\mathbf{i}})}$$

如果常规地作为基于排序的评价指标, 那么求总的NDCG使用的平均就应该是基于样本的形式. 故有总NDCG计算公式:
$$\text{NDCG}=\sum _{i=1}^N\frac{\text{DCG}(\mathbf{r},{\hat{\mathbf{y}}}_{\mathbf{i}})}{\text{IDCG}(\mathbf{r},{\hat{\mathbf{y}}}_{\mathbf{i}})}$$
然后下面的内容就是我的一种猜测, 全网我似乎还没看到采用这种方式的文章.
首先, 通过基于排序的评价指标的规律, 我们也可以设计出macro-NDCG
$$\text{macro-NDCG}=\sum _{i=1}^L\frac{\text{DCG}(\mathbf{r},l_i)}{\text{IDCG}(\mathbf{r},{\hat{l}}_i)}$$
顺理成章, micro-NDCG也是可以设计出来的, 大体上就是预测矩阵和真实目标矩阵都压缩为一维向量$\hat{\mathbf{s}}$和$\mathbf{s}$, 然后有公式:
$$\text{micro-NDCG}=\frac{\text{DCG}(\mathbf{r},{\mathbf{s}}_i)}{\text{IDCG}(\mathbf{r},{\hat{\mathbf{s}}}_i)}$$

1.3.6 $\text{Peak-}{F}_1\text{-Score}$

有的地方可能会将其称之为$\text{Best-}{F}_1\text{-Score}$, 我在我的MASP算法介绍的博客中详细介绍了这个评价指标的来由和应用(请查看这篇文章的4.3.3节 )
他的思想是将预测标签结果$\hat{\mathbf{Y}}$依照从大到小顺序重排, 这个重排的基本单位必须是矩阵, 因为我们计算$\text{Peak-}{F}_1\text{-Score}$的目的是为了找到一个全局的阈值$\theta$, 在这个$\theta$控制下, $p(\cdot )$函数可以引导一个最佳的阈值过滤, 使得$p(\hat{\mathbf{Y}})$与$p(\mathbf{Y})$引导的混淆矩阵下的$\text{micro-}{F}_1\text{-Score}$最大.

• 为什么没法找到个公共阈值$\theta$使得$\text{micro-}{F}_1\text{-Score}$或者基于样本的$F_1\text{-Score}$最大?
  $\text{micro-}{F}_1\text{-Score}$和基于样本的$F_1\text{-Score}$难以找到一个最佳的大家共用的阈值$\theta$, 因为大家的$F_1\text{-Score}$都是 各自列 或者 各自行 各算各的, 这陷入了多目标规划的最优解困境. 某几个向量的度量最优, 但是另外几个就不一定最优.

言归正传.
假设将$\hat{\mathbf{Y}}$压缩为向量$\hat{\mathbf{s}}$, 将$\mathbf{Y}$压缩为向量$\mathbf{s}$, $\hat{\mathbf{s}}$从大到小排序, 这个排序方案同样作用到$\mathbf{s}$上, 重排后我们按照大到小依序采样, 每个采样点都预测为正标签, 一共会计算$N\times L$次$F_1\text{-score}$:
假设预测概率标签$\hat{\mathbf{s}}=[0.98,0.95,0.90,...,0.08,0.01]$

真实标签为$\mathbf{s}=[1,1,0,...,1,0]$
第一次推测的真实标签$[1,0,0,...,0,0]$, 计算当前$F_1\text{-score}$
第二次推测的真实标签$[1,1,0,...,0,0]$, 计算当前$F_1\text{-score}$
…
第$N\times L-1$次推测的真实标签$[1,1,1,...,1,0]$, 计算当前$F_1\text{-score}$
第$N\times L$次推测的真实标签$[1,1,1,...,1,1]$, 计算当前$F_1\text{-score}$

每层都以真实标签作为参考, 从而像计算AP那样逐次更新Recall和Precision, 并且按照这个Recall和Precision来计算$F_1\text{-Score}$.
下面举个例子, 这里是一个五维的标签

现在将其按照预测标签来进行联合的排序, 然后依次采样, 分别预测Precision和Recall, 计算$F_1\text{-Score}$

这时可以看到有段$F_1\text{-Score}$处于最高值, 我们的$\text{Peak-}{F}_1$就取这个值.
${\text{Peak-F}}_1$反映出一种阈值效应: 在我们按照预测标签的预测值进行排序后, 在中间某点找到了$\text{Peak-}{F}_1$, 这时标签的预测值为$0.75$. 于是设置预测阈值为$\theta =0.75$, 即预测标签中所有预测实值大于$0.75$的都预测为$+1$, 其余为$0$. 这样的话可以保证全局$\text{micro-}{F}_1\text{-Score}$能保持在$\text{Peak-}{F}_1\text{-Score}$状态.
可见上述例子, 不难得出$\theta =0.5$, 标签$[0.4,0.5,0.2,0.3,0.8]$预测为$[0,1,0,0,1]$, 这样我们哪怕不排序而直接计算$F_1\text{-Score}$都可以稳定在最高值.
这也是我最近投稿的论文采用的评价指标, 它用来评价还算是不错的. 但是也需要认清一个现实, 往往来说$F_1\text{-Score}$的数值是非常低的, 所以现在非常多的算法在力图做高$F_1\text{-Score}$, 这也是目前机器学习中多分类多标签等算法在努力的方向.

2.极限多标签的评价指标

起初我一直以为极限多标签共享一般多标签的评价指标, 但是就几篇论文来看似乎不是这样.
若极限多标签也采用这样的评价方案效率会很低, 而且数值本身也会很差.
下面是我在Bhatia等一行人总结的极限多标签研究的开源网站 (http://manikvarma.org/downloads/XC/XMLRepository.html)中学习得到的.
同时, 参考了部分极限的多标签的算法的源码 (FastXML)
极限多标签的特征数目和标签维度巨大且稀疏的, 相关知识可见我的这篇文章第一节
一些预备知识:

$$l\in {\mathrm{rank}}_k(\hat{\mathbf{y}})$$

$\hat{\mathbf{y}}$是一个预测得到的标签, 满足$\hat{\mathbf{y}}\in {\mathbb{R}}^L$.
$\mathrm{rank}(\hat{\mathbf{y}})$是将预测标签$\hat{\mathbf{y}}$向量的标签值更改为一个新值, 这个新值是此向量内部按照从大到小排序后每个标签值的新位置的下标.
例如有向量$\hat{\mathbf{y}}=[0.5,0.8,0.2,0.3]$, 有$\mathrm{rank}(\hat{\mathbf{y}})=[1,0,3,2]$, 而${\mathrm{rank}}_k(\hat{\mathbf{y}})$就是拎出$\hat{\mathbf{y}}$中前$k$大的下标, 例如 rank ⁡ 3 ( y ^ ) = { 0 , 1 , 3 } \operatorname{rank}_3(\hat{\mathbf{y}}) = \{0,1,3\} rank3​(y^​)={0,1,3}, rank ⁡ 2 ( y ^ ) = { 0 , 1 } \operatorname{rank}_2(\hat{\mathbf{y}}) = \{0,1\} rank2​(y^​)={0,1}, rank ⁡ 2 ( y ^ ) = { 1 } \operatorname{rank}_2(\hat{\mathbf{y}}) = \{1\} rank2​(y^​)={1}.
如果你想不带脑子理解的话, 你可以认为, ${\mathrm{rank}}_k(\hat{\mathbf{y}})$返回了$\hat{\mathbf{y}}$向量中前$k$个最大的标签值的下标.

2.1 Precision@k

这个算法既不像Accuracy, 也不像Precision. 公式如下:

$$\mathrm{P}@k:=\frac{1}{k}\sum _{v\in {\mathrm{rank}}_k(\hat{\mathbf{y}})}{\mathbf{y}}_t$$

其中$k<\Vert \mathbf{y}{\Vert }_0\ll |\mathbf{y}|$.
极限多标签算法预测得到了一个预测矩阵$\hat{\mathbf{Y}}$, 这公式只关注其中某个$\hat{\mathbf{y}}$
得到了$\hat{\mathbf{y}}$中前$k$个最大的标签值的下标集$v$, 然后通过这些下标来映射到真实标签向量$\mathbf{y}$中, 从而得到${\mathbf{y}}_t$. 预测正确, 则求和$+1$, 否则求和$+0$, 最后, 取平均.
总结来看, $\text{Precision@}k$ 是 对于标签数组最有把握的前$k$个标签值的预测正确率. 当某个标签的$\text{Precision@}5$ = 1.0 说明这个标签数组预测中标签预测值最高的那五个标签都预测对了, 确实在目标标签中它们为$+1$; 但是如果$\text{Precision@}5$ = 0.8, 那么说明那五个标签至少有一个预测错了.
一般的极限多标签算法喜欢将$k$取为1, 3, 5, 往往来说$k$越大, 我们失误的几率越大, $\text{Precision@}k$也会越低; 而$k=1$时, 评价指标退化为One-Error的对偶评价指标; 当$k$等于$\mathbf{y}$的长度时, 这个评价指标又变为了一般的Accuracy评价指标.

2.2 NDCG@k

这个算法是基于常规的基于排序的NDCG算法改进得到. 极限多标签算法中有例如FastXML这种专门通过优化这个评价指标而实现的算法.
下面我们只讨论一个向量$\mathbf{y}$在预测向量$\mathbf{y}$影响下的$\text{ DCG@}k$

$$\text{ DCG@}k:=\sum _{t\in {\mathrm{rank}}_k(\hat{\mathbf{y}})}\frac{{\mathbf{y}}_t}{\log (t+1)}$$

$$NDCG@k:=\frac{\mathrm{DCG}@k}{{\sum }_{t=1}^{\min \left(k,\Vert \mathbf{y}{\Vert }_0\right)}\frac{1}{\log (t+1)}}$$

可见, 相比NDCG, 这里的算法也是多了一个$k$, 它们的判断思路是一致.
并且选择了其中的前$k$的下标集, 将其命名为$v$.
$\text{DCG@}k$与$\text{Precision@}k$基本上是一致的, 只不过$\text{ DCG@ }k$在加上每次的结果时都除以一个对数损失, 因此, 随着排名的靠后, 它为$\text{DCG@}k$的贡献会逐步减小, 同时又因为我们加以的是对数损失, 因此在$t$不是特别大时, 这种损失往往又不会导致特别严重的下降.
另外要注意, 这个公式并不是死的, 倘若你的基础编程语言的下标是从0开始的, 那么这里的对数损失应该改为$\log (t+2)$, 避免除0错误.
$\text{NDCG@}k$是归一化的$\text{DCG@}k$, 即对$\text{DCG@}k$除以一个$\text{IDCG@}k$.
通过1.3.5可得, $\text{IDCG}$的计算主要取决于标签$\mathbf{y}$中有多少非零元, 而引入$k$后, 因为存在$k<\Vert \mathbf{y}{\Vert }_0$, 因此要遵守木桶原则, 选择最小的那个作为求和上限.

• 了解其原理后可以试着思考: 为什么$\text{NDCG}$可以采用$\text{@k}$来限制呢?
  因为$\text{NDCG}$非常依赖于排名靠前的预测, 往后的正确预测固然能带来数值的正反馈, 但是因为对数损失的存在, 它们的贡献始终是少的. 例如$l=1,10,20,30,40$的变化: $\frac{1}{{\log }_2(1+1)}=1$, $\frac{1}{{\log }_2(10+1)}\approx 0.29$, $\frac{1}{{\log }_2(20+1)}\approx 0.23$, $\frac{1}{{\log }_2(30+1)}\approx 0.20$, $\frac{1}{{\log }_2(40+1)}\approx 0.19$ ——可见数值波动逐渐不显著.
  可以认为, 因为在极限多标签中, 对标签矩阵进行整体评价的开销非常大, 所以极限多标签的评价指标更侧重于"管中窥豹", 即从局部来最大化推测全局.
  而在许多评价指标中, 基于排序的评价指标能很好承担这个职责 (因为排序后的关键信息集中在了前端, 且因为标签稀疏性, 前端的内容也并不会很多); 而在众多基于排序的评价指标中, $\text{NDCG@k}$又是其中最好的选择之一 (因为它对排名的"中", "末"端的依赖性低, 能最大化缩小复杂度, 同时也保证了通过引入$k$之后的$\text{NDCG@k}$与原$\text{NDCG}$的差异是可以接受的).

2.3 PSP@k

(目前学习范围暂时与此无关, 故还未学习)

2.4 PSnDCG@k

(目前学习范围暂时与此无关, 故还未学习)

3 私货环节 (随时更新)

私货环节主要是用来存些代码用的.
这些代码有些是我看论文收集的, 有些是我自己写的, 有些是仅仅调库使用过的.
我基本是可以保证, 同个评价指标的同样输入, 在不同编程语言环境下的输出是一致的!
排名不分向后.
请注意输入矩阵是$N\times L$ 还是 $L\times N$, 因为信息太多, 这部分我就没统一了, 大家使用的时候注意下, 必要的话就自己改下吧.

3.1 Python

1.3.5 节的 NDCG

• 注意: 计算的严格说是micro-NDCG, 因为我将矩阵都压缩为一维来计算的.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{N\times L}$, 第二个是 Y ∈ { 0 , 1 } N × L \mathbf{Y}\in\{0,1\}^{N \times L} Y∈{0,1}N×L. 数据类型为numpy.
• 计算思想: 压缩为一维, 直接计算一维向量之间关系.

def computeNDCG(output, test_target):
    '''
    Compute the NDCG

    :return: the NDCG
    '''

    # 获得概率序列与原目标序列
    tempProbVector = output.reshape(-1)
    tempTargetVector = test_target.reshape(-1)

    # 按照概率序列排序原1/0串
    temp = np.argsort(-tempProbVector)
    allLabelSort = tempTargetVector[temp]

    # 获得最佳序列: 1111...10000...0
    sortedTargetVector = np.sort(tempTargetVector)[::-1]

    # compute DCG
    DCG = 0
    for i in range(temp.size):
        rel = allLabelSort[i]
        denominator = np.log2(i + 2)
        DCG += (rel / denominator)

    # compute iDCG
    iDCG = 0
    for i in range(temp.size):
        rel = sortedTargetVector[i]
        denominator = np.log2(i + 2)
        iDCG += (rel / denominator)

    return DCG / iDCG
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

1.3.6 节的$\text{Peak-}{F}_1\text{ Score}$ (自己写的, 但参考了师兄的代码)

• 注意: 无.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{N\times L}$, 第二个是 Y ∈ { 0 , 1 } N × L \mathbf{Y}\in\{0,1\}^{N \times L} Y∈{0,1}N×L. 数据类型为numpy.
• 计算思想: 压缩为一维, 直接计算一维向量之间关系.

def computepeakF1Score(outputs, test_target):
    '''
    Compute the Peak F1-score

    :return: The Peak F1-score
    '''

    tempProbVector = outputs.reshape(-1).cpu().detach().numpy()
    temp = np.argsort(-tempProbVector)
    tempTargetVector = test_target.reshape(-1)
    allLabelSort = tempTargetVector[temp]

    tempYF1 = np.zeros(temp.size)

    allTP = np.sum(tempTargetVector == 1)

    for i in range(temp.size):

        TP = np.sum(allLabelSort[0:i + 1] == 1)
        P = TP / (i + 1)
        R = TP / allTP
        if (P + R) == 0:
            tempYF1[i] = 0
        else:
            tempYF1[i] = 2.0 * P * R / (P + R)
    return np.max(tempYF1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

1.2.2 micro-AUC

• 注意: 无.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{N\times L}$, 第二个是 Y ∈ { 0 , 1 } N × L \mathbf{Y}\in\{0,1\}^{N \times L} Y∈{0,1}N×L. 数据类型为numpy.
• 计算思想: 压缩为一维, 直接计算一维向量之间关系.

def computeMicroAUC(outputs, test_target):
    '''
    Compute the MicroAUC

    :return: The MicroAUC
    '''

    # The matrix is compressed into 1 dimension,
    # then the internal information of the original single label can be ignored.
    # so the global AUC can be calculated
    tempProbVector = outputs.reshape(-1)
    tempTargetVector = test_target.reshape(-1)
    return metrics.roc_auc_score(tempTargetVector, tempProbVector)
1
2
3
4
5
6
7
8
9
10
11
12
13

1.2.1 macro-AUC

• 注意: 若某一列的真实目标标签全是0, 那么这一列+0; 若某一列的真实目标标签全是1, 那么这一列+1;
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{N\times L}$, 第二个是 Y ∈ { 0 , 1 } N × L \mathbf{Y}\in\{0,1\}^{N \times L} Y∈{0,1}N×L. 数据类型为numpy.
• 计算思想: 每列每列算, 最后取平均.

def computeMacroAUC(outputs, test_target):
    '''
    Compute the MacroAUC

    :return: The MacroAUC
    '''

    labelNum = outputs.shape[1]
    aucValue = 0

    # "One Error" needs to judge each row of the label matrix.
    # If we judge matrix by column, the information may be too little
    for i in range(labelNum):
        if np.mean(test_target[:, i]) == 1:
            aucValue += 1
        elif np.mean(test_target[:, i]) == 0:
            aucValue += 0
        else:
            aucValue += metrics.roc_auc_score(test_target[:, i], outputs[:, i])
    return aucValue / labelNum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1.3.1 One-Error

• 注意: 若某一行的真实目标标签全是0, 那么这一行不进入统计.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{N\times L}$, 第二个是 Y ∈ { 0 , 1 } N × L \mathbf{Y}\in\{0,1\}^{N \times L} Y∈{0,1}N×L. 数据类型为numpy.
• 计算思想: 每行每行算, 最后取平均.

def computeOneError(output, test_target):
    '''
    Compute the One Error

    :return: The One Error
    '''

    instanceNum = output.shape[0]

    errorList = []
    # "One Error" needs to judge each row of the label matrix.
    # If we judge matrix by column, the information may be too little.
    for i in range(instanceNum):
        # The target label consists only of 0 and 1.
        # If the sample has no positive label, the sample is not predicted.
        if np.mean(test_target[i]) == 0.0:
            continue
        index = np.argmax(output[i])
        if test_target[i][index] == 0:
            errorList.append(1)
        else:
            errorList.append(0)
    return np.mean(np.array(errorList))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

1.3.2 Coverage

• 注意: 若某一行的真实目标标签全是0, 那么这一行统计值+0.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{N\times L}$, 第二个是 Y ∈ { 0 , 1 } N × L \mathbf{Y}\in\{0,1\}^{N \times L} Y∈{0,1}N×L. 数据类型为numpy.
• 计算思想: 每行每行算, 最后取平均.

def computeCoverage(output, test_target):
    '''
    Compute the Coverage

    :return: the Coverage
    '''

    # Subtract 1 when sorting each sample
    instanceNum = test_target.shape[0]
    label_index = []
    for i in range(instanceNum):
        index = np.where(test_target[i] == 1)[0]
        label_index.append(index)
    cover = 0
    for i in range(instanceNum):
        index = np.argsort(-output[i]).tolist()
        tmp = 0
        for item in label_index[i]:    # If the current instance has no positive label, end directly.
            tmp = max(tmp, index.index(item))
        cover += tmp
    coverage = cover * 1.0 / instanceNum
    return coverage
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

1.3.3 Ranking Loss

• 注意: 若某一行的真实目标标签全是0, 那么这一行不进入统计.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{N\times L}$, 第二个是 Y ∈ { 0 , 1 } N × L \mathbf{Y}\in\{0,1\}^{N \times L} Y∈{0,1}N×L. 数据类型为numpy.
• 计算思想: 每行每行算, 最后取平均.

def computeRankingLoss(output, test_target):
    '''
    Compute the Ranking Loss

    :return: the Ranking Loss
    '''

    probaMatrix = []
    targetMatrix = []
    for index, trueLabel in enumerate(test_target):
        if np.mean(trueLabel) == 0:     # empty true label have no meaning
            continue
        probaMatrix.append(output[index])
        targetMatrix.append(trueLabel)
    return metrics.label_ranking_loss(np.array(targetMatrix), np.array(probaMatrix))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.1.2 Hamming Loss

• 注意: 这里默认将阈值设置为了0.5.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{N\times L}$, 第二个是 Y ∈ { 0 , 1 } N × L \mathbf{Y}\in\{0,1\}^{N \times L} Y∈{0,1}N×L. 数据类型为numpy.
• 计算思想: 每行每行算, 最后取平均.

def computeHammingLoss(output, test_target):
    '''
    Compute the Hamming Loss

    :return: the Hamming Loss
    '''

    # Set the prediction threshold to 0.5
    output[np.where(output >= 0.5)] = 1.0
    output[np.where(output < 0.5)] = 0.0

    return metrics.hamming_loss(test_target, output)
1
2
3
4
5
6
7
8
9
10
11
12

3.2 Matlab

1.3.1 节的One-Error

• 注意: 若某一列的真实目标标签全是0, 那么这一列不进入统计.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{L\times N}$ (支持$\hat{\mathbf{Y}}\in [-1,1{]}^{L\times N}$), 第二个是 Y ∈ { 0 , 1 } L × N \mathbf{Y}\in\{0,1\}^{L \times N} Y∈{0,1}L×N (支持 Y ^ ∈ { − 1 , 1 } L × N \mathbf{\hat{Y}}\in\{-1,1\}^{L \times N} Y^∈{−1,1}L×N).
• 计算思想: 每列每列算, 最后取平均.

function OneError=One_error(Outputs,test_target)
%Computing the one error
%Outputs: the predicted outputs of the classifier, the output of the ith instance for the jth class is stored in Outputs(j,i)
%test_target: the actual labels of the test instances, if the ith instance belong to the jth class, test_target(j,i)=1, otherwise test_target(j,i)=-1
  
    test_target((test_target == 0)) = -1;       % To avoid the illegal input
    
    [num_class,num_instance]=size(Outputs);
    temp_Outputs=[];
    temp_test_target=[];
    for i=1:num_instance                                        
        temp=test_target(:,i);
        if((sum(temp)~=num_class)&(sum(temp)~=-num_class))
            temp_Outputs=[temp_Outputs,Outputs(:,i)];
            temp_test_target=[temp_test_target,temp];
        end
    end
    Outputs=temp_Outputs;
    test_target=temp_test_target;     
    [num_class,num_instance]=size(Outputs);
    
    Label=cell(num_instance,1);                                 
    not_Label=cell(num_instance,1);                             
    Label_size=zeros(1,num_instance);                           
    for i=1:num_instance
        temp=test_target(:,i);                                  
        Label_size(1,i)=sum(temp==ones(num_class,1));           
        for j=1:num_class
            if(temp(j)==1)
                Label{i,1}=[Label{i,1},j];                      
            else
                not_Label{i,1}=[not_Label{i,1},j];
            end
        end
    end
    
    oneerr=0;
    for i=1:num_instance
        indicator=0;
        temp=Outputs(:,i);
        [maximum,index]=max(temp);
        for j=1:num_class
            if(temp(j)==maximum)                
                if(ismember(j,Label{i,1}))
                    indicator=1;
                    break;
                end
            end
        end
        if(indicator==0)
            oneerr=oneerr+1;
        end
    end
    OneError=oneerr/num_instance;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

1.3.2 节的 Coverage

• 注意: 若某一列的真实目标标签全是0, 那么这一列统计值+0.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{L\times N}$ (支持$\hat{\mathbf{Y}}\in [-1,1{]}^{L\times N}$), 第二个是 Y ∈ { 0 , 1 } L × N \mathbf{Y}\in\{0,1\}^{L \times N} Y∈{0,1}L×N (支持 Y ^ ∈ { − 1 , 1 } L × N \mathbf{\hat{Y}}\in\{-1,1\}^{L \times N} Y^∈{−1,1}L×N).
• 计算思想: 每列每列算, 最后取平均.

function Coverage=coverage(Outputs,test_target)
%Computing the coverage
%Outputs: the predicted outputs of the classifier, the output of the ith instance for the jth class is stored in Outputs(j,i)
%test_target: the actual labels of the test instances, if the ith instance belong to the jth class, test_target(j,i)=1, otherwise test_target(j,i)=-1

       test_target((test_target == 0)) = -1;       % To avoid the illegal input

       [num_class,num_instance]=size(Outputs);
    
       Label=cell(num_instance,1);
       not_Label=cell(num_instance,1);
       Label_size=zeros(1,num_instance);
       for i=1:num_instance
           temp=test_target(:,i);
           Label_size(1,i)=sum(temp==ones(num_class,1));
           for j=1:num_class
               if(temp(j)==1)
                   Label{i,1}=[Label{i,1},j];
               else
                   not_Label{i,1}=[not_Label{i,1},j];
               end
           end
       end

       cover=0;
       for i=1:num_instance
           temp=Outputs(:,i);
           [tempvalue,index]=sort(temp);
           temp_min=num_class+1;
           for m=1:Label_size(i)
               [tempvalue,loc]=ismember(Label{i,1}(m),index);
               if(loc<temp_min)
                   temp_min=loc;
               end
           end
           if Label_size(i) == 0
              cover=cover+1;
           else
              cover=cover+(num_class-temp_min+1);
           end
       end
       Coverage=(cover/num_instance)-1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

1.3.3 节的 Ranking Loss

• 注意: 若某一列的真实目标标签全是0, 那么这一列不进入统计.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{L\times N}$ (支持$\hat{\mathbf{Y}}\in [-1,1{]}^{L\times N}$), 第二个是 Y ∈ { 0 , 1 } L × N \mathbf{Y}\in\{0,1\}^{L \times N} Y∈{0,1}L×N (支持 Y ^ ∈ { − 1 , 1 } L × N \mathbf{\hat{Y}}\in\{-1,1\}^{L \times N} Y^∈{−1,1}L×N).
• 计算思想: 每列每列算, 最后取平均.

function RankingLoss=Ranking_loss(Outputs,test_target)
%Computing the hamming loss
%Outputs: the predicted outputs of the classifier, the output of the ith instance for the jth class is stored in Outputs(j,i)
%test_target: the actual labels of the test instances, if the ith instance belong to the jth class, test_target(j,i)=1, otherwise test_target(j,i)=-1

    test_target((test_target == 0)) = -1;       % To avoid the illegal input

    [num_class,num_instance]=size(Outputs);
    temp_Outputs=[];
    temp_test_target=[];
    for i=1:num_instance
        temp=test_target(:,i);
        if((sum(temp)~=num_class)&(sum(temp)~=-num_class))
            temp_Outputs=[temp_Outputs,Outputs(:,i)];
            temp_test_target=[temp_test_target,temp];
        end
    end
    Outputs=temp_Outputs;
    test_target=temp_test_target;     
    [num_class,num_instance]=size(Outputs);
    
    Label=cell(num_instance,1);
    not_Label=cell(num_instance,1);
    Label_size=zeros(1,num_instance);
    for i=1:num_instance
        temp=test_target(:,i);
        Label_size(1,i)=sum(temp==ones(num_class,1));
        for j=1:num_class
            if(temp(j)==1)
                Label{i,1}=[Label{i,1},j];
            else
                not_Label{i,1}=[not_Label{i,1},j];
            end
        end
    end
    
    rankloss=0;
    for i=1:num_instance
        temp=0;
        for m=1:Label_size(i)
            for n=1:(num_class-Label_size(i))
                if(Outputs(Label{i,1}(m),i)<=Outputs(not_Label{i,1}(n),i))
                    temp=temp+1;
                end
            end
        end
        rl_binary(i)=temp/(m*n);
        rankloss=rankloss+temp/(m*n);
    end
    RankingLoss=rankloss/num_instance;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

1.1.2 节的 Hamming Loss

• 注意: 这里的两个变量同类型, 请在函数外完成阈值转换
• 参数信息: 第一个第二个都是 Y ∈ { 0 , 1 } L × N \mathbf{Y}\in\{0,1\}^{L \times N} Y∈{0,1}L×N (支持 Y ^ ∈ { − 1 , 1 } L × N \mathbf{\hat{Y}}\in\{-1,1\}^{L \times N} Y^∈{−1,1}L×N).
• 计算思想: 每列每列算, 最后取平均.

function HammingLoss=Hamming_loss(Pre_Labels,test_target)
%Computing the hamming loss
%Pre_Labels: the predicted labels of the classifier, if the ith instance belong to the jth class, Pre_Labels(j,i)=1, otherwise Pre_Labels(j,i)=-1
%test_target: the actual labels of the test instances, if the ith instance belong to the jth class, test_target(j,i)=1, otherwise test_target(j,i)=-1

    Pre_Labels((Pre_Labels == 0)) = -1;            % unification
    test_target((test_target == 0)) = -1;       

    [num_class,num_instance]=size(Pre_Labels);
    miss_pairs=sum(sum(Pre_Labels~=test_target));
    HammingLoss=miss_pairs/(num_class*num_instance);
1
2
3
4
5
6
7
8
9
10
11

1.3.4 节的 Average Precision

• 注意: 无.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{L\times N}$ (支持$\hat{\mathbf{Y}}\in [-1,1{]}^{L\times N}$), 第二个是 Y ∈ { 0 , 1 } L × N \mathbf{Y}\in\{0,1\}^{L \times N} Y∈{0,1}L×N (支持 Y ^ ∈ { − 1 , 1 } L × N \mathbf{\hat{Y}}\in\{-1,1\}^{L \times N} Y^∈{−1,1}L×N).
• 计算思想: 每列每列算, 最后取平均.

function Average_Precision=Average_precision(Outputs,test_target)
%Computing the average precision
%Outputs: the predicted outputs of the classifier, the output of the ith instance for the jth class is stored in Outputs(j,i)
%test_target: the actual labels of the test instances, if the ith instance belong to the jth class, test_target(j,i)=1, otherwise test_target(j,i)=-1

	test_target((test_target == 0)) = -1;       % To avoid the illegal input

    [num_class,num_instance]=size(Outputs);
    temp_Outputs=[];
    temp_test_target=[];
    for i=1:num_instance
        temp=test_target(:,i);
        if((sum(temp)~=num_class)&(sum(temp)~=-num_class))
            temp_Outputs=[temp_Outputs,Outputs(:,i)];
            temp_test_target=[temp_test_target,temp];
        end
    end
    Outputs=temp_Outputs;
    test_target=temp_test_target;     
    [num_class,num_instance]=size(Outputs);
    
    Label=cell(num_instance,1);
    not_Label=cell(num_instance,1);
    Label_size=zeros(1,num_instance);
    for i=1:num_instance
        temp=test_target(:,i);
        Label_size(1,i)=sum(temp==ones(num_class,1));
        for j=1:num_class
            if(temp(j)==1)
                Label{i,1}=[Label{i,1},j];
            else
                not_Label{i,1}=[not_Label{i,1},j];
            end
        end
    end
    
    aveprec=0;
    for i=1:num_instance
        temp=Outputs(:,i);
        [tempvalue,index]=sort(temp);
        indicator=zeros(1,num_class);
        for m=1:Label_size(i)
            [tempvalue,loc]=ismember(Label{i,1}(m),index);
            indicator(1,loc)=1;
        end
        summary=0;
        for m=1:Label_size(i)
            [tempvalue,loc]=ismember(Label{i,1}(m),index);
            summary=summary+sum(indicator(loc:num_class))/(num_class-loc+1);
        end
        ap_binary(i)=summary/Label_size(i);
        aveprec=aveprec+summary/Label_size(i);
    end
    Average_Precision=aveprec/num_instance;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

1.3.5 节的 NDCG

• 注意: 这里更准确是micro-NDCG因为我们压缩为一维了
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{L\times N}$ (支持$\hat{\mathbf{Y}}\in [-1,1{]}^{L\times N}$), 第二个是 Y ∈ { 0 , 1 } L × N \mathbf{Y}\in\{0,1\}^{L \times N} Y∈{0,1}L×N (支持 Y ^ ∈ { − 1 , 1 } L × N \mathbf{\hat{Y}}\in\{-1,1\}^{L \times N} Y^∈{−1,1}L×N).
• 计算思想: 压缩为一维, 直接计算一维向量之间关系.

function res = nDCG(Outputs, true_label)
% output is a predicted label matrix of L x N, where L represents the
% number of labels and N represents the number of instances. Its value is in the range of [0,1]
% test_targets is a predicted label matrix of L x N, where L represents the
% number of labels and N represents the number of instances. Its value can be {1,0} or {1,-1}

label_prob = reshape(Outputs,1,numel(Outputs));
true_label((true_label == -1)) = 0;
label_target = reshape(true_label,1,numel(true_label));

[~,temp] = sort(-label_prob);
allLabelSort = label_target(temp);
sortedTargetVector = sort(label_target);
sortedTargetVector = fliplr(sortedTargetVector);

dcg = 0;
for i = 1: numel(temp)
    rel = allLabelSort(i);
    denominator = log2(i + 1);
    dcg = dcg + (rel / denominator);
end

idcg = 0;    
for i = 1: numel(temp) 
    rel = sortedTargetVector(i);
    denominator = log2(i + 1);
    idcg = idcg + (rel / denominator);
end 

res = max(dcg / idcg);
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

1.3.6 节的 $\text{Peak-}{F}_1\text{ Score}$

• 注意: 无.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{L\times N}$ (支持$\hat{\mathbf{Y}}\in [-1,1{]}^{L\times N}$), 第二个是 Y ∈ { 0 , 1 } L × N \mathbf{Y}\in\{0,1\}^{L \times N} Y∈{0,1}L×N (支持 Y ^ ∈ { − 1 , 1 } L × N \mathbf{\hat{Y}}\in\{-1,1\}^{L \times N} Y^∈{−1,1}L×N).
• 计算思想: 压缩为一维, 直接计算一维向量之间关系.

function res = PeakF1Score(Outputs, true_label)
% output is a predicted label matrix of L x N, where L represents the
% number of labels and N represents the number of instances. Its value is in the range of [0,1]
% test_targets is a predicted label matrix of L x N, where L represents the
% number of labels and N represents the number of instances. Its value can be {1,0} or {1,-1}

% The matrix is compressed into 1 dimension
% The implementation of peak F1 here is based on the idea of micro-F1
label_prob = reshape(Outputs,1,numel(Outputs));
true_label((true_label == -1)) = 0;
label_target = reshape(true_label,1,numel(true_label));

[~,temp] = sort(-label_prob);
allLabelSort = label_target(temp);
tempF1 = zeros(1, numel(temp));
allTP = sum(label_target == 1);

for i = 1: numel(temp)
    sliceArray = allLabelSort(1:i); 
    TP = sum(sliceArray == 1);
    P = TP / (i);
    R = TP / allTP;
    if(P + R == 0)
        tempF1(i) = 0;
    else
        tempF1(i) = (2.0 * P * R) / (P + R);
    end
end
res = max(tempF1);
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1.2.2 节的micro-AUC

• 注意: 无.
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{L\times N}$ (支持$\hat{\mathbf{Y}}\in [-1,1{]}^{L\times N}$), 第二个是 Y ∈ { 0 , 1 } L × N \mathbf{Y}\in\{0,1\}^{L \times N} Y∈{0,1}L×N (支持 Y ^ ∈ { − 1 , 1 } L × N \mathbf{\hat{Y}}\in\{-1,1\}^{L \times N} Y^∈{−1,1}L×N).
• 计算思想: 压缩为一维, 直接计算一维向量之间关系.

function res = microAUC(Outputs, true_label)
% output is a predicted label matrix of L x N, where L represents the
% number of labels and N represents the number of instances. Its value is in the range of [0,1]
% test_targets is a predicted label matrix of L x N, where L represents the
% number of labels and N represents the number of instances. Its value can be {1,0} or {1,-1}

% The matrix is compressed into 1 dimension,
% then the internal information of the original single label can be ignored.
% so the global AUC can be calculated
label_prob = reshape(Outputs,1,numel(Outputs));
true_label((true_label == -1)) = 0;
label_target = reshape(true_label,1,numel(true_label));

[~,I]=sort(label_prob);
M=0;N=0;
for i=1:length(label_prob)
    if(label_target(i)==1)
        M=M+1;
    else
        N=N+1;
    end
end
sigma=0;
for i=M+N:-1:1
    if(label_target(I(i))==1)
        sigma=sigma+i;
    end
end
res=  (sigma-(M+1)*M/2)/(M*N);
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

1.2.1 节的macro-AUC

• 注意: 若某一行的真实目标标签全是0, 那么当前行的统计值+1; 若某一行的真实目标标签全是1, 那么当前行的统计值+1. 使用的内部函数perfcurve可能是matlab自带的 (若没有的同学可以自行百度下载)
• 参数信息: 第一个是$\hat{\mathbf{Y}}\in [0,1{]}^{N\times L}$ (支持$\hat{\mathbf{Y}}\in [-1,1{]}^{N\times L}$), 第二个是 Y ∈ { 0 , 1 } N × L \mathbf{Y}\in\{0,1\}^{N \times L} Y∈{0,1}N×L (支持 Y ^ ∈ { − 1 , 1 } N × L \mathbf{\hat{Y}}\in\{-1,1\}^{N \times L} Y^∈{−1,1}N×L).
• 计算思想: 每行每行算, 最后取平均.

function res = macroAUC(Outputs, true_label)
% output is a predicted label matrix of N x L, where L represents the
% number of labels and N represents the number of instances. Its value is in the range of [0,1]
% test_targets is a predicted label matrix of N x L, where L represents the
% number of labels and N represents the number of instances. Its value can be {1,0} or {1,-1}

true_label((true_label == -1)) = 0;
avgauc = 0;

for i=1:size(Outputs,2)
    y = Outputs(:,i);
    t = true_label(:,i);
    if mean(t) == 1 || mean(t) == 0
        if mean(t) == 1
            auc_tmp = 1;
        else
            auc_tmp = 0;
        end
    else
        [~,~,~,auc_tmp] = perfcurve(t,y,1);
    end
    avgauc = avgauc + auc_tmp/size(Outputs,2);
end

res = avgauc;
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.1 节的Precision@k (参考至相关算法源代码)
创建一个precision_k.m文件, 然后复制下面的代码, 但是请注意! 这个无法直接使用, 因为这里的sort_sparse_mat方法是源码中通过C++提前编译好的方法. 若在无环境的情况下是无法运行的.
这个代码中的score_mat是${\hat{\mathbf{Y}}}^{\top }$, true_mat是${\mathbf{Y}}^{\top }$, 他们都是形如$L\times N$的矩阵, 其中每列都是一个$L\times 1$的标签向量. 请注意, 这里使用的所有矩阵都是matlab自带的稀疏矩阵方法.
相关函数说明:

• 这里的sort_sparse_mat方法相当于公式中的$\mathrm{rank}()$, 它将标签向量中的数值换成了其值在排序的排名值, 若读者有需要可以自行实现.
• spones( )方法是将矩阵中所有非零元素都更改为$1$

function P = precision_k(score_mat,true_mat,K)
	P = helper(score_mat,true_mat,K);
end

function P = helper(score_mat,true_mat,K)
	num_inst = size(score_mat,2);
	num_lbl = size(score_mat,1);

	P = zeros(K,1);
	rank_mat = sort_sparse_mat(score_mat);  % 具体的值更改为这个值在这一列的"排序值"

	for k=1:K
		mat = rank_mat;
		mat(rank_mat>k) = 0;    			% 把低于阈值排名的排名设置为0
		mat = spones(mat);      			% 将幸存的数值都改为1
		mat = mat.*true_mat;    			% 将预测错的变为0
		num = sum(mat,1);       			% 按照列求和

		P(k) = mean(num/k);
	end
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.2 节的NDCG@k (参考至相关算法源代码)
创建一个nDCG_k.m文件, 然后复制下面的代码, 但是请注意! 这个无法直接使用, 因为这里的sort_sparse_mat方法是源码中通过C++提前编译好的方法. 若在无环境的情况下是无法运行的.
这个代码中的score_mat是${\hat{\mathbf{Y}}}^{\top }$, true_mat是${\mathbf{Y}}^{\top }$, 他们都是形如$L\times N$的矩阵, 其中每列都是一个$L\times 1$的标签向量. 请注意, 这里使用的所有矩阵都是matlab自带的稀疏矩阵方法.
相关函数说明:

• 这里的sort_sparse_mat方法相当于公式中的$\mathrm{rank}()$, 它将标签向量中的数值换成了其值在排序的排名值, 若读者有需要可以自行实现.
• spones( )方法是将矩阵中所有非零元素都更改为$1$
• sparse( )是构建稀疏矩阵的方法, X是非零点的纵坐标数组, Y是非零点的横坐标数组, V是非零值, 它们是一一对应的. 后续num_lbl与num_inst是稀疏矩阵的最大行数和列数. ($L\times N=\text{num\_lbl}\times \text{num\_inst}$)
• cum_wts()用于累加求和, cum_wts([1,1,1]) -> [1,2,3], cum_wts([2,7,8]) -> [2,9,17], 代码中他被用来算IDCG

function N = nDCG_k(score_mat,true_mat,K)
	N = helper(score_mat,true_mat,K);
end

function P = helper(score_mat,true_mat,K)
	num_inst = size(score_mat,2);
	num_lbl = size(score_mat,1);
    

	P = zeros(K,1);
	wts = 1./log2((1:num_lbl)+1)';              
	cum_wts = cumsum(wts);                      % 计算每个IDCG

	rank_mat = sort_sparse_mat(score_mat);      % 然后返回每个排序值的位置
	[X,Y,V] = find(rank_mat);                   % 找出rank_mat中非零元素所在的行和列, 并且分别存储在X和Y中, 并将具体非零的值放在V里面
	V = 1./log2(V+1);                           % sort_sparse_mat操作后, 当前列的某个V值体现是原值此向量的中的排名, 符合公式中l的定义
	coeff_mat = sparse(X,Y,V,num_lbl,num_inst); % 将原预测稀疏矩阵转变为单DCG的稀疏矩阵

	for k=1:K
		mat = coeff_mat;
		mat(rank_mat>k) = 0;                    % 把排序没靠在前k的数据改为0, 其余靠在k前的数据的具体的值保持原来的值(1./log2(V+1)的结果)
		mat = mat.*true_mat;                    % 把那些预测错的归零, 这里是haty->y的映射
		num = sum(mat,1);                       % 得到每个列的DCG@k值 (求和过程中若预测错了, + 0)

        % 下面是处理IDCG
		count = sum(true_mat,1);                % 求原Y的每列的||y||_0           
		count = min(count,k);                   % min(k, ||y||_0)
		count(count==0) = 1;                    % 为了避免除零, 对于空标签向量, 设置基础值l=1, 保守认为有一个标签
		den = cum_wts(count)';                  % 得到每一列的IDCG
		
		P(k) = mean(num./den);                  % 每一列求NDCG
	end
    
end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

4 后记

这个文章本质是个记录用, 当然也包含我的一些理解.
因为文本量太大, 而且中途还修改过一次, 因此文章中可能存在部分错误, 欢迎指正!