计算所软件室TREC-11报告资料教程

TREC概况及TREC-11简介中科院计算所软件室王斌wangbin@2002.12.4主要内容一、TREC概况二、TREC评测方法及标准三、TREC-11介绍以及我们的工作第一部分TREC概况TREC的历史、发展与目标TREC的运行过程TREC由一个程序委员会(包括来自政府、工业界和学术界的代表)管理。TREC以年度为周期运行。过程为：确定任务(1~2):NIST选择某些任务，制定规范参加者报名(2~3):参加者根据自己的兴趣选择任务（报名免费，大部分数据也免费！）参加者运行任务(3~9):参加者用自己的系统运行测试问题，给出结果并将它们提交给NIST结果评估(10):NIST使用固定的评测软件和工具对结果进行评估，并将结果返回给参加者大会交流(11马里兰州的Gaithersburg)：论文交流YearlyConferenceCycleTREC目标总目标：支持在信息检索领域的基础研究，提供对大规模文本检索方法的评估办法1.鼓励对基于大测试集合的信息检索方法的研究2.提供一个可以用来交流研究思想的论坛，增进工业界、学术界和政府部门之间的互相了解；3.示范信息检索理论在解决实际问题方面的重大进步，提高信息检索技术从理论走向商业应用的速度4.为工业界和学术界提高评估技术的可用性，并开发新的更为适用的评估技术。历届TREC参加单位数及任务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参加单位数示意图参加过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(哈工大)测试数据和测试软件由LDC(LinguisticDataConsortium)等多家单位免费提供，但少数数据有所修改，而且必须签订协议每年使用的数据可以是新的，也可以是上一年度已经使用过的TREC使用的评估软件是开放的，任何组织和个人都可以用它对自己的系统进行评测第二部分TREC评测方法及标准相关名词、评测方法名词定义TrackTREC的每个子任务，QAFilteringWebTopic预先确定的问题，用来向检索系统提问topicquery(自动或者手工)Question(QA)Document包括训练集和测试集合(TIPSTER&TRECCDs)RelevanceJudgments相关性评估，人工或者自动Topic的一般结构Title：标题，通常由几个单词构成，非常简短Description：描述，一句话，比Title详细，包含了Title的所有单词Narrative：详述，更详细地描述了哪些文档是相关的Topic示例<num>Number:351<title>Falklandpetroleumexploration<desc>Description:WhatinformationisavailableonpetroleumexplorationintheSouthAtlanticneartheFalklandIslands?<narr>Narrative:AnydocumentdiscussingpetroleumexplorationintheSouthAtlanticneartheFalklandIslandsisconsideredrelevant.DocumentsdiscussingpetroleumexplorationincontinentalSouthAmericaarenotrelevant.使用Topic的方式按照会议要求，可以利用Topic文本中的部分或者全部字段，构造适当的查询条件可以使用任何方式构造查询条件，这包括手工的和自动的两大类。但提交查询结果时要注明产生方式。评测方法基于无序集合的评测：返回结果无顺序SetPrecision/SetRecall基于有序集合的评测：P@n/AveragePrecision/ReciprocalRank其他评测方法FilteringUtility相关性评估过程(1)对于每一个topic，NIST从参加者取得的结果中挑选中一部分运行结果，从每个运行结果中取头100个文档，然后用这些文档构成一个文档池，使用人工方式对这些文档进行判断。相关性判断是二值的：相关或不相关。

没有进行判断的文档被认为是不相关的。相关性评估过程(2)NIST使用trec_eval软件包对所有参加者的运行结果进行评估，给出大量参数化的评测结果（主要是precision和recall)。根据这些评测数据，参加者可以比较彼此的系统性能。其他track也有相应的公开评测工具第三部分TREC-11主要任务介绍以及我们的工作目的、方法与结果TREC-11的所有TracksCLIR(UseEnglishTopictoRetrieveArabicDocuments)Filtering(Filteroutrelevantdocuments)Interactive(Constructthebestquery)QuestionAnswering(Findanswerfragments)Video(RetrieveDigitalVideo)Web(RetrieveWebpages)Novelty(Retrievenewrelevantdocs)GenomicDatapre-track参加TREC11的单位TREC-11Filtering任务Goal顺序扫描文档流中的每个文档，在当前的query下，确定是否要检出。数据集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，但返回结果要排序应用场景个性化网络信息推送敏感信息发现网络信息分类个人兴趣的跟踪Topic集合Topicassessortopics:前50(101-150)个topic为传统的TREC风格，是由NIST的裁判员手工构造的；intersectiontopics:后50(151-200)个topic由ReutersCorpus的若干个类别组合而成，叫做intersectiontopics，是自动构造的。每个topic包括title,description和narrative三部分，各部分均可用于过滤过程。100个topic统一处理，结果分别评测。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>数据集使用ReutersCorpusVolume1,来自Reuters/researchandstandards/corpus/TrainingSet:83,650篇文档,大约400M。TestingSet：720,000多文档,大约5G。辅助数据：供反馈的答案集合(每个Topic和每篇文档在该集合中可能存在三种关系：相关，不相关，未知，TREC11增加了未知一项，防止作弊)文件访问的顺序。程序运行时间：TREC-11约为4小时，20M/m(TREC-10约为9.5小时,主要是由于反馈量减少)Adaptivefiltering系统框架特征选择用户兴趣(Profile)初始化扫描文档计算Profile/文档的相似度Profile调整训练集合相似度>阈值？YesNo输出结果文档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模型的实现上由原来的tf*log(N/n)改为log(tf)*log(N/n)ProfileInitializing3positivesamples+适当比例的Topic+根据前两者从训练集中筛选出来的适量伪正例。Threshold:通过经验和训练确定初始值，在反馈过程中调整。ProfileAdaptationOptimizationfortwoMeasurementfunctionsRocchio反馈算法:Pn+1=Pn+a*Dpos+b*Dneg+b’*DundTREC-10filtering存在问题大集合结果好，小集合结果很差，零太多优化方法太简单特征选择有待改进是否尝试语义特征项？TREC-11filtering算法的改进改进了原来的互信息特征选择算法，在整个训练集上计算各个topic的特征词，由3个种子和适量的扩展文档组成“相关文档集”，训练集中剩下的文档作为“不相关文档集”。鉴于TREC-11的topic改为TREC风格后，原来的特征选择算法几乎失效，故最后直接用3个种子，原始topic和扩展产生的伪相关文档按照一定的比例混合构成原始的profile。改进了原来的针对TREC目标函数的优化算法，引入了局部最优策略，追求各个反馈区间的局部最优值来达到全局的最优值；同时尽量避免‘0’返回的出现。对小样本训练集进行优化处理：根据扩展时伪相关文档数的多少决定是否应扩大“正例样本集”，小于某一阈值的样本集将被复制若干遍。TREC-11改进算法在TREC-10上的实验实验结果表明，改进的特征选择算法略好于旧的特征选择算法，并且可以控制小样本训练集的优化。二者结合的结果由原来的0.207上升到0.220，约提高6%。局部最优策略的引入是成功的，可进一步使结果由0.220增加到0.270，约提高23%。TREC-11跟TREC-10filtering的差别Topic形式由Reuters类别变为TREC格式，数目由84个增加到100个，每个topic的已知正例数目由2个变为3个。不再给出训练/测试集合中的全部正反例答案，改为只给出部分正例和反例，训练/测试集合中的其他文档将作为未判定文档对待。即过滤过程中的反馈是不充分的。U目标函数的归一化方法有所变化，相同的U值归一化后T11SU约为T10SU的两倍。TREC-11filtering的主要困难由于测试集合的标准答案只给出一部分，因而过滤时继续使用原来的优化策略无法获得充分的反馈信息；已知的部分答案在整个测试集合中所占的比例无法得知，因而不能控制未判定文档(undetermined)的返回比例，从而无从把握最终返回文档的数量。原来的优化策略有些可能不再适用，需要重新修正。TREC-11filtering的反馈试验(1)鉴于已知正反例答案的不完全性，我们已经尝试了3种方法控制过滤反馈的效用：（1）通过正例/反例的相对比例来调节过滤阈值，即不考虑返回结果中的未判定文档。缺点：不能保证在已知正反例构成的小集合上很好的结果可以推广到整个测试集合上，取决于各个topic的实际相关文档在整个测试集上的具体分布情况。TREC-11filtering的反馈试验(2)（2）利用过滤时获得的正反例信息构造正例中心和反例中心，再用正反例中心分割未判定文档，形成伪正例/伪反例集合，从而模拟出已知整个测试集的正反例答案的情况，这使得TREC-10的优化策略可以继续使用。优点：返回文档的数量较多，当实际相关文档较多时有优势。缺点：正反例中心的初值似乎对未判定文档的分类影响很大，目前还没有找到较好的构造方法。TREC-11filtering的反馈试验(3)（3）假定测试集合中已知的相关文档足够多，据此把过滤时遇到的未判定文档大部或者全部作为反例文档对待。优点：可以有效控制返回文档的数量。缺点：不能保证假设成立，当实际相关文档确实较少时有优势；但是当实际相关文档集合较已知正例答案大很多时，损失也大。TREC-11filtering最终的反馈方案TREC-11filteringmailinglist的讨论表明，方案三的假设比较合理。根据以上实验结果的比较分析，最终确定以方案三为基础，经过改进后形成最终的反馈方案。优化方案仍采用局部最优策略，然后针对未判定文档的处理作相应调整。ICTTREC-11filtering的结果

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结果(50Assessortopics)ICTTREC-11filtering的结果

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结果(50Intersectiontopics)ICTTREC-11filtering的结果

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结果(all100topics)ICTTREC-11filtering的结果

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结果跟baseline的比较(all100topics)结论对50个assessortopic效果很好，自然语言描述中包含丰富的信息。对50个intersectiontopic效果不是很好，但是对于其中正确结果较多的topic效果也还行。排名未知，预计名列前茅＝>排名第一!排名情况根据T11SU(14)ICT 0.405KerMIT0.390CMU 0.369CLIPS-IMAGLab0.349

MicrosoftCambridge0.343(微软剑桥研究院)根据T11F(14)ICT 0.245KerMIT、Thu0.237CMU 0.2315MicrosoftCambridge0.2305每个run得分情况(T11SU)每个run得分情况(T11F)WEBTrackNamedPageFinding找到用户命名的网页，例如

passportapplicationformTopicDistillation找到与内容相关的keyresource,可以是相关站点的主页相关子站点的主页高度相关的单个页面Hub页面数据集.Gov数据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>系统框架指导原则：以Wt10g为训练集，指导Gov数据集上的试验。组织形式：考虑到实际情况，以松散耦合的形式为主，系统的组成部分相对独立，每一部分考虑一个单独的因素，最后以线性组合的形式综合考虑。组成部分纯内容文档结构(标题，格式信息等)链接文本(anchortext)URL分析链接分析内容检索经过对比试验，选定了Lnu-Ltu(pivoteddocumentlengthnormalization)方式作为内容权重计算公式。在Wt10g上，topic501-550的一次检索平均准确率为0.1939(去年的结果是0.08，第一名是0.2226)，达到OKAPI的水平；使用纯内容检索得到的homepagefinding任务的结果的MRR达到0.4185，超过上届参加者使用内容检索得到的结果。文档结构信息结构信息对于文档的精确定位有重要作用。由于超文本分析的复杂性，目前只使用了文档的title域。单独使用结构信息进行检索，homepagefinding任务的结果MRR达到了0.4467，高于内容检索。链接分析试图利用文档之间的链接关系发现重要资源主要利用HITS算法(hub,authority)原始算法存在缺陷，主要是计算结果存在topicdrift现象，不再和原主题紧密相关。对算法的迭代过程进行了改进，把页面的内容相关值(由内容检索得到)作为一个因子乘在hub和authority上，并对排名靠后的页面的影响度进行了衰减。结果有所改善，但仍不能取得满意的结果。链接文本链接文本在检索中所起的作用类似于结构信息，有助于文档的精确的定位。单独使用链接文本检索，homepagefinding的MRR值达到0.3769，略低于内容检索的结果。URL分析尝试利用URL包