計(jì)算所軟件室TREC-11報(bào)告資料教程

TREC概況及TREC-11簡介中科院計(jì)算所軟件室王斌wangbin@2002.12.4主要內(nèi)容一、TREC概況二、TREC評(píng)測方法及標(biāo)準(zhǔn)三、TREC-11介紹以及我們的工作第一部分TREC概況TREC的歷史、發(fā)展與目標(biāo)TREC的運(yùn)行過程TREC由一個(gè)程序委員會(huì)(包括來自政府、工業(yè)界和學(xué)術(shù)界的代表)管理。TREC以年度為周期運(yùn)行。過程為：確定任務(wù)(1~2):NIST選擇某些任務(wù)，制定規(guī)范參加者報(bào)名(2~3):參加者根據(jù)自己的興趣選擇任務(wù)（報(bào)名免費(fèi)，大部分?jǐn)?shù)據(jù)也免費(fèi)?。﹨⒓诱哌\(yùn)行任務(wù)(3~9):參加者用自己的系統(tǒng)運(yùn)行測試問題，給出結(jié)果并將它們提交給NIST結(jié)果評(píng)估(10):NIST使用固定的評(píng)測軟件和工具對(duì)結(jié)果進(jìn)行評(píng)估，并將結(jié)果返回給參加者大會(huì)交流(11馬里蘭州的Gaithersburg)：論文交流YearlyConferenceCycleTREC目標(biāo)總目標(biāo)：支持在信息檢索領(lǐng)域的基礎(chǔ)研究，提供對(duì)大規(guī)模文本檢索方法的評(píng)估辦法1.鼓勵(lì)對(duì)基于大測試集合的信息檢索方法的研究2.提供一個(gè)可以用來交流研究思想的論壇，增進(jìn)工業(yè)界、學(xué)術(shù)界和政府部門之間的互相了解；3.示范信息檢索理論在解決實(shí)際問題方面的重大進(jìn)步，提高信息檢索技術(shù)從理論走向商業(yè)應(yīng)用的速度4.為工業(yè)界和學(xué)術(shù)界提高評(píng)估技術(shù)的可用性，并開發(fā)新的更為適用的評(píng)估技術(shù)。歷屆TREC參加單位數(shù)及任務(wù)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.(釜項(xiàng)?)AppleMarylandU.TinghuaU.(Mainland，清華)TREC11FujitsuMassachusettsU.TsinghuaU.(Taiwan)TREC7NECNewMexicoStateU.TaiwanU.TREC8&9&10XEROXCaliforniaBerkeleyU.HongkongChineseU.TREC9RICOHMontrealU.MicrosoftResearchChinaTREC9&10CLRITECHJohnsHopkinsU.FudanU.TREC9&10&11(復(fù)旦)NTTRutgersU.ICTTREC10&11(中科院計(jì)算所)OraclePennsylvaniaU.HITTREC10(哈工大)測試數(shù)據(jù)和測試軟件由LDC(LinguisticDataConsortium)等多家單位免費(fèi)提供，但少數(shù)數(shù)據(jù)有所修改，而且必須簽訂協(xié)議每年使用的數(shù)據(jù)可以是新的，也可以是上一年度已經(jīng)使用過的TREC使用的評(píng)估軟件是開放的，任何組織和個(gè)人都可以用它對(duì)自己的系統(tǒng)進(jìn)行評(píng)測第二部分TREC評(píng)測方法及標(biāo)準(zhǔn)相關(guān)名詞、評(píng)測方法名詞定義TrackTREC的每個(gè)子任務(wù)，QAFilteringWebTopic預(yù)先確定的問題，用來向檢索系統(tǒng)提問topicquery(自動(dòng)或者手工)Question(QA)Document包括訓(xùn)練集和測試集合(TIPSTER&TRECCDs)RelevanceJudgments相關(guān)性評(píng)估，人工或者自動(dòng)Topic的一般結(jié)構(gòu)Title：標(biāo)題，通常由幾個(gè)單詞構(gòu)成，非常簡短Description：描述，一句話，比Title詳細(xì)，包含了Title的所有單詞Narrative：詳述，更詳細(xì)地描述了哪些文檔是相關(guān)的Topic示例<num>Number:351<title>Falklandpetroleumexploration<desc>Description:WhatinformationisavailableonpetroleumexplorationintheSouthAtlanticneartheFalklandIslands?<narr>Narrative:AnydocumentdiscussingpetroleumexplorationintheSouthAtlanticneartheFalklandIslandsisconsideredrelevant.DocumentsdiscussingpetroleumexplorationincontinentalSouthAmericaarenotrelevant.使用Topic的方式按照會(huì)議要求，可以利用Topic文本中的部分或者全部字段，構(gòu)造適當(dāng)?shù)牟樵儣l件可以使用任何方式構(gòu)造查詢條件，這包括手工的和自動(dòng)的兩大類。但提交查詢結(jié)果時(shí)要注明產(chǎn)生方式。評(píng)測方法基于無序集合的評(píng)測：返回結(jié)果無順序SetPrecision/SetRecall基于有序集合的評(píng)測：P@n/AveragePrecision/ReciprocalRank其他評(píng)測方法FilteringUtility相關(guān)性評(píng)估過程(1)對(duì)于每一個(gè)topic，NIST從參加者取得的結(jié)果中挑選中一部分運(yùn)行結(jié)果，從每個(gè)運(yùn)行結(jié)果中取頭100個(gè)文檔，然后用這些文檔構(gòu)成一個(gè)文檔池，使用人工方式對(duì)這些文檔進(jìn)行判斷。相關(guān)性判斷是二值的：相關(guān)或不相關(guān)。

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

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

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