未經(jīng)允許，不得轉(zhuǎn)載，謝謝~~

一文章簡(jiǎn)介

為什么要提出這個(gè)新的評(píng)價(jià)算法？

我們都知道ranking過程對(duì)于信息檢索的結(jié)果是非常重要的，那么我們就需要有一些算法能評(píng)價(jià)ranking的結(jié)果到底如何。
現(xiàn)有用來評(píng)價(jià)ranking的常用算法有：Kendall's τ, Average Precision（AP） , Mean Average Precision(MAP)，Discounted Cumulative Gain (DCG)， nDCG.
跟簡(jiǎn)單的分類任務(wù)只需要一個(gè)accuracy不一樣，盡管已經(jīng)有了那么多的ranking measures，但仍然存在一些問題。
尤其是在解決“對(duì)那些具有相同等級(jí)分布和傾斜等級(jí)分布多個(gè)關(guān)系的離散值元素進(jìn)行排序任務(wù)時(shí)”；
所以本文基于nDCG算法提出了RankDCG，并提出一些標(biāo)準(zhǔn)來測(cè)試這些算法，實(shí)驗(yàn)發(fā)現(xiàn)只有本文的RankDCG滿足全部的要求。

二排序問題描述

Ordering：用網(wǎng)頁檢索的例子來看就是要在接近無窮大的數(shù)據(jù)集中找到相應(yīng)的信息并對(duì)它們進(jìn)行相關(guān)性排序。
問題可以用數(shù)學(xué)的方式定義為：
- A為一系列元素： A = [x1,x2,x3,...,xn]；
- f(x)度量了元素x與query的相關(guān)性，f(x)屬于0-1；
- 通常我們能在A中的n個(gè)元素找到m個(gè)相關(guān)的元素，并按相關(guān)性由高到低進(jìn)行排序得到目標(biāo)結(jié)果B；
- B = [x|x ∈ A,f(x) > 0]，且 B = [ f(x1) > f(x2) > f(x3) > ... > f(xm) ]；
在本文中考慮現(xiàn)實(shí)世界中經(jīng)常出現(xiàn)的排序問題，例如推薦系統(tǒng)和用戶排序；這跟上面提到的網(wǎng)頁檢索有一些不太一樣的地方，包括：
- 在這里每個(gè)元素都是相關(guān)的；
- 待排序的都是離散值；
- 會(huì)出現(xiàn)多個(gè)元素具有相同等級(jí)的情況；
- 排序結(jié)果可能會(huì)出現(xiàn)只有非常少數(shù)的top result是相關(guān)的情況；
針對(duì)上述問題，重新定義了目標(biāo)結(jié)果B的表示為： B = [f(x1) ≥ f(x2) ≥ f(x3) ≥ ... ≥ f(xn)]，并對(duì)ranking measure提出了需要能夠正確反映上述4點(diǎn)的要求。

信息檢索領(lǐng)域有多個(gè)方法來評(píng)價(jià)rank ordering的好壞，但是沒有一個(gè)對(duì)上面描述的這種問題是完全適用的，接下來先看看目前常用的一些評(píng)價(jià)算法。

這是一個(gè)在IR中非常常見的評(píng)價(jià)指標(biāo)；
同時(shí)考慮了檢測(cè)精度p和召回率r；
但是不適用于所有元素都相關(guān)的情況，也沒有將不同的ranks考慮在內(nèi)，所以不適合作為rank-ordering的評(píng)價(jià)標(biāo)準(zhǔn)。

其中：P(k) = precision@k ， ?R(k) = |recall(k?1)?recall(k)|.
其實(shí)理論上的AP應(yīng)該等于綠色的precision-recall線的下方面積，而用近似計(jì)算就等于看成是一小塊的長(zhǎng)方形的面積之和，即為圖中紅色虛線的下方面積。

AP,MAP都可以評(píng)價(jià)rank-ordering問題；
AP，MAP基于rank與rank之間沒有關(guān)系的這個(gè)前提，沒有考慮多個(gè)元素會(huì)是同一個(gè)rank的情況；
AP，MAP對(duì)所有的rank values都是用相同的cost對(duì)待，沒有考慮需要將更多的注意力放在少數(shù)幾個(gè)high-rank的元素上。

這個(gè)算法考慮了rank排序的問題，是目前文章中介紹過的唯一一個(gè)用了cost function的算法；
本文也是自己與這個(gè)算法做的改進(jìn)；
rel（）指的是相關(guān)度度量函數(shù)，i 表示元素所在的位置；
這里有一個(gè)很不錯(cuò)的例子哦.
標(biāo)準(zhǔn)的DCG根據(jù)元素所在的位置不同給出不同的cost；
而文章作者認(rèn)為[9,1,1]對(duì)于結(jié)果[1,9,1]與[1,1,9]應(yīng)該是一樣的（因?yàn)橹挥幸粋€(gè)9是top-1，而且都出錯(cuò)了）

從一個(gè)例子開始分析：
下面兩張圖為standard DCG與別人改進(jìn)的DCG在各個(gè)元素上的cost圖：
不足之處：這兩個(gè)算法都將一般以上的cost放在了最高rank的元素上，這會(huì)導(dǎo)致整個(gè)評(píng)價(jià)算法引導(dǎo)ranking的走向找到top-rank的元素而不是做好ordering工作。
所以文章做的第一個(gè)工作：提出了新的rel（）函數(shù)，具體體現(xiàn)為將原來的變成：

具體步驟是：在L中有10個(gè)rank值，但是只有4個(gè)不同的rank，所以按照rank value對(duì)元素進(jìn)行分組，得到4，那個(gè)第一個(gè)sublist的rankvalue就改成4，后面的sublist依次遞減。
這樣可以得都到以下的結(jié)果圖，可以看到整個(gè)cost下降更均衡了。
現(xiàn)在這樣其實(shí)還有一個(gè)問題，基于位置的折損函數(shù)cost會(huì)導(dǎo)致本來rank value一樣的值最后得到的cost卻是不一樣的，例如最后4個(gè)1。
文章做的第二個(gè)工作就是將基于位置的折損改成新的折損系統(tǒng)，具體方法是對(duì)L‘的rank value做一個(gè)翻轉(zhuǎn)，將值依次賦給各個(gè)sublist。最后得到：
這時(shí)候的cost圖為：
最后也模仿DCG->nDCG的過程，做了一次歸一化，即最終的RankDCG算法等于：