「数学之美」书摘

本文主要摘自「数学之美」(第二版)的关键内容,摘取内容与原书相比肯定不够全面。如果对此书内容感兴趣,强烈建议阅读原书。

image

以下为摘取内容(为了辅助说明,部分内容同时引用了相关网络资源,均有出处链接):

文字和语言与数学,从产生起原本就有相通性,虽然它们的发展一度分道扬镳,但是最终还是能走在一起。

人类对机器理解自然语言的认识走了一条大弯路。早起的研究中采用基于规则的方法,虽然解决了一些简单的问题,但是无法从根本上将自然语言理解实用化。直到多年以后,人们开始尝试基于统计的方法进行自然语言处理,才有了突破性进展和实用的产品。

统计语言模型是自然语言处理的基础,并且被广泛应用于机器翻译、语音识别、印刷体或手写体识别、拼写纠错、汉字输入和文献查询。

中文分词是中文信息处理的基础,它同样走过了一段弯路,目前依靠统计语言模型已经基本解决了这个问题。

隐含马尔可夫模型最初应用于通信领域,继而推广到语音和语言处理中,成为连接自然语言处理和通信的桥梁。同时,隐含马尔可夫模型也是机器学习的主要工具之一。

WIKI:隐马尔可夫模型

隐马尔可夫模型(Hidden Markov Model,HMM)是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。

在正常的马尔可夫模型中,状态对于观察者来说是直接可见的。这样状态的转换概率便是全部的参数。而在隐马尔可夫模型中,状态并不是直接可见的,但受状态影响的某些变量则是可见的。每一个状态在可能输出的符号上都有一概率分布。因此输出符号的序列能够透露出状态序列的一些信息。

信息是可以量化度量的。信息熵不仅是对信息的量化度量,也是整个信息论的基础。它对于通信、数据压缩、自然语言处理都有很强的指导意义。

作为现代自然语言处理的奠基者,贾里尼克教授成功地将数学原理应用于自然语言处理领域中,他的一生富于传奇色彩。

布尔代数虽然非常简单,却是计算机科学的基础,它不仅把逻辑和数学合二为一,而且给了我们一个全新的视角看待世界,开创了数字化时代。

互联网搜索引擎在建立索引前需要用一个程序自动地将所有的网页下载到服务器上,这个程序称为网络爬虫。它的编写是基于离散数学中图论的原理。

图论:图由一些节点和连接这些节点的弧组成。网络爬虫基于图论进行网页下载。

  • BFS (Breadth-First Search),广度优先搜索。
  • DFS (Depth-First Search):深度优先搜索。

PageRank:网页民主排名。

核心思想为:如果一个网页被很多网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。

TF-IDF:网页与查询相关性度量。

  • TF:Term Frequency,词频。
  • IDF:Inverse Document Frequency,逆文本频率指数。信息检索中使用最多的权重。

阮一峰的网络日志『TF-IDF与余弦相似性的应用(一):自动提取关键词』

第一步,计算词频。

考虑到文章有长短之分,为了便于不同文章的比较,进行“词频”标准化。

词频(TF)= 某个词在文章中的出现次数 / 文章总词数

第二步,计算逆文档频率。

这时,需要一个语料库(corpus),用来模拟语言的使用环境。

逆文档频率(IDF)= log(语料库的文档总数 / 包含该词的文档数 + 1)

如果一个词越常见,那么分母就越大,逆文档频率就越小越接近 0 。分母之所以要加 1,是为了避免分母为 0(即所有文档都不包含该词)。log表示对得到的值取对数。

第三步,计算 TF-IDF。

TF-IDF = 词频(TF) * 逆文档频率(IDF)

可以看到,TF-IDF 与一个词在文档中的出现次数成正比,与该词在整个语言中的出现次数成反比。

地图和本地服务中要用到有限状态机和动态规划技术。这两项技术是机器智能和机器学习的工具,它们的应用非常广泛,还包括语音识别、拼写和语法纠错、拼音输入法、工业控制和生物的序列分析等。

「地址」是种有限状态机,导航的关键算法是图论中的动态规划。

WIKI:有限状态机

有限状态机(Finite-State Machine,FSM)又称有限状态自动机,简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

在计算机科学中,有限状态机被广泛用于建模应用行为、硬件电路系统设计、软件工程、编译器、网络协议和计算与语言的研究。

WIKI:动态规划

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题,它们的结果都逐渐被计算并被保存,从简单的问题直到整个问题都被解决。因此,动态规划保存递归时的结果,因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足,故有时需要引入一定的近似)。简单地说,问题能够分解成子问题来解决。

辛格做事的哲学:先帮助用户解决 80% 的问题,再慢慢解决剩下的 20% 问题,是在工业界成功的秘诀之一。

计算机虽然读不懂新闻,却可以准确地对新闻进行分类。其数学工具是看似毫不相干的余弦定理。

阮一峰的网络日志『TF-IDF与余弦相似性的应用(二):找出相似文章』

因此,我们可以通过夹角的大小,来判断向量的相似程度。夹角越小,就代表越相似。

余弦值越接近 1,就表明夹角越接近 0 度,也就是两个向量越相似,这就叫“余弦相似性”。

  1. 使用 TF-IDF 算法,找出两篇文章的关键字;
  2. 每篇文章各取出若干个关键词(比如 20 个),合并成一个集合,计算每篇文章对于这个集合中的词的词频(为了避免文章长度的差异,可以使用相对词频);
  3. 生成两篇文章各自的词频向量;
  4. 计算两个向量的余弦相似度,值越大就表示越相似。

“余弦相似性”是一种非常有用的算法,只要是计算两个向量的相似程度,都可以采用它。

无论是词汇的聚类还是文本的分类,都可以通过线性代数中矩阵的奇异值分解来进行。这样一来,自然语言处理的问题就变成了一个数学问题。

世间万物都有一个唯一标识的特征,信息也是如此。每一条信息都有它特定的指纹,通过这个指纹可以区别不同的信息。

密码学的根本是信息论和数学。没有信息论指导的密码是非常容易被破解的。只有在信息论被广泛应用于密码学后,密码才真正变得安全。

搜索引擎中排名靠前的网页也未必是有用的网页。消除这些作弊网页的原理和通信中过滤噪音的原理相同。

正确的数学模型在科学和工程中至关重要,而发现正确模型的途径常常是曲折的。正确的模型在形式上通常是简单的。

最大熵模型是一个完美的数学模型。它可以将各种信息整合到一个统一的模型中,在信息处理和机器学习中有着广泛的应用。它在形式上非常简单、优美,而在实现时需要有精深的数学基础和高超的技巧。

汉字的输入过程本身就是人和计算机之间的通信。好的输入法会自觉或不自觉地遵循通信的数学模型。当然要做出最有效的输入法,应当自觉使用信息论做指导。

将自然语言处理从基于规则的研究方法转到基于统计的研究方法上,宾夕法尼亚大学的教授米奇·马库斯功不可没。他创立了今天在学术界广泛使用的 LCD 语料库,同时培养了一大批精英人物。

判断一个元素是否在一个集合中,布隆过滤器是计算机工程中解决这个问题最好的数学工具。

贝叶斯网络是一个加权的有向图,是马尔可夫链的扩展。而从认识论的层面看:贝叶斯网络克服了马尔可夫链那种机械的线性约束,它可以把任何有关联的事件统一到它的框架下面。它在生物统计、图像处理、决策支持系统和博弈论中都有广泛的使用。

条件随机场是计算联合概率分布的有效模型,而句法分析似乎是英文课上英语老师教的东西,这两者有什么联系呢?

维特比算法是现代数字通信中使用最频繁的算法,同时也是很多自然语言处理的解码算法。可以毫不夸张地讲,维特比是对我们今天生活的影响力最大的科学家之一。因为如今基于 CDMA 的 3G 移动通信标准主要就是他创办的高通公司制定的。

只要有一些训练数据,再定义一个最大化函数,采用 EM 算法,利用计算机经过若干次迭代,就可以得到所需要的模型。这实在是太美妙了,这也许是我们的造物主刻意安排的。所以我把它称作上帝的算法。

逻辑回归模型是一种将影响概率的不同因素结合在一起的指数模型,它不仅在搜索广告中起着重要的作用,而且被广泛应用于信息处理和生物统计中。

Google 颇为神秘的云计算中最重要的 MapReduce 工具,其原理就是计算机算法中常用的“各个击破”算法,它的原理原来这么简单——将复杂的大问题分解成很多小问题分别求解,然后再把小问题的解合并成原始问题的解。由此可见,在生活中大量用到的、真正有用的方法常常都是简单朴实的。

Google 大脑并不是一个什么都能思考的大脑,而是一个很能计算的人工神经网络。因此,与其说 Google 大脑很聪明,不如说它很能算。不过,换个角度来说,随着计算能力的不断提高,计算量大但简单的数学方法有时能够解决很复杂的问题。

如果说在过去的 40 年里,主导全球 IT 产业发展的是摩尔定律,那么在今后的 20 年里,主导 IT 行业继续发展的动力则将来自于数据。