吴军《数学之美》第二版阅读整理

吴军的《数学之美》第一版于2012年出版，并获得国家图书馆第八届文津图书奖。我读的是第二版（再版），作者在第一版的基础上又增加了一些内容。

作者大有来头（IT行业），吴军博士，毕业于清华大学和美国约翰.霍普金斯大学，02年就职于Google，从事搜索算法相关工作。（百度百科）

-------------------------------------------------------------------------
以下是我本人的书评
《数学之美》严格来说，应该叫《数学在信息技术行业的应用之美》，主要是讲述数学在信息技术（IT）领域，特别是语音识别和搜索引擎方面的美丽之处予以了精彩表达。让我比较佩服的是作者作为了个忙碌的程序员（高级别），居然能抽出空闲时间写了三本高质量的书。本书的很多章节后面都有列出参考文献，可见深入浅出的讲解高深莫测的“科学”需要做很多功课，感谢作者。此外，作者介绍（科普）了很多数学模型，如隐含马尔可夫模型、图论等等。当然做为搜索引擎方面的专家，作者对于搜索引擎，介绍了如何自动下载网页、建立索引和度量网页的质量（PageRank）以及如何确定网页。最后，科学的美本质是思维的美~ 保持好奇心，保持一颗谦虚的心。
-------------------------------------------------------------------------

书的目录:

• 第1章，文字和语言 vs 数字和信息
• 第2章，自然语言处理——从规则到统计
• 第3章，统计语言模型
• 第4章，谈谈分词
• 第5章，隐含马尔可夫模型
• 第6章，信息的度量和作用
• 第7章，贾里尼克和现代语言处理
• 第8章，简单之美——布尔代数和搜索引擎
• 第9章，图论和网络爬虫
• 第10章，PageRank——Google的民主表决式网页排名技术
• 第11章，如何确定网页和查询的相关性
• 第12章，有限状态机和动态规划——地图与地本搜索的核心技术
• 第13章，Google AK-47的设计者: 阿米特.辛格博士
• 第14章，余弦定理和新闻的分类
• 第15章，矩阵运算和文本处理中的两个分类问题
• 第16章，信息指纹及其应用
• 第17章，由电视剧《暗算》所想到的——谈谈密码学的数学原理
• 第18章，闪光的不一定是金子——淡淡搜索引擎反作_弊问题和搜索结果的权威性问题
• 第19章，谈谈数学模型的重要性
• 第20章，不要把鸡蛋放到一个篮子里——谈谈最大熵模型
• 第21章，拼音输入法的数学原理
• 第22章，自然语言处理的教父马库斯和他的优秀弟子们
• 第23章，布隆过滤器
• 第24章，马尔可夫链的扩展——贝叶斯网络
• 第25章，条件随机场、文法及析及其他
• 第26章，维特比和他的维特比算法
• 第27章上帝的算法——期望最大化算法
• 第28章，逻辑回归和搜索广告
• 第29章，各个击破算法和Google云计算的基础
• 第30章，Google大脑和人工神经网络
• 第31章，大数据的威力——谈谈数据的重要性
• 附录，计算复杂度

-------------------------------------------------------------------------

【第1章】文字和语言 vs 数学和信息
文字的记录: 古埃及的《亚尼的死者之书》（现藏于大英博物馆），罗塞塔石碑（Rosetta）。

乔治.伽莫夫（George Gamow）《从一到无穷大》

对于数字的表示，先进的中国人和罗马人。
描述数字最有效的是古印度人，发现了包括0在内的10个阿拉伯数字。（由阿拉伯人传入欧洲，所以被阿拉伯人捡了“便宜”）。

【第2章】 自然语言处理——从规则到统计
计算机发明于1946年，而自然语言处理却在上世纪90年代才找到快速有效的方法。使用数学和统计方法代替发明可以模拟人脑的电脑。

【第3章】统计语言模型（Statistical Language Model）
数学的精彩之处就在于简单的模型可以干大事。

自然语言处理使用概率论和数理统计: 二阶模型、三元模型。

【第4章】谈谈分词
词是表达语义最小的单位，所以我们需要分词。

现在中文分词是一个已经解决了的问题。

【第5章】 隐含可尔可夫模型
隐含马尔可夫模型是一个并不复杂的数学模型，到目前为止，它一直被认为是解决大多数自然语言处理问题最快速、有效的方法。

隐含马尔可夫模型属于随过过程（概率论）的学科。

同时，隐含马尔可夫模型也是机器学习的主要工具之一。和几乎所有的机器学习的模型工具一样，它需要一个训练算法（鲍姆-韦尔奇算法）和使用时的解码算法（维特比算法），掌握了这两类算法，就基本上可以使用隐含马尔可夫模型这个工具了。

【第6章】信息的度量和作用
信息的度量: 香农（Claude Shannon）在文论《通信的数学原理》（A Mathematic Theory of Communication）中提出了“信息熵（shang）”的概念。

扩展阅读: 《汉语信息熵和语言模型的复杂度》（本书作者吴军和王作英教授著）（百度搜索可得）

信息的作用: 如果没有信息，任何公式或者数学的游戏都无法排除不确定性。几乎所有的自然语言处理、信息与信号处理的应用都是一个消除不确定性的过程。
合理利用信息，是做好搜索的关键。

本章三个重要的概念: 信息熵、条件熵和相对熵。

扩展阅读: 斯坦福大学托马斯.科弗（Thomas Cover）教授著的《信息论基础》（Elements of Information Theory）。

【第7章】贾里尼克和现代语言处理
这一章主要介绍弗里德里克.贾里尼克（Frederek Jelinek）教授。

贾里尼克和作者在学习上的观点: 学习（和教育）是持续一辈子的过程。

上个世纪70年代的IBM有点像上个世纪90年代的微软和过去10年（施密特时代）的Google，任由杰出科学家做自己感兴趣的研究。

【第8章】简单之美——布尔代数和搜索引擎
做事情的方法有道和术两种境界，具体的做事方法是术，做事的原理和原则是道。很多具体的技术很快会从独门绝技到普及，再到落伍，追求术的人一辈子工作很辛苦。只有掌握了搜索的本质和精髓才能永远游刃有余。

真正做好一件事情没有捷径，离不开一万小时的专业训练和努力。

建立一个搜索引擎大致需要这样几件事:
1. 自动下载尽可能多的网页；
2. 建立快速有效的索引；
3. 根据相关性对网页进行公平准备的排序。

布尔代数对于数学的意义等同于量子力学对于物理学的意义，它们将我们对世界的认识从连续状态扩展到离散状态。在布尔代数的“世界”里，万物都是可以量子化的。

googol: 10^100（10的100次方），Google公司的名称便是来源于此，表示它的索引量大。

数据库的查询语句（SQL）支持各种复杂的逻辑组合，但是背后的基本原理是基于布尔运算的。

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

本章讨率的如何自动下载互联网所有的网页，需要用到的就是图论中的遍历（Traverse）算法。

广度优先搜索（Breadth-First Search，BFS）和深度优点搜索（Depth-First Search，DFS）。

网终爬虫: Web Crawlers
通过网页找到该页所有的超链接，下载并继续分析...一直重复做以上步骤。注意的是，需要记载哪个网页下载过了，以免重复。通过人们使用一种“散列表”（Hash Table，也可以叫哈希表）而不是一个记事本记录网页是否下载过的信息。

网络爬虫在工程实现上要考虑的细节非常多，其中大的方面有这样几点:
1. 用BFS还是DFS？
2. 页面的分析和URL的提取
3. 记录哪些网页已经下载过的小本本——URL表

【第10章】PageRank——Google的民主表决式网页排名技术
一个特定的查询，搜索结果的排名取决于两组信息: 关于网页的质量信息（Quality），以及这个查询与每个网页的相关性信息（Relevance）。

在互联网上，如果一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。这就是PageRank的核心思想。

2003年，Google工程师迪恩（Jeffrey Dean）和格麦瓦特（Sanjay Ghemawat）发明了并行计算工具MapReduce。

PageRank算法被公认为是文献检索中最大的贡献之一，由于PageRank算法受到专利保护，带来的结果是其他搜索引擎开始时都比较遵守游戏规则，不去侵犯它，这对当时还很弱小的Google是一个很好的保护。

【第11章】如何确定网页和查询的相关性
搜索关键词权重的科学度量TF-IDF（Term Frequency / Inverse Document Frequency）

【第12章】有限状态机和动态规划——地图与地本搜索的核心技术
有限状态机的一个典型应用是Google Now——一个在智能手机上的基于个人信息的服务软件。

全球导航的关键算法是计算机科学图论中的动态规划（Dynamic Programming，DP）的算法。

【第13章】Google AK-47的设计者: 阿米特.辛格博士
辛格博士被认为是当今最权威的网络搜索专家。

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

【第14章】余弦定理和新闻的分类
世界上有些事情常常超乎人们的想象。余弦定理和新闻的分类看似八竿子打不着，却有着紧密的联系。具体来说，新闻的分类很大程序上依靠的是余弦定理。

美国人总是倾向于用机器（计算机）代替人工来完成任务。虽然在短期内需要做一些额外的工作，但是从长远看可以节省很多时间和成本。

【第15章】矩阵运算和文本处理中的两个分类问题
矩阵运算中的奇异值分解（Singular Value Decomposition，SVD）。

如何用计算机进行奇异值分解。对于不大的矩阵，比如几万乘以几万的矩阵，用计算机上的数学工具MATLAB就可以计算。但是更大的矩阵，比如上百万乘以上百万，奇异值分解的计算量大常大，就需要很多台计算机并行处理了。虽然Google早就有了MapReduce等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在Google内部以前也无法利用并行计算的优势来分解矩阵。直到2007年Google中国的张智威博士带领几个中国的工程师及实习生实现了奇异值分解的并行算法。

【第16章】信息指纹及其应用
产生信息指纹的关键算法: 伪随机数产生器算法（Pseudo-Random Number Generator，PRNG），通过它将任意很长的整数转换成特定长度的伪随机数。

在互联网上加密要使用基于加密的伪随机数产生器（CSPRNG），常用的算法有MD5或者SHA-1等标准。

YouTube的反盗版原理。

相似哈希（Simhash）

【第17章】由电视剧《暗算》所想到的——谈谈密码学的数学原理
赫伯特.雅德利《中国黑室（The Chinese Black Chamber）》，中文版本是2011年出版的《中国黑室——鲜为人知的中日谍报战》。

一种加密方法只要保证50年内计算机破解不了也就可以满意了。

【第18章】闪光的不一定是金子——淡淡搜索引擎反作_弊问题和搜索结果的权威性问题
从动机上讲，作_弊者无非是想让自己的网站排名靠前，进而获得商业利益。而帮助别人作_弊的人（他们自称是搜索引擎优化者，Search Engine Optimizer，SEO）也是要从中牟利的。

【第19章】谈谈数学模型的重要性
伟大的天文学家托密勒: 发明了球坐标，定义了包括赤道和零度经线在内的经纬线，出提了黄道，发明了弧度制。

由托密勒的地心说到开普勒的准备地描述行星运动（椭圆模型），中间的故事非常有意思。作者也由此得出以下结论: （道理都是相通的嘛~）
1. 一个正确的数学模型应当在形式上是最简单的。（托密勒的模型显然太复杂。）
2. 一个正确的模型一开始可能还不如一个精雕细琢过的错误模型来的准确，但是，如果我们认定大方向是对的，就应该坚持下去。（日心说一开始并没有地心说准确。）
3. 大量准备的数据对研发很重要。（“大数据”的威力。）
4. 正确的模型也可能受噪音干扰，而显得不准备；这时不应该用一种凑合的修正方法加以弥补，而是要找到噪音的根源，这也许能通往重大的发现（参现海王星的发现。）

【第20章】 不要把鸡蛋放到一个篮子里——谈谈最大熵模型
最大熵模型（Maximum Entropy），保留全部的不确定性，将风险降到最小。

到今天为止，世界上能有效实现最大熵算法的也不到一百人。

【第21章】拼音输入法的数学原理
好的输入法会遵循通信的数学模型，当然要做出最有效的输入法，应当自觉使用信息论做指导。

【第22章】自然语言处理的教父马库斯和他的优秀弟子们
米奇.马库斯（Mitch Marcus）。

【第23章】 布隆过滤器
计算机的集合是用散列表（Hash Table）来存储的，优点是快速准备，缺点是耗费村储空间。

数学工具存隆过滤器（Bloom Filter，于1970年由伯顿.布隆提出），它只需要散列表1/8到1/4的大小就能解决同样的问题（占用存储空间问题）。

【第24章】马尔可夫链的扩展——贝叶斯网络
贝叶斯网络（Belief Networks）: 一个加权的有向图，是可尔可夫链的扩展，贝叶斯网络上的每个弧都有一个可以量化的可信度（Belief）。

在文字处理方面，语义相近的词之间的关系可以用一个贝叶斯网络来描述。我们利用贝叶斯网络，可以找出近义词和相关的词，因而在Google搜索和Google广告中都有直接的应用。

【第25章】条件随机场、文法及析及其他
条件随机场是计算联合概率分布的有效模型。条件随机场是隐含马尔可夫模型的一种扩展。

条件随机场是无向图，而上一章节讲的贝叶斯模型是有向图。

条件随机场在模式识别、机器学习、生物统计，甚至预访犯罪等方面都有很成功的应用。

【第26章】维特比和他的维特比算法
维特比算法是现代数字通信中最常用的算法，同时也是很多自然语言处理采用的解码算法。

篱笆网络（Lattice）

码分多址（CDMA）

【第27章】上帝的算法——期望最大化算法
机器学习中最重要的一个法算——期望最大化算法（Expectation Maximization Algorithm）。

【第28章】逻辑回归和搜索广告
逻辑回归模型（Logistic Regression / Logistic Model）。

【第29章】各个击破算法和Google云计算的基础
云计算的关键之一是，如何把一个非常大的计算问题，自动分解到许多计算能力不是很强大的计算机上，共同完成。针对这个问题，Google给出的解决工具是一个叫MapReduce的程序，其根本原理就是十分常见的分治算法（Diviede-and-Conquer），我称之为“各个击破”法。

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

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

如何将一个大矩阵自动拆分，保证各个服务器负载均衡，如何合并返回值，就是MapReduce在工程上所做的事情了。

【第30章】Google大脑和人工神经网络
2011年底，Google发布了一项新技术，基于深度学习（Deep Learning）的“Google大脑".

人工神经网络有很多应用领域，比如语音识别、机器翻译、人脸图像识别、癌细服的识别、疾病的预测和股市走向的预测等等。

【第31章】大数据的威力——谈谈数据的重要性
在Google内部，产品经理们都遵循这样一个规则: 在没有数据之前，不要给出任何结论。因为日常的很多感觉与数据给出的结论是相反的。

人的直觉和数据之间相差巨大:
2012年，世界上人口最多的10个城市（有包括远郊县）是哪些？
在中国主要互联门户网站的首页上放一个3cm*5cm的游戏广，游戏公司每获得一个点击平均付出的广告费是多少？
有多少人相信职业投资人所管理的基金能给他们带来比大盘更好的回报。

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

今天的IT行业的竞争，在某种程度上已经是数据的竞争了。

除了IT行业，医疗保健是对大数据最热衷的行业。

【附录】计算复杂度
一个优秀的计算机科学家或者工程师与平庸的程序员的差别就在于: 前者总是不断寻找并且有能力找到好的算法，而后者仅常常满足于勉强解决问题。

数学在计算机科学中的一个重要作用，就是找到计算复杂度尽可能低的解。同时，对于那些NP-Complete或者NP-Hard的问题，找到近似解。

-------------------------------------------------------------------------

推荐:
乔治.伽莫夫《从一到无穷大》
霍金《时间简史》
摩根.弗里曼担任旁边和主持人的节目《穿越虫洞》（Through the Wormhole）

吴军《浪潮之巅》、《文明之光》