计算所软件室TREC-11报告.ppt

《计算所软件室TREC-11报告.ppt》由会员分享，可在线阅读，更多相关《计算所软件室TREC-11报告.ppt（72页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、TREC概况及TREC-11简介中科院计算所软件室 王 斌 主要内容一、TREC概况二、TREC评测方法及标准三、TREC-11 介绍以及我们的工作第一部分 TREC概况TREC的历史、发展与目标TREC的历史TRECnTextREtrievalConference，文本检索会议n一开始仅仅面向文本，现在处理对象更广n情报分析和处理组织者nNIST(NationalInstituteofStandardsandTechnology)，政府部门nDARPA(DefenseAdvancedResearchProjectsAgency)，军方会议情况n评测会议n19922002，11届TREC的运行

2、过程TREC由一个程序委员会(包括来自政府、工业界和学术界的代表)管理。TREC以年度为周期运行。过程为：n确定任务(12):NIST选择某些任务，制定规范n参加者报名(23):参加者根据自己的兴趣选择任务（报名免费，大部分数据也免费！）n参加者运行任务(39):参加者用自己的系统运行测试问题，给出结果并将它们提交给NISTn结果评估(10):NIST使用固定的评测软件和工具对结果进行评估，并将结果返回给参加者n大会交流(11 马里兰州的Gaithersburg)：论文交流Yearly Conference CycleTREC目标总目标：支持在信息检索领域的基础研究，提供对大规模文本检索方法的

3、评估办法n1.鼓励对基于大测试集合的信息检索方法的研究n2.提供一个可以用来交流研究思想的论坛，增进工业界、学术界和政府部门之间的互相了解；n3.示范信息检索理论在解决实际问题方面的重大进步，提高信息检索技术从理论走向商业应用的速度n4.为工业界和学术界提高评估技术的可用性，并开发新的更为适用的评估技术。历届TREC参加单位数及任务Org.TracksTREC125Ad hoc/Routing TREC231Ad hoc/Routing TREC332Ad hoc/Routing TREC436Spanish/Interactive/Database Merging/Confusion/Fil

4、teringTREC538Spanish/Interactive/DatabaseMerging/Confusion/Filtering/NLP TREC651Chinese/Interactive/Filtering/NLP/CLIR/Highprecision/SDR/VLCTREC756CLIR/High Precision/Interactive/Query/SDR/VLC TREC866CLIR/Filtering/Interactive/QA/Query/SDR/WebTREC970QA/CLIR(E-C)/Web/Filtering/Interactive/Query/SDR T

5、REC1089QA/CLIR/Web/Filtering/Interactive/Video TREC1195QA/CLIR/Web/Filtering/Interactive/Video/Novelty/历届TREC参加单位数示意图参加过TREC的部分单位Corp.Corp.UniversityUniversityAsian OrganizationAsian OrganizationIBMMITSingapore U.(KRDL)AT&TCMUKAISTMicrosoftCambridge U.Korea U.SunCornell U.Pohang U.(釜项?)AppleMaryland

6、 U.Tinghua U.(Mainland，清华)TREC11FujitsuMassachusetts U.Tsinghua U.(Taiwan)TREC7NECNew Mexico State U.Taiwan U.TREC8&9&10XEROXCalifornia Berkeley U.Hongkong Chinese U.TREC9RICOHMontreal U.Microsoft Research China TREC9&10CLRITECH Johns Hopkins U.Fudan U.TREC9&10&11(复旦)NTTRutgers U.ICT TREC10&11(中科院计算

7、所)OraclePennsylvania U.HIT TREC10(哈工大)测试数据和测试软件由LDC(Linguistic Data Consortium)等多家单位免费提供，但少数数据有所修改，而且必须签订协议每年使用的数据可以是新的，也可以是上一年度已经使用过的TREC使用的评估软件是开放的，任何组织和个人都可以用它对自己的系统进行评测第二部分 TREC评测方法及标准相关名词、评测方法名词定义TracknTREC的每个子任务，QA Filtering WebTopicn预先确定的问题，用来向检索系统提问ntopicquery(自动或者手工)nQuestion(QA)Documentn包括

8、训练集和测试集合(TIPSTER&TREC CDs)Relevance Judgmentsn相关性评估，人工或者自动Topic的一般结构Title：标题，通常由几个单词构成，非常简短Description：描述，一句话，比Title详细，包含了Title的所有单词Narrative：详述，更详细地描述了哪些文档是相关的Topic示例 Number:351 Falkland petroleum exploration Description:What information is available on petroleum exploration in the South Atlantic n

9、ear the Falkland Islands?Narrative:Any document discussing petroleum exploration in the South Atlantic near the Falkland Islands is considered relevant.Documents discussing petroleum exploration in continental South America are not relevant.使用Topic的方式按照会议要求，可以利用Topic文本中的部分或者全部字段，构造适当的查询条件可以使用任何方式构造查

10、询条件，这包括手工的和自动的两大类。但提交查询结果时要注明产生方式。评测方法基于无序集合的评测：返回结果无顺序nSet Precision/Set Recall基于有序集合的评测：nPn/Average Precision/Reciprocal Rank其他评测方法nFiltering Utility相关性评估过程(1)对于每一个topic，NIST从参加者取得的结果中挑选中一部分运行结果，从每个运行结果中取头100个文档，然后用这些文档构成一个文档池，使用人工方式对这些文档进行判断。相关性判断是二值的：相关或不相关。没有进行判断的文档被认为是不相关的。相关性评估过程(2)NIST使用trec

11、_eval软件包对所有参加者的运行结果进行评估，给出大量参数化的评测结果（主要是precision和recall)。根据这些评测数据，参加者可以比较彼此的系统性能。其他track也有相应的公开评测工具第三部分 TREC-11 主要任务介绍以及我们的工作目的、方法与结果TREC-11的所有TracksCLIR(Use English Topic to Retrieve Arabic Documents)Filtering(Filter out relevant documents)Interactive(Construct the best query)Question Answering(Fi

12、nd answer fragments)Video(Retrieve Digital Video)Web(Retrieve Web pages)Novelty(Retrieve new relevant docs)Genomic Data pre-track参加TREC11的单位TREC-11 Filtering 任务Goaln 顺序扫描文档流中的每个文档，在当前的query下，确定是否要检出。数据集nTopic Set：100个topic，两种风格。nTraining Set:83,650nTesting Set：720,000子任务nAdaptive Filtering：每个Topic只给

13、出三个训练正例nBatch Filtering：每个Topic给出Training Set中的所有正例Routing：同Batch Filtering，但返回结果要排序应用场景个性化网络信息推送敏感信息发现网络信息分类个人兴趣的跟踪Topic集合Topicnassessor topics:前50(101-150)个topic为传统的TREC风格，是由NIST的裁判员手工构造的；nintersection topics:后50(151-200)个topic由Reuters Corpus的若干个类别组合而成，叫做intersection topics，是自动构造的。n每个topic包括title,

14、description和narrative三部分，各部分均可用于过滤过程。n100个topic统一处理，结果分别评测。assessor topic Number:R101 Economic espionage Description:What is being done to counter economic espionage internationally?Narrative:Documents which identify economic espionage cases and provide action(s)taken to reprimand offenders or termi

15、nate their behavior are relevant.Economic espionage would encompass commercial,technical,industrial or corporate types of espionage.Documents about military or political espionage would be irrelevant.intersection topic Number:R151 Markets/marketing,Science And Technology Description:Markets and mark

16、eting,Science And Technology Narrative:Relevant documents discuss sales,markets,marketing,market research,product pricing concerning all aspects of science,research and new technology;space travel&exploration.TREC-10 Filtering的topic(对比)R17 R18 C31 C311MARKETS/MARKETINGDOMESTIC MARKETS R19 R21 C312 C

17、32 EXTERNAL MARKETSADVERTISING/PROMOTION 数据集使用Reuters Corpus Volume 1,来自Reuters nTraining Set:83,650篇文档,大约400M。nTesting Set：720,000多文档,大约5G。n辅助数据：w供反馈的答案集合(每个Topic和每篇文档在该集合中可能存在三种关系：相关，不相关，未知，TREC11增加了未知一项，防止作弊)w文件访问的顺序。程序运行时间：TREC-11约为4小时，20M/m(TREC-10约为9.5小时,主要是由于反馈量减少)Adaptive filtering 系统框架特征选择用

18、户兴趣(Profile)初始化扫描文档计算Profile/文档的相似度Profile调整训练集合相似度阈值？YesNo输出结果文档Yes/No/不确定是否相关？Filtering评估方法Adaptive&Batch filteringnUtility=A*R+B*N+C*R-+D*N-nT11U=2*R+-N+nP=R+/(R+N+),R=R+/(R+R-)nT11F=1.25/(0.25/R+1/P)n归一化平均得到T11SU，T11FRouting：类似于Web：Average PrecisionRelevant(含未判定doc)Not Relevant(含未判定doc)Retrieved

19、R+/A N+/B Not RetrievedR-/C N-/D Adaptive Filtering 主要算法Adaptive filteringn在tf*idf模型的实现上由原来的tf*log(N/n)改为log(tf)*log(N/n)nProfile Initializingw3 positive samples+适当比例的Topic+根据前两者从训练集中筛选出来的适量伪正例。wThreshold:通过经验和训练确定初始值，在反馈过程中调整。nProfile AdaptationwOptimization for two Measurement functionswRocchio反馈算

20、法:Pn+1=Pn+a*Dpos+b*Dneg+b*DundTREC-10 filtering存在问题大集合结果好，小集合结果很差，零太多优化方法太简单特征选择有待改进是否尝试语义特征项？TREC-11 filtering算法的改进改进了原来的互信息特征选择算法，在整个训练集上计算各个topic的特征词，由3个种子和适量的扩展文档组成“相关文档集”，训练集中剩下的文档作为“不相关文档集”。鉴于TREC-11的topic改为TREC风格后，原来的特征选择算法几乎失效，故最后直接用3个种子，原始topic和扩展产生的伪相关文档按照一定的比例混合构成原始的profile。改进了原来的针对TREC目标

21、函数的优化算法，引入了局部最优策略，追求各个反馈区间的局部最优值来达到全局的最优值；同时尽量避免0返回的出现。对小样本训练集进行优化处理：根据扩展时伪相关文档数的多少决定是否应扩大“正例样本集”，小于某一阈值的样本集将被复制若干遍。TREC-11改进算法在TREC-10上的实验实验结果表明，改进的特征选择算法略好于旧的特征选择算法，并且可以控制小样本训练集的优化。二者结合的结果由原来的0.207上升到0.220，约提高6%。局部最优策略的引入是成功的，可进一步使结果由0.220增加到0.270，约提高23%。TREC-11跟TREC-10 filtering的差别Topic形式由Reuters

22、类别变为TREC格式，数目由84个增加到100个，每个topic的已知正例数目由2个变为3个。不再给出训练/测试集合中的全部正反例答案，改为只给出部分正例和反例，训练/测试集合中的其他文档将作为未判定文档对待。即过滤过程中的反馈是不充分的。U目标函数的归一化方法有所变化，相同的U值归一化后T11SU约为T10SU的两倍。TREC-11 filtering的主要困难由于测试集合的标准答案只给出一部分，因而过滤时继续使用原来的优化策略无法获得充分的反馈信息；已知的部分答案在整个测试集合中所占的比例无法得知，因而不能控制未判定文档(undetermined)的返回比例，从而无从把握最终返回文档的数量

23、。原来的优化策略有些可能不再适用，需要重新修正。TREC-11 filtering的反馈试验(1)鉴于已知正反例答案的不完全性，我们已经尝试了3种方法控制过滤反馈的效用：（1）通过正例/反例的相对比例来调节过滤阈值，即不考虑返回结果中的未判定文档。n缺点：不能保证在已知正反例构成的小集合上很好的结果可以推广到整个测试集合上，取决于各个topic的实际相关文档在整个测试集上的具体分布情况。TREC-11 filtering的反馈试验(2)（2）利用过滤时获得的正反例信息构造正例中心和反例中心，再用正反例中心分割未判定文档，形成伪正例/伪反例集合，从而模拟出已知整个测试集的正反例答案的情况，这使得

24、TREC-10的优化策略可以继续使用。n优点：返回文档的数量较多，当实际相关文档较多时有优势。n缺点：正反例中心的初值似乎对未判定文档的分类影响很大，目前还没有找到较好的构造方法。TREC-11 filtering的反馈试验(3)（3）假定测试集合中已知的相关文档足够多，据此把过滤时遇到的未判定文档大部或者全部作为反例文档对待。n优点：可以有效控制返回文档的数量。n缺点：不能保证假设成立，当实际相关文档确实较少时有优势；但是当实际相关文档集合较已知正例答案大很多时，损失也大。TREC-11 filtering最终的反馈方案TREC-11 filtering mailing list的讨论表明，

25、方案三的假设比较合理。根据以上实验结果的比较分析，最终确定以方案三为基础，经过改进后形成最终的反馈方案。优化方案仍采用局部最优策略，然后针对未判定文档的处理作相应调整。ICT TREC-11 filtering的结果Run IDMeanT11UT11U vs.median(topic nums)MeanT11FT11F vs.median(topic nums)(Best)=(Best)=(Best)=(Best)=(Best)=(Best)=ICTAdaFT11Ua0.40543/7/500/5/57/38/45ICTAdaFT11Ub0.402543/7/500/5/57/38/45ICT

26、AdaFT11Uc0.40341/7/480/5/59/38/47ICTAdaFT11Fd0.280519/2/210/0/031/48/79Best-performing?50/12/620/?/?0/?/排名第一!排名情况根据T11SU(14)nICT0.405nKerMIT 0.390nCMU0.369nCLIPS-IMAG Lab 0.349 nMicrosoft Cambridge 0.343(微软剑桥研究院)根据T11F(14)nICT0.245nKerMIT、Thu 0.237nCMU0.2315nMicrosoft Cambridge 0.2305每个run得分情况(T11SU

27、)每个run得分情况(T11F)WEB TrackNamed Page Findingn找到用户命名的网页，例如passport application formTopic Distillationn找到与内容相关的key resource,可以是w相关站点的主页w相关子站点的主页w高度相关的单个页面wHub页面数据集.Gov数据nA crawl of.gov Web sites(early 2002).nStopped after 1 million text/html pages nAlso including text/plain and the extracted text of pd

28、f,doc and ps.n18G Documents truncated to 100k(reducing size from 35G to 18G)TOPIC集合(1)Topic distillation:50个 Number:obesity in the U.S.Description:Find resources describing the dangers,the prevalence,prevention or treatment of obesity in the U.S.Narrative:Relevant resources describe programs or indi

29、vidual efforts to treat obesity in the U.S.Also relevant are those documenting the prevalence of obesity.To be relevant overweight must be gross and medically defined as obese.Grant proposals for research on this problem are not relevant.Topic集合(2)Named Page Finding:150 Number:NP3 Description:Volunt

30、eer FEMA World Trade Center 系统框架指导原则：以Wt10g为训练集，指导Gov数据集上的试验。组织形式：考虑到实际情况，以松散耦合的形式为主，系统的组成部分相对独立，每一部分考虑一个单独的因素，最后以线性组合的形式综合考虑。组成部分纯内容文档结构(标题，格式信息等)链接文本(anchor text)URL分析链接分析内容检索经过对比试验，选定了Lnu-Ltu(pivoted document length normalization)方式作为内容权重计算公式。在Wt10g上，topic 501-550的一次检索平均准确率为0.1939(去年的结果是0.08，第一名是

31、0.2226)，达到OKAPI的水平；使用纯内容检索得到的homepage finding任务的结果的MRR达到0.4185，超过上届参加者使用内容检索得到的结果。文档结构信息结构信息对于文档的精确定位有重要作用。由于超文本分析的复杂性，目前只使用了文档的title域。单独使用结构信息进行检索，homepage finding任务的结果MRR达到了0.4467，高于内容检索。链接分析试图利用文档之间的链接关系发现重要资源主要利用HITS算法(hub,authority)原始算法存在缺陷，主要是计算结果存在topic drift现象，不再和原主题紧密相关。对算法的迭代过程进行了改进，把页面的内容

32、相关值(由内容检索得到)作为一个因子乘在hub和authority上，并对排名靠后的页面的影响度进行了衰减。结果有所改善，但仍不能取得满意的结果。链接文本链接文本在检索中所起的作用类似于结构信息，有助于文档的精确的定位。单独使用链接文本检索，homepage finding的MRR值达到0.3769，略低于内容检索的结果。URL分析尝试利用URL包含的文本信息进行检索单独使用URL信息检索的结果，MRR为0.2104，准确率较低与内容检索所得结果进行组合，最高可提高MRR 11%，但较难调整参数。经过分析，发现利用URL发现的较好结果包括在利用anchor text和结构信息所得结果中，因此U

33、RL分析没有使用在今年的结果中。实验结果-Named Page FindingRunIDMRRFoundedAnswersNotFoundictnp20.559114/15018/150ictnp30.557116/15018/150ictnp40.555116/15018/150ictnp60.613127/15014/150ictnp70.613127/15014/150TREC11 Name Page Finding结果TREC11 NamePageFinding 结果实验结果-Topic DistillationRunIDAveragePrecisionR-PrecisionRel_r

34、eticttd10.16200.19191038/1574icttd20.13640.15991038/1574icttd30.05970.1034288/1574TREC11 Topic Distillation 结果Topic Distillation排名情况排名情况(单位RunIDP10P20MAP)nTsinghuathutd50.2510 0.1959 0.1571ncity-plierspltr02wt20.2408 0.1929 0.1645nICTicttd10.2306 0.1806 0.1620 nibm_haifaibmhaifapr0.2286 0.1765 0.157

35、1 nGlasgowuog05tad0.2224 0.1765 0.1540n按照传统排名指标MAP列第二位。Topic Distillation结果Named Page Finding排名排名情况(MMR 单位 RunID Doc Anchor Link)n0.719 tsinghua thunp3 D An0.676 cmu lti lmralleq D An0.671 yonsei yenp01 D A Ln0.654 glasgow uog07cta D An0.636 neuchatel uninenp1 D An0.626 hummingbird hum02pd Dn0.613 chinese academy ictnp6 D ANamed Page Finding结果结论取得了令人鼓舞的结果某些因素可能在一些新的任务中起确定性的作用我们可以在新的任务中大显身手排名：nTopic Distillation排名第三(18)nNamed Page Finding排名第七(19)总结论和展望和应用相结合继续跟踪和交流明年继续参加谢谢！