接下来的问题就是如何估计 P (wi|wi-1)。现在有了大量机读文本后，这个问题变得很简单，只要数一数这对词（wi-1,wi) 在统计的文本中出现了多少次，以及 wi-1 本身在同样的文本中前后相邻出现了多少次，然后用两个数一除就可以了,P(wi|wi-1) = P(wi-1,wi)/ P (wi-1)。
也许很多人不相信用这么简单的数学模型能解决复杂的语音识别、机器翻译等问题。其实不光是常人，就连很多语言学家都曾质疑过这种方法的有效性，但事实证明，统计语言模型比任何已知的借助某种规则的解决方法都有效。比如在 Google 的[url=http://www.google.com/language_tools?hl=zh-CN]中英文自动翻译中，用的最重要的就是这个统计语言模型。去年美国标准局(NIST) 对所有的机器翻译系统进行了评测，Google 的系统是不仅是全世界最好的，而且高出所有基于规则的系统很多。
也许你想不到，中文分词的方法也被应用到英语处理，主要是手写体识别中。因为在识别手写体时，单词之间的空格就不很清楚了。中文分词方法可以帮助判别英语单词的边界。其实，语言处理的许多数学方法通用的和具体的语言无关。在 Google 内，我们在设计语言处理的算法时，都会考虑它是否能很容易地适用于各种自然语言。这样，我们才能有效地支持上百种语言的搜索。
3. 郭进
[url=http://acl.ldc.upenn.edu/J/J97/J97-4004.pdf]Critical Tokenization and its Properties
http://acl.ldc.upenn.edu/J/J97/J97-4004.pdf
4. 孙茂松
[url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=980775]Chinese word segmentation without using lexicon and hand-crafted training data
[url=http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=980775]http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=980775作者: 翔子 时间: 2012-5-14 16:51 标题: 数学之美系列三：隐含马尔可夫模型在语言处理中的应用 前言：隐含马尔可夫模型是一个数学模型，到目前为之，它一直被认为是实现快速精确的语音识别系统的最成功的方法。复杂的语音识别问题通过隐含马尔可夫模型能非常简单地被表述、解决，让我不由由衷地感叹数学模型之妙。
[url=http://searchwhatis.techtarget.com.cn/searchwhatis/402/1946902.shtml]布尔（George Boole) 是十九世纪英国一位小学数学老师。他生前没有人认为他是数学家。布尔在工作之余，喜欢阅读数学论著、思考数学问题。1854 年“[url=http://www.nxipo.gov.cn/file/page_5.jsp?code=000400000600004]思维规律”（An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities）一书，第一次向人们展示了如何用数学的方法解决逻辑问题。
对于互联网的搜索引擎来讲，每一个网页就是一个文献。互联网的网页数量是巨大的，网络中所用的词也非常非常多。因此这个索引是巨大的，在万亿字节这个量级。早期的搜索引擎（比如 Alta Vista 以前的所有搜索引擎），由于受计算机速度和容量的限制，只能对重要的关键的主题词建立索引。至今很多学术杂志还要求作者提供 3-5 个关键词。这样所有不常见的词和太常见的虚词就找不到了。现在，为了保证对任何搜索都能提供相关的网页，所有的搜索引擎都是对所有的词进行索引。为了网页排名方便，索引中还需存有大量附加信息，诸如每个词出现的位置、次数等等。因此，整个索引就变得非常之大，以至于不可能用一台计算机存下。大家普遍的做法就是根据网页的序号将索引分成很多份（Shards)，分别存储在不同的服务器中。每当接受一个查询时，这个查询就被分送到许许多多服务器中，这些服务器同时并行处理用户请求，并把结果送到主服务器进行合并处理，最后将结果返回给用户。
“互信息”是信息熵的引申概念，它是对两个随机事件相关性的度量。比如说今天随机事件北京下雨和随机变量空气湿度的相关性就很大，但是和姚明所在的休斯敦火箭队是否能赢公牛队几乎无关。互信息就是用来量化度量这种相关性的。在自然语言处理中，经常要度量一些语言现象的相关性。比如在机器翻译中，最难的问题是词义的二义性（歧义性）问题。比如 Bush 一词可以是美国总统的名字，也可以是灌木丛。（有一个笑话，美国上届总统候选人凯里 Kerry 的名字被一些机器翻译系统翻译成了"爱尔兰的小母牛"，Kerry 在英语中另外一个意思。）那么如何正确地翻译这个词呢？人们很容易想到要用语法、要分析语句等等。其实，至今为止，没有一种语法能很好解决这个问题，真正实用的方法是使用互信息。具体的解决办法大致如下：首先从大量文本中找出和总统布什一起出现的互信息最大的一些词，比如总统、美国、国会、华盛顿等等，当然，再用同样的方法找出和灌木丛一起出现的互信息最大的词，比如土壤、植物、野生等等。有了这两组词，在翻译 Bush 时，看看上下文中哪类相关的词多就可以了。这种方法最初是由吉尔(Gale)，丘奇(Church)和雅让斯基(Yarowsky)提出的。
贾里尼克从麻省理工获得博士学位后，在哈佛大学教了一年书，然后到康乃尔大学任教。他之所以选择康乃尔大学，是因为找工作时和那里的一位语言学家谈得颇为投机。当时那位教授表示愿意和贾里尼克在利用信息论解决语言问题上合作。但是，等贾里尼克到康乃尔以后，那位教授表示对语言学在没有兴趣而转向写歌剧了。贾里尼克对语言学家的坏印象从此开始。加上后来他在 IBM 时发现语言学家们嘴上头头是道，干起活来高不成低不就，对语言学家从此深恶痛绝。他甚至说："我每开除一名语言学家，我的语音识别系统错误率就降低一个百分点。" 这句话后来在业界广为流传，为每一个搞语音识别和语言处理的人所熟知。
贾里尼克治学极为严谨，对学生要求也极严。他淘汰学生的比例极高，即使留下来的，毕业时间也极长。但是，另一方面，贾里尼克也千方百计利用自己的影响力为学生的学习和事业创造方便。贾里尼克为组里的每一位学生提供从进组第一天到离开组最后一天全部的学费和生活费。他还为每一位学生联系实习机会，并保证每位学生在博士生阶段至少在大公司实习一次。从他那里拿到博士学位的学生，全部任职于著名实验室，比如IBM, 微软，AT&T 和 Google 的实验室。为了提高外国人的英语水平，贾里尼克用自己的经费为他们请私人英语教师。
从加入 Google 的第一天，我就开始了和辛格长期而愉快的合作，而他一直是我的一个良师益友。辛格、Matt Cutts（中国一些用户误认为他是联邦调查局特工，当然他不是）、马丁和我四个人当时一同研究和解决网络搜索中的作弊问题（Spam)。我们需要建一个分类器，我以前一直在学术界工作和学习，比较倾向找一个很漂亮的解决方案。我设计了一个很完美的分类器，大约要花三个月到半年时间来实现和训练，而辛格认为找个简单有效的办法就行了。我们于是尽可能简化问题，一、两个月就把作弊的数量减少了一半。当时我们和公司工程副总裁罗森打了个赌，如果我们能减少 40% 的作弊，他就送我们四个家庭去夏威夷度假，后来罗森真的履约了。这个分类器设计得非常小巧（只用很小的内存），而且非常快速（几台服务器就能处理全球搜索的分类），至今运行得很好。
后来我和辛格一起又完成了许多项目，包括对中、日、韩文排名算法的改进。每一次，辛格总是坚持找简单有效的解决方案。这种做法在 Google 这个人才济济的公司常常招人反对，因为很多资深的工程师怀疑这些简单方法的有效性。不少人试图用精确而复杂的办法对辛格的设计的各种“阿卡47” 进行改进，后来发现几乎所有时候，辛格的简单方法都接近最优化的解决方案，而且还快得多。另一条选择简单方案的原因是这样设计的系统很容易查错（debug)。
辛格非常鼓励年轻人不怕失败，大胆尝试。一次一位刚毕业不久的工程师因为把带有错误的程序推出到 Google 的服务器上而惶惶不可终日。辛格安慰她讲，你知道，我在 Google 犯的最大一次错误是曾经将所有网页的相关性得分全部变成了零，于是所有搜索的结果全部是随机的了。这位工程师后来为 Google 开发了很多好的产品。
辛格在 AT&T 时确立了他在学术界的地位，但是，他不是一个满足于做实验写论文的人，于是他离开了实验室来到了当时只有百、十人的 Google。在这里，他得以施展才智，重写了 Google 的排名算法，并且一直在负责改进它。辛格因为舍不得放下两个孩子，很少参加各种会议，但是他仍然被学术界公认为是当今最权威的网络搜索专家。2005年，辛格作为杰出校友被请回母校康乃尔大学计算机系在 40 年系庆上作报告，获得这一殊荣的还有大名鼎鼎的美国工程院院士，计算机独立磁盘冗余阵列（RAID)的发明人凯茨(Randy Katz) 教授。
我们在图论和网络爬虫一文中提到，为了防止重复下载同一个网页，我们需要在哈希表中纪录已经访问过的网址（URL)。但是在哈希表中以字符串的形式直接存储网址，既费内存空间，又浪费查找时间。现在的网址一般都较长，比如，如果在 Google 或者百度在查找数学之美，对应的网址长度在一百个字符以上。下面是百度的链接
柯林斯毕业后，在 AT&T 实验室度过了三年快乐的时光。在那里柯林斯完成了许多世界一流的研究工作诸如隐含马尔科夫模型的区别性训练方法，卷积核在自然语言处理中的应用等等。三年后，AT&T 停止了自然语言处理方面的研究，柯林斯幸运地在 MIT 找到了教职。在 MIT 的短短几年间，柯林斯多次在国际会议上获得最佳论文奖。相比其他同行，这种成就是独一无二的。柯林斯的特点就是把事情做到极致。如果说有人喜欢“繁琐哲学”，柯林斯就是一个。
布莱尔就靠这么简单的方法，在很多自然语言研究领域，得到了几乎最好的结果。由于他的方法再简单不过了，许许多多的人都跟着学。布莱尔可以算是我在美国的第一个业师，我们俩就用这么简单的方法作词性标注 (part of speech tagging)，也就是把句子中的词标成名词动词，很多年内无人能超越。（最后超越我们的是后来加入 Google 的一名荷兰工程师，用的是同样的方法，但是做得细致很多）布莱尔离开学术界后去了微软研究院。在那里的第一年，他一人一年完成的工作比组里其他所有人许多年做的工作的总和还多。后来，布莱尔又加入了一个新的组，依然是高产科学家。据说，他的工作真正被微软重视要感谢 Google，因为有了 Google，微软才对他从人力物力上给于了巨大的支持，使得布莱尔成为微软搜索研究的领军人物之一。在研究方面，布莱尔有时不一定能马上找到应该怎么做，但是能马上否定掉一种不可能的方案。这和他追求简单的研究方法有关，他能在短时间内大致摸清每种方法的好坏。
[我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里，这样可以降低风险。在信息处理中，这个原理同样适用。在数学上，这个原理称为[url=http://www.wljx.sdu.edu.cn/wlwz/reading/r_infor/shang7.htm]最大熵原理(the maximum entropy principle)。这是一个非常有意思的题目，但是把它讲清楚要用两个系列的篇幅。]
八十年代，很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面的改进，提出了改进迭代算法 IIS（improved iterative scaling）。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此，在当时也只有 IBM 有条件是用最大熵模型。
由于最大熵模型在数学上十分完美，对科学家们有很大的诱惑力，因此不少研究者试图把自己的问题用一个类似最大熵的近似模型去套。谁知这一近似，最大熵模型就变得不完美了，结果可想而知，比打补丁的凑合的方法也好不了多少。于是，不少热心人又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的，是宾夕法尼亚大学马库斯的另一个高徒原 IBM 现微软的研究员拉纳帕提(Adwait Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似，而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题，比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词等）、句子成分（主谓宾）通过最大熵模型结合起来，做出了当时世界上最好的词性标识系统和句法分析器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统，至今仍然是使用单一方法最好的系统。科学家们从拉纳帕提的成就中，又看到了用最大熵模型解决复杂的文字信息处理的希望。
但是，最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型的计算量。终于有一天，我对我的导师说，我发现一种数学变换，可以将大部分最大熵模型的训练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时，他没有找出我的推导中的任何破绽，接着他又回去想了两天，然后告诉我我的算法是对的。从此，我们就建造了一些很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以后，为了训练一个包含上下文信息，主题信息和语法信息的文法模型(language model)，我并行使用了 20 台当时最快的 SUN 工作站，仍然计算了三个月。由此可见最大熵模型的复杂的一面。最大熵模型快速算法的实现很复杂，到今天为止，世界上能有效实现这些算法的人也不到一百人。有兴趣实现一个最大熵模型的读者可以阅读[url=http://www.cs.jhu.edu/~junwu/publications/ch3.pdf]我的论文。
在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（Singular Value Decomposition，简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先，我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章，每一列对应一个词。
在上面的图中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 个词在第 i 篇文章中出现的加权词频（比如，[url=http://www.kuqin.com/math/20071204/2783.html]TF/IDF)。读者可能已经注意到了，这个矩阵非常大，有一百万乘以五十万，即五千亿个元素。
现在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中的许多概念，比如矩阵的特征值等等，以及数值分析的各种算法就统统用上了。在很长时间内，奇异值分解都无法并行处理。（虽然 Google 早就有了MapReduce 等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。）最近，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，我认为这是 Google 中国对世界的一个贡献。
这样，如果不知道密码本，即使截获一段信息也看不懂，比如收到一个的消息是 EBKTBP，那么在敌人看来是毫无意义的字，通过密码本解破出来就是 CAESAR 一词，即凯撒的名字。这种编码方法史称凯撒大帝。当然，学过信息论的人都知道，只要多截获一些情报，统计一下字母的频率，就可以解破出这种密码。柯蓝道尔在他的“福尔摩斯探案集”中“跳舞的小人”的故事里已经介绍了这种小技巧。在很长时间里，人们试图找到一些好的编码方法使得解密者无法从密码中统计出明码的统计信息，但是，基本上靠经验。有经验的编码者会把常用的词对应成多个密码， 使得破译者很难统计出任何规律。比如，如果将汉语中的“是”一词对应于唯一一个编码 0543，那么破译者就会发现 0543 出现的特别多。但如果将它对应成十个密码 0543，3737，2947 等等，每次随机的挑一个使用，每个密码出现的次数就不会太多，而且破译者也无从知道这些密码其实对应一个字。这里面虽然包含着朴素的概率论的原理，但是并不科学化。另外，好的密码必须做到不能根据已知的明文和密文的对应推断出新的密文的内容。历史上有很多在这方面设计得不周到的密码的例子。在第二次世界大战中，日本军方的密码设计就很成问题。美军破获了日本很多密码。在中途岛海战前，美军截获的日军密电经常出现 AF 这样一个地名，应该是太平洋的某个岛屿，但是美军无从知道是哪个。于是，美军就逐个发表自己控制的每个岛屿上的假新闻。当美军发出“中途岛供水系统坏了”这条假新闻后，从截获的日军情报中又看到 AF 供水出来问题的电文，美军就断定中途岛就是 AF。事实证明判断正确，美军在那里成功地伏击了日本主力舰队。
2.可靠。公开密钥方法保证产生的密文是统计独立而分布均匀的。也就是说，不论给出多少份明文和对应的密文，也无法根据已知的明文和密文的对应来破译下一份密文。更重要的是 N,E 可以公开给任何人加密用，但是只有掌握密钥 D 的人才可以解密, 即使加密者自己也是无法解密的。这样，即使加密者被抓住叛变了，整套密码系统仍然是安全的。（而凯撒大帝的加密方法有一个知道密码本的人泄密，整个密码系统就公开了。）
3.灵活，可以产生很多的公开密钥E和私钥D的组合给不同的加密者。
最后让我们看看破解这种密码的难度。首先，要声明，世界上没有永远破不了的密码，关键是它能有多长时间的有效期。要破公开密钥的加密方式，至今的研究结果表明最好的办法还是对大字 N 进行因数分解，即通过 N 反过来找到 P 和 Q，这样密码就被破了。而找 P 和 Q 目前只有用计算机把所有的数字试一遍这种笨办法。这实际上是在拼计算机的速度，这也就是为什么 P 和 Q 都需要非常大。一种加密方法只有保证 50 年计算机破不了也就可以满意了。前几年破解的 RSA-158 密码是这样因数分解的
