信息檢索的評價課件

UNITtwo

信息檢索的評價

（IRevaluation）授課人：宋偉

sw_cyt@126.com1課前思考幾個問題為什么要評價？評價什么？如何評價？怎么基于實(shí)驗(yàn)結(jié)果，給出各項(xiàng)評價指標(biāo)？2信息檢索的評價基本指標(biāo)：召回率、正確率其他指標(biāo)：F值、AP、MAPTREC會議概況內(nèi)容提綱3從競技體育說起(曾經(jīng)的一說)世界記錄vs.世界最好成績110米欄世界記錄：羅伯斯，古巴，12”87男子馬拉松世界最好成績：保羅·特爾加特，肯尼亞，2小時4分55秒評價要公平！環(huán)境要基本一致：天氣、風(fēng)速、跑道等等比賽過程要一樣：競走中的犯規(guī)指標(biāo)要一樣：速度、耐力5為什么要評估IR？通過評估可以評價不同技術(shù)的優(yōu)劣，不同因素對系統(tǒng)的影響，從而促進(jìn)本領(lǐng)域研究水平的不斷提高類比：110米欄各項(xiàng)技術(shù)---起跑、途中跑、跨欄、步頻、沖刺等等信息檢索系統(tǒng)的目標(biāo)是較少消耗情況下盡快、全面返回準(zhǔn)確的結(jié)果。6

IR中評價什么？效率(Efficiency)—可以采用通常的評價方法時間開銷空間開銷響應(yīng)速度效果(Effectiveness)返回的文檔中有多少相關(guān)文檔所有相關(guān)文檔中返回了多少返回得靠不靠前其他指標(biāo)覆蓋率(Coverage)訪問量數(shù)據(jù)更新速度7

如何評價效果？相同的文檔集合，相同的查詢主題集合，相同的評價指標(biāo)，不同的檢索系統(tǒng)進(jìn)行比較。TheCranfieldExperiments,CyrilW.Cleverdon,1957–1968(上百篇文檔集合)SMARTSystem,GeraldSalton,1964-1988(數(shù)千篇文檔集合)TREC(TextRetrievalConference),DonnaHarman,美國標(biāo)準(zhǔn)技術(shù)研究所,1992-(上百萬篇文檔)，信息檢索的“奧運(yùn)會”8

單個查詢的評價指標(biāo)（1）未檢索出（NotRetrieved)RNNRNN檢索出（Retrieved)相關(guān)的（Relevant)不相關(guān)的（NotRelevant)RR檢索出的不相關(guān)文檔未檢索出的相關(guān)文檔未檢索出的不相關(guān)文檔檢索出的相關(guān)文檔10單個查詢的評價指標(biāo)（1）

召回率(Recall):RR/(RR+NR)，返回的相關(guān)結(jié)果數(shù)占實(shí)際相關(guān)結(jié)果總數(shù)的比率，也稱為查全率，R∈[0,1]

正確率(Precision):RR/(RR+RN)，返回的結(jié)果中真正相關(guān)結(jié)果的比率，也稱為查準(zhǔn)率，P∈[0,1]

兩個指標(biāo)分別度量檢索效果的某個方面，忽略任何一個方面都有失偏頗。兩個極端情況：返回1篇，P=100%，但R極低；全部返回，R＝1，但P極低相關(guān)文檔（標(biāo)準(zhǔn)答案）應(yīng)答文檔（返回答案）12關(guān)于召回率和正確率的討論（1）

“寧可錯殺一千，不可放過一人”偏重召回率，忽視正確率。冤殺太多。判斷是否有罪：如果沒有證據(jù)證明你無罪，那么判定你有罪。召回率高，有些人受冤枉如果沒有證據(jù)證明你有罪，那么判定你無罪。

召回率低，有些人逍遙法外14關(guān)于召回率和正確率的討論（2）雖然Precision和Recall都很重要，但是不同的應(yīng)用、不用的用戶可能會對兩者的要求不一樣。因此，實(shí)際應(yīng)用中應(yīng)該考慮這點(diǎn)。垃圾郵件過濾：寧愿漏掉一些垃圾郵件，但是盡量少將正常郵件判定成垃圾郵件。有些用戶希望返回的結(jié)果全一點(diǎn)，他有時間挑選；有些用戶希望返回結(jié)果準(zhǔn)一點(diǎn)，他不需要結(jié)果很全就能完成任務(wù)。15關(guān)于召回率的計算對于大規(guī)模語料集合，列舉每個查詢的所有相關(guān)文檔是不可能的事情，因此，不可能準(zhǔn)確地計算召回率緩沖池(Pooling)方法：對多個檢索系統(tǒng)的TopN個結(jié)果組成的集合進(jìn)行標(biāo)注，標(biāo)注出的相關(guān)文檔集合作為整個相關(guān)文檔集合。這種做法被驗(yàn)證是可行的，在TREC會議中被廣泛采用。16召回率和正確率的問題兩個指標(biāo)分別衡量了系統(tǒng)的某個方面，但是為比較帶來了難度，究竟哪個系統(tǒng)好？大學(xué)最終排名也只有一個指標(biāo)。解決方法：單一指標(biāo)，將兩個指標(biāo)融成一個指標(biāo)兩個指標(biāo)都是基于集合進(jìn)行計算，并沒有考慮序的作用舉例：兩個系統(tǒng)，對某個查詢，返回的相關(guān)文檔數(shù)目一樣都是10，但是第一個系統(tǒng)是前10條結(jié)果，后一個系統(tǒng)是最后10條結(jié)果。顯然，第一個系統(tǒng)優(yōu)。但是根據(jù)上面基于集合的計算，顯然兩者指標(biāo)一樣。解決方法：引入序的作用召回率難以計算解決方法：Pooling方法，或者不考慮召回率17單個查詢評價指標(biāo)(3)—P和R融合F值：召回率R和正確率P的調(diào)和平均值，ifP=0orR=0,thenF=0,else采用下式計算：E值：召回率R和正確率P的加權(quán)平均值，b>1表示更重視P18單個查詢評價指標(biāo)(5)

—引入序的作用正確率-召回率曲線(precisionversusrecallcurve)檢索結(jié)果以排序方式排列，用戶不可能馬上看到全部文檔，因此，在用戶觀察的過程中，正確率和召回率在不斷變化(vary)?？梢郧蟪鲈谡倩芈史謩e為0%,10%,20%,30%,…,90%,100%上對應(yīng)的正確率，然后描出圖像20P-R曲線的例子某個查詢q的標(biāo)準(zhǔn)答案集合為：Rq={d3,d5,d9,d25,d39,d44,d56,d71,d89,d123}某個IR系統(tǒng)對q的檢索結(jié)果如下：1.d123R=0.1，P=16.d9R=0.3，P=0.511.d382.d847.d51112.d483.d56R=0.2，P=0.67

8.d12913.d2504.d69.d18714.d1135.d810.d25R=0.4，P=0.415.d3

R=0.5，P=0.3321P-R曲線的插值問題對于前面的例子，假設(shè)Rq={d3,d56,d129}3.d56R=0.33,P=0.33;8.d129R=0.66,P=0.25;15.d3R=1,P=0.2不存在10%,20%,…,90%的召回率點(diǎn)，而只存在33.3%,66.7%,100%三個召回率點(diǎn)在這種情況下，需要利用存在的召回率點(diǎn)對不存在的召回率點(diǎn)進(jìn)行插值(interpolate)對于t%，如果不存在該召回率點(diǎn)，則定義t%為從t%到(t+10)%中最大的正確率值。對于上例，0%,10%,20%,30%上正確率為0.33，40%~60%對應(yīng)0.25，70%以上對應(yīng)0.223P-R曲線的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡單直觀既考慮了檢索結(jié)果的覆蓋度，又考慮了檢索結(jié)果的排序情況缺點(diǎn)：單個查詢的P-R曲線雖然直觀，但是難以明確表示兩個查詢的檢索結(jié)果的優(yōu)劣24P-R曲線中的BreakpointBreakpoint26單個查詢評價指標(biāo)(7)

—引入序的作用平均正確率(AveragePrecision,AP)：對不同召回率點(diǎn)上的正確率進(jìn)行平均未插值的AP:某個查詢Q共有6個相關(guān)結(jié)果，某系統(tǒng)排序返回了5篇相關(guān)文檔，其位置分別是第1，第2，第5，第10，第20位，則AP=(1/1+2/2+3/5+4/10+5/20+0)/6插值的AP:在召回率分別為0,0.1,0.2,…,1.0的十一個點(diǎn)上的正確率求平均，等價于11點(diǎn)平均只對返回的相關(guān)文檔進(jìn)行計算的AP,AP=(1/1+2/2+3/5+4/10+5/20)/5，傾向那些快速返回結(jié)果的系統(tǒng)，沒有考慮召回率27單個查詢評價指標(biāo)(8)

—不考慮召回率Precision@N：在第N個位置上的正確率，對于搜索引擎，考慮到大部分作者只關(guān)注前一、兩頁的結(jié)果，P@10,P@20對大規(guī)模搜索引擎非常有效bpref、NDCG：后面詳細(xì)介紹。28多個查詢評價指標(biāo)(9)平均的求法：宏平均(MacroAverage):

對每個查詢求出某個指標(biāo)，然后對這些指標(biāo)進(jìn)行算術(shù)平均微平均(MicroAverage):

將所有查詢視為一個查詢，將各種情況的文檔總數(shù)求和，然后進(jìn)行指標(biāo)的計算如：MicroPrecision=(對所有查詢檢出的相關(guān)文檔總數(shù))/(對所有查詢檢出的文檔總數(shù))宏平均對所有查詢一視同仁，微平均受返回相關(guān)文檔數(shù)目比較大的查詢影響MAP(MeanAP)：對所有查詢的AP求宏平均30多個查詢評價指標(biāo)(10)宏平均和微平均的例子

兩個查詢q1、q2的標(biāo)準(zhǔn)答案數(shù)目分別為100個和50個，某系統(tǒng)對q1檢索出80個結(jié)果，其中正確數(shù)目為40，系統(tǒng)對q2檢索出30個結(jié)果，其中正確數(shù)目為24，則：P1=40/80=0.5,R1=40/100=0.4P2=24/30=0.8,R2=24/50=0.48MacroP=(P1+P2)/2=0.65MacroR=(R1+R2)/2=0.44MicroP=(40+24)/(80+30)=0.58MicroR=(40+24)/(100+50)=0.4331整個IR系統(tǒng)的P-R曲線在每個召回率點(diǎn)上，對所有的查詢在此點(diǎn)上的正確率進(jìn)行算術(shù)平均，得到系統(tǒng)在該點(diǎn)上的平均正確率(averageprecision)。兩個檢索系統(tǒng)可以通過P-R曲線進(jìn)行比較。位置在上面的曲線代表的系統(tǒng)性能占優(yōu)。32面向用戶的評價指標(biāo)前面的指標(biāo)都沒有考慮用戶因素。而相關(guān)不相關(guān)由用戶判定。假定用戶已知的相關(guān)文檔集合為U，檢索結(jié)果和U的交集為Ru，則可以定義覆蓋率(Coverage)C=|Ru|/|U|，表示系統(tǒng)找到的用戶已知的相關(guān)文檔比例。假定檢索結(jié)果中返回一些用戶以前未知的相關(guān)文檔Rk，則可以定義出新率(NoveltyRatio)N=|Rk|/(|Ru|+|Rk|)，表示系統(tǒng)返回的新相關(guān)文檔的比例。33其他評價指標(biāo)不同的信息檢索應(yīng)用或者任務(wù)還會采用不同的評價指標(biāo)MRR(Mean

ReciprocalRank):對于某些IR系統(tǒng)(如問答系統(tǒng)或主頁發(fā)現(xiàn)系統(tǒng))，只關(guān)心第一個標(biāo)準(zhǔn)答案返回的位置(Rank)，越前越好，這個位置的倒數(shù)稱為RR，對問題集合求平均，則得到MRR例子：兩個問題，系統(tǒng)對第一個問題返回的標(biāo)準(zhǔn)答案的Rank是2，對第二個問題返回的標(biāo)準(zhǔn)答案的Rank是4，則系統(tǒng)的MRR為(1/2+1/4)/2=3/834其他評價指標(biāo)Adaptive&BatchfilteringUtility=A*R++B*N++C*R-+D*N-T11U=2*R+-N+P=R+/(R++N+),R=R+/(R++R-)T11F=1.25/(0.25/R+1/P)歸一化平均相關(guān)的不相關(guān)的檢索出的R+/AN+/B未檢索出的R-/CN-/D35近幾年出現(xiàn)的新的評價指標(biāo)

BprefGMAPNDCG36BprefBpref：Binarypreference，2005年首次引入到TREC的Terabyte任務(wù)中基本的思想：在相關(guān)性判斷(RelevanceJudgement)不完全的情況下，計算在進(jìn)行了相關(guān)性判斷的文檔集合中，在判斷到相關(guān)文檔前，需要判斷的不相關(guān)文檔的篇數(shù)相關(guān)性判斷完全的情況下，利用Bpref和MAP進(jìn)行評價的結(jié)果很一致，但是相關(guān)性判斷不完全的情況下，Bpref更好。*Buckley,C.&Voorhees,E.M.RetrievalEvaluationwithIncompleteInformation,ProceedingsofSIGIR200437原始定義對每個Topic，已判定結(jié)果中有R個相關(guān)結(jié)果r是相關(guān)文檔，n是TopR篇不相關(guān)文檔集合的子集例子：R=4d15r,d13n,d10u,d12n,d9r,d7u,d4n,d6n,d5u,d2r,d1n,d3r,d14n,…bpref=1/4*(1-0+1-2/4+1-4/4+1-4/4)=3/81不參加計算38特定情況當(dāng)R很小(1or2)時，原公式不合適

r是相關(guān)文檔，n是Top10+R篇不相關(guān)文檔集合的子集39最新定義對每個Topic，已判定結(jié)果集合中有R個相關(guān)文檔，N個不相關(guān)文檔，則Bprefcanbethoughtofastheinverseofthefractionofjudgedirrelevantdocumentsthatareretrievedbeforerelevantones.Bprefandmeanaverageprecisionareveryhighlycorrelatedwhenusedwithcompletejudgments.Butwhenjudgmentsareincomplete,rankingsofsystemsbybprefstillcorrelatehighlytotheoriginalranking,whereasrankingsofsystemsbyMAPdonot.*參看trec_eval工具8.0修正說明(bpref_bug文件)40GMAPGMAP(GeometricMAP):TREC2004Robust任務(wù)引進(jìn)先看一個例子從MAP（宏平均）來看，系統(tǒng)A好于系統(tǒng)B，但是從每個查詢來看，3個查詢中有2個TopicB比A有提高，其中一個提高的幅度達(dá)到300%系統(tǒng)TopicAPIncreaseMAP系統(tǒng)ATopic10.02-0.113Topic20.03-Topic30.29-系統(tǒng)BTopic10.08+300%0.107Topic20.04+33.3%Topic30.20-31%41GMAP幾何平均值上面那個例子GMAPa=0.056,GMAPb=0.086GMAPa<GMAPbGMAP和MAP各有利弊，可以配合使用，如果存在難Topic時，GMAP更能體現(xiàn)細(xì)微差別42NDCG每個文檔不僅僅只有相關(guān)和不相關(guān)兩種情況，而是有相關(guān)度級別，比如0,1,2,3。我們可以假設(shè)，對于返回結(jié)果：相關(guān)度級別越高的結(jié)果越多越好相關(guān)度級別越高的結(jié)果越靠前越好*Jarvelin,K.&Kekalainen,J.CumulatedGain-basedEvaluationofIRTechniques.ACMTransactionsonInformationSystems,2002,20,422-44643NDCG44NDCG45NDCG46NDCG47NDCG優(yōu)點(diǎn)：圖形直觀，易解釋支持非二值的相關(guān)度定義，比P-R曲線更精確能夠反映用戶的行為特征(如：用戶的持續(xù)性persistence)缺點(diǎn)：相關(guān)度的定義難以一致需要參數(shù)設(shè)定48TREC會議概況49TREC概況TheTextRetrieval

Conference,TREC,http://由NIST(theNationalInstituteofStandardsandTechnology)和DARPA(theDefenseAdvancedResearchProjectsAgency)聯(lián)合舉辦1992年舉辦第一屆會議，每年11月舉行，至2006年已有15屆，可以看成信息檢索的“奧運(yùn)會”50TREC的目標(biāo)（1）總目標(biāo)：支持在信息檢索領(lǐng)域的基礎(chǔ)研究，提供對大規(guī)模文本檢索方法的評估辦法1.鼓勵對基于大測試集合的信息檢索方法的研究2.提供一個可以用來交流研究思想的論壇，增進(jìn)工業(yè)界、學(xué)術(shù)界和政府部門之間的互相了解；51TREC的目標(biāo)（2）3.示范信息檢索理論在解決實(shí)際問題方面的重大進(jìn)步，提高信息檢索技術(shù)從理論走向商業(yè)應(yīng)用的速度；4.為工業(yè)界和學(xué)術(shù)界提高評估技術(shù)的可用性，并開發(fā)新的更為適用的評估技術(shù)。52TREC的運(yùn)作方式（1）TREC由一個程序委員會管理。這個委員會包括來自政府、工業(yè)界和學(xué)術(shù)界的代表。TREC以年度為周期運(yùn)行。過程為：確定任務(wù)參加者報名參加者運(yùn)行任務(wù)返回運(yùn)行結(jié)果結(jié)果評估大會交流一開始僅僅面向文本，后來逐漸加入語音、圖像、視頻方面的評測53TREC的運(yùn)作方式（2）確定任務(wù)：NIST提供測試數(shù)據(jù)和測試問題報名：參加者根據(jù)自己的興趣選擇任務(wù)運(yùn)行任務(wù)：參加者用自己的檢索系統(tǒng)運(yùn)行測試問題，給出結(jié)果返回結(jié)果：參加者向NIST返回他們的運(yùn)行結(jié)果，以便評估54TREC的運(yùn)作方式（3）結(jié)果評估：NIST使用一套固定的方法和軟件對參加者的運(yùn)行結(jié)果給出評測結(jié)果大會交流：每年的11月召開會議，由當(dāng)年的參加者們交流彼此的經(jīng)驗(yàn)55TREC的運(yùn)作方式（4）56測試數(shù)據(jù)和測試軟件由LDC(LinguisticDataConsortium)或者其他單位免費(fèi)提供，但有些數(shù)據(jù)需要繳納費(fèi)用，一般都必須簽訂協(xié)議每年使用的數(shù)據(jù)可以是新的，也可以是上一年度已經(jīng)使用過的TREC使用的評估軟件是開放的，任何組織和個人都可以用它對自己的系統(tǒng)進(jìn)行評測57TREC中的名詞定義Track

TREC的每個子任務(wù)，QA、Filtering、Web、Blog等Topic

預(yù)先確定的問題，用來向檢索系統(tǒng)提問topicquery(自動或者手工)Question(QA)Document包括訓(xùn)練集和測試集合(TIPSTER&TRECCDs、WT2G、WT10G、GOV2)RelevanceJudgments

相關(guān)性評估，人工或者半自動58Topic的一般結(jié)構(gòu)Title：標(biāo)題，通常由幾個單詞構(gòu)成，非常簡短

Description：描述，一句話，比Title詳細(xì)，包含了Title的所有單詞

Narrative：詳述，更詳細(xì)地描述了哪些文檔是相關(guān)的59Topic示例<num>Number:351<title>Falklandpetroleumexploration<desc>Description:WhatinformationisavailableonpetroleumexplorationintheSouthAtlanticneartheFalklandIslands?<narr>Narrative:AnydocumentdiscussingpetroleumexplorationintheSouthAtlanticneartheFalklandIslandsisconsideredrele