LionKing数据科学专栏

购买普通会员高级会员可以解锁网站精华内容且享受VIP服务的优惠

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏

信息检索和网页搜索(information retrieval and web search)

搜索引擎原理

搜索引擎实现了检索信息的系统,包括网页搜索(如Google、bing、百度、Yandex、Naver),文本搜索(如Mac系统的Spotlight搜索),产品搜索(如Amazon、淘宝)。

一般的搜索引擎由两个部分组成:选择(selection)和排序(ranking)。当用户进行一次查询(query)时,搜索引擎首先在所有文档(document)中选择可能符合用户信息需求的候选文档;接下来搜索引擎会对每一个候选文档,计算和用户查询的匹配度分数(score),关于该分数对结果进行排序。

本文以网页搜索为例介绍网页搜索引擎的主要组成部分:文档获取、索引系统、数据压缩、拼写建议、排序算法、评估。

文档获取

网页搜索中的文档,即互联网中的网页(webpage)。获取互联网中网页的核心技术为网络爬虫(web crawler)。

简单地来说,网络爬虫从一些已知的网页(seeds)出发,访问每个网页的超链接(hyperlinks),并以此循环往复,可以看作对于互联网进行图的广度优先搜索(Breadth-First-Search, BFS)。

对于实际的网络爬虫,需要进行去重(deduplicate),考虑礼貌性(politeness)即不能太频繁地爬取一个网站(site)或爬取该网站在robot.txt中禁止爬取的集合,考虑并行化(parallelization)的效率,考虑多少时间更新该网站的内容等。

原始的网页文件为html格式,并不方面进行后续的索引,因此需要进行格式的标准化使文档成为纯文本(plain text)。

索引系统

索引系统(indexing system)是搜索引擎不可或缺的一部分,可以显著增加搜索效率。事实上,如果不使用索引系统,那么当面对用户的查询(query)时,只能依次访问所有文档,并进行类似字符串匹配的KMP算法寻找所有相关文档,若文档规模巨大,不可能在短时间内完成搜索。

最经典的索引系统由倒排索引(inverted index)这一数据结构及其变体实现。

下文介绍如何对一个文档进行倒排索引,并实现最简单的布尔检索(Boolean retrieval)。

首先假设每个文档有一个编号(doc-id)并且从0开始顺序排列。其次假设每个文档已经被一个语法分析器(parser)划分成了一个个单词(word)。用户的查询(query)可以看作是一系列单词$w_1, \ldots, w_k$。布尔检索的目标是查询所有同时包含$w_1, \ldots, w_k$的文档的编号。

可以将该目标拆解为对于每一个单词$w$,查询所有包含$w$的文档的编号,然后只需要对这$k$个编号向量取交集(intersection)即可。

倒排索引为一个哈希表(hash table)的结构,记录了从$w$到所有包含$w$的文档的编号的键值对(key-value pairs)。实现方式为:依次访问每一个文档,对于该文档中出现的每一个单词,将文档编号插入该单词在哈希表中的值。

例如我们有如下几个文档:

0: i work for a software company

1: i went to work at nine

2: where is the restaurant

3: the restaurant is close to our company

4: where do you live

5: i live in san francisco

6: i work for a company in san bruno

倒排索引记录了每个单词出现的文档编号,例如'work'对应[0, 1, 6],'company'对应[0, 3, 6],'live'对应[4, 5]。

如果用户搜索'work company',那么返回[0, 1, 6]和[0, 3, 6]的交集[0, 6];如果用户搜索'where',那么返回[2, 4];如果用户搜索'i', 'work', 'for',那么返回[0, 1, 5, 6]和[0, 1, 6]和[0, 6]的交集[0, 6]。

$k$个编号向量都是从小到大排序的,对它们取交集可以使用分治(divide-and-conquer)法每次对两个集合取交集,或使用一个最小堆(minimum heap)管理每个向量上当前所在的编号,时间复杂度不会超过所有总单词的个数和$k$的对数的乘积。

一个常见的优化是优先对于较短的向量进行取交集。

不难通过在倒排索引中加入单词出现在文档中的位置,用以实现限定用户查询的单词在文档中出现未知的距离不超过$K$的搜索。这样的搜索在实际中非常常用。

具体的实现可以参考如下Python代码。

需要购买普通会员高级会员登录后刷新该页面查看

数据压缩

对于索引系统建立的倒排索引(inverted index),其键值有一些不必要的冗余信息,因此可以通过数据压缩的算法来减少其占用空间。最基本的数据压缩算法是使用$\gamma$编码记录相邻文档编号的差值(gap)。

如果数据范围较大,例如最大的文档编号需要占用8个字节(byte),那么传统的数据编码方法在存储一个文档编号的向量时,首先存储向量的元素个数$n$,然后使用$8n$个字节,其中每连续8个用以记录一个文档编号。

然而这8个字节中的大部分信息是无效信息,我们可以优化文档编号编码的平均长度。

$\gamma$编码的思路是首先将需要编码的数字转换为二进制,然后将二进制编码的长度使用游程编码(run-length encoding),将两者合并,且可以省去二进制编码首位的1。

117的二进制编码为1110101,长度为7,而7的游程编码为11111110,因此117的$\gamma$编码为11111110110101。

数据压缩算法还有一些类似$\gamma$编码的变体,如$\delta$编码、Golomb编码,还可以和哈夫曼编码(Huffman encoding)相结合。不同的数据压缩算法分别适合不同的数据分布情况,因此往往需要对实际数据进行不同压缩算法的实验来选择最合适的压缩算法。另外,越复杂的压缩算法往往能得到越节省空间的结果,但是解码的时候需要的时间也会更长。由于解码是在用户查询(query)之后进行的步骤,因此解码时间不能过于长,和压缩效果有一个相互权衡(tradeoff)。

拼写建议

搜索引擎在检测到用户的查询可能有错别词时,会进行拼写建议(spelling correction)。如果搜索引擎对该建议非常有信心,会直接改写这一查询,并且直接返回改写的查询结果,如下图:

如果搜索引擎相信用户的拼写可能有错但是不够确定,会仍然显示原始的查询结果,但是给用户提供一个链接指向改写后的查询结果,如下图:

我们介绍对单个单词进行拼写建议的算法。

假设有可能拼写错误的单词$w$,我们希望能够给出一个拼写建议$c$。

首先假设有一个字典$D$包含了所有可能的正确单词,例如牛津英语词典。对于一个拼写建议的算法,我们需要以下组成部分:

  1. 候选集生成(candidate generation):选出字典的子集$C$作为候选的拼写建议。
  2. 语言模型(language model):对于字典中的单词$c$本身出现概率$\Pr[c]$建模。
  3. 错误模型(error model):对于将字典中的单词$c$误打成$w$的概率$\Pr[w|c]$建模。

根据贝叶斯定理(Bayes' theorem)

$$\Pr[c|w] = \frac{\Pr[c]\Pr[w|c]}{\Pr[w]}$$

因此,我们希望选出$C$中的$c$以最大化$\Pr[c|w]$。等价地,我们选取$$\arg\max_{c \in C}\Pr[c]\Pr[w|c]$$

最基本的拼写建议算法选择如下模型:

  1. 候选集生成:选取字典中所有与$w$的编辑距离(edit distance; Levenshtein distance)不超过2的单词。
  2. 语言模型:在一个文集中$c$出现的次数与文集总单词数的比例作为$c$的概率。
  3. 错误模型:若$w$与$c$的编辑距离为0,则概率为1;若编辑距离为1,则概率为$p_1$;若编辑距离为2,则概率为$p_2$。

具体的实现可以参考如下Python代码。

需要购买普通会员高级会员登录后刷新该页面查看

排序算法

用户的查询为$q = w_1 w_2 \ldots w_s$,候选文档为$d_1, \ldots, d_K$。对于$q$和$d_k$可以计算一个打分$s_k = score(q, d_k)$,并且将候选文档关于分数排序,并依次返回给用户。

对于网页搜索,打分函数为文档的相关度(relevance)打分与网站的质量(quality)打分之和。

对于相关度打分,最基本的算法是使用tf-idf或其变体。

tf-idf的想法是对于用户查询中的每个单词(term)$w$进行一个和文档$d$的打分。最简单的打分方式是计算$w$在文档$d$中的出现次数。这一打分的缺点是没有考虑到单词$w$本身的频率,如"the"几乎在所有的文档中出现,因此"the"在文档中的出现次数应当没有其它更少见的单词出现次数重要,我们希望通过惩罚本身频率高的单词来体现这一区别。

对于网站的质量,最基本的算法是Google的核心算法PageRank。

PageRank的想法是,如果一个网站被高质量的网站所引用,则该网站倾向于具有更高的质量。考虑在整个互联网上的随机游走,那么充分多步后,到达高质量网站的概率会相对较高,而到达低质量网站的概率会相对较低,用随机游走到达一个网站的概率作为其网站质量打分。PageRank可以避免一个钓鱼网站依靠大量伪造的入链获得高质量得分。

业界中,在提取了大量特征,如相关度的tf-idf打分、BM25打分、网站的PageRank、查询的单词个数等,可以使用机器学习算法来学习打分函数,称为排序学习(learning to rank)。

排序学习算法的类别为:

评估

网页搜索的评估方式有两种:基于群众外包(crowdsourcing)的评估和基于用户反馈的评估。

群众外包的评估指的是公司利用外包平台,如Amazon Mechanical Turk,寻找一些评估者对搜索结果进行打分;用户反馈的评估指的是使用在线用户与页面的交互,如点击率(click-through rate)、第一个点击的位置等指标(metric),用以评估算法。

对于两种数据获取方式,均可使用随机分组实验将用户分为旧版算法和新版算法两组,对各类指标做A/B测试来确定新算法是否更优。

附加内容:tf-idf

介绍

tf-idf的全称为term frequency-inverse document frequency,是一种衡量一个单词(term)在一个文档(document)中的重要性的打分。

tf-idf定义在一个用户查询(query)$q = w_1, w_2, \ldots w_s$,一个文档$d$和一个文集$D = d_1, d_2, \ldots, d_N$上。

其中tf-idf定义在一个单词(term)上时为$$tfidf(w, d, D) = tf(w, d) \times idf(w, D)$$

tf-idf定义在整个用户查询(query)上时为$$tfidf(q, d, D) = \sum_{i=1}^{s} tfidf(w_i, d, D)$$即每个单词的tf-idf打分之和。

$tf(w, d)$为词频(term frequency),有不同的定义方式,一般为单词$w$在文档$d$中的出现次数$f_{w, d}$。

$idf(w, D)$为逆文本评率(inverse document frequency),刻画了单词$w$在整个文集中的稀有程度,有不同的定义方式,一般定义为单词在文集中出现的文档比例的负对数$$idf(w, D) = \log{\frac{N}{|\{d \in D: w \in d\}|}}$$

tf和idf的乘积联合表示了文档$d$和单词$w$的相关程度,考虑了单词本身出现次数和单词的稀有程度。不同的tf-idf总和衡量了用户查询$q$和文档$d$的相关程度,是很基本的排序指标。

例子

假设有如下文集$D$:

0: a cat is an animal and a monkey is also an animal

1: kitty is a cat and little monkey is a monkey

2: cat cat cat cat cat

3: leo is a lion but she looks like a cat

4: i like my cat leo

5: i also like my monkey

若需要计算用户查询q = "cat"和4号文档d = "i like my cat leo"的tf-idf打分,"cat"该文档$d$中出现1次,"cat"在$D$中总共出现了5次,有$$tf("cat", d) = 1, idf("cat", D) = \log_{10}{\frac{6}{5}}, tfidf(q, d, D) = tfidf("cat", d, D) = 1 \times \log_{10}{\frac{6}{5}} \approx 0.079$$

若需要计算用户查询q = "cat"和2号文档d = "cat cat cat cat cat"的tf-idf打分,有$$tf("cat", d) = 5, idf("cat", D) = \log_{10}{\frac{6}{5}}, tfidf(q, d, D) = tfidf("cat", d, D) = 5 \times log_{10}{\frac{6}{5}} \approx 0.396$$

若需要计算用户查询q = "lion"和3号文档d = "leo is a lion but she looks like a cat"的tf-idf打分,有$$tf("lion", d) = 1, idf("lion", D) = log_{10}{\frac{6}{1}}, tfidf(q, d, D) = tfidf("lion", d, D) = 1 \times \log_{10}{\frac{6}{1}} \approx 0.778$$

若需要计算用户查询q = "monkey cat"和1号文档d = "kitty is a cat and little monkey is a monkey"的tf-idf打分,有$$tf("monkey", d) = 2, idf("monkey", D) = log_{10}{\frac{6}{3}}, tf("cat", d) = 1, idf("cat", D) = log_{10}{\frac{6}{5}}$$

$$tfidf(q, d, D) = tfidf("monkey", d, D) + tfidf("cat", d, D) = 2 \times \log_{10}{\frac{6}{3}} + 1 \times \log_{10}{\frac{6}{5}} \approx 0.681$$

查询"leo",得到的tf-idf得分最高的文档是3号文档"leo is a lion but she looks like a cat";查询"cat",得到的tf-idf得分最高的文档是2号文档"cat cat cat cat cat";查询"monkey",得到的tf-idf得分最高的文档是1号文档"kitty is a cat and little monkey is a monkey";查询"monkey cat",得到的tf-idf得分最高的文档是1号文档"kitty is a cat and little monkey is a monkey"。

可以看到,在查询单个单词时(如"cat"),由于每一个文档都乘以了该单词的idf,得分最高的文档是该单词出现次数最多的文档;然而在查询多个单词时(如"monkey cat"),由于不同的单词被其各自的idf加权,高频词没有低频词重要,tf-idf能够总和每个单词在文章内的出现次数得到结果。

具体的实现可以参考如下Python代码。

需要购买普通会员高级会员登录后刷新该页面查看

附加内容:PageRank算法

介绍

如果只是使用了tf-idf等相关性打分作为排序的唯一指标,那么钓鱼网站很容易通过无意义地重复关键词来提高其搜索引擎排名,因此,还需要通过其它信息对网页质量进行打分。

一般来说网页的质量由网站本身决定,因此往往在网站级别进行质量打分。网站质量可以通过查看网站本身的内容,如代码混乱程度、是否包含低俗词语等,还可通过网站之间的链接进行分析。PageRank是最具代表性的通过网站之间的链接进行质量打分的算法,是Google早年获得成功的重要原因之一。

我们将互联网看作各个网站(site)之间的一个有向图(directed graph),其结点为各个网站,从A到B的链接表示网站A含有指向网站B的超链接(hyperlink)。

我们认为一个网站指向另一个网站的链接代表了前者对后者质量的认可,一个好的网站指向的网站质量偏高,一个不好的网站指向的网站质量可高可低,我们希望通过一个算法来实现这个思想。

下图来自wikipedia,每个结点上的数字为其对应的PageRank乘以100。

其中中等质量网站E被较多低质量网站所指,而高质量网站B被中等质量的网站和低质量网站共同指向,高质量网站C只有高质量网站B指向。可以看到,尽管E的入链远多于C,但是C获得了来自高质量网站B的链接(认可),因此PageRank得分高于E。

为了实现这一算法,我们假想有一个用户(surfer)从随机的一个网站出发,每次以$1 - d$的概率随机地在整个互联网的$N$个网站中选取一个网站浏览,以$d$的概率在该网站的超链接指向的网站中随机地选取一个浏览(若没有超链接指向外站,则留在当前网站)。其中,$d$为超参数,称为阻尼系数(damping factor),其概率意义为用户浏览超链接的概率,一般取0.85。在充分多次这样的转移之后,用户所在的网站具有随机性,但是在每一个网站的概率会接近平稳分布(stationary distribution)下的概率值,我们以这一概率作为该页面的PageRank打分。

算法

为了计算网站的平稳概率,我们需要之前描述的随机过程的状态转移矩阵(state transition matrix)$M$。

对于任何一个初始分布$\pi$,一次转移后的分布为$M\pi$,$k$次转移后的分布为$M^k\pi$,只要$k$充分大,$M^k\pi$会非常接近平稳分布$\widetilde{\pi}$,即PageRank向量。

从网站$i$转移到网站$j$的概率,如果存在从$i$到$j$的超链接,为$$\frac{1 - d}{N} + \frac{d}{d_i^{\text{out}}}$$如果不存在从$i$到$j$的超链接,为$$\frac{1 - d}{N}$$其中$d_i^{\text{out}}$为网站$i$指向的不同网站的个数,即结点$i$的出度(out-degree)。

注意$M$中的大多数元素均为$\frac{1 - d}{N}$,因此可以将其看作一个稀疏矩阵,只需考虑矩阵中的链接而不是所有元素,从而减少$M$与$\pi$乘积的运算量。业界使用这一特点,使用MapReduce并行框架进行PageRank计算。

$\pi$的更新方程为:

$$\pi'(j) = \frac{1 - d}{N} + \sum_{i \rightarrow j}\frac{d}{d_i^{\text{out}}}\pi(i)$$

PageRank算法如下:

具体的实现可以参考如下Python代码。

需要购买普通会员高级会员登录后刷新该页面查看

可以发现,在50次迭代后,算法接近收敛,得到了图中标示的PageRank值。

更多面试问题见面试真题汇总

想要查看更多数据科学相关的内容请关注我们的微信公众号知乎专栏