TF-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)和w在文档集合D中出现总次数count(w, D)的比值：

tf(w,d)
= count(w, d) / count(w, D)
= count(w, d) / sum { i = 1..n | count(w, d[i]) }

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) / count(w, D)？能不能是count(w, d[i]) / max { j = 1..n, i != j | count(w, d[j])}等其他形式？ 2) 为什么idf是一个log形式，而tf又不是log？ 3) 为什么tf和idf之间是乘积关系，而不是加法或指数关系？ 4) 为什么多个关键词的tf-idf值是加法关系，而不是乘法或者指数关系？ 5) Google除了计算网页的tf-idf值，还会计算网页的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]小球的条件概率。

在没有更多信息的情况下，我们可以用w[j]出现的频度代表P(w[j])，即P(w[j])等于w[j]颜色小球数占总小球数的比例；而P(w[j] | d[i])等于w[j]颜色小球在盒子d[i]中所占的比例，即：

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]) * (count(w[j], d[i]) / size(d[i])) / (count(w[j]) / size(D))
= P(d[i]) * (count(w[j], d[i]) / count(w[i])) / (size(d[i]) / size(D))
= P(d[i]) * tf(w[j], d[i]) * size(D) / size(d[i])

其中，size(d[i])是d[i]中的小球总数，size(D)是总小球数（一个公共的常数）。可见，tf模型可以被纳入这个概率模型，这从一定程度解释了tf模型的合理性。但是，它比tf还多出了P(d[i])和size(d[i])。

首先，我们来看盒子d[i]被选中的先验概率P(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(d[i])之外，文档d[i]中的词数size(d[i])也是一个变化因素，而这个变化因素实际上是被tf所忽略的，或者我们可以认为tf模型是假设各个文档的词数都近似相等，这样它和概率模型就统一起来了。这样，从严格的概率角度，我们既解释了tf的合理性，又看到了其不足之处。

词的信息量

上面，我们在计算P(w[j] | d[i])的过程中是把小球视为除了颜色可区分外，没有选中概率的差别，即某一颜色的小球被选中的概率只与其数量有关。这在信息检索中并不成立，直观上看人们不会对“的”，“什么”，“我们”这些普遍出现的虚词和代词感兴趣，而会关注能代表文档中心意思的词汇。比如，一篇文章如果提到“库克”，“iPhone 5”，“发布会”这几个词，那你多半可以猜到它的大致内容了；反过来说，用户的搜索关键词也更可能来自这些词汇。所以，我们有必要在盒子小球模型中改进条件概率P(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，其中2^14篇文档出现了“美国”，那么“美国”这个词就把文档的不确定性从2^30缩小为2^14，它所包含的信息量为log(2^30/2^14)=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]) * (count(w[j], d[i]) * idf(w[j]) / sum { k = 1..size(d[i]), idf(w[k]) }) / (count(w[j] / size(D))
= P(d[i]) * (count(w[j], d[i]) / count(w[j]) * idf(w[j]) / sum { k = 1..size(d[i]), idf(w[k]) } / size(D)
= P(d[i]) * tf(w[j], d[i]) * idf(w[i]) * C2 / sum { k = 1..size(d[i]), idf(w[k]) }
= P(d[i]) * tf-idf(w[j], d[i]) / idf(d[i]) * C2

我们看到tf-idf已经被纳入框架内了，但是还多出了一个idf(d[i])，即文档d[i]的中各个词的信息量之和。这个多出来的idf(d[i])的意义是什么呢？实际上，tf-idf(w[j], d[i]) / idf(d[i])代表了关键词w[j]代表文档d[i]主题的概率。人们总是希望关键词代表了文档所表达的主题意思，比如：搜索“2012美国大选”是希望搜索结果文档的主题就是关于2012美国大选的。对于同样大小的tf-idf(w[j], d[i])，如果一篇文章的总信息量很大，那么关键词w[j]能代表文章主题的可能性当然就更小。这也可以解释为什么通常搜索引擎会给于网页标题中的词汇更高的权重，因为标题本身代表文档主题的概率是非常大的（除了少数所谓的标题党）。从搜索体验的角度讲，如果关键词w匹配文档d1和d2，但w是代表d1主题的关键词，但w不是代表d2主题的关键词，tf-idf不区分这两种情况，会给于d1和d2相同的权值，而条件概率模型会给于d1更高的概率。从另一个角度说，我们可以认为tf-idf是假设“所有文档中各词的信息量之和相等”。

多关键字

上面的条件概率模型主要是针对单个关键词的情况，下面我们进一步将其扩展到多关键字情况。我们知道，在tf-idf中，多个关键字的所产生的tf-idf值是一种叠加关系，那么这是否符合条件概率模型呢？答案是否定的。在两个关键字情况下，条件概率问题转化为“如果有人从一个盒子中同时摸出颜色c[x]的小球和颜色c[y]的小球，这两个小球来自于盒子b[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(b[i] | (c[x], c[y]))
= P(b[i], c[x], c[y]) / P(c[x], c[y])
= P(b[i]) * P(c[x], c[y] | b[i]) / P(c[x], c[y])
= P(b[i]) * P(c[x] | b[i]) * P(c[y] | b[i]) / (P(c[x]) * P(c[y]))
= P(b[i]) * (P(c[x] | b[i]) / P(c[x])) * (P(c[y] | b[i]) / P(c[y]))
= P(b[i]) * tf-idf(c[x], b[i]) * tf-idf(c[y], b[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]) * (P(w[x] | d[i]) / P(w[x])) * (P(w[y] | d[i]) / P(w[y]))
= P(d[i]) * (tf-idf(c[x], d[i]) / idf(d[i])) * (tf-idf(c[y], d[i]) / idf(d[i])) * C3

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

总结

TF-IDF模型是搜索引擎等实际应用中被广泛使用的信息检索模型，但对于TF-IDF模型一直存在各种疑问。本文为信息检索问题一种基于条件概率的盒子小球模型，其核心思想是把“查询串q和文档d的匹配度问题”转化为“查询串q来自于文档d的条件概率问题”。它从概率的视角为信息检索问题定义了比TF-IDF模型所表达的匹配度更为清晰的目标。此模型可将TF-IDF模型纳入其中，一方面解释其合理性，另一方面也发现了其不完善之处。另外，此模型还可以解释PageRank的意义，以及PageRank权重和TF-IDF权重之间为什么是乘积关系。

 

转: http://www.cnblogs.com/weidagang2046/archive/2012/10/22/tf-idf-from-probabilistic-view.html