数学之美


C3: 统计语言模型 and C5: 隐含马尔可夫模型


C6: 信息的度量和作用

信息熵是对不确定性的衡量, 因此可以想象信息熵能直接用于衡量统计语言模型的好坏. 当然, 因为有了上下文的条件, 所以对高阶的语言模型, 应该用条件熵. 如果再考虑到从训练语料和真实应用的文本中得到的概率函数有偏差, 就需要再引入相对熵的概念.


C7: 贾里尼克和现代语言处理

每当弗莱德和我谈起各自少年时的教育, 我们都同意这样几个观点. 首先, 小学生和中学生其实没有必要花那么多时间读书, 而他们的社会经验, 生活能力, 以及在那时树立起的志向将帮助他们的一生. 第二, 中学阶段花很多时间比同伴多读的课程, 上大学以后用很短时间就能读完, 因为大学阶段, 人的理解能力要强得多. 举个例子, 在中学需要花500小时才能学会的内容, 在大学可能花100小时就够了. 因此, 一个学生在中小学阶段建立的那一点点优势在大学很快就会丧失殆尽. 第三, 学习(和教育)是持续一辈子的过程, 很多中学成绩优异的亚裔学生进入名校后表现明显不如那些出于兴趣而读书的美国同伴, 因为前者持续学习的动力不足. 第四, 书本的内容可以早学, 也可以晚学, 但是错过了成长阶段却是无法补回来的. (因此, 少年班的做法不足取) 现在中国的好学校, 恐怕百分之九十九的孩子在读书上花的时间比我当时要多, 比贾里尼克要多得多, 但是这些孩子今天可能有百分之九十九在学术上的建树不如我, 更不如贾里尼克. 这实在是教育的误区.

贾里尼克从头开始, 在短短两三年内就将CLSP(Center for Language and Speech Processing)变成世界一流的研究中心. 他主要做了两件大事, 两件小事. 两件大事是, 首先, 从美国政府主管研究的部门那里申请到了许多研究经费, 然后, 每年夏天, 他用一部分经费, 邀请世界上20-30名顶级的科学家和兄生到CLSP一起工作, 使得CLSP变成世界上语音和语言处理的中心之一. 两件小事是, 首先他招募了一批当时很有潜力的年轻学者, 第二他利用自己的影响力, 在暑期把他的学生拍到世界上最好的公司去实习, 通过这些学生的优异表现, 树立起CLSP在培养人才方面的声誉.


C8 简单之美-布尔代数和搜索引擎

但是真正做好一件事情是没有捷径, 离不开一万小时的专业训练和努力. 最好搜索, 最基本的要求是每天分析10-20个不好的搜索结果, 累积一段时间才会有感觉. 我在Google改进搜索质量的时候每天分析的搜素数量远不止这个, Google的搜索质量第一技术负责人Amit Singhal至今依然经常分析那些不好的搜索结果. 但是, 很多搜索的工程师(美国的, 中国的都有)都做不到这一点, 他们总是期望靠一个算法, 一个模型就能毕业其功于一役, 而这是不现实的.


C11 如何确定网页和查询的相关性


C15 矩阵运算和文本处理中的两个分类问题.


C16 信息指纹及其应用

视频的匹配有两个核心技术, 关键帧的提取和特征的提取(信息指纹表示关键帧). 有了这些信息指纹之后, 检测是否盗版就类似于比较两个集合元素是否相同了. Google收购Youtube后, 由Google研究院研究图像处理的科学家们开发出的反盗版系统, 效果非常好. 由于可以找出相同的视频的原创和拷贝, Google制定了一个很有意思的广告分成策略: 虽然所有的视频都可以插入广告, 但是广告的收益全部提供给原创的视频, 即使广告是插入在拷贝的视频. 这样一来, 所有拷贝和上传别人的视频的网站就不可能获得收入. 没有了经济利益, 也就少了很多盗版和拷贝.


C20 谈谈最大熵模型

最大熵原理指出,对一个随机事件的概率分布进行预测时,我们的预测应当满足全部已知的条件,而对未知的情况不要做任何主观假设(不做主观假设这点很重要)。在这种情况下,概率分布最均匀,预测的风险最小。因为这时概率分布的信息熵最大,所以人们把这种模型叫做“最大熵模型”。我们常说,不要把所有的鸡蛋放在同一个篮子里,其实就是最大熵原理的一个朴素说法,因为当我们遇到不确定性时,就要保留各种可能性。

最原始的最大熵模型的训练方法是一种称为通用迭代算法GIS(Generalized Iterative Scaling)的迭代算法,是一个典型的期望值最大化算法(Expectation Maximization, EM). 但是运算效率非常低,改进迭代算法(IIS, Improved Iterative Scaling)可以将训练时间缩短1~2个数量级。


C27 上帝的算法-期望最大化算法

在一般性的问题中,如果有非常多的观测数据点,可以用如下方法,让计算机不断迭代来学习一个模型:首先根据现有的模型,计算各个观测数据输入到模型中的计算结果,这个过程成为期望值计算过程(Expectation), 或E过程;接下来重新计算模型参数,以最大化期望值,这个过程成为最大化的过程(Maximization), 或M过程。这一类算法都称为EM算法。

前面介绍的很多算法,其实都是EM算法,比如隐式马尔科夫模型的训练方法Baum-Welch算法,以及最大熵模型的训练方法GIS算法。在BM算法中,E过程就是根据现有的模型计算每个状态之间转移的次数以及每个状态产生它们的输出次数,M过程就是根据这些次数重新估计隐含马尔可夫模型的参数,这里最大化的目标函数就是观测值的概率。在最大熵模型的通用迭代算法GIS中,E过程就是跟着现有的模型计算每一个特征的数学期望值,M过程就是根据这些特征的数学期望值和实际观察值的比值,调整模型参数,这里最大化的目标函数就是熵函数。


C30 Google大脑和人工神经网络

人工神经网络和贝叶斯网络至少有这样几个共同点:

  1. 它们都是有向图,每一个节点的取值只取决于前一级的节点,而于更前面的节点无关,也就是说遵从马尔可夫假设。
  2. 它们的训练方法类似。
  3. 对于很多模式分类问题上,这两种方法在效果上类似,也就是说很多用人工神经网络解决的问题,也能用贝叶斯网络解决,反之亦然,但是它们的效率可能会不同。如果把人工神经网络和贝叶斯网络都看做统计模型,那么这两种模型的准确性也是类似的。
  4. 它们的训练计算量都特别大,对此大家在使用人工神经网络时要有心理准备。

不过人工神经网络和贝叶斯网络还是有不少不同之处的:

  1. 人工神经网络在结构上是标准化的,而贝叶斯网络更灵活。G大脑选用NN就是看中它的标准化这点。
  2. 虽然神经元函数为非线性函数,但是各个变量只能先进行线性组合,然后对最终变量做非线性变化,因此计算机实现起来比较容易。而在贝叶斯网络中,变量可以组合成为任意函数,毫无限制,在获得灵活性的同时,也增加了复杂性。
  3. 贝叶斯网络更容易考虑(上下文)前后的相关性,因此可以解码一个输入序列。而NN的输出相对孤立,很难处理一个序列。因此她主要的应用常常是估计一个概率模型的参数,比如语音识别中声学模型参数的训练,机器翻译中语言模型参数的训练等,而不是作为解码器。

Google大脑为什么要采用人工神经网络而不是其他机器学习技术呢?这里面的原因有三:


Appendix. 计算复杂度


Appendix. 第二版后记

无论是在美国还是在中国, 我经常看到大部分软件工程师在一个未知领域都是从直观感觉出发, 用"凑"的方法来解决问题, 在中国尤其如此. 这样的做法说得不好听, 就是山寨. 我刚到Google时, 发现Google早期的一些算法(比如拼写纠错)根本没有系统的模型和理论基础, 就是用词组或者词的二元组凑出来. 这些方法也算是聊胜于无, 但是几乎没有完善和提高的可能, 而且使得程序的逻辑非常混乱. 随着公司的成长和实力的壮大, Google开始从全球最好的大学招揽理论基础优异的工程师, 工程的正确性得到了很好保证. 2006年后, 我知道了三四个美国名校毕业的研究生, 用隐含马尔可夫模型的框架把Google的拼写纠错模型统一起来. 在那几年里, Google几乎重写了所有项目的程序, 山寨的东西基本上看不到了.

comments powered by Disqus