《数学之美》读书笔记 - 读书笔记

《数学之美》读书笔记

《数学之美》是一本领域相关的数学概念书，生动形象地讲解了关于数据挖掘、文本检索等方面的基础知识，可以作为数据挖掘、文本检索的入门普及书。另外，就像作者吴军老师提到的，关键是要从中学到道----解决问题的方法，而不仅仅是术。书中也启发式的引导读者形成自己解决问题的道。

下面记录一下自己读这本书的一些感想：

第一章《文字和语言vs数字和信息》：文字和语言中天然蕴藏着一些数学思想，数学可能不仅仅的是一门非 常理科的知识，也是一种艺术。另外，遇到一个复杂的问题时，可能生活中的一些常识，一些简单的思想会 给你带来解决问题的灵感。

第二章《自然语言处理----从规则到统计》：试图模拟人脑处理语言的模式，基于语法规则，词性等进行语法分析、语义分析的自然语言处理有着很大的复杂度，而基于统计的语言模型很好的解决了自然语言处理的诸多难题。人们认识这个过程，找到统计的方法经历了20多年，非常庆幸我们的前辈已经帮我们找到了正确的方法，不用我们再去苦苦摸索。另外，这也说明在发现真理的过程中是充满坎坷的，感谢那些曾经奉献了青春的科学家。自己以后遇到问题也不能轻易放弃，真正的成长是在解决问题的过程中。事情不可能一帆风顺的，这是自然界的普遍真理吧！

第三章《统计语言模型》：自然语言的处理找到了一种合适的方法---基于统计的模型，概率论的知识开始发挥作用。二元模型、三元模型、多元模型，模型元数越多，计算量越大，简单实用就是最好的。对于某些不出现或出现次数很少的词，会有零概率问题，这是就要找到一数学方法给它一个很小的概率。以前学概率论的时候觉的没什么用，现在开始发现这些知识可能就是你以后解决问题的利器。最后引用作者本章的最后一句话：数学的魅力就在于将复杂的问题简单化。

第四章《谈谈中文分词》：中文分词是将一句话分成一些词，这是以后进一步处理的基础。从开始的查字典到后来基于统计语言模型的分词，如今的中文分词算是一个已经解决的问题。然而，针对不同的系统、不同的要求，分词的粒度和方法也不尽相同，还是针对具体的问题，提出针对该问题最好的方法。没有什么是绝对的，掌握其中的道才是核心。

第五章《隐马尔科夫模型》：隐马尔科夫模型和概率论里面的马尔科夫链相似，就是该时刻的状态仅与前面某几个时刻的状态有关。基于大量数据训练出相应的隐马尔科夫模型，就可以解决好多机器学习的问题，训练中会涉及到一些经典的算法(维特比算法等)。关于这个模型，没有实际实现过，所以感觉好陌生，只是知道了些概率论讲过的原理而已。

第六章《信息的度量和作用》：信息论给出了信息的度量，它是基于概率的，概率越小，其不确定性越大，信息量就越大。引入信息量就可以消除系统的不确定性，同理自然语言处理的大量问题就是找相关的信息。信息熵的物理含义是对一个信息系统不确定性的度量，这一点与热力学中的熵概念相同，看似不同的学科之间也会有着很强的相似性。事务之间是存在联系的，要学会借鉴其他知识。

第七章《贾里尼克和现代语言处理》：贾里尼克是为世界级的大师，不仅在于他的学术成就，更在于他的风范。贾里尼克教授少年坎坷，也并非开始就投身到自然语言方面的研究，关键是他的思想和他的道。贾里克尼教授治学严谨、用心对待自己的学生，对于学生的教导，教授告诉你最多的是“什么方法不好”，这很像听到的一句话“我不赞同你，但我支持你”。贾里克尼教授一生专注学习，最后在办公桌前过世了。读了这章我总结出的一句话是“思想决定一个人的高度”。在这章中对于少年时的教育，以下几点值得借鉴：1、少年时期其实没有必要花那么多时间读书，他们的社会经验、生活能力以及在那时树立起的志向将帮助他们一生。2、中学时花大量时间学会的内容，在大学用非常短的时间就可以读完，因为在大学阶段，人的理解力要强很多。3、学习（和教育）是一个人一辈子的过程。4、书本的内容可以早学，也可以晚学，但是错过了成长阶段却是无法补回来的。

第八章《简单之美----布尔代数和搜索引擎的索引》：布尔是19世纪英国的一位中学教师，但他的公开身份是啤酒商，提出好的思想的人不一定是大师。简单的建立索引可以根据一个词是否在一个网页中出现而设置为0和1，为了适应索引访问的速度、附加的信息、更新要快速，改进了索引的建立，但原理上依然简单，等价于布尔运算。牛顿的一句话“（人们）发觉真理在形式上从来是简单的，而不是复杂和含混的”。做好搜索，最基本的要求是每天分析10-20个不好的搜索结果，积累一段时间才有感觉。有时候，学习、处理问题，可以从不好的方面入手，效果可能更好。

第九章《图论和网络爬虫》：图的遍历分为“广度优先搜索（Breadth-First Search，简称BFS）”和“深度优先搜索（Depth-First Search，简称DFS）。互联网上有几百亿的网页，需要大量的服务器用来下载网页，需要协调这些服务器的任务，这就是网络设计和程序设计的艺术了。另外对于简单的网页，没必要下载。还需要存储一张哈希表来记录哪些网页已经存储过（如果记录每个网页的url，数量太多，这里可以用后面提到的信息指纹，只需要一个很多位的数字即可），避免重复下载。另外，在图论出现的很长一段时间里，实际需求的图只有几千个节点，那时图的遍历很简单，人们都没有怎么专门研究这个问题，随着互联网的出现，图的遍历一下子有了用武之地，很多数学方法就是这样，看上去没有什么用途，等到具体的应用出来了一下子开始派上大用场了，这可能就是世界上很多人毕生研究数学的原因吧。一个系统看似整体简单，但里面的每个东西都可能是一个复杂的东西，需要很好的设计。

第十章《PageRank----Google的民主表决式网页排名技术》：搜索返回了成千上万条结果，如何为搜索结果排名？这取决与两组信息：关于网页的质量信息以及这个查询和每个网页的相关性信息。PageRank算法来衡量一个网页的质量，该算法的思想是如果一个网页被很多其他网页所链接，说明它收到普遍的承认和信赖，那么它的排名就高。谷歌的创始人佩奇和布林提出了该算法并用迭代的方法解决了这个问题。PageRank在Google所有的算法中依然是至关重要的。该算法并不难，可是当时只有佩奇和布林想到了，为什么呢？

第十一章《如何确定网页和查询的相关性》：构建一个搜索引擎的四个方面：如何自动下载网页、如何建立索引、如何衡量网页的质量以及确定一个网页和某个查询的相关性。搜索关键词权重的科学度量TF—IDF，TF衡量一个词在一个网页中的权重，即词频。IDF衡量一个词本身的权重，对主题的预测能力。一个查询和该网页的相关性公式由词频的简单求和变成了加权求和，即TF1*IDF1 TF2*IDF2 ... TFN*IDFN。看似复杂的搜索引擎，里面的原理竟是这么简单！

第十二章《地图和本地搜索的最基本技术——有限状态机和动态规划》：地址的解析依靠有限状态机，当用户输入的地址不太标准或有错别字时，希望进行模糊匹配，提出了一种基于概率的有限状态机。通用的有限状态机的程序不是很好写，要求很高，建议直接采用开源的代码。图论中的动态规划问题可以用来解决两点间的最短路径问题，可以将一个“寻找全程最短路线”的问题，分解成一个个寻找局部最短路线的小问题。有限状态机和动态规划问题需要看相关的算法讲解，才能深入理解，目前对其并未完全理解。

第十三章《Google AK-47 的设计者——阿米特·辛格博士》：辛格坚持选择简单方案的一个原因是容易解释每一个步骤和方法背后的道理，这样不仅便于出了问题时查错，而且容易找到今后改进的目标。辛格要求对于搜索质量的改进方法都要能说清楚理由，说不清楚理由的改进即使看上去有效也不会采用，因为这样将来可能是个隐患。辛格非常鼓励年轻人要不怕失败，大胆尝试。遵循简单的哲学。

第十四章《余弦定理和新闻的分类》：将新闻根据词的TF-IDF值组成新闻的特征向量，然后根据向量之间的余弦距离衡量两个特征之间的相似度，将新闻自动聚类。另外根据词的不同位置，权重应该不同，比如标题的词权重明显应该大点。大数据量的余弦计算也要考虑很多简化算法。

第十五章《矩阵运算和文本处理中的两个分类问题》：将大量的文本表示成文本和词汇的矩阵，然后对该矩阵进行奇异值SVD分解，可以得到隐含在其中的一些信息。计算余弦相似度的一次迭代时间和奇异值分解的时间复杂度在一个数量级，但计算余弦相似度需要多次迭代。另外，奇异值分解的一个问题是存储量大，而余弦定理的聚类则不需要。奇异值分解得到的结果略显粗糙，实际工作中一般先进行奇异值分解得到粗分类结果，在利用余弦计算得到比较精确地结果。我觉得这章讲的SVD有些地方不是很清楚，已向吴军老师请教了，等待回信。

第十六章《信息指纹及其应用》：信息指纹可以作为信息的唯一标识。有很多信息指纹的产生方法，互联网加密要使用基于加密的伪随机数产生器，常用的算法有MD5或者SHA-1等标准。信息指纹可以用来判定集合相同或基本相同。YouTobe就用信息指纹来反盗版。128位的指纹，1.8*10^19次才可能重复一次，所以重复的可能性几乎为0。判定集合是否相同，从简单的逐个比对到利用信息指纹，复杂度降低了很多很多。启发我们有时候要用变通的思想来解决问题。

第十七章《由电视剧《暗算》所想到的——谈谈密码学的数学原理》：RSA加密算法，有两个完全不同的钥匙，一个用于加密，一个用于解密。该算法里面蕴含着简单但不好理解的数学思想。信息论在密码设计中的应用：当密码之间分布均匀并且统计独立时，提供的信息最少。均匀分布使得敌人无从统计，而统计独立能保证敌人即使知道了加密算法，也不能破译另一段密码。

第十八章《闪光的不一定是金子——谈谈搜索引擎反作弊问题》：把搜索反作弊看成是通信模型，作弊当做是加入的噪声，解决噪声的方法：从信息源出发，增强排序算法的抗干扰能力；过滤掉噪声，还原信息。只要噪声不是完全随机并且前后有相关性，就可以检测到并消除。作弊者的方法不可能是随机的，且不可能一天换一种方法，及作弊是时间相关的。因此在搜集一段时间的作弊信息后，就可以将作弊者抓出来，还原原有的排名。一般作弊都是针对市场份额较大的搜索引擎做的，因此，一个小的搜索引擎作弊少，并不一定是它的反作弊技术好，而是到它那里作弊的人少。

第十九章《谈谈数学模型的重要性》：早期的行星运行模型用大圆套小圆的方法，精确地计算出了所有行星运行的轨迹。但其实模型就是简单的椭圆而已。一个正确的数学模型应该在形式上是简单的；一个正确的模型可能开始还不如一个精雕细琢过的错误模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去；大量准备的数据对研发很重要；正确的模型可能受到噪声干扰，而显得不准确，这是不应该用一种凑合的修正方法来弥补它，要找到噪声的根源，这也许能通往重大的发现。

第二十章《不要把鸡蛋放在一个篮子里——谈谈最大熵模型》：对一个随机事件预测时，当各种情况概率相等时，信息熵达到最大，不确定性最大，预测的风险最小。最大熵模型的训练非常复杂，需要时查看资料做进一步的理解。

第二十一章《拼音输入法的数学原理》：输入法经历了以自然音节编码，到偏旁笔画拆字输入，再回归自然音节输入的过程。任何事物的发展，螺旋式的回归不是简单的重复，而是一种升华。输入法的速度取决于编码的场地*寻找这个键的时间。传统的双拼，记住编码太难，寻找每个键的时间太长，并且增加了编码上的歧义。根据香农第一定理可以计算理论上每个汉字的平均最短码长。全拼不仅编码平均长度较少，而且根据上下文的语言模型可以很好的解决歧义问题。利用统计语言模型可是实现拼音转汉字的有效算法，而且可以转换为动态规划求最短路径问题。如今各家输入法的效率基本在一个量级，进一步提升的关键就在于建立更好的语言模型。可以根据每个用户建立个性化的语言模型。输入的过程本身就是人和计算机的通信，好的输入法会自觉或者不自觉的的遵循通信的数学模型。要做出最有效的输入法，应该自觉使用信息论做指导。

第二十二章《自然语言处理的教父马库斯和他的优秀弟子们》：将自然语言处理从基于规则到基于统计，贡献最大的两个人，一个是前面介绍的贾里尼克教授，他是一个开创性任务；另一个是将这个方法发扬光大的米奇·马库斯。马库斯的贡献在于建立了造福全世界研究者的宾夕法尼亚大学LDC语料库以及他的众多优秀弟子。马库斯的影响力很大程度上是靠他的弟子传播出去的。马库斯教授有很多值得钦佩的地方：给予他的博士研究生自己感兴趣的课题的自由，高屋建瓴，给学生关键的指导；宽松的管理方式，培养各有特点的年轻学者；是一个有着远见卓识的管理者。他的学生为人做事风格迥异，但都年轻有为，例如追求完美的迈克尔·柯林斯和寻求简单美的艾克尔·布莱尔。大师之所以能成为大师，肯定有着一些优秀的品质和追求。

第二十三章《布隆过滤器》：判断一个元素是否在一个集合当中时，用到了布隆过滤器，存储量小而且计算快速。其原理是：建立一个很长的二进制，将每个元素通过随机数产生器产生一些信息指纹，再将这些信息指纹映射到一些自然数上，最后在建立的那个很长的二进制上把这些自然数的位置都置为1。布隆过滤器的不足之处是它可能把不在集合中的元素错判成集合中的元素，但在某些条件下这个概率是很小的，补救措施是可以建立一个小的白名单，存储那些可能误判的元素。布隆过滤器背后的数学原理在于完全随机的数字其冲突的可能性很小，可以用很少的空间存储大量的信息，并且由于只进行简单的算术运算，因此速度非常快。《编程珠玑》中第一章的那个例子就是布隆过滤器的思想。开阔思维，寻找更好更简单的方法。

第二十四章《马尔科夫链的扩展——贝叶斯网络》：贝叶斯网络是马尔科夫链的扩展，由简单的线性链式关系扩展为网络的关系，但贝叶斯网络仍然假设每一个状态只与它直接相连的状态相关。确定贝叶斯网络的拓扑结构和各个状态之间相关的概率也需要训练。在词分类中，可以建立文章、主题和关键词的贝叶斯网络，用来得到词的分类。贝叶斯网络的训练包括确定拓扑结构和转移概率，比较复杂，后者可以参考最大熵训练的方法。贝叶斯网络导出的模型是非常复杂的。

第二十五章《条件随机场和句法分析》：句法分析是分析出一个句子的句子结构，对于不规则的句子，对其进行深入的分析是很复杂的，而浅层的句法分析在很多时候已经可以满足要求了。条件随机场就是进行浅层句法分析的有效的数学模型。条件随机场与贝叶斯网络很像，不用之处在于，条件随机场是无向图，而贝叶斯网络是有向图。条件随机场的训练很复杂，简化之后可以参考最大熵训练的方法。对于条件随机场的详细参数及原理还不理解。

第二十六章《维特比和他的维特比算法》：维特比算法是一个动态规划算法，凡是使用隐马尔科夫模型描述的问题都可以用它来解码。维特比算法采用逐步渐进的方法，计算到每步的最短距离，到下步的最短距离只用接着本步的计算即可，相比穷举法，大大缩短了计算的时间，并且基本可以实现实时的输出，这看似简单，但在当时确是很了不起的。维特比并不满足停留在算法本身，他将算法推广出去，并应用到了实际中，创立了高通公司，成为了世界上第二富有的数学家。高通公司在第二代移动通信中并不占很强的市场地位，而其利用CDMA技术霸占了3G的市场，可见远见的洞察力是多么的重要。

第二十七章《再谈文本分类问题——期望最大化算法》：该章讲的其实就是K均值聚类问题，设置原始聚类中心，然后不断迭代，直至收敛，将每个点分到一个类中。其实隐马尔科夫模型的训练和最大熵的训练都是期望最大化算法（EM）。首先，根据现有的模型，计算各个观测数据输入到模型中的计算结果，这个过程称为期望值计算过程，或E过程；接下来，重新计算模型参数，以最大化期望值，这个过程称为最大化的过程，或M过程。优化的目标函数如果是个凸函数，则一定有全局最优解，若不是凸函数，则可能找到的是局部最优解。在以后的一些问题求解过程中，应该考虑其是否是EM问题，也可以考虑参考这种思想，不断迭代以优化目标的过程。

第二十八章《逻辑回归和搜索广告》：雅虎和百度的竞价排名广告并不比谷歌的根据广告的预估点击率来客观的推送广告收入多。点击预估率有很多影响因素，一种有效的方法是逻辑回归模型，逻辑回归模型是一种将影响概率的不同因素结合在一起的指数模型。其训练方法和最大熵模型相似。同样不是很理解其具体内涵。

第二十九章《各个击破和Google云计算的基础》：分而治之，各个击破是一个很好的方法，Google开发的MapReduce算法就应用了该方法。将一个大任务分成几个小任务，这个过程叫Map，将小任务的结果合并成最终结果，这个过程叫Reduce，该过程如何调度、协调就是工程上比较复杂的事情了。可见大量用到的、真正有用的方法往往简单而又朴实。

附录《计算复杂度》：计算机中复杂度是以O()来表示的，如果一个算法的计算量不超过N的多项式函数，则称算法为多项式函数复杂度的（P问题），是可以计算的。若比N的多项式函数还高，则是非多项式问题，实际上是不可计算的。非多项式问题中一种非确定的多项式问题（简称NP），是科学家研究的焦点，因为现实中好多问题都是NP问题。另外还有NP-Complete问题（NP问题可以在多项式时间内规约到该问题）和NP-Hard问题，对于这两种问题，需要简化找到近似解。

整体上，《数学之美》这本书让我了解了很多文本处理，数据挖掘相关的知识，学到了很多。其中，简单美以及一些科学家的大师风范让我印象深刻！书中提到的一些思想（即道）让我受益匪浅！