[NLP] 信息熵在自然语言处理中的运用


浅谈Entropy,Conditional Entropy 和 Mutual Information

Posted by Yufan Zheng on Octorber 15, 2017

生活经验告诉我们,想要知道一个物体的长宽高,我们可以通过尺子测量。想要比较两个物体的质量,我们可以用天平来衡量。一切的一切,因为有了度量,而变得精准并且可比较。但现在我问你,如果在你的面前的是一本50万字的书,你能告诉我这本书包含了多少信息么?

这个时候,我们好像就陷入了沉思中,我们知道文字是信息的载体,而信息是看不见摸不着的东西,怎样可以给信息的多少定义呢?

Entropy

1948 年的香农祖师爷(Claude Shannon),和现在的我们一样,也在绞尽脑汁的想着如何解决这个难题。但是祖师爷毕竟是祖师爷,和我等凡人不同,他在著名的论文 “通讯的数学原理” 中,他提出了一个著名的概念,那就是信息熵(Entropy),即是基于一个随机事件出现的概率,来衡量信息的大小。一个随机事件的不确定度越高,它的信息熵也就越高。就是这个简单的“香农公式”的基本原理。让信息第一次有了大小了。而正是这个信息熵的概念,对后世的研究起到了无比重要的作用。

年轻时候的香农,真的是个不折不扣的美男子呢。明明可以靠脸吃饭,偏偏要靠才华。

那么,那个流芳百世的香农公式,到底是什么呢?其实它的形式非常的简单,只是将概率和概率的对数相乘,然后求和取相反数即是了。

现在我们回归最开始的问题,一本50万字的中文书,究竟包含了多少信息呢?我们知道常用的汉字大概是有7000个。假如每个汉字出现的概率相等,那么我们大概需要13个字节来表示一个汉字(即是二进制的13位),那么每个汉字我们需要13比特来表示。但是实际上汉字的使用是不平衡的,前百分之十的汉字占用了百分之九十五的篇幅。所以根据香农的公式,实际上信息的含量大概会被降低到8到9个比特。如果我们再考虑一下上下文的关系,那么汉字的信息熵会变为大概5个比特。

50万字的书籍,所包含的信息就是250万比特,如果我们用一个比较好的压缩算法,整本书可以存成一个320K的文件。

可是光知道一本书的信息量有多少并没什么意义,和自然语言处理有什么关系呢?

好吧,我承认我有点跑题了,现在我就来介绍一下信息熵在自然语言中的运用。其实我现在回想起来,觉得信息熵的出现更多的是为了提供了 NLP 的理论基础。其实很多自然语言处理的方法是非常 intuitive 的,我们很容易会想到要这么去做,但是问为什么要这么做呢?往往就不太好解释了,而香农的这一套公式,则可以很好的解释他们。

Conditional Entropy

闲话不多说,首先来举个栗子。想象一个情景,你现在问小明一个问题,说你的脑袋里面正在构思着一个句子,让小明来猜这个句子里面都有些什么词组成。

小明会说,我擦嘞,中文词语成千上万,那么多的词,我怎么猜呀。这时候,你告诉他,这个句子里面有单词“我”。OK,小明开始思考,既然这个句子里面有了人称代词“我”,那么应该会出现个动词做谓语,于是小明开始猜这个句子里可能会有的谓语词,是“做”?是“去”?还是“爱”呢?等等等等。这时候,你又提供了他了这个句子里的另外一个词的信息,是“北京”,那么这个时候的小明就将一些不合理的动词选项排除掉了,比如“做”,因为“我做北京”,这个句子不合理。然后你又告诉小明,这个句子里还有一个词是“天安门”。“我?北京天安门”,哦,这个时候小明大概可以猜出来了,这个句子应该是“我爱北京天安门”。

从上面的故事,我们可以发现,好像一个单词,它是否会出现在句子中,是由它周围的词来决定的。比如前面和后面,出现了“我”和“北京天安门”,那么这个可能出现的词,好像就已经被限定死了,而不是任意词填进去都可以了。是不是很像我们小时候做的语文题,将一个句子中的一个部分挖去,然后我们来填空。

当一个句子的已知词越少,我们预测这个句子里的其他的难度越大,而知道的词越多,预测其他的词也就越容易。这也就是我们说的自由度下降了。利用信息熵的说法,当我们对一个句子一无所知的时候,它的熵值越大,而当我们知道的词越多,剩下的词的自由度越小,信息熵也在随之在下降。

这是不是已经很像我们的统计语言学模型了呢?

从信息熵的角度,我们来重新审视一下 word2vec,是不是觉得合理多了呢?

好,我们现在来利用公式来表示一下这个问题。这个时候,我们需要引入一个概念,叫做条件熵 ( conditional entropy )。

上图中的 X 和 Y 分别是一个句子中不同的两个词语,条件熵就是如果我们已知 X 存在这个句子中,Y 也出现在这个句子中的概率是多少。当然,这里所说的句子的概念,是广义的,你也可以是自定义一个 window size来说这是一个句子。

我们也可以证明,H(Y|X) <= H(Y),即是说,知道另外一个词 X 之后,词 Y 是否出现,这个事件的信息熵会下降。但我们看到还有等号的存在,聪明的你应该这时候会发现,当且仅当 X 和 Y 是完全独立的两个事件时,等号才成立。这也和我们的生活中的常识相对应。

以上我们都是讨论 X 和 Y 是两个词是否存在于一个句子中的情况。现在我们稍微扩展一下。

扩展一:主题模型 ( Topic Modeling )

主题模型是用于解决文档的分类问题的。如果现在我们已知的事件 X 不再是一个单词是否存在,而是这个句子是否是属于某一个类别,比如是体育类,是时事新闻类,等等。那么这样,单词 Y 出现在句子里的概率分布就会发生变化了。它的出现或者出现的概率就不是50%了。它的信息熵也会相对应的下降了。

主题模型中最经典的 Naive Bayes 算法,是根据单词出现在当前 Topic 的频率作为概率来推算,这也是根据最大期望模型 EM 算法来得出的结论。仔细想想,是不是也有条件熵模型的因素在里面呢?

扩展二:最大熵模型 ( MaxEnt )

我们已经知道,现实世界给与我们的信息越多,要预测的事件的信息熵值就会下降,相应的这个事件的发生概率也越来越趋于稳定,因为自由度下降了。最大熵模型就是这个原理。

在自然语言处理的命名实体识别问题当中,如果我给定的信息是,当前英文单词的前面一个词是at,并且是介词,当前单词的词性是名词且首字母是大写的,后面一个单词是句子的结束符。那么知道了这些信息的你,多半已经猜出这个当前单词的实体类别应该是地点 Location 了。

我们将一个一个的事件作为特征函数提取出来,然后根据事件发生的情况来发掘要预测事件的概率。特征越多,理论上预测也会越准。现在看上去,这是不是已经很像 CRF 算法的雏形了呀?

Mutual Information

“互信息”是信息熵的引申概念,它是对两个随机事件相关性的度量。比如说今天随机事件北京下雨和随机变量空气湿度的相关性就很大,但是和姚明所在的休斯敦火箭队是否能赢公牛队几乎无关。互信息就是用来量化度量这种相关性的。

这么看公式有些难以理解,我们换个形式。

这个时候,看上去就简单多了,所谓的互信息,就是了解 Y 的情况下,对 X 的信息的消减情况的一个度量。

在自然语言处理中,经常要度量一些语言现象的相关性。比如在机器翻译中,最难的问题是词义的二义性(歧义性)问题。比如 Bush 一词可以是美国总统的名字,也可以是灌木丛。(有一个笑话,美国上届总统候选人凯里 Kerry 的名字被一些机器翻译系统翻译成了"爱尔兰的小母牛",Kerry 在英语中另外一个意思。)那么如何正确地翻译这个词呢?人们很容易想到要用语法、要分析语句等等。其实,至今为止,没有一种语法能很好解决这个问题。

熵,条件熵和互信息的关系。

真正实用的方法是使用互信息。具体的解决办法大致如下:首先从大量文本中找出和总统布什一起出现的互信息最大的一些词,比如总统、美国、国会、华盛顿等等,当然,再用同样的方法找出和灌木丛一起出现的互信息最大的词,比如土壤、植物、野生等等。有了这两组词,在翻译 Bush 时,看看上下文中哪类相关的词多就可以了。

Conclusion & Acknowledgement

这篇文章是我在上 Coursera 上伊利诺伊大学厄巴纳-香槟分校的 Text Mining and Analytics 这门课的时候,写下的一点感悟,文章中的部分内容有参考吴军的《数学之美》这本书的部分章节。再次对其表示感谢。

信息熵的概念,我在很久之前就已经接触过了,当时上本科的时候,并没有觉得它有什么用处。直到现在在自然语言处理的研究和工作中,发现它的用处几乎无处不再。再次给香农祖师爷献上我的膝盖。