搜索与机器学习_browserank算法

今年是图灵诞辰100周年。如果图灵在世的话，他会惊喜地发现互联网搜索引擎已经能在自己当年设计的人工智能测试上取得相当好的成绩，因为在主要的搜索引擎上提出各种各样的问题，比如“理想国的作者？”或者“从知春路到清华东门怎么坐公交车？”，都能找到正确的答案。毫无疑问，互联网搜索引擎已成为当今最为实用、最具代表性的智能系统。

 

1．互联网搜索技术

据统计，约有60%的互联网用户每天至少使用一次搜索引擎，约有90%的互联网用户每周至少使用一次搜索引擎。搜索引擎已经成为人们访问互联网的必经通道。对一般用户来说，除了搜索，没有其他手段可以帮助更方便地获得网上的信息。

 

图1. 互联网搜索引擎架构图

 

搜索引擎能看到万亿（trillion）量级的URL，需要成千上万台的计算机抓取、分析、索引网页；每天有几十亿的用户查询，需要将最相关、最新、最全的结果提供给用户。互联网搜索的发展取决于软件、硬件、系统等多方面的计算机技术的研发与创新。

 

图1是互联网搜索引擎的架构示意图。简单地说，搜索引擎由抓取器、索引器、排序器、用户界面组成。抓取器从互联网上抓取网页，将垃圾网页过滤；索引器分析网页的内容，计算网页的重要度，将网页索引；用户界面接受查询语句，分析查询语句的内容；排序器从索引中检索出含有查询词的网页，实行查询语句与网页的匹配，将网页按相关度、重要度等进行排序；用户界面将排序结果展示给用户，同时收集用户搜索行为数据。

 

可以认为互联网搜索主要建立在两大领域的技术之上，即大规模分布式计算与统计机器学习。搜索引擎的规模巨大，必须采用大规模分布式处理。搜索属于智能处理，必定是数据驱动，基于统计机器学习的。

 

从使用的数据，以及相关的技术的观点来看，互联网搜索经历了三代的发展历程。第一代搜索，将互联网网页看作文本，采用传统信息检索的方法。第二代搜索，利用互联网的超文本结构，有效地计算网页的相关度与重要度，代表的算法有PageRank。第三代搜索，有效利用日志数据与统计学习，使网页相关度与重要度计算的精度有了进一步的提升，代表的技术包括排序学习、网页重要度学习、匹配学习、话题模型学习、查询语句转化学习。

 

2．机器学习在互联网搜索中的应用

下面介绍一些基于统计机器学习的最前沿的互联网搜索技术。

 

排序学习

对给定的查询语句，将检索到的网页进行排序是排序学习的任务。排序学习将此问题形式化为监督学习的问题，将网页表示为特征向量，其中特征表示网页与查询语句的匹配程度或网页的重要度，基于标注数据学习一个排序模型。现在最常用的方法是LambdaMART [1]。该方法将排序问题转换为二类分类问题，利用Boosting算法优化学习目标函数。其最大特点是不显示地定义损失函数，而定义损失函数的梯度函数，以解决排序损失函数不易优化的问题。其他代表的排序学习方法还有Rank SVM [5]、 IR SVM [2]、AdaRank [10]等。

 

网页重要度学习

网页重要度学习旨在计算出每个网页的重要度，排序时将重要的网页尽量排在前面。传统的网页重要度计算基于超链接与PageRank算法。直观上，有许多链接指向的网页重要，网页的重要度可以通过链接在网上传播；PageRank用马尔可夫模型实现这一直观。可以认为最近提出的BrowseRank算法 [6]是PageRank算法的扩展与补充。BrowseRank首先根据用户行为数据构建用户浏览图。然后再在用户浏览图上定义连续时间马尔可夫过程，用其平稳分布表示网页的重要度。直观上，用户在网页上平均停留时间越长，网页就越重要；转移到网页的次数越高，网页就越重要。基于用户的互联网使用行为数据，BrowseRank能够更好地计算网页重要度。

 

匹配学习

查询语句与网页的相关性靠两者的匹配程度决定，匹配结果直接影响搜索结果。比如，查询“ny times”应与含有“new york times”的网页匹配。理想的匹配应该是语义上的匹配，而不是关键字上的匹配。匹配学习的目的在于将字面上并不相同，但语义相同的查询语句与网页匹配上，将语义相关的网页排在搜索结果的前面。代表的方法有翻译模型 [3]与隐空间模型 [9]。日志数据中记录了用户点击。比如用户搜索“ny”，因为既含有“ny”又含有“new york”的网页会被搜到，所以两者通过用户搜索中的点击得以联系。隐空间模型方法基于点击数据将查询语句与网页投影到隐空间，在隐空间中学习到查询语句与网页之间的相似度，也就是匹配关系，进而能对新的查询语句与网页的匹配程度作出判断。比如，学到“ny”与“new york”的相似度，判断“ny times”与“new york times”是可以匹配的。

 

话题模型学习

查询语句与网页应该在话题上也能匹配，比如，查询语句是“jaguar car”，那么关于jaguar汽车的网页是与查询相关的，而关于动物jaguar的网页即使含有jaguar与car这两个字，往往也是不相关的。话题模型学习旨在自动从索引网页中抽出所有可能的话题，以及每个网页的话题，以便在搜索时，进行查询语句与网页在话题上的匹配。话题模型学习的方法很多，有概率方法，如PLSI、LDA，也有非概率方法，如LSI、NMF、RLSI。互联网搜索需要处理大规模网页数据，最近提出的RLSI [7] 方法有很好的扩展性、能够在大规模网页数据上进行高效的话题模型学习。

 

查询语句转换学习

10-15%的英文查询语句含有拼写错误；中文查询语句中含有许多拼音汉字转换错误，如“新浪”被误转换为“新郎”。除此之外，查询语句中还有许多不规范、不准确的表述。搜索引擎一般能够自动纠正拼写等错误，将不正确的查询语句转换为正确的查询语句。代表的方法有CRF-QF [3]、LogLinear [8]等。例如，LogLinear方法从日志数据中收集大量的含有拼写错误的查询语句，以及相应的正确的查询语句，从中提取转换规则，自动学习拼写转换的对数线形模型。搜索时，对新的查询语句试用各种转换规则，根据对数线形模型，找出最有可能的转换，即纠正，如果转换的概率足够大，就对查询语句实施转换。

 

3．互联网搜索的挑战与机遇

帮助用户尽快、尽准、尽全地找到信息，从本质上需要对用户需求（查询语句），以及互联网上的文本、图像、视频等多种数据的内容进行“理解”。也就是要解决人工智能的挑战。这种意义上，互联网搜索永远需要面对且克服这一挑战。

 

互联网搜索遵循幂率分布，有头部查询（高频查询）与尾部查询（低频查询）。人工智能挑战在尾部与头部体现出不同的特点。

 

回到图灵测试。也许经过几轮测试，图灵就会发现互联网搜索对头部的查询能给出很好的结果，但是对尾部的查询结果常常不很理想。互联网搜索主要还是基于关键字匹配。因为尾部查询没有足够多的信号，比如点击数据，有时查询语句与网页不能有很好的匹配，搜索引擎无法做出正确的相关度判断。匹配学习能解决一部分问题，但是还有很长的路要走。

 

另一方面，头部查询的结果往往会很多，虽然相关，但是用户会感到难于掌握全貌。如何将这些结果进行摘要总结变成另一个挑战。问题也需要内容的理解，同样是极其困难的任务。

 

4．搜索的发展趋势

过去10多年里，互联网搜索是搜索中的“主战场”。但是可以预见，今后10年，搜索的重点将从互联网搜索逐渐转移到移动搜索。搜索技术也会发生革命性的变化，产生范式转移（paradigm shift）。新一代的搜索应该有以下几个特点：移动、多样化、任务指向、自然与个性化。

 

移动中的搜索

虽然在台式机、智能手机、平板电脑、电视屏幕等各种终端上的搜索都会增加，但是搜索的主要终端将从台式机转变为智能手机、平板电脑等移动设备。通过语音与触摸屏的搜索会更加普遍。

 

多样化的搜索

搜索的内容也将从互联网网页，转变为多种信息的融合。具体表现如下。跨越信息种类，可以统一搜索文本、图片、视频、图表、实体；跨越信息源，可以同时搜索互联网、社区网、社会媒体、数据库的信息；跨越样式，可以通过文字、语音、图片搜索；跨越语言，可以用一种语言搜索其它语言。

 

任务指向的搜索

搜索会帮助用户直接完成某项任务，比如，订机票、买家具。搜索与终端上的应用的结合会极大改变用户体验。

 

自然的搜索

搜索会变得更加自然，搜索引擎会变成用户的“信息仆人”。用户可以用自己认为最自然的方式搜索，比如，关键词、自然语言问句、以及其组合。搜索会越来越像问答系统。搜索将不会是“一锤子买卖”，而是与用户的交互。

 

个性化的搜索

搜索会根据不同的用户提供不同的内容，“投其所好”。从用户的社会网络、地理位置、行为纪录会得到更多信息帮助加深对用户的理解，使个性化搜索变得更加可能。

 

5．结束语

可以看出统计机器学习在搜索中起着举足轻重的作用。事实上，互联网搜索引擎所展现的不是个体智慧，而是群体智慧。 能回答文献作者、公交车路线等问题是因为网上有大量的内容数据，搜索引擎积累了大量的用户行为数据，而搜索引擎能够通过机器学习有效地将这些数据联系、组织、利用起来，在大规模的分布式计算平台上为用户提供服务。互联网搜索如此，今后的移动搜索亦将是如此。

 

图灵诞辰200周年的时候，搜索会变成什么样，我们无法具体想像。但是有一点是肯定的，搜索会越来越接近通过图灵测试的目标。

 

6．参考文献

[1] Burges, From RankNet to LambdaRank to LambdaMART, MSR-TR-2010-82.

[2] Cao et al., Adapting Ranking SVM to Document Retrieval, SIGIR 2006.

[3] Gao et al., Click-through-based Translation Models for Web Search: from Word Models to Phrase Models. CIKM 2010.

[4] Guo et al., A Unified and Discriminative Model for Query Refinement. SIGIR, 2008.

[5] Herbrich et al., Large Margin Rank Boundaries for Ordinal Regression, Advances in Large Margin Classifiers, 2000.

[6] Liu et al., BrowseRank: Letting Users Vote for Page Importance, SIGIR 2008.

[7] Wang, et al., Regularized Latent Semantic Indexing, SIGIR 2011.

[8] Wang, et al., A Fast and Accurate Method for Approximate String Search, ACL-HLT, 2011.

[9] Wu, et al., Learning Query and Document Similarities from Click-through Bipartite Graph with Metadata. Microsoft Research Technical Report, 2011.

[10] Xu and Li, AdaRank: A Boosting Algorithm for Information Retrieval, SIGIR 2007.