极限多标签分类-评价指标

杨利霞

+ R5 W' V8 d8 y5 }6 J2 d$ e8 A极限多标签分类-评价指标

极限多标签分类-评价指标
" n* R9 P+ a: n$ w5 z, [. J2 WReferences:
8 `8 t" h" p2 b" mhttp://manikvarma.org/downloads/XC/XMLRepository.html
https://blog.csdn.net/minfanphd/article/details/126737848?spm=1001.2014.3001.5502
5 D6 J9 c  j  vhttps://en.wikipedia.org/wiki/Discounted_cumulative_gain
. B5 A5 ]. R% K
什么是极限多标签分类 (eXtreme multi-label Classification (XC))？
$ ^" W$ N- _  h' S2 d标签数非常多（Million），典型的就是BoW数据标签。
. E+ o" d$ Y1 ]0 E3 K极限多标签分类的典型应用：Image Caption（头大）。不过在Image Caption里面，Word之间存在序关系。XC可以看成是Image Caption的一个关键阶段，它能够选出与当前Image最相关的BoW。
（上述都是靠过往经验吹的，近期没调研）。

先来看一下评价指标：
, @( M0 b- A9 O1 \: t: U; B由于标签数非常多，且GroundTruth又非常小，因此通常意义上的分类精度、召回(多标签分类用macro或者micro的acc或者recall)等指标不work。
$ ^$ t0 }) B8 \这些评价指标通常考虑了head/tail labels，也就是高频标签和低频标签；以及reciprocal pairs（互惠对）去除?
" H" |5 M+ {- y4 T# t3 Q( R6 O互惠对似乎？是指彼此相关的标签对，比如针对一个数据点，如果预测了标签A，如果标签B和A相关，那可以自然预测B。
为了避免这种trival prediction, reciprocal pairs应该被去除。

(1) Top-k kk Performance:
(Precision@ k ) P @ k : = 1 k ∑ l ∈ rank k ( y ^ ) y l \text{(Precision@$k$)}\text{P}@k := \frac{1}{k}\sum_{l \in \text{rank}_k (\hat{\mathbf{y}})} \mathbf{y}_l
(Precision@k)P@k:=
k
9 B0 X; p6 s+ J4 g1 }0 t1
: N8 G+ G  ?+ ^  C​
6 d! f0 V/ @" |
l∈rank
k
​
* R# K, C( I! v4 b2 m, C (
y
^
8 l' A% G  M! C0 T​
)
∑
​
y
l
+ x+ R6 }. }" ]7 r2 q​
8 Z- o6 X! \* m9 j  G8 c; t
0 ]% y' p, v7 |
(Discounted Cumulative Gain (贴现累积收益))DCG @ k : = ∑ l ∈ rank k ( y ^ ) y l log ⁡ ( l + 1 ) \text{(Discounted Cumulative Gain (贴现累积收益))} \text{DCG}@k := \sum_{l \in \text{rank}_k(\hat{\mathbf{y}})} \frac{\mathbf{y}_l}{\log(l+1)}
(Discounted Cumulative Gain (贴现累积收益))DCG@k:=
) Y7 o$ n  {. {l∈rank
k
' }5 ~9 L1 K8 }( i​
(
! Q  s+ G0 T1 u0 n1 L2 Ty
1 p# T8 b, ]) s9 f^
( ?) i- I( `# g3 O  `' j3 G& k​
)
∑
9 t- E5 P2 k0 c) V5 k​

$ W; D% l8 W) r! e) \log(l+1)
/ v% A& k) U; B' ^5 @( _; Xy
l
) z* k! e+ v/ t​

, w5 V+ X) D- h​


; x: y% Z* |$ U) R/ `" f/ O, i6 @8 ?(Normalized DCG)nDCG @ k : = DCG@ k ∑ l = 1 min ⁡ ( k , ∣ ∣ y ∣ ∣ 0 ) 1 log ⁡ ( l + 1 ) \text{(Normalized DCG)} \text{nDCG}@k := \frac{\text{DCG@$k$}}{\sum_{l=1}^{\min(k,||\mathbf{y}||_0)} \frac{1}{\log(l+1)}}
3 c. H: @) `# t! l) M(Normalized DCG)nDCG@k:=
∑
l=1
min(k,∣∣y∣∣
2 Z8 _& ~, W% Q6 w8 V. R) S' h! n, s0
​
$ f& G* L2 }1 p )
+ o0 {* y1 U+ c8 g​

log(l+1)
7 G9 i% R# A4 [% W1
0 T: M; B3 v% K3 z# R/ n4 a9 \​
+ A" Y3 }) P: o, o9 t7 H
" T9 ~0 ~2 J7 v% H7 w2 w/ gDCG@k
​
: w( l" ?* p. p6 m* T

5 S* A! z: l% U, ~2 Prank k ( y ) \text{rank}_k(\mathbf{y})rank
7 V+ o! h3 V4 ck
; y; G/ i/ `% @& a5 a" E​
+ z0 R7 {" Z* J3 h (y)为逆序排列y \mathbf{y}y的前k个下标。Note: DCG公式里的分母实际上不是l，而是from 1 to k.
8 t1 h/ ?# M+ r3 S
- m. T: H/ n3 r5 l9 [8 n, F8 j靠后的标签按照对数比例地减小，说白了就是加权。至于为什么用log？两个事实：1. 平滑缩减; 2. Wang等人提供了理论支撑说明了log缩减方式的合理性。The authors show that for every pair of substantially different ranking functions, the nDCG can decide which one is better in a consistent manner. （看不懂，暂时不管）

(2) Top-k kk Propensity-score:

2 R, ~$ T9 U. u" \+ Q有些数据集包含一些频度很高的标签（通常称之为head labels），可以通过简单地重复预测头部标签来实现高的P @ k \text{P}@kP@k。Propensity-score可以检查这种微不足道的行为。
. I/ A$ ~6 g( B3 t8 H7 i1 _( Propensity-score Precision )  PSP @ k : = 1 k ∑ l ∈ rank k ( y ^ ) y l p l (\text{Propensity-score Precision}) \text{ PSP}@k := \frac{1}{k} \sum_{l\in \text{rank}_k(\hat{\mathbf{y}})} \frac{\mathbf{y}_l}{p_l}
(Propensity-score Precision) PSP@k:=
k
& w, \5 C# X0 \( C3 I" e* R1
# {: b9 q/ e8 u7 m% o6 ], ^​

l∈rank
k
/ p, H* d2 u& c​
(
y
% A& [1 k) I# @9 ^& N^
​
% {* @% T7 X" I( ~3 q )
∑
- l* n2 V) A2 d0 Z2 d3 s0 O​
/ i8 ~% Z9 i% S. i" F
p
l
/ C- O: P/ d/ V1 ~+ P) R​
$ t; m& a( ^- Y+ q8 E5 c$ l5 _7 O
y
: ]- k6 v1 V3 P$ b0 g, @l
( r& r! e8 m2 k7 @; @! p​

  g7 E4 Z1 B. h4 ]2 P6 A​
. @" h4 z  R, E! K( d8 }& q

7 X4 e6 g! r  Y6 i; T3 VPSDCG @ k : = ∑ l ∈ rank k ( y ^ ) y l p l log ⁡ ( l + 1 ) \text{PSDCG}@k := \sum_{l \in \text{rank}_k(\hat{\mathbf{y}})} \frac{\mathbf{y}_l}{p_l\log(l+1)}
PSDCG@k:=
l∈rank
) {0 `/ v  J& m: E# M" qk
. L; w9 w" b0 @% i$ O( F! S2 D% v​
(
y
8 x5 c$ X6 ~5 w^
​
)
6 j" ]1 r! A  P" y# D2 |) }; k∑
, V- I6 I" u5 B7 j. H1 g+ ~3 b5 u​

) l8 u( ~" a! C+ lp
1 m4 G) t, h; s" Q: j- I/ yl
​
: v( ]+ o" h* v/ Q% h! I0 r log(l+1)
y
' X5 y1 ]% e! R  X: Zl
​

​
- D+ x3 a' }  R4 k; S9 M, A+ P

PSnDCG @ k : = PSDCG@ k ∑ l = 1 k 1 log ⁡ ( l + 1 ) \text{PSnDCG}@k := \frac{\text{PSDCG@$k$}}{\sum_{l=1}^{k} \frac{1}{\log(l+1)}}
PSnDCG@k:=
∑
l=1
+ y, H/ ?# S$ gk
/ D$ {7 j) D" ?% Z​

* h8 p9 J% S8 n0 S$ Xlog(l+1)
1
) I2 I. G( A& B, @( Y+ |! h% G- M​

' F9 M# Y4 \/ t0 N) qPSDCG@k
  I% D) z+ F/ |/ U, D( y" A( B" m​

; p6 }5 {  f3 C$ c
  x/ ?- U1 x0 _6 {) S4 [其中p l p_lp
! Y5 A5 J# X) T0 ~  K& ml
​
8 x8 Q  O% U3 Q- f7 e, j- D, }/ J 为标签l ll的propensity-score，使得这种度量在missing label方面无偏差(unbiased)。
( c# L6 k- q7 d# i, u6 K( cPropensity-score强调在tail labels上的表现，而对预测head labels提供微弱的奖励。
- u. a5 B0 U7 S7 A. _% g————————————————
4 \% z. D. T$ W+ O版权声明：本文为CSDN博主「摆烂的-白兰地」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
# \  T; \9 T$ o* x7 ~" D原文链接：https://blog.csdn.net/wuyanxue/article/details/126805190
! V! F; u+ t, n5 D7 }
+ X3 }* R) ^2 Z5 Q( ~
: B! G$ N, L9 ]