NDCG指標在有限排序結果怎麼應用

最近跑rank比較多，發現還是MAP和NDCG作為測算指標比較友好，這裡說說怎麼應用NDCG。前面廢話比較多，乾貨就最後幾句話。

基礎

概念基礎就不多說了，直接看Discounted cumulative gain。注意公式除了常用版本的，也可以應用不同版本。

一般而論，MAP,NDCG都是對Precision的進階，通過數學方法加大了序列結果前若干項的Precision權重。適用場景應該是序列特別長，但有意義的結果佔比較小，或者只關注前若干項的情況。

問題

NDCG的分布有一個特點，就是長尾，比如按照常用公式，假設給所有正項賦值1，負項賦值0，DCG前100項的權重分布如下，注意0對應第一項：

這說明什麼？說明NDCG在序列前20-30項以後就基本和Precision相似了，所以在演算法中一般應用NDCG時都是截取最前面一部分進行計算，這也是它的優勢。

應用

比如跑一個rank演算法，應用NDCG對前20項評價，平均結果是0.8，怎麼看這個結果？

首先，NDCG的結果一定處於[0,1]區間，原則上越高越好。

如果結果是0.8，那麼說明前20項中有N項錯誤，那麼這個N是多少？

理論上解決這個問題思路簡單：

1. 前20項的IDCG為：7.04
2. 錯誤項對應的N個DCG和為7.04*（1-0.8）=1.408
3. 求這個N

由於奇怪的分布形狀，筆算應該不是特別簡單，但我們有簡單的辦法：蒙地卡羅

比如，假設N=5，即從20項中抽取5項，一共有15504種可能，那麼我們最少應該蒙地卡羅模擬重複這一過程大約15504*100=155萬次（實際跑了300萬次），看一下和的分布和均值：

均值是1.76

下面把N從1-6對應的均值都列出：

• N=1 均值 0.35
• N=2 均值 0.70
• N=3 均值 1.06
• N=4 均值 1.41
• N=5 均值 1.76
• N=6 均值 2.11

試試查表，上面的1.408接近N=4的1.41，說明前20項排序結果中平均有4項錯誤（最大概率來說），80%的正確率。

如果NDCG（20項）結果是0.9呢？7.04*（1-0.9）=0.704，查表對應N=2，90%的正確率。

上面的分析都是進行了概率平均的。

對於單次結果而言，也有很大的可能是尾部的更多項錯誤。即N完全有可能大於2，極端情況下，N可以等於5，

另外這裡有一個規律：

NDCG結果經過概率平均後，直接對應Precision。這個規律從公式上也能推導出。這一點上它比MAP更直觀。

實用中NDCG的價值就在這裡：

1：它在大尺度（樣本量大，次數足夠多）的情況下，期望就是Precision

2：它對排序靠前的10項左右特別敏感

實際情況下，前10多項的排序錯誤會使NDCG顯著降低，使我們能更好地評價該排序結果的價值。

上面結論只有在所有正項都給予相同權重的情況下才有效，若給期望的前10項賦值2，11-20項賦值1，就不行了，這時候分析結果，最好用上面的蒙地卡羅辦法先跑一下。