2801# 数学之美-Statistical Language Models

Google 的使命是 "整合全球信息，让人人能获取，使人人能受益"，研究如何让机器对信息、语言做最好的处理和理解。乔姆斯基提出 “形式语言” 以后，人们更坚定了利用语法规则的办法进行文字处理的信念。

此前，数学家兼信息论的祖师爷就提出了用数学的办法处理自然语言的想法（浪潮之巅里对此人印象极为深刻），当时的计算机条件根本无法满足大量信息处理的需要。

还有一位首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师Fred Jelinek，当时贾里尼克在 IBM 公司做学术休假，领导了一批杰出的科学家利用大型计算机来处理人类语言问题。统计语言模型就是在那个时候提出的。

自然语言处理（NLP：Natural Language Process）的领域机器翻译可以包括：语音识别、印刷体、手写体识别、拼写纠错、汉字输入、文献查询。文中没有提及的有情感分析（Sentiment Analysis）和机器翻译（美国标准局NIST对所有的机器翻译系统进行了评测，Google 的系统是不仅是全世界最好的，而且高出所有基于规则的系统很多。
）。

我们都需要知道一个文字序列是否能构成一个大家能理解的句子，显示给使用者。对这个问题，我们可以用一个简单的统计模型来解决这个问题。此处作者用条件概率公式解释了及其对于语言识别的模式（马尔可夫假设）。

数学的精妙就在于把一些复杂的问题变得如此的简单，也是本书的主题。

2802#数学之美-NLP中文分词

中文分词是统计语言模型在中文处理中的一个应用，含有分词的语言包括中日韩等在自然书写时没有分割的语言，在计算机处理时首先应进行分词处理。

一般分词办法就是查字典，这种方法最早是由北京航天航空大学梁南元教授提出。 “查字典” 法把一个句子从左向右扫描一遍，遇到字典里有的词便进行标识，遇到复合词（比如 “上海大学”）就找最长的词匹配，遇到不认识的字串就分割成单字词，于是简单的分词就完成了。

90年前后，清华大学郭进博士用统计语言模型成功解决分词二义性问题，将汉语分词错误率降低了一个数量级。因此只要利用统计语言模型计算出每种分词后句子出现的概率，并找出其中概率最大的，就能够找到最好的分词方法。

实现的技巧，穷举所有可能的分词方法并计算出每种可能性下句子的概率，计算量是相当大的。因此，可以把它看成是一个动态规划（Dynamic Programming) 的问题，并利用 “维特比” 算法快速地找到最佳分词。

Ref. Computational Linguistics” （《计算机语言学》）

2803#数学之美-信息论

一些关键词：隐含马尔可夫模型 条件概率 贝叶斯公式 马尔可夫链 信息熵 冗余度 互信息

七十年代，当时 IBM 的 Fred Jelinek（关于贾的更多故事可以看《浪潮之巅》） 和卡内基·梅隆大学的 Jim and Janet Baker 分别独立地提出用隐含马尔可夫模型来识别语音，语音识别的错误率相比人工智能和模式匹配等方法降低了三倍。

八十年代李开复坚持采用隐含马尔可夫模型的框架， 成功地开发了世界上第一个大词汇量连续语音识别系统 Sphinx。

1948 年，Shannon提出了“信息熵”（Entropy）（一般用符号 H 表示，单位比特，从而解决了对信息的量化度量问题，信息熵很有意思，详见Wikipedia）用来度量信息的大小。

原理则是假设一条信息的信息量大小和它的不确定性有直接的关系。可以认为，信息量的度量就等于不确定性的多少。信息量的比特数和所有可能情况的对数函数 log 有关，一个比特是一位二进制数，计算机中的一个字节是八个比特。

e.g. 一本五十万字的中文书，信息量大约是 250 万比特，如果用一个好的算法压缩一下，整本书可以存成一个 320KB 的文件。

冗余度：如果用两字节的国标编码存储这本书，大约需要 1MB 大小，是压缩文件的三倍。这两个数量的差距，在信息论中称作"冗余度"（Redundancy)。

如果一本书重复的内容很多，它的信息量就小，冗余度就大。不同语言的冗余度差别很大，而汉语在所有语言中冗余度是相对小的。这和人们普遍的认识”汉语是最简洁的语言"是一致的。

信息熵正是对不确定性的衡量，因此信息熵可以直接用于衡量统计语言模型的好坏。

信息论中仅次于熵的另外两个重要的概念是“互信息”（Mutual Information) 和“相对熵”（Kullback-Leibler Divergence)。 互信息是信息熵的引申概念，它是对两个随机事件相关性的度量。

2804#数学之美-检索原理——布尔运算

George Boole是十九世纪英国一位小学数学老师（他生前没有人认为他是数学家，原因就是布尔运算本身= =）。

布尔在工作之余，喜欢阅读数学论著、思考数学问题。1854 年“思维规律”（An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities）一书，第一次向人们展示了如何用数学的方法解决逻辑问题。

布尔运算所包含的元素运算的元素只有两个1 （TRUE， 真) 和 0。直到 1938 年Shanon在他的硕士论文中指出用布尔代数来实现开关电路，才使得布尔代数成为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、乘方、开方等等，全部能转换成二值的布尔运算。

早期的文献检索查询系统大多基于数据库，严格要求查询语句符合布尔运算。今天的搜索引擎相比之下要聪明的多，它自动把用户的查询语句转换成布尔运算的算式。当然在查询时，不能将每篇文献扫描一遍，来看看它是否满足上面三个条件，因此需要建立一个索引。

因此，整个索引就变得非常之大，以至于不可能用一台计算机存下。大家普遍的做法是根据网页的序号将索引分成很多份（Shards)，分别存储在不同的服务器中。每当接受一个查询时，这个查询就被分送到许许多多服务器中，这些服务器 同时并行处理用户请求，并把结果送到主服务器进行合并处理，最后将结果返回给用户。不管索引如何复杂，查找的基本操作仍然是布尔运算。

布尔运算把逻辑和数学联系起来了。它的最大好处是容易实现和速度快，这对于海量信息查找非常关键。

不足是只能给出是与否的判断，而不能给出量化的度量。因此所有搜索引擎在内部检索完毕后，都要对符合要求的网页根据相关性排序，然后才返回给用户。

2805#数学之美-图论

离散数学是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支，数理逻辑便基于布尔运算。简历搜索引擎的引索主要依靠图论中的遍历算法（Traverse），图论的起源可追溯到数学家欧拉。

关于图的算法有很多，但最重要的是图的遍历算法，也就是如何通过弧访问图的各个节点。

此处介绍了两种图的算法，以地图绘制为例，为了达到通过弧访问图的每个节点，可以分为：“广度优先算法”（BFS)，尽可能广地访问每个节点所直接连接的其他节点；
”深度优先算法”（DFS)，因为它是一条路走到黑。

图论的遍历算法可以理解为，互联网是一张大地图，每个网页是一个节点，超链接是连接他们的弧。浏览器是通过这些隐含的网址转到相应的网页中的。这些隐含在文字背后的网址称为”超链接"。有了超链接，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并把它们存起来。完成这个功能的程序叫做网络爬虫，或者在一些文献中称为"机器人" （Robot)。

在网络爬虫中，我们使用一个称为"哈希表"(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。因此，一个商业的网络爬虫需要有成千上万个服务器，并且由快速网络连接起来。如何建立这样复杂的网络系统，如何协调这些服务器的任务，就是网络设计和程序设计的艺术了。

在计算机中一个好的算法，应该向阿卡 47 冲锋枪那样简单、有效、可靠性好而且容易读懂(或者说易操作），而不应该是故弄玄虚。Google 工程师Amit Singhal就是为 Google 设计阿卡 47 冲锋枪的人，在公司内部，Google 的排序算法便是以他的名字命名的。Singhal早年是从搜索大师Salton，毕业后就职于AT&T 实验室，并在这里确立了他在学术界的地位。

2806#数学之美-余弦定理与新闻分类

余弦定理和新闻的分类似乎是两件八杆子打不着的事。但是它们确有紧密的联系。具体说，新闻的分类很大程度上依靠余弦定理。Google 的新闻是自动分类和整理的。所谓新闻的分类无非是要把相似的新闻放到一类中。计算机其实读不懂新闻，它只能快速计算。这就要求我们设计一个算法来算出任意两篇新闻的相似性。为了做到这一点，我们需要想办法用一组数字来描述一篇新闻。

向量代数中，向量实际上是多维空间中有方向的线段，如果两个向量的方向一致（夹角为0）那么这两个向量就相近。确定两向量是否一致，就用到余弦定理计算向量夹角了。

任何一段信息文字，都可以对应一个不太长的随机数，作为区别它和其它信息的指纹（Fingerprint)。只要算法设计的好，任何两短信息的指纹都很难重复，如同人类指纹。新信息指纹在加密、信息压缩和处理中有着广泛的应用。

产生信息指纹的关键算法是伪随机数产生器算法prng，最早的prng算法是由冯诺伊曼提出来的。他的办法很简单，即将一个数的平方掐头去尾，取中间的几位数。e.g. 一个四位的二进制数 1001（相当于十进制的9），其平方为 01010001 (十进制的 81）掐头去尾剩下中间的四位 0100。当然这种方法产生的数字并不很随机，也就是说两个不同信息很有可能有同一指纹。
信息指纹的用途远不止网址的消重，信息指纹的的孪生兄弟是密码。信息指纹的一个特征是其不可逆性, 也就是说,无法根据信息指纹推出原有信息，这种性质正是网络加密传输所需要的。值得一提的事，SHA1以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。