TREC概况及TREC-11简介,中科院计算所软件室 王 斌 2002.12.4,主要内容,一、TREC概况 二、TREC评测方法及标准 三、TREC-11 介绍以及我们的工作,第一部分 TREC概况,TREC的历史、发展与目标,TREC的运行过程,TREC由一个程序委员会(包括来自政府、工业界和学术界的代表)管理。 TREC以年度为周期运行。过程为： 确定任务(12): NIST选择某些任务，制定规范 参加者报名(23):参加者根据自己的兴趣选择任务（报名免费，大部分数据也免费！） 参加者运行任务(39):参加者用自己的系统运行测试问题，给出结果并将它们提交给NIST 结果评估(10): NIST使用固定的评测软件和工具对结果进行评估，并将结果返回给参加者 大会交流(11 马里兰州的Gaithersburg)：论文交流,Yearly Conference Cycle,TREC目标,总目标：支持在信息检索领域的基础研究，提供对大规模文本检索方法的评估办法 1.鼓励对基于大测试集合的信息检索方法的研究 2.提供一个可以用来交流研究思想的论坛，增进工业界、学术界和政府部门之间的互相了解； 3.示范信息检索理论在解决实际问题方面的重大进步，提高信息检索技术从理论走向商业应用的速度 4.为工业界和学术界提高评估技术的可用性，并开发新的更为适用的评估技术。,历届TREC参加单位数及任务,历届TREC参加单位数示意图,参加过TREC的部分单位,测试数据和测试软件,由LDC(Linguistic Data Consortium)等多家单位免费提供，但少数数据有所修改，而且必须签订协议 每年使用的数据可以是新的，也可以是上一年度已经使用过的 TREC使用的评估软件是开放的，任何组织和个人都可以用它对自己的系统进行评测,第二部分 TREC评测方法及标准,相关名词、评测方法,名词定义,Track TREC的每个子任务，QA Filtering Web Topic 预先确定的问题，用来向检索系统提问 topicquery (自动或者手工) Question (QA) Document 包括训练集和测试集合 (TIPSTER space travel & exploration. ,TREC-10 Filtering的topic(对比), R17 R18 C31 C311 MARKETS/MARKETINGDOMESTIC MARKETS R19 R21 C312 C32 EXTERNAL MARKETSADVERTISING/PROMOTION ,数据集,使用Reuters Corpus Volume 1,来自Reuters Training Set: 83,650篇文档,大约400M。 Testing Set：720,000多文档,大约5G。 辅助数据： 供反馈的答案集合(每个Topic和每篇文档在该集合中可能存在三种关系：相关，不相关，未知，TREC11增加了未知一项，防止作弊) 文件访问的顺序。 程序运行时间：TREC-11约为4小时，20M/m (TREC-10约为9.5小时,主要是由于反馈量减少),Adaptive filtering 系统框架,Filtering评估方法,Adaptive & Batch filtering Utility=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，T11F Routing：类似于Web：Average Precision,Adaptive Filtering 主要算法,Adaptive filtering 在tf*idf模型的实现上由原来的tf*log(N/n)改为log(tf)*log(N/n) Profile Initializing 3 positive samples + 适当比例的Topic + 根据前两者从训练集中筛选出来的适量伪正例。 Threshold: 通过经验和训练确定初始值，在反馈过程中调整。 Profile Adaptation Optimization for two Measurement functions Rocchio反馈算法: Pn+1=Pn+a*Dpos+b*Dneg +b*Dund,TREC-10 filtering存在问题,大集合结果好，小集合结果很差，零太多 优化方法太简单 特征选择有待改进 是否尝试语义特征项？,TREC-11 filtering算法的改进,改进了原来的互信息特征选择算法，在整个训练集上计算各个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-10 filtering的差别,Topic形式由Reuters类别变为TREC格式，数目由84个增加到100个，每个topic的已知正例数目由2个变为3个。 不再给出训练/测试集合中的全部正反例答案，改为只给出部分正例和反例，训练/测试集合中的其他文档将作为未判定文档对待。即过滤过程中的反馈是不充分的。 U目标函数的归一化方法有所变化，相同的U值归一化后T11SU约为T10SU的两倍。,TREC-11 filtering的主要困难,由于测试集合的标准答案只给出一部分，因而过滤时继续使用原来的优化策略无法获得充分的反馈信息； 已知的部分答案在整个测试集合中所占的比例无法得知，因而不能控制未判定文档(undetermined)的返回比例，从而无从把握最终返回文档的数量。 原来的优化策略有些可能不再适用，需要重新修正。,TREC-11 filtering的反馈试验(1),鉴于已知正反例答案的不完全性，我们已经尝试了3种方法控制过滤反馈的效用： （1）通过正例/反例的相对比例来调节过滤阈值，即不考虑返回结果中的未判定文档。 缺点：不能保证在已知正反例构成的小集合上很好的结果可以推广到整个测试集合上，取决于各个topic的实际相关文档在整个测试集上的具体分布情况。,TREC-11 filtering的反馈试验(2),（2）利用过滤时获得的正反例信息构造正例中心和反例中心，再用正反例中心分割未判定文档，形成伪正例/伪反例集合，从而模拟出已知整个测试集的正反例答案的情况，这使得TREC-10的优化策略可以继续使用。 优点：返回文档的数量较多，当实际相关文档较多时有优势。 缺点：正反例中心的初值似乎对未判定文档的分类影响很大，目前还没有找到较好的构造方法。,TREC-11 filtering的反馈试验(3),（3）假定测试集合中已知的相关文档足够多，据此把过滤时遇到的未判定文档大部或者全部作为反例文档对待。 优点：可以有效控制返回文档的数量。 缺点：不能保证假设成立，当实际相关文档确实较少时有优势；但是当实际相关文档集合较已知正例答案大很多时，损失也大。,TREC-11 filtering最终的反馈方案,TREC-11 filtering mailing list的讨论表明，方案三的假设比较合理。 根据以上实验结果的比较分析，最终确定以方案三为基础，经过改进后形成最终的反馈方案。 优化方案仍采用局部最优策略，然后针对未判定文档的处理作相应调整。,ICT TREC-11 filtering的结果,Table 1 ICT TREC-11 adaptive filtering结果(50 Assessor topics),ICT TREC-11 filtering的结果,Table 2 ICT TREC-11 adaptive filtering结果(50 Intersection topics),ICT TREC-11 filtering的结果,Table 3 ICT TREC-11 adaptive filtering结果(all 100 topics),ICT TREC-11 filtering的结果,Table 4 ICT TREC-11 adaptive filtering结果跟baseline的比较 (all 100 topics),结论,对50个assessor topic 效果很好，自然语言描述中包含丰富的信息。 对50个intersection topic效果不是很好，但是对于其中正确结果较多的topic效果也还行。 排名未知，预计名列前茅排名第一!,排名情况,根据T11SU(14) ICT0.405 KerMIT 0.390 CMU0.369 CLIPS-IMAG Lab 0.349 Microsoft Cambridge 0.343 (微软剑桥研究院) 根据T11F(14) ICT0.245 KerMIT、Thu 0.237 CMU0.2315 Microsoft Cambridge 0.2305,每个run得分情况(T11SU),每个run得分情况(T11F),WEB Track,Named Page Finding 找到用户命名的网页，例如passport application form Topic Distillation 找到与内容相关的key resource,可以是 相关站点的主页 相关子站点的主页 高度相关的单个页面 Hub页面,数据集,.Gov数据 A crawl of .gov Web sites (early 2002). Stopped after 1 million text/html pages Also including text/plain and the extracted text of pdf, doc and ps. 18G 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 individual 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 Numbe