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

ShannonShannon 怎样测定英语字母的熵值 怎样测定英语字母的熵值 冯志伟 早在 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 元语法模型的最普通的计量方法 如果考虑到前面的语言符号对后面的语言符号出现概率的影响 那么 可得出条件熵 Markov 链的熵就是条件熵 随着 Markov 链重数的增大 条件熵越来越小 我们总是有 这说明 每在前面追加一个语言符号 不会使包含在文本中一个语言符号的熵有所增 加 另一方面 因为包含在文本的一个语言符号中的熵在任何场合总是正的 所以 存在 着关系式 也就是说 熵是有下限的 当 k 逐渐增加时 熵逐渐趋于稳定而不再减少 这时 这个 不再减少的熵就是包含在自然语言一个符号中的真实信息量 叫做极限熵 从等概率独立链的熵到不等概率独立链的熵 从不等概率独立链的熵到一阶条件熵 从一阶条件熵到二阶 三阶 一直到极限熵 是语言信息结构化的体现 它反映 了语言的结构对于语言的信息的制约性 极限熵的概念 科学地把语言结构的这种制约性 反映在语言符号的熵值中 它对于自然信息处理的研究具有重要的意义 某个模型的交叉熵可以用来作为某个随机过程的极限熵的上界 我们可以使用这样的方法 来估计英语的极限熵 为什么我们要关心英语极限熵呢 第一个原因是英语的极限熵将为我们对概率语法的试验提供一个可靠的下界 另一个原因 是我们可以利用英语极限熵帮助理解语言中的哪一部分提供的信息最大 例如 判断英语 的预测能力主要是依赖于词序 还是语义 还是形态 还是组成符号 还是语用方面的线 索 这可以大大地帮助我们了解我们的语言模型应该着重研究哪一方面 计算英语极限熵的方法通常有两种 第一种方法是 Shannon 使用的方法 这是他在信息论领域的开创性工作的一部分 他的思 想是利用受试人来构造一个信息试验 要求受试人来猜测字母 观察他们的猜测的字母中 有多少是正确的 从而估计字母的概率 然后估计序列的熵值 实际的试验是这样来设计的 我们给受试人看一个英语文本 然后要求受试人猜测下一个 字母 受试人利用他们的语言知识来猜测最可能出现的字母 然后猜测下一个最可能的字 母 如此等等 我们把受试人猜对的次数记录下来 Shannon 指出 猜测数序列的熵与英 语字母的极限熵是相同的 Shannon 这种观点的直觉解释是 如果受试人做 n 个猜测 那 么 给定猜测数序列 我们能够通过选择第 n 个最可能的字母的方法 重建原来的文本 这样的方法要求猜字母而不是猜单词 受试人有时必须对所有的字母进行穷尽的搜索 所 以 Shannon 计算的是英语中每个字母的极限熵 而不是英语中每个单词的极限熵 他报 告的结果是 英语字母的极限熵是 1 3 比特 对于 27 个字母而言 26 个字母加上空白 Shannon 的这个估值太低了一些 因为他是根据单篇的文本 Dumas Malose 的 Jefferson the Virginian 来进行试验的 Shannon 还注意到 对于其他的文本 新 闻报道 科学著作 诗歌 他的受试人往往会猜测错误 因此这时的熵就比较高 第二种计算英语的熵的方法有助于避免导致 Shannon 结果失误的单篇文本的问题 这个方 法使用一个很好的随机模型 在一个很大的语料库上训练这个模型 用它给一个很长的英 语序列指派一个对数概率 计算时使用 Shannon McMillan Breiman 定理 例如 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 测出了英语字母的不等概率独立链的熵 H1之后 人 们又测出了一些印欧语言的熵 到目前为止 英语已经测出了九阶条件熵 俄语已经测出 了十四阶条件熵 下面 我们把法语 意大利语 西班牙语 英语 德语 罗马尼亚语 俄语的不等概率独立链的熵 H1列表比较如下 表 某些语言的熵 H1 冯志伟在上世纪 70 年代 模仿香农对于英语字母的熵的研究 采用手工查频的方法首 次估算出汉字的熵 H1为 9 65 比特 并提出了 汉字容量极限定理 他根据 Zipf 定律 使用数学方法 证明了当统计样本中汉字的容量不大时 包含在一个汉字中的熵 H1随着汉 字容量的增加而增加 当统计样本中的汉字容量达到 12366 字时 包含在一个汉字中的熵 H1就不再增加了 这意味着 在测定汉字的熵 H1的时候 统计样本中汉字的容量是有极限 的 这个极限值就是 12366 字 超出这个极限值 测出的汉字的熵再也不会增加了 在这 12366 个汉字中 有 4000 多个是常用字 4000 多个是次常用字 4000 多个是罕用字 他 认为 这 12366 个汉字可以代表古代和现代文献中汉字的基本面貌 由此他得出结论 从 汉语书面语总体来考虑 在全部汉语书面语中 包括现代汉语和古代汉语 包含在一个 汉字中的熵 H1是 9 65 比特 由于当时冯志伟没有条件使用计算机查频 全部工作都是手 工完成的 精确度难以得到保证 所以 冯志伟始终认为 这只是他的一个极不成熟猜测 1988 年 北京航空学院计算机系刘源使用计算机自动查频计算出汉字的熵 H1为 9 71 比特 1994 年 新加坡国立大学计算机系赖金锭使用计算机计算出汉字的熵 H1为 9 59 比特 他 们的结果与冯志伟原来用手工查频方法猜测的结果是很接近的 1996 年 冯志伟还根据汉语与英语文本对比 首次估算出汉字的极限熵为 4 0462 比 特 2006 年 清华大学计算机系孙茂松 孙帆在大规模语料库 106 107汉字 的基础上 使用 Brown 的