读书笔记|数学之美(Beauty Of Mathmetics)

摘要

  • 作者:吴军
  • 起源:Google中国的官方博客–谷歌黑板报连载的系列博客
  • 主题:自然语言处理、科技史

数学的魅力就在于将复杂的问题复杂化

人类信息交流的发展贯穿了人类的进化和文明的全过程。而自然语言是人类交流信息的工具,语言和通信的联系是天然的。通信的本质就是一个解编码和传输的过程。(p49)

《数学之美》 Topic

  • 自然语言识别与概率论:第 3、5、24 章
  • 信息论:第 6 章

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

故事:罗赛塔石牌、犹太人抄圣经(校验)、口语和文言文(信道压缩)

  • 通信的原理和信息传播的模型
  • (信源)编码和最短编码
  • 解码的规则,语法
  • 聚类
  • 校验位
  • 双语对照文本,语料库和机器翻译
  • 多义性和利用上下文消除歧义性

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

Tips:

自然语言发展阶段

  • 20世纪50-70年代:基于规则的方法,电脑模拟人脑理解语法、文法,收效甚微
  • 20世纪70年代以后:基于数学模型和统计的方法。例如翻译,计算机不需要像人类一样理解两种语言。

人物

长达15年的对峙时期

两派人马各自召开自己的会议,持续争议。

基于统计方法的发展

  • 上世纪70年代:基于统计的方法的核心模型是通信系统加隐含马尔可夫模型。
    输入和输出都是一维的符号序列,保持原有的次序。最早的语音识别、词性分析取得成果;句法分析中输入的是一维的句子,输出的是二维的分析树;机器翻译中,输出的句子次序会有很大变化,效果不佳。

  • 1998年,彼得·布朗(Peter Brown) | IBM 等提出了基于统计的机器翻译方法效果很差,模型、数据不足。
    (文艺复兴技术公司)

  • 基于有向图的统计模型解决复杂的句法分析。

  • 20世纪90年代末期:通过统计得到的句法规则甚至比语言学家总结的更有说服力。

  • 2005年,Google 基于统计方法的翻译系统全面超过基于规则方法的 SysTran 翻译系统

科学史的教训:等待老科学家退休

基于统计的方法代替传统的方法,需要等原有的一批语言学家退休。“老的科学家” 或者 “老科学的家” (钱钟书《围城》),后一种年纪不算老,但是已经落伍,大家必须耐心等待他们退休让出位子。毕竟,不是所有人都乐意改变自己的观点,无论对错。 …… 因此,我常想,我自己一定要在还不太糊涂和固执时就退休(p25)

第三章 统计语言模型

计算机处理自然语言的基本问题:为自然语言这种上下文相关的特性建立数学模型,即 统计语言模型(Statistical Language Model)

贾里尼克:一个句子是否合理,就看看它的可能性大小如何。可能性用概率来衡量。

P(S) = P(W1 ,W2, … , Wn)
=P(W1)·P(W2|W1) ·P(W3|W1,W2) ··· P(Wn | W1,W2, … , Wn-1)

S 表示某一个有意义的句子,由一连串特定顺序排列的词W1,W2, ··· , Wn 组成,n 是句子的长度。句子越长,条件概率 P(Wn | W1,W2, … , Wn-1) 的可能性越多,无法估算。

19 世纪到 20 世纪初,马尔可夫(Andrey Markov)提出假设,任意一个词 Wi 出现的概率只同它前面的词 Wi-1有关,偷懒但颇为有效的方法。【符合这个假设的随机过程则称为马尔科夫过程,也称为马尔可夫链。】二元模型( Bigram Model )对应的公式如下:

P(S) = P(W1 ,W2, … , Wn)
=P(W1)·P(W2|W1) ·P(W3|W2) ··· P(Wi | Wi-1) ··· P(Wn | Wn-1)

语料库( Corpus ): 大量机读样本
相对频度
根据 大数定理( Law of Large Numbers ),只要统计量足够,相对频度就等于概率
推导过程省略(P30)

延伸阅读:统计语言模型的工程诀窍

  • 2.1 高阶语言模型
    很少有人能使用四元以上的模型,Google 的罗塞塔翻译系统和语言搜索引擎使用四元模型,该模型存储于 500 台 以上的 Google 服务器中。

马尔可夫假设的局限性:自然语言中上下文相关性跨度可能非常大,需采用其他一些 长程的依赖性( Long Distance Dependency ) 来解决。

  • 2.2 模型的训练、零概率问题和平滑方法

  • 古德·图灵估计( Good-Turing Estimate)

一种概率估计方法:1953年,古德( I. J. Good)、图灵( Alan Turing )提出,在统计中相信可靠的统计数据,而对不可信的统计数据打折扣,同时将折扣出来的那一小部分概率给予未看见的事件( Unseen Events )。

如果训练语料与模型应用的领域相脱节,那么模型的效果通常要大打折扣。例如腾讯搜索部门的语言模型,最早使用《人民日报》的语料训练(干净、无噪音),实际效果不佳,之后使用网页的数据,尽管有很多噪音但是训练数据与应用一致,搜索质量反而好。

第四章 谈谈中文分词

  • 早期的分词:《说文解字》和《论语》注解,目的都是为了以一家的理解消除歧义性
  • 分词准确率:不是越高越好,而要看所谓正确的人工分词的数据是如何得来的。我们甚至只能讲某个分词器和另一个分词器相比,与人工分词结果的吻合度稍微高一点而已。目前采用统计语言模型,(选择哪种分词器)效果都差不到哪里去。

第五章 隐含马尔可夫模型

计划:201706
通读:201709

人类信息交流的发展贯穿了人类的进化和文明的全过程。而自然语言是人类交流信息的工具,语言和通信的联系是天然的。通信的本质就是一个解编码和传输的过程。但是自然语言处理早期的努力都集中在语法、语义和知识表述上,离通信的原理越来越远,而这样答案也就越来越远。当自然语言处理的问题回归到通信系统中的解码问题时,很多难题都迎刃而解了。(p49)

  • 雅格布森( Roman Jakobson)提出的通信六个要素
1
2
3
4
5
6
7
8
9
10
11
digraph communicate{
label="雅格布森提出的通信六个要素";

信息和上下文[label = "信息和上下文(发送者)"];
传递的信息[label = "传递的信息(信道)"];
接收的信息[label = "接收的信息(接收者)"];

信息和上下文 -> 传递的信息[label = "编码(S1,S2,S3,···)"];
传递的信息 -> 接收的信息[label = "解码(O1,O2,O3,···)"];

}
  • 马尔可夫链:符合这个马尔可夫假设的随机过程则称为马尔科夫过程。
1
2
3
4
5
6
7
8
9
digraph markov{
label = " 马尔可夫模型( Markov Model )";
rankdir = LR;
m1->m2[label = "1.0"];
m2->m3[label = "0.6"];
m3->m4[label = "0.3"];
m2->m4[label = "0.4"];
m3->m3[label = "0.7"];
}

  • 隐含马尔可夫模型( Hidden Markov Model )
    最早由20世纪六七十年代,美国数学家鲍姆( Leonard E. Baum ) 发表的一系列论文中提出。隐含马尔可夫模型是马尔可夫链的一个扩展,即任一时刻 t 的状态 St 是不可见的。但是,在每个时刻 t 会输出一个富豪 Ot ,而且 Ot 和 St 相关且仅和 St 相关。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
digraph hiddenmarkov{
label = " 隐含马尔可夫模型( Hidden Markov Model )";
rankdir = LR;

S1->S2[label = ""];
S1->O1[label = ""];

S2->S3[label = ""];
S2->O2[label = ""];

S3->S4[label = ""];
S3->O3[label = ""];

S4->O4[label = ""];
}

  • 隐马尔可夫模型的应用
    隐含马尔可夫模型成功的应用最早是语音识别(Sphinx——大词汇量连续语音识别系统)。根据应用的不同而有不同的名称,例如语音识别中的声学模型( Acoustic Model ),机器翻译中的翻译模型( Translation Model )等。

延伸阅读隐含马尔可夫模型的训练

  • 知识背景:概率论
  • 围绕隐含马尔可夫模型的基本问题
    1. 给定一个模型,如何计算某个特定输出序列的概率;
      Forward-Backward 算法
      参考书 Frederick Jelinek《Statistical Methods for Speech Recognition(Language, Speech, and Communication)》
    2. 给定一个模型和某个特定的输出序列,如何找到最可能产生这个输出的状态序列
      解码算法:维特比算法
    3. 给定足够量的观测数据,如何估计隐含马尔可夫模型的参数。
      绚练算法:鲍姆-韦尔奇算法(Baum-Welch Algorithm)

第六章 信息的度量和作用

  • 信息熵
    要搞清楚意见非常非常不确定的事,或是我们一无所知的事情,就需要了解大量的信息。
    相反,如果我们对某件事已经有了较多的了解,那么不需要太多的信息就能把它搞清楚。
    所以,从这个角度来看,可以认为,信息量就等于不确定性的多少。

  • 信息的作用
    在英语里,信息和情报是同一个词( Information ),而我们知道情报的作用就是排除不确定性。

  • 案例:斯大林、日军南下战略情报

如果没有信息,任何公式或者数字的游戏都无法排除不确定性。这个朴素的结论非常重要,但是在研究工作中经常被一些半瓶子醋的专家忽视,希望做这方面工作的读者谨记

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

延伸阅读:信息论在信息处理中的应用

  • 信息熵
  • 冗余度 ( Redundancy )
  • 互信息 ( Mutual Information ),量化地度量相关性
  • 相对熵 ( Relative Entropy 或 Kullback-Leibler Divergence )

信息论参考文献

  • 《A Mathematic Theory of Communication》(“通信的数学原理”),香农( Claude Shannon ),1948
  • 《Elements of Information Theory》(“信息论基础”),托马斯·科弗( Thomas Cover )

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

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

第九章 图论和网络爬虫

计划:201706
通读:20170927

  • 交通路径规划
  • 深度优先搜索( Depth-First Search , DFS)
  • 广度优先搜索( Breadth-First Search , BFS)
  • 网络爬虫 ( Web Crawlers ) :超链接 ( Hyperlinks )

延伸阅读:图论的亮点补充说明

  1. 欧拉七桥问题的证明
  2. 构建网络爬虫的工程要点:
    1)搜索引擎的调度(BFS)
    2)页面分析和 URL 的提取
    3)记录哪些网页已经下载( URL 表)

很多数学方法就是这样,看上去没有什么实际用途,但是随着时间的推移会一下子派上大用场。这恐怕是世界上还有很多人毕生研究数学的原因。

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

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

第十二章 地图和本地搜索的最基本技术——有限状态机和动态规划

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

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

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

第十六章 信息指纹及其应用

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

计划:201706

第十八章 闪光的不一定是金子——谈谈搜索引擎反作弊问题

第十九章 谈谈数学模型的重要性

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

第二十一章 拼音输入法的数学模型

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

第二十三章 布隆过滤器

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

计划:201706
通读:20170925

贝叶斯网络(Bayesian network) 是一种概率图型模型。

一般而言,贝叶斯网络中的节点表示随机变量,连接两个节点的箭头代表此两个随机变量是具有因果关系的;而两个节点间若没有箭头相互连接一起,表明他们之间没有直接的因果关系(注:并不表明A不会通过其他状态间接地影响状态B)。所有这些(因果)关系,都可以有一个量化的可信度(Belief),用一个概率描述。也就是说,贝叶斯网络的弧上可以有附加的权重。因此,贝叶斯网络也被称作 信念网络(Belief Networks) 或者 有向无环图模型(directed acyclic graphical model)

案例:描述心血管疾病和成因

一个简单的贝叶斯网络案例,描述心血管疾病和成因。

1
2
3
4
5
6
7
8
9
10
11
12
13
digraph diseaseCVD{
label="\n 案例:一个描述心血管疾病和成因的贝叶斯网络 \n";
心血管疾病->胆固醇量;
心血管疾病->血脂;
心血管疾病->吸烟;
心血管疾病->运动量;
心血管疾病->家族病史;
胆固醇量->运动量;
胆固醇量->饱和脂肪摄取量;
胆固醇量->家族病史;
血脂->饱和脂肪摄取量;
血脂->家族病史;
}

上面的例子进一步简化之后,假定只有三个状态 “心血管疾病”,“高血脂”和“家族病史”。假定每个状态只有“有”、“无”两种,并且给出组合状态的条件概率。

1
2
3
4
5
6
digraph SimpleDiseaseCVD{
label="\n 案例:心血管疾病和成因的贝叶斯网络(简化) \n";
心血管疾病->高血脂;
心血管疾病->家族病史;
高血脂->家族病史;
}
心血管疾病 家族病史、高血脂
0.9 0.1
0.4 0.6
0.4 0.6
0.1 0.9
高血脂 家族病史
0.4 0.6
0.1 0.9

联合概率分布(贝叶斯公式):

P(家族病史,高血脂,心血管疾病) = P(家族病史|高血脂,心血管疾病)x P(高血脂|家族病史)x P(家族病史)

例如,计算心血管疾病有多大概率是由家族病史引起的。

P(家族病史|有心脏病) = P(有家族病史,有心脏病)/ P(有心脏病)

其中:

P(有家族病史,有心脏病) = P(有家族病史,有心脏病,无高血脂)+ P(有家族病史,有心脏病,有高血脂)

P(有心脏病) = P(有家族病史,有心脏病,无高血脂)+ P(有家族病史,有心脏病,有高血脂)+ P(无家族病史,有心脏病,无高血脂)+ P(无家族病史,有心脏病,有高血脂)

P(有家族病史,有心脏病) = 0.18 x 0.4 + 0.12 x 0.4
= 0.12

P(有心脏病) = 0.12 + 0.08x0.4 + 0.72x0.1
= 0.12 + 0.144
= 0.264

第二十五章 条件随即场和句法分析

第二十六章 维特比和他的维特比算法

第二十七章 再谈文本自动分类问题——期望最大化算法

第二十八章 逻辑回归和搜索广告

第二十九章 各个击破算法和Google云计算的基础

第三十章 逻辑回归和搜索广告

扩展阅读

参考文献

推荐文章