搜索引擎的前沿技术

原文：http://blog.csdn.net/zhanghefu/archive/2007/05/15/1609640.aspx   人工智能中的机器学习技术在基于语料的文本信息处理中获得了快速发展，同时基于统计和经验的方法在超出传统机器学习的范畴之外也发展出一些独特的方法和技术，这些应用将会使下一代搜索引擎在技术上取得突破。 搜索引擎并非只是一个网络上的应用程序，它要用到信息检索、人工智能、自然语言处理、分布式网络并行计算技术、多媒体技术、数据库技术、数据挖掘技术、数字图书馆等多领域的理论和技术，具有很强的综合性和挑战性。   从技术发展角度讲，随着计算机的发展和互联网的普及，对海量文本信息处理的需求越来越迫切，这使得人工智能中机器学习技术在基于语料的文本信息处理中获得了快速发展。同时，基于统计和经验的方法在超出传统机器学习的范畴之外发展出一些独特的方法和技术。但是,自然语言处理中仍然存在许多尚未解决的问题，甚至是影响到自然语言处理的基础性的核心问题。检索专家Bruce R.Schatz预测，在自然语言理解没有取得突破性进展之前，基于概念语义空间的文本信息组织与检索，将在本世纪前10年起主要的作用。 语义索引 如何处理海量文本信息，特别是随着网络的飞速发展，如何快速为海量文本信息建立分类目录有效地组织网上海量信息，以及如何建立具有某种程度语义的索引机制就是当前乃至今后相当一段时间的研究热点。 美国Arizona大学的陈火斤钧(Hsinchun Chen）教授首先提出基于概念的文本自动分类与语义检索。概念语义空间实际上是基于概念空间的语义索引。这是为克服关键词检索过程中由于检索词的差异导致检索结果差异而建立的支持相关概念的索引机制。该项技术成功地采用机器学习的方法实现了大量文本的自动分类、标注与检索。他采用此项技术成功地承接并完成了美国涉及多个领域的文本信息处理项目。 所谓概念语义空间，就是对文本集建立的能反映文本集中概念之间语义关系的一个索引。概念语义空间与文本检索、搜索引擎、知识管理密切相关，它是基于目前自然语言处理技术的进展状况而产生的。 这里所说的概念在形式上的表现是词，但并不是所有的词都是概念。概念是从语料中抽取出来的用于表明一类文档特征的标识词，一类文档可能有不同的概念来标识。上面所说的语义词典包括同义词、近义词。 采用语义词典是建立语义索引的一种机制。语义词典往往是手工建立的，但这样建立的词典不能针对要处理的语料提取语义关系，会降低检索性能。例如，当我们提到“钱钟书”时就会自然联想到“围城”，提到“非典”自然就想起了“SARS”，如果语义词典没有建立这种语义关系（事先手工编辑的语义词典很难提取这类“联想”的语义）。当我们用“非典”检索时，就不能返回仅包含“SARS”的文本; 同样仅用“钱钟书”检索，未必能检索到钱钟书所有著作的信息。解决这一问题的一个重要途径是共现分析。通过统计同一类文本中两个词在同一篇文本中的共现率，可以发现类似的语义关联。这种语义联想的激活可以通过Hopfield网络实现，网络的权值则由共现率确定。随着技术的进展，还有许多其他自动形成语义词典的方法不断提出，其中很多都和机器学习有关。 查准与查全的平衡 评价文本检索系统性能的一个关键概念是“相关性”（relevance）。它是用来判断获取的文档集合对于用户需求满足的程度。相关性是一个主观的概念。相关性的度量不仅仅依赖于用户的查询和所搜索的文档的集合，还与用户的个人需求、偏好、知识、语言等有关系。 通常将“查准率”和“查全率”这两个指标共同用来衡量检索系统的性能。查准率表明系统的精确性。查全率反映了系统的覆盖性。这两个量不是独立的，其中一个指标的提高往往以另一个指标的降低为代价。 查准率(Precision)是信息检索的性能指标，定义为被检索到的相关文档数除以所有要检索的文档数。 查全率(Recall)是信息检索的另一个性能指标。定义为查找到的相关文档数除以集合中全部相关文档数的值。 在实际应用中，有些用户更加注重查准率，而另外一些用户则更加注重查全率。也有专家引入一个综合了查全率与查准率的指标来衡量系统的性能。查准率比较易于度量。对于所获取的文档集合，只要判断每一篇文档是否和给定查询相关就可以了，其计算是比较直接的。而对于查全率的计算就相对困难一些，因为这意味着对于给定查询，必须计算整个文档集合中相关文档的数目。当文档集合过大时，这是不可行的。 检索返回结果过多，对于用户来说冗余信息过多。解决这一问题的途径之一是对检索结果进行分类，目前主要是人工选择有用信息，这样的人工工作量太大，另外就是对检索结果进行实时聚类，但这样做处理速度跟不上，等待时间过长，用户难以忍受。还有一种方式是事先分类并分类检索，返回的结果也分类显示，但对海量数据及时分类其粒度不可能太小。值得尝试的办法是基于事例的学习，就是对搜索到的好的结果作为样本，让机器再次搜索。 机器学习技术与自然语言处理 统计方法在语音识别方面的成功，促进了类似方法在自然语言处理其他方面的应用。现在各种机器学习方法几乎都应用到了自然语言处理的不同方面，包括词法、句法分析、歧义消除和理解、会话过程和信息抽取以及机器翻译。然而，传统的人工智能中的机器学习对计算语言学的研究贡献有限。这是因为基于机器学习和基于经验的自然语言处理需要通过相互交流、相互促进才能发展。 现在自然语言处理中大多数机器学习的研究都借助了语音识别中特定的统计技术，如隐马尔科夫模型（Hidden Markov Models, HMMs）、概率上下文相关语法（Probabilistic Context Free Grammars, PCFGs）。其他各种学习算法包括决策树、规则归纳、神经网络、基于示例的方法、贝叶斯（Bayesian）网络方法、归纳逻辑程序、基于理解的学习。 遗传算法也能用于自然语言处理，并且在特定的应用中有其优势。另外，一些特别的机器学习算法如主动学习、推进（Boosting）算法、修正学习、有知识背景的构造归纳学习、理论修正、经验评价法、PAC （Probably Approximately Correct）学习等对处理自然语言问题是非常有用的。事实上已经有一些文献提出了利用机器学习技术进行自然语言处理的特定方法。这表明目前的研究已经不局限于研究UCI（University of California，Irvine）数据库中由标准数据集提供的特征向量的分类问题。计算语言研究组织和机构已经收集了很多有趣的涉及许多自然语言问题的文本数据集。其中有些问题通过选取合适的特征可以退化为标准的分类问题，但是其他一些问题需要采用或建立复杂的数据结构，如完备的句子或解析树来解决。 以上表明，机器学习能为自然语言处理提供一系列非传统的学习方法的同时，还能提供一般的方法论的指导。反过来，自然语言处理为机器学习提出了各种有趣的和富有挑战性的问题。这些问题常常具有一些特定的特征，如: 非常大的特征空间和极度稀疏的数据。另外，统计语言学对机器学习的一个不太明显的潜在贡献是引入了一些新的机器学习算法,如最大熵方法、指数模型方法。这些方法在传统机器学习的文献中没有很好地论述。它们可能会像HMMs和PCFGs在分子生物学中的成功应用一样有效地被用于其他机器学习问题。 机器学习技术与自然语言处理任务有着密切的联系，表中列出了他们之间的关联关系。1999年Claire Cardie和Raymond J. Mooney编辑出版了机器学习杂志的一本专缉，该专辑收集了当时在自然语言处理领域机器学习技术的典型应用。其中还介绍了一些端到端的自然语言应用，如Golding & Roth 的感知上下文的拼读修正系统，以及完整的信息抽取系统。该专辑特别提到Soderland的概念抽取模式和Bikel的能够准确识别姓名、日期、时间、数字的系统。 目前，自然语言处理和信息检索在技术上没能很好地融合。在文本检索过程中如果只使用关键词匹配技术往往会遇到词汇不匹配，这是因为存在表达差异。关键词匹配检索模式通常基于这样一种基本假设: 仅在一个文档含有与查询完全相同的词汇时，它们才相关。这种相关性匹配实际上是基于表层的匹配(Surface-Based Matching)。然而，人类的自然语言中，随着时间、地域、领域等因素的改变，同一概念可以用不同的语言表现形式来表达。因此即使对于同一概念的检索，不同的用户可能使用不同的关键词来查询，而基于表层的匹配不可能检索到同一概念的多种语言表达形式。因此，词汇不匹配将导致系统的查全率降低。从根本上说是目前机器对自然语言不能完全理解，缺乏对概念的语义表达支持。从目前技术状况来看，尽管我们付出了大量努力，但是要达到使计算机对自然语言完全理解这一目标还差得很远。对于解决上述问题在目前可能达到的目标是通过机器学习对原始语料中的概念之间的语义关联进行挖掘，对这些语义关联给出合理的表示，从而产生一些常识性的概念语义。 概念语义空间技术能很好移植到中文自然语言处理方面。中科院王永成教授领导的课题组开发出了一个中文概念检索系统，该系统支持具有一定模式的自然语言查询和基于概念的检索，并具有概念表达扩充功能; 用户可以添加系统原来不熟悉的概念，而且可以在用户的帮助下排除差错; 可以提供200字的精确摘要; 能进行新闻去重，并且改进了国际著名网站Google的排序算法; 系统的 Crawler(自动搜索软件)对各大新闻网站自行跟踪、更新，并且根据查询动态调整。 中科院计算所在国家自然科学基金资助下，采用概念语义空间的思想，实现了一个概念语义检索系统GHunt。该系统采用网络蜘蛛采集网页，以概念语义空间组织网页，对网页建立语义索引，实现基于概念的智能互动语义查询，以不同粒度摘要或全文方式展现; 对专题事件展现其来龙去脉; 对多媒体信息实现基于内容的图文联合检索。 建立概念语义空间涉及多方面的文本信息处理技术，包括海量文本自动分类聚类技术、自动标注技术、语义索引、语义联想检索技术。在这一系统中集成了网页采集多模式定向采集技术、基于粗糙集的文本分类技术、基于群体智能的蚂蚁聚类法、基于直接模糊聚类的概念聚类、专题自组织等自有研究成果。联索科技开发的IFACE专业搜索技术聚焦于适用和实用的更小搜索单位，利用基于内容的语义计算模型，发现精深的信息内容，识别信息并将信息整理好，拼装出表格化信息库，返回给用户更加准确而简化的内容，而不仅仅是得到包含关键字的网页。 搜索引擎其他新技术 1. P2P方式的搜索引擎 搜索引擎的实现可以采用集中式体系结构和分布式体系结构。当系统规模达到一定程度（如网页数达到亿级）时，必然要采用某种分布式方法以提高系统性能。P2P方式的搜索引擎就是基于此目的诞生的。搜索引擎的各个组成部分除了用户接口之外都可以进行分布: 搜索器可以在多台机器上相互合作、相互分工进行信息发现，以提高信息发现和更新速度; 索引器可以将索引分布在不同的机器上，以减小索引对机器的要求; 检索器可以在不同的机器上进行文档的并行检索，以提高检索的速度和性能。 P2P是peer-to-peer的缩写。peer在英语里有“（地位、能力等）同等者”、“同事”和“伙伴”等意义。因此，P2P也就可以理解为“伙伴对伙伴”的意思，或称为对等网。目前人们认为其在加强网络上人的交流、文件交换、分布计算、协同、深度检索等方面大有前途。 P2P软件能在互联网中迅速地普及，其中起到主导作用的是一款P2P文件共享软件Napster。Napster技术在1999年由当时在美国东北大学就读的Shawn Fanning开发成功，并迅速在众多MP3数字音乐爱好者中传播开来。人们可以通过Napster在网络上搜索自己需要的MP3音乐，并从任一台联网使用Napster的计算机中下载。P2P使得参与网络的各个主机都能够提供服务，同时也可以享受到来自所有其他主机所提供的服务。 P2P网络具有集中式服务网络所缺乏的优势: 可扩展性强、容错性好、成本低、充分利用分布资源。这些特点使得P2P架构在文件共享、分布式存储、搜索引擎、分布式计算、传感器网络、协作软件中有宽广的应用前景。同时其所强调的“以人为本”的理念，将深刻地体现于下一代互联网运营模式。 2.跨粒度检索 信息呈现个性化、可视化、综合化的特征，但现有信息检索结果一般没有粒度区别，只是若干检索结果的罗列，没有对检索结果的分析综合，没有形成统一的综合摘要提供给用户。另外很少对用户关心的领域信息进行处理。信息呈现方式单一，很少以可变粒度的可视化的图形方式呈现，特别是多篇摘要技术用于大量文档的综述。 概念语义空间的可视化 概念语义空间是在网络信息急剧增长的条件下产生的，它为快速、有效地组织海量、动态变化、半结构化的网络文本信息提供了机器学习手段。在自然语言理解没有取得突破性进展之前，基于概念语义空间的文本信息组织与检索，将在本世纪前10年起主要的作用。概念语义空间的可视化是近来发展的一个方向。采用概念语义空间技术将文本组织起来以后，如何向用户个性化地展现检索结果就成为一个关键问题。现有的逐个浏览网页的方式显然不能满足用户个性化的需求，因此最近有关主题探测与专题组织方面的研究在美国成为研究热点。这项研究将涉及自然语言处理的几乎所有方面。自然语言处理的研究成果将促进该项研究的深入开展。 链接:搜索引擎核心技术的演进 ● 上个世纪70年代，著名的信息检索专家Gerald Salton提出了向量空间模型（Vector Space Model），从此，文本检索引入了倒排索引（Inverted index）以及向量空间模型。另外，他还创立了基于贝叶斯统计（Bayesian statistics）的布尔方法（Boolean retrieval method）和简单概率获取模型（Simple probabilistic retrieval models）。虽然已经经过了近30年的历史，这些技术至今仍然构成当今信息检索系统以及互联网搜索引擎的理论基础。 ● 上个世纪80年代，在新的人工智能技术的发展同时，产生了一些模拟专业文献搜集者和领域专家的专家系统。使用了对用户建模以及自然语言处理等技术来辅助对于用户和文档的表示。并且产生了一些供研究用的原型系统。 ● 上个世纪90年代初期，当研究者们认识到了创建领域知识库的困难之后，试图采用新的机器学习技术用于信息分析。这些技术包括神经网络、遗传算法、符号学习等。概念语义空间技术就是在这个年代提出的，但当时处于初步研究探索阶段。 ● 上个世纪90年代中期之后，随着搜索引擎的普及以及网络Spider（蜘蛛程序）超链分析等技术的发展，文本检索系统已经成为更新的并且更强大的用于网络内容的搜索工具。概念语义空间技术的研究取得突破，并在美国的数字图书馆领域得到应用。 ● 在过去10来年，统计学习方法改变了手工建立语法和知识库以及文本目录索引的状况，通过对大量已标注的和未标注的自然语料的训练可以部分或全部自动地完成上述过程。