1.1 统计语言模型

香农(Claude Shannon)就提出了用数学的办法处理自然语言。首先成功利用数学方法解决自然语言处理问题的是语音和语言处理大师贾里尼克 (Fred Jelinek)。事实证明，统计语言模型比任何已知的借助某种规则的解决方法都有效。李开复用统计语言模型把 997 词语音识别的问题简化成了一个 20 词的识别问题，实现了有史以来第一次大词汇量非特定人连续语音的识别。

1.2 中文分词

最简单的分词办法就是查字典，最早是由北京航天航空大学的梁南元教授提出的。八十年代，哈工大的王晓龙博士把它理论化，发展成最少词数的分词理论，即一句话应该分成数量最少的词串。90年前后，清华大学的郭进博士用统计语言模型成功解决分词二义性问题，将汉语分词的错误率降低了一个数量级。最好的一种分词方法应该保证分完词后这个句子出现的概率最大。我们可以把它看成是一个动态规划（Dynamic Programming) 的问题，并利用 “维特比”（Viterbi） 算法快速地找到最佳分词。清华大学孙茂松教授和香港科技大学吴德凯教授进一步完善中文分词。Google 的葛显平博士和朱安博士，专门为搜索设计和实现了自己的分词系统。中文分词的方法也被应用到英语处理，主要是手写体识别中。因为在识别手写体时，单词之间的空格就不很清楚了。中文分词方法可以帮助判别英语单词的边界。

1.3 隐含马尔可夫模型在语言处理中的应用

根据应用的不同而又不同的名称，在语音识别中它被称为“声学模型”(Acoustic Model)，在机器翻译中是“翻译模型” (Translation Model) 而在拼写校正中是“纠错模型” (Correction Model)。八十年代李开复博士坚持采用隐含马尔可夫模型的框架， 成功地开发了世界上第一个大词汇量连续语音识别系统 Sphinx。

1.4 怎样度量信息

1948 年，香农提出了“信息熵”。变量的不确定性越大，熵也就越大。是压缩文件的三倍。这两个数量的差距，在信息论中称作“冗余度”（redundancy)。不同语言的冗余度差别很大，而汉语在所有语言中冗余度是相对小的。这和人们普遍的认识“汉语是最简洁的语言”是一致的。

1.5 布尔代数和搜索引擎的索引

1938 年香农在他的硕士论文中指出用布尔代数来实现开关电路.最简单索引的结构是用一个很长的二进制数表示一个关键字是否出现在每篇文献中。不管索引如何复杂，查找的基本操作仍然是布尔运算。布尔运算把逻辑和数学联系起来了。它的最大好处是容易实现，速度快，这对于海量的信息查找是至关重要的。它的不足是只能给出是与否的判断，而不能给出量化的度量。

1.6 图论和网络爬虫

自动下载互联网所有的网页要用到图论中的遍历（Traverse) 算法。世界上第一个网络爬虫是由麻省理工学院 (MIT)的学生马休.格雷（Matthew Gray)在 1993 年写成的。在网络爬虫中，我们使用一个称为“哈希表”(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。

1.7 信息论在信息处理中的应用

贾里尼克从信息熵出发，定义了一个称为语言模型复杂度(Perplexity)的概念，直接衡量语言模型的好坏。信息论中仅次于熵的另外两个重要的概念是   “互信息”（Mutual Information) （这种方法最初是由吉尔(Gale)，丘奇(Church)和雅让斯基(Yarowsky)提出的）和“相对熵”（Kullback-LeiblerDivergence)（是以它的两个提出者库尔贝克和莱伯勒的名字命名的。相对熵用来衡量两个正函数是否相似，对于两个完全相同的函数，它们的相对熵等于零）。科弗教授是当今最权威的信息论专家。

1.8 贾里尼克的故事和现代语言处理

语言学大师贾格布森 Roman Jakobson（他提出了著名的通信六功能）他的团队：解决最大熵迭代算法的达拉皮垂(Della Pietra)孪生兄弟，BCJR 算法的另外两个共同提出者库克(Cocke)和拉维夫(Raviv)，以及第一个提出机器翻译统计模型的布朗。科学家们把语音识别问题当作人工智能问题和模式匹配问题。而贾里尼克把它当成通信问题，并用两个隐含马尔可夫模型（声学模型和语言模型）把语音识别概括得清清楚楚。贾里尼克和波尔，库克以及拉维夫对人类的另一大贡献是 BCJR 算法，这是今天数字通信中应用的最广的两个算法之一（另一个是维特比算法）。每年夏天，贾里尼克邀请世界上 20-30 名顶级的科学家和学生到 CLSP（约翰霍普金斯大学） 一起工作，使得 CLSP 成为世界上语音和语言处理的中心之一。

1.9 如何确定网页和查询的相关性

我们把这个商称为“关键词的频率”，或者“单文本词汇频率”（Term Frequency)词“的”站了总词频的 80% 以上，而它对确定网页的主题几乎没有用。我们称这种词叫“应删除词”（Stopwords)在信息检索中，使用最多的权重是“逆文本频率指数” （Inverse document frequency 缩写为ＩＤＦ），它的公式为ｌｏｇ（Ｄ／Ｄｗ）其中Ｄ是全部网页数。ＴＦ／ＩＤＦ（term frequency/inverse document frequency) 的概念被公认为信息检索中最重要的发明。其实 IDF 的概念就是一个特定条件下、关键词的概率分布的交叉熵

1.10 有限状态机和地址识别

地址的识别和分析是本地搜索必不可少的技术，尽管有许多识别和分析地址的方法，最有效的是有限状态机。使用有限状态机识别地址，关键要解决两个问题，即通过一些有效的地址建立状态机，以及给定一个有限状态机后，地址字串的匹配算法。希望有一个能进行模糊匹配、并给出一个字串为正确地址的可能性。于是提出了基于概率的有限状态机，它和离散的马尔可夫链基本上等效。

1.13. 数学之美系列十三 — 信息指纹及其应用

产生信息指纹的关键算法是伪随机数产生器算法（prng)。最早的 prng 算法是由计算机之父冯诺伊曼提出来的。现在常用的 MersenneTwister 算法要好得多。SHA1 以前被认为是没有漏洞的，现在已经被中国的王小云教授证明存在漏洞。

1.14. 数学之美系列十四 — 谈谈数学模型的重要性

１. 一个正确的数学模型应当在形式上是简单的。（托勒密的模型显然太复杂。）２. 一个正确的模型在它开始的时候可能还不如一个精雕细琢过的错误的模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去。（日心说开始并没有地心说准确。）３. 大量准确的数据对研发很重要。４. 正确的模型也可能受噪音干扰，而显得不准确；这时我们不应该用一种凑合的修正方法来弥补它，而是要找到噪音的根源，这也许能通往重大发现。在网络搜索的研发中，我们在前面提到的单文本词频/逆文本频率指数（TF/IDF) 和网页排名（page rank)都相当于是网络搜索中的“椭圆模型”，它们都很简单易懂。

1.15 繁与简 自然语言处理的几位精英

柯林斯的博士论文堪称是自然语言处理领域的范文。它像一本优秀的小说，把所有事情的来龙去脉介绍的清清楚楚，对于任何有一点计算机和自然语言处理知识的人，都可以轻而易举地读懂他复杂的方法。布莱尔的成名作是基于变换规则的机器学习方法 (transformation rule based machine learning)第一步，我们把每个拼音对应的汉字中最常见的找出来作为第一遍变换的结果，当然结果有不少错误。比如，“常识”可能被转换成“长识”；第二步，可以说是“去伪存真”，我们用计算机根据上下文，列举所有的同音字替换的规则，比如，如果 chang 被标识成“长”，但是后面的汉字是“识”，则将“长”改成“常”；第三步，应该就是“去粗取精”，将所有的规则用到事先标识好的语料中，挑出有用的，删掉无用的。然后重复二三步，直到找不到有用的为止。

1.16. 数学之美系列十六(上)—不要把所有的鸡蛋放在一个篮子里-谈谈最大熵模型

“最大熵”就是要保留全部的不确定性，将风险降到最小。最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。不做主观假设这点很重要。）在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫“最大熵模型”。信息论最高奖香农奖得主希萨（Csiszar）证明，对任何一组不自相矛盾的信息，这个最大熵模型不仅存在，而且是唯一的。而且它们都有同一个非常简单的形式 -- 指数函数。最大熵模型在形式上是最漂亮的统计模型，而在实现上是最复杂的模型之一。最原始的最大熵模型的训练方法是一种称为通用迭代算法GIS(generalized iterative scaling) 的迭代 算法。

GIS 的原理并不复杂，大致可以概括为以下几个步骤：1. 假定第零次迭代的初始模型为等概率的均匀分布。2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把相应的模型参数变小；否则，将它们便大。3. 重复步骤 2 直到收敛。信息处理的很多数学手段，包括隐含马尔可夫模型、子波变换、贝叶斯网络等等，在华尔街多有直接的应用。

1.19. 数学之美系列十八 — 矩阵运算和文本处理中的分类问题分类的关键是计算相关性。

Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，我认为这是 Google 中国对世界的一个贡献。

1.22. 数学之美系列二十一 — 布隆过滤器（Bloom Filter）

布隆过滤器只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。

GIS算法 IIS算法 维特比算法 Baum-Welch算法 EM算法