二十、自然语言处理的教父 马库斯
2007 年 4 月 13 日 下午 07:03:00
发表者：Google 研究员，吴军
我 们在前面的系列中介绍和提到了一些年轻有为的科学家，迈克尔·柯林斯， 艾里克·布莱尔，大卫·雅让斯基，拉纳帕提等等，他们都出自宾夕法尼亚计算 机系米奇 ·马库斯(Mitch Marcus)名下。就像许多武侠小说中描写的，弟子都 成了各派的掌门，师傅一定了不得。的确，马库斯虽然作为第一作者发表的论文 并不多，但是从很多角度 上讲，他可以说是自然语言处理领域的教父。
马库斯教授长期当任宾夕法尼亚大学计算机系主任，直到他在几年前从 AT&T 找 到皮耶尔替代他为止。作为一个管理者，马库斯显示出在自然处理和计算机科学 方面的卓识的远见。在指导博士生时，马库斯发现语料库在自然语言处理中的重 要 性。马库斯呕心沥血，花了十几年工夫建立了一系列标准的语料库，提供给 全世界的学者使用。这套被称为 LDC 的语料库，是当今全世界自然语言处理的 所有学者都使用的工具。我们在以前的系列中讲到，当今的自然语言处理几乎都 是使用给予统计的方法。要做统计，就需要 大量有代表性的数据。利用这些数 据开发一个自然语言处理系统的过程，可以统称为训练。比如，我们要训练一个 汉语分词系统，我们需要一些已经分好词的中文句 子。当然这些句子需要有代 表性。如果想知道一个分词系统的准确性，我们也需要一些人工分好词的句子进 行测试。这些人工处理好的文字数据库，成为语料库 (corpus)。如果每个研究 室都人工建立几个语料库，不仅浪费时间精力，而且发表文章时，数据没有可比 性。因此，马库斯想到了建立一系列标准的语料库 为全世界的学者用。他利用 自己的影响力让美国自然科学基金会和 DARPA 出钱立项，联络的多所大学和研 究机构，建立的数百个标准的语料库。其中最著名的是 PennTree
Bank 的语料库。PennTree Bank 覆盖多种语言（包括中文）。每一种语言，它 有几十万到几百万字的有代表性的句子，每个句子都有的词性标注，语法分析树 等等。LDC 语料库如今已成为全世界自然语言处理科学家共用的数据库。如今， 在自然语言处理方面发表论文，几乎都要提供基于 LDC 语料库的测试结果。
马 库斯给予他的博士生研究自己感兴趣的课题的自由，这是他之所以桃李满天 下的原因。马库斯对几乎所有的自然语言处理领域有独到的见解。和许多教授让 博士生去 做他拿到基金的项目，马库斯让博士生提出自己有兴趣的课题，或者 用他已有的经费支持学生，或者为他们的项目区申请经费。马库斯高屋建瓴，能 够很快的判断一 个研究方向是否正确，省去了博士生很多 try-and-error 的时 间。因此他的学生有些很快地拿到的博士学位。
作为系主任，马库 斯在专业设置方面显示出卓识的远见。我有幸和他在同一个 校务顾问委员会任职，一起讨论计算机系的研究方向。马库斯在几年前互联网很 热门、很多大学开始互联 网研究时，看到 bioinformatics (生物信息学）的重 要性，在宾夕法利亚大学设置这个专业，并且在其他大学还没有意识到时，开始
-----------------------------------------------------Page 49-----------------------------------------------------
招聘这方面的教授。马库斯还建议一些相关领域的教授，包括后 来的系主任皮 耶尔把一部分精力转到生物信息学方面。马库斯同时向他担任顾问的其他一些大 学提出同样的建议。等到网络泡沫破裂以后，很多大学的计算机系开始 向生物 信息学转向，但是发现已经很难找到这些方面好的教授了。我觉得，当今中国的 大学，最需要的就是马库斯这样卓有远见的管理者。
过几天我又要和马库斯一起开顾问委员会的会议了，不知道这次他对计算机科学 的发展有什么见解。
-----------------------------------------------------Page 50-----------------------------------------------------
二十一、 布隆过滤器（Bloom Filter）
2007 年 7 月 3 日 上午 09:35:00
发表者：Google（谷歌）研究员 吴军
在 日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一 个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是 要判断它 是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑 名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合 中全部的元素存在计算机中，遇到一个新 元素时，将它和集合中的元素直接比 较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的 好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是 当集合巨大时，哈希表存储效率低的问题就显现出来 了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤 来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾 邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有 几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用 哈希表，每存储一亿 个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的
具体办法是将每一个
email 地 址 对 应 成 一 个 八 字 节 的 信 息 指 纹
m/2006/08/ml ， 然后将这些信息指纹存入哈 希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十 六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十 亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法 存储的。
今天，我们介绍一种称作布隆过滤器的数学工具，它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。
布隆过滤器是由巴顿.布隆于一九七零年提出的。它实际上是一个很长的二进制 向量和一系列随机映射函数。我们通过上面的例子来说明起工作原理。
假 定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特）， 即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮 件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指 纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全 部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这 些 email 地址的布隆过滤器就建成了。（见下图）
-----------------------------------------------------Page 51-----------------------------------------------------
现 在，让我们看看如何用布隆过滤器来检测一个可疑的电子邮件地址 Y 是否在 黑名单中。我们用相同的八个随机数产生器（F1, F2, ..., F8）对这个地址产 生八个信息指纹 s1,s2,...,s8，然后将这八个指纹对应到布隆过滤器的八个二 进制位，分别是 t1,t2,...,t8。如果 Y 在黑名单中，显然，t1,t2,..,t8 对应 的八个二进制一定是一。这样在遇到任何在黑名单中的电子邮件地址，我们都能 准确地发现。
布隆过滤器决不会漏掉任何一个在黑名单中的可 疑地址。但是，它有一条不足 之处。也就是它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名 单中，因为有可能某个好的邮件地址正巧对应个八个都 被设置成一的二进制位。 好在这种可能性很小。我们把它称为误识概率。在上面的例子中，误识概率在万 分之一以下。
布隆过滤器的好处在于快速，省空间。但是有一定的误识别率。常见的补救办法 是在建立一个小的白名单，存储那些可能别误判的邮件地址。
-----------------------------------------------------Page 52-----------------------------------------------------
二十二、 谈谈密码学的数学原理
2007 年 9 月 13 日 下午 09:00:00
发表者：Google（谷歌）研究员 吴军
前一阵子看了电视剧《暗算》，蛮喜欢它的构思和里面的表演。其中有一个故事 提到了密码学，故事本身不错，但是有点故弄玄虚。不过有一点是对的，就是当 今的密码学是以数学为基础的。（没有看过暗算的读者可以看一下介绍， 因为我们后面要多次提到这部电视剧。）
密码学的历史大致可以推早到两千年前，相传名将凯撒为了防止敌方截获情报， 用密码传送情报。凯撒的做法很简单，就是对二十几个罗马字母建立一张对应表， 比如说
这 样，如果不知道密码本，即使截获一段信息也看不懂，比如收到一个的消息 是 EBKTBP，那么在敌人看来是毫无意义的字，通过密码本解破出来就是 CAESAR 一词，即凯撒的名字。这种编码方法史称凯撒大帝。当然，学过信息论的人都知 道，只要多截获一些情报，统计一下字母的频率，就可以解破出这种密码。柯蓝 道尔 在他的“福尔摩斯探案集”中“跳舞的小人”的故事里已经介绍了这种小 技巧。在很长时间里，人们试图找到一些好的编码方法使得解密者无法从密码中 统计出明码 的统计信息，但是，基本上靠经验。有经验的编码者会把常用的词 对应成多个密码， 使得破译者很难统计出任何规律。比如，如果将汉语中的 “是”一词对应于唯一一个编码 0543，那么破译者就会发现 0543 出现的特别 多。但如果将它对应成十个密码 0543，3737，2947 等等，每次随机的挑一个使 用，每个密码出现的次数就不会太多，而且破译者也无从知道这些密码其实对应 一个字。这里面虽然包含着朴素的概率论的原理，但是并 不科学化。另外，好 的密码必须做到不能根据已知的明文和密文的对应推断出新的密文的内容。历史 上有很多在这方面设计得不周到的密码的例子。在第二次世界大 战中，日本军 方的密码设计就很成问题。美军破获了日本很多密码。在中途岛海战前，美军截 获的日军密电经常出现 AF 这样一个地名，应该是太平洋的某个岛屿，但是美军
-----------------------------------------------------Page 53-----------------------------------------------------
无从知道是哪个。于是，美军就逐个发表自己控制的每个岛屿上的假新闻。当美 军发出“中途岛供水系统坏了” 这条假新闻后，从截获的日军情报中又看到 AF 供水出来问题的电文，美军就断定中途岛就是 AF。事实证明判断正确，美军在 那里成功地伏击了日本主力舰队。
事实上，在第二次世界大战中，很多顶尖的科学家包括提出信息论的香农都在 为 美军情报部门工作，而信息论实际上就是情报学的直接产物。香农提出信息论后， 为密码学的发展带来了新气象。根据信息论，密码的最高境界是使得敌人在截获 密码后，对我方的所知没有任何增加，用信息论的专业术语讲，就是信息量没有 增加。一般来讲，当密码之间分布均匀并且统计独立时，提供的信息最少。均匀 分布 使得敌人无从统计，而统计独立能保证敌人即使看到一段密码和明码后， 不能破译另一段密码。这也是《暗算》里传统的破译员老陈破译的一份密报后， 但无法推广 的原因，而数学家黄依依预见到了这个结果，因为她知道敌人新的 密码系统编出的密文是统计独立的。有了信息论后，密码的设计就有了理论基础， 现在通用的公开 密钥的方法，包括《暗算》里的“光复一号”密码，就是基于 这个理论。
公开密钥的原理其实很简单，我们以给上面的单词 Caesar 加解密来说明它的原 理。我们先把它变成一组数，比如它的 Ascii 代码 X=099097101115097114（每 三位代表一个字母）做明码。现在我们来设计一个密码系统，对这个明码加密。
1，找两个很大的素数（质数）P 和 Q，越大越好，比如 100 位长的, 然后计算 它们的乘积 N=P×Q，M=（P-1）×（Q-1）。
2，找一个和 M 互素的整数 E，也就是说 M 和 E 除了 1 以外没有公约数。
3，找一个整数 D，使得 E×D 除以 M 余 1，即 E×D mod M = 1。
现在，世界上先进的、最常用的密码系统就设计好了，其中 E 是公钥谁都可以 用来加密，D 是私钥用于解密，一定要自己保存好。乘积 N 是公开的，即使敌 人知道了也没关系。
现在，我们用下面的公式对 X 加密，得到密码 Y。
好了，现在没有密钥 D，神仙也无法从 Y 中恢复 X。如果知道 D，根据费尔马 小定理，则只要按下面的公式就可以轻而易举地从 Y 中得到 X。
这个过程大致可以概况如下：
-----------------------------------------------------Page 54-----------------------------------------------------
公开密钥的好处有：
1.简单。
2. 可靠。公开密钥方法保证产生的密文是统计独立而分布均匀的。也就是说， 不论给出多少份明文和对应的密文，也无法根据已知的明文和密文的对应来破译 下一份密 文。更重要的是 N,E 可以公开给任何人加密用，但是只有掌握密钥 D 的人才可以解密, 即使加密者自己也是无法解密的。这样，即使加密者被抓住叛 变了，整套密码系统仍然是安全的。（而凯撒大帝的加密方法有一个知道密码本 的人泄密，整个密码系 统就公开了。）
3.灵活，可以产生很多的公开密钥E和私钥D的组合给不同的加密者。
最后让我们看看破解这种密码的难度。 首先，要声明，世界上没有永远破不了 的密码，关键是它能有多长时间的有效期。要破公开密钥的加密方式，至今的研 究结果表明最好的办法还是对大字 N 进行因数分解，即通过 N 反过来找到 P 和 Q，这样密码就被破了。而找 P 和 Q 目前只有用计算机把所有的数字试一遍 这种笨办法。这实际上是在拼计算机的速度，这也就是为什么 P 和 Q 都需要非 常大。一种加密方法只有保证 50 年计算机破不了也就可以满意了。前几年破解 的 RSA-158 密码是这样因数分解的
395058745832651445264197678006144819960207764603049364541393760515793 556265294
506836097278424682195350935443058704902519956553357102097992264849779 49442955603 =
338849583746672139436839320467218152281583036860499304808492584055528 1177
×1165882340667125990314837655838327081813101225814639260043952099413 1344334162924536139
现 在，让我们回到《暗算》中，黄依依第一次找的结果经过一系列计算发现无 法归零，也就是说除不尽，我猜她可能试图将一个大数 N 做分解，没成功。第 二次计算的结果是归零了，说明她找到的 N=P×Q 的分解方法。当然，这件事能 不能用算盘完成，我就不知道了，但我觉得比较夸张。另外我对该电视剧还有一
-----------------------------------------------------Page 55-----------------------------------------------------
个搞不懂的问题就是里面提到的“光复一号”密码的误 差问题。一个密码是不 能有误差的，否则就是有的密钥也无法解码了。我想可能是指在构造密码时，P 和 Q 之一没找对，其中一个（甚至两个都）不小心找成了合数，这时密码的保密性 就差了很多。如果谁知道电视剧里面讲的“误差”是指什么请告诉我。另外，电 视剧里 提到冯 · 诺依曼，说他是现代密码学的祖宗，我想是弄错了，应该是香农。 冯 · 诺依曼的贡献在发明计算机和提出博弈论（game theory）。
不管怎么样，我们今天用的所谓最可靠的加密方法的数学原理其实就这么简单， 一点也不神秘，无非是找几个大素数做一些乘除和乘方运算就可以了。
-----------------------------------------------------Page 56-----------------------------------------------------
二十三、 输入一个汉字需要敲多少个键 — 谈谈香农第一定律
2007 年 12 月 3 日 上午 10:05:00
发表者：Google（谷歌）研究员 吴军
今天各种汉字输入法已经很成熟了，随便挑出一种主要的输入法比十几年前最好 的输入法都要快、要准。现在抛开具体的输入法，从理论上分析一下，输入汉字 到底能有多快。
我 们假定常用的汉字在二级国标里面，一共有 6700 个作用的汉字。如果不考 虑汉字频率的分布，用键盘上的 26 个字母对汉字编码，两个字母的组合只能对 676 个汉字编码，对 6700 个汉字编码需要用三个字母的组合，即编码长度为三。 当然，聪明的读者马上发现了我们可以对常见的字用较短的编码对不常见的字用 较长的编码，这样平均起来每 个汉字的编码长度可以缩短。我们假定每一个汉 字的频率是
p1, p2, p3, ..., p6700 它们编码的长度是
L1, L2, L3, ..., L6700 那么，平均编码长度是
p1×L1 + p2×L2 + ... + p6700×L6700
香 农第一定理指出：这个编码的长度的最小值是汉字的信息熵，也就是说任何 输入方面不可能突破信息熵给定的极限。当然，香农第一定理是针对所有编码的， 不但是 汉字输入编码的。这里需要指出的是，如果我们将输入法的字库从二级 国标扩展到更大的字库 GBK，由于后面不常见的字频率较短，平均编码长度比针 对 国 标 的 大 不 了 多 少 。 让 我 们 回 忆 一 下 汉 字 的 信 息 熵 （ 见 m/2006/04/4.html ）， H = -p1 * log p1 - ... - p6700 log p6700。
我们如果对每一个字进行统计，而且不考虑上下文相关性，大致可以估算出它的 值在十比特以内，当然这取决于用什么语料库来做估计。如果我们假定输入法只 能用 26 个字母输入，那么每个字母可以代表 log26=
4.7 比特的信息，也就是说，输入一个汉字平均需要敲 10/4.7= 2.1 次键。
聪 明的读者也许一经发现，如果我们把汉字组成词，再以词为单位统计信息熵， 那么，每个汉字的平均信息熵将会减少。这样，平均输入一个字可以少敲零点几 次键 盘。不考虑词的上下文相关性，以词为单位统计，汉字的信息熵大约是 8 比特作用，也就是说，以词为单位输入一个汉字平均只需要敲 8/4.7=1.7 次键。 这就是现在所有输入法都是基于词输入的内在原因。当然，如果我们再考虑上下 文 的 相 关 性 ， 对 汉 语 建 立 一 个 基 于 词 的 统 计 语 言 模 型 （ 见 m/2006/04/ml ），我们可以将每 个汉字的信息熵降到 6 比特作用，这时，输入一个汉字只要敲 6/4.7=1.3 次键。 如果一种输入方法能做到这一点，那么汉字的输入已经比英文快的多了。
-----------------------------------------------------Page 57-----------------------------------------------------
但 是，事实上没有一种输入方法接近这个效率。这里面主要有两个原因。首先， 要接近信息论给的这个极限，就要对汉字的词组根据其词频进行特殊编码。事实 上像王 码这类的输入方法就是这么做到，只不过它们第一没有对词组统一编码， 第二没有有效的语言模型。这种编码方法理论上讲有效，实际上不实用。原因有 两个，第 一，很难学；第二，从认知科学的角度上讲，人一心无二用，人们在 没有稿子边想边写的情况下不太可能在回忆每个词复杂的编码的同时又不中断 思维。我们过去在 研究语言识别时做过很多用户测试，发现使用各种复杂编码 输入法的人在脱稿打字时的速度只有他在看稿打字时的一半到四分之一。因此， 虽然每个字平均敲键次数 少，但是打键盘的速度也慢了很多，总的并不快。这 也就是为什么基于拼音的简单输入法占统治地位的原因。事实上，汉语全拼的平 均长度为 2.98，只要基于拼音的输入法能利用上下文彻底解决一音多字的问题， 平均每个汉字输入的敲键次数应该在三次左右，每分钟输入 100 个字完全有可 能达到。
另外一个不容易达到信息论极限的输入速度的原因在于，这个理论值是根据一个 很多的语言模型计算出来的。在产品中，我 们不可能占有用户太多的内存空间， 因此各种输入方法提供给用户的是一个压缩的很厉害的语音模型，而有的输入方 法为了减小内存占用，根本没有语言模型。拼音 输入法的好坏关键在准确而有 效的语言模型。
另一方面，由于现有输入方法离信息论给的极限还有很大的差距，汉语输入方法 可提升的空间很大，会有越来越好用的输入方法不断涌现。当然，输入速度只是 输入法的一项而不是唯一的衡量标准。我们也会努力把谷歌的输入法做的越来越 好。大家不妨先试试现在的版本， m/pinyin/ ，半年后 再看看我们有没有提高。
-----------------------------------------------------Page 58-----------------------------------------------------
