【技術分析】六：搜索排序—指標介紹與選擇

• 2019 年 11 月 4 日
• 筆記

本文原作者：彭江軍，經授權後發布。

導語:

這一節將著重說明，怎樣定位線上和線下指標之間的差異，對齊線下和線上指標，得到一個大致的關係。優化線下什麼指標，對應的能帶來線上什麼指標的提升。這樣可以避免模型上線的風險。因此也是指標的分析也是十分重要的一個問題。

1：指標介紹

在該系列文章1中列舉了幾種常見的指標，在這裡顯示的給出分析和計算的過程。

1.1：NDCG

全稱: Normalized discounted cumulative gain。 該衡量指標通過這種歸一化的折扣的方式來保證頭部的排序的準確性。

我們從NDCG的計算式子說起（沒辦法還是得用公式）：

這個式子可以拆分成三個部分，CG，DCG，NDCG。

先說CG，代表著Cumulating Gain. 這個一般會配合著位置來用。因為不限定位置的話，對一個排序不管怎麼排，它的CG都是一樣的。如下圖所示：

假設分值在0.8以上label標記為2, 0.5至0.8記為1，0-0.5記為0。(這裡是不是看的很奇怪，一般分值在0-1之間都是以0.5作為閾值，將label分成0,1兩類。其實閾值的選取的不同，最終分出來正負樣本的比例就不同，而AUC就避免了閾值的選取，後面會講到。這裡只是我自己構造的一個例子，方便講解NDCG的概念)

例子1:一次搜索排序下面共有5個doc,其真實label和預測的label如上所示：

若是算前5個的CG。

Ground truth 的順序為：Doc_1,Doc_2,Doc_5,Doc_4,Doc_3

Predict 的順序為：Doc_2,Doc_1,Doc_5,Doc_4,Doc_3

計算可得：

ground truth：CG = (2^1-1)+(2^2-1)+ (2^1-1)+(2^0-1)+ (2^0-1)=5

Predict：CG=(2^1-1)+(2^2-1)+ (2^1-1)+(2^0-1)+ (2^0-1)=5

這裡做三點說明：

1：這裡的每個樣本的gain 的計算是採用了指數的形式，主要為了拉開label 之間的差異，我們當然也可以直接用label值作為gain 加和得到CG。

2：算CG的時候，是以ground truth 的label來計算，所以雖然predict doc_1和doc_2預測反了，但是在算CG的時候仍以ground truth 的label來計算的。

3：CG配合著位置使用的時候，就能體現出來差異，如

Ground truth : CG@1=2^2-1=3

Predict :CG@1=2^1-1=1

這就是Ground 比predict 要好（這個顯然，都是Groundtruth 了。）

接下來在說DCG，相比CG而言，多了D。記得在第一節中說到NDCG更注重對頭部的評估，就是根據這個D來的。

為了讓label大的數值排在前面，或者說為了懲罰大的數值label排在後面，DCG對位置做了相應的discount,也就是讓不同位置的discount 不一樣，位次越往後懲罰（discount）越大。

這裡可以計算出：

Predict:  DCG = (2^1-1)/1+(2^2-1)/1.58+ (2^1-1)/2+(2^1-1)/2.32+ (2^0-1)/2.58=1.551

Groundtruth: DCG = (2^2-1)/1+(2^1-1)/1.58+ (2^1-1)/2+(2^0-1)/2.32+ (2^0-1)/2.58=3.148

這裡做三點說明：

1：每個gain後的除數是上圖公式的log(i+1)加上位次的數值

2：之所以計算Groundtruth 的DCG，是為了後面的NDCG服務

最後來到NDCG，因為只算DCG的話，長度比較長的排列列表是明顯要佔優，因為累積更多，所以需要除以Groundtruth的DCG。來進行歸一化

於是，預測的排序結果的NDCG值最後就：

NDCG=1.551/3.1486=0.4925

1.2：MAP

全稱為Mean Average Precision。MAP是每個主題的平均準確率的平均值。

MAP 是反映系統在全部相關文檔上性能的單值指標。系統檢索出來的相關文檔越靠前(rank 越高)，MAP就可能越高。如果系統沒有返回相關文檔，則準確率默認為0。

例子：一個主題1：有四個相關的doc，分別被排在了1，2，4，7位置。則MAP=(1/1+2/2+3/4+4/7)/4=0.83。

1.3：MRR

全稱為Mean Reciprocal Rank。是把標準答案在被評價系統給出結果中的排序取倒數作為它的準確度,對於top的排序做一個discount,保證頭部。

例子：一個主題1：有四個相關的doc，分別被排在了1，2，4，7位置。則MRR=(1/1+1/2+1/4+1/7)/4=0.475。

1.4: AUC

AUC 其實是一個極其常用的評價指標，甚至可以單獨拿出來進行闡述。我們為了文章的結構的完整性，把它放在了搜索排序評價指標下面來進行闡述。

AUC本身不關注是不是預測的小於某個閾值，它本身就是用來解決閾值的，所以AUC在下圖的程式碼中即使預測的值都大於0.5依舊可以預測出AUC值。和選取某個閾值無關。

下面來描述一下AUC。

AUC：全稱Area Under Curve，這裡的Curve 指的是ROC曲線。

ROC曲線：橫坐標表示偽陽性率（false positive rate）y軸是真陽性率（true positive rate)。計算不同的閾值下的(x,y)所組成的連線。因此ROC曲線可以轉化成隨機抽出一對樣本（一個正樣本，一個負樣本），然後用訓練得到的分類器來對這兩個樣本進行預測，預測得到正樣本的概率大於負樣本概率的概率。

因此，結合AUC和ROC的定義，我們可以得到AUC解決了傳統的計算準確度(accuracy)時，必須先設定閾值，將概率轉成類別，才能計算accuracy的問題。因為當樣本均勻的時候，閾值很好確定，對於2分類問題而言，選0.5就好；但是當樣本不均衡的時候，這個閾值就很難去界定，需要手動選擇，就意味著風險。而AUC直接把所有的閾值挨個試一遍，生成ROC曲線。因此AUC更加適合對有偏樣本的度量。

實際上，我們計算的時候不是直接將所有的閾值都試一遍，計算ROC下面的面積，而是去計算構造正負樣本對，計算正負樣本對預測正確的個數佔總的正負樣本對的總數的比值。轉化為公式為：

統計ROC曲線計算AUC和這種方式計算的等價性可參看：https://blog.csdn.net/chjjunking/article/details/5933105。

例子：真實的label和預測的label 如下所示：

畫出真值表如下：

挨個設定閾值，畫出ROC曲線

其實我們可以直接通過構造正負樣本對方式來計算AUC。

由將樣本編號為：doc1-doc8，doc1-dc4為正樣本，doc5-doc8為負樣本。

正負樣本對有4*4=16個，統計正負樣本對裡面預測對的個數為10個，可得到為AUC=0.625。

2：線上線下指標對齊分析

下面以最近做的一個項目進行分析機器學習常見的一個預測線下線上對不齊的問題。

具體項目的背景及機器學習建模見：

2.1：問題的產生

在做模型的過程中發現線上指標和線下對不齊的問題。某個平台下的兩個模型的實驗結果如下圖所示：

這裡，計算NDCG，MAP，MRR的時候我們以0-3（無點擊，短點擊，中點擊，長點擊）四類label來計算。計算長點擊的AUC和GAUC的時，label是按照有無長點擊進行計算的；同理，計算點擊的AUC和GAUC的時，label是按照有無點擊（裡面包含短中長點擊）進行計算的。線上的指標CTR代表點擊率，CVR代表轉化率，LCVR代表長轉化率。不同的前綴是出於不同的對比對比設置的，但都是立足於長轉化率的。

可以發現在計算4類label計算的時候，發現有下面兩個現象：

1：模型1的MAP，NDCG，MRR均高於模型2，但是並不能長轉化率的提升，線上線下對不齊。

2：從AUC的數值上來看，模型1不管是在長點擊的AUC還是點擊的AUC都遠遠的高於模型二，為什麼上線後模型1的長點擊並沒有提升。

2.2：問題的定位

定位了很久，後來想到用模型預測的平均位置來解釋。如下圖所示：

針對2.1裡面的問題1：我們發現模型1會傾向於將整體的點擊預測的更好（對應的圖中有點擊的預測平均位），而對於長點擊的預測平均位確實低於模型2的。所以從預測的平均位置上而言，可以看到模型1對於點擊的預測效果更好，因此點擊的AUC高。這裡是不是以為預測的平均位置也可以作為一個衡量排序好壞的指標（我覺得其實是可以的，但是這個指標是離散的，從優化的角度並不好優化，但是離線評估時候應該是可以用的）。

這個時候我們再結合樣本的分布圖來看。

會發現在我們構造的四類樣本中，長點擊的佔比佔總體點擊的並不高，從而導致一個模型對於點擊的預測效果好，那麼整體的NDCG值就會高，這和指標圖中NDCG，MAP，MRR等指標和點擊的AUC保持一致可以看出來。

問題1至此可以得到解答，因為label的構造中，長點擊的總量不佔優，導致NDCG值並不能很好反應這種label設置的長點擊的效果。

問題2：在前面的表中，我一直沒有談有一個指標GAUC的。在琢磨好久之後，才找到了GAUC的。後面在準備寫這系列文章的時候，發現公司已經有好幾篇博文中已經提到並且用了GAUC作為評價的指標。

在上面的圖中，我們會發現GAUC是可以和線上保持一致的，而AUC是失效的。這就回答了第二個問題。接下來將花一個小段詳細介紹GAUC和AUC的區別。

3：GAUC

GAUC全稱為Group AUC。它相對於AUC的改變是不在算整體的AUC，而是計算每一個Group下的AUC然後計算AUC的均值。

CAUC的公式如下所示：

在機器學習演算法中，很多情況我們都是把AUC當成最常用的一個評價指標，而AUC反映整體樣本的排序能力，但是有時候AUC這個指標可能並不能完全說明問題，有可能AUC並不能真正反映模型的好壞，

以CTR預估演算法(排序演算法一般把這個作為一個很重要的指標)為例，把用戶點擊的樣本當作正樣本，沒有點擊的樣本當作負樣本，把這個任務當成一個二分類進行處理，最後模型輸出的是樣本是否被點擊的概率。

將所有的用戶不同時刻的樣本混合到一起，來計算模型對用戶點擊的正樣本來負樣本預測的正確性得到AUC值，並不能很好的適配單詞搜索下的排序效果，因為可能這個搜索用戶展示的結果就只是A(點擊),B,C, 下次搜索的結果展示的是D,E(點擊),F。將這兩次搜索展示的結果融合到一起來預測，可能得到AUC不能很好的反應單次搜索的效果，因此在單次的搜索結果中用戶當時看到只是那一次搜索下面的結果，其他次搜索的結果的排序順序不應該應該這次排序的結果的評估的。

給出一個具體的例子：

排序的結果為：

在這種情況下，模型A，B對於甲乙兩個用戶的單次搜索下的體驗是沒有差別的。因為在各自的搜索情況下，他們點擊的doc都是排在沒有點擊的前面的。而在AUC下差異就會很大。

於是最終選擇用GAUC作為評估優化的指標。

至於GAUC的上漲和線上指標上漲的定量關係，還得花比較長的時間的觀察。