周志華西瓜書習題2.5詳細解答

03-06

證明等式： $AUC=1-l_{rank}$

在證明這個式子之前先把幾個概念捋一捋，方便後面討論。

① 混淆矩陣

② 真正例率（TPR）和假正正例率（FPR）

$TPR=frac{TP}{TP+FN}$

$FPR=frac{FP}{TN+FP}$

③ ROC曲線畫法

因為在實際任務中常常是利用有限個樣例來繪製ROC曲線，此時只能獲得有限個（TPR,FPR）坐標時，就只能繪製一個不光滑的ROC曲線。給定 $m^+$ 個正例和 $m^-$ 個反例，所以有 $TP+FN=m^+$ ， $FP+TN=m^-$ 。訓練出來的學習器可以得到每個樣例預測為正例的概率score，根據這個概率，將所有樣例按照score降序排列，即最可能為正例的樣例排在最前面。判斷一個樣例為正例還是反例，需要將score與一個分類閾值作比較，若大於這個閾值則為正例，反之為反例。首先將分類閾值設置最大，即把所有樣例均預測為反例，此時的TPR和FPR均為0，即為ROC曲線的（0,0）點。然後，將分類閾值依次設為剛剛排序好樣例的score，即依次將每個樣例劃分為正例。設ROC曲線上前一個點坐標為 $ext{（}x,y ext{）}$ ，當前若為真正例，則對應ROC曲線上的點為 $ext{（}x,y+frac{1}{m^+} ext{）}$ ；當前若為假正例，則對應點為 $ext{（}x+frac{1}{m^-},y ext{）}$ ，然後用線段連接相鄰點即可。（這裡可能有點抽象，後文將舉一個例子來畫一個ROC曲線就很清楚了）

根據ROC曲線的畫法，可以估算出AUC（ROC曲線下區域面積）的公式：

$AUC=frac{1}{2}sum_{i=1}^m{left( x_{i+1}-x_i ight) left( y_i+y_{i+1} ight)}$

這實際上就是各個小梯形的面積和。

然後西瓜書35面又給出了一個排序「損失」 $l_{rank}$ 的定義，其中 $D^+ ext{，}D^-$ 分別表示正反例集合， $ext{II}left( cdot ight)$ 表示 $cdot$ 為真時， $ext{II}left( cdot ight)$ 等於1，為假時等於0

$l_{rank}=frac{1}{m^+m^-}sum_{x^+in D^+}{sum_{x^-in D^-}{left( ext{II}left( fleft( x^+ ight) <fleft( x^- ight) ight) +frac{1}{2} ext{II}left( fleft( x^+ ight) =fleft( x^- ight) ight) ight)}}$

並解釋說，這就是考慮每一對正例和反例，若正例的score小於反例，則記一個「罰分」，若相等，則記0.5個「罰分」，而且 $l_{rank}$ 就是ROC曲線之上的面積，所以有我們要證明的式子

$AUC=1-l_{rank}$

好，下面我們舉一個實際例子來證明一下這個等式。假設我現在有8個樣例，其中正例5個，反例3個，即 $m^+=5$ ， $m^-=3$ 。通過學習器對每個樣例進行預測，得到score,並排序，其中class為樣例實際屬性（正例P還是反例N）

現在根據這個表來繪製ROC曲線

0) 將分類閾值設為最大，即所有閾值都為反例，有

$FPR=frac{FP}{FP+TN}=frac{FP}{m^-}=frac{0}{3}=0$ ， $TPR=frac{TP}{TP+FN}=frac{TP}{m^+}=frac{0}{5}=0$ ，得到點（0,0）

1) 將分類閾值設為0.9，有

$FPR=frac{0}{3}=0$ , $TPR=frac{1}{5}=0.2$ ,得到點（0,0.2）

2) 將分類閾值設為0.8，有

$FPR=frac{0}{3}=0$ , $TPR=frac{2}{5}=0.4$ ,得到點（0,0.4）

3) 將分類閾值設為0.7，有

$FPR=frac{1}{3}$ , $TPR=frac{3}{5}=0.6$ ,得到點（1/3,0.6）

4) 將分類閾值設為0.7，有

$FPR=frac{1}{3}$ , $TPR=frac{3}{5}=0.6$ ,得到點（1/3,0.6）重疊點

5) 將分類閾值設為0.6，有

$FPR=frac{1}{3}$ , $TPR=frac{4}{5}=0.8$ ,得到點（1/3,0.8）

6) 將分類閾值設為0.5，有

$FPR=frac{2}{3}$ , $TPR=frac{4}{5}=0.8$ ,得到點（2/3,0.8）

7) 將分類閾值設為0.4，有

$FPR=frac{2}{3}$ , $TPR=frac{5}{5}=1$ ,得到點（2/3,1）

8) 將分類閾值設為0.3，有

$FPR=frac{3}{3}=1$ , $TPR=frac{5}{5}=1$ ,得到點（1,1）

如圖，就得到ROC曲線，陰影部分的面積即為AUC的值

那麼問題來了， $l_{rank}$ 怎麼和面積聯繫起來，進而得到要證的等式 $AUC=1-l_{rank}$ ，再看一眼 $l_{rank}$ 的表達式： $l_{rank}=frac{1}{m^+m^-}sum_{x^+in D^+}{sum_{x^-in D^-}{left( ext{II}left( fleft( x^+ ight) <fleft( x^- ight) ight) +frac{1}{2} ext{II}left( fleft( x^+ ight) =fleft( x^- ight) ight) ight)}}$ ，其中 $frac{1}{m^+m^-}$ 就等於上圖一個小單元格的面積，首先思考一下，什麼情況下AUC會最大？那就是當所有5個正例全排在前面的時候，AUC最大為1，這也反應出我們的學習器預測效果很好，正例預測對的概率很高。而實際情況並不是如此，比如排在第三位的是一個反例，出現這種情況時，在ROC曲線中就表現為下一個坐標點向x軸的正方向移動 $frac{1}{m^-}=frac{1}{3}$ 個距離，這也是前面講到的 $ext{（}x+frac{1}{m^-},y ext{）}$ 。注意這裡第三位和第四位的Score都是0.7，這也就是 $l_{rank}$ 公式里的 $fleft( x^+ ight) =fleft( x^- ight)$ 情況，為什麼前面乘了一個1/2呢？從圖中應該就能明白了吧，因為當把0.7作為分類閾值時，同時把一個正例和一個反例都當成了正例，x軸和y軸就都移動了一個單位，所以連起來以後就只是半個小單元，面積就是 $frac{1}{2}frac{1}{m^+m^-}$ 。對於這個排在正例前面的反例，也就是第三位的這個反例， $ext{II}left( fleft( x^+ ight) <fleft( x^- ight) ight) =2$ ， $ext{II}left( fleft( x^+ ight) =fleft( x^- ight) ight) =1$ ,所以對應於下圖中紅色區域的面積。另外還一個排在正例前面的反例（第六位），就對應了下圖白色區域這塊面積，所以加起來就是 $l_{rank}$ ，整個區域的面積為1，所以 $AUC=1-l_{rank}$ 。這個例子就充分說明了 $l_{rank}$ 就代表了ROC曲線上方的面積，推而廣之，就可以推廣 $AUC=1-l_{rank}$ 這個關係式了。