转自：http://book.douban.com/annotation/19461092/


       半个月前在豆瓣上看到了一本新书《数学之美》，评价很高。而因为在半年前看了《什么是数学》就对数学产生浓厚兴趣，但苦于水平不足的我便立马买了一本，希望能对数学多一些了解，并认真阅读起来。
       令我意外并欣喜的是，这本书里边的数学内容并不晦涩难懂，而且作者为了讲述数学之美而搭配的一些工程实例都是和我学习并感兴趣的模式识别，目标分类相关算法相关联的。这让我觉得捡到了意外的宝藏。
        书中每一个章节都或多或少是作者亲身经历过的，比如世界级教授的小故事，或者Google的搜索引擎原理，又或者是Google的云计算等。作者用其行云流水般的语言将各个知识点像讲故事一样有趣的叙述出来。
        这本书着实让我印象深刻，所以我把笔记分享出来，希望更多和我学习研究领域一样的人会喜欢并亲自阅读这本书，并能支持作者。毕竟国内这种书实在是太少了，也希望能有更多领域内的大牛能再写出一些这种书籍来让我们共同提高。
1.    因为需要传播信息量的增加，不同的声音并不能完全表达信息，语言便产生了。
2.    当文字增加到没有人能完全记住所有文字时，聚类和归类就开始了。例如日代表太阳或者代表一天。
3.    聚类会带来歧义性，但上下文可以消除歧义。信息冗余是信息安全的保障。例如罗塞塔石碑上同一信息重复三次。
4.    最短编码原理即常用信息短编码，生僻信息长编码。
5.    因为文字只是信息的载体而非信息本身，所以翻译是可以实现的。
6.    2012，其实是玛雅文明采用二十进制，即四百年是一个太阳纪，而2012年恰巧是当前太阳纪的最后一年，2013年是新的太阳纪的开始，故被误传为世界末日。
7.    字母可以看为是一维编码，而汉字可以看为二维编码。
8.    基于统计的自然语言处理方法，在数学模型上和通信是相通的，甚至是相同的。
9.    让计算机处理自然语言的基本问题就是为自然语言这种上下文相关的特性建立数学模型，即统计语言模型（Statistical Language Modal）。
10.    根据大数定理（Law of Large Numbers），只要统计量足够，相对频度就等于概率。
11.    二元模型。对于p(w1,w2,…,wn)=p(w1)p(w2|w1)p(w3|w1,w2)…p(wn|w1,w2,…,wn-1)的展开问题，因为p(w3|w1,w2)难计算，p(wn|w1,w2,…,wn-1)更难计算，马尔科夫给出了一个偷懒但是颇为有效的方法，也就是每当遇到这种情况时，就假设任意wi出现的概率只与它前面的wi-1有关，即p(s)=p(w1)p(w2|w1)p(w3|w2)…p(wi|wi-1)…p(wn|wn-1)。现在这个概率就变的简单了。对应的语言模型为2元模型（Bigram Model）。
12.    *N元模型。wi只与前一个wi-1有关近似的过头了，所以N-1阶马尔科夫假设为p(wi|w1,w2,…,wi-1)=p(wi|wi-N+1,wi-N+2,…,wi-1)，对应的语言模型成为N元模型（N-Gram Model）。一元模型就是上下文无关模型，实际应用中更多实用的是三元模型。Google的罗塞塔翻译系统和语言搜索系统实用的是四元模型，存储于500台以上的Google服务器中。
13.    *卡兹退避法（Katz backoff），对于频率超过一定阈值的词，它们的概率估计就是它们在语料库中的相对频度，对于频率小于这个阈值的词，它们的概率估计就小于他们的相对频度，出现次数越少，频率下调越多。对于未看见的词，也给予一个比较小的概率（即下调得到的频率总和），这样所有词的概率估计都平滑了。这就是卡兹退避法（Katz backoff）。
14.    训练数据通常是越多越好，通过平滑过渡的方法可以解决零概率和很小概率的问题，毕竟在数据量多的时候概率模型的参数可以估计的比较准确。
15.    利用统计语言模型进行分词，即最好的分词方法应该保证分完词后这个句子出现的概率最大。根据不同应用，汉语分词的颗粒度大小应该不同。
16.    符合马尔科夫假设（各个状态st的概率分布只与它前一个状态st-1有关）的随即过程即成为马尔科夫过程，也称为马尔科夫链。
17.    隐含马尔科夫模型是马尔科夫链的扩展，任意时刻t的状态st是不可见的，所以观察者没法通过观察到一个状态序列s1,s2,s3,…,sT来推测转移概率等参数。但是隐马尔科夫模型在每个时刻t会输出一个符号ot，而且ot和st相关且仅和ot相关。这个被称为独立输出假设。其中隐含的状态s1,s2,s3,…是一个典型的马尔科夫链。
18.    隐含马尔科夫模型是机器学习主要工具之一，和几乎所有机器学习的模型工具一样，它需要一个训练算法（鲍姆-韦尔奇算法）和使用时的解码算法（维特比算法）。掌握了这两类算法，就基本上可以使用隐含马尔科夫模型这个工具了。
19.    鲍姆-韦尔奇算法（Baum-Welch Algorithm），首先找到一组能够产生输出序列O的模型参数，这个初始模型成为Mtheta0，需要在此基础上找到一个更好的模型，假定不但可以算出这个模型产生O的概率P(O|Mtheta0)，而且能够找到这个模型产生O的所有可能的路径以及这些路径的概率。并算出一组新的模型参数theta1，从Mtheta0到Mtheta1的过程称为一次迭代。接下来从Mtheta1出发寻找更好的模型Mtheta2，并一直找下去，直到模型的质量没有明显提高为止。这样一直估计（Expectation）新的模型参数，使得输出的概率达到最大化（Maximization）的过程被称为期望值最大化（Expectation-Maximization）简称EM过程。EM过程能保证一定能收敛到一个局部最优点，但不能保证找到全局最优点。因此，在一些自然语言处理的应用中，这种无监督的鲍姆-韦尔奇算法训练处的模型比有监督的训练得到的模型效果略差。
20.    熵，信息熵的定义为H(X)=-SumP(x)logP(x)，变量的不确定性越大，熵也越大。
21.    一个事物内部会存在随机性，也就是不确定性，假定为U，而从外部消除这个不确定性唯一的办法是引入信息I，而需要引入的信息量取决于这个不确定性的大小，即I>U才行。当I<U时，这些信息可以消除一部分不确定性，U'=U-I。反之，如果没有信息，任何公示或者数字的游戏都无法排除不确定性。
22.    信息的作用在于消除不确定性。
23.    互信息，对两个随机事件相关性的量化度量，即随机事件X的不确定性或者说熵H(X)，在知道随机事件Y条件下的不确定性，或者说条件熵H(X|Y)之间的差异，即I(X;Y)=H(X)-H(X|Y)。所谓两个事件相关性的量化度量，即在了解了其中一个Y的前提下，对消除另一个X不确定性所提供的信息量。
24.    相对熵（Kullback-Leibler Divergence）也叫交叉熵，对两个完全相同的函数，他们的相对熵为零；相对熵越大，两个函数差异越大，反之，相对熵越小，两个函数差异越小；对于概率分布或者概率密度函数，如果取值均大于零，相对熵可以度量两个随机分布的差异性。
25.    弗里德里克·贾里尼克（Frederek Jelinek）是自然语言处理真谛的先驱者。
26.    技术分为术和道两种，具体的做事方法是术，做事的原理和原则是道。术会从独门绝技到普及再到落伍，追求术的人会很辛苦，只有掌握了道的本质和精髓才能永远游刃有余。
27.    真理在形式上从来是简单的，而不是复杂和含混的。
28.    搜索引擎不过是一张大表，表的每一行对应一个关键字，而每一个关键字后面跟着一组数字，是包含该关键词的文献序号。但当索引变的非常大的时候，这些索引需要通过分布式的方式存储到不同的服务器上。
29.    网络爬虫（Web Crawlers），图论的遍历算法和搜索引擎的关系。互联网虽然复杂，但是说穿了其实就是一张大图……可以把每一个网页当做一个节点，把那些超链接当做连接网页的弧。有了超链接，可以从任何一个网页出发，用图的遍历算法，自动访问到每一个网页并且把他们存储起来。完成这个功能的程序叫网络爬虫。
30.    哥尼斯堡七桥，如果一个图能从一个顶点出发，每条边不重复的遍历一遍回到这个顶点，那么每一个顶点的度必须为偶数。
31.    构建网络爬虫的工程要点：1.用BFS（广度优先搜索）还是DFS（深度优先搜索），一般是先下载完一个网站，再进入下一个网站，即BFS的成分多一些。2.页面的分析和URL的提取，如果有些网页明明存在，但搜索引擎并没有收录，可能的原因之一是网络爬虫中的解析程序没能成功解析网页中不规范的脚本程序。3.记录哪些网页已经下载过的URL表，可以用哈希表。最终，好的方法一般都采用了这样两个技术：首先明确每台下载服务器的分工，也就是在调度时，一看到某个URL就知道要交给哪台服务器去下载，这样就避免了很多服务器对同一个URL做出是否需要下载的判断。然后，在明确分工的基础上，判断URL是否下载就可以批处理了，比如每次向哈希表（一组独立的服务器）发送一大批询问，或者每次更新一大批哈希表的内容，这样通信的次数就大大减少了。
32.    PageRank衡量网页质量的核心思想，在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。同时，对于来自不同网页的链接区别对待，因为网页排名高的那些网页的链接更可靠，于是要给这些链接比较大的权重。
33.    TF-IDF(Term Frequency / Inverse Document Frequency) ，关键词频率-逆文本频率值，其中，TF为某个网页上出现关键词的频率，IDF为假定一个关键词w在Dw个网页中出现过，那么Dw越大，w的权重越小，反之亦然，公式为log(D/Dw)。1.一个词预测主题的能力越强，权重越大，反之，权重越小。2.停止词的权重为零。
34.    动态规划（Dynamic Programming）的原理，将一个寻找全程最优的问题分解成一个个寻找局部最优的小问题。
35.    一个好的算法应该像轻武器中最有名的AK-47冲锋枪那样：简单、有效、可靠性好而且容易读懂（易操作）而不应该故弄玄虚。选择简单方案可以容易解释每个步骤和方法背后的道理，这样不仅便于出问题时的查错，也容易找到今后改进的目标。
36.    在实际的分类中，可以先进行奇异值分解（得到分类结果略显粗糙但能较快得到结果），在粗分类结果的基础上，利用计算向量余弦的方法（对范围内的分类做两两计算），在粗分类结果的基础上，进行几次迭代，得到比较精确的结果。
37.    奇异值分解（Singular Value Decomposition），在需要用一个大矩阵A来描述成千上万文章和几十上百万词的关联性时，计算量非常大，可以将A奇异值分解为X、B和Y三个矩阵，Amn=Xmm*Bmn*Ynn，X表示词和词类的相关性，Y表示文本和主题的相关性，B表示词类和主题的相关性，其中B对角线上的元素很多值相对其他的非常小，或者为零，可以省略。对关联矩阵A进行一次奇异值分解，就可以同时完成近义词分类和文章的分类，同时能得到每个主题和每个词义类之间的相关性，这个结果非常漂亮。
38.    信息指纹。如果能够找到一种函数，将5000亿网址随即地映射到128位二进制，也就是16字节的整数空间，就称这16字节的随机数做该网址的信息指纹。信息指纹可以理解为将一段信息映射到一个多维二进制空间中的一个点，只要这个随即函数做的好，那么不同信息对应的点不会重合，因此这个二进制的数字就变成了原来信息所具有的独一无二的指纹。
39.    判断两个集合是否相同，最笨的方法是这个集合中的元素一一比较，复杂度O(squareN)，稍好的是将元素排序后顺序比较，复杂度O(NlogN)，最完美的方法是计算这两个集合的指纹，然后直接进行比较，计算复杂度O(N)。
40.    伪随机数产生器算法（Pseudo-Random Number Generator，PRNG），这是产生信息指纹的关键算法，通过他可以将任意长的整数转换成特定长度的伪随机数。最早的PRNG是将一个数的平方掐头去尾取中间，当然这种方法不是很随即，现在常用的是梅森旋转算法（Mersenne Twister）。
41.    在互联网上加密要使用基于加密的伪随机数产生器（Cryptography Secure Pseudo-Random Number Generator，CSPRNG），常用的算法有MD5或者SHA-1等标准，可以将不定长的信息变成定长的128位或者160位二进制随机数。
42.    最大熵模型（Maximum Entropy）的原理就是保留全部的不确定性，将风险降到最小。最大熵原理指出，需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。在这种情况下，概率分布最均匀，预测的风险最小。I.Csiszar证明，对任何一组不自相矛盾的信息，这个最大熵模型不仅存在，而且是唯一的，此外，他们都有同一个非常简单的形式-指数函数。
43.    通用迭代算法（Generalized Iterative Scaling，GIS）是最原始的最大熵模型的训练方法。1.假定第零次迭代的初始模型为等概率的均匀分布。2.用第N次迭代的模型来估算每种信息特征在训练数据中的分布。如果超过了实际的，就把相应的模型参数变小，反之变大。3.重复步骤2直至收敛。这是一种典型的期望值最大化（Expectation Maximization，EM）算法。IIS(Improved Iterative Scaling)比GIS缩短了一到两个数量级。
44.    布隆过滤器实际上是一个很长的二进制向量和一系列随机映射的函数。
45.    贝叶斯网络从数学的层面讲是一个加权的有向图，是马尔科夫链的扩展，而从知识论的层面看，贝叶斯网络克服了马尔科夫那种机械的线性的约束，它可以把任何有关联的事件统一到它的框架下面。在网络中，假定马尔科夫假设成立，即每一个状态只与和它直接相连的状态有关，而和他间接相连的状态没有直接关系，那么它就是贝叶斯网络。在网络中每个节点概率的计算，都可以用贝叶斯公式来进行，贝叶斯网络也因此得名。由于网络的每个弧都有一个可信度，贝叶斯网络也被称作信念网络（Belief Networks）。
46.    条件随机场是计算联合概率分布的有效模型。在一个隐含马尔科夫模型中，以x1,x2,...,xn表示观测值序列，以y1,y2,...,yn表示隐含的状态序列，那么xi只取决于产生它们的状态yi,和前后的状态yi-1和yi+1都无关。显然很多应用里观察值xi可能和前后的状态都有关，如果把xi和yi-1,yi,yi+1都考虑进来，这样的模型就是条件随机场。它是一种特殊的概率图模型（Probablistic Graph Model），它的特殊性在于，变量之间要遵守马尔科夫假设，即每个状态的转移概率只取决于相邻的状态，这一点和另一种概率图模型贝叶斯网络相同，它们的不同之处在于条件随机场是无向图，而贝叶斯网络是有向图。
47.    维特比算法（Viterbi Algoritm）是一个特殊但应用最广的动态规划算法，利用动态规划，可以解决任何一个图中的最短路径问题。它之所以重要，是因为凡是使用隐含马尔科夫模型描述的问题都可以用它来解码。1.从点S出发，对于第一个状态x1的各个节点，不妨假定有n1个，计算出S到他们的距离d(S,x1i)，其中x1i代表任意状态1的节点。因为只有一步，所以这些距离都是S到他们各自的最短距离。2.对于第二个状态x2的所有节点，要计算出从S到他们的最短距离。d(S,x2i)=min_I=1,n1_d(S,x1j)+d(x1j,x2i)，由于j有n1种可能性，需要一一计算，然后找到最小值。这样对于第二个状态的每个节点，需要n1次乘法计算。假定这个状态有n2个节点，把S这些节点的距离都算一遍，就有O(n1*n2)次运算。3.按照上述方法从第二个状态走到第三个状态一直走到最后一个状态，这样就得到整个网络从头到尾的最短路径。
48.    扩频传输（Spread-Spectrum Transmission）和固定频率的传输相比，有三点明显的好处：1.抗干扰能力强。2.信号能量非常低，很难获取。3.扩频传输利用带宽更充分。
49.    Google针对云计算给出的解决工具是MapReduce，其根本原理就是计算机算法上常见的分治算法（Divide-and-Conquer）。将一个大任务拆分成小的子任务，并完成子任务的计算，这个过程叫Map，将中间结果合并成最终结果，这个过程叫Reduce。
50.    逻辑回归模型（Logistic Regression）是将一个事件出现的概率适应到一条逻辑曲线（Logistic Curve）上。典型的逻辑回归函数：f(z)=e`z/e`z+1=1/1+e`-z。逻辑曲线是一条S型曲线，其特点是开始变化快，逐渐减慢，最后饱和。逻辑自回归的好处是它的变量范围从负无穷到正无穷，而值域范围限制在0-1之间。因为值域的范围在0-1之间，这样逻辑回归函数就可以和一个概率分别联系起来了。因为自变量范围在负无穷到正无穷之间，它就可以把信号组合起来，不论组合成多大或者多小的值，最后依然能得到一个概率分布。
51.    期望最大化算法（Expectation Maximization Algorithm），根据现有的模型，计算各个观测数据输入到模型中的计算结果，这个过程称为期望值计算过程（Expectation），或E过程；接下来，重新计算模型参数，以最大化期望值，这个过程称为最大化的过程（Maximization），或M过程。这一类算法都称为EM算法，比如隐含马尔科夫模型的训练方法Baum-Welch算法，以及最大熵模型的训练方法GIS算法。