原文引自 豆瓣《数学之美》-笔记总结

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

讲述了文字、数字和语言的历史，目的是帮助读者感受语言和数字的内在联系。

任何事物的规律性是内在的，不随着载体的改变而改变。

通信方式：信息源编码——信道传播——接收者解码

文字和数字的历史：

简单的声音不能满足沟通的需求，语言由此产生——随着对新鲜事物的学习，用来描述共同因素的语言被抽象成词汇——语言和词汇多到难以记忆，便产生了文字——文字多到难以记忆时，概念的概括和归纳就开始了——文字按照意思来聚类会产生歧义，可以利用上下文来消除——不同文明相互融合，于是产生翻译——记录物件数量，计数系统产生（10位以内掰指头，10位后使用10进制，后产生数量级）——阿拉伯数字的产生标志着数字和文字的分离，奠定了数学未来的发展。

【事物发展到一定阶段时，会变得复杂起来，这时会有新的事物来代替它。新的事物看起来简单，但这种简单也是它的复杂性之所在，因为它又需要其它事物来进行解释。从这方面来说，事物之间并不存在好坏之分，放到合适的位置上便是好的。】

关于翻译：

翻译之所以能达成，是因为不同的文字在记录信息上的能力是等价的。即文字只是信息的载体，而非信息本身。信息冗余是信息安全的保障，只要有一份内容完好保存下来，原有信息就不会丢失。双语或者多语的对照语料对翻译至关重要，它是机器翻译的基础。

文字和语言背后的数学：

楔形/象形文字诞生——为方便雕刻，简化成22个字母——为方便学习，拼写和读音结合（将物体外表编码为抽象概念，常用字短，生僻字长）——为节省信道，传播信息前需进行压缩，接收后再解压，并校验——语法使语言表达更准确、更丰富

关于语言、语法：

语言坚持从真实语句文本（即语料）出发，语法坚持从规则出发，前者在自然语言处理上获胜。

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

自然语言的发展：

第一阶段，局限在人类学习语言的方式上（即句法分析）；第二阶段，基于数学模型和统计的方法，并取得突破。

句法分析：

将句子分为主语、谓语、句号三部分，然后对每一个部分进行分析，得到语法分析树。

不足在于：一个短短的句子需要很复杂的文法规则，这些文法规则写到后来甚至会出现矛盾，为了解决这些矛盾，还需要说明各个规则特定的使用环境；自然语言中的词很难用文法去描述，严重依赖于上下文，甚至是“世界知识”或者“常识”，所以很难用计算机去解析。

基于统计方法的发展：

上世纪70年代，IBM利用统计方法将语音识别率从70%提到90%，基于统计的方法核心模型是通信系统加隐含马尔科夫模型（这个系统的输入输出都是一维符号系列，且保持原有次序）；

80年代，IBM提出提出基于统计的机器翻译方法，因数据、模型欠缺，解决不了语序颠倒问题；

90年代，随着计算机能力的提高和数据量的增加，统计方法得以实现

第3章 统计语言模型

讲述如何利用统计语言模型处理自然语言，以及如何确保结果的准确性、减少不平滑。

统计语言模型：用来处理自然语言的上下文关系，它是所有自然语言处理的基础。并广泛应用于机器翻译、语音识别、印刷体或手写体识别、拼音纠错、汉字输入和文献查询。

利用概率大小来衡量一个文字序列是否能构成大家理解而且有意义的句子：

序列S出现的概率W，等于序列中每一个词出现的条件概率相乘，W出现的概率同他前面的所有词有关，即P（S）=P（W1，W2，...，Wn）=P（W1）P（W2|W1）P(W3|W1,W2)...P(Wn|W1,W2，...,W(n-1)）。

由于计算复杂，所以就假设任意一个词Wi出现的概率只同它前面的词W（i-1）有关，即P（S）=P（W1）*P（W2|W1）...P（Wi|W(i-1)）...P(Wn|W(n-1))）

P（W(i-1)，Wi）=#(W(i-1)，Wi)/# （注：#（W(i-1)，Wi）为W(i-1),Wi这对词在统计的文本中前后相邻出现的次数，#为语料库的大小）

N-1阶马尔科夫模型：

假设文本中的每个词Wi和前面的N-1个词有关系，而与更前面的词无关，则P（Wi|W1，W2，...，W(i-1)）=P(Wi|W(i-n+1)，W(i-n+2)，...,W(i-1)）。

n=1的一元模型实际上是一个上下文无关的模型，n的值一般为2，或3。n值很少取更高值的原因，一是n越大，复杂度n方越大；二是自然语言中上下文的相关性可能跨度非常大，甚至可以从一个段落跨到另一个段落，所以即使模型阶数n再高，也没有太多意义。这是马尔科夫假设的局限。

模型的训练：通过对语料的统计，得到模型中的参数。

大数定理： 在试验不变的条件下，重复试验多次，随机事件的频率近似于它的概率。偶然中包含着某种必然。

我们需要足够的语料才能得到较为可靠的概率。然而语料过多，可能会导致大部分条件概率为0的情况，这种模型叫做“不平滑”。

减少不平滑：

古德-图灵估计，对于没有看见的事件，我们不能认为它的发生概率就是零，因此我们从概率的总量中，分配一个很小的概率给予这些没有看见的事件。这样一来，看见的时间的概率总和就要小于1了。即“越是不可信的统计折扣越多”。

设语料库中出现r次的词有Nr个，则当r比较小时，它的统计可能不可靠，经过古德-图灵估计后的相对频度r’=（r+1）*N(r+1)/N(r).

删除插值法，因为一元组（Wi）出现的次数平均比二元组（W(i-1)，Wi）出现的次数要高得多，根据大数定理，它的频度更接近概率分布。所依，用低阶语言模型和高阶模型进行线性差值来达到平滑的目的。即连续三个字出现的概率=T倍连续三个字出现的概率+t倍连续两个字出现的概率+（1-T-t）倍该字单独出现的概率

语料的选取：

训练语料和模型应用的领域须保持一致，以减少噪音；语料数据通常是越多越好，可以利用平滑过渡方法解决小/零概率事件；最好能预处理能具有规律的、量比较大的噪音。

第4章 谈谈中文分词

利用统计模型进行自然语言处理，这些语言模型是建立在词的基础上的，因为词是语义的最小单位。在此之前，需要对句子进行分词。

常见分词方法——查字典：

把一个句子从左往右扫描一遍，遇到字典里有的词就标识出来，遇到复核词（如“上海大学”）就找最长的词匹配，遇到不认识的字串就分割成单字词。该方法能解决七八成问题，然而对二义性的分割无能为力（如发展-中-国家、发展-中国-家）。

处理二义性：

最好的分词方法应该保证分完词后，该句子出现的概率最大，但是如果穷举所有的分词方法并计算所有可能的概率，计算率太大。对此，不同的应用，分词的颗粒度应采用不同的大小，即不同的应用应该有不同的分词系统。

关于词的颗粒度和层次：

不同的人对词的切分方法差异甚大，其主要原因是对词的颗粒度的认识不一致。在不同的应用中，词的颗粒度可能很不一样，如在机器翻译中，颗粒度大翻译效果好，在网页搜索中则相反。如果对不同的应用构造不同的分词系统，会很浪费，最好的方法是让一个分词器同时支持不同层次的词的切分，然后由不同的应用自行决定采用哪个颗粒的切分。

分词器的准确性：

应避免越界型错误、覆盖型错误、颗粒不一致。越界型错误，如“北京大学生”分为“北京大学——生”。覆盖型错误，如"贾里尼克”拆成了四个字。错误要尽可能消除。关于颗粒不一致，需要多做些数据挖掘工作，完善不同应用的复合词词典。

第5章 隐含马尔可夫模型

通信的过程本质上就是：发送者编码——信道传播——接收者解码。如何根据接收端的观测信号O1,O2,...O3...来推测信号源的发送信息S1,S2,S3,...呢？我们需要从所有的信息源中找到最可能产生观测信号的那一个信息。

隐含马尔可夫模型：

假设模型在每个时刻t会输出一个符号Ot，而且Ot仅和St相关（即马尔科夫假设），我们可以计算出某个特定状态序列S1,S2,S3,...产生输出符O1,O2,...O3...号的概率。如何让找到概率最大值，需运用维特比算法（后面会提到）。（注：St可能会生成Ot，即生成概率；也可能会转化为S(t-1)，即转移概率）

隐含马尔科夫模型的训练：

首先有三个基本问题：1、给定一个模型，如何计算某个特定输出序列的概率；2、给定一个模型和某个特定的输出序列，如何找到最可能产生这个输出的状态序列；3、给定足够的观测数据，如何估算隐含马尔可夫模型的参数。

问题1可参考贾里尼克《Statistical Methods for Speech Recognition 》，问题2使用维特比算法来解码（后面会提到）。

关于问题3。通过大量的观察信号推测模型参数的生成概率、转移概率，以寻找最可能的模型，主要使用的是鲍穆-韦尔奇算法。首先，找到能够产生O序列的模型参数；然后，计算出这个模型产生O的概率，以及产生O的所有可能路径和产生这些路径的概率。最终，计算出一组新的模型参数，根据新的模型参数再继续寻找更好的模型参数。以此类推，直到目标函数的输出概率达到最大化。这个过程被称为期望最大化，即EM。EM能保证算法收敛到一个局部最优点，却不能保证找到全局最优点。

第6章 信息的度量和作用

信息嫡：即我们弄清楚一件事所需要的信息量。信息量就等于不确定性的多少。假设一件事由n部分组成，每件事发生的概率为p(i)，则该事信息嫡为H=-（p1.logp1+p2.logp2+...+pn.logpn），单位是比特。可以用来衡量统计语言模型的好坏。

信息的作用在于消除不确定性，这些信息可以针对事物本身，也可以是与关注对象相关的信息。

条件嫡：假定x和y是两个随机变量，我们知道了y随x一起出现的概率，以及x的概率，那我们就可以求出y的概率。

互信息就是对两个随机事件“相关性”的量化度量。例举互信息在解决词义二义性上的运用，bush一词可以解释为：灌木丛、布什，区分办法如下：首先从大量文本中找出和总统布什一起出现的互信息最大的一些词，比如：总统、美国、国会等；同理找出和灌木丛一起出现的互信息量大的词，比如土壤、树木、植物等。翻译时，看看上下文中哪类相关的词多就可以了。

相对嫡也可以用来衡量两个取值为正数的函数相关性。相对嫡越大，两个函数的差异越大；反之差异越小。对于概率分布或者概率密度函数，如果取值均大于零，相对嫡可以度量两个随机分布的差异性，如用来衡量两个常用词在不同文本中的概率分布，看它们是否同义，或者根据两篇文章中不同词的分布，看看它们的内容是否相近。

因为有了上下文条件，所以对于高阶的语言模型，应该用条件嫡；如果再考虑从训练语料和真实应用的文本中得到的概率函数有偏差，就需要再引入相对嫡的概念。

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

贾里尼克和作者花在学校里读书的时间比99%的孩子都少，却比他们的建树都高。他们都认为，第一，小学生没和中学生其实没必要花那么多时间读书，而他们的社会经验、生活能力以及在那时树立起的志向将帮助他们的一生。第二，中学阶段花很多时间比同伴多读的课程，在大学以后用非常短的时间就可以读完，因为大学阶段，人的理解力要强得多。第三，学习是一辈子的事，兴趣是最好的动力。第四，书本的内容可以早学，也可以晚学，但是错过了成长阶段确是无法弥补回来的。

第8章 简单之美——布尔代数和搜索引擎的应用

技术分为术和道两种，具体的做事方法是术，做事的原理和原则是道。追求术的人一辈子工作都很辛苦，只有掌握了搜索的本质和精髓才能游刃有余。真正做好一件事没有捷径，作者在Google做搜索时，每天至少要分析20个左右不好的搜索结果。

搜索引擎的原理：自动下载尽可能多的网页；建立快速有效的索引；根据相关性对网页进行公平准确的排序。

布尔代数：元素（真、假）、基本运算（与、或、非）。文献检索时，需要根据是否含关键字返回相应的参数：真或假。这样逻辑推理和计算就合二为一了。

索引：是一张大表，表的每一行对应一个关键字，以及包含该关键字的文献序号。为方便网页排名，索引中还有一些附加信息，诸如每个词出现的位置、次数等等，使得索引变得非常之大，一台服务器难以存储。普遍的做法是根据网页的序号将索引分成很多份，分别存储在不同的服务器中，这些服务器同时并行处理用户的请求，并把结果送到主服务器进行合并处理，最终将结果返回给用户。

需要根据网页的重要性、质量和访问的频率建立常用和非常用等不同级别的索引。常用的索引需要访问速度快、更新快，附加信息多。

真理在形式上从来是简单的，而不是复杂和含混的。

第9章 图论和网络爬虫

图论中的遍历算法：

图论中的图由一些节点和连接这些节点的弧组成。顺着弧把所有的节点都走一遍，记录访问过的节点，同时避免多次访问或漏掉某个节点，该方法叫做遍历。常见遍历算法有广度优先（BFS-尽可能广得访问每一个节点所直接连接的其他节点）和深度优先（DFS-从头一路走到黑）。

网络爬虫：有了超链接，我们可以利用遍历算法，自动地访问每一个网页，并把它们存起来。完成该功能的程序即网络爬虫。

图论定理：如果一个图能够从一个顶点出发，每条边不重复地遍历一遍回到这个顶点，那么每个顶点的度必须为偶数。（若想回到顶点，则有多少出去的边，就要有多少进入的边）

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

1、采用BFS还是DFS？即如何在有限的时间里最多地爬下最重要的网页。

对于某个网站来说，首页最重要，其次是首页的链接，链接越深越相对不重要。所以，在下载某一个互联网的具体内容时，BFS优先于DFS。

但是，在网路通信的握手成本上，DFS优先于BFS。“握手”就是指下载服务器网站和网站服务器建立通信的过程。如果握手的次数太多，下载的效率就降低。对于某个网站，一般是由特定的一台或几台服务器专门下载。这些服务器下载完一个网站，再去下载另一个网站，而不是先下载一部分，再来回折腾。

所以，同时存在DFS、BFS。有一个调度系统来存储那些已经发现但尚未下载的网页URL，且按优先级排列。

2、页面的分析和URL的提取

以html语言书写的网页，解析起来比较简单；以脚本js等书写网页，解析起来较为困难，需要做浏览器的内核工程师来做。

3、记录哪些网页URL已经下载过——哈希表

如果同时有上千台服务器一起下载网页，维护一张统一的哈希表就比较麻烦。首先，哈希表会大到一台服务器存储不下，其次由于每个下载服务器在开始下载前和完成下载后都需要访问和维护这张表，以免不同的服务器重复工作，存储这张哈希表的服务器的通信就成为了整个爬虫系统的瓶颈。

好的方法一般采用两个技术：首先明确每台服务器的分工，也就是在调度时一看到某个URL就知道要交给哪台服务器去下载，这样就避免了很多服务器对同一个URL做出是否要下载的判断。然后，在明确分工的基础上，可以批量判断URL是否下载，比如每次向哈希表发送一大批询问，或者每次更新一大批哈希表的内容，以减少通信的次数。

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

对于一个特定的查询，搜索结果取决于网页的质量信息，和这个查询与每个网页的相关性信息。

pagerank算法核心思想：如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖。比如说，对于来自不同网页的链接区别对待，因为网页排名高的网页链接更可靠，于是要给这些链接以较大的权重。

计算结果的网页排名需要用到网页本身的排名。布林破解了这个怪圈，把这个问题变成了一个二维矩阵相乘的问题。先假设所有的网页排名是相同的，并根据这个初始值，算出各个网页的第一次迭代排名，然后根据第一次迭代排名算出第二代的排名。

网页排名的高明之处在于它把整个互联网系统当作一个整体对待。以前的信息检索把每个网页当做独立的个体对待，只注意到网页内容和查询语句的相关性，忽略了网页之间的关系。

pagerank的计算方法

假定向量B=[b1;b2;...bn]为第一、第二...第n个网站的网页排名。初始值为B0=[1/n；1/n...；1/n]

矩阵A=[a11 ...a1n...a1m；...；am1...amn...amm；...；am1 ...amn...amm]为网页之间的链接数目，其中amn代表第m个网页指向第n个网页的链接数。A已知，B未知。

假定Bi是第i次迭代结果，那么Bi=A*Bi-1。最终Bi会收敛于B，当Bi与Bi-1的结果差异非常小时，就可以停止迭代运算。（注：计算访问概率较小的网站时，需要做平滑处理）

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

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

某关键词频率TF=关键词的次数/该网页的总字数。这个查询和该网页的相关度=TF1+TF2+...+TFn。由于每个词的重要程度不一样，所以给每个词设置权重时，需满足如下两个条件：

1、一个词的预测主题能力越强，权重越大；反之，权重越小。

2、停止词的权重为零。如果一个词只在很少的网页中出现，通过它就容易锁定目标，它的权重也就应该大；反之，类似“的、是”等词，权重应该小。概括地将，假定一个词w在Dw个网页中出现过，那么Dw越大，w的权重越小。使用最多的权重是“逆文本频率指数”，即IDF=log（D/Dw）,其中，D是全部网页数。

所以，得到相关性的计算公式TF-IDF=TF1IDF1+TF2IDF2+...+TFn*IDFn

TF-IDF的信息论依据？？P136

第12章 地图和本地搜索的最基本技术

智能手机的定位和导航功能涉及3个关键技术：利用导航仪进行卫星定位，地址的识别，根据用户输入的起点和终点，在地图上规划最短路线或者最快路线。

有限状态机：是一个特殊的有向图，包括一些状态（节点）和连接这些状态的有向弧。每一个有限状态机有一个开始状态和一个终止状态，以及若干中间状态。每一条弧上带有从上一个状态进入下一个状态的条件。如果输入的符号可以从状态机的开始状态经过中间状态，走到终止状态，那么这条地址就有效，否则无效。

有限状态机是一个五元组，输入符号的集合、非空的有限状态的集合S、初始状态S0、从输入到有限状态的映射函数、终止状态。如果输入和输出的可能性不同，也可以给赋予每条边权重。

使用有限状态机识别地址，关键要解决两个问题，即通过一些有效的地址建立状态机，以及地址字串的匹配算法。

有限状态机只能进行严格匹配，当用户输入存在错误时，则无法识别。基于概率的有限状态机可以解决该问题（效果等同马尔可夫链，相当于给每个有向弧加上概率）

动态规划——解决最短路径：

加权图：一个抽象的图包括节点和连接他们的弧，以及每条弧的权重。找到一个图中给定两点间的距离，最直接的办法就是计算出所有的路径权重，找出最优的。不过可能路径数量随着节点数的增长而成指数增长，复杂度过高。

假设已经找到了从北京到广州的最短路径，且经过郑州，那么从北京到郑州的这条子径也是所有从北京到郑州的路线中最短的。反过来想，如果想要找到从北京到广州的最短路线，先要找到北京到郑州（即某个必经的中间节点）的最短路线。如何找到必经的中间节点？

只要在图上横切一刀，这一刀一定要保证将任何从北京到广州的路线一分为二（怎么切？？）。那么从广州到北京的最短路径必须经过这一条线上的某个城市。我们可以先找到从北京出发到这条线上所有城市的最短路径，最后得到的全城最短路线一定包括这些局部最短路线中的一条，这样，就可以将一个“寻找全城最短路线”的问题，分解成一个个寻找局部最短路线的小问题。

第13章 Google ak-47 的设计者

从辛格身上学到的：

先帮助用户解决80%的问题，再慢慢解决剩下20%的问题。一开始追求大而全，可能长时间不能完成，最后不了了之。

坚持选择简单方案的另一个原因是容易解释每一个步骤和方法背后的道理，这样不仅便于出了问题时查错，而且容易找到今后的改进目标。

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

总结：求特征向量时，要先计算TF-IDF（即每篇文章中关键词的词频 乘以 关键词的权重。权重与关键词在语料库文章中的集中/分散程度，以及关键字在文章中的位置有关。）。计算余弦相似度时，要注意矩阵存储大小及计算复杂度。

对于一篇新闻中所有的实词，计算出它们的TF-IDF值，没有出现的词的TF-IDF为零。把这些词按照对应的实词在词汇表的位置依次排列，就得到一个多维向量，即该新闻的特征向量，向量中每一个维度的大小代表每个词对这篇新闻主题的贡献度。

同一类新闻一定是某些主题词用得较多，即它们的特征向量在某几个维度上的值都比较大。如果不属于同一类，则较大的特征向量应该没什么交集。由于每篇新闻的文本长度不同，所以特征向量各个维度的数值也不同。单纯比较各个维度的大小没有太大意义。但是向量的方向却有很大意义。如果两个向量的方向一字，说明对应的新闻用词的比例也基本一致。因此可以利用余弦定理计算两个向量的夹角来判断对应新闻主题的接近程度。

有两种计算方法：

第一种假设我们已知一些新闻类别的特征向量，计算出要被分类的新闻和各类新闻特征向量的余弦相似性，余弦越小，相似度越高。

第二种假设我们不知道这些新闻类别的特征向量，则我们要计算出所有新闻两两之间的余弦相似性，把相似性大于一个阈值的新闻合并成一个小类，然后把每个小类中的所有新闻作为一个整体，并计算出小类的特征向量，再计算出所有小类之间两两的余弦相似性，然后把小类合并成大一点的小类，以此类推，直到小类之间的余弦相似度很小时，就可以停止迭代了。

计算向量余弦的技巧：

计算N篇新闻之间的两两相关性，一次迭代计算复杂度为N方，计算量较大。简化方法如下：首先，分母（向量的长度）不需要重复计算，第一次计算余弦以后，长度可以存起来。其次，只考虑向量中的非零元素即可，这样一来复杂度取决于两个向量中非零元素个数的最小值。第三，删除虚词，如“因为、是、的、如果”等等，既提高了计算速度，又减少了干扰。

标题中的词对主题的贡献要大于正文中的；出现在文章首尾中的词比中间部分的词重要。所以，可以对重要位置的词进行额外的加权，以提高文本分类的准确性。

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

将文本按主题归类与将词汇表中的词按意思归类，需要多次迭代计算相似度，耗时较长。可以利用矩阵运算中的奇异值分解来一次性计算相关性。

首先，要用一个大矩阵A描述成千上万篇文章和百万个词的关联性。在矩阵中，每一行对应一篇文章，每一列对应一个词，导致矩阵非常大。奇异值分解就是将大矩阵分解成三个小矩阵相乘。

第一个矩阵X是对词进行分类的一个结果，每一行代表一个词，每一列表示一个语义相近的词类。第三个矩阵Y是对文本分类的结果，每一列对应一个文本，每一行对应一个主题，每一列可以只保留最大值，其余的都改为零，那么每一篇文本都被唯一地分到一类主题中。中间的矩阵B则表示词的类和文章的类之间的相关性，每一行代表一篇文章，每一列代表一个词。

A=X *B *Y。分解后，可以同时完成近义词分类和文章的分类，以及每个主题和每个词的语义类之间的相关性。

相比于利用文本特征向量余弦的距离自底向上聚类的方法，奇异值分解的优点是能较快速地得到结果，因为它不需要一次次迭代。但这种方法得到的分类结果略显粗糙。实际工作中，可以先进行奇异值分解得到粗分类结果，再利用计算向量余弦的方法，在粗分类结果的基础上，迭代得到更精确的结果。

P169奇异值分解的方法？？

第16章 信息指纹及其应用

一段文字所包含的信息，就是它的信息嫡。如果对这段信息进行无损压缩编码，理论上编码后的最短长度就是它的信息嫡。但是，如果仅仅要区分两段文字或者图片，则远不需要那么长的编码。任何一段信息，都可以对应一个不太长的随机数，作为区分它和其他信息的指纹。

信息指纹的用途：

网址消重：比如一般网址由字符串组成，长度不固定，所以查找困难，占用容量较大。可以将字符串看成是一个特殊的、长度很长的整数，利用伪随机数产生算法器，将其转换成特定长度的伪随机数，即信息指纹。

密码：cookie也是一种信息指纹，网站无法根据信息指纹了解用户的身份，这样可以起到保护隐私的作用。信息指纹具有不可逆性。

网络爬虫：可以利用信息指纹判断一个网址是否已经下载过。

判定集合相同：计算两个集合元素的信息指纹，由于加法的交换律，保证集合的指纹不因元素出现的次序而改变，如果两个集合元素相同，那么它们的信息指纹一定相同。

判定集合基本相同：比较两个网页是否相同，只需找出每个网页中IDF最大的几个词，计算并比较他们的信息指纹。

反盗版：提取并比较视频的关键帧

P151相似哈希计算方法？（能看懂，原因？？）

第17章 由电视剧《暗算》所想到的

加密的过程可以看做是一个函数的运算F，解密的过程是反函数运算。明码是自变量，密码是函数值。好的加密函数不应该通过几个自变量和函数值就能推导出函数。

一般来讲，当密码之间分布均匀并且统计独立时，提供的信息最少。均匀使得敌人无从统计，而统计独立能够保证敌人即使看到一段密码和明码后，不能破译另一段密码。

设计一个密码系统：

1、找两个很大的素数（质数）P和Q，越大越好，然后计算他们的乘积：

N=P * Q，M=（P-1）*（Q-1）

2、找一个和M互素的整数E，找一个整数D，使得E*D mod M=1（mod为两个表达式作除法运算后的余数）。E是公钥，谁都可以用来加密，D是私钥用于解密，一定要自己保存好。乘积N是公开的。

3、用公式对X加密，得到密码Y= X的E次方 mod N。根据费尔马小定理，得到：X=Y的D次方 mod N，所以要解密，必须知道D。

公开密钥的好处有：简单，只涉及一些乘法；可靠，公开密钥方法保证产生的密文是统计独立而分布均匀的。更重要的是N、E可以公开给任何人加密使用，但只有掌握密钥D的人才能解密；灵活，可以产生很多E和D的组合给不同的加密者。

该种方法破解难度较大，破解的最好办法是对大数N进行因式分解，即通过N反过来找P、Q，得到M、N。而找到P、Q目前只有用计算机把所有的数字试一遍的笨办法，耗时很长。这也是为什么P、Q都需要非常大的原因。

第18章 闪光的不一定是金子——谈谈搜索引擎

搜索反作弊也存在道和术两种境界：

术：分析作弊的例子，分析它，然后清除它，这种方法能解决问题，且不需要太动脑筋，但工作量较大，难以从个别现象上升级到普遍规律。道：通过具体的作弊例子，找到作弊的动机和本质，从本质上解决问题。

在通信中解决噪音抗干扰问题的基本思路有两条：

从信息源出发，加强通信编码自身的抗干扰能力；从传输上看，过滤掉噪音，还原信息。

卖链接的网站，都有大量的出链。每一个网站到其它网站的出链数目可以作为一个向量，它是网站的固有特征。既然是向量就可以计算出余弦距离。通常情况下，这些网站的出链向量之间的余弦距离几乎为1。

运用图论。作弊网站一般需要互相链接，以提高排名。这样就在互联网这张大图中形成了一些Clique。

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

一个正确的模型应当在形式上是简单的。

一个正确的模型可能一开始还不如一个精雕细琢过的错误模型来得准确，但是，如果我们认定大方向是对的，就应该坚持下去。

大量的准确数据对研发很重要。

正确的模型也可能受噪音干扰，而显得不准确；这时不应该用一种凑合的修正方法来弥补它，二是要找到噪音的根源，这样也许能通往重大的发现。

第20章 不要把鸡蛋放到一个篮子里

最大嫡原理指出，需要对一个随机事件分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。在这种情况下，概率分布最均匀，预测风险最小。因为这时，概率分布的信息嫡最大，所以叫“最大嫡模型”。总结一句话就是：当我们不确定时，就要保留各种可能性。

P208最大嫡模型公式及训练？？

通用迭代算法GIS：

假定第零次迭代的初始模型为等概率的均匀分布；用第n次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过实际的，则把相应参数变小，反之，则变大；重复步骤2直至收敛。

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

输入法输入汉字的快慢取决于对汉字编码的平均长度，即击键次数乘以寻找这个键所需要的时间。

拼音输入法的优点：第一，不需要专门学习；第二，输入自然，不会中断思维，也就是说找每个键的时间非常短。第三，因为编码长，有信息冗余，容错性好。如果把字换成词，每个汉字的信息嫡将会减少。如果能更多地利用上下文相关性，当输入一半的时候，可能已经看到自己要找的字了。

拼音转汉字的算法：

输入法就是将拼音串变为汉字串的转换器。一个拼音可以对应多个汉字，把一个拼音对应的汉字从左到右连起来，就是一张有向图，它被称为网格图或篱笆图。

从第一个汉字到最后一个汉字可以对应很多很多句子，每一个句子和图中的一条路径一一对应。拼音输入法就是要根据上下文在给定拼音条件下找到一个最优的句子（可以参考隐含马尔可夫，前后汉字关系可以只考虑二阶关系，求出概率最大的句子）。

个性化的语音模型：

每个人的输入习惯不同，可以找到大量符合用户经常输入的内容和用语习惯的语料，训练出一个用户特定的语言模型，步骤如下：

将训练语言模型的文本按照主题分成很多不同的类别，对于每个类，找出它们的特征向量；

统计某个人输入的文本，得到他输入的词的特征向量Y；

计算Y和每个分类特征向量的余弦相似度，并选择前K个和Y距离最近的类对应的文本，作为这个特定用户的语言模型训练数据；

训练出用户特定的语言模型M1。大部分情况下，M1对这个用户的输入比通用模型M0要好。但是相对于偏僻的内容，M1覆盖语言较少，效果就不如M0了。所以最好是综合二者（线性关系）。

第22章 自然语言处理的教父马库斯

第23章 布隆过滤器

布隆过滤器实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器过滤垃圾邮件的工作原理：对于每一个电子邮件地址，用8个不同的随机数产生器产生8个信息指纹（f1，f2，...f8）。再用一个随机数产生器把这8个信息指纹映射到布隆过滤器的8个二进制位，并把这8个位置的二进制全部设置为1。

如果邮件在黑名单中，该邮件经过两次映射最终得到的8个二进制位都是1。

布隆过滤器优点在于快速、省空间，但是有一定的误识别率。常见的办法是再建立一个小的白名单，存储那些有可能被误判的邮件地址。

P207布隆过滤器的误识别问题？？

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

贝叶斯网络：有很多节点（状态），节点之间通过有向弧连接，各个节点之间的相互转化可能存在一定的概率。

首先确定贝叶斯网络的结构。优化结构要保证它产生的序列从头到尾的可能性最大，即后验概率最大。寻找全局最优的路径，一般采用贪婪算法，也就是在每一步时，沿着箭头的方向寻找有限步。若要避免局部最优，就要用许多随机数在贝叶斯网络中试一试，看看是否有更好的方法。

然后，要通过参数训练确定这些节点之间的弧的权重（参考前面提到的EM过程）。实际上，结构的训练和参数的训练是交替进行、不断优化的，直至得到收敛或者误差较小的模型。

第25章 条件随机场和句法分析

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

维特比算法是一个特殊的但应用最广泛的动态规划算法，维特比算法主要解决篱笆网络的有向图的最短路径问题。它之所以重要，是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码。

对于每一个给定的起始点、终止点，如果列出所有可能的路径，从中找出最短路径，计算复杂度呈指数增长。

P230维特比算法：假设在隐含马尔可夫链中，总共有N个节点，节点最多的状态有D个节点，也就是整个网格的宽度为D，那么找出任何相邻两个状态节点的最短路径的复杂度不超过 D的平方。由于网格的长度是N，所以整个维特比的复杂度不超过 N*D的平方。（确定节点的状态顺序？？）

第27章 再谈文本自动分类问题——期望最大化EM

文本的自收敛分类：

不同于TF-IDF利用余弦相似度来进行分类，这里不需要事先设定好类别，也不需要对文本两两比较进行合并聚类。而是随机挑选一些类的中心，然后来优化这些中心，使它们和真实的聚类中心尽可能一致。步骤如下：

假设有很多点随机分布，随机挑选k个点作为聚类的中心；分别计算出所有点到这些聚类中心的距离，将这些点归到最近的一类中；重新计算每一类的中心（分别计算每个维度的平均值）；重复上述过程，直到新的中心和旧的中心之间偏移非常非常小，即过程收敛。

如何确保期望最大化：

首先，我们的距离函数必须足够好，能保证同一类相对距离较近，不同类相对距离较远。我们希望最终的分类结果是：相近的点都被聚类到了一类中，即同一类中各个点到中心距离的平均距离d较近，而不同类中心之间的平均距离D较远。

EM算法——上帝的算法：

在一般性的问题中如果有很多观测值，可以让计算机不断迭代来学习一个模型。首先，根据现有的模型，计算出观测数据输入到模型中的结果，这个过程为期望值计算过程（Expectation，E过程）；接下来，重新计算模型参数，以最大化期望值（文本分类中是最大化D和-d），该过程为最大化过程（Maximization，M过程）。统称为EM算法。

EM算法只需要有一些训练数据，定义一个最大化函数，剩下的事就交给计算机了。经过若干次迭代，达到收敛或误差最小化，模型就训练好了。是一个通用的算法。

EM算法不一定能得到全局最优解，如果目标函数是凸函数，就可以；如果是凹函数，则可能得到的是局部最优解。

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

广告搜索跟很多因素相关，如以前的经验值、统计数据的大小、摆放的位置、广告费等等。

逻辑回归模型

f（z）=e的z次方/(e的z次方+1）。

将一个事件出现的概率适应到一条逻辑曲线上。逻辑曲线是一条S型曲线，其特点是开始变化快，逐渐减慢，最后饱和。其好处是自变量范围是负无穷到正无穷，而值域范围限制在0~1之间，不论自变量如何组合，总能得到一个概率分布。

假设有n个影响广告点击率的变量x1，x2，...xn。设自变量z=k0+k1x1+k2x2+...+knxn。（ki是自回归参数，k0是一个特殊的参数，保证在没有任何信息时，有一个稳定的分布）

可以通过最大嫡-GIS算法来训练逻辑回归函数的参数。

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

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

分治算法：将一个复杂的问题，分成若干简单的子问题进行解决。然后，对子问题的结果进行合并，得到原有问题的解。

通过分治算法实现矩阵相乘C=A*B：将矩阵A、B划分为小的矩阵，分别放到不同的服务器上计算求得中间值，再进行合并。