数学之美 第二，第i时刻的接收信号0i只由发送信号si决定（又 称为独立输出假设，即P(o1,02,03,..|s1,s2,s3...)= P(o1|s1)*P(o2|s2)*P(o3|s3)..。 那么我们就可以很容易利用算法Viterbi找出上面式子的 最大值，进而找出要识别的句子s1,s2,s3,·。 满足上述两个假设的模型就叫隐含马尔可夫模型。我们之所 以用“隐含”这个词，是因为状态s1,s2,s3,..是无法直接观 测到的。 隐含马尔可夫模型的应用远不只在语音识别中。在上面的公 式中，如果我们把s1,s2,s3,..当成中文，把o1,o2,03, 当成对应的英文，那么我们就能利用这个模型解决机器翻译问 题；如果我们把o1,o2,03,..当成扫描文字得到的图像特征， 就能利用这个模型解决印刷体和手写体的识别。 P(o1,02,o3,.1s1,s2,s3..)根据应用的不同而又不同 的名称，在语音识别中它被称为“声学模型”(Acoustic Model), 在机器翻译中是“翻译模型”(Translation Model)而在拼写 校正中是“纠错模型”(Correction Model)。而P(s1,s2,s3,..) 就是我们在系列一中提到的语言模型。 在利用隐含马尔可夫模型解决语言处理问题前，先要进行模 型的训练。常用的训练方法由伯姆(Baum)在60年代提出的， 并以他的名字命名。隐含马尔可夫模型在处理语言问题早期的成 功应用是语音识别。七十年代，当时IBM的Fred Jelinek(贾 12
数学之美 第二， 第 i 时刻的接收信号 oi 只由发送信号 si 决定（又 称为独立输出假设, 即 P(o1,o2,o3,...|s1,s2,s3....) = P(o1|s1) * P(o2|s2)*P(o3|s3)...。 那么我们就可以很容易利用算法 Viterbi 找出上面式子的 最大值，进而找出要识别的句子 s1,s2,s3,...。 满足上述两个假设的模型就叫隐含马尔可夫模型。我们之所 以用“隐含”这个词，是因为状态 s1,s2,s3,...是无法直接观 测到的。 隐含马尔可夫模型的应用远不只在语音识别中。在上面的公 式中，如果我们把 s1,s2,s3,...当成中文，把 o1,o2,o3,... 当成对应的英文，那么我们就能利用这个模型解决机器翻译问 题； 如果我们把 o1,o2,o3,...当成扫描文字得到的图像特征， 就能利用这个模型解决印刷体和手写体的识别。 P (o1,o2,o3,...|s1,s2,s3....) 根据应用的不同而又不同 的名称，在语音识别中它被称为“声学模型” (Acoustic Model)， 在机器翻译中是“翻译模型” (Translation Model) 而在拼写 校正中是“纠错模型” (Correction Model)。 而 P (s1,s2,s3,...) 就是我们在系列一中提到的语言模型。 在利用隐含马尔可夫模型解决语言处理问题前，先要进行模 型的训练。 常用的训练方法由伯姆（Baum）在 60 年代提出的， 并以他的名字命名。隐含马尔可夫模型在处理语言问题早期的成 功应用是语音识别。七十年代，当时 IBM 的 Fred Jelinek (贾 12
数学之美 里尼克)和卡内基·梅隆大学的Jim and Janet Baker(贝克夫 妇，李开复的师兄师姐)分别独立地提出用隐含马尔可夫模型来 识别语音，语音识别的错误率相比人工智能和模式匹配等方法降 低了三倍（从30%到10%）。八十年代李开复博士坚持采用隐 含马尔可夫模型的框架，成功地开发了世界上第一个大词汇量 连续语音识别系统Sphinx。. 我最早接触到隐含马尔可夫模型是几乎二十年前的事。那时 在《随机过程》（清华“著名”的一门课）里学到这个模型，但 当时实在想不出它有什么实际用途。几年后，我在清华跟随王作 英教授学习、研究语音识别时，他给了我几十篇文献。我印象 最深的就是贾里尼克和李开复的文章，它们的核心思想就是隐含 马尔可夫模型。复杂的语音识别问题居然能如此简单地被表述、 解决，我由衷地感叹数学模型之妙。 1.4.数学之美系列四一怎样度量信息？ 2006年4月26日上午08：11：00 发表者：吴军，Google研究员 前言：Google一直以“整合全球信息，让人人能获取，使人人 能受益”为使命。那么究竟每一条信息应该怎样度量呢？ 13
数学之美 里尼克) 和卡内基·梅隆大学的 Jim and Janet Baker (贝克夫 妇，李开复的师兄师姐) 分别独立地提出用隐含马尔可夫模型来 识别语音，语音识别的错误率相比人工智能和模式匹配等方法降 低了三倍 (从 30% 到 10%)。 八十年代李开复博士坚持采用隐 含马尔可夫模型的框架， 成功地开发了世界上第一个大词汇量 连续语音识别系统 Sphinx。 我最早接触到隐含马尔可夫模型是几乎二十年前的事。那时 在《随机过程》（清华“著名”的一门课）里学到这个模型，但 当时实在想不出它有什么实际用途。几年后，我在清华跟随王作 英教授学习、研究语音识别时，他给了我几十篇文献。 我印象 最深的就是贾里尼克和李开复的文章，它们的核心思想就是隐含 马尔可夫模型。复杂的语音识别问题居然能如此简单地被表述、 解决，我由衷地感叹数学模型之妙。 1.4. 数学之美系列四 — 怎样度量信息? 2006 年 4 月 26 日 上午 08:11:00 发表者：吴军，Google 研究员 前言: Google 一直以 “整合全球信息，让人人能获取，使人人 能受益” 为使命。那么究竟每一条信息应该怎样度量呢？ 13
数学之美 信息是个很抽象的概念。我们常常说信息很多，或者信息较 少，但却很难说清楚信息到底有多少。比如一本五十万字的中文 书到底有多少信息量。直到1948年，香农提出了“信息熵”(sh ang)的概念，才解决了对信息的量化度量问题。 一条信息的信息量大小和它的不确定性有直接的关系。比如 说，我们要搞清楚一件非常非常不确定的事，或是我们一无所知 的事情，就需要了解大量的信息。相反，如果我们对某件事已经 有了较多的了解，我们不需要太多的信息就能把它搞清楚。所以， 从这个角度，我们可以认为，信息量的度量就等于不确定性的多 少。 那么我们如何量化的度量信息量呢？我们来看一个例子，马 上要举行世界杯赛了。大家都很关心谁会是冠军。假如我错过了 看世界杯，赛后我问一个知道比赛结果的观众“哪支球队是冠 军”？他不愿意直接告诉我，而要让我猜，并且我每猜一次， 他要收一元钱才肯告诉我是否猜对了，那么我需要付给他多少钱 才能知道谁是冠军呢？我可以把球队编上号，从1到32，然 后提问：“冠军的球队在1-16号中吗？”假如他告诉我猜对 了，我会接着问：“冠军在1-8号中吗？”假如他告诉我猜 错了，我自然知道冠军队在9-16中。这样只需要五次，我 就能知道哪支球队是冠军。所以，谁是世界杯冠军这条消息的信 息量只值五块钱。 g
数学之美 信息是个很抽象的概念。我们常常说信息很多，或者信息较 少，但却很难说清楚信息到底有多少。比如一本五十万字的中文 书到底有多少信息量。直到 1948 年，香农提出了“信息熵”(sh āng) 的概念，才解决了对信息的量化度量问题。 一条信息的信息量大小和它的不确定性有直接的关系。比如 说，我们要搞清楚一件非常非常不确定的事，或是我们一无所知 的事情，就需要了解大量的信息。相反，如果我们对某件事已经 有了较多的了解，我们不需要太多的信息就能把它搞清楚。所以， 从这个角度，我们可以认为，信息量的度量就等于不确定性的多 少。 那么我们如何量化的度量信息量呢？我们来看一个例子，马 上要举行世界杯赛了。大家都很关心谁会是冠军。假如我错过了 看世界杯，赛后我问一个知道比赛结果的观众“哪支球队是冠 军”？ 他不愿意直接告诉我， 而要让我猜，并且我每猜一次， 他要收一元钱才肯告诉我是否猜对了，那么我需要付给他多少钱 才能知道谁是冠军呢? 我可以把球队编上号，从 1 到 32， 然 后提问： “冠军的球队在 1-16 号中吗?” 假如他告诉我猜对 了， 我会接着问： “冠军在 1-8 号中吗?” 假如他告诉我猜 错了， 我自然知道冠军队在 9-16 中。 这样只需要五次， 我 就能知道哪支球队是冠军。所以，谁是世界杯冠军这条消息的信 息量只值五块钱。 14
数学之美 当然，香农不是用钱，而是用“比特”(bit)这个概念来 度量信息量。一个比特是一位二进制数，计算机中的一个字节 是八个比特。在上面的例子中，这条消息的信息量是五比特。（如 果有朝一日有六十四个队进入决赛阶段的比赛，那么“谁世界杯 冠军”的信息量就是六比特，因为我们要多猜一次。)读者可 能已经发现，信息量的比特数和所有可能情况的对数函数10g 有关。(10g32=5,10g64=6。) 有些读者此时可能会发现我们实际上可能不需要猜五次就能 猜出谁是冠军，因为象巴西、德国、意大利这样的球队得冠军的 可能性比日本、美国、韩国等队大的多。因此，我们第一次猜测 时不需要把32个球队等分成两个组，而可以把少数几个最可能 的球队分成一组，把其它队分成另一组。然后我们猜冠军球队是 否在那几只热门队中。我们重复这样的过程，根据夺冠概率对剩 下的候选球队分组，直到找到冠军队。这样，我们也许三次或四 次就猜出结果。因此，当每个球队夺冠的可能性（概率）不等时， “谁世界杯冠军”的信息量的信息量比五比特少。香农指出，它 的准确信息量应该是 =-(p1*10gp1+p2*10gp2+··· +p32*10gp32), 其中，p1,p2,···,p32分别是这32个球队夺冠的 概率。香农把它称为“信息熵”(Entropy),一般用符号H表 示，单位是比特。有兴趣的读者可以推算一下当32个球队夺冠 概率相同时，对应的信息熵等于五比特。有数学基础的读者还可 6
数学之美 当然，香农不是用钱，而是用 “比特”（bit）这个概念来 度量信息量。 一个比特是一位二进制数，计算机中的一个字节 是八个比特。在上面的例子中，这条消息的信息量是五比特。（如 果有朝一日有六十四个队进入决赛阶段的比赛，那么“谁世界杯 冠军”的信息量就是六比特，因为我们要多猜一次。） 读者可 能已经发现, 信息量的比特数和所有可能情况的对数函数 log 有关。 (log32=5, log64=6。） 有些读者此时可能会发现我们实际上可能不需要猜五次就能 猜出谁是冠军，因为象巴西、德国、意大利这样的球队得冠军的 可能性比日本、美国、韩国等队大的多。因此，我们第一次猜测 时不需要把 32 个球队等分成两个组，而可以把少数几个最可能 的球队分成一组，把其它队分成另一组。然后我们猜冠军球队是 否在那几只热门队中。我们重复这样的过程，根据夺冠概率对剩 下的候选球队分组，直到找到冠军队。这样，我们也许三次或四 次就猜出结果。因此，当每个球队夺冠的可能性（概率）不等时， “谁世界杯冠军”的信息量的信息量比五比特少。香农指出，它 的准确信息量应该是 = -（p1*log p1 + p2 * log p2 + ．．． ＋p32 *log p32)， 其中，p1，p2 ， ．．．，p32 分别是这 32 个球队夺冠的 概率。香农把它称为“信息熵” (Entropy)，一般用符号 H 表 示，单位是比特。有兴趣的读者可以推算一下当 32 个球队夺冠 概率相同时，对应的信息熵等于五比特。有数学基础的读者还可 15
数学之美 以证明上面公式的值不可能大于五。对于任意一个随机变量X (比如得冠军的球队)，它的熵定义如下： HW=-∑P6网1og影[Pw1 变量的不确定性越大，熵也就越大，把它搞清楚所需要的信 息量也就越大。 有了“熵”这个概念，我们就可以回答本文开始提出的问题， 即一本五十万字的中文书平均有多少信息量。我们知道常用的汉 字（一级二级国标）大约有7000字。假如每个字等概率，那么 我们大约需要13个比特（即13位二进制数)表示一个汉字。 但汉字的使用是不平衡的。实际上，前10%的汉字占文本的95% 以上。因此，即使不考虑上下文的相关性，而只考虑每个汉字的 独立的概率，那么，每个汉字的信息熵大约也只有8-9个比特。 如果我们再考虑上下文相关性，每个汉字的信息熵只有5比特左 右。所以，一本五十万字的中文书，信息量大约是250万比特。 如果用一个好的算法压缩一下，整本书可以存成一个320KB的 文件。如果我们直接用两字节的国标编码存储这本书，大约需要 1MB大小，是压缩文件的三倍。这两个数量的差距，在信息论中 称作“冗余度”(redundancy)。需要指出的是我们这里讲的250 万比特是个平均数，同样长度的书，所含的信息量可以差很多。 如果一本书重复的内容很多，它的信息量就小，冗余度就大。 6
数学之美 以证明上面公式的值不可能大于五。对于任意一个随机变量 X （比如得冠军的球队），它的熵定义如下： 变量的不确定性越大，熵也就越大，把它搞清楚所需要的信 息量也就越大。 有了“熵”这个概念，我们就可以回答本文开始提出的问题， 即一本五十万字的中文书平均有多少信息量。我们知道常用的汉 字（一级二级国标）大约有 7000 字。假如每个字等概率，那么 我们大约需要 13 个比特（即 13 位二进制数）表示一个汉字。 但汉字的使用是不平衡的。实际上，前 10% 的汉字占文本的 95% 以上。因此，即使不考虑上下文的相关性，而只考虑每个汉字的 独立的概率，那么，每个汉字的信息熵大约也只有 8-9 个比特。 如果我们再考虑上下文相关性，每个汉字的信息熵只有 5 比特左 右。所以，一本五十万字的中文书，信息量大约是 250 万比特。 如果用一个好的算法压缩一下，整本书可以存成一个 320KB 的 文件。如果我们直接用两字节的国标编码存储这本书，大约需要 1MB 大小，是压缩文件的三倍。这两个数量的差距，在信息论中 称作“冗余度”（redundancy)。 需要指出的是我们这里讲的 250 万比特是个平均数，同样长度的书，所含的信息量可以差很多。 如果一本书重复的内容很多，它的信息量就小，冗余度就大。 16