第二版前言

数学演化的过程，实际上是将我们生活中遇到的具体事物及其运动的规律不断抽象化的过程。

第1章文字和语言VS数字和信息

1.信息

原始人通信的方式和今天的通信模型没有什么不同。

说话人——信息编码——接收者

2.文字和数字

高效记录信息的需求产生了，这便是文字的起源

不同的文字系统在记录信息上的能力是等价的

案例：罗森塔石碑

3.文字和语言背后的数学

从象形文字到拼音文字是一个飞跃，因为人类在描述物体的方式是，从物体的外表进化到了抽象的概念，同时不自觉地采用了信息的编码。

第2章自然语言处理——从规则到统计

任何一种语言都是一种编码的方式，而语言的语法规则是编解码的算法。

1.机器智能

图灵测试：让人和机器进行交流，如果人无法判断自己交流的对象是人还是机器，就说明这个机器有智能了。

“飞鸟派”就是看鸟是怎么飞的，就能模仿鸟造出飞机，而不需要了解空气动力学。

在20世纪60年代，对于如何理解自然语言，当时普遍的认识是做好两件事：分析语句和获取语义。

2.从规则到统计

到了20世纪90年代末期，大家发现通过统计得到的句法规则甚至比语言学家总结的更有说服力。

第3章统计语言模型

1.用数学的方法描述语言规律

事实证明，统计语言模型比任何已知的借助某种规则的解决方法更有效。

2.延伸阅读：统计延伸阅读：统计语言模型的工程诀窍

2.1 高阶语言模型

假设文本中的每个词W和前面的N-1个词有关，N不能太大，当N从1到2，再从2到3时，模型的效果上升显著。而当模型从3到4时，效果的提升不是很显著了，而资源的耗费却增加得非常快。

Google的罗森塔翻译系统和语音搜索系统，使用的是四元模型

2.2 模型的训练、零概率和平滑方法

正确地训练一个语言模型一个直接的办法就是增加数据量。

2.3 语料的选取问题

在成本不高的情况下，有必要对训练数据进行过滤

第4章谈谈分词

1.中文分词方法的演变

需要先对句子进行分词，才能做进一步的自然语言处理。

郭进是中国大陆自觉运用统计语言模型方法进行自然语言处理的第一人。

手机输入法可以统计出分词数据

2.延伸阅读：如何衡量分词的结果

2.1 分词的一致性

在将统计语言模型用于分词以前，分词的准确率通常较低，可以提升的空间非常大。

2.2 词的颗粒度和层次

针对不同的应用构造不同的分词器非常浪费，也没有必要。更好的做法是让一个分词器同时支持不同层次的词的切分。

第5章隐含马尔可夫模型

1.通信模型

雅各布森通信六个要素：发送者（信息源）、信道、接受者、信息、上下文和编码。

所谓语音识别，就是听者去猜测说话者表达的意思。这其实就像通信中，接收端根据收到的信号去分析、理解、还原发送端传出来的信息。

2.隐含马尔可夫模型

在隐马尔可夫模型中，状态是不直接可见的，但输出依赖于该状态下，是可见的。每个状态通过可能的输出记号有了可能的概率分布。

隐含马尔可夫模型最早的成功应用是语音识别。

3.延伸阅读：隐含马尔可夫模型的训练

围绕着隐含马尔可夫模型有三个基本问题：

给定一个模型，如何计算某个特定输出序列的概率；
给定一个模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列；
给定足够量的观测数据，如何估计隐含马尔可夫模型的参数。

第6章信息的度量和作用

1.信息熵

信息量就等于不确定性的多少。

变量的不确定性越大，熵也就越大，要把它搞清楚，所需信息量也就越大。

2.信息的作用

信息的作用在于消除不确定性，自然语言处理的大量问题就是寻找相关的信息。

3.互信息

香农在信息论中提出了一个“互信息”（mutual information）的概念作为两个随机事件“相关性”的量化度量。

4.延伸阅读：相对熵

对于两个完全相同的函数，它们的相对熵等于零。

相对熵越大，两个函数差异越大；

第7章贾里尼克和现代语言处理

1.早年生活

小学生和中学生其实没有必要花那么多时间读书，而他们的社会经验、生活能力以及那时树立起的志向将帮助他们的一生。

中学阶段话花多时间比同伴多读的课程，上大学以后用很短时间就能读完；

学习（和教育）是持续一辈子的过程；

书本的内容可以早学，也可以晚学，但是错过了成长阶段却是无法弥补回来的。

一人想要在自己的领域做到世界一流，他的周围必须有非常多的一流人物。

2.从水门事件到莫妮卡莱温斯基

在贾里尼克之前，科学家们把语音识别问题当作人工智能和模式匹配问题。而贾里尼克把它当成通信问题。

统计自然语言处理诞生于IBM有着历史的必然性，当时只有IBM有这样的计算能力，又有物质条件同时聚集起一大批世界上最聪明的头脑。

3.一位老人的奇迹

贾里尼克会在第一时间告诉我什么方法不好（失败的经验）

第8章简单之美——布尔代数和搜索引起

技术分为术和道两种，具体的做事方法是术，做事的原理和原则是道。

做好搜索引擎，最基本的要求是每天分析10——20个不好的搜索结果。

1.布尔代数

1938年香农在他的硕士论文中指出用布尔代数来实现开关电路，才使得布尔代数成为数字电路的基础。

2.索引

最简单的索引结构是用一个很长的二进制表示一个关键字是否出现在每篇文献中。

为了解决索引变得很大的问题，需要将索引通过分布式的方式存储到不同的服务器上。

第9章图论和网络爬虫

离散数学是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。

1.图论

“广度优先搜索”：尽可能“广”地访问与每个节点直接连接的其他节点。

“深度优先搜索”：一条路走到黑

2.网络爬虫

网络爬虫（web crawlers）：有了超链接，我们可以从任何一个网页出发，用图的遍历算法，自动地访问到每一个网页并把它们存起来。

3.延伸阅读：图论的两点补充说明

3.1 欧拉七桥问题的证明

定理：如果一个图能够从一个顶点出发，每条边不重复地遍历一遍回到这个点，那么每一顶点的度必须为偶数。

3.2 构建网络爬虫的工程要点

搜索引擎的网络爬虫问题更应该定义成“如何在有限时间里最多地爬下最重要的网页”

网络爬虫有一个相对复杂的下载优先级排序的方法。

第10章 PageRank——Google的民主表决式网页排名技术

对于一个特定的查询，搜索结果的排名取决于两组信息：关于网页的质量信息（quality），以及这个查询与每个网页的相关信息（relevance）。

1.PageRank算法的原理

在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖。

网页排名高的网站贡献的链接权重大。

2.延伸阅读：PageRank的计算方法

网页排名的计算主要是矩阵相乘，这种计算很容易分解成许多小任务。

第11章如何确定网页和查询的相关性

1.搜索关键词权重的科学度量TF-IDF

度量网页和查询的相关性，有一个简单的方法，就是直接使用各个关键词在网页中出现的总词频。

如果一个关键词只在很少的网页中出现，通过它就容易锁定搜索目标，它的权重也就应该大。

所谓的IDF的概念就是一个特定条件下关键词的概率分别和交叉熵。

2.延伸阅读：TF-IDF的信息论依据

一个查询（query）中的每一个关键词（key Word）w的权重应该反映这个词对查询来讲提供了多少信息。一个简单的办法就是用每个次的信息量作为它的权重。

第12章有限状态机和动态规划——地图与本地搜索的核心技术

1.地址分析和有限状态机

有限状态机是一个特殊的有向图，它包括一些状态和连接这些状态的有向弧。

为了解决用户输入的地址不太标准或者有错别字，我们希望可以看到可以进行模糊匹配，并给出一个字串为正确地址的可能性。

2.全球导航和动态规划

所有的导航系统都采用了动态规划（dynamic programming ，DP）的办法。

先在地图上横切一刀，保障将任何从北京到广州的路线一分为二。先找到从北京出发到这条线上所有城市的最短路径，最后找到局部最短路线。

3.延伸阅读：有限状态传感器

在语音识别中，每个被识别的句子都可以用一个WFST来表示。WFST中的每一个路径就是一个候选的句子，其中概率最大的那条路径就是这个句子的识别结果。

第13章 Google AK-47的设计者——阿木特·辛格博士

在计算机科学领域，一个好的算法应该像AK-47冲锋枪那样：简单、有效、可靠好而且容易读懂（或者说易操作），而不应该是故弄玄虚。

许多失败并不是因为人不优秀，而是做事情的方法不对，一开始追求大而全的解决方案，之后长时间不能完成，最后不了了之。

第14章余弦定理和新闻的分类

1.新闻的特征向量

为了让计算机能够“算”新闻（而不是读新闻），就要求我们先把文字的新闻变成一组可计算的数字，然后再设计一个算法来算出任意两篇新闻的相似性。

2.向量距离的度量

两篇新闻的主题是否接近，取决于它们的特征向量“长得像不像”。

当夹角的余弦接近于1时，两条新闻相似，从而可以归成一类；夹角的余弦越小，夹角越大，两条新闻越不相关。

3.延伸阅读：计算向量余弦的技巧

3.1 大数据量时的余弦计算

删除虚词，不仅可以提高计算速度，对新闻分类的准确性也大有好处，因为虚词的权重其实是一种噪音。

3.2 位置的加权

出现在标题中的词对主题的贡献远比出现在新闻正文中的重要。

第15章矩阵运算和文本处理中的两个分类问题

1.文本和词汇的矩阵

奇异值分解：每一行对应一篇文章，每一列对应一个词，如果有N个词，M篇文章，则得到一个M*N的矩阵。

2.延伸阅读：奇异值分解的方法和应用场景

奇异值分解的计算复杂度不需要多次迭代，因此计算时间短。

第16章信息指纹及其应用

1.信息指纹

任何一段信息（包括文字、语音、视频、图片等），都可以对应一个不太长的随机数。

网络爬虫在下载网页时，会将访问过的网页地址都变成一个个信息指纹，存到散列表中。

为了保障信息安全，一些网站（比如银行的）采用加密的HTTPS，用户访问这些网站留下的cookie本身也需要加密。

2.信息指纹的用途

2.1 集合相同的判定

判断两个查询用词是否完全相同，最普遍的讲法是判断两个集合是否相同，完美的方法是计算这两个集合的指纹，然后直接进行比较。

2.2 判断集合基本相同

判断一篇文章是否抄袭另一篇文章，具体做法是，将每一篇文章切成小的片段，然后用上述方法挑选这些片段的特征词集合，并计算它们的指纹。

2.3 YouTube的反盗版

关键帧对视频的重要性，就如同主题词对新闻的重要性一样。

处理视频图像首先是找到关键帧，接下来就是要用一组信息指纹来表示这些关键帧了。

3.延伸阅读：信息指纹的重复性和相似哈希

3.1 信息指纹重复的可能性

不同信息产生相同指纹的可能性几乎为零。

3.2 相似哈希（simhash）

相似哈希的特点是，如果两个网页的相似哈希相差越小，这两个网页的相似性就越高。如果两个网页相同，它们的相似哈希必定相同。

第17章由电视剧《暗算》所想到的——谈谈密码学的数学原理

1.密码学的自发时代

从数学角度上讲，加密的过程可以看作是一个函数的运算F，解密的过程是反函数的运算。明码是自变量，密码是函数值。好的（加密）函数不应该通过几个自变量和函数值就能推出函数。

2.信息论时代的密码学

均匀分布使得敌方无从统计，而统计独立可以保证敌人即使知道了加密算法，并且看到了一段密码和明码后，也无法破译另一端密码。

第18章闪光的不一定是金子——谈谈搜索引擎反作弊问题和搜索结果的权威性问题

1.搜索引擎的反作弊

搜索引擎作弊从本质上看就如同对（搜索）排序的信息加入噪音，因此反作弊的第一条就是要增强排序算法的抗噪声能力。

掌握了动机就可以针对他们的动机进行防范。

一个网站想要长期排名靠前，就需要把内容做好，同时要跟那些作弊网站划清界限。

2.搜索结果的权威性

权威性通过“提及”来度量。

在计算权威度时，我们采用了本书中另外三章的方法，包括句法分析、互信息和短语（词组）的聚类。

第19章谈谈数学模型的重要性

古埃及的农业文明受益于尼罗河的洪水，它直接促进了天文学的诞生。

几点结论：

一个正确的数学模型应当在形式上是简单的
一个正确的模型一开始可能还不如一个精雕细琢的错误模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去。
大量准确的数据对研发很重要。

第20章不要把鸡蛋放到一个篮子里——谈谈最大熵模型

1.最大熵原理和最大熵模型

最大熵原理指出，对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。

最大熵模型在形式上是最漂亮、最完美的统计模型。在自然语言处理和金融方面有很多有趣的应用。

最大熵模型形式简单，实现复杂。

第21章拼音输入法的数学原理

1.输入法与编码

第一代输入法的问题在于减少了每个汉子击键的次数，而忽视了找到每个键的时间。

2.输入一个汉子需要敲多少个键——谈谈香农第一定理

香农第一定理指出：对于一个信息，任何编码的长度都不小于它的信息熵。

如果把汉子组成词，再以词为单位统计信息熵，那么每个汉子的平均信息熵将会减少。

利用上下文最好的办法是借助语言模型。

3.拼音转汉字的算法

拼音汉字的算法和在导航中寻找最短路径的算法相同，都是动态规划。

4.延伸阅读：个性化的语言模型

因此，如果每个人有各自的语言模型，用拼音输入时，候选词次序的排序一定比通用的输入法排得好。

找到符合用户经常输入的内容和用语习惯的语料，训练一个用户特定的语言模型。

第22章自然语言处理的教父马库斯和他的优秀弟子们

1.教父马库斯

马库斯比很多同行更早地发现了建立标准语料库在自然语言处理研究中的重要性。

马库斯的主张一贯是建立几个世界上最好的专业，而不是专业最齐全的系。

2.从宾夕法尼亚大学走出的精英们

2.1 柯林斯：追求完美

柯林斯和他的师兄弟不同，他做文法分析器的出发点不是为了验证一个理论，而是要做一个世界上最好的分析器。

柯林斯成功的关键在于将文法分析的每一个细节都研究得很仔细。

2.2 布莱尔：简单才美

布莱尔总是试图寻找简单得不能再简单的方法。

第23章布隆过滤器

1.布隆过滤器的原理

对于每一个电子邮件地址X，用8个不同的随机数产生器产生8个信息指纹。再用一个随机数产生器G把这8个信息指纹映射到1—16亿中的8个自然数。

补救误识别的常见办法是再建一个小的白名单，存储那些可能被别误判的信息。

第24章马尔可夫链的扩展——贝叶斯网络

1.贝叶斯网络

使用贝叶斯网络必须选确定这个网络的拓扑结构，然后还要知道各个状态之间相关的概率。

2.贝叶斯网络在词分类中的应用

可以用贝叶斯网络建立一个文章、概念和关键词之间的联系。

小结

从数学的层面来讲，贝叶斯网络是一个加权的有向图，是马尔可夫链的扩展。

第25章条件随机场、文法分析及其他

1.文法分析——计算机算法的演变

自然语言的句法分析一般是指根据文法对一个句子进行分析，建立这个句子的语法树，即文法分析。

在很多自然语言处理的应用中，并不需要对语句做深入的分析，只要做浅层的分析。于是科学家们把研究的重点从语句的深层分析转到对语句的浅层分析上。

2.条件随机场

更广义的讲，条件随机场是一种特殊的概率图模型。

条件随机场在其他领域的应用

最好的办法不是在犯罪发生后去破案，而是提前制止犯罪行为。

第26章维特比和他的维特比算法

维特比算法是现代数字通讯中最常用的算法，同时也是很多自然语言处理采用的解码算法。

1.维特比算法

维特比算法是一个特殊但应用最广的动态规划算法。利用动态规划，可以解决任何一个途中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆网络的有向图最短路径的问题而提出的。

2.CDMA技术——3G移动通信的基础

在CDMA以前，移动通信使用过两种技术：频分多地址（FDMA）和时分多址（TDMA）。

将CDMA技术用于移动通信的是高通公司。

第27章上帝的算法——期望最大化算法

1.文本的自收敛分类

分类步骤如下：

随机挑选K个点，作为起始中心，
计算所有点到这些聚类中心的距离，将这些点归到最近的一类中。
重新计算每一类的中心
重复上述过程，直到每次新的中心和旧的中心之间的偏移非常非常小，即过程收敛。

2.延伸阅读：期望最大化和收敛的必然性

我们希望最终的分类结果是：相近的点都被聚集到了一类中，这样同一类中各个点到中心平均距离d较近，而不同类中心之间的平均距离D较远。我们希望的迭代过程是每一次迭代时，d比以前变小，而D变大。

第28章逻辑回归和搜索广告

1.搜索广告的发展

Google并不简单地将出价高的广告放在前面，而是预测到哪一个广告可能被点击，综合出价和点击率（chick through rate 简称CTR）等因素决定广告的投放。

2.逻辑回归模型

逻辑回归模型是指讲一个事件出现的概率逐渐适应到一条逻辑曲线上。

一个广告系统中，点击率预估机制的好坏决定了能否成倍提高单位搜索的广告收入。

第29章各个击破算法和Google云计算的基础

云计算的关键之一是，如何把一个非常大的计算问题，自动分解到许多计算能力不是很强大的计算机上，共同完成。

1.分治算法的原理

分治算法是计算机科学中最漂亮的工具之一。它的基本原理是：讲一个复杂的问题，分成若干个简单的子问题进行解决。然后，对子问题的结果进行合并，得到原有问题的解。

2.从分治算法到MapReduce

MapReduce的根本原理是将一个大任务分解成小的子任务，并且完成子任务的计算，这个过程叫做map，将中间结果合并成最终成果，这个过程叫做reduce。

第30章 Google大脑和人工神经网络

1.人工神经网络

人工神经网络和人脑没有半点关系，它本质上是一种特殊的有向图。

大多数与“智能”有点关系的问题，都可以归结为一个在多维空间进行模式分类的问题。

2.训练人工神经网络

人工神经网络的训练分为有监督的训练和无监督的训练。

和有监督的训练不同，无监督的训练只有输入数据（x），而没有赌赢的输出数据（y），这样依赖成本函数（c）就无法使用了。因此我们需要定义一种新的（而且容易计算的）成本函数。

成本函数总是遵循这样的一个原则：既然人工神经网络解决的是分类问题，那么我们希望分完类之后，同一样本应该相互比较靠近。

3.人工神经网络与贝叶斯网络的关系

人工神经网络和贝叶斯网络的共同点：

它们都是有向图
训练方法相似
对于很多模式分类问题效果上相似
训练计算量都特别大

不同之处：

人工神经网络在机构上是完全标准化的，而贝叶斯网络更灵活
神经元函数为非线性函数对一个变量（即前面组合出来的结果）进行非线性变换。而在贝叶斯网络中，变量可以组合成任意的函数
贝叶斯网络更容易考虑（上下文）前后的相关性，而人工神经网络的输出相对孤立。

4.延伸阅读：“Google大脑”

Google大脑说穿了是一种大规模并行处理的人工神经网络。

计算能力的提升一半是靠处理器性能的提升，另一半则是靠很多处理器并行工作体现出来的。

第31章大数据的威力——谈谈数据的重要性

1.大数据的重要性

人类的文明与进步，从某种意义上来讲通过对数据进行收集、处理和总结而达成的。

在Google内部，产品经理都遵循这个一个规则：在没有数据之前，不要给出任何结论。

人们在没有看到数据之前总是倾向于高估自己，或者夸大一件事情的正面效果，而忽视它的负面影响。

统计表明95%的个人投资者最终跑不赢大盘，50%-70%的频繁短线交易者甚至在亏钱。

事实上70%的基金长期表现不如大盘。

如果一个散户投资人能真正做到“用数据说话”，只需奉行一条投资决策，那就是买指数基金。

2.数据的统计和信息技术

概率论是研究随机现象数量规律的数学分支。统计学是通过搜索、整理、分析数据等手段，以达到推断所测对象的本质，甚至是预测对象未来的一门综合性科学。

除了要求数据量必须足够多，统计还要求采样的数据具有代表性。

数据成了决定搜索引擎好坏的第一要素，而算法倒在其次了。

3.为什么需要大数据

大数据的好处远不只是成本和准确性的问题，它的优势还在于多维度（或叫全方位）。

医疗保健行业是美国最大的行业，2013年它的产值占到美国GDP的15%左右。

附录：计算复杂度

将解决实际问题的方法变成计算可以运行的程序，中间的桥梁就是计算机的算法。