KwCheng's blog

1.Precision & Recall

2.F-Score

3.ROC Curve ( Receiver Operatng Characteristics)

4.Area under the ROC curve

5.Eleven-point interpolated average precision

5.MAP (Mean average precision)

Precision & Recall

在Information Retrieval 中,最直接用來衡量一個model的效能就是Precision & Recall

Precision : Tp / Tp + Fp , 即表示在所有Retrieve出的document中,有多少是Relevance.

Recall : Tp / Tp + Tn ,   即表示在所有Relevance的document中,有多少是被Retrieve到.

在理論上,Precision跟Recall之間是無絕對的對應關係,

但在實際應用上,通常Precision會隨著Retrieval document越多而遞減,而Recall則會遞增.

For Example(假設database中,relevance的document數目為10)

而如果我們要使用單一個measure來evaluation搜尋的效能,

使用的通常為F-Score.

F-Score

F-score就是Precision與Recall的調和平均數(Harmonic Mean),

即 F = 2/(1/p + 1/r) = 2pr/(p+r)

而有時也會給予Precision及Recall不同的權重(weight)來進行計算,

即F = 2 / [a*(1/p)+(1-a)*(1/r)] = (b*b+1)pr / (b*b)p+r

若取b=1則F就等同於原來的式子,

若b>1,代表weight較偏重於Recall,

若0<b<1,代表weight較偏重於Precision.

前面所介紹的Precison & Recall 以及 F-score,針對的都是未排序的document,

但在實際的search engine中,所search的結果之間都是經過排序的,

因此就有人提出了 Eleven-point interpolated average precision, MAP(Mean Average Precision)

以及NDCG (normal discount cumulative gain).

ROC Curve

Y軸為True Positive (或稱為sensitivity或recall),而X軸為False Positive (或稱為1-Specificity),

一個Query的回傳結果分為兩個Part,一個為相關的set,另一個為不相關的set,

而True Positive指的就是相關的set在所有相關的document中佔有多大比例.[即 tp / (tp + tn)]

False Positive則是指不相關的set在所有不相關的document中佔有多大的比例.[即 fp /(fp+fn)]

當一個system越好時,則它的ROC Curve會較偏向於左邊.

關於此點,我們固定Y軸來看,若一個System的 Recall越高,則有兩種狀況,

第一:回傳的Result不大,但Corpus中的Relevance document有很高的比例都被retrieval到了.

第二:回傳的Result很大,讓Corpus中的Relevance document有很高的比例都被retrieval到了.

如果為第一點,則False positive會很低,因為回傳的結果有大部份都是不相關,則整個ROC curve會

往左邊靠,但如果是第二點,則False positive會很高,因為回傳的結果有大部份都是不相關,

此時ROC curve會往右邊偏移.

因此可得知,若一個System較好,則其ROC Curve必定較為偏向右邊.(即起伏較快)

以下圖來講,C的curve在回傳較少的result時便可達到100% recall,

而A curve相對來說則需要較多的result才能達到100% recall.

因此C 這個System相對於A來說,其performance是較好的.

(ref:http://clincancerres.aacrjournals.org/content/12/23/6985.full)

Area under the ROC Curve (AUC):

AUC即是計算ROC Curve的曲線下面積(即下圖的A區域),

以下圖來看,假設HR(C)代表的是回傳的結果中佔所有相關document的比例,

而FAR(C)則是代表回傳的結果中佔有不相關document的比例,

則此曲線下的面積值,即是HR(C)*FAR(C)再由0積分到1.

而其道理同ROC Curve,若AUC的value較高,則表示一個System可正確的區分

正確及錯誤的狀況.

(ref:http://www.acadametrics.co.uk/roc.htm)

Eleven-point interpolated average precision

11-point interpolated average precision是將Recall分為11個等級,

分別為 0.0 , 0.1 , 0.2 , 0.3 , ... , 1.0 , 分別表示全部資料的 0% , 10% , 20% , ... , 100%

而每個等級上的precision則取目前此點之後的Max precision,而為什麼要這樣子 , 因為在

11-point interpolated average precision上的一個基本假設是:如果我們可以增加View set中

relevance document 的比利的話, 那user都會想要去看更多的document.

由此方法所繪出的Precision-Recall Curve在某種程度上就可以看出不同方法在document

ranking上的好壞.