Deep Learning Specialization on Coursera

idf逆文档频率为什么要用log??

+4 投票
时间: 2012年 6月 15日 分类:信息检索 作者: sgh3352952 (170 基本)
更改标签 2012年 6月 18日 作者:fandywang

首先,log很容易让人联想到熵和简化计算,而此处无疑是前者。

这里不妨扩展下楼主的问题:TF*IDF的科学依据是什么?或者如何科学解释tf*idf,为什么tf*idf可以成为信息检索领域文档关键词行之有效的权重量化方法?

记得在读研期间也曾想追根溯源,找到tf*idf的科学解释,而绝大部分书本上给出的文字解释 “TF:衡量词对描述文档内容的能力大小,IDF:衡量词区分其所在文档与其他文档的能力”。刚开始如 @52nlp 一样找到了吴军老师google黑板报的《数学之美 系列九 -- 如何确定网页和查询的相关性》,可惜文中仅给出了TF*IDF的历史背景以及结论(亦可见@52nlp 给出的解释),相信大家看后还是一头雾水,至少我是。因为其略去了太多中间过程,好在最近出版的《数学之美》 实体书中吴军老师在延伸阅读部分给出了较详细的解释,但是,个人感觉还不够严谨。

关于TF*IDF的解释,我认为解释最到位、最直观的是梁斌博士的《走进搜索引擎》,详细如下:

假定一个文档就是信息源,该文档包含T1,T2,T3,...,Tn共n个词汇,每个词汇出现了N1,N1,N3,...,Nn次,词汇在文档集中出现的文档频率(词汇的发生概率)分别为D1,D2,D3,...,Dn,那么传输一个这样的文档需要多少编码长度呢?

假设每个词汇的出现相互独立,并且不考虑出现的先后顺序(即把文档看作bag of words,信息检索模型中常见)。因此由这些词汇组成的文档的概率为:X=D1^N1*D2^N2*D3*N3* ... *Dn^Nn。那么,对具有这种概率的事件进行编码,需要的编码长度为(依据为自信息:任意随机事件的自信息量定义为该事件发生概率的对数的负值,设事件x的概率为p(x),那么其自信息定义为I(x)=-log(p(x)),也可以理解为某个概率的事件进行编码所需要的最小编码长度):

-log(X)=-log(D1^N1*D2^N2*D3*N3* ... *Dn^Nn)

          =-N1*log(D1) - N2*log(D2) - N3*log(D3) - ... -Nn*log(Dn)

即这篇文档理论上能够最大极限地被压缩到-log(X)比特,并且数学上可以证明这样的压缩形式是极限压缩。

另外,也可以这样理解,对于关键词Ti,文档频率为Di,这个关键词的编码长度为-log(Di),因此在文档中出现Ni次,所以,共需要编码长度为-Ni*log(Di)。而整个文档的编码长度为sum(-Ni*log(Di)),其中1<=i<=n,与上面的式子相同。

接下来,考察该文档中每个词的平均编码长度(与之对应的是熵的概念,因为在信息论中自信息量是一个随机变量,不能用来作为整个信源的信息测度,所以引入平均自信息量,即熵,定义为H(X)=sum(-pi*log(pi))),即整个文档需要的编码长度除以总词数,即:log(X)/sum(Ni),即-N1*log(D1) - N2*log(D2) - N3*log(D3) - ... -Nn*log(Dn) / (N1+N2+N3 + ... + Nn)

在这个平均编码长度中,每个关键词都做出了不同的贡献。我们将关键词在文档中的重要性量化为对平均编码长度的贡献上。不难得出如下结论:越是出现次数多(词频高)且罕见的词汇(文档频率低)的关键词对平均编码长度大小的贡献越大。

假设K=sum(Ni),对于关键词Ti而言,它对平均编码长度的贡献为:-Ni*log(Di) / K,即 Ni / k * log(1/Di),其中Ni / K为在文档中关键词Ti的词频(TF,Term Frequency),log(1/Di)=log(|D| / |{j: Ti 出现在文档dj中}|)为文档中关键词Ti的文档频率倒数的对数式,称为逆文档频率(IDF,Inverse Document Frequency),这就是经典的TF*IDF。

这里把文档看作信息源,需要通过信道传输,而首要工作就是编码,文档的最小编码长度即为自信息量,平均编码长度为熵,而每个关键词对文档的编码都有不同的贡献,根据贡献的大小量化其重要性,即TF*IDF。

拓展:

由于TF*IDF未考虑词的位置,以及web页面中的HTML标记等信息,所以在实际应用中有很多变形,大家如果有好的实践经验,不妨在此分享和讨论?smiley

汇总如下后面怎么没有了?
sorry,正在写,如上

1个回答

+1投票

可以参考吴军老师的《数学之美》,在“如何确定网页和查询的相关性“这一章讲到了idf的历史,关于为什么是log,也做了相关的解释:

TF/IDF(term frequency/inverse document frequency) 的概念被公认为信息检索中最重要的发明。在搜索、文献分类和其他相关领域有广泛的应用。讲起 TF/IDF 的历史蛮有意思。IDF 的概念最早是剑桥大学的斯巴克-琼斯[注:她有两个姓] (Karen Sparck Jones)提出来的。斯巴克-琼斯 1972年在一篇题为关键词特殊性的统计解释和她在文献检索中的应用的论文中提出IDF。遗憾的是,她既没有从理论上解释为什么权重IDF 应该是对数函数log(D/Dw)(而不是其它的函数,比如平方根),也没有在这个题目上作进一步深入研究,以至于在以后的很多文献中人们提到 TF/IDF时没有引用她的论文,绝大多数人甚至不知道斯巴克-琼斯的贡献。同年罗宾逊写了个两页纸的解释,解释得很不好。倒是后来康乃尔大学的萨尔顿 (Salton)多次写文章、写书讨论 TF/IDF 在信息检索中的用途,加上萨尔顿本人的大名(信息检索的世界大奖就是以萨尔顿的名字命名的)。很多人都引用萨尔顿的书,甚至以为这个信息检索中最重要的概 念是他提出的。当然,世界并没有忘记斯巴克-琼斯的贡献,2004年,在纪念文献学学报创刊 60 周年之际,该学报重印了斯巴克-琼斯的大作。罗宾逊在同期期刊上写了篇文章,用香农的信息论解释 IDF,这回的解释是对的,但文章写的并不好、非常冗长(足足十八页),把一个简单问题搞复杂了。其实,信息论的学者们已经发现并指出,其实 IDF 的概念就是一个特定条件下、关键词的概率分布的交叉熵(Kullback-Leibler Divergence)(详见上一系列)。这样,信息检索相关性的度量,又回到了信息论

补充:多谢fandy的解释,这个问题很有意思,我也只是引用了《数学之美》中的内容,但是对于其中所提及的论文没有考证,以下是几篇相关的论文,先放到这里,欢迎大家讨论:

1.  斯巴克-琼斯 1972年在一篇题为关键词特殊性的统计解释和她在文献检索中的应用的论文中提出IDF: A statistical interpretation of term specificity
and its application in retrieval

2. 2004年,在纪念文献学学报创刊 60 周年之际,该学报重印了斯巴克-琼斯的大作。罗宾逊在同期期刊上写了篇文章,用香农的信息论解释 IDF: Understanding Inverse Document Frequency: On theoretical arguments for IDF

3. Inverse Document Frequency (IDF): A Measure of Deviations from Poisson

4. Interpreting TF-IDF term weights as making relevance decisions

已回复 2012年 6月 15日 作者: 52nlp (3,230 基本)
编辑 2012年 6月 18日 作者:52nlp
谢谢你!
NLPJob

Text Summarization

Keyword Extraction

Text Processing

Word Similarity

Best Coursera Course

Best Coursera Courses

Elastic Patent

本站架设在 DigitalOcean 上, 采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本站内容必须也遵循“署名-非商业用途-保持一致”的创作共用协议.