XML地图 深圳SEO培训为广大SEO爱好者提供免费SEO教程,致力于SEO优化、SEO服务
首页 > SEO培训 » SEO搜索引擎检索模型与搜索排序

SEO搜索引擎检索模型与搜索排序

2018-10-11 | 人围观 | 关键词:


  SEO搜索引擎检索模型与搜索排序
 

  “得意贤士不可不举,不得意贤士不可不举,尚欲祖述尧、舜、禹、汤之道,将不可以不尚贤。夫尚贤者,政之本也。”
 

  [图片]墨子《尚贤上第八》
 

  搜索结果排序是搜索引擎最核心的构成部分,很大程度上决定了搜索引擎的质量好坏及用户接受与否。尽管搜索引擎在实际结果排序时融合了上百种排序因子,但最重要的两个因素还是用户查询和网页的内容相关性及网页链接情况,关于网页链接分析算法在本书第6章有详述,本章主要介绍的是:给定用户搜索词‍,如何从内容相关性的角度对网页进行排序。
 

  判断网页内容是否与用户查询相关,这依赖于搜索引擎所采用的检索模型。关于检索模型的研究,从信息检索学科建立之初就一直是研究重点,到目前为止,已经提出了多种各异的模型,本章将介绍其中最重要的几种‍检索模型:布尔模型、向量空间模型、概率模型、语言模型及最近几年兴起的机器学习排序算法。
 

  尽管检索模型多种多样,但其在搜索引擎中所处的位置和功能是相同的,图5-1给出了一个搜索引擎计算内容相似性的框架。当用户产生了信息需求后,构造查询词,以此作为信息需求的具体体现,搜索引擎在内部会对‍用户的查询词构造内部的查询表示方法。对于海量的网页或者文档集合,对每个文档,在搜索系统内部也有相应的文档表示方法。搜索引擎的核心是判断哪些文档是和用户需求相关的,并按照相关程度排序输出,所以相关度计算是将用户查询和文档内容进行匹配的过程,而检索模型就是用来计算内容相关度的理论基础及核心部件。
 

  [图片]图5-1 内容相似性计算框架
 

  什么样的检索模型是个好模型呢?用户发出查询词Q后,我们可以把要搜索的文档集合按照“是否相关”及“是否包含‍查询词”两个维度,将其划分为4个象限(参见图5-2),其中,第一象限的文档出现了用户查询词同时被用户判定为相关的;第二象限的文档不包含用户查询词但是被用户判断为相关的;第三象限的文档出现了用户查询词但被用户判定为不相关的;而第四象限的文档则是不包含用户查询词且被用户判断为不相关的。一个好的检索模型应该做到的是:在排序结果中,提升第一象限和第二象限文档的排名,抑制第三象限和第四象限文档的排名。
 

  [图片]图5-2 文档划分的4个象限
 

  读者看图5-2可能会产生疑问:如果文档不包含查询词,会是相关的搜索结果吗?答案很明显是肯定的,比如用户搜索“电脑”,如果一个文档没有出现过这个单词,但是出现了“PC”或者“计算机”,那也是相关的。至于处理此种情况,往往是查询扩展技术或者语义搜索讨论的范围,目前绝大多数检索模型考虑的文档对象主要是第一象限和第三象限的对象,即一定出现搜索词的文档。
 

  这里需要注意的一点是:检索模型理论研究都存在理想化的隐含假设,即假设用户需求已经通过查询非常清晰明确地被表达出来,所以检索模型的任务不牵扯到对用户需求建模。很明显这与事实相距甚远,即使是相同的查询词,不同用户的需求目的可能差异很大,而检索模型对此无能为力。所以可以将检索模型看做是:在用户需求已经很明确地由查询词表征的情况下,如何找出内容相关的文档。如果查询词不能精确代表用户真实需求,那么无论检索模型再优秀也无济于事,这是为何搜索引擎发展到目前阶段,重点转向了填补用户真实需求和发出的查询词之间的鸿沟的原因,此发展趋势有其必然性。
 

  5.1 布尔模型(Boolean Model)
 

  布尔模型是检索模型中最简单的一种,其数学基础是集合论。在布尔模型中,文档与用户查询由其包含的单词集合来表示,两者的相似性则通过布尔代数运算来进行判定。
 

  用户查询一般使用逻辑表达式,即使用“与/或/非”这些逻辑连接词将用户的查询词串联,以此作为用户的信息需求的表达。比如用户希望查找和苹果公司相关的信息,可以用以下逻辑表达式来作为查询:
 

  苹果AND(乔布斯OR iPad2)
 

  其代表的含义是:如果一篇文档包含单词“苹果”,同时也包含单词“乔布斯”或者“iPad2”两者其中的任意一个,那么这个文档就是满足用户需求的。所以对于布尔模型来说,满足用户逻辑表达式的文档就算是相关的。
 

  我们以具体例子来说明,图5-3是一个文档集合,其中包含5个文档,每个文档的内容在图5-3中都已标出。为了简单起见,我们只考虑“苹果”、“乔布斯”和“iPad2”这3个单词,在搜索系统内部,单词—文档矩阵如图5-4所示,其代表的含义是单词出现在哪些文档中,比如对于单词“苹果”来说,文档D2、D3、D5包含这个单词,在图中以对钩来表达这一状况,其他单词文档关系与此类似。
 

  [图片]图5-3 文档集合
 

  [图片]图5-4 单词—文档矩阵
 

  假设此时搜索系统接收到了用户查询:“苹果AND (乔布斯OR iPad2)”,搜索系统会检查单词—文档矩阵,找出满足这个逻辑表达式的文档。对于逻辑表达式“(乔布斯OR iPad2)”来讲,其含义是:文档需要包含单词“乔布斯”或者单词“iPad2”中任意一个。从单词—文档矩阵可以看出,满足这个逻辑条件的文档包括D1、D3、D4、D5,而包含“苹果”这个单词的文档集合是D2、D3、D5。
 

  档包括D1、D3、D4、D5,而包含“苹果”这个单词的文档集合是D2、D3、D5。按照用户查询的要求,两个集合求交集,得出D3、D5。这两个文档就是满足整个逻辑表达式的文档,将其输出即为搜索结果。
 

  由上可看出,布尔模型简单直观,但是正是因为其简单性,导致一些明显的缺点。从上面例子可以看出,只要文档满足逻辑表达式,就会被认为是相关的,其他文档被认为是不相关的,即其结果输出是二元的,要么相关要么不相关,至于文档在多大程度上和用户查询相关,能否按照相关程度排序输出搜索结果?这些布尔模型都无能为力,所以无法对搜索结果根据相关性进行排序,其搜索结果过于粗糙。同时,对于普通用户来说,要求其以布尔表达式的方式构建查询,无疑要求过高。
 

  5.2 向量空间模型(Vector Space Model)
 

  向量空间模型历史悠久,最初由信息检索领域奠基人Salton教授提出,经过相关学科几十年的探索,目前已经是非常成熟和基础的检索模型。向量空间模型作为一种文档表示和相似性计算的工具,不仅仅在搜索领域,在自然语言处理、文本挖掘等诸多其他领域也是普遍采用的有效工具。
 

  5.2.1 文档表示
 

  作为表示文档的工具,向量空间模型把每个文档看做是由t维特征组成的一个向量,特征的定义可以采取不同方式,可以是单词、词组、N-gram片段等多种形式,最常用的还是以单词作为特征。其中每个特征会根据一定依据计算其权重,这t维带有权重的特征共同构成了一个文档,以此来表示文档的主题内容。
 

  图5-5展示了4个文档在3维向量空间中如何表示,比如对于文档2来说,由3个带有权重的特征组成{w21,w22,w23},w21代表了第2个文档的第1维特征的权重,其他的权值代表相似含义。在实际应用系统中,维度是非常高的,达到成千上万维很正常,图中为了简化说明,只列出3个维度。在搜索这种应用环境下,用户查询可以被看做是一个特殊的文档,将其也转换成t维的特征向量。至于特征的权值如何计算,本节后面会专门讲述。
 

  [图片]图5-5 向量空间模型中的文档表示
 

  图5-6展示的是具体的文档表示实例,对于文档D4和D5及用户查询,通过特征转换,可以将其转换为带有权值的向量表示。
 

  [图片]图5-6 将文档转换为特征向量
 

  5.2.2 相似性计算
 

  将文档转换为特征向量后,就可以计算文档之间或者是查询和文档之间的相似性了。对于搜索排序这种任务来说,给定用户输入的查询,理论上应该计算查询和网页内容之间的“相关性”,即文档是否和用户需求相关,之后按照相关程度由高到低排序。向量空间模型将问题做了转换,即以查询和文档之间的内容相似性来作为相关性的替代,按照文档和查询的相似性得分由高到低排序作为搜索结果,但是要注意,两者并非等同的概念。
 

  给定用户查询特征向量和文档特征向量,如何计算其内容相似性?Cosine相似性是最常用也是非常有效的计算相似性的方式。Cosine相似性计算定义如下:
 

  [图片]
 

  这个公式计算用户查询Q和Di文档的相似性,公式中的分子部分,将文档的每个特征权值和查询的每个特征权值相乘取和,这个过程也叫做求两个向量的点积;公式的分母部分是两个特征向量在欧式空间中长度的乘积,作为对点积计算结果的规范化。之所以要对特征向量的长度做规范化操作,主要是对长文档的一种惩罚机制,否则的话,计算结果往往是长文档得分较高,而这并非因为长文档与查询更相关,而是因为其长度较长,导致特征权值比短文档要大,所以加入规范化操作抑制长文档在排序中的位置。
 

  Cosine公式中的规范化方法有一个明显的缺陷,即存在对长文档的过分抑制:如果同时有相关的短文档和长文档,它会使短文档的相关度数值大大高于长文档的相关度数值。设想以下情况:一篇短文档,与某主题相关;一篇长文档,除了与这个主题相关之外还讨论了多个其他主题,其中与这个主题相关的部分词频与短文档相仿。在这种情况下,两篇文档中有关这个主题的特征词的权值大致相当,长文档由于包含的索引词很多,文档向量长度比较大,规范化之后有关这个主题的特征词的权重会比短文档小得多。于是,经过相似度计算,短文档得到的相关度数值会比长文档高得多。在TREC测试任务中可以很清楚地观察到这种现象:使用Cosine规范化方法,对于一个包含4个词的查询,返回的第1个结果大多数是10个词以下的文档。
 

  为了便于理解Cosine相似性,可以将每个文档及查询看做是t维特征空间中的一个数值点,每个特征形成t维空间中的一个维度,连接特征空间原点和这个数值点形成一个向量,而Cosine相似性就是计算特征空间中两个向量之间的夹角,这个夹角越小,说明两个特征向量内容越相似,夹角越大,说明两个向量内容越不同。考虑一种极端情况:两个完全相同的文档,其在向量空间中的两个向量是重叠的,通过Cosine相似性计算得到的相似性结果为1。
 

  图5-7是上述计算的一个形象化示意图,在这个例子里,特征维度为3,即由“苹果”、“乔布斯”和“iPad2”3个单词组成特征空间,每个单词代表三维空间中的一个维度。对于文档D4、D5和查询“乔布斯 iPad2”,是三维空间中3个数值点,和坐标原点相连形成一个向量。查询和文档的相似性就是两个向量之间的夹角大小,从示例中可以看出,查询和文档D4之间的夹角要小于与文档D5形成的夹角,这意味着查询和文档D4更相似些。
 

  [图片]图5-7 Cosine相似性图示
 

  我们以Cosine计算公式来计算图5-6示例中的文档与查询的相似度,假设文档D4的特征向量为{0.0,0.8,0.5},即对于“乔布斯”的这个特征权值是0.8,“iPad2”的特征权值是0.5,由于D4中没有出现“苹果”,所以对应的特征权值是0。相似地,D5的特征向量为{0.3, 0.8, 0.0},用户查询“乔布斯 iPad2”的特征向量为{0.0,1.2,0.6}。有了特征向量,可以参照Cosine公式,计算出查询和文档D4、D5的相似性如下:从上述计算结果可以看出,文档D4与查询的Cosine相似性要大于文档D5与查询的相似性,在搜索结果排序中,会将D4排在D5前面。
 

  5.2.3 特征权重计算
 

  文档和查询转换为特征向量时,每个特征都会赋予一定的权值,本节叙述如何对特征计算相应的权值。在向量空间模型里,特征权值的计算框架一般被称做Tf*IDF框架,虽然具体计算方式可以有多种,但是大都遵循这一框架,而这一计算框架考虑的主要计算因子有两个:词频Tf和逆文档频率IDF。
 

  词频因子(Tf)
 

  Tf计算因子代表了词频,即一个单词在文档中出现的次数,一般来说,在某个文档中反复出现的单词,往往能够表征文档的主题信息,即Tf值越大,越能代表文档所反映的内容,那么应该给予这个单词更大的权值。这是为何引入词频作为计算权值的重要因子的原因。
 

  具体计算词频因子的时候,基于不同的出发点,可以采纳不同的计算公式。最直接的方式就是直接利用词频数,比如文档中某个单词出现过5次,就将这个单词的Tf值计为5。
 

  一种词频因子的变体计算公式是:
 

  WTf=1+log(Tf)
 

  即将词频数值Tf取Log值来作为词频权值,比如单词在文档中出现过4次,则其词频因子权值是3,公式中的数字1是为了平滑计算用的,因为如果Tf值为1的情况下,取Log后值为0,即本来出现了一次的单词,按照这种方法计算会认为这个单词从来没有在文档中出现过,为了避免这种情形,采用加1的方式来进行平滑。之所以要对词频取Log,是基于如下考虑:即使一个单词出现了10次,也不应该在计算特征权值时,比出现1次的情况权值大10倍,所以加入Log机制抑制这种过大的差异。
 

  另外一种单词词频因子的变体计算公式是:
 

  [图片]
 

  这种方法被称为增强型规范化Tf,其中的a是调节因子,过去经验取值0.5,新的研究表明取值为0.4效果更好。公式中的Tf代表这个单词的实际词频数目,而Max(Tf)代表了文档中所有单词中出现次数最多的那个单词对应的词频数目。之所以要如此操作,主要出于对长文档的一种抑制,因为如果文档较长,与短文档相比,则长文档中所有单词的Tf值会普遍比短文档的值高,但是这并不意味着长文档与查询更相关。用单词实际词频除以文档中最高词频,等于将绝对的数值进行了规范化转换,公式的含义就转换为:同一个文档内单词之间的相对重要性。即使一个文档很长,单词词频普遍很高,但是除以文档最高词频,那么通过这种计算方式得出的数值比短文档来说并不一定就大。这样就剔除了文档长度因素的影响,长文档和短文档的词频因子就成为可比的了。
 

  逆文档频率因子(IDF)
 

  词频因子是与文档密切相关的,说一个单词的Tf值,指的是这个单词在某个文档中的出现次数,同一个单词在不同文档中Tf值很可能不一样。而逆文档频率因子IDF则与此不同,它代表的是文档集合范围的一种全局因子。给定一个文档集合,那么每个单词的IDF值就唯一确定,跟具体的文档无关。所以IDF考虑的不是文档本身的特征,而是特征单词之间的相对重要性。
 

  所谓逆文档频率因子IDF,其计算公式如下:
 

  [图片]
 

  其中的N代表文档集合中总共有多少个文档,而nk代表特征单词k在其中多少个文档中出现过,即文档频率。由公式可知,文档频率nk越高,则其IDF值越小,即越多的文档包含某个单词,那么其IDF权值越小。IDF反映了一个特征词在整个文档集合中的分布情况,特征词出现在其中的文档数目越多,IDF值越低,这个词区分不同文档的能力越差。在极端情况下,考虑一个在文档集合中所有文档中都出现的特征词“term”,即nk=N,这说明无论搜索任何主题,“term”这个词都会出现在所有相关和不相关的文档中,因此“term”对任何主题都没有区分相关文档和不相关文档的能力,这时“term”的IDF值为0。例如,在一个有关计算机领域的文档集合中,特征词“电脑”几乎肯定会出现在所有文档中,这时用它进行搜索没有任何效果。但如果另一个文档集合中包括计算机领域相关的文档和很多有关经济学的文档,那么在这个集合中使用“电脑”搜索计算机相关的文档效果会比较好。也就是说,“电脑”这个特征词在第1个文档集合中区分不同文档的能力很差,在第2个文档集合中区分能力很强。而IDF就是衡量不同单词对文档的区分能力的,其值越高,则其区分不同文档差异的能力越强,反之则区分能力越弱。整体而言,IDF的计算公式是基于经验和直觉的,有研究者进一步分析认为:IDF代表了单词带有的信息量的多少,其值越高,说明其信息含量越多,就越有价值。
 

  Tf*IDF框架
 

  Tf*IDF框架就是结合了上述的词频因子和逆文档频率因子的计算框架,一般是将两者相乘作为特征权值,特征权值越大,则越可能是好的指示词,即:
 

  Weightword=Tf×IDF
 

  从上述公式可以看出,对于某个文档D来说:
 

  如果D中某个单词的词频很高,而且这个单词在文档集合的其他文档中很少出现,那么这个单词的权值会很高。
 

  如果D中某个单词的词频很高,但是这个单词在文档集合的其他文档中也经常出现,或者单词词频不高,但是在文档集合的其他文档中很少出现,那么这个单词的权值一般。
 

  如果D中某个单词词频很低,同时这个单词在文档集合的其他文档中经常出现,那么这个单词权值很低。
 

  经过几十年的不断探索,向量空间模型已经相当成熟,并被各种领域广泛采用。从数学模型的角度看,向量空间模型简单直观,用查询和文档之间的相似性来模拟搜索中的相关性。与布尔模型相比,也能对文档与查询的相关性进行打分排序。但是总体而言,向量空间模型是个经验型的模型,是靠直觉和经验不断摸索完善的,缺乏一个明确的理论来指导其改进方向。
 

  5.3 概率检索模型
 

  概率检索模型是目前效果最好的模型之一,在TREC等各种检索系统评测会议已经证明了这一点,而且okapi BM25这一经典概率模型计算公式已经在商业搜索引擎的网页排序中广泛使用。
 

  5.3.1 概率排序原理
 

  概率检索模型是从概率排序原理推导出来的,所以理解这一原理对于理解概率检索模型非常重要。概率排序原理的基本思想是:给定一个用户查询,如果搜索系统能够在搜索结果排序时按照文档和用户需求的相关性由高到低排序,那么这个搜索系统的准确性是最优的。而在文档集合的基础上尽可能准确地对这种相关性进行估计则是其核心。
 

  从概率排序原理的表述来看,这是一种直接对用户需求相关性进行建模的方法,这点与向量空间模型不同,向量空间模型是以查询和文档的内容相似性来作为相关性的代替品。
 

  概率排序原理只是一种指导思想,并未阐述如何才能做到这种理想的情形,在这个框架下,怎样对文档与用户需求的相关性建立模型呢?用户发出一个查询请求,如果我们把文档集合划分为两个类别:相关文档子集和不相关文档子集,于是就可以将这种相关性衡量转换为一个分类问题。
 

  图5-8示意了概率模型作为一个分类问题,对于某个文档D来说,如果其属于相关文档子集的概率大于属于不相关文档子集的概率,我们就可以认为这个文档与用户查询是相关的。图中的P(R│D)代表给定一个文档D对应的相关性概率,而P(NR│D)则代表该文档的不相关概率。即如果P(R│D)>P(NR│D),我们可以认为文档与用户查询是相关的。
 

  [图片]
 

  所以现在问题的关键是如何估算P(R│D)和P(NR│D)的数值。为了简化问题,首先我们根据贝叶斯规则对两个概率值进行改写,即:
 

  [图片]
 

  [图片]
 

  相关性计算的目的是要判断是否P(R│D)>P(NR│D),将改写公式代入成为如下形式:
 

  [图片]
 

  因为是同一篇文档,所以右端公式的分母P(D)是相同的,在做相关性判断的时候可以消掉,并对因子移项,转换成如下形式:
 

  [图片]
 

  尽管概率模型将相关性判断转换为一个二值分类问题,但搜索应用并不需要进行真正的分类,而是将搜索结果按照相关性得分由高到低排序,所以对于搜索系统来说只需要将文档按照[图片]大小降序排列即可,于是问题进一步转换成如何估算因子P(D│R)和P(D│NR),而二元独立模型提供了计算这些因子的框架。
 

  5.3.2 二元独立模型(Binary Independent Model)
 

  为了能够使得估算上述两个计算因子可行,二元独立模型(BIM模型)做出了两个假设:
 

  假设1:二元假设
 

  所谓二元假设,类似于布尔模型中的文档表示方法,一篇文档在由特征进行表示的时候,以特征“出现”和“不出现”两种情况来表示,不考虑词频等其他因素。假设特征集合包含5个单词,某个文档D根据二元假设,表示为{1,0,1,0,1},其含义是这个文档出现了第1个、第3个和第5个单词,但是不包含第2个和第4个单词。做出二元假设是将复杂问题简单化的一种措施。
 

  假设2:词汇独立性假设
 

  所谓词汇独立性假设,是指文档里出现的单词之间没有任何关联,任意一个单词在文档的分布概率不依赖于其他单词是否出现。这个假设很明显和事实不符,比如一篇文档出现了单词“乔布斯”,那么出现“苹果”、“iPad”这些单词的概率显然很大,即单词之间是有依赖性的。但是为了简化计算,很多方法都会做出词汇独立性假设。有了词汇独立性假设,我们就可以将对一个文档的概率估计转换为对文档包含单词的概率估计,因为词汇之间没有关联,所以可以将文档概率转换为单词概率的乘积。
 

  在以上两个前提假设下,二元独立模型即可对两个因子P(D│R)和P(D│NR)进行估算,在进行形式化描述前,我们举个简单的例子。
 

  上文提到的文档D表示为{1,0,1,0,1},我们用pi来代表第i个单词在相关文档集合内出现的概率,于是在已知相关文档集合的情况下,观察到文档D的概率为:
 

  [图片]
 

  因为在文档中出现了第1个、第3个和第5个单词,所以这些单词在相关文档集合中出现的概率为pi,而第2个和第4个单词没有出现,那么1-pi就代表了单词不在文档出现的概率,根据词汇独立性假设,将对文档D的概率估计转换为每个单词概率的乘积,这样就可以估算因子P(D│R)。
 

  对于因子P(D│NR),我们假设用si代表第i个单词在不相关文档集合内出现的概率,于是在已知不相关文档集合的情况下,观察到文档D的概率为:
 

  [图片]
 

  两个因子已经估算完毕,于是我们可以估算[图片],即:
 

  [图片]
 

  如果可以从文档集合估计pi和si,那么我们就可以对文档的相关性进行直接计算。这是一个具体的实例,下面我们用形式化方式表示如何计算[图片]:
 

  [图片]
 

  这个公式与上面实例所列公式含义相同,只不过将各个计算因子归为两个部分,其中[图片]代表了在文档D中出现过的各个单词的概率乘积,[图片]则代表了没有在文档D中出现的各个特征单词的概率乘积。进一步对这个公式进行一些数学等价变换,可得:
 

  [图片]
 

  即将计算公式分解为两个组成部分,第1个组成部分[图片]代表在文档中出现过的单词所计算得到的单词概率乘积,第2个部分[图片]代表对所有特征词计算所得到的单词概率乘积。因为pi和si是从相关文档和不相关文档集合中统计出来的全局概率,所以与具体文档无关,这说明对于所有文档来说第2个部分得分都一样,所以在排序中不起作用,于是可以将这个部分消掉,得到最终的相关性估算公式:
 

  [图片]
 

  出于计算方便,可以对上述公式取log值,得到如下相关性估值公式:
 

  [图片]
 

  到目前为止,我们已经获得了计算相关性的具体方法,剩下的问题就是如何计算单词概率pi和si。给定用户查询,如果我们可以确定哪些文档构成了相关文档集合,哪些文档构成了不相关文档集合,可以利用下表所列数据来估算单词概率:
 

  表中第3行的N为文档集合总共包含的文档个数,R为相关文档的个数,于是N-R就是不相关文档集合的大小。对于某个单词di来说,假设包含这个单词的文档数量共有ni个,而其中相关文档有ri个,那么不相关文档中包含这个单词的文档数量则为ni-ri。再考虑表中第2列,因为相关文档个数是R,而其中出现过单词di的有ri个,那么相关文档中没有出现过这个单词的文档个数为R-ri个,同理,不相关文档中没有出现过这个单词的文档个数为(N-R)-(ni-ri)个。从表中可以看出,如果我们假设已经知道N、R、ni、ri的话,其他参数是可以靠这4个数值推导出来的。
 

  根据表格数据,即可估算si和pi。si因为pi代表第i个单词在相关文档集合内出现的概率,在BIM模型的二元假设下,可以用包含这个单词的相关文档个数ri除以相关文档总数R来估算,即pi=ri/R。而si代表第i个单词在不相关文档集合内出现的概率,所以可以用包含这个单词的不相关文档个数ni-ri除以不相关文档总数(N-R)来估算,即si=ni-ri/(N-R)。把这两个估值公式代入相关性估值公式即可得出如何计算相关性,但是这里有个问题,相关性估值公式采取了log形式,如果ri=0,那么会出现log(0)的情形,为了避免这种情况,我们对pi和si的估值公式进行平滑,分子部分加上0.5,分母部分加上1.0,即:
 

  将这两个估值因子代入相关性估算公式,得到如下公式:
 

  [图片]
 

  其代表的含义是:对于同时出现在用户查询Q和文档D中的单词,累加每个单词的估值,其和就是文档D和查询的相关性度量。这即是二元独立模型推导出的用户查询和文档之间的相关性计算方法,如果我们事先不知道哪些是相关文档,哪些是不相关文档,可以给公式的估算因子赋予固定值,此种情况下该公式等价于在向量空间模型中提到的IDF因子。各种实验表明,根据二元独立模型计算相关性实际效果并不好,但是这个模型却是非常成功的概率模型方法BM25的基础,这是为何本节花较大篇幅介绍BIM模型的原因。
 

  5.3.3 BM25模型
 

  BIM模型基于二元假设推导而出,即对于单词特征,只考虑是否在文档中出现过,而没有考虑单词的权值。BM25模型在BIM模型基础上,考虑了单词在查询中的权值及单词在文档中的权值,拟合出综合上述考虑因素的公式,并通过实验引入一些经验参数。BM25模型是目前最成功的内容排序模型。
 

  图5-9展示了BM25模型的具体计算公式,对于查询Q中出现的每个查询词,
 

  依次计算单词在文档D中的分值,累加后就是文档D与查询Q的相关性得分。从图中可以看出,计算第i个查询词的权值时,计算公式可以拆解为3个组成部分,第1个组成部分就是上节所述的BIM模型计算得分,上节也提到,如果赋予一些默认值的话,这个部分的公式等价于IDF因子的作用;第2个组成部分是查询词在文档D中的权值,其中fi代表了单词在文档D中的词频,k1和K是经验参数;第3个组成部分是查询词自身的权值,其中qfi代表查询词在用户查询中的词频,如果查询较短小的话,这个值往往是1,k2是经验参数。BM25模型就是融合了这3个计算因子的相关性计算公式。
 

  [图片]图5-9 BM25计算公式
 

  在第2个计算因子中,K因子代表了对文档长度的考虑,图中所示K的计算公式中,dl代表文档D的长度,而avdl则是文档集合中所有文档的平均长度,k1和b是经验参数。其中参数b是调节因子,极端情况下,将b设定为0,则文档长度因素将不起作用,经验表明一般将b设定为0.75会获得较好的搜索效果。
 

  BM25公式中包含3个自由调节参数,除了调节因子b外,还有针对词频的调节因子k1和k2。k1的作用是对查询词在文档中的词频进行调节,如果将k1设定为0,则第2部分计算因子成了整数1,即不考虑词频的因素,退化成了BIM模型。如果将k1设定较大值,则第2部分计算因子基本和词频fi保持线性增长,即放大了词频的权值,根据经验,一般将k1设定为1.2。调节因子k2和k1的作用类似,不同点在于其是针对查询中的词频进行调节,一般将这个值设定在0到1000较大的范围内,之所以如此,是因为查询往往很短,所以不同查询词的词频都很小,词频之间差异不大,较大的调节参数数值设定范围允许对这种差异进行放大。
 

  综合来看,BM25模型计算公式其实融合了4个考虑因素:IDF因子、文档长度因子、文档词频和查询词频,并利用3个自由调节因子(k1、k2和b)对各种因子的权值进行调整组合。
 

  下面我们以用户查询“乔布斯iPad2”为例子,来看看如何实际利用BM25公式计算某个文档D的相关性。首先假定BM25的第1个计算因子中,我们不知道哪些是相关文档,所以将相关文档个数R和包含查询词的相关文档个数r设定为0,此时第1个计算因子退化成类似于IDF的形式:
 

  [图片]
 

  因为查询中两个查询词都只出现了一次,所以其对应的都为1。其他数值假定如下:
 

  文档集合总数N=100000
 

  文档集合中包含单词“乔布斯”的文档个数n乔布斯=1000文档集合中包含单词“iPad2”的文档个数niPad2=100
 

  文档D中出现单词“乔布斯”的词频f乔布斯=8
 

  文档D中出现单词“iPad2”的词频fiPad2=5
 

  调节因子=1.2
 

  调节因子=200
 

  调节因子b=0.75
 

  假定文档长度是平均文档长度的1.5倍,即K=1.2×(0.25+0.75×1.5)=1.65,将这些数值代入BM25计算公式,可以得出文档D和查询的如下相关性得分:
 

  [图片]
 

  对于文档集合里的所有文档,都按照上述方法计算,将计算结果按照大小排序,就根据BM25公式得出了内容相关性排序。
 

  5.3.4 BM25F模型
 

  Okapi BM25模型于1994年提出,之后被广泛研究并应用在不同系统里,也陆续有在此基础上的改进算法出现。2004年推出的BM25F模型就是一个很典型的BM25改进算法。
 

  BM25模型在计算一个文档和查询的相关性的时候,是把文档当做一个整体来看待的,但是在有些应用场景下,需要将文档内容切割成不同的组成部分,然后对不同成分分别对待。最典型的应用场景就是网页搜索,一个网页由页面标题、Meta描述信息、页面内容等不同的“域”(Field)构成,在计算内容相关性得分的时候,往往希望标题的权重大些,因为标题是一个网页的中心思想简述。而BM25由于没有考虑这点,所以不容易做到不同“域”的内容给予不同权重,BM25F就非常适合这种将文档划分为若干“域”,不同“域”需要不同权值的应用场景。
 

  BM25F思路如上,但是不同系统有各异的具体计算方法,本节叙述其中的一种,为了让公式看起来简洁一些,我们用[图片]代替BIM推导出的部分,也即BM25公式的第1个组成部分:
 

  [图片]
 

  BM25F的计算公式如下:
 

  [图片]
 

  BM25F公式与BM25的区别体现在第2个计算因子中的[图片]上,这个因子综合了第i个单词出现在不同“域”的得分,其定义如下:
 

  [图片]
 

  [图片]
 

  假设一个文档D包含了u个不同的“域”,而每个“域”的权值设定为Wk,[图片]将第i个单词在各个不同“域”的分值fui/Bu加权求和,其中fui代表单词在第u个“域”出现的词频数,Bu则是“域”长度因素。对于Bu来说,ulu是这个“域”的实际长度,avulu是文档集合中这个“域”的平均长度,而bu则是调节因子,这里要注意的一点是:不同的“域”要设定不同的调节因子,这样搜索效果才好。所以对于BM25F来说,除了调节因子k1外,如果文档包含u个不同的“域”,则还需要凭经验设定u个“域”权值和u个长度调节因子。
 

  5.4 语言模型方法
 

  基于统计语言模型的检索模型于1998年首次提出,是借鉴了语音识别领域采用的语言模型技术,将语言模型和信息检索相互融合的结果。
 

  从基本思路上来说,其他的大多数检索模型的思考路径是从查询到文档,即给定用户查询,如何找出相关的文档。语言模型方法的思路正好相反,是由文档到查询这个方向,即为每个文档建立不同的语言模型,判断由文档生成用户查询的可能性有多大,然后按照这种生成概率由高到低排序,作为搜索结果。
 

  给定了一篇文档和对应的用户查询,如何计算文档生成查询的概率呢?图5-10展示了利用语言模型来生成查询的过程。首先,可以为每个文档建立一个语言模型,语言模型代表了单词或者单词序列在文档中的分布情况。我们可以想象从文档的语言模型生成查询类似于从一个装满“单词”的壶中随机抽取,一次抽取一个单词,这样,每个单词都有一个被抽取到的概率。对于查询中的单词来说,每个单词都对应一个抽取概率,将这些单词的抽取概率相乘就是文档生成查询的总体概率。
 

  [图片]图5-10 文档生成查询
 

  以图5-10中的文档为例,可以看出,文档D包含5个单词{乔布斯,出门,买了,4袋,苹果},每个单词出现次数都是1次,所以抽取到这5个单词的概率大小相同,都为0.2,这个单词抽取概率分布就是文档D对应的一元语言模型。为文档建立一元语言模型后,即可计算文档D生成用户查询{苹果,乔布斯,iPad2}的概率:
 

  P(Q│D)=P(苹果│D)×P(乔布斯│D)×P(iPad2│D)=0.2×0.2×0=0
 

  因为文档中出现过“苹果”和“乔布斯”两个单词,其对应的概率都为0.2,但是由于文档D没有出现过单词“iPad2”,所以这个单词的生成概率为0,导致查询整体的生成概率也为0。从这个例子可以看出,由于一个文档文字内容有限,所以很多查询词都没有在文中出现过,这会导致基于语言模型的检索方法失效,这个问题被称做语言模型的数据稀疏问题,是语言模型方法重点需要解决的问题。
 

  一般采用数据平滑的方式解决数据稀疏问题,所谓数据平滑,可以理解为单词分布概率领域的“劫富济贫”,即从文档中出现过的单词的分布概率值中取出一部分,将这些值分配给文档中没有出现过的单词,这样所有单词都有一个非零的概率值,避免计算中出现问题。
 

  语言模型检索方法则是为所有单词引入一个背景概率来做数据平滑。所谓背景概率,就是给文档集合建立一个整体的语言模型,因为其规模比较大,所以绝大多数查询词都有一个概率值。对于文档集合的一元语言模型,某个单词的背景概率就是这个单词出现的次数除以文档集合的单词总数,这与一个文档计算语言模型是一致的,可以将背景概率的计算理解为:将文档集合内所有文档拼接成一个虚拟的大文档,然后给这个虚拟文档建立语言模型。所以,对于语言模型方法来说,如果文档集合包含N个文档,则需要建立N+1个不同的语言模型,其中每个文档建立自己的语言模型,而文档集合语言模型则作为数据平滑的用处。
 

  图5-11是加入数据平滑后的文档生成查询概率计算公式,可以看出,每个查询词的生成概率由两部分构成,一部分是之前提到的文档语言模型,另一部分是用做平滑的文档集合语言模型。两者之间可以通过参数调节其权重。
 

  [图片]图5-11 文档生成查询概率计算
 

  了解了如何计算某个文档生成查询的概率,那么如何对文档按照相关性排序也就很清楚了。图5-12是基于语言模型方法的检索系统对搜索结果排序的示意图,用户提交查询Q,文档集合内所有文档都计算生成Q的概率,然后按照生成概率值由大到小排序,这就是搜索结果。
 

  [图片]图5-12 语言模型排序
 

  上述是最基本的语言模型检索方法思路,很多研究在此基础上做出了改进,比如HMM隐马尔科夫语言模型、相关模型、翻译模型等诸多改进模型对基础模型做出了改进。目前各种检索评测证明,语言模型检索方法效果略优于精调参数的向量空间模型,与BM25等概率模型效果相当。
 

  语言模型检索方法从形式上看与向量空间模型和概率模型有很大差异,其实它们之间有密切联系。通过理论推导,可以得出:语言模型检索方法的排序公式符合概率模型的概率排序原理,所以可以归为概率模型的一种。另外,通过一些公式变形推导,可以将其公式转化为类似于向量空间模型的Tf*IDF的形式,这说明了几种模型在利用计算因子方面的一致性。
 

相关内容推荐:

Top