class="topic_img" alt=""/>
信息检索概述
信息检索是当前应用十分广泛的一种技术，论文检索、搜索引擎都属于信息检索的范畴。通常，人们把信息检索问题抽象为：在文档集合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 count (w， d[j])}等其他形式？
2) 为什么 idf 是一个 log 形式，而 tf 又不是 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]小球的条件概率。
在没有更多信息的情况下，我们可以用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 值是一种叠加关系，那么这是否符合条件概率模型呢？答案是否定的。在两个关键字情况下，条件概率问题转化为“如果有人从一个盒子中同时摸出颜色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]) * (P(w[x] | d[i]) / P (w[x])) * (P(w[y] | d[i]) / P (w[y]))
= P (d[i]) * (tf-idf (w[x], d[i]) / idf (d[i])) * (tf-idf (w[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 权重之间为什么是乘积关系。
相关文章
