On the shoulders of giants.

搜索引擎中的数学原理

读文须知

本博文是概述吴军一书《数学之美》中第八章至第十一章的内容,涉及科班所学内容不进行解释。
因为本书面向大众,所以对于本书内容,作者只讲述简单的原理。

前置知识

搜索引擎的原理其实非常简单,建立一个搜索系统大致需要做这样几件事情:

  • 自动下载尽可能多的网页。
  • 建立快速有效的索引。
  • 根据相关性对网页进行公平准确的排序。

简单概括就是:下载、索引、排序。

索引

好比去图书馆借书,当你要找一本书时,你不可能从头到尾去找,而是根据搜索卡片去找到它的位置,索引也是这样存在的。

最简单的索引结构是用很长的二进制表示一个关键词是否出现在每篇文献中。

显然,有多少篇文章,二进制数就有多长。当有多个关键词时,可以用布尔代数系统处理,例如:

搜索 “原子能” 的结果为: 000101110100010......

搜索 “应用” 的结果为: 011001110010100......

搜索 “原子能应用” 的结果因该为二者的并: 000001110000000......

计算机做布尔运算是非常快的,当然这些二进制数中绝大多位数上都是零,我们只需记下等于一的位数即可。

于是,搜索引擎的索引就变成了一张大表:表的每一行对应一个关键词,每个关键词后面跟着一组数字,是包括该关键词的文献编号。

如果考虑到各种因素,整个索引将会变得非常大,并不是一台服务器能够存下的,所以得用分布式的方法存储到不同的服务器中。

下载

本章需要一些图论及其遍历算法的基础(这里不多做介绍)。

对于互联网,可以把每一个网页当作一个节点,把超链接(Hyperlinks)当作连接网页的弧,然后就构成了一张很大的图。

我们可以从任何一个网页出发,用图的遍历算法,自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫(Web Crawlers)

如何利用网络爬虫下载整个互联网?

假设从一家门户网站的首页出发(例如腾讯),可以找到页面里所有的超链接,就知道了这家门户网站直接链接的所有网页(例如:腾讯邮件、腾讯新闻等)。

接下来分析其网页又可以得知其他门户网站。让计算机不停的做下去,就能下载整个互联网。当然要使用工具记录某个网页是否被下载过(例如:哈系表(Hash Table))。

对于数据的庞大,如何建起这样复杂的网络系统,如何协调这些服务器的任务,这就是网络设计和程序设计的艺术了。

网络爬虫在工程实现上要考虑的细节非常多,其中大的方面有这样几点:

  • 使用 BFS 还是 DFS
  • 页面的分析和 URL 的提取。
  • 记录哪些网页已经下载过的工具。

排序

搜索结果的排名取决于两组信息:

  • 关于网页的质量信息(Quality
  • 这个查询与每个网页的相关性信息(Relevance

度量网页的质量

使用 PageRank 算法,Google 的 “PageRank” 简单来说就是民主表决。

在互联网上,如果一个网页被很多其它网页所链接,说明它是收到普遍承认和信赖的,那么它的排名就高。

这就是 PageRank 的核心思想,当然 Google 的 PageRank 算法实际上要复杂得多。

对于那些排名高的网页的链接更可靠,于是要给那些网页加大权重。

可这样以来,就陷入了悖论怪圈(没有权重何来排名,没有排名何来权重)。

有人破解了这个怪圈。把问题变成一个二维矩阵相乘的问题,并用迭代的方式解决了这个问题。

先假设所有网页的排名是相同的,并根据这个初始值,算出各个网页的第一次迭代排名。

然后再根据第一次迭代排名算出第二次的排名,他们从理论上证明了不论初始值如何选取,这种算法都能保证网页排名的估计值能收敛排名的真实值。

PageRank 的计算方法

假设向量:

\(B=(b_1,b_2,\cdots,b_N)^T\)

为第一、第二、……第 N 个网页的网页排名。矩阵

\(A=\begin{bmatrix}a_{11} & \cdots & a_{1N}\\ \vdots & \ddots & \vdots \\ a_{N1} & \cdots & a_{NN} \\ \end{bmatrix}\)

为网页之间链接的数目,其中 \(a_{uv}\) 代表第 u 个网页指向第 v 个网页的链接数。矩阵 A 是已知的,向量 B 是我们所要计算的。

假定 \(B_i\) 是第 i 次迭代的结果,那么:

\(B_i=A*B_{i-1}\)

初始假设:所有网页的排名都是 \(\frac{1}{N}\) ,即:

\(B_0=(\frac{1}{N},\frac{1}{N},\cdots,\frac{1}{N})^T\)

通过简单的(但是计算量非常大)的矩阵运算,可以得到 \(B_1,B_2,\cdots\) 。可以证明 \(B_i\) 最终会收敛。

当 \(B=A\times B\) 时,停止迭代,算法结束。一般来讲,只要 10 次左右的迭代基本上就收敛了。

因为网页之间链接相对互联网规模非常稀疏,因此计算网页排名也需要对小概率时间进行平滑处理。

网页排名是一个一维向量,对它的平滑处理只能利用一个小的常数 \(\alpha\) ,于是公式变成:

\(B_i=[\frac{\alpha}{N}\cdot E+(1-\alpha)A]\cdot B_{i-1}\)

网页和查询的相关性

以前,技术和算法的重要性高于数据,因此确定网页和查询的相关性主要依靠算法。

但是今天,由于搜索引擎已经有了大量的用户点击数据,相关性贡献最大的是根据用户对网页点击结果的概率模型。

影响搜索引擎质量的诸多因素,除了用户的点击数据之外,都可以归纳成下面四大类:

  • 完备的索引。如果一个网页不再索引中,那么再好的算法也找不到。
  • 对网页质量的度量,比如 PageRank 。
  • 用户偏好。因为不同用户喜好不同,所以对搜索相同的结果要给出不同的排名。
  • 确定一个网页和某个查询的相关性的方法(这也是接下来要说的)。

如何度量网页和查询的相关性?

搜索关键词权重的科学度量 TF-IDF

一些关键词出现较多的网页应该比它们出现较少的网页相关性要高。

这样显然有些漏洞,那就是篇幅长的网页比篇幅短的网页占便宜,因为一般来说长网页包含的关键词要多些。

因此根据网页的总字数,对关键词的次数进行归一化,也就是用关键词的次数除以网页的总字数。

我们把这个商称为 “关键词的频率” ,或者 “单文本词频”(Term Frequency,TF)

比如,一个网页一共有 1000 个词,其中 “原子能” 、“的”、“应用” 分别出现了 2 次、 35 次和 5 次,

那么它们的词频就分别是 0.002 、0.035、0.005 ,这三个数相加就是相应网页和查询 “原子能的应用” 的 “单文本词频” 。

因此,度量网页和查询的相关性,有一个简单的办法,就是直接使用每个关键词在网页中出现的总词频。

具体地讲,如果一个查询包含 N 个关键词 \(w_1,w_2,\cdots,w_N\) ,它们在一个特定网页中词频分别是 \(TF_1,TF_2,\cdots,TF_N\) 。

那么这个查询和该网页的相关性就是: \(TF_1+TF_2+\cdots+TF_N\) 。

这时,又有几个显然的漏洞。

在上面的例子中,“的” 这个词占了词频的 80% 上,而它对确定主题几乎没什么用处,我们称这种词为 停止词(Stop Word)

对于 “应用” 这个词是个很通用的词,而 “原子能” 是个很专业的词。

因此,需要对汉语中的每一个词给一个权重,这个权重的设定必须满足:

  • 一个词预测主题的能力强,权重越大,反之,权重越小。
  • 停止词的权重为零。

容易发现,如果一个关键词只在很少的网页中出现,通过它就容易锁定搜索目标,它的权重也就应该大。

反之,如果一个词在大量的网页中出现,看到它依然不很清楚要找什么内容,它的权重就应该小。

简要概括,假定一个关键词 \(w\) 在 \(D_w\) 个网页出现过,那么 \(D_w\) 越大,\(w\) 的权重就越小,反之亦然。

在信息检索中,使用最多的权重是 “逆文本频率指数”(Inverse Document Frequency,IDF)

它的公式为:\(\log (\frac{D}{D_w})\) ,其中 D 是全部网页数。

利用 IDF ,上述相关性计算的公式就变成由词频的加权求和:

\(TF_1\cdot IDF_1+TF_2\cdot IDF_2+\cdots+TF_N\cdot IDF_N\)

TF-IDF 的信息论依据

一个查询中每个关键词 \(w\) 的权重应该反映这个词对查询来讲提供了多少信息。

一个简单的办法就是用每个词的信息量作为它的权重,即:

\(I(w)=-P(w)\log P(w)=-\frac{TF(w)}{N}\log \frac{TF(w)}{N}=\frac{TF(w)}{N}\log \frac{N}{TF(w)}\)

其中,N 是整个语料库的大小,是个可以忽略的常数,所以可以简化为:

\(I(w)=TF(w)\log \frac{N}{TF(w)}\)

不过还是会有一些缺陷,更好的权重公式应该反映出关键词的分辨率。

如果做一些理想的假设:

1)每个文献大小基本相同,均为 M 个词,即 \(M=\frac{N}{D}=\frac{\sum_w TF(w)}{D}\) 。

2)一个关键词在文献中一旦出现,不论次数多少,贡献都等同,这样一个词在一个文献中要么 \(c(w)=\frac{TF(w)}{D(w)}\) ,要么是零,注意 \(c(w)<M\) 。

那么从公式出发可以得到下面的公式:

\(TF(w)\log \frac{N}{TF(w)}=TF(w)\log \frac{MD}{c(w)D(w)}=TF(w)\log (\frac{D}{D(w)} \frac{M}{c(w)})\)

这样,我们综合以上内容得出 TF-IDF 公式:

\(TF-IDF(w)=I(w)-TF(w)\log \frac{M}{c(w)}\)

Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注