TF-IDF之极简化信息论分析

昨天看到有人说，TF-IDF本质上是Kullback–Leibler divergence。参《如何确定网页和查询的相关性》by 吴军

问了一个搞IR的教授这个说法的出处。他说，似乎很明显，但搞不清楚谁第一个说的。

我试着做一个最简化的推导。这里用的TF-IDF是最简单的一种定义，实际用的，要比这复杂。

问题描述：一个查询q=(w1, w2…)，一个文档d=(w1, w2….)，其中w是单词，q和d都是bag of words。所有文档的集合是D=(d1, d2, …) 要求对所有文档，针对与q的相关性进行排序。

词频 TF(w,d) = w在d中出现的次数  / d中所有单词的个数

逆文档频率 IDF(w) = 所有文档的数量 / 包含w的文档的数量

单词w对文档d的相关度： TF*IDF(w,d) = TF(w,d)*IDF(w)

查询q对文档d的相关度，是它里面所有单词对d相关度的总和，Σ_w TF*IDF(w,d)。

对两个概率分布P和R，其KL-divergence，或者说相对熵， KL(P||R) = Σ_xP(x) log(P(x)/R(x))

如果直接套，查询q对文档d的K-L divergence是

KL(Q||D) = Σ_qP(q) log(P(q)/P(d))

这个不好算，什么叫q出现的概率和d出现的概率？

我们假设相关度具有可加性，我们只看一个单词w对一个文档的相关性，而不是一个查询q。

KL(W||D) = Σ_w P(w) log(P(w)/P(w|d))

其中P(w)是w在文档d中出现的概率【概率空间是单词】，P(w|d)是d中出现w的概率【概率空间是文档】。

KL(W||D) = Σ_w P(w) logP(w) -Σ_w P(w) log P(w|d))

第一项可排序无关，可略去。第二项，就和TF-IDF形似了。

【有待进一步思考】

参考 Robertson, S. (2004). Understanding inverse document frequency: on theoretical arguments for IDF. Journal of Documentation, 60(5), 503-520.