計算所軟件室TREC-11報告資料教程

TREC概況及TREC-11簡介中科院計算所軟件室王斌wangbin@2002.12.4主要內(nèi)容一、TREC概況二、TREC評測方法及標準三、TREC-11介紹以及我們的工作第一部分TREC概況TREC的歷史、發(fā)展與目標TREC的運行過程TREC由一個程序委員會(包括來自政府、工業(yè)界和學術界的代表)管理。TREC以年度為周期運行。過程為：確定任務(1~2):NIST選擇某些任務，制定規(guī)范參加者報名(2~3):參加者根據(jù)自己的興趣選擇任務（報名免費，大部分數(shù)據(jù)也免費?。﹨⒓诱哌\行任務(3~9):參加者用自己的系統(tǒng)運行測試問題，給出結(jié)果并將它們提交給NIST結(jié)果評估(10):NIST使用固定的評測軟件和工具對結(jié)果進行評估，并將結(jié)果返回給參加者大會交流(11馬里蘭州的Gaithersburg)：論文交流YearlyConferenceCycleTREC目標總目標：支持在信息檢索領域的基礎研究，提供對大規(guī)模文本檢索方法的評估辦法1.鼓勵對基于大測試集合的信息檢索方法的研究2.提供一個可以用來交流研究思想的論壇，增進工業(yè)界、學術界和政府部門之間的互相了解；3.示范信息檢索理論在解決實際問題方面的重大進步，提高信息檢索技術從理論走向商業(yè)應用的速度4.為工業(yè)界和學術界提高評估技術的可用性，并開發(fā)新的更為適用的評估技術。歷屆TREC參加單位數(shù)及任務Org.TracksTREC125Adhoc/RoutingTREC231Adhoc/RoutingTREC332Adhoc/RoutingTREC436Spanish/Interactive/DatabaseMerging/Confusion/FilteringTREC538Spanish/Interactive/DatabaseMerging/Confusion/Filtering/NLPTREC651Chinese/Interactive/Filtering/NLP/CLIR/Highprecision/SDR/VLCTREC756CLIR/HighPrecision/Interactive/Query/SDR/VLCTREC866CLIR/Filtering/Interactive/QA/Query/SDR/WebTREC970QA/CLIR(E-C)/Web/Filtering/Interactive/Query/SDRTREC1089QA/CLIR/Web/Filtering/Interactive/Video

TREC1195QA/CLIR/Web/Filtering/Interactive/Video/Novelty/歷屆TREC參加單位數(shù)示意圖參加過TREC的部分單位Corp.UniversityAsianOrganizationIBMMITSingaporeU.(KRDL)AT&TCMUKAISTMicrosoftCambridgeU.KoreaU.SunCornellU.PohangU.(釜項?)AppleMarylandU.TinghuaU.(Mainland，清華)TREC11FujitsuMassachusettsU.TsinghuaU.(Taiwan)TREC7NECNewMexicoStateU.TaiwanU.TREC8&9&10XEROXCaliforniaBerkeleyU.HongkongChineseU.TREC9RICOHMontrealU.MicrosoftResearchChinaTREC9&10CLRITECHJohnsHopkinsU.FudanU.TREC9&10&11(復旦)NTTRutgersU.ICTTREC10&11(中科院計算所)OraclePennsylvaniaU.HITTREC10(哈工大)測試數(shù)據(jù)和測試軟件由LDC(LinguisticDataConsortium)等多家單位免費提供，但少數(shù)數(shù)據(jù)有所修改，而且必須簽訂協(xié)議每年使用的數(shù)據(jù)可以是新的，也可以是上一年度已經(jīng)使用過的TREC使用的評估軟件是開放的，任何組織和個人都可以用它對自己的系統(tǒng)進行評測第二部分TREC評測方法及標準相關名詞、評測方法名詞定義TrackTREC的每個子任務，QAFilteringWebTopic預先確定的問題，用來向檢索系統(tǒng)提問topicquery(自動或者手工)Question(QA)Document包括訓練集和測試集合(TIPSTER&TRECCDs)RelevanceJudgments相關性評估，人工或者自動Topic的一般結(jié)構(gòu)Title：標題，通常由幾個單詞構(gòu)成，非常簡短Description：描述，一句話，比Title詳細，包含了Title的所有單詞Narrative：詳述，更詳細地描述了哪些文檔是相關的Topic示例<num>Number:351<title>Falklandpetroleumexploration<desc>Description:WhatinformationisavailableonpetroleumexplorationintheSouthAtlanticneartheFalklandIslands?<narr>Narrative:AnydocumentdiscussingpetroleumexplorationintheSouthAtlanticneartheFalklandIslandsisconsideredrelevant.DocumentsdiscussingpetroleumexplorationincontinentalSouthAmericaarenotrelevant.使用Topic的方式按照會議要求，可以利用Topic文本中的部分或者全部字段，構(gòu)造適當?shù)牟樵儣l件可以使用任何方式構(gòu)造查詢條件，這包括手工的和自動的兩大類。但提交查詢結(jié)果時要注明產(chǎn)生方式。評測方法基于無序集合的評測：返回結(jié)果無順序SetPrecision/SetRecall基于有序集合的評測：P@n/AveragePrecision/ReciprocalRank其他評測方法FilteringUtility相關性評估過程(1)對于每一個topic，NIST從參加者取得的結(jié)果中挑選中一部分運行結(jié)果，從每個運行結(jié)果中取頭100個文檔，然后用這些文檔構(gòu)成一個文檔池，使用人工方式對這些文檔進行判斷。相關性判斷是二值的：相關或不相關。

沒有進行判斷的文檔被認為是不相關的。相關性評估過程(2)NIST使用trec_eval軟件包對所有參加者的運行結(jié)果進行評估，給出大量參數(shù)化的評測結(jié)果（主要是precision和recall)。根據(jù)這些評測數(shù)據(jù)，參加者可以比較彼此的系統(tǒng)性能。其他track也有相應的公開評測工具第三部分TREC-11主要任務介紹以及我們的工作目的、方法與結(jié)果TREC-11的所有TracksCLIR(UseEnglishTopictoRetrieveArabicDocuments)Filtering(Filteroutrelevantdocuments)Interactive(Constructthebestquery)QuestionAnswering(Findanswerfragments)Video(RetrieveDigitalVideo)Web(RetrieveWebpages)Novelty(Retrievenewrelevantdocs)GenomicDatapre-track參加TREC11的單位TREC-11Filtering任務Goal順序掃描文檔流中的每個文檔，在當前的query下，確定是否要檢出。數(shù)據(jù)集TopicSet：100個topic，兩種風格。TrainingSet:83,650篇文檔,96.8.20~96.9.30TestingSet：720,000多文檔,96.10.1~97.8.19子任務AdaptiveFiltering：每個Topic只給出三個訓練正例BatchFiltering：每個Topic給出TrainingSet中的所有正例Routing：同BatchFiltering，但返回結(jié)果要排序應用場景個性化網(wǎng)絡信息推送敏感信息發(fā)現(xiàn)網(wǎng)絡信息分類個人興趣的跟蹤Topic集合Topicassessortopics:前50(101-150)個topic為傳統(tǒng)的TREC風格，是由NIST的裁判員手工構(gòu)造的；intersectiontopics:后50(151-200)個topic由ReutersCorpus的若干個類別組合而成，叫做intersectiontopics，是自動構(gòu)造的。每個topic包括title,description和narrative三部分，各部分均可用于過濾過程。100個topic統(tǒng)一處理，結(jié)果分別評測。assessortopic<top><num>Number:R101<title>Economicespionage<desc>Description:Whatisbeingdonetocountereconomicespionageinternationally?<narr>Narrative:Documentswhichidentifyeconomicespionagecasesandprovideaction(s)takentoreprimandoffendersorterminatetheirbehaviorarerelevant.Economicespionagewouldencompasscommercial,technical,industrialorcorporatetypesofespionage.Documentsaboutmilitaryorpoliticalespionagewouldbeirrelevant.</top>intersectiontopic<top><num>Number:R151<title>Markets/marketing,ScienceAndTechnology<desc>Description:Marketsandmarketing,ScienceAndTechnology<narr>Narrative:Relevantdocumentsdiscusssales,markets,marketing,marketresearch,productpricingconcerningallaspectsofscience,researchandnewtechnology;spacetravel&exploration.</top>TREC-10Filtering的topic(對比)<top> <top><num>R17 <num>R18<Reuters-code>C31 <Reuters-code>C311<title> <title>MARKETS/MARKETING DOMESTICMARKETS</top> </top><top> <top><num>R19 <num>R21<Reuters-code>C312 <Reuters-code>C32<title> <title>EXTERNALMARKETS ADVERTISING/PROMOTION</top> </top>數(shù)據(jù)集使用ReutersCorpusVolume1,來自Reuters/researchandstandards/corpus/TrainingSet:83,650篇文檔,大約400M。TestingSet：720,000多文檔,大約5G。輔助數(shù)據(jù)：供反饋的答案集合(每個Topic和每篇文檔在該集合中可能存在三種關系：相關，不相關，未知，TREC11增加了未知一項，防止作弊)文件訪問的順序。程序運行時間：TREC-11約為4小時，20M/m(TREC-10約為9.5小時,主要是由于反饋量減少)Adaptivefiltering系統(tǒng)框架特征選擇用戶興趣(Profile)初始化掃描文檔計算Profile/文檔的相似度Profile調(diào)整訓練集合相似度>閾值？YesNo輸出結(jié)果文檔Yes/No/不確定是否相關？Filtering評估方法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)歸一化平均得到T11SU，T11FRouting：類似于Web：AveragePrecisionRelevant(含未判定doc)NotRelevant(含未判定doc)RetrievedR+/AN+/BNotRetrievedR-/CN-/DAdaptiveFiltering主要算法Adaptivefiltering在tf*idf模型的實現(xiàn)上由原來的tf*log(N/n)改為log(tf)*log(N/n)ProfileInitializing3positivesamples+適當比例的Topic+根據(jù)前兩者從訓練集中篩選出來的適量偽正例。Threshold:通過經(jīng)驗和訓練確定初始值，在反饋過程中調(diào)整。ProfileAdaptationOptimizationfortwoMeasurementfunctionsRocchio反饋算法:Pn+1=Pn+a*Dpos+b*Dneg+b’*DundTREC-10filtering存在問題大集合結(jié)果好，小集合結(jié)果很差，零太多優(yōu)化方法太簡單特征選擇有待改進是否嘗試語義特征項？TREC-11filtering算法的改進改進了原來的互信息特征選擇算法，在整個訓練集上計算各個topic的特征詞，由3個種子和適量的擴展文檔組成“相關文檔集”，訓練集中剩下的文檔作為“不相關文檔集”。鑒于TREC-11的topic改為TREC風格后，原來的特征選擇算法幾乎失效，故最后直接用3個種子，原始topic和擴展產(chǎn)生的偽相關文檔按照一定的比例混合構(gòu)成原始的profile。改進了原來的針對TREC目標函數(shù)的優(yōu)化算法，引入了局部最優(yōu)策略，追求各個反饋區(qū)間的局部最優(yōu)值來達到全局的最優(yōu)值；同時盡量避免‘0’返回的出現(xiàn)。對小樣本訓練集進行優(yōu)化處理：根據(jù)擴展時偽相關文檔數(shù)的多少決定是否應擴大“正例樣本集”，小于某一閾值的樣本集將被復制若干遍。TREC-11改進算法在TREC-10上的實驗實驗結(jié)果表明，改進的特征選擇算法略好于舊的特征選擇算法，并且可以控制小樣本訓練集的優(yōu)化。二者結(jié)合的結(jié)果由原來的0.207上升到0.220，約提高6%。局部最優(yōu)策略的引入是成功的，可進一步使結(jié)果由0.220增加到0.270，約提高23%。TREC-11跟TREC-10filtering的差別Topic形式由Reuters類別變?yōu)門REC格式，數(shù)目由84個增加到100個，每個topic的已知正例數(shù)目由2個變?yōu)?個。不再給出訓練/測試集合中的全部正反例答案，改為只給出部分正例和反例，訓練/測試集合中的其他文檔將作為未判定文檔對待。即過濾過程中的反饋是不充分的。U目標函數(shù)的歸一化方法有所變化，相同的U值歸一化后T11SU約為T10SU的兩倍。TREC-11filtering的主要困難由于測試集合的標準答案只給出一部分，因而過濾時繼續(xù)使用原來的優(yōu)化策略無法獲得充分的反饋信息；已知的部分答案在整個測試集合中所占的比例無法得知，因而不能控制未判定文檔(undetermined)的返回比例，從而無從把握最終返回文檔的數(shù)量。原來的優(yōu)化策略有些可能不再適用，需要重新修正。TREC-11filtering的反饋試驗(1)鑒于已知正反例答案的不完全性，我們已經(jīng)嘗試了3種方法控制過濾反饋的效用：（1）通過正例/反例的相對比例來調(diào)節(jié)過濾閾值，即不考慮返回結(jié)果中的未判定文檔。缺點：不能保證在已知正反例構(gòu)成的小集合上很好的結(jié)果可以推廣到整個測試集合上，取決于各個topic的實際相關文檔在整個測試集上的具體分布情況。TREC-11filtering的反饋試驗(2)（2）利用過濾時獲得的正反例信息構(gòu)造正例中心和反例中心，再用正反例中心分割未判定文檔，形成偽正例/偽反例集合，從而模擬出已知整個測試集的正反例答案的情況，這使得TREC-10的優(yōu)化策略可以繼續(xù)使用。優(yōu)點：返回文檔的數(shù)量較多，當實際相關文檔較多時有優(yōu)勢。缺點：正反例中心的初值似乎對未判定文檔的分類影響很大，目前還沒有找到較好的構(gòu)造方法。TREC-11filtering的反饋試驗(3)（3）假定測試集合中已知的相關文檔足夠多，據(jù)此把過濾時遇到的未判定文檔大部或者全部作為反例文檔對待。優(yōu)點：可以有效控制返回文檔的數(shù)量。缺點：不能保證假設成立，當實際相關文檔確實較少時有優(yōu)勢；但是當實際相關文檔集合較已知正例答案大很多時，損失也大。TREC-11filtering最終的反饋方案TREC-11filteringmailinglist的討論表明，方案三的假設比較合理。根據(jù)以上實驗結(jié)果的比較分析，最終確定以方案三為基礎，經(jīng)過改進后形成最終的反饋方案。優(yōu)化方案仍采用局部最優(yōu)策略，然后針對未判定文檔的處理作相應調(diào)整。ICTTREC-11filtering的結(jié)果

RunIDMeanT11UT11Uvs.median(topicnums)MeanT11FT11Fvs.median(topicnums)>(Best)=<(Worst/Zero)>(Best)=<(Worst/Zero)ICTAdaFT11Ua0.47546(6)31(0/0)0.42743(5)07(2/2)ICTAdaFT11Ub0.47546(6)31(0/0)0.42843(5)07(2/2)ICTAdaFT11Uc0.47145(6)32(0/0)0.42241(4)09(2/2)ICTAdaFT11Fd0.32118(0)230(3/3)0.30629(0)219(2/2)Table1ICTTREC-11adaptivefiltering結(jié)果(50Assessortopics)ICTTREC-11filtering的結(jié)果

RunIDMeanT11UT11Uvs.median(topicnums)MeanT11FT11Fvs.median(topicnums)>(Best)=<(Worst/Zero)>(Best)=<(Worst/Zero)ICTAdaFT11Ua0.33550(18)00(0/0)0.06112(5)326(6/6)ICTAdaFT11Ub0.33049(17)01(1/1)0.06213(3)316(6/6)ICTAdaFT11Uc0.33550(18)00(0/0)0.06112(5)326(6/6)ICTAdaFT11Fd0.24019(0)724(3/3)0.05221(1)245(5/5)Table2ICTTREC-11adaptivefiltering結(jié)果(50Intersectiontopics)ICTTREC-11filtering的結(jié)果

RunIDMeanT11UT11Uvs.median(topicnums)MeanT11FT11Fvs.median(topicnums)>(Best)=<(Worst/Zero)>(Best)=<(Worst/Zero)ICTAdaFT11Ua0.40596(24)31(0/0)0.24455(10)3213(8/8)ICTAdaFT11Ub0.402595(23)32(1/1)0.24556(8)3113(8/8)ICTAdaFT11Uc0.40395(24)32(0/0)0.241553(9)3215(8/8)ICTAdaFT11Fd0.280537(0)954(6/6)0.17950(1)2624(7/7)Table3ICTTREC-11adaptivefiltering結(jié)果(all100topics)ICTTREC-11filtering的結(jié)果

RunIDMeanT11UT11Uvs.baseline=0.333(Assessor/Intersection/alltopicnums)>=<ICTAdaFT11Ua0.40543/7/500/5/57/38/45ICTAdaFT11Ub0.402543/7/500/5/57/38/45ICTAdaFT11Uc0.40341/7/480/5/59/38/47ICTAdaFT11Fd0.280519/2/210/0/031/48/79Best-performing?50/12/620/?/?0/?/<=38Median0.31929/1/303/0/318/49/67Table4ICTTREC-11adaptivefiltering結(jié)果跟baseline的比較(all100topics)結(jié)論對50個assessortopic效果很好，自然語言描述中包含豐富的信息。對50個intersectiontopic效果不是很好，但是對于其中正確結(jié)果較多的topic效果也還行。排名未知，預計名列前茅＝>排名第一!排名情況根據(jù)T11SU(14)ICT 0.405KerMIT0.390CMU 0.369CLIPS-IMAGLab0.349

MicrosoftCambridge0.343(微軟劍橋研究院)根據(jù)T11F(14)ICT 0.245KerMIT、Thu0.237CMU 0.2315MicrosoftCambridge0.2305每個run得分情況(T11SU)每個run得分情況(T11F)WEBTrackNamedPageFinding找到用戶命名的網(wǎng)頁，例如

passportapplicationformTopicDistillation找到與內(nèi)容相關的keyresource,可以是相關站點的主頁相關子站點的主頁高度相關的單個頁面Hub頁面數(shù)據(jù)集.Gov數(shù)據(jù)Acrawlof.govWebsites(early2002).Stoppedafter1milliontext/htmlpagesAlsoincludingtext/plainandtheextractedtextofpdf,docandps.18GDocumentstruncatedto100k(reducingsizefrom35Gto18G)TOPIC集合(1)Topicdistillation:50個 <top> <num>Number: <title>obesityintheU.S. <desc>Description:Findresourcesdescribingthedangers,theprevalence,preventionortreatmentofobesityintheU.S. <narr>Narrative:RelevantresourcesdescribeprogramsorindividualeffortstotreatobesityintheU.S.Alsorelevantarethosedocumentingtheprevalenceofobesity.Toberelevantoverweightmustbegrossandmedicallydefinedas"obese."Grantproposalsforresearchonthisproblemarenotrelevant. </top>Topic集合(2)NamedPageFinding:150 <top> <num>Number:NP3 <desc>Description:VolunteerFEMAWorldTradeCenter </top>系統(tǒng)框架指導原則：以Wt10g為訓練集，指導Gov數(shù)據(jù)集上的試驗。組織形式：考慮到實際情況，以松散耦合的形式為主，系統(tǒng)的組成部分相對獨立，每一部分考慮一個單獨的因素，最后以線性組合的形式綜合考慮。組成部分純內(nèi)容文檔結(jié)構(gòu)(標題，格式信息等)鏈接文本(anchortext)URL分析鏈接分析內(nèi)容檢索經(jīng)過對比試驗，選定了Lnu-Ltu(pivoteddocumentlengthnormalization)方式作為內(nèi)容權重計算公式。在Wt10g上，topic501-550的一次檢索平均準確率為0.1939(去年的結(jié)果是0.08，第一名是0.2226)，達到OKAPI的水平；使用純內(nèi)容檢索得到的homepagefinding任務的結(jié)果的MRR達到0.4185，超過上屆參加者使用內(nèi)容檢索得到的結(jié)果。文檔結(jié)構(gòu)信息結(jié)構(gòu)信息對于文檔的精確定位有重要作用。由于超文本分析的復雜性，目前只使用了文檔的title域。單獨使用結(jié)構(gòu)信息進行檢索，homepagefinding任務的結(jié)果MRR達到了0.4467，高于內(nèi)容檢索。鏈接分析試圖利用文檔之間的鏈接關系發(fā)現(xiàn)重要資源主要利用HITS算法(hub,authority)原始算法存在缺陷，主要是計算結(jié)果存在topicdrift現(xiàn)象，不再和原主題緊密相關。對算法的迭代過程進行了改進，把頁面的內(nèi)容相關值(由內(nèi)容檢索得到)作為一個因子乘在hub和authority上，并對排名靠后的頁面的影響度進行了衰減。結(jié)果有所改善，但仍不能取得滿意的結(jié)果。鏈接文本鏈接文本在檢索中所起的作用類似于結(jié)構(gòu)信息，有助于文檔的精確的定位。單獨使用鏈接文本檢索，homepagefinding的MRR值達到0.3769，略低于內(nèi)容檢索的結(jié)果。URL分析嘗試利用URL包