检索模型与搜索排序

  搜索结果排序是搜索引擎最核心的构成部分,很大程度上决定了搜索质量的好坏和用户接受与否,其最重要的两个因素是用户查询与网页的相关性以及网页链接情况,判断用户查询与网页内容的相关性依赖于搜索引擎所采用的检索模型,这里介绍几种重要的检索模型:布尔模型、向量空间模型、概率模型。

布尔模型

  布尔模型是检索模型中最简单的一种,其数学基础是集合论。在布尔模型中,文档与用户查询由其所包含的单词集合来表示,两者的相似性则通过布尔代数运算来进行判定。
  用户查询内容一般使用布尔表达式,即使用“与/或/非”这些逻辑连接词将用户的查询词串联,依次最为用户的信息需求的表达。
  布尔模型简单直观,导致一些明显的缺点。只要文档满足逻辑表达式,就会被认为是相关的,否则被认为是不相关的,其结果输出是二元的,即要么相关,要么不相关。至于文档在多大程度上与用户查询相关,能够按照相关程度排序输出搜索结果?这些布尔模型就无能为力了。

向量空间模型

  向量空间模型历史悠久,由信息检索领域奠基人 Salton 教授提出。向量空间模型作为一种文旦表示和相似性计算的工具,不仅仅在搜索领域,在自然语言处理、文本挖掘等诸多领域也是普遍采用的有效工具。

文档表示

  作为表示文档的工具,向量空间模型把每个文档看做是由 $t$ 维特征组成的一个向量,特征的定义一般为单词。其中,每个特征会更具一定依据计算其权值,这 $t$ 维带有权重的特征共同构成了一个文档,以此来表示文档的主题内容。

相似性计算

  将文档转化为特征向量后,就可以计算文档之间或者查询和文档之间的相似性了。对于搜索排序这种任务,理论上应该计算查询和网页内容之间的“相关性”,即文档与用户需求之间的相关性,之后按照相关程度高低排序。向量空间模型将问题做了转换,即以查询和文档内容之间的相似性来替代相关性,按照文档与查询的相似性得分高低排序来作为搜索结果,但两者并非同一概念。
  给定用户查询的特征向量和文档的特征向量,Cosine 相似性是最常用也是最有效的计算相似性的方式。Cosine 相似性计算定义如下:
$$Cosine(Q,D_i)=\frac{\sum_{j=1}^{t}w_{ij}\times{q_j}}{\sqrt{\sum_{j=1}^{t}w_{ij}^2\times\sum_{j=1}^{t}q_j^2}}$$
  这个公式计算用户查询 $Q$ 和 $D_i$ 文档的相似性,该公式的分子部分是将文档的每个特征权值和查询的每个特征权值相乘取和,也即两个向量的点积;公式的分母部分是两个特征向量在欧式空间中长度的乘积,作为对点积结果的规范化(对长文档的一种惩罚机制)。
  Cosine 公式一个明显的缺陷就是对长文档的过分抑制。Cosine 相似性的集合解释就是特征空间中两个特征向量的夹角,这个夹角越小,那么这两个特征向量的内容也越相似,夹角越大,则两个向量的内容差异越大。

特征权重计算

  在向量空间模型中,特征权值计算框架一般被称为 Tf*IDF 框架,这一框架的两个计算因子是:词频 Tf 和逆文档词频 IDF。
  词频因子(Tf)
  Tf 计算因子代表了词频,即一个单词在文档中出现的次数,一般来说,在某个文档中反复出现的单词,往往能够表征文档的主题信息,即 Tf 值越大,越能代表文档所反映的内容,那么应该赋予该单词更大的权值。
  具体计算词频因子的时候,基于不同的出发点,可以采纳不同的计算公式。一种词频因子的变体计算公式是:
$$W_{Tf}=1+\log{Tf}$$
  另外一种单词词频因子变体计算公式为:
$$W_{Tf}=a+(1-a)\times\frac{Tf}{Max(Tf)}$$
  这种方法被称为增强型规范化 Tf,其中的 a 是调节因子,取值0.4效果较好。公式中的 Tf 代表这个单词的实际词频数目,而 Max(Tf) 代表了文档中所有单词出现次数最多的那个单词对应的词频数目。这样做的目的是对长文档的一种压制。
  逆文档频率因子(IDF)
  词频因子是与文档密切相关的,而逆文档频率因子 IDF 代表的是文档集合范围内的一种全局因子。给定一个文档集合,那么每个单词的 IDF 值就唯一确定,跟具体的文档无关。所以 IDF 考虑的不是文档本身的特征,而是特征单词之间的相对重要性。
  逆文档频率因子 IDF 计算公式如下:
$$IDF_k=\log{\frac{N}{n_k}}$$
  其中,N 代表文档集合中文档的总数,而 $n_k$ 包含特征单词 k 的文档数量,即文档频率。由公式可知,文档频率 $n_k$ 越高,则其 IDF 值越小,即越多文档包含某个特征单词,那么其 IDF 权值越小。IDF 反映的是特征词在整个文档集合中的分布情况,特征次出现的文档数目越多,IDF 值越低,这个词区分不同文档的能力就越差。整体而言,IDF 的计算公式是基于直觉和经验的,IDF代表了单词带有的信息量的多少,其值越高,说明其信息含量越多,就越有价值。
  Tf*IDF 框架
  Tf*IDF 框架就是结合了上述的词频因子和逆文档频率因子的计算框架,一般式将两者相乘作为特征权值,特征权值越大,则越可能是好的指示词,即:
$$Weight_{word}=Tf\times IDF$$
  从上述公式可以看出,对某个文档 D 来说:
  如果 D 中某个单词的词频很高,而且这个单词在文档集合的其它文档中很少出现,那么这个单词的权值会很高。
  如果 D 中某个单词的词频很高,但是这个单词在文档集合的其它文档中经常出现,或者单词词频不高,但是在文档集合的其它文档中很少出现,那么这个单词的权值一般。
  如果 D 中某个单词的词频很低,同时这个单词在文档集合的其它文档中经常出现,那么这个单词权值很低。

概率检索模型

  概率检索模型是目前效果最好的模型之一,在 TREC 等各种检索系统评测会议已经证明了这一点。

概率排序原理

  概率排序的基本思想是:给定一个用户查询,如果搜索系统能够在搜索结果排序时按照文档和用户需求的相关性由高到低排序,那么认为这个搜索系统的准确性是最优的。而在文档集合的基础上尽可能准确地对这种相关性进行估计则是其核心。
  从概率排序的原理来看,这是一种直接对用户需求相关性进行建模的方法,这点与向量空间模型不同,向量空间模型是以查询和文档的相似性来代替相关性。
  概率排序原理只是一种指导思想,怎样对文档与用户需求进行相关性建模?用户发出一个查询请求时,如果我们把文档集合划分为两个类别:相关文档子集和不相关文档子集,于是就可以将这种相关性衡量转换为一个分类问题。
  对于某个文档 D 而言,如果其属于相关文档子集的概率大于属于不相关文档子集的概率,我们就可以认为这个文档与用户查询是相关的。假设 $P(R|D)$ 代表给定一个文档 D 对应的相关性概率,而 $P(NR|D)$ 代表该文档的不相关性概率。即如果 $P(R|D)>P(NR|D)$,我们可以认为文档与用户查询相关。
  由贝叶斯规则可得:
$$P(R|D)=\frac{P(D|R)R(R)}{P(D)} \\\
P(NR|D)=\frac{P(D|NR)P(NR)}{P(D)}$$
  相关性计算的目的是要判断是否 $P(R|D)>P(NR|D)$,即:
$$\begin{align}
P(R|D)>P(NR|D) & \iff \frac{P(D|R)R(R)}{P(D)}>\frac{P(D|NR)P(NR)}{P(D)} \\\
& \iff \frac{P(D|R)}{P(D|NR)}>\frac{P(NR)}{P(R)}
\end{align}$$
  尽管概率模型将相关性判断转换为一个二值分类问题,但搜索系统并不是要真正的分类,而是将搜索结果按照相关性得分由高到低排序,所以对于搜索系统来说只要将文档按照 $\frac{P(D|R)}{P(D|NR)}$ 大小降序排列即可,于是问题被转化为如何估算因子 $P(D|R)$ 和 $P(D|NR)$,而二元独立模型提供了计算这些因子的 框架。

二元独立模型

  为了能够使得估算上述两个因子可行,二元独立模型(BIM模型)做出了两个建设:
  假设1:二元假设
  所谓二元假设,类似布尔模型中的文档表示方法,一篇文档在由特征进行表示的时候,以特征“出现”和“不出现”两种情况来表示,不考虑词频等其他因素。假设特征集合包含5个单词,某个文档 D 根据二元假设,表示为 {1,0,1,0,1},其含义是这个文档出现了第1、3、5个单词,但不包含第2、4个单词。做出二元假设是将复杂问题简单化的一种措施。
  词汇独立性假设
  所谓词汇独立性假设,是指文档中出现的单词之间没有任何联系,任意一个单词在文档的分布概率不依赖于其他单词是否出现。这个假设显然与现实不符,但是为了简化计算,很多方法都会做出词汇独立性假设。有了词汇独立性假设,我们可以将对一个文档的概率估计转换为对文档包含单词的概率估计,也即可以将文档概率转换为单词概率的乘积。
  对于上文提到的文档 D 表示为 {1,0,1,0,1},用 $p_i$ 表示第 i 个单词在相关文档集合内出现的概率,于是在已知相关文档集合的情况下,观察到的文档 D 的概率为:
$$P(D|R)=p_1\times(1-p_2)\times p_3\times(1-p_4)\times p_5$$
  假设用 $s_i$ 表示第 i 个单词在不相关文档集合内出现的概率,于是在已知不相关文档集合的情况下,观察到文档 D 的概率为:
$$P(D|NR)=s_1\times(1-s_2)\times s_3\times(1-s_4)\times s_5$$
  两个因子估算完毕,于是我们可以估算 $\frac{P(D|R)}{P(D|NR)}$,即:
$$\frac{P(D|R)}{P(D|NR)} = \frac{p_1\times(1-p_2)\times p_3\times(1-p_4)\times p_5}{s_1\times(1-s_2)\times s_3\times(1-s_4)\times s_5}$$
  从这个具体的实例,我们用形式化方式表示为:
$$\frac{P(D|R)}{P(D|NR)} = \prod_{i:d_i=1}\frac{p_i}{s_i}\times\prod_{i:d_i=0}\frac{1-p_i}{1-s_i}$$
  其中 $\prod_{i:d_i=1}$ 代表在文档 D 中出现过的各个单词的概率乘积,$\prod_{i:d_i=0}$ 代表没有在文档 D 中出现的各个特征单词的概率乘积。进一步变换得:
$$\begin{align}
\frac{P(D|R)}{P(D|NR)} & = \prod_{i:d_i=1}\frac{p_i}{s_i}\times\Big(\prod_{i:d_i=1}\frac{1-s_i}{1-p_i}\times\prod_{i:d_i=1}\frac{1-p_i}{1-s_i}\Big)\times\prod_{i:d_i=0}\frac{1-p_i}{1-s_i} \\\
& = \Big(\prod_{i:d_i=1}\frac{p_i}{s_i}\times\prod_{i:d_i=1}\frac{1-s_i}{1-p_i}\Big)\times\Big(\prod_{i:d_i=1}\frac{1-p_i}{1-s_i}\times\prod_{i:d_i=0}\frac{1-p_i}{1-s_i}\Big) \\\
& = \prod_{i:d_i=1}\frac{p_i(1-s_i)}{s_i(1-p_i)}\times\prod_{i}\frac{1-p_i}{1-s_i}
\end{align}$$
  该公式第一个组成部分 $\prod_{i:d_i=1}$ 代表在文档中出现的单词所计算得到的单词概率乘积,第二个部分代表 $\prod_{i}$ 代表对所有特征词计算得到的单词概率乘积。因为 $p_i$ 和 $s_i$ 是从相关文档和不相关文档集合中统计出来的全局概率,所以与具体文档无关,在排序中不起作用,于是得到最终的相关性估算公式:
$$\frac{P(D|R)}{P(D|NR)} = \prod_{i:d_i=1}\frac{p_i(1-s_i)}{s_i(1-p_i)}$$
  为了计算方便,对上述公式取 log 值,得到:
$$\frac{P(D|R)}{P(D|NR)} = \sum_{i:d_i=1}\log{\frac{p_i(1-s_i)}{s_i(1-p_i)}}$$
  到目前为止,我们已经获得了计算相关性的具体方法,接下来是如何计算单词概率 $p_i$ 和 $s_i$。给定用户查询,如果我们能确定那些文档构成了相关文档集合,那些文档构成了不相关文档集合,可以利用下表所列数据估算单词概率:

  表中第3行的 $N$ 为文档集合总共包含的文档个数,$R$ 为相关文档的个数,于是 $N-R$ 就是不相关文档的个数。从表中可以看出,其它参数都可以由 $N、R、n_i、r_i$ 4个数值推出。
  根据表格数据,即可估算 $s_i$ 和 $p_i$。在 BIM 模型的二元假设下,有 $p_i=r_i/R, s_i=(n_i-r_i)/(N-R)$。为避免 $log(0)$ 情况的出现可能,对 $p_i$ 和 $s_i$ 的估值公式进行平滑,分子部分加上 0.5,分母部分加上 1.0,即:
$$P_i=(r_i+0.5)/(R+1.0) \\\
S_i = (n_i-r_i+0.5)/(N-R+1.0)$$
  将这两个估值因子带入相关性估算公式,得到如下公式:
$$\sum_{i:q_i=d_i=1}\log{\frac{(r_i+0.5)/(R-r_i+0.5)}{(n_i-r_i+0.5)/((N-R)-(n_i-r_i)+0.5)}}$$
  其代表的含义是:对于同时出现在用户查询 Q 和文档D中的单词,累加每个单词的估值,其和就是文档D和查询的相关性度量。如果我们事先不知道那些是相关文档,那些是不相关文档,可以给公式的估算因子赋予固定值,这种情况下该公式等价于在向量空间模型中提到的 IDF 因子。实验表明,根据二元独立关系模型计算相关性实际效果并不好,但是这个模型是非常成功的概率模型方法 BM25 的基础。

BM25 模型

  BIM 模型是基于二元假设推导而出,即对于单词特征,只考虑是否在文档中出现过,而没有考虑单词的权值。BM25 模型在 BIM模型基础上,考虑了单词在查询中的权值以及单词在文档中的权值,拟合出综合上述考虑因素的公式,并通过实验引入一些参数。BM25 模型是目前最成功的内容排序模型。
  BM25 模型的具体计算公式如下:
$$\sum_{i\in Q}\log{\frac{(r_i+0.5)/(R-r_i+0.5)}{(n_i-r_i+0.5)/((N-R)-(n_i-r_i)+0.5)}}\cdot\frac{(k_1+1)f_i}{K+f_i}\cdot\frac{(k_2+1)qf_i}{k_2+qf_i}$$
  对于查询 Q 中出现的每个查询词,依次计算单词在文档 D 中的分值,累加后就是文档 D 与查询 Q 之间的相关性得分。由公司可知:第1个组成部分就是上节所述的 BIM 模型计算得分;第2个组成部分是查询词在文档 D 中的权值,其中 $f_i$ 代表了单词在文档 D 中的词频,$k_1$ 和 $K$ 是经验参数;第3个部分是查询词自身的权值,其中 $qf_i$ 代表查询词在用户查询中的词频,如果查询词较短小的话,这个值往往是 1,$k_2$ 是经验参数。BM25 模型就是融合了这 3 个计算因子的相关性计算公式。
  在第2个计算因子中,
$$K=k_1((1-b)+b\cdot\frac{dl}{avdl})$$
  $K$ 因子代表了相对文档长度的考虑,dl 代表文档 D 的长度,而 avdl 则是文档集合中所有文档的平均长度,$k_1$ 和 b 是经验参数。通常情况下将 b 设定为 0.75 会获得较好的搜索结果。
  BM25 公式中包含3个自由调节参数,除了调节因子 b 外,还有针对词频的调节因子 $k_1$ 和 $k_2$。$k_1$ 的作用是对查询词在文档中的词频进行调节,一般设为 1.2。调节因子 $k_2$ 与 $k_1$ 类似,一般设定在 0 到 1000 较大的范围内。原因是查询往往很短,不同查询词的词频都很小,词频之间的差异不大,较大的调节参数数值设定范围允许对这种差异进行放大。
  实例:
  假设现有两个查询词 A 和 B,首先假定 BM25 中的第一个计算因子中,我们不知道哪些是相关文档,所以将所有相关文档个数 R 和包含相关文档个数 r 设定为 0,此时第1个计算因子退化成类似 IDF 的形式:
$$\log\frac{(0+0.5)/(0-0+0.5)}{(n_i-0+0.5)/((N-0)-(n_i-0)+0.5)}\iff \log\frac{N-n_i+0.5}{n_i+0.5} $$
  因为查询中每个查询词都值出现了一次,所以其对应的都为1.其它数值假定如下:
  文档集合总数 N=100000
  文档集合中包含单词 A 的文档个数 $n_A = 1000$
  文档集合中包含单词 B 的文档个数 $n_B = 100$
  文档 D 中出现单词 A 的词频 $f_A = 8$
  文档 D 中出现单词 B 的词频 $f_B = 5$
  调节因子 $k_1 = 1.2$
  调节因子 $k_2 = 200$
  调节因子 $b = 0.75$
  假定文档长度是平均文档长度的 1.5 倍,即 $K=1.2\times(0.25+0.75\times 1.5)=1.65$,将这些数值带入 BM25 计算公式,可以得到文档 D 和查询的相关性得分:
$$\begin{align}BM25(“A B”, D) & = \log{\frac{100000-1000+0.5}{1000+0.5}\times\frac{(1.2+1)\times 8}{1.65+8}\times\frac{(200+1)\times 1}{200+1}}+ \\\
& \quad \log{\frac{100000-100+0.5}{100+0.5}\times\frac{(1.2+1)\times 5}{1.65+5}\times\frac{(200+1)\times 1}{200+1}} \\\
& =8.59\end{align}$$
  对文档集合里的所有文档,都按照上述方法计算,将计算结果按照大小排序,就根据 BM25 公式得出了内容相关性排序。