排序評估名額——NDCG和MAP

在搜尋和推薦任務中，系統常傳回一個item清單。如何衡量這個傳回的清單是否優秀呢？

例如，當我們檢索【推薦排序】，網頁傳回了與推薦排序相關的連結清單。清單可能會是[A,B,C,G,D,E,F],也可能是[C,F,A,E,D]，現在問題來了，當系統傳回這些清單時，怎麼評價哪個清單更好？

這就引出了這篇文章要介紹的兩個評價名額——NDCG和MAP，這兩個名額都是用來評估排序結果的。

1. NDCG

NDCG的全稱是：Normalized Discounted Cumulative Gain(歸一化折損累計增益）學習NDCG最好按照G-CG-DCG-NDCG這個順序來學習。

• Gain：表示一個清單中所有item的相關性分數。rel(i)表示item(i)相關性得分。

  G a i n = r e l ( i ) Gain = rel(i) Gain=rel(i)

• Cumulative Gain：表示對K個item的Gain進行累加。

  C G k = ∑ i = 1 k r e l ( i ) CG_k = \sum_{i=1}^krel(i) CGk​=∑i=1k​rel(i)

  CG隻是單純累加相關性，不考慮位置資訊。

  如果傳回一個list_1= [A,B,C,D,E]，那list_1的CG為0.5+0.9+0.3+0.6+0.1=2.4

  如果傳回一個list_2=[D,A,E,C,B]，那list_2的CG為0.6+0.5+0.1+0.3+0.9=2.4

  是以，順序不影響CG得分。如果我們想評估不同順序的影響，就需要使用另一個名額DCG來評估。

• Discounted Cumulative Gain: 考慮排序順序的因素，使得排名靠前的item增益更高，對排名靠後的item進行折損。

  CG與順序無關，而DCG評估了順序的影響。DCG的思想是：list中item的順序很重要，不同位置的貢獻不同，一般來說，排在前面的item影響更大，排在後面的item影響較小。（例如一個傳回的網頁，肯定是排在前面的item會有更多人點選）。是以，相對CG來說，DCG使排在前面的item增加其影響，排在後面的item減弱其影響。

  D C G k = ∑ i = 1 k r e l ( i ) l o g 2 ( i + 1 ) DCG_k = \sum_{i = 1}^k\frac{rel(i)}{log_2(i+1)} DCGk​=∑i=1k​log2​(i+1)rel(i)​

  怎麼實作這個思想呢？DCG在CG的基礎上，給每個item的相關性比上log2(i+1)，i越大，log2(i+1)的值越大，相當于給每個item的相關性打個折扣，item越靠後，折扣越大。

  還是上面那個例子：

  list_1=[A,B,C,D,E], 其對應計算如下：

  i	rel(i)	log(i+1)	rel(i)/log(i+1)
  1=A	0.5	1	0.5
  2=B	0.9	1.59	0.57
  3=C	0.3	2	0.15
  4=D	0.6	2.32	0.26
  5=E	0.1	2.59	0.04

  list_1的 DCG_1= 0.5+0.57+0.15+0.26+0.04=1.52

  list_2=[D,A,E,C,B]，其對應計算如下：

  i	rel(i)	log(i+1)	rel(i)/log(i+1)
  1=D	0.6	1	0.6
  2=A	0.5	1.59	0.31
  3=E	0.1	2	0.05
  4=C	0.3	2.32	0.13
  5=B	0.9	2.59	0.35

  list_2的 DCG_2= 0.6+0.31+0.05+0.13+0.35=1.44

  DCG_1 > DCG_2, 是以在這個例子裡list_1優于list_2。

  到這裡，我們可以知道，使用DCG方法就可以對不同的list進行評估，那為什麼後面還有一個NDCG呢？

• NDCG(Normalized DCG): 歸一化折損累計增益

  在NDCG之前，先了解一些IDGC(ideal DCG)–理想的DCG，IDCG的依據是：是根據rel(i)降序排列，即排列到最好狀态。算出最好排列的DCG，就是IDCG。

  IDCG=最好排列的DCG

  對于上述的例子，按照rel(i)進行降序排列的最好狀态為list_best=[B,D,A,C,E]

  i	rel(i)	log(i+1)	rel(i)/log(i+1)
  1=B	0.9	1	0.9
  2=D	0.6	1.59	0.38
  3=A	0.5	2	0.25
  4=C	0.3	2.32	0.13
  5=E	0.1	2.59	0.04

  IDCG = list_best的DCG_best = 0.9+0.38+0.25+0.13+0.04=1.7 (理所當然，IDCG>DCG_1和DCG_2)

  因為不同query的搜尋結果有多有少，是以不同query的DCG值就沒有辦法來做對比。是以提出NDCG。

  N D C G = D C G I D C G NDCG = \frac{DCG}{IDCG} NDCG=IDCGDCG​

  是以NDGC使用DCG/IDCG來表示，這樣的話，NDCG就是一個相對值，那麼不同query之間就可以通過NDCG值進行比較評估。

2. MAP

要學習MAP名額首先要了解Precision這個名額，即精确度。在推薦系統場景下，我們可以定義正樣本為相關的商品，是以Precision就代表了，推薦的 n 個商品中，有多少個商品是相關的。而Recall就代表了資料庫中一共有 m個相關商品，推薦系統選出了多少個相關商品。

例如下面的理财産品推薦場景，使用者在未來購買了四款産品，而一個推薦系統在目前推薦了三款産品，使用者隻購買了一款産品。那麼此時，推薦系統的Recall為 1/4 ，Precision為 1/3。

值得注意的是，由于螢幕大小限制，推薦系統隻能展示前 N 個商品，是以一般推薦系統中的Precision計算會采用Cutoff形式進行計算。如下圖所示，盡管我們的推薦系統可以推薦 m個商品，但是在Cutoff-Precision的計算過程中，隻會考慮前 k 個商品的Precision。

根據上面的概念，我們就可以定義Average Precision。從公式中可以看出，[email protected]可以直覺了解為枚舉[email protected]之後取平均值。

第k個item的precision是指前k個推薦的item裡被使用者pick的item有幾個

在推薦系統場景下，使用AP最大的好處在于AP不僅僅考慮了商品推薦的準确率，還考慮了推薦順序上的差異。考慮下面這樣一個表格，從整體來考慮的話，三種推薦方案都隻推薦了一個相關商品，但是第一種推薦方案明顯是更好的，而AP名額可以展現這種差異。

介紹了[email protected]名額，我們就可以定義[email protected]名額了。其實[email protected]名額就是将所有使用者 UUU 的[email protected]名額進行平均。

總的來說，MAP名額同時考慮了預測精準度和相對順序，進而避免了傳統Precision名額無法刻畫推薦商品相對位置差異的弊端。是以。在很多推薦系統場景下，MAP名額是一個非常值得嘗試的推薦系統評估名額。

參考1：知乎Satellite

參考2：知乎震靈