http://s7/middle/72d083c7g9e4e4d2fe0e6&690

 

            Shannon怎样测定英语字母的熵值？

                                       冯志伟

 

    早在1928年，L. Hartley（哈特利）就提出了如何测量信息量大小的问题。他认为，如果某个装置有D个可能的位置或物理状态，那么，两个这样的装置组合起来工作就会有D²个状态，三个这样的装置组合起来工作就会有D³个状态，随着装置数量的增加，整个系统的可能的状态树木也相应地增加。为了测定其信息能力，要使2D个装置的能力恰恰为D个装置的能力的2倍。因此，Hartley把一个装置的信息能力定义为logD，其中，D是整个系统可以进入的不同的状态数目。

   在信息论中，Shannon采用了Hartley的这种办法来测定熵值。

   Shannon提出，如果我们做某一有n个可能的等概率结局的随机试验（例如，掷骰子，n=6），那么，这个随机试验的熵就用log₂n来度量。这种度量熵的方法是合理的。理由如下：

第一，随机试验的可能结局n越大，这个随机试验的不定度也就越大，因而它的熵也就越大。

第二，如果我们同时做包含两个随机试验的复合试验，每一个随机试验有n个可能的结局（例如，同时掷两颗骰子），那么，这个复合试验有n²个结局，其熵等于 ，即等于只掷一颗骰子时的二倍，这与Hartley的看法完全一致。

第三，如果我们同时做包含两个随机试验的复合试验，一个随机试验有m个可能结局，另一个随机试验有n个可能结局（例如，投硬币时，m=2；掷骰子时，n=6），那么，这个复合试验有m·n个可能的等概率结局，也就是说，这个复合试验的熵应该等于log₂mn，另一方面，我们又可以认为，这个复合试验结局的熵应该等于构成这个复合试验的两个随机试验结局的熵之和，即等于log₂m + log₂n。但是，我们知道，

   http://s15/middle/72d083c7g9e4e76e880ee&690 

可见，复合试验结局的熵，不论是把它看成一个统一的试验，还是看成两个随即试验的总和，都是相等的。

这些事实都说明了我们用log₂n来度量熵的合理性。

我们把有n个可能的等概率结局的随机试验的熵记为H₀，

   http://s5/middle/72d083c7g9e4e584606a4&690                 

这时的熵，叫做1比特。

   这意味着，如果某一消息由两个等概率的语言成分构成，那么，包含于每一个语言成分中的熵就是1比特。

如果随机试验有n个结局，而且，它们是不等概率的，那么，第i个结局的概率为p_i,那么，这个随机试验的熵H₁用下面的公式来计算：

                  http://s15/middle/72d083c7g9e4e7b7da77e&690       

1951年，Shannon首先应计算出英语字母的不等概率独立链的熵H₁为4.03比特。

随机试验结局不等概率，减少了这个随机试验的不定度，因此，有不等式：

 http://s10/middle/72d083c7g9e4e7d7750a9&690

 

 

对于计算机科学工作者来说，定义熵的最直观的办法，就是把熵想像成在最优编码中一定的判断或信息编码的比特数的下界。

       假定我们想在我们住的地方给赛马场的赛马下赌注，但是赛马场距离我们住的地方太远，我们不亲自到赛马场去，只好在我们住的地方给赛马场登记赌注的人发一个短的消息，告诉他我们给哪匹马下赌注。

假定有八匹马参加比赛。给这个消息编码的一个办法是用二进制代码来表示马的号码；这样，号码为1的马的二进制代码是001，号码为2的马的二进制代码是010，号码为3的马的二进制代码是011，等等，号码为8的马的二进制代码是000。如果我们用一天的时间来下赌注，每一匹马用比特来编码，每次比赛我们要发出3比特的信息。

       我们能不能把这件事做得好一点呢？我们可以根据赌注的实际分布来传送消息，假定每匹马的先验概率如下：

 

              马1        1/2                 马5        1/64

              马2        1/4                 马6        1/64

              马3        1/8                 马7        1/64

              马4        1/16                马8        1/64  

                               马的先验概率

 

对于这些马的随机变量X的熵可以让我们知道其比特数的下界，计算如下：

 

http://s14/middle/72d083c7g9e4e7f7c129d&690

每次比赛平均为2比特的代码可以这样来编码：用最短的代码来表示我们估计概率最大的马，估计概率越小的马，其代码越长。例如，我们可以用0来给估计概率最大的马编码，按照估计概率从大到小的排列，其余的马的代码分别为：10，110，1110，111100，111101，111110，111111。

如果我们对于每一匹马的概率估计都是一样的，情况将如何呢？前面我们已经看到，如果对于每一匹马，我们都使用等长的二进制编码，每匹马都用3比特来编码，因此平均的比特数为3。这时的熵是一样的吗？是的，在这种情况下，每匹马的估计概率都是1/8。我们选择马的熵是这样计算的：http://s2/middle/72d083c7g9e4e81b450a1&690   

与熵有密切关系的是“困惑度”（perplexity）这个概念。如果我们把熵H作为2的指数，那么，2^H这个值就叫做困惑度。从直觉上，我们可以把困惑度理解为在随机试验中选择随机变量的加权平均数。因此，在等概率估计的8匹马之间进行选择（这时，熵 H=3比特），困惑度为2³，也就是8。在概率有差异的8匹马之间进行选择（这时，熵H=2比特），困惑度是2²，也就是4。显然，一个随机试验的熵越大，它的困惑度也就越大。

在自然语言处理中，熵和困惑度是用于评估N元语法模型的最普通的计量方法。

    如果考虑到前面的语言符号对后面的语言符号出现概率的影响，那么，可得出条件熵，Markov链的熵就是条件熵。

  随着Markov链重数的增大，条件熵越来越小，我们总是有：

http://s6/middle/72d083c7g9e4e839fda05&690            

     这说明，每在前面追加一个语言符号，不会使包含在文本中一个语言符号的熵有所增加。另一方面，因为包含在文本的一个语言符号中的熵在任何场合总是正的，所以，存在着关系式：

http://s10/middle/72d083c7g9e4e8544e259&690                                                             

  也就是说，熵是有下限的。当 k 逐渐增加时，熵逐渐趋于稳定而不再减少，这时，这个不再减少的熵就是包含在自然语言一个符号中的真实信息量，叫做极限熵。

    从等概率独立链的熵到不等概率独立链的熵，从不等概率独立链的熵到一阶条件熵，从一阶条件熵到二阶、三阶、......，一直到极限熵，是语言信息结构化的体现，它反映了语言的结构对于语言的信息的制约性。极限熵的概念，科学地把语言结构的这种制约性反映在语言符号的熵值中，它对于自然信息处理的研究具有重要的意义。

某个模型的交叉熵可以用来作为某个随机过程的极限熵的上界。我们可以使用这样的方法来估计英语的极限熵。

为什么我们要关心英语极限熵呢？

第一个原因是英语的极限熵将为我们对概率语法的试验提供一个可靠的下界。另一个原因是我们可以利用英语极限熵帮助理解语言中的哪一部分提供的信息最大。例如，判断英语的预测能力主要是依赖于词序，还是语义，还是形态，还是组成符号，还是语用方面的线索？这可以大大地帮助我们了解我们的语言模型应该着重研究哪一方面。

计算英语极限熵的方法通常有两种。

第一种方法是Shannon使用的方法，这是他在信息论领域的开创性工作的一部分。他的思想是利用受试人来构造一个信息试验，要求受试人来猜测字母，观察他们的猜测的字母中有多少是正确的，从而估计字母的概率，然后估计序列的熵值。

实际的试验是这样来设计的：我们给受试人看一个英语文本，然后要求受试人猜测下一个字母。受试人利用他们的语言知识来猜测最可能出现的字母，然后猜测下一个最可能的字母，如此等等。我们把受试人猜对的次数记录下来。Shannon指出，猜测数序列的熵与英语字母的极限熵是相同的。Shannon这种观点的直觉解释是：如果受试人做n个猜测，那么，给定猜测数序列，我们能够通过选择第n个最可能的字母的方法，重建原来的文本。这样的方法要求猜字母而不是猜单词，受试人有时必须对所有的字母进行穷尽的搜索！所以，Shannon计算的是英语中每个字母的极限熵，而不是英语中每个单词的极限熵。他报告的结果是：英语字母的极限熵是1.3比特（对于27个字母而言[26个字母加上空白]）。Shannon 的这个估值太低了一些，因为他是根据单篇的文本（Dumas Malose的《Jefferson the Virginian》）来进行试验的。Shannon还注意到，对于其他的文本（新闻报道、科学著作、诗歌），他的受试人往往会猜测错误，因此这时的熵就比较高。

第二种计算英语的熵的方法有助于避免导致Shannon 结果失误的单篇文本的问题。这个方法使用一个很好的随机模型，在一个很大的语料库上训练这个模型，用它给一个很长的英语序列指派一个对数概率，计算时使用Shannon-McMillan-Breiman定理：

                          http://s2/middle/72d083c7g9e4e87c2aa01&690

例如，Brown（布朗）等在58,300万单词的英语文本上（293,181个“型”[type]）训练了一个三元语法模型，用它来计算整个Brown语料库的概率（1,014,312个“例”[token]）。训练数据包括新闻、百科全书、小说、官方通信、加拿大议会的论文集，以及其他各种资源。

    然后，他们使用词的三元语法给Brown语料库指派概率，把语料库看成是一个字母序列，从而来计算Brown语料库的字符的熵。他们得到的结果是：每个字符的极限熵为1.75比特（这里的字符集包含了95个可印刷的全部ASCII 字符）。这是在三元语法的情况下英语字母的条件熵。显而易见，这个条件熵比Shannon测出的熵1.3比特要大一些，而且Brown使用的字符集是ASCII 字符集，包含95个字符，很多字符超出了英语26个字母的界限。

大多数文献报道，包含在一个英语字母中的极限熵大约在 0.9296比特到1.5604比特之间，其平均值为 1.245比特，这个计算结果与Shannon测定的结果（1.3比特）相近，我们一般都采用这样的计算结果。

    在实践的迫切要求下，继Shannon测出了英语字母的不等概率独立链的熵H₁之后，人们又测出了一些印欧语言的熵。到目前为止，英语已经测出了九阶条件熵，俄语已经测出了十四阶条件熵。下面，我们把法语、意大利语、西班牙语、英语、德语、罗马尼亚语、俄语的不等概率独立链的熵H₁列表比较如下：

                 表    某些语言的熵H₁

http://s16/middle/72d083c7g9e4e557cbb5f&690

 

 

    冯志伟在上世纪70年代，模仿香农对于英语字母的熵的研究，采用手工查频的方法首次估算出汉字的熵H₁为9.65比特，并提出了“汉字容量极限定理”。他根据Zipf定律，使用数学方法，证明了当统计样本中汉字的容量不大时，包含在一个汉字中的熵H₁随着汉字容量的增加而增加，当统计样本中的汉字容量达到12366字时，包含在一个汉字中的熵H₁就不再增加了，这意味着，在测定汉字的熵H₁的时候，统计样本中汉字的容量是有极限的。这个极限值就是12366字，超出这个极限值，测出的汉字的熵再也不会增加了，在这12366个汉字中，有4000多个是常用字，4000多个是次常用字，4000多个是罕用字。他认为，这12366个汉字可以代表古代和现代文献中汉字的基本面貌。由此他得出结论：从汉语书面语总体来考虑，在全部汉语书面语中（包括现代汉语和古代汉语），包含在一个汉字中的熵H₁是9.65比特。由于当时冯志伟没有条件使用计算机查频，全部工作都是手工完成的，精确度难以得到保证。所以，冯志伟始终认为，这只是他的一个极不成熟猜测。

1988年，北京航空学院计算机系刘源使用计算机自动查频计算出汉字的熵H₁为9.71比特，1994年，新加坡国立大学计算机系赖金锭使用计算机计算出汉字的熵H₁为9.59比特，他们的结果与冯志伟原来用手工查频方法猜测的结果是很接近的。

    1996年，冯志伟还根据汉语与英语文本对比，首次估算出汉字的极限熵为4.0462比特；2006年，清华大学计算机系孙茂松、孙帆在大规模语料库（10⁶-10⁷汉字）的基础上，使用Brown的方法估算出汉字的极限熵为5.31比特，我个人认为，这个结果比冯志伟估算的结果更为准确。

    熵是信息量的度量，在自然语言处理中，熵是用来刻画语言数学面貌的非常有价值的数据。熵可以用来度量一个特定的语法中的信息量是多少，度量给定语法和给定语言的匹配程度有多高，预测一个给定的N元语法中下一个单词是什么。如果有两个给定的语法和一个语料库，我们可以使用熵来估计哪一个语法与语料库匹配得更好。我们也可以使用熵来比较两个语音识别任务的困难程度，也可以使用它来测量一个给定的概率语法与人类语法的匹配程度。