2020年03月16日 DF-IDF

信息检索概述

信息检索是当前应用十分广泛的一种技术，论文检索、搜索引擎都属于信息检索的范畴。通常，人们把信息检索问题抽象为：在文档集合D上，对于由关键词w[1] ... w[k]组成的查询串q，返回一个按查询q和文档d匹配度relevance(q, d)排序的相关文档列表D'。

对于这一问题，先后出现了布尔模型、向量模型等各种经典的信息检索模型，它们从不同的角度提出了自己的一套解决方案。布尔模型以集合的布尔运算为基础，查询效率高，但模型过于简单，无法有效地对不同文档进行排序，查询效果不佳。向量模型把文档和查询串都视为词所构成的多维向量，而文档与查询的相关性即对应于向量间的夹角。不过，由于通常词的数量巨大，向量维度非常高，而大量的维度都是0，计算向量夹角的效果并不好。另外，庞大的计算量也使得向量模型几乎不具有在互联网搜索引擎这样海量数据集上实施的可行性。

tf-idf模型

目前，真正在搜索引擎等实际应用中广泛使用的是tf-idf模型。tf-idf模型的主要思想是：如果词w在一篇文档d中出现的频率高，并且在其他文档中很少出现，则认为词w具有很好的区分能力，适合用来把文章d和其他文章区分开来。该模型主要包含了两个因素：

1. 词w在文档d中的词频tf (Term Frequency)，即词w在文档d中出现次数count(w, d)和文档d中总词数size(d)的比值：

tf(w,d) = count(w, d) / size(d)

2. 词w在整个文档集合中的逆向文档频率idf (Inverse Document Frequency)，即文档总数n与词w所出现文件数docs(w, D)比值的对数:

idf = log(n / docs(w, D))

tf-idf模型根据tf和idf为每一个文档d和由关键词w[1]...w[k]组成的查询串q计算一个权值，用于表示查询串q与文档d的匹配度：

tf-idf(q, d)
= sum { i = 1..k | tf-idf(w[i], d) }
= sum { i = 1..k | tf(w[i], d) * idf(w[i]) }

信息检索问题的概率视角

直观上看，tf描述的是文档中词出现的频率；而idf是和词出现文档数相关的权重。我们比较容易定性地理解tf-idf的基本思想，但具体到tf-idf的一些细节却并不是那么容易说清楚为什么。比如：

1. 为什么tf是count(w, d) / size(d)？能不能是log(count(w, d) / size(d))等其他形式？

2. 为什么idf是一个log形式？

3. 为什么tf和idf之间是乘积关系，而不是加法或指数关系？

4. 为什么多个关键词的tf-idf值是加法关系，而不是乘法或者指数关系？

5. 除了tf-idf值，Google还会计算网页的PageRank值，二者相乘得到最后的权值，为什么是乘法，而不是加法或指数？

据说，最初甚至tf-idf的提出者自己也没有对诸如“为什么idf是log形式”这个问题给出有力的解释，虽然后来有人从信息论的角度对idf的log形式给出了令人信服的解释，但是剩下的其他一些疑问仍然存在。在我了解的范围内，对于tf-idf模型还没有一个真正统一完整的理论解释。在试图为tf-idf找到更好的理论解释的过程中，我意识到对tf-idf模型种种疑问的根源在于tf-idf试图表达的“查询q和文档的匹配度”本身就有一定的模糊性，什么叫做“匹配度”，这就有很大的自由发挥空间。如果说向量模型的用向量夹角来表示匹配度概念还有一定的理论基础，那么用tf-idf来表达匹配度就有点“与其说是科学，不如说是艺术”的味道。

更进一步，其实，信息检索问题的抽象方式“在文档集合D上，对于给定查询串q，返回一个按查询q和文档d匹配度relevance(q, d)排序的相关文档列表D'”本身是值得反思的。我们应当考虑抛弃“匹配度”这种模糊的目标，从根源上寻求一种具有明确数学意义的目标。如果我们从概率视角来看，把“查询串q和文档d的匹配度”问题转换为“当查询串是q时，用户期望获得文档d的概率”问题，信息检索问题就清晰多了。一方面这个概率描述是站在人的角度来看待信息检索问题的，更加贴近实际的用户体验；另一方面，概率本身是有明确数学意义的，这样我们就首先从目标上对问题进行了严格化。

下面，我将通过一个模型，从概率的视角，一边解释tf-idf的概率意义，一边指出其不合理之处。

盒子小球模型
为了分析“当查询串是q时，用户期望获得文档d的概率”问题，我首先建立了一种称为“盒子小球模型”的简化模型。盒子小球模型把词想象成各种不同颜色的小球，文档想象成装有若干小球的盒子，把“当查询串是q时，用户期望获得文档d的概率“转换为下面的问题：

有n个盒子d[1], d[2], ... d[n]，每个盒子中有若干不同颜色的小球，有人随机地选择了一个盒子，并从盒子中随机地拿出了一个颜色为w[j]的小球，那么这个小球来自于盒子d[i]的概率是多少？

其实，这就是经典的条件概率问题P(d[i] | w[j])，采用贝叶斯推断将其转化为：

P(d[i] | w[j])
= P(d[i], w[j]) / P(w[j])
= P(d[i]) * P(w[j] | d[i]) / P(w[j])

我们注意到这个条件概率包括几个部分，P(d[i])是盒子d[i]被选中的先验概率，p(w[j])是w[j]颜色小球被选中的先验概率，P(w[j] | d[i])是在盒子d[i]中选中颜色w[j]小球的条件概率。

文档先验概率P(d)与PageRank

首先，我们来看盒子d[i]被选中的先验概率P(d[i])是什么。P(d[i])的意义是：当用户什么也没有输入的时候，它可能对文档d[i]感兴趣的概率。在没有更多信息的情况下，我们可以认为每个盒子被选中的先验概率P(d[i])是相等的，都等于1 / m，其中m表示总文档数（总盒子数），这时P(d[i])作为公共系数可被忽略。不过，在实际应用中，我们通常可以根据其他知识获得各文档的先验概率，比如，学术文献和网页通常可以基于引用度模型计算其先验概率，这些经典论文和热门网页是多数人乐于见到的。说到这里，你可能已经发现，Google PageRank本质上就是这个先验概率P(d[i])乘以某个系数！所以，PageRank实际上也被纳入这个条件概率模型中来了，这就不难解释为什么在Google的排序算法中PageRank权重和tf-idf权重是一种乘积关系而不是加或者指数关系。另一方面，在理解了文档先验概率对整个搜索结果概率的影响后，当搜索引擎中针对PageRank出现各种假链接SEO时，我们可以不拘泥于基于链接引用模型的PageRank，只要是以网页先验概率为目标，不论是采用基于链接引用的PageRank，还是基于搜索结果点击数模型，或是其他模型，都是可以的。这就是“变通”，从原理上“通”了，就可以在方法上“变”。

词的先验概率P(w)

下面我们来考察词w[j]的先验概率P(w[j])。P(w[j])的意义是：在整个文档集合中，w[j]被作为搜索关键词的概率，比如：“iPhone 5”，“青花瓷”这类词被用作搜索关键词的概率较高，而“的”，“什么”，“我们”这类高频词不大可能成为搜索关键词。那么，我们如何来定量计算P(w[j])呢？一种思路就是把w[j]在文档集中出现的频率作为其先验概率。不过，显然存在更好的方案：在大量的搜索查询中进行统计，统计方法得出P(w[j])的方法很接近P(w[j])本质的，不需要引入额外的假设。比如，一段时间内某搜索引擎的搜索总次数为10^10次，“公积金”这个词出现了100次，那么，我们可以认为先验概率P("公积金")就是100 / 10^10 = 10^-8。

词代表文档主题的条件概率P(w | d)

最后，我们来看条件概率P(w[j] | d[i])。P(w[j] | d[i])的意义是在文档d[i]中，人们用关键词w[j]来搜索它的概率。那么，什么样的词是人们会用来搜索一篇文档的呢？多数情况下，是那些代表一篇文档主题的词。比如，有一篇新闻是关于iPhone 5发布会的，那么“iPhone5”， “发布会”，“库克”，“苹果”这些词基本上就构成了文章的主题；那么，反过来说，如果用户想搜索这篇关于iPhone 5发布会的新闻，他就有很大的可能通过这几个词来进行搜索。我们应当注意分辨P(w[j] | d[i])与P(w[j])的区别，后者可以通过大量的查询统计得来，而前者不能与后者直接划等号，因为前者的意义是w[j]代表d[i]主题的概率。如果非要引入统计方法，那么P(w[j] | d[i])对应的统计是：当搜索关键词是w[j]且搜索结果包含d[i]时，用户点击（满意）d[i]作为搜索结果的频率。比如，用“iPhone5 发布会”的搜索，在结果中有都10000次出现了网页x，其中，用户8000次点击了网页x，那么，可以认为有80%的概率网页x的主题是关于“iPhone5 发布会”的。

词的信息量和idf

上面谈到了对P(w[j] | d[i])的计算的统计方法，但该方法有一定的局限，比如，要能进行统计首先需要文档出现在足够多的搜索结果中，需要时间和量的积累。除了统计方法外，我们可以考虑其他方法计算词w[j]代表文档d[i]主题的概率。可能有人立刻会想到要对文章进行语义分析提取关键词，给这些关键词高权重，给其他词低权重。这种想法有一定的合理性，但实现上涉及语义分析，没有成熟高效的方法。实际上，信息论为我们提供了另一条高效方案。上面谈到“的”，“什么”，“我们”这类高频词不会成为文档主题和搜索关键词的原因是它们不能提供足够的信息，而“iPhone 5”，“发布会”这样的词汇则信息量丰富。所谓信息是指对不确定性（熵）的减小程度，信息的单位是比特(bit)，信息量越大对于不确定性的减小程度越大。比如，外面可能在下雨也可能没有下雨，可能性空间大小为2，如果我们看一眼窗外，可能性空间就变成了1，那么“看见窗外在下雨”所提供的信息量就和熵的减小程度成正比，具体来讲等于log(2/1)=1。如果要用二进制编码是否下雨，需要1个bit，0代表没有下雨，1代表下雨。

但在很多场景下，各个可能性的概率并不相同，比如：欧洲杯16只球队都可能夺冠，赛前它们夺冠的先验概率并不相同，那么结果的不确定性程度实际上是小于log(16)=4。如果你没有看比赛，有人告诉你西班牙夺冠了，你可能会觉得很正常，但如果有人告诉你瑞士夺冠了，你通常会非常惊讶。这一现象的理论解释是，如果赛前西班牙夺冠概率是1/4，而瑞士夺冠概率是1/32，那么，“西班牙夺冠”的信息量为log(4)=2，即把不确定性减小为原来的1/4，而“瑞士夺冠”的信息量为log(32)=5，不确定性减小为原来的1/32，一下子接受比前者大了两倍以上的信息量，当然你会吃惊。

回到信息检索，比如，“2012美国大选”这个查询串包含了“2012”，“美国”和“大选”3个关键词，我们应该如何定量计算它们的信息量呢？根据信息的定义，词的信息量等于它对不确定性的缩小程度。如果文档总数为2^30，其中214篇文档出现了“美国”，那么“美国”这个词就把文档的不确定性从2^30缩小为214，它所包含的信息量为log(2^30/214)=16；而只有2^{10篇文档出现了“大选”，那么大选的信息量就是log(2}30/2^10)=20，比“美国”多了4个bit。而“的”，“什么”，“我们”这些高频词对减小文档不确定性几乎没有帮助，因而信息量为0。相信你已经发现，上面idf(w)公式中的log(n / docs(w, D))实际上就是词w的信息量了。

如果我们考虑词的信息量对条件概率P(w[j] | d[i])的影响，假设“词w在文档中被选中的概率与其在文档中的出现频率和其信息量的乘积成正比”，那么上面的条件概率模型就变成：

P(d[i] | w[j])
= P(d[i], w[j]) / P(w[j])
= P(d[i]) * P(w[j] | d[i]) / P(w[j])
= P(d[i]) * (tf(w[j], d[i]) * idf(w[j] / sum { k = 1..size(d[i]), tf(w[k], d[i]) * idf(w[k]) }) / p(w[j])
= P(d[i]) * (tf-idf(w[j], d[i]) / sum { k = 1..size(d[i]), tf-idf(w[k], d[i]) }) / p(w[j])
= P(d[i]) * (tf-idf(w[j], d[i]) / tf-idf(d[i])) / p(w[j])

我们看到tf-idf已经被纳入框架内了，但是还多出文档先验概率P(d[i])，关键词先验概率P(w[j])和文档各词的总tf-idf(d[i])。普通搜索引擎是基于PageRank和tf-idf的，那么，根据这个概率模型，我们可以看出，它没有考虑文档总tf-idf(d[i])和关键词先验概率p(w[j])。如果考虑这两个因素，相信搜索效果会更好。

多关键词
上面的条件概率模型主要是针对单个关键词的情况，下面我们进一步将其扩展到多关键词情况。我们知道，在tf-idf中，多个关键词的所产生的tf-idf值是一种叠加关系，那么这是否符合条件概率模型呢？答案是否定的。在两个关键字情况下，条件概率问题转化为“如果有人从一个盒子中同时摸出颜色w[x]的小球和颜色w[y]的小球，这两个小球来自于盒子d[i]的概率是多少？”。假设从盒子中摸出各个小球事件是相互独立的情况下，即

P(w[x], w[y]) = P(w[x]) * P(w[y])
P(w[x], w[y] | d[i]) = P(w[x] | d[i]) * P(w[y] | d[i])

我们可以推导出条件概率：

P(d[i] | w[x], w[y])
= P(d[i], w[x], w[y]) / P(w[x], w[y])
= P(d[i]) * P(w[x], w[y] | d[i]) / P(w[x], w[y])
= P(d[i]) * P(w[x] | d[i]) * P(w[y] | d[i]) / (P(w[x] * P(w[y]))
= P(d[i]) * (tf-idf(w[x], d[i]) / tf-idf(d[i])) * ((tf-idf(w[y], d[i]) / tf-idf(d[i]))) / (p(w[x]) * P(w[y]))

可见，概率模型所得出的各个关键词的tf-idf值之间是乘积关系，这是与tf-idf模型的加法关系是不同的。这一点可能与二者是否要求“文档必须包含所有查询关键词”的基本假设有关系。在文档不包含所有关键字的这种情况下，tf-idf模型可能得出一个非0的匹配度，但条件概率模型得出的概率肯定为0。不过，如果考虑一般查询关键词数量不多（3个以内），而大量文档都同时包含这些关键词，概率模型的乘积关系是比tf-idf模型的加法关系更有理论基础。从根本上讲，这是因为tf-idf的“匹配度”是一个模棱两可的概念，而条件概率有坚实的理论基础。

总结
TF-IDF模型是搜索引擎中广泛使用的信息检索模型，但对于TF-IDF模型一直存在各种疑问。本文为信息检索问题一种基于条件概率的盒子小球模型，其核心思想是把“查询串q和文档d的匹配度问题”转化为“查询串q来自于文档d的条件概率问题”。它从概率的视角为信息检索问题定义了比TF-IDF模型所表达的匹配度更为清晰的目标。从概率模型中，我们看到查询串q来自于文档d的条件概率主要包含以下几个因素：1) 文档的先验概率P(d[i])，这与PageRank对应；2) 词w被作为搜索关键词的先验概率P(w)，这可以通过统计方法获得；3) 关键词w代表文档d主题，或以词w搜索文档d的概率，P(w | d)，除了统计方法，这可以通过tf-idf来计算。