《Shannon怎样测定英语字母的熵值》由会员分享，可在线阅读，更多相关《Shannon怎样测定英语字母的熵值（6页珍藏版）》请在金锄头文库上搜索。
1、Shannon怎样测定英语字母的熵值？冯志伟早在 1928年，L. Hartley（哈特利）就提出了如何测量信息量大小的问题。他认为，如果某个装置有 D个可能的位置或物理状态，那么，两个这样的装置组合起来工作就会有D2个状态，三个这样的装置组合起来工作就会有 D3个状态，随着装置数量的增加，整个系统的可能的状态树木也相应地增加。为了测定其信息能力，要使 2D个装置的能力恰恰为 D个装置的能力的 2倍。因此，Hartley 把一个装置的信息能力定义为 logD，其中，D 是整个系统可以进入的不同的状态数目。在信息论中，Shannon 采用了 Hartley的这种办法来测定熵值。Shannon提出
2、，如果我们做某一有 n个可能的等概率结局的随机试验（例如，掷骰子，n=6），那么，这个随机试验的熵就用 log2n来度量。这种度量熵的方法是合理的。理由如下：第一，随机试验的可能结局 n越大，这个随机试验的不定度也就越大，因而它的熵也就越大。第二，如果我们同时做包含两个随机试验的复合试验，每一个随机试验有 n个可能的结局（例如，同时掷两颗骰子），那么，这个复合试验有 n2个结局，其熵等于 ，即等于只掷一颗骰子时的二倍，这与 Hartley的看法完全一致。第三，如果我们同时做包含两个随机试验的复合试验，一个随机试验有 m个可能结局，另一个随机试验有 n个可能结局（例如，投硬币时，m=2；掷骰子时
3、，n=6），那么，这个复合试验有 mn个可能的等概率结局，也就是说，这个复合试验的熵应该等于 log2mn，另一方面，我们又可以认为，这个复合试验结局的熵应该等于构成这个复合试验的两个随机试验结局的熵之和，即等于 log2m + log2n。但是，我们知道，可见，复合试验结局的熵，不论是把它看成一个统一的试验，还是看成两个随即试验的总和，都是相等的。这些事实都说明了我们用 log2n来度量熵的合理性。我们把有 n个可能的等概率结局的随机试验的熵记为 H0，这时的熵，叫做 1比特。 这意味着，如果某一消息由两个等概率的语言成分构成，那么，包含于每一个语言成分中的熵就是 1比特。如果随机试验有 n
4、个结局，而且，它们是不等概率的，那么，第 i个结局的概率为 pi,那么，这个随机试验的熵 H1用下面的公式来计算：1951年，Shannon 首先应计算出英语字母的不等概率独立链的熵 H1为 4.03比特。随机试验结局不等概率，减少了这个随机试验的不定度，因此，有不等式：对于计算机科学工作者来说，定义熵的最直观的办法，就是把熵想像成在最优编码中一定的判断或信息编码的比特数的下界。假定我们想在我们住的地方给赛马场的赛马下赌注，但是赛马场距离我们住的地方太远，我们不亲自到赛马场去，只好在我们住的地方给赛马场登记赌注的人发一个短的消息，告诉他我们给哪匹马下赌注。假定有八匹马参加比赛。给这个消息编码的
5、一个办法是用二进制代码来表示马的号码；这样，号码为 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的熵可以让我们知道其比特数的下界，计算如下：每
6、次比赛平均为 2比特的代码可以这样来编码：用最短的代码来表示我们估计概率最大的马，估计概率越小的马，其代码越长。例如，我们可以用 0来给估计概率最大的马编码，按照估计概率从大到小的排列，其余的马的代码分别为：10，110，1110，111100，111101，111110，111111。如果我们对于每一匹马的概率估计都是一样的，情况将如何呢？前面我们已经看到，如果对于每一匹马，我们都使用等长的二进制编码，每匹马都用 3比特来编码，因此平均的比特数为 3。这时的熵是一样的吗？是的，在这种情况下，每匹马的估计概率都是 1/8。我们选择马的熵是这样计算的：与熵有密切关系的是“困惑度”（perplex
7、ity）这个概念。如果我们把熵 H作为 2的指数，那么，2 H这个值就叫做困惑度。从直觉上，我们可以把困惑度理解为在随机试验中选择随机变量的加权平均数。因此，在等概率估计的 8匹马之间进行选择（这时，熵 H=3 比特），困惑度为 23，也就是 8。在概率有差异的 8匹马之间进行选择（这时，熵 H=2比特），困惑度是 22，也就是 4。显然，一个随机试验的熵越大，它的困惑度也就越大。在自然语言处理中，熵和困惑度是用于评估 N元语法模型的最普通的计量方法。如果考虑到前面的语言符号对后面的语言符号出现概率的影响，那么，可得出条件熵，Markov链的熵就是条件熵。随着 Markov链重数的增大，条件熵
8、越来越小，我们总是有： 这说明，每在前面追加一个语言符号，不会使包含在文本中一个语言符号的熵有所增加。另一方面，因为包含在文本的一个语言符号中的熵在任何场合总是正的，所以，存在着关系式：也就是说，熵是有下限的。当 k 逐渐增加时，熵逐渐趋于稳定而不再减少，这时，这个不再减少的熵就是包含在自然语言一个符号中的真实信息量，叫做极限熵。从等概率独立链的熵到不等概率独立链的熵，从不等概率独立链的熵到一阶条件熵，从一阶条件熵到二阶、三阶、.，一直到极限熵，是语言信息结构化的体现，它反映了语言的结构对于语言的信息的制约性。极限熵的概念，科学地把语言结构的这种制约性反映在语言符号的熵值中，它对于自然信息处理
9、的研究具有重要的意义。某个模型的交叉熵可以用来作为某个随机过程的极限熵的上界。我们可以使用这样的方法来估计英语的极限熵。为什么我们要关心英语极限熵呢？第一个原因是英语的极限熵将为我们对概率语法的试验提供一个可靠的下界。另一个原因是我们可以利用英语极限熵帮助理解语言中的哪一部分提供的信息最大。例如，判断英语的预测能力主要是依赖于词序，还是语义，还是形态，还是组成符号，还是语用方面的线索？这可以大大地帮助我们了解我们的语言模型应该着重研究哪一方面。计算英语极限熵的方法通常有两种。第一种方法是 Shannon使用的方法，这是他在信息论领域的开创性工作的一部分。他的思想是利用受试人来构造一个信息试验，
10、要求受试人来猜测字母，观察他们的猜测的字母中有多少是正确的，从而估计字母的概率，然后估计序列的熵值。实际的试验是这样来设计的：我们给受试人看一个英语文本，然后要求受试人猜测下一个字母。受试人利用他们的语言知识来猜测最可能出现的字母，然后猜测下一个最可能的字母，如此等等。我们把受试人猜对的次数记录下来。Shannon 指出，猜测数序列的熵与英语字母的极限熵是相同的。Shannon 这种观点的直觉解释是：如果受试人做 n个猜测，那么，给定猜测数序列，我们能够通过选择第 n个最可能的字母的方法，重建原来的文本。这样的方法要求猜字母而不是猜单词，受试人有时必须对所有的字母进行穷尽的搜索！所以，Shan
11、non 计算的是英语中每个字母的极限熵，而不是英语中每个单词的极限熵。他报告的结果是：英语字母的极限熵是 1.3比特（对于 27个字母而言26 个字母加上空白）。Shannon 的这个估值太低了一些，因为他是根据单篇的文本（Dumas Malose 的Jefferson the Virginian）来进行试验的。Shannon 还注意到，对于其他的文本（新闻报道、科学著作、诗歌），他的受试人往往会猜测错误，因此这时的熵就比较高。第二种计算英语的熵的方法有助于避免导致 Shannon 结果失误的单篇文本的问题。这个方法使用一个很好的随机模型，在一个很大的语料库上训练这个模型，用它给一个很长的英语
12、序列指派一个对数概率，计算时使用 Shannon-McMillan-Breiman定理：例如，Brown（布朗）等在 58,300万单词的英语文本上（293,181 个“型”type）训练了一个三元语法模型，用它来计算整个 Brown语料库的概率（1,014,312 个“例”token）。训练数据包括新闻、百科全书、小说、官方通信、加拿大议会的论文集，以及其他各种资源。然后，他们使用词的三元语法给 Brown语料库指派概率，把语料库看成是一个字母序列，从而来计算 Brown语料库的字符的熵。他们得到的结果是：每个字符的极限熵为 1.75比特（这里的字符集包含了 95个可印刷的全部 ASCII
13、字符）。这是在三元语法的情况下英语字母的条件熵。显而易见，这个条件熵比 Shannon测出的熵 1.3比特要大一些，而且Brown使用的字符集是 ASCII 字符集，包含 95个字符，很多字符超出了英语 26个字母的界限。大多数文献报道，包含在一个英语字母中的极限熵大约在 0.9296 比特到 1.5604比特之间，其平均值为 1.245 比特，这个计算结果与 Shannon测定的结果（1.3 比特）相近，我们一般都采用这样的计算结果。在实践的迫切要求下，继 Shannon测出了英语字母的不等概率独立链的熵 H1之后，人们又测出了一些印欧语言的熵。到目前为止，英语已经测出了九阶条件熵，俄语已经
14、测出了十四阶条件熵。下面，我们把法语、意大利语、西班牙语、英语、德语、罗马尼亚语、俄语的不等概率独立链的熵 H1列表比较如下：表 某些语言的熵 H1 冯志伟在上世纪 70年代，模仿香农对于英语字母的熵的研究，采用手工查频的方法首次估算出汉字的熵 H1为 9.65比特，并提出了“汉字容量极限定理”。他根据 Zipf定律，使用数学方法，证明了当统计样本中汉字的容量不大时，包含在一个汉字中的熵 H1随着汉字容量的增加而增加，当统计样本中的汉字容量达到 12366字时，包含在一个汉字中的熵H1就不再增加了，这意味着，在测定汉字的熵 H1的时候，统计样本中汉字的容量是有极限的。这个极限值就是 12366
15、字，超出这个极限值，测出的汉字的熵再也不会增加了，在这12366个汉字中，有 4000多个是常用字，4000 多个是次常用字，4000 多个是罕用字。他认为，这 12366个汉字可以代表古代和现代文献中汉字的基本面貌。由此他得出结论：从汉语书面语总体来考虑，在全部汉语书面语中（包括现代汉语和古代汉语），包含在一个汉字中的熵 H1是 9.65比特。由于当时冯志伟没有条件使用计算机查频，全部工作都是手工完成的，精确度难以得到保证。所以，冯志伟始终认为，这只是他的一个极不成熟猜测。1988年，北京航空学院计算机系刘源使用计算机自动查频计算出汉字的熵 H1为 9.71比特，1994年，新加坡国立大学计
16、算机系赖金锭使用计算机计算出汉字的熵 H1为 9.59比特，他们的结果与冯志伟原来用手工查频方法猜测的结果是很接近的。1996年，冯志伟还根据汉语与英语文本对比，首次估算出汉字的极限熵为 4.0462比特；2006 年，清华大学计算机系孙茂松、孙帆在大规模语料库（10 6-107汉字）的基础上，使用 Brown的方法估算出汉字的极限熵为 5.31比特，我个人认为，这个结果比冯志伟估算的结果更为准确。熵是信息量的度量，在自然语言处理中，熵是用来刻画语言数学面貌的非常有价值的数据。熵可以用来度量一个特定的语法中的信息量是多少，度量给定语法和给定语言的匹配程度有多高，预测一个给定的 N元语法中下一个单词是什么。如果有两个给定的语法和一个语料库，我
