《数学之美》读书笔记

《数学之美》是一本与领域相关的数学概念书，生动地讲解了数据挖掘和文本检索的基础知识。可以作为数据挖掘和文本检索的入门科普书籍。另外，正如作者吴军所说，关键是从中学道——解决问题的方法，而不仅仅是技术。本书还启发式地引导读者形成自己的解决问题的方法。

下面记录一下我读完这本书后的一些想法：

第一章“文字和语言vs. 数字和信息”：文字和语言天然地包含着一些数学思想。数学可能不仅是一门非常科学的知识，而且还是一门艺术。另外，当你遇到复杂的问题时，生活中的一些常识和简单的想法可能会给你解决问题的灵感。

第二章《自然语言处理——从规则到统计》：试图模拟人脑的语言处理模型，根据语法规则、词性等进行语法分析和语义分析的自然语言处理非常复杂，而且统计基于的语言模型可以很好地解决自然语言处理中的许多问题。人们花了20多年的时间才理解这个过程并找到统计方法。我们很幸运，前人帮我们找到了正确的方法，我们不用再摸索了。此外，这也说明发现真相的过程是充满坎坷的。感谢那些奉献青春的科学家们。以后遇到问题时不要轻易放弃。真正的成长来自于解决问题的过程。事情不可能一帆风顺。这是自然界的普遍真理！

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

第四章“谈中文分词”：中文分词就是把一个句子分成一些词，这是以后进一步处理的基础。从一开始的查字典，到基于统计语言模型的分词，如今的中文分词已经算是解决了问题。但对于不同的系统、不同的需求，分词的粒度和方法也不同。仍然有必要针对具体问题提出最佳方法。没有什么是绝对的，悟道才是核心。

第五章“隐马尔可夫模型”：隐马尔可夫模型类似于概率论中的马尔可夫链，即此时的状态只与之前某些时刻的状态相关。基于大量数据训练相应的隐马尔可夫模型可以解决很多机器学习问题。训练中会涉及到一些经典算法（维特比算法等）。关于这个模型，我从来没有实际实现过，所以感觉很奇怪。我只知道概率论中教授的一些原理。

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

第七章“贾里尼克与现代语言处理”：贾里尼克是世界级大师，不仅因为他的学术成就，还因为他的风格。贾里尼克教授的青年时代坎坷，他并没有从一开始就致力于自然语言的研究。关键在于他的思想和他的道。 Jarikni教授治学严谨，对待学生用心。在教学生的时候，教授们最常告诉你的就是“什么方法不好”，这和那句话“我不同意你的观点，但我支持你”很相似。Jarikni教授倾注了自己的心血。读完这一章，我得出结论：“思想决定一个人的高度。”这一章中，关于青少年的教育，有以下几点值得借鉴：1.其实有青少年时期没必要花那么多时间学习，那时确立的社会经验、生活能力、志向都会对他们一生有帮助。2、中学时花大量时间学习的内容，可以用阅读的方式来阅读。大学的时间很短，因为到了大学阶段人们的理解力就强多了。3.学习（和教育）是一个终生的过程。4.书本上的内容可以早学到晚，但错过的成长阶段是无法弥补的。准备好了。

第8章“简单之美——布尔代数和搜索引擎索引”：布尔是19世纪英国的一名中学教师，但他的公开身份是一名酿酒师。想出好主意的人不一定是大师。简单的索引可以根据单词是否出现在网页中设置为0和1。为了适应索引访问的速度，附加信息和更新必须快，对索引的建立进行了改进，但原则上仍然是简单等价的。用于布尔运算。牛顿说：“（人们）发现真理总是在形式上简单，而不是复杂和模棱两可。”要做一个好的搜索，最基本的要求就是每天分析10-20个不好的搜索结果，并且需要一段时间来感受一下。有时候，在学习和处理问题时，可以从不好的方面入手，效果可能会更好。

第9章“图论与网络爬虫”：图遍历分为“广度优先搜索（BFS）”和“深度优先搜索（DFS）。互联网上有数百种，数十亿网页需要大量需要多少台服务器来下载网页，这些服务器的任务需要协调，这就是网络设计和编程的艺术，另外，对于简单的网页，不需要下载，还需要一个哈希表记录保存了哪些网页（如果记录了每个网页的URL，太多，可以使用后面提到的信息指纹，只需要多位数的数字即可），避免重复下载。在图论中，很长一段时间，实际需要的图只有几千个节点，当时图的遍历非常简单，人们并没有专门研究这个问题，随着互联网的出现，图的遍历突然变得有用了。很多数学方法都是这样的。他们似乎没有什么用处。当特定的应用程序出现时，它们突然派上用场。这或许就是世界上很多人终其一生研究数学的原因。一个系统整体上看起来很简单，但内部的一切可能都是一个复杂的东西，需要良好的设计。

第10章《PageRank----Google的民主投票网页排名技术》：搜索返回数千个结果，如何对搜索结果进行排名？这取决于两组信息：关于网页质量的信息和关于查询与每个网页的相关性的信息。 PageRank 算法衡量网页的质量。该算法的思想是，如果一个网页被许多其他网页链接，则意味着它得到了广泛的认可和信任，那么它的排名就会很高。谷歌创始人佩奇和布林提出了这个算法，并使用迭代的方法来解决这个问题。 PageRank 在所有Google 算法中仍然至关重要。该算法并不难，但当时只有佩奇和布林想到了。为什么？

第11章“如何确定网页和查询的相关性”：构建搜索引擎的四个方面：如何自动下载网页、如何建立索引、如何衡量网页质量、确定相关性网页的某个查询。搜索关键词权重的科学衡量标准是TF-IDF。 TF衡量的是网页中单词的权重，即词频。 IDF 衡量单词本身的权重及其预测主题的能力。查询与网页的相关性公式从简单的词频求和变为加权求和，即TF1*IDF1 + TF2*IDF2 + . + TFN*IDFN。看似复杂的搜索引擎，其实里面有这么简单的原理！

第十二章《地图和局部搜索最基本的技术——有限状态机和动态编程》：地址的解析依赖于有限状态机。当用户输入的地址不太规范或者有拼写错误时，希望进行模糊匹配。这就提出了一种基于概率的有限状态机。一般的有限状态机程序不易编写，要求较高。建议直接使用开源代码。图论中的动态规划问题可以用来解决两点之间的最短路径问题。它可以将一个“寻找全程最短路线”的问题分解为寻找局部最短路线的小问题。有限状态机和动态规划问题需要通过相关算法来解释才能深入理解。目前，它们还没有被完全理解。

第13章“—— Amit Singh博士，Google AK-47的设计师”：Singh坚持选择简单解决方案的原因之一是很容易解释每个步骤和方法背后的基本原理。这不仅可以在问题出现时更轻松地解决问题、检测错误并轻松找到未来改进的目标。辛格要求必须明确说明提高搜索质量的原因。无法解释清楚的改进即使看起来有效也不会被采用，因为这可能是未来的隐患。辛格极力鼓励年轻人不要害怕失败，要大胆尝试。遵循简单的哲学。

第14章《余弦定理与新闻分类》：新闻根据单词的TF-IDF值组成新闻的特征向量，然后根据向量之间的余弦距离来衡量两个特征之间的相似度，并且新闻是自动聚类的。另外，根据单词位置的不同，权重也应该不同。例如，标题中的单词权重显然应该更大。大量数据的余弦计算还需要考虑许多简化的算法。

第15章“矩阵运算和文本处理中的两个分类问题”：将大量文本表示为文本和词汇矩阵，然后对矩阵进行奇异值SVD分解，以获得其中隐含的一些信息。计算余弦相似度的一次迭代的时间复杂度与奇异值分解在同一数量级，但计算余弦相似度需要多次迭代。另外，奇异值分解的一个问题是存储量大，而余弦定理聚类则不需要。奇异值分解得到的结果稍显粗糙。在实际工作中，一般先进行奇异值分解，得到粗略的分类结果，然后再利用余弦计算，得到较为准确的结果。我觉得本章讨论的SVD有些方面不是很清楚。我已向吴军老师请教，正在等待答复。

第十六章“信息指纹及其应用”：信息指纹可以作为信息的唯一标识符。生成信息指纹的方法有很多种。互联网加密使用基于加密的伪随机数生成器。常用的算法包括MD5 或SHA-1 等标准。信息指纹可用于确定集合是相同的或基本相同的。 YouTube 使用信息指纹来打击盗版。一个128位的指纹可能只重复1.8*10^19次，所以重复的可能性几乎为0。判断集合是否相同，从简单的逐一比较到使用信息指纹。它激励我们有时运用灵活的思维来解决问题。

第十七章《受电视剧《阴谋》启发，与——聊密码学的数学原理》：RSA加密算法有两个完全不同的密钥，一个用于加密，一个用于解密。该算法包含简单但难以理解的数学思想。信息论在密码设计中的应用：当密码均匀分布且统计独立时，它们提供的信息最少。均匀分布使敌人无法统计，而统计独立性则确保即使敌人知道加密算法，也无法破译另一个密码。

第18章《闪闪发光的不一定是金子——谈搜索引擎反作弊问题》：把搜索反作弊当作一种沟通模式，把作弊当作附加噪音。解决噪声的方法：从信息源入手，增强排序算法的抗干扰能力；过滤掉噪音并恢复信息。只要噪声不是完全随机的并且是相关的，就可以被检测到并消除。作弊者的手段不可能是随意的，也不可能每天都换一种方法，而且作弊是与时间相关的。因此，在收集一段时间的作弊信息后，可以将作弊者抓获并恢复原来的排名。一般来说，作弊是针对市场份额较大的搜索引擎进行的。所以，一个小型搜索引擎作弊少，并不一定说明它的反作弊技术好，只是说明那里作弊的人少。

第十九章“谈谈数学模型的重要性”：早期的行星运动模型采用小圆内大圆的方法来精确计算所有行星的运行轨迹。但实际上该模型只是一个简单的椭圆。一个正确的数学模型应该是形式简单的；一个正确的模型一开始可能不如精心设计的错误模型那么准确，但如果我们相信大方向是对的，我们就应该坚持下去；准备大量数据对于研发来说很重要；正确的模型可能会受到噪声的影响而显得不准确。这不应该通过临时校正方法来补偿。找到噪声源可能会带来重大结果。发现。

第20章《不要把鸡蛋放在同一个篮子里——谈最大熵模型》：预测一个随机事件时，当各种情况的概率相等时，信息熵达到最大，不确定性最大，而预测的风险是最小的。最大熵模型的训练非常复杂。需要时检查数据以进一步了解。

第21章《拼音输入法数学原理》：输入法经历了对自然音节进行编码，然后将字符拆分成部首笔画进行输入，再回到自然音节输入的过程。任何事物的发展过程中，螺旋式回归并不是简单的重复，而是一种升华。输入法的速度取决于编码站点* 找到密钥所需的时间。传统的双拼编码太难记住，找到每个键需要很长时间，并且增加了编码的歧义性。根据香农第一定理，可以计算出每个汉字的理论平均最短码长。全拼不仅平均编码长度更小，而且基于上下文的语言模型可以很好地解决歧义问题。利用统计语言模型是将拼音转换为汉字的有效算法，并且可以转化为寻找最短路径的动态规划问题。如今各种输入法的效率基本处于同一水平。进一步改进的关键在于建立更好的语言模型。可以为每个用户构建个性化的语言模型。输入过程本身就是人与计算机之间的通信。好的输入法会自觉不自觉地遵循通信的数学模型。要创造最有效的输入法，你应该有意识地以信息论为指导。

第22章“自然语言处理教父马库斯和他的杰出弟子”：对自然语言处理从基于规则到基于统计的转变做出最大贡献的两个人是前面介绍的Jalinik教授。是一项开创性的使命；另一位是米奇马库斯（Mitch Marcus），他推广了这种方法。马库斯的贡献在于建立了宾夕法尼亚大学LDC语料库，使世界各地的研究人员和他的众多优秀弟子受益。马库斯的影响力主要通过他的弟子传播。 Marcus教授有很多值得敬佩的地方：他给予博士生追求自己感兴趣的课题的自由，具有高层次的视野，对学生给予重点指导；他管理风格宽松，培养各具特色的青年学者；他是一位有远见的管理者。他的学生做事风格各异，但都年轻有为，比如追求完美的迈克尔柯林斯，追求简单之美的伊克尔布莱尔。高手之所以能成为高手，必须具备一些优秀的品质和追求。

第23章“布隆过滤器”：判断某个元素是否在集合中时，使用布隆过滤器，它存储容量小，计算速度快。原理是：创建一个很长的二进制，使用每个元素通过随机数生成器生成一些信息指纹，然后将这些信息指纹映射到一些自然数，最后将这些自然数映射到创建的很长的二进制上。位置都设置为1。布隆过滤器的缺点是它可能会将不在集合中的元素误判为集合中的元素，但在某些条件下这种概率很小。补救的办法是建立一个小的白名单，存储可能误判的Element。布隆过滤器背后的数学原理是，完全随机数的碰撞概率很低，可以在少量空间中存储大量信息，并且速度非常快，因为只执行简单的算术运算。 《编程珍珠》第一章的例子就是布隆过滤器的思想。敞开心扉，寻找更好、更简单的方法。

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

第25章“条件随机场与句法分析”：句法分析就是分析句子的句子结构。对于不规则的句子，深入的分析是非常复杂的，浅层的句法分析在很多情况下是非常困难的。已经到了满足要求的时候了。条件随机场是浅层语法分析的有效数学模型。条件随机场与贝叶斯网络非常相似，只不过条件随机场是无向图，而贝叶斯网络是有向图。条件随机场的训练非常复杂。简化后可以参考最大熵训练方法。条件随机场的详细参数和原理尚不清楚。

第26章“维特比和他的维特比算法”：维特比算法是一种动态规划算法，可用于解码隐马尔可夫模型描述的任何问题。维特比算法采用一步一步的方法来计算每一步的最短距离。只需要在下一步中计算到下一步的最短距离即可。与穷举法相比，计算时间大大缩短，基本可以实现。实时输出，这个看似简单，但在当时确实是很神奇的。维特比对算法本身并不满意。他推广了该算法并将其应用于实践。他创立了高通公司，并成为世界上第二富有的数学家。高通在第二代移动通信领域并没有很强的市场地位，但却利用CDMA技术称霸了3G市场，可见远见是多么重要。

第27章《重温文本分类问题——期望最大化算法》：这一章其实是讲K-means聚类问题，设定原来的聚类中心，然后不断迭代直到收敛，将每个点分配到一个类。事实上，隐马尔可夫模型的训练和最大熵的训练都是期望最大化算法（EM）。首先，根据现有模型，计算输入模型的各个观测数据的计算结果。这个过程称为期望值计算过程，或E过程；接下来，重新计算模型参数以最大化期望值。这个过程称为最大过程，或M过程。如果优化后的目标函数是凸函数，则必然存在全局最优解。如果不是凸函数，则可能会找到局部最优解。以后解决一些问题的过程中，要考虑是否是EM问题。你也可以考虑参考这个思路，不断迭代优化目标流程。

第28章“Logistic回归和搜索广告”：根据广告的估计点击率，雅虎和百度的PPC广告产生的收入并不比Google的客观广告多。影响点击预估率的因素有很多。一种有效的方法是逻辑回归模型。逻辑回归模型是结合了影响概率的不同因素的指数模型。其训练方法与最大熵模型类似。我也不太明白它的具体内涵。

第29章《每次突破与Google云计算的基础》：分而治之，单独突破是一个好方法，Google开发的MapReduce算法就应用了这种方法。将一个大任务分成若干个小任务称为Map。将小任务的结果合并到最终结果中称为Reduce。如何调度和协调这个过程是工程上比较复杂的事情。可见，被广泛使用、真正有用的方法往往都是简单、简单的。

附录“计算复杂度”：计算机中的复杂度用O()表示。如果一个算法的计算量不超过N个多项式函数，则该算法称为多项式函数复杂度（P问题）并且可以计算。的。如果高于N的多项式函数，则属于非多项式问题，实际上是不可计算的。非多项式问题中的一类非确定性多项式问题（简称NP）是科学家们研究的重点，因为现实中很多问题都是NP问题。还有NP-Complete问题（NP问题可以在多项式时间内简化为这个问题）和NP-Hard问题。对于这两个问题，需要进行简化并寻找近似解。

总的来说，《数学之美》这本书教会了我很多关于文本处理和数据挖掘的知识，让我学到了很多。其中，一些科学家的质朴之美和大师风范给我留下了深刻的印象！书中提到的一些思想（即道）让我受益匪浅！