搜索引擎技术：性能提高遇到瓶颈

2006-08-10 13:34:17.08
骆卫华 刘群 张俊林
计世网 评估搜索引擎背后的信息检索技术的先进性，验证互联网环境下大规模数据的信息检索技术的系统有效性，推动检索技术的进步和成果转化，这是信息检索技术评测的主要目标。
互联网蓬勃兴起使人们摆脱了信息贫乏的桎梏，进入了一个信息极度丰富的时代。比如，今天仅Google能索引到的网页就超过80亿个，图片超过10亿张。当信息的来源不再是问题时，如何快捷准确地获取感兴趣的信息就成为人们关注的主要问题。因此，以Web搜索引擎为代表的 Google、百度、Yahoo都取得了很大成功。然而，基于不同的信息检索技术发展而来的搜索引擎系统，对于同一个用户查询其结果往往存在差异，由此产生了比较结果的需求。而基于主观使用感受的评价既不客观也不可靠，因此，必须提出一套客观的评测体系，这种评测不受个别人主观感觉的影响，并且所做出的评价在通常情况下都成立。这种评测研究的方法具有以下特点：明确的形式化研究任务、公开的训练与测试数据、公开的评测比较。它使得研究之间的比较更加客观，从而让研究者认清各种技术的优劣，起到正确引导研究发展方向的目的。
信息检索技术的现状
提及信息检索，大家往往马上会想起Google、Yahoo等搜索引擎公司。可以说，Web搜索引擎与大家的日常生活最为密切，在某种程度上成了信息检索技术的代称。但作为实用化的系统，搜索引擎一般采用比较成熟的技术，并对稳定性、反映速度、界面等工程化问题更为关注。因此，这些系统并不完全代表信息检索技术的发展水平。
由于人们对于各种粒度的信息获取的需求不断增长，国外的学术界和企业界对为此投入了相当大的力量进行前瞻性研究，这方面比较有代表性的机构是马萨诸塞大学、卡耐基梅隆大学、伦敦城市大学、IBM、微软研究院、滑铁卢大学等。
总的来看，早期以Okapi、Smart、查询扩展、相关反馈为代表的内容分析技术，后来以Pagerank、HITS为代表的链接分析技术，以及近年来的语言模型，都曾在信息检索发展过程中掀起研究热潮，但近年来却少有激动人心的新技术出现。2005年，TREC在其总结报告指出现在“信息检索性能已进入平台期”。这表明，用户无关的传统信息检索技术已相对成熟。这些技术已经被商用搜索引擎广泛应用，并在一定程度上解决了用户在粗粒度（文档级）上的信息获取需求。
从TREC来看，现在的任务设置向高精度、细粒度和大规模三个方向倾斜，比较有代表性的有高精度文档检索任务（HARD）、新信息检测任务（Novelty）、问答任务（QA）、TB级检索（Terabyte）等。其中前三个任务要求返回的结果不再是简单的一篇篇文档，而是信息片断，而TB级检索则是把测试集的规模提高到了TB级，其他不变。从评测结果来看，这些任务已经取得了很大进展。但相对于目前的技术而言，这些任务还是相当困难的，与实用还有一段距离。
总的来看，国外主流的Web检索技术已比较成熟，无论从结果、性能还是稳定性来看，都能提供令人满意的结果，并且已经在人们的日常信息获取中发挥作用。更高精度和更细粒度的检索技术仍处于实验室阶段，但这方面的研究方兴未艾。也许在不远的将来，我们就能看到基于这些新技术的搜索引擎的出现。而推动信息检索技术的不断进步正是信息检索评测索要达到的目标。
信息检索评测
作为扶持科技发展的重要措施之一，863国家高技术研究发展计划一直对国内的研究有着重要影响。而规范化评测作为检验系统性能的可信机制，逐渐成为 863关注的重点之一。2003年，国家863计划软硬件主题设立了“中文信息处理和智能人机接口技术评测”专项课题，对包括机器翻译、语音识别、信息检索在内的中文信息处理关键技术进行评测。信息检索评测的目的并不仅仅定位为863课题验收或资格认证，而是要了解国内在中文信息检索技术领域的研究现状，验证互联网环境下大规模数据的中文信息检索技术的系统有效性，推动技术进步和成果的应用和转化，成为这个领域技术评价和交流的平台。
从2003年开始，连续三届信息检索评测在任务设置和组织形式上有所不同，如表1所示：
时间 评测任务 评测形式 参加单位
2003.10.28 全文检索 现场评测 北京语言大学语言信息处理研究所
复旦大学计算机科学与工程系
清华大学智能技术与系统国家重点实验室
2004.10.19 文档检索 现场评测 北京语言文化大学
段落检索 哈尔滨工业大学检索组
哈尔滨工业大学语言组
南京大学
清华大学智能技术与系统实验室
2005.9.20-9.22 相关网页检索 网上评测 北京大学计算机技术研究所
北京邮电大学模式识别实验室
哈尔滨工业大学信息检索研究室
清华大学智能技术与系统国家重点实验室
中国科学院自动化研究所
表1
2003年度评测只有一个子任务，即全文检索核心技术评测，但测试在小规模和大规模两种数据集上进行，目的是更为全面地考察系统的性能。其中小规模数据评测主要侧重于奥运领域文本的检索。检索题目
以及标准答案委托中科院软件所人工完成，在精选的数千篇网页上设计了20道检索题目，其中体育类 15道。大规模数据采用从国内9个网站采集的约100多万篇网页作为评测数据，规模达到GB级。检索题目由中科院计算所设计，共18道，选题领域广泛，包括政治、经济、文化、体育等诸多方面。对大规模数据集，不可能全部通过人工方式制作出标准答案。因此，这里采用了一种称为Pooling的方法。该方法最早由Jones和Rijsbergen提出，并在TREC中得到广泛应用和检验，其思想是：针对每个查询主题，从参与评比的各系统所送回的测试结果中抽取出前若干篇文档，合并形成一个文档池（Pool），视之为该查询主题可能的相关文档候选集合，将集合中重复的文档去除后，再送给该查询集的构建者进行相关判断。
2004年度评测的任务变为两项，即文档检索和段落检索。其中文档检索要求参评者对每个查询条件返回以文档为单位的检索结果；而段落检索要求参评者以段落为单位给出检索结果，段落的具体定义和长短可由参评者自由选择。为了引导参赛单位研究更具实用性的技术，本次测试还增加了对检索速度的评测。两个任务的评测语料都是由北大天网提供的15GB的中文简体网页。组织方在这些数据上拟定了30个查询条件。由于参赛队伍较少，2003年的评测中Pooling技术没有有效发挥作用，因此本次评测集的答案采用Pooling和人工相结合的方法生成，即利用检索工具以及段落查找辅助工具同时结合人工判断形成了初步标准答案，在各队提交了检索结果后，又利用Pooling方法对初步标准答案进行调整形成最终的标准答案。
随着参评单位来源的扩大以及测试集规模的增长，以往把系统在测试现场安装、运行并提交结果的模式面临很多问题。于是，借鉴国外著名评测会议的经验，2005年的评测以网上测试代替现场测试。9月20日，组织方通过官方网站（www.863data.org.cn）发布测试数据，要求参评单位在22日之前提交运行结果。本届信息检索评测影响力迅速扩大，在组织过程中得到了中科院软件所、北京大学、微软亚洲研究院等单位的鼎力协助。本届评测只安排了相关网页检索子任务，要求给定主题，返回测试集中与该主题相关的网页并按相关度排序。参加评测的单位通过自动方式和人工方式根据主题构造查询。自动方式是指在没有任何人为因素的影响下根据主题构造查询的方式，除此之外的方式均为人工方式。
本次评测的任务的难度比以往大大增加。首先，测试数据的规模达到了海量级，采用了北京大学计算机网络与分布式系统实验室提供的以中文为主的Web测试集 CWT100g，共571万个网页，容量为90GB。其次，查询条件的数量也大幅增加到50个。本届评测的测试集构造、评测组织实施和结果分析，都更加规范科学。查询条件尽量模拟用户的真实信息需求。标题查询域（title）尽量简短，一般为2~5个词汇。描述查询域(desc)一般为一到两句自然语言语句。叙述查询域 (narr)进一步详细描述用户的信息需求。部分题目出题时参考目前互联网搜索引擎统计出的比较热门的用户需求。题目涉及领域尽可能全面。包含政治、经济、文化、娱乐、体育等多个不同领域。题目整体难易程度适中，标准答案数目不太少也不过多，从而提高不同系统结果的区分度。此外，为了使参评单位的系统调整到最佳性能，组织方还提前发布训练集、开发集和检索源数据。
评测结果分析
作为国内有较大影响的评测会议，863信息检索评测基本上反映了中文信息检索技术的发展水平。下面我们通过2005年度最新评测结果来分析国内的研究现状。这次评测分为自动和手工构造查询条件两组。评测结果如下表所示（由于863评测结果发布采用匿名方式，因此这里只给出最终结果而不显示参赛单位名称）：
指标 System 1 System 2 System 3 System 4 System 5 MAP 0.2727 0.1862 0.3107 0.3175 0.2858 R-PRECISION 0.3320 0.2554 0.3672 0.3605 0.3293 P@10 0.5300 0.5180 0.6240 0.5540 0.6280 表1 信息检索评测结果—自动组
指标 System 1 System 2 System 3 System 4 System 5 MAP 0.3257 0.1705 0.3538 0.2673 0.3671 R-PRECISION 0.3826 0.2327 0.4078 0.3185 0.4140 P@10 0.5580 0.4640 0.6840 0.4800 0.7040 　　 表2 信息检索评测结果—手工组
从所有参评队伍的整体检索效果看，这次评测的结果与以往的评测结果相比，在各个指标都有了很大提高。这主要是因为研究者利用了链接分析技术、锚文本等相关评价因素来提高准确率，并针对评测采取有效的技术
手段来克服中文检索中的某些难点，比如命名实体识别等。此外相关反馈或者重排序技术对于提高检索效果也有一定的帮助。从检索模型来说，参评队伍采用了向量空间模型、概率模型、语言模型等基本模型或者混合模型，同时利用了PageRank、链入分析等链接分析或者页面分析技术来提高检索效果。中文检索相对英文等其他语种来说，如何正确分词对于检索效果有所影响，尤其是命名实体、缩略语以及新词等未登录词的正确识别对于某些查询来说影响较大。现在的大部分检索系统在索引以及查询分析阶段采用了命名体识别，从结果来看，取得了比较好的效果。
当前的中文检索技术均基于国际主流的算法，在评测中成绩较好的单位在TREC评测中也曾取得不错的成绩。可以看出，这些算法提供了基准级的性能，系统级的创新或改进不多，不过现有系统都会针对中文的特点进行改进。总体上，如果用户草拟的查询条件能够比较全面准确地表达用户需求的话，现有的中文检索技术一般能够提供比较好的检索结果，但是对于以下方面还存在着一些问题：
* 查询条件与文档词汇内容失配；
* 部分命名体，新词以及缩略语识别还存在着一些问题；
* 在计算相似度时，查询词汇权重的设定正确与否也在一定程度上影响检索效果。
这些问题的存在导致现有检索系统性能下降，针对这些问题，现有的检索技术还有很大的改善空间来获得比较满意的检索结果。
经过众多研究者的努力，规范化评测对信息检索技术发展的重要作用已经得到了广泛认同。虽然和国外相比起步较晚，但短短几年间，中文信息检索的规范化评测从无到有，已经取得了令人鼓舞的进步。但是，总的来说，国内仍处于学习国外的相关评测（尤其是TREC系列会议）的阶段。
规范化评测与公正客观这个终极目标还有一定的距离，而如何降低人为因素的影响仍是摆在评测组织者面前的一道难题。而国内的信息检索评测无论是从数据规模还是从评测手段来看，与国际知名评测仍有较大差距，这是由我国目前的科研和应用的总体水平决定的。但差距的存在也表明提升的空间巨大，国内的相关研究者任重而道远。
链接
1. Cranfield试验
早期信息检索技术评测最著名的研究是由Cleverdon在1960年代所进行的Cranfield试验，它首开规范化评测研究之先河，开创了以测试集（Test Collection）配合测试标准（Measures）来评估系统的模式。所谓测试集，是一种在规范化环境中测试系统性能的机制，包括测试问题（Queries）、测试文件集（Document Set）以及相关判断（Relevance Assessment）三个部分。其研究设计的概念是假设在给定的查询问句与文件集中，某些文件是与查询问句相关的。系统的目的是检索出相关的文件，并拒绝不相关的文件。Cranfield研究在评测技术的发展历程上具有里程碑意义，很多思想和做法都成为后人评测的基石。然而，由于刚刚起步， Cranfield试验还存在很多不足之处。早期所采用的测试集规模均不大，且大多数是使用同质型较高的文件集（例如，Cranfield二期研究只包含 279个查询问句和1400个文件），因此它与真实的检索环境之间存在着很大差异。基于这样的测试集所发展出来的检索系统，在实际应用中往往受到极大的限制，效果并不好。
2.文本检索会议TREC
Cranfiled试验之后的20多年间，也有研究机构做了类似试验，但都存在两个根本缺陷：一是缺少在相同的测试数据上使用相同评测方法的跨系统公开评测；二是缺少真实的大规模测试集。不过，要建构大型测试集必须耗费相当可观的人力、物力，这对大多数单位来说是不堪负荷的，因此大规模的测试集一直无法真正实施。
20世纪90年代，基于军事和反恐情报处理的需要，美国国防部高级研究计划署（DARPA）提出了TIPSTER文本处理计划，文本检索会议（Text REtrieval Conference，简称TREC）就是该计划的重要组成部分。1992年，在美国国防部高级研究与开发机构和DARPA的资助下，NIST召开了第一届TREC会议，以后每年举办一次，到2005年已举办了14届。TREC的组织者认为，对不同系统的比较，其意义并不在于要证明某个系统优于其他系统，而是要把更多不同的技术放在一起公开讨论，这对技术的发展有很大好处。于是，TREC自开办之初，就明确提出了四个目标：
1. 以大规模测试集为基础，推动信息检索的研究；
2. 通过建立一个开放式的论坛，使与会者交流研究成果与心得，以增进学术界、产业界与政府的交流互通；
3. 通过对真实检索环境的模拟与重要改进，加速将实验室研究技术转化为商业产品；
4. 开发适当且具有实用性的评价技术，供各界遵循采用。
TREC的评测机制基本沿袭Cranfield模式，但它的很多思想和做法也突破了传统的限制。首先，TREC极力强调数据规模的重要性，并投入了大量人力、物力去构建大规模测试集和训练集，第一届就提供了2G的数据集；其次，TREC把复杂的单一目标分解为若干明确的测试项目（称为“Track”），其中很多项目都以模拟真实的使用环境为目标；第三，TREC非常重视不同的算法和系统设计者之间的交流，参赛单位除了要提交系统的运行结果之外，还可以参加研讨会，与会者可以公开系统的架构，评估结果并互相讨论切磋。
TREC发展到现在，已经成为备受瞩目的标尺性测试，对信息检索研究领域产生了巨大而深远的影响。今天，在TREC评测中名列前茅的算法往往成为大家研究的重点，很多商用搜索引擎所采用的核心技术就是那些被TREC证明成功的算法发展而来的。TREC论坛成为研究人员互相交流学习的重要途径，很多新的思想和方法正是从这里碰撞产生。TREC为新的热点研究提供了急需的数据和评价体系，促进了这些技术的快速发展。鉴于TREC的巨大成功，现在的众多评测，甚至其他研究领域的评测，如跨语言检索评测会议NTCIR、CLEF，机器翻译评测TC-STAR等，都或多或少受到它的影响。
3. 信息检索评价指标
信息检索评测指标直接关系到参评系统的最终评价，指标不合理会导致对系统的评价也不合理，因此规范化的评测会议对于评价指标的选择都是很慎重的。
早期常用的评测指标包括准确率（Precision）、召回率（Recall）、F1值等，其意义如下：
召回率=系统检索到的相关文件数/相关文件总数
准确率=系统检索到的相关文件数/系统返回文件总数
显而易见，召回率考察系统找全答案的能力，而准确率考察系统找准答案的能力，两者相辅相成，从两个不同侧面较为全面地反映了系统性能。F1值是一个把准确率和召回率结合起来的指标。考虑到某些情况下不同系统的准确率和召回率互有高低，不便于直接比较，而使用F1值就可以更直观地对系统性能进行排序。
随着测试集规模的扩大以及人们对评测结果理解的深入，更准确反映系统性能的新评价指标逐渐出现，包括：
（1） 平均准确率（Mean Average Precision，即MAP）：单个主题的MAP是每篇相关文档检索出后的准确率的平均值。主题集合的MAP是每个主题的MAP的平均值。MAP是反映系统在全部相关文档上性能的单值指标。
（2） R-Precision：单个主题的R-Precision是检索出R篇文档时的准确率。其中R是测试集中与主题相关的文档的数目。主题集合的R-Precision是每个主题的R-Precision的平均值。
（3） P@10：P@10是系统对于该主题返回的前10个结果的准确率。考虑到用户在查看搜索引擎结果时，往往希望在第一个页面（通常为10个结果）就找到自己所需的信息，因此设置了这样一个拟人化的指标，P@10常常能比较有效地反映系统在真实应用环境下所表现的性能。
（骆卫华、刘群工作单位为中国科学院计算技术研究所，张俊林工作单位为中国科学院软件所）