作者寄语
愿科学之精神在国民中得到普及，愿中国年轻的一代涌现更多的杰出专业人才。
名人语录
除那些真实而已足够说明其现象者外，不必去寻找自然界事物的其他原因。
—牛顿
简单性和模块化是软件工程的基石；分布式和容错性是互联网的声明。
—蒂姆 伯纳斯 李
纯数学使我们能够发现概念和联系这些概念的规律，这些概念和规律给了我们了解自然
现象的钥匙。
—爱因斯坦
相关读物
《从一到无穷大》 — 乔治 伽莫夫 (George Gamow)
第一章：文字和语言 vs 数字的信息
1.信息的冗余是信息安全的保障。罗塞塔石碑上的内容是同一信息重复三次
2.阿拉伯数字的发明人是古印度人，只不过这种计数方式是由阿拉伯人传入欧洲的
3.关于古文与白话文的信息论解释：
如果信道较宽，信息不必压缩就可以直接传递；如果信道很窄，信息在传递前需要尽可
能的压缩，然后在接收端解压缩。
在古代，两个人讲话说得快，是一个宽信道，无需压缩；书写则是一个慢而代价昂贵的
窄信道，需要压缩。
4.这章主要是帮助读者感受语言和数学天然、内在的联系。
第二章：自然语言处理 — 从规律到统计
1.今天，机器翻译和语音识别已经做得不错，并且有上亿人使用过，但是大部分这个领
域之外的人依然错误地认为这两个应用是靠计算机理解自然语言完成的。事实上，他们
全部都都靠的是数学，更准确的说是靠统计。
2.描述自然语言的文法和计算机高级程序语言的文法不同。自然语言在演变的过程中，
产生了词义和上下文相关的特性。因此，它的文法是比较复杂的上下文有关文法，而程
序语言是我们认为设计的，为了便于计算机解码的上下文无关文法，相比自然语言而言
简单的多。对于上下文无关文法，算法的复杂度基本上是语句长度的二次方，而对于上
下文有关文法，计算复杂度基本上是语句长度的六次方。
3.基于统计的自然语言处理方法，在数学模型上和通信是相通的，甚至就是相通的。因
此，在数学意义上自然语言处理又和语言的初衷 — 通信联系在一起了。但是，科学家
们认识到这个联系却花了几十年的时间。
第三章：统计语言模型
1.19世纪到20世纪初，俄罗斯有个数学家叫马尔科夫，他给了个偷懒但还颇为有效的方
法，也就是每当遇到这种情况时，就假设任意一个词$W_{i}$出现的概率只同它前面的
词$W_{i-1}$有关，于是问题就变简单了。这种假设在数学上成为马尔科夫假设。
2.也可以假设一个词由前面N-1个词决定，对应的模型稍微复杂些，被称为N元模型。
3.在实际工程中，还需要考虑零概率问题和平滑的方法，细节可参考原书。
第四章：谈谈中文分词
1.利用统计语言模型进行自然语言处理是建立在词的基础上的，因为词是表达语义的
最小单位。对于西方拼音语言来讲，词之间有明确的分界符(Delimit)，统计和使用语言
模型非常直接。而对于中、日、韩、泰等语言，需要首先对句子进行分词，才能做进一
步的自然语言处理。
2.最容易想到的分词方法，也是最简单的办法，就是查字典(最早由北航的梁南元教授提
出)。”查字典”的办法，其实就是把一个句子扫描一遍，遇到字典里有的词就标识出来，
遇到复合词就找最长的词匹配，遇到不认识的字串就分割成单字词。
3.利用统计语言模型分词的方法，基本的想法就是：最好的一种分词方法应该保证分完词
后这个句子出现的概率最大。
4.中文分词以统计语言模型为基础，通过几十年的发展和完善，今天基本可以看做是一个
已经解决的问题。当然不同的人做的分词器有好有坏，这里面的差别主要在于数据的使用
和工程实现的精度。
第五章：隐含马尔科夫模型
1.马尔科夫假设：随机过程中各个状态$S_{t}$的概率分布，只与它的前一个状态$S_{t-1}$
有关。
2.隐含马尔科夫模型是上述马尔科夫链的一个扩展：任一时刻t的状态$S_{t}$是不可见
的。所以观察者无法通过观察到一个状态序列$S_{1}, S_{2}, S_{3}, ..., S_{T}$来
推测转移概率等参数。但是隐含马尔科夫模型在每个时刻t会输出一个符号$O_{t}$，而
且$O_{t}$和$S_{t}$相关且仅和$S_{t}$相关。这个被称为独立输出假设。其中隐
含的状态是一个典型的马尔科夫链。
3.围绕着隐含马尔科夫模型有三个基本问题：
a.给定一个模型，如何计算某个特定的输出序列的概率；
Forward-Backward算法
b.给定一个模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列；
解码算法：维特比算法
c.给定足够的观测数据，如何估计隐含马尔科夫模型的参数。
训练算法：鲍姆-韦尔奇算法
第六章：信息的度量和作用
1.信息量就等于不确定性的多少。
2.WIKI：信息熵
3.变量的不确定越大，熵也就越大，把它搞清楚所需要的信息量也就越大。
4.合理利用信息，而不是玩弄什么公式和机器学习算法，是做好搜索的关键。
第七章：贾里尼克和现代语言处理
1.每当弗莱德和我谈起我们各自少年时的教育，我们都同意这样几个观点(博主也很同意)：
a.小学生和中学生其实没有必要花那么多时间读书，而他们的社会经验、生活能力以及在
那时树立起的志向将帮助他们一生。
b.中学阶段化很多时间比同伴多读的课程，在大学以后用非常短的时间就可以读完，因为
在大学阶段，人的理解力要强的多。
c.学习和教育是一个人一辈子的过程，很多中学成绩好的亚裔学生进入名校后表现明显不
如那些因为兴趣而读书的美国同伴，因为前者不断读书的动力不足。
d.书本的内容可以早学，也可以晚学，但是错过了成长阶段却是无法补回来的。
2.贾里尼克最初的理想在他十来岁时就建立起来了，他原本想成为一个律师，为他父亲那
样的冤屈者辩护，但是到美国后，他很快意识到他那弄弄的外国口音将使他在法庭上的辩
护很吃力。贾里尼克的第二个理想是成为医生，也算是子承父业。他想进哈弗大学医学院，
但他无力承担医学院8年高昂的学费。而恰恰此时麻省理工学院给了他一份为东欧一名设的
全额奖学金。贾里尼克决定到麻省理工学电机工程。贾里尼克的理想在不断的改变，但是
他通过努力走向成功的志向一直没有改变。
第八章：简单之美 — 布尔代数和搜索引擎的索引
1.布尔代数非常简单，但是对数学和计算机发展的意义重大，它不仅把逻辑和数学合二为
一，而且给了我们一个全新的视角看待世界，开创了今天数字化的时代。
2.Truth is ever to be found in simplicity, and not in the multiplicity and
confusion of things. —by Sir Isaac Newton(艾萨克 牛顿爵士)
第九章：图论和网络爬虫
1.欧拉七桥问题
2.网路爬虫在工程实现上要考虑的细节非常多，其中大的方面有这样几点：
a.用BFS还是DFS
从理论上讲，这两个算法能够在大致相同的时间里，爬下整个静态互联网的内容。
但是互联网是动态更新的，所以网络爬虫问题更应该定义成：如何在有限时间里最多的爬
下最重要的网页。
显然各个网站最重要的网页是它的首页。
如果爬虫非常小，只能下载非常有限的网页，那么应该下载的是所有网页的首页。BFS
但是互联网又是分布式的，BFS必然导致大量的各个网站直接的跳转与跳回，效率会降低。
而且爬虫器基本也是分布式的，所以更好的方式是总体上选用BFS，然而针对某个网站，
某个爬虫服务器应该尽量一次爬完所有的页面，这样就是DFS的策略。
第十章：PageRank — Google的民主表决式网页排名技术
第十一章：如何确定网页和查询的相关性
2.TF: Term Frequency IDF: Iverse Document Frequency
3.词的权重：如果一个关键词只在很少的网页中出现，通过它就容易确定搜索目标，它的
权重也就应该大。反之，如果一个词在大量网页中出现，看到它依然不清楚要找什么内容，
因此它的权重就应该小。
4.IDF就是一个词的权重的指标。公式：$\log \left( \dfrac {D}{D_{w}}\right)$
其中D是全部网页数，关键词w在$D_{w}$个网页中出现过。 那么$D_{w}$越大，IDF
就会越小。
第十二章：地图和本地搜索的最基本技术 — 有限状态机和动态规划
1.地址分析用到有限状态机
2.导航路线用到动态规划
第十三章：Google AK-47的设计者 — 阿米特 辛格博士
1.许多失败并不是因为人不优秀，而是做事情的方法不对，一开始追求大而全的解决方案，
之后长时间不能完成，最后不了了之。
2.在Google里，辛格一直坚持寻找简单有效的解决方案。
3.当然，辛格之所以总是能找到那些简单有效的方法，不是靠直觉，更不是撞大运，这首
先是靠他丰富的研究经验。辛格早年师从于搜索大师萨尔顿(Salton)教授，毕业后就职于
AT&T实验室。
第十四章：余弦定理和新闻的分类
1.首先找到一组来描述新闻主题的数字：对于一篇新闻中的所有诗词，计算出他们的TF-IDF
值，把这些值按照对应的实词在词汇表的位置一次排序，就得到一个向量。
2.余弦定理就是计算两个向量夹角的方法。运用到新闻分类问题中，就可以认为夹角越小，
新闻越相似，反之则越不同。
第十五章：矩阵运算和文本处理中的两个分类问题
2.相比上一章介绍的利用文本特征向量余弦的举例自底向上的分类方法，奇异值分解的
优点是能较快地得到结果，因为它不需要一次次地迭代。但是用这种方法得到的分类结果
略显粗略，因此，它适合处理超大规模文本的粗分类。在实际工作中，先使用奇异值分解
进行粗分类，然后使用向量余弦得到比较精确的结果。
第十六章：信息指纹及其应用
1.产生信息指纹的关键算法：伪随机数产生器算法(Pseudo-Random Number Generator, PRNG),
通过它将任意很长的整数转换成特定长度的伪随机数。
2.现在常用的梅森旋转算法(Mersenne Twister)要好得多。
3.信息指纹的用途远不止网址的消重，它的孪生兄弟是密码。信息指纹的一个特征是其不
可逆性。
第十七章：由电视剧《暗算》所想到的 — 谈谈密码学的数学原理
1.类似凯撒大帝式的加密方式，使用统计学的方法能够轻松解密。
2.信息论时代的密码学，就我现在的简单理解就是倒腾大素数的过程。
第十八章：闪光的不一定是金子 — 谈谈搜索引擎反作弊问题
1.网页搜索反作弊对于搜索引擎公司来讲是一项长期的任务。作弊的本质是在网页排名信
号中加入噪音，因此反作弊的关键是去噪音。沿着这个思路可以从根本上提高搜索算法抗
作弊的能力，事半功倍。而如果只是根据作弊的具体特征头痛医头，脚痛医脚，则很容易
被作弊者牵着鼻子走。
第十九章：谈谈数学模型的重要性
1.一个正确的数学模型应该在形式上是简单的。
2.一个正确的模型一开始可能还不如一个精雕细琢的错误模型来的准确，但是，如果我们
认定大方向是对的，就应该坚持下去。
3.大量准确的数据对研发很重要。
4.正确的模型也可能受噪音干扰，而显得不准确；这时不应该用一种凑合的修正方法来弥
补它，而是要找到噪音的根源，这也许能通往重大的发现。
第二十章：不要把鸡蛋放到一个篮子里 — 谈谈最大熵模型
1.最大熵模型说白了，就是要保留全部的不确定性，将风险降到最小。
2.最大熵原理指出，需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全
部已知的条件，而对未知的情况不要做任何主观假设。在这种情况下，概率分布最均匀，
预测的风险最小。因为这是概率分布的信息熵最大，所以人们称这种模型叫：最大熵模型。
3.最原始的最大熵模型的训练方法是一种称为通用迭代算法GIS(Generalized Iterative
Scaling)的迭代算法。GIS的原理并不复杂，大致可以概括为一下几个步骤：
a.假定第零次迭代的初始模型为等概率的均匀分布
b.通过第N次迭代的模型来估算每种信息特征在训练数据中的分布。如果超过了实际的，
就把相应的模型参数变小。否则，将他们变大。
c.重复步骤2直到收敛
4.达拉皮垂孪生兄弟在IBM对GIS算法做了两方面的改进，提出了改进迭代算法IIS(Improved
Iterative Scaling)。
第二十一章：拼音输入法的数学原理
1.和任何事物的发展一样，螺旋式的回归不是简单的重复，而是一种升华。
2.香农第一定理：对于一个信息，任何编码的长度都不小于它的信息熵。
第二十二章：自然语言处理的教父马库斯和他的优秀弟子们
1.宾夕法尼亚大学LDC语料库以及他的优秀弟子是马库斯对自然语言处理领域的重大贡献。
2.柯林斯：追求完美
3.布莱尔：简单才美
第二十三章：布隆过滤器
1.基本流程：对于一个需要处理的元素，使用多个随机数产生器产生多个数，将各个数对
应的位标为1。在使用时，使用同样的随机数产生器得到多个数，然后判断响应位是否为1
即可。布隆过滤器的优点是快速和节省空间，确定就是有一定的误识别率。常见的补救方
法是再建立一个小的白名单，存储哪些可能被误判的元素。
2.布隆过滤器背后的数学原理在于两个完全随机的数字冲突的概率很小，因此，可以在很
小的误识别率的条件下，用很好的空间存储大量信息。
第二十四章：马尔科夫链的扩展 — 贝叶斯网络
1.假定在这个图中马尔科夫假设成立，即每个状态只和它直接相连的状态有关，而和它间
接相连的状态没有直接关系，那么它就是贝叶斯网络。