《数学之美》读书笔记

其实这本书越早读越好,最好在中学阶段,中国教育最失败的就是学生从上课的第一天到考试结束,都不知道他学的东西能做什么。《数学之美》正好能告诉学生(包括大学生),从小到大学的那些数学知识可以如何改造世界。 —— gj83 / 亚马逊读者

有时我在想,现在的社会多了一点压力和浮躁,少了一点踏实和对自然科学本质的好奇求知。吴军的这本《数学之美》真的非常好。非常希望吴军今后能写出更多这样深入浅出的好书,它们是给这个社会和年轻人最好的礼物。 —— 李开复

其实很想将自己理解的数学模型、公式贴上来解释,但现在还不太会怎么弄,而且理解不是非常深!以后有机会的。

前言

  • 很多大学毕业生毕业后,在大学所学的数学可能一辈子都没有机会应用,几年后就忘得差不多了。

    坐着这里强调了实践的重要性!

  • Virtue is like a rich stone, best plain set.

    美德就如同华贵的宝石,在朴素的衬托下最显华丽。

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

  • 很多读者问我为什么在《浪潮之巅》一书中讲的公司大多在美国,因为近百年的技术革命大多发生在那里。

  • 信息的冗余是信息安全的保障。

  • 语言的数据,我们称之为语料,尤其是双语或者多语的对照语料对翻译至关重要,它是我们从事机器翻译研究的基础。

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

  • 从20世纪50年代到70年代,是科学家们走弯路的阶段。全世界的科学家对计算机处理自然语言的认识都局限在人类学习语言的方式上,也就是说,用电脑模拟人脑,这20多年的成果近乎为零。直到20世纪70年代,一些自然语言处理的先驱开始重新认识这个问题,找到了基于数学模型和统计的方法,自然语言处理进入第二个阶段。

  • 钱钟书在《围城》中讲,老科学家可以理解成“老的科学家”或者“老科学的家”两种。如果是后者,他们年纪不算老,但是已经落伍,大家必须耐心等他们退休让出位子。毕竟,不是所有人都乐意改变自己的观点,无论对错。当然,等这批人退休之后,科学就会以更快的速度发展。因此,我常想,我自己一定要在还不太糊涂和固执时就退休。

    有道理!人们不敢挑战权威。

第3章 统计语言模型

  • 在实际应用中,统计语言模型的零概率问题是无法回避的,必须解决。

  • 古德-图灵估计的原理是这样的:对于没有看见的事件,我们不能认为它发生的概率就是零,因此我们从概率的总量(Probability Mass)中,分配一个很小的比例给这些没有看见的事件。

  • 在成本不高的情况下,有必要对训练数据进行过滤。

  • 数学的魅力就在于将复杂的问题简单化。

第4章 谈谈分词

  • 自然语言处理的许多数学方法是通用的,与具体的语言无关。在Google内部,我们设计语言处理的算法时,都会考虑它是否能很容易地适用于各种自然语言。这样才能有效地支持上百种语言的搜索。

  • 需要指出的是任何方法都有它的局限性,虽然利用统计语言模型进行分词,可以取得比人工更好的结果,但是也不可能做到百分之百准确。因为统计语言模型很大程度上是依照“大众的想法”,或者“多数句子的用法”,而在特定情况下可能是错的。

第5章 隐含马尔可夫模型

  • 隐含马尔可夫模型是一个并不复杂的数学模型,到目前为止,它一直被认为是解决大多数自然语言处理问题最快速、有效的方法。它成功地解决了复杂的语音识别、机器翻译等问题。

  • 雅各布森通信六个要素是:发送者(信息源),信道,接受者,信息,上下文和编码。

  • 隐含马尔可夫模型最早的成功应用是语音识别。20世纪80年代末李开复博士坚持采用隐含马尔可夫模型的框架,成功研发出了世界上第一个大词汇量连续语音识别系统Sphinx。

  • 围绕着隐含马尔可夫模型有三个基本问题:

    1. 给定一个模型,如何计算某个特定的输出序列的概率;

    2. 给定一个模型和某个特定的输出序列,如何找到最可能产生这个输出的状态序列;

    3. 给定足够量的观测数据,如何估计隐含马尔可夫模型的参数。

  • 数据由人工标注的方法称为有监督的训练方法(Supervised Training)。

第6章 信息的度量和作用

  • 直到1948年,香农(Claude Shannon)在他著名的论文“通信的数学原理”(A Mathematic Theory of Communication)中提出了“信息熵”的概念,才解决了信息的度量问题,并且量化出信息的作用。

  • 几乎所有的自然语言处理、信息与信号处理的应用都是一个消除不确定性的过程。

  • 合理利用信息,而非玩弄什么公式和机器学习算法,是做好搜索的关键。

  • 信息的作用在于消除不确定性,自然语言处理的大量问题就是寻找相关的信息。

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

  • 在当今物欲横流的中国社会,学术界浮躁,年轻人焦虑,少数有着远大志向的年轻人实际上是非常孤独的。这很像罗曼·罗兰笔下一战后的法国。罗曼·罗兰为那些追求灵魂高尚而非物质富裕的年轻人写下了《巨人三传》,让大家呼吸到巨人的气息。

  • 首先,小学生和中学生其实没有必要花那么多时间读书,而他们的社会经验、生活能力以及在那时树立起的志向将帮助他们的一生。第二,中学阶段花很多时间比同伴多读的课程,上大学以后用很短时间就能读完,因为在大学阶段,人的理解力要强得多。第三,学习(和教育)是持续一辈子的过程。第四,书本的内容可以早学,也可以晚学,但是错过了成长的阶段却是无法补回来的。(因此,少年班的做法不足取。)

  • 贾里尼克教授在学术上给我最大的帮助就是提高了我在学术上的境界。他告诉我最多的是:什么方法不好。在这一点上与股神巴菲特给和他吃饭的投资人的建议有异曲同工之处。

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

  • 在腾讯内部升级搜索引擎时,首先要改进和统一的就是所有搜索业务的索引,否则提高搜索质量就如同浮沙建塔一样不稳固。同样,我们在这本书中介绍搜索,也是从索引出发,因为它最基础,也最重要。

  • 最简单的所以呢结构是一个很长的二进制数表示一个关键字是否出现在每篇文献中。

第9章 图论和网络爬虫

  • 在网络爬虫中,人们使用一种“散列表”(Hash Table,也叫哈希表)而不是一个记事本记录网页是否下过的信息。

  • 如果一个图能够从一个定点出发,每条边不重复地遍历一遍回到这个顶点,那么每一顶点的度必须为偶数。

  • “如何构建一个网络爬虫”是我在Google最常用的一道面试题。一个好的候选人不需要做过网络爬虫也能很好地回答这道题。一般要考虑以下几点:

    • 首先,用BFS还是DFS?网络爬虫对网页遍历的次序不是简单的BFS或者DFS,而是有一个相对复杂的下载优先级排序的方法。管理这个优先级排序的子系统一般称为调度系统(Scheduler),由它来决定当一个网页下载完成后,接下来下载哪一个。其在工程上和BFS更相似,因此BFS成分多一些。

    • 第二,页面的分析和URL的提取。不像以前,现在URL可能藏匿于JavaScript代码中。

    • 第三,记录哪些网页已经下载过的小本本——URL表。采用散列表的好处是,判断一个网页URL是否在表中,平均只需一次(或者略多的)查找。常遇到的问题:首先,这张散列表会大到一台服务器存储不下。其次,由于每个下载服务器在开始下载前和完成下载后都要访问和维护这张表,以免不同的服务器做重复的工作,这个存储散列表的服务器的通信就成了整个爬虫系统的瓶颈。

  • 好的爬虫方法一般都采用了这样两个技术:首先明确每台下载服务器的分工,也就是说在调度时一看到某个URL就知道要交给哪台服务器去下载,以免很多服务器都要重复判断某个URL是否需要下载。然后,在明确分工的基础上,判断URL是否下载就可以批处理了,

  • 随着互联网的出现,图的遍历方法一下子有了用武之地。很多数学方法就是这样,看上去没有什么实际用途,但是随着时间的推移会突然排上大用场。这恐怕是世界上还有很多人毕业研究数学的原因。

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

  • 网页排名算法的高明之处在于它把整个互联网当作一个整体来对待。

  • 由于PageRank算法受到专利保护,它带来了两个结果。首先,其他搜索引擎开始时都比较遵守游戏规则,不去侵犯它,这对当时还很弱小的Google是一个很好的保护。第二,它使得斯坦福大学拥有了超过1%的Google股票,收益超过10亿美元。

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

  • TF-IDF(Term Frequency / Inverse Document Frequency)的概念被公认为信息检索中最重要的发明。即使是对搜索不是很精通的人,直接采用TF-IDF,效果也不会太差。

第12章 有限状态机和动态规划 —— 地图与本地搜索的核心技术

  • 有限状态机是一个特殊的有向图,它包括一些状态(节点)和连接这些状态的有向弧。每一个有限状态机都有一个开始状态和一个终止状态,以及若干中间状态。每一条弧上带有从一个状态进入下一个状态的条件。

  • 当用户输入的地址不太标准或者有错别字时,有限状态机会束手无策,因为它只能进行严格匹配。为了可以进行模糊匹配,科学家们提出基于概率的有限状态机。这种基于概率的有限状态机和离散的马尔可夫链基本上等效。

  • 在Google新一代的产品中,有限状态机的一个典型的应用是Google Now —— 一个在智能手机上的基于个人信息的服务软件。

  • 全球导航的关键算法是计算机科学图论中的动态规划(Dynamic Programming)的算法。

  • 正确的数学模型可以将一个计算量看似很大的问题的计算复杂度大大降低。这便是数学的妙用。

第13章 Google AK-47 的设计者 —— 阿米特·辛格博士

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

  • 许多失败并不是因为人不优秀,而是做事情的方法不对,一开始追求大而全的解决方案,之后长时间不能完成,最后不了了之。

  • 辛格坚持每天要分析一些搜索结果不好的例子,以掌握第一手的资料,即使在他成为Google Fellow以后,依旧如此。这一点,非常值得从事搜索研究的年轻工程师学习。事实上,我发现中国大部分做搜索的工程师在分析不好的结果上花的时间远比功成名就的辛格要少。

  • 辛格非常鼓励年轻人要不怕失败,大胆尝试。有一次,一位刚毕业不久的工程师因为把带有错误的程序推出到Google的服务器上而惶惶不可终日。辛格安慰她说,你知道,我在Google犯的最大一次错误是曾经将所有网页的相关性得分全部变成了零,于是所有搜索的结果全部都是随机的了。后来,这位出过错的工程师为Google开发出了很多好产品。

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

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

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

  • 我在大学学习线性代数时,实在想不出这门课除了告诉我们如何解线性方程外,还能有什么别的用途。后来在数值分析中又学了很多矩阵的近似算法,还是看不到可以应用的地方。当时选这些课,完全是为了挣学分得学位,今天大部分大学生恐怕也是如此。我想,很多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究,我才发现数学家们提出的那些矩阵的概念和算法,是有实际应用的意义的。

  • 在2007年,Google中国(谷歌)的张智威博士带领几个中国的工程师及实习生实现了奇异值的并行算法,这是Google中国对世界的一个贡献。

第16章 信息指纹及其应用

  • 一段文字所包含的信息,就是它的信息熵。如果对这段信息进行无损压缩编码,理论上编码后的最短长度就是它的信息熵。

第17章 由电视剧《暗算》所想到的 —— 谈谈密码学的数学原理

  • 在第二次世界大战中,很多顶尖的科学家包括提出信息论的香农都在为美军情报部门工作,而信息论实际上就是情报学的直接产物。

  • 根据信息论,密码的最高境界是敌方在截获密码后,对我方的所知没有任何增加,即信息量没有增加。

第18章 闪光的不一定是金子 —— 搜索反作弊问题和搜索结果的权威性问题

  • 网页搜索反作弊对搜索引擎公司来讲是一项长期的任务。作弊的本质是在网页排名信号中加入了噪音,因此反作弊的关键是去噪音。沿着这个思路可以从根本上提高搜索算法抗作弊的能力,事半功倍。

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

  • 其实,托勒密在天文学上的地位堪比欧几里得之于几何学,牛顿之于物理学。

  • 一个正确的数学模型一般有以下特点:

    1. 在形式上是简单的;

    2. 一开始可能还不如一个精雕细琢过的错误模型来的准确;

    3. 大量准确的数据对研发很重要;

    4. 可能会受噪音干扰,而显得不准确,这时需要找到噪音的根源。

第20章 不要把鸡蛋放到一个篮子里 —— 谈谈最大熵模型

  • 最大熵原理指出,对一个随机事件的概率分布进行预测时,我们的预测应当满足全部已知条件,而对未知的情况不要做任何主观假设,使得概率分布最均匀,预测的风险最小。

  • 最大熵模型在形式上是最漂亮、最完美的统计模型,在自然语言处理和金融方面有很多有趣的应用。注意其在实现上异常复杂,计算量非常大。

  • 通用迭代算法GIS(Generalized Iterative Scaling):

    1. 假定第零次迭代的初始模型为等概率的均匀分布。

    2. 用第N次迭代的模型来估算每种信息特征在训练数据中的分布。如果超过了实际的,就把相应的模型参数变小。否则,将它们变大。

    3. 重复步骤2,直到收敛。

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

  • 输入法输入汉字的快慢取决于汉字编码的平均长度。

  • 对汉字编码分为两部分:对拼音的编码和消除歧义性的编码。

  • 由于种种原因,早期的拼音输入法不是很成功,这就给其他输入法的迅速崛起创造了条件。

第22章 自然语言处理的教父马库斯和他的优秀弟子们

  • 马库斯的主张一贯是建立几个世界上最好的专业,而不是专业最齐全的系。我觉得,当今中国的大学,最需要的就是马库斯这样卓有远见的管理者。

第23章 布隆过滤器

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

  • 布隆过滤器背后的数学原理在于两个完全随机的数字相冲突的概率很小。

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

第25章 条件随机场、文法分析及其他

  • 条件随机场是无向图,而贝叶斯网络是有向图。

  • 使用条件随机场模型预测洛杉矶地区犯罪在2011年被《时代》周刊誉为年度最优秀的发明之一。

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

  • 码分多址(CDMA)、频分多址(FDMA)、时分多址(TDMA)。

  • 世界上绝大多数科学家最大的满足就是自己的研究成果得到同行的认可,如果能有应用就更是喜出望外了。而能够亲自将这些成就应用到实际中的人少之又少,因为做到这一点对科学家来讲很不容易。

第27章 上帝的算法 —— 期望最大化算法

  • EM算法只需要有一些训练数据,定义一个最大化函数,剩下的事情就交给计算机了。经过若干次迭代,我们需要的模型就训练好了。这实在是太美妙了,这也许是造物主刻意安排的。

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

  • 搜索广告之所以比传统的在线展示广告赚钱多很多,除了搜索者的意图明确外,更重要的是靠预测用户可能会点击哪些广告,来决定搜索结果页中插入哪些广告。

  • 逻辑回归模型是指将一个事件出现的概率逐渐适应到一条逻辑曲线(Logistic Curve,其值域在(0,1)之间)上。逻辑曲线是一条S型曲线,特点是一开始变化快,逐渐减慢,最后饱和。

第29章

  • 分治算法是计算机科学中最漂亮的工具之一。它的基本原理是:将一个复杂的问题,分成若干个简单的子问题进行解决。然后,对子问题的结果进行合并,得到原有问题的解。

  • 将一个大任务拆分成小任务,并且完成子任务的计算,这个过程叫做Map,将中间结果合并成最终结果,这过过程叫做Reduce。这就是MapReduce。

第30章 Google大脑和人工神经网络

  • 通过“Google大脑”的深度学习后,语音识别的错误率从13.6%下降至11.6%。大家可不要小看这两个百分点,要做到这一点,通常需要全世界语音识别专家们努力两年左右。

  • 如果有幸遇到一个好心同时又善于表达的科学家或教授,他愿意花一两个小时的时间,深入浅出地为你讲解人工神经网络的底细,你就会发现,“哦,原来是这么回事”。

  • Google大脑并不是一个什么都能思考的大脑,而是一个很能计算的人工神经网络。因此,与其说Google大脑很聪明,不如说它很能算。

第31章 大数据的威力 —— 谈谈数据的重要性

  • 在Google内部,产品经理们都遵循这样一个规则:在没有数据之前,不要给出任何结论。

  • 数据不仅在科学研究中,而且在生活的方方面面都很重要,它应该成为我们日常做决策的依据。

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

附录 计算复杂度

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

后记

  • 无论是在美国还是在中国,我经常看到大部分软件工程师在一个未知领域都是从直观感觉出发,用“凑”的方法来解决问题,在中国尤其如此。这样的做法说得不好听,就是山寨。

  • 在国内,创业小公司做事情重量不重质,倒也无可厚非;但是,上了市、有了钱甚至利润成为在世界上也数得上的公司,做事情依然如此,就让人觉得境界低。另一方面,在修建大楼和装修高管办公室的投入上,这些公司倒是很快超越了许多跨国公司。

  • 世界上最好的学者总是有办法深入浅出地把大道理将给外行听,而不是故弄玄虚地把简单的问题复杂化。

《数学之美》豆瓣地址

0%