<< 2016年3月23日 | 首页 | 2016年3月25日 >>

搜索引擎利用机器学习排序 - August_1989 - 博客频道 - CSDN.NET

首先,由人工标注训练数据。也就是说,对于某个查询Q,人工标出哪些文档是和这个査询相关的,同时标出相关程度,相关程度有时候可以用数值序列来表示,比如从1分 到5分为3个档次,1代表微弱相关,5代表最相关,其他数值代表相关性在两者之间。对于某个查询,可能相关文档众多,同时用户査询也五花八门,所以全部靠人工标注有时候 不太可能。此时,可以利用用户点击记录来模拟这种人工打分机制。
      对于机器学习来说,输入是用户查询和一系列标注好的文档,机器学习系统需要学习打分函数,然后按照打分函数输出搜索结果,但是在其内部,每个文档由若干特征构成的,即每个文档进入机器学习系统之前,首先需要将其转换我饿滴特征向量,比较常用的特征包括:

• 查询词在文档中的词频信息
• 查询词的IDF信息
• 文档长度: 
• 网页的入链数量: 
• 网页的出链数量:
• 网页的pageRank值; 
• 网页的URL松度: 
• 査询词的Proximity值:即在文档中多大的窗口内可以出现所有査询词。

        以上所列只是影响排序的一部分特征,实际上还有很多类似的特征可以作为特征向量中的一维加入。在确定了特征数量后,即可将文档转換为特征向量X,前面说过每个文档会人工标出其相关性得分y.这样每个文档会转換为<X,Y>的形式,即特征向量及其对应的相关性得分,这样就形成了一个具体的训练实例。

       通过多个调练实例,就可以采用机器学习技术来对系统进行训练,训练的结果往在是 ―个分类函数或者回归函数,在之后的用户搜索中,就可以用这个分类函数对文档进行打分,形成搜索结果 

    从目前的研究方法来说,可以将机器学习揉序方法分为以下3种:单文档方法、文档对方法和文档列表方法。

 

3. 单文档方法(PointWise Approach》

        单文档方法的处理对象是单独的一篇文档,将文档转换为特征向量后,机器学习系统根据从训练数据中学习到的分类或者回归函数对文档打分,打分结果即是搜索结果。下面我们用一个简单的例子说明这种方法。 
        图2是人工标注的训练集合,在这个例子中,我们对于每个文档采用了3个特征: 査询与文档的Cosme相似性分值、査询词的Proximity值及页面的PageRank数值,而相关性判断是二元的,即要么相关要么不相关,当然,这里的相关性判断完全可以按照相关程度扩展为多元的,本例为了方便说明做了简化。

           

                                          图2 训练数据
        

      例子中提供了5个训练实例,每个训练实例分别标出来其对应的查询,3个特征的得分情况及相关性判断。对于机器学习系统来说,根据训练数据,需要如下的线性打分函数:
  
       Score(Q, D)=a x CS+ b x PM+cx PR+ d 
        这个公式中,cs代表Cosine相似度变徽,PM代表Proximity值变量,PR代表pageRank, 而a、 b、 c、 d则是变量对应的参数。

        如果得分大于一设定阀值,则叫以认为是相关的, 如果小于设定闽值则可以认为不相关。通过训练实例,可以获得最优的a、 b,、c、d参数组合,当这些参数确定后,机器学习系统就算学习完毕,之后即可利用这个打分函数进行相关性判断。对于某个新的查询Q和文档D,系统首先获得其文档D对应的3个特 I特征值,之后利用学习到的参数组合计算两者得分,当得分大于设定的闽值,即可判断文档是相关文档,否则判断为不相关文档。

 

4. 文档对方法(PairWise Approach)

        对于搜索系统来说,系统接收到用户査询后,返回相关文档列表,所以问题的关键是确定文档之间的先后顺序关系。单文档方法完全从单个文档的分类得分角度计算,没有考虑文档之间的顺序关系。文档对方法则将重点转向量对文档顺序关系是否合理进行判断。

        之所以被称为文档对方法,是因为这种机器学习方法的训练过程和训练目标,是判断任意两个文档组成的文档对<D0C1,D0C2>是否满足顺序关系,即判断是否D0C1应该排在DOC2的前面。图3展示了一个训练实例:査询Q1对应的搜索结果列表如何转换为文档对的形式,因为从人工标注的相关性得分可以看出,D0C2得分最高,D0C3次之,D0C1得分最低,于是我们可以按照得分大小顺序关系得到3个如图3所示的文档对,将每个文档对的文档转换为特征向量后,就形成了一个具体的训练实例。

      

                                            图3  文档对的方法训练实例


       根据转换后的训练实例,就可以利用机器学习方法进行分类函数的学习,具体的学习方法有很多,比如SVM. Boosts、神经网络等都可以作为具体的学习方法,但是不论具体方法是什么,其学习目标都是一致的,即输入- 个査询和文档对<Docl,DOC2>, 机器学习排序能够判断这种顺序关系是否成立,如果成立,那么在搜索结果中D0C1应该排在D0C2 前面,否则Doe2应该摔在Docl前面,通过这种方式,就完成搜索结果的排序任务。
        尽管文档对方法相对单文档方法做出了改进,但是这种方法也存在两个明显的问题:

       一个问题是:文档对方法只考虑了两个文档对的相对先后顺序,却没有考虑文档出现在搜索列表中的位置,排在搜索站果前列的文档更为重要,如果前列文档出现判断错误,代价明显高于排在后面的文档。针对这个问题的改进思路是引入代价敏感因素,即每个文档对根据其在列表中的顺序具有不同的权重,越是排在前列的权重越大,即在搜索列表前列如 果排错顺序的话其付出的代价更高•
        另外一个问题是:不同的査询,其相关文档数量差异很大,所以转换为文档对之后, 有的查询对能有几百个对应的文档对,而有的查询只有十几个对应的文档对,这对机器学习系统的效果评价造成困难 •我们设想有两个查询,査询Q1对应500个文文档对,查询Q2 对应10个文档对,假设学习系统对于査询Ql的文档对能够判断正确480个,对于査询 Q2的义格对能够判新正确2个,如果从总的文档对数量来看,这个学习系统的准确率是 (480+2)/(500+10)=0.95.即95%的准确率,但是从査询的角度,两个査询对应的准确率 分别为:96%和20%,两者平均为58%,与纯粹从文档对判断的准确率相差甚远,这对如何继续调优机器学习系统会带来困扰。

 

4. 文档列表方法(ListWise Approach)

          单文档方法将训练集里每一个文档当做一个训练实例,文档对方法将同一个査询的搜索结果里任意两个文档对作为一个训练实例,文档列表方法与上述两种表示方式不同,是将每一个查询对应的所有搜索结果列表整体作为一个训练实例,这也是为何称之为文档列表方法的原因。
        文档列表方法根据K个训练实例(一个査询及其对应的所有搜索结果评分作为一个实 例)训练得到最优评分函数F, 对于一个新的用户査询,函数F 对每一个文档打分,之后按照得分顺序由高到低排序,就是对应的搜索结果。 所以关键问题是:拿到训练数据,如何才能训练得到最优的打分函数?

        这里介绍一种训练方法,它是基于搜索结果排列组合的概率分布情况来训练的,图4是这种方式训练过程的图解示意。

        

                                       图4 不同评分函数的KL距离

 

       首先解释下什么是搜索结果排列组合的概率分布,我们知道,对于搜索 引擎来说,用户输入査询Q, 搜索引擎返回搜索结果,我们假设搜索结果集合包含A. B 和C 3个文档,搜索引擎要对搜索结果排序,而这3个文档的顺序共有6种排列组合方式:

      ABC, ACB, BAG, BCA, CAB和CBA,

        而每种排列组合都是一种可能的搜索结果排序方法。

        对于某个评分函数F来说,对3个搜索结果文档的相关性打分,得到3个不同的相关度得分F(A)、 F(B)和F(C), 根据这3个得分就可以计算6种排列组合情况各自的概率值。 不同的评分函数,其6种搜索结果排列组合的概率分布是不一样的。
      了解了什么是搜索结果排列组合的概率分布,我们介绍如何根据训练实例找到最优的 评分函数。图4展示了一个具体的训练实例,即査询Q1及其对应的3个文档的得分情况,这个得分是由人工打上去的,所以可以看做是标准答案。可以设想存在一个最优的评分函数g,对查询Q1来说,其打分结果是:A文档得6分,B文档得4分,C文档得3分, 因为得分是人工打的,所以具体这个函数g是怎样的我们不清楚,我们的任务就是找到一 个函数,使得函数对Ql的搜索结果打分顺序和人工打分顺序尽可能相同。既然人工打分 (虚拟的函数g) 已知,那么我们可以计算函数g对应的搜索结果排列组合概率分布,其具体分布情况如图4中间的概率分布所示。假设存在两个其他函数h和f,它们的计算方法已知,对应的对3个搜索结果的打分在图上可以看到,由打分结果也可以推出每个函数对应的搜索结果排列组合概率分布,那么h与f哪个与虚拟的最优评分函数g更接近呢?一般可以用两个分布概率之间的距离远近来度量相似性,KL距离就是一种衡量概率分布差异大小的计算工具,通过分别计算h与g的差异大小及f与g的差异大小,可以看出f比h更接近的最优函数g,那么在这个函数中,我们应该优先选f作为将来搜索可用的评分函数,训练过程就是在可能的函数中寻找最接近虚拟最优函数g的那个函数作为训练结果,将来作为在搜索时的评分函数。

       上述例子只是描述了对于单个训练实例如何通过训练找到最优函数,事实上我们有K 个训练实例,虽然如此,其训练过程与上述说明是类似的,可以认为存在一个虚拟的最优 评分函数g (实际上是人工打分),训练过程就是在所有训练实例基础上,探寻所有可能的 候选函数,从中选择那个KL距离最接近于函数g的,以此作为实际使用的评分函数。 经验结果表明,基于文档列表方法

的机器学习排序效果要好于前述两种方法。

阅读全文……

(3)搜索与机器学习_李航博士_新浪博客

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

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

 

排序学习

对给定的查询语句,将检索到的网页进行排序是排序学习的任务。排序学习将此问题形式化为监督学习的问题,将网页表示为特征向量,其中特征表示网页与查询语句的匹配程度或网页的重要度,基于标注数据学习一个排序模型。现在最常用的方法是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.互联网搜索的挑战与机遇

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

 

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

 

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

 

阅读全文……