(Shannon怎样测定英语字母的熵值.docxVIP

Shannon怎样测定英语字母的熵值？????冯志伟???早在1928年，L. Hartley（哈特利）就提出了如何测量信息量大小的问题。他认为，如果某个装置有D个可能的位置或物理状态，那么，两个这样的装置组合起来工作就会有D2个状态，三个这样的装置组合起来工作就会有D3个状态，随着装置数量的增加，整个系统的可能的状态树木也相应地增加。为了测定其信息能力，要使2D个装置的能力恰恰为D个装置的能力的2倍。因此，Hartley把一个装置的信息能力定义为logD，其中，D是整个系统可以进入的不同的状态数目。??在信息论中，Shannon采用了Hartley的这种办法来测定熵值。??Shannon提出，如果我们做某一有n个可能的等概率结局的随机试验（例如，掷骰子，n=6），那么，这个随机试验的熵就用log2n来度量。这种度量熵的方法是合理的。理由如下：第一，随机试验的可能结局n越大，这个随机试验的不定度也就越大，因而它的熵也就越大。第二，如果我们同时做包含两个随机试验的复合试验，每一个随机试验有n个可能的结局（例如，同时掷两颗骰子），那么，这个复合试验有n2个结局，其熵等于 ，即等于只掷一颗骰子时的二倍，这与Hartley的看法完全一致。第三，如果我们同时做包含两个随机试验的复合试验，一个随机试验有m个可能结局，另一个随机试验有n个可能结局（例如，投硬币时，m=2；掷骰子时，n=6），那么，这个复合试验有m·n个可能的等概率结局，也就是说，这个复合试验的熵应该等于log2mn，另一方面，我们又可以认为，这个复合试验结局的熵应该等于构成这个复合试验的两个随机试验结局的熵之和，即等于log2m + log2n。但是，我们知道，??可见，复合试验结局的熵，不论是把它看成一个统一的试验，还是看成两个随即试验的总和，都是相等的。这些事实都说明了我们用log2n来度量熵的合理性。我们把有n个可能的等概率结局的随机试验的熵记为H0，??这时的熵，叫做1比特。??这意味着，如果某一消息由两个等概率的语言成分构成，那么，包含于每一个语言成分中的熵就是1比特。如果随机试验有n个结局，而且，它们是不等概率的，那么，第i个结局的概率为pi,那么，这个随机试验的熵H1用下面的公式来计算：??1951年，Shannon首先应计算出英语字母的不等概率独立链的熵H1为4.03比特。随机试验结局不等概率，减少了这个随机试验的不定度，因此，有不等式：???对于计算机科学工作者来说，定义熵的最直观的办法，就是把熵想像成在最优编码中一定的判断或信息编码的比特数的下界。??假定我们想在我们住的地方给赛马场的赛马下赌注，但是赛马场距离我们住的地方太远，我们不亲自到赛马场去，只好在我们住的地方给赛马场登记赌注的人发一个短的消息，告诉他我们给哪匹马下赌注。假定有八匹马参加比赛。给这个消息编码的一个办法是用二进制代码来表示马的号码；这样，号码为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的熵可以让我们知道其比特数的下界，计算如下：?每次比赛平均为2比特的代码可以这样来编码：用最短的代码来表示我们估计概率最大的马，估计概率越小的马，其代码越长。例如，我们可以用0来给估计概率最大的马编码，按照估计概率从大到小的排列，其余的马的代码分别为：10，110，1110，111100，111101，111110，111111。如果我们对于每一匹马的概率估计都是一样的，情况将如何呢？前面我们已经看到，如果对于每一匹马，我们都使用等长的二进制编码，每匹马都用3比特来编码，因此平均的比特数为3。这时的熵是一样的吗？是的，在这种情况下，每匹马的估计概率都是1/8。我们选择马的熵是这样计算的：?与熵有密切关系的是“困惑度”（perplexity）这个概念。如果我们把熵H作为2的指数，那么，2H这个值就叫做困惑度。从直觉上，我们可以把困惑度理解为在随机试验中选择随机变量的加权平均数。因此，在等概率估计的8匹马之间进行选择（这时，熵 H=3比特），困惑度为23，也就是8。在概率有差异的8匹马之间进行选择（这时，熵H=2比特），困惑度是22，也就是4。显然，一个随机试验的熵越大，它的困惑度也就越大。在自然语言处理中，熵和困惑度是用于评估N元语法模型的最普通的计量方法