数学之美

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

N-1阶马尔可夫假设: 假定文本中的每个词w[i]和前面N-1个词有关, 而与更前面的词无关. 对应的语言模型称为N元模型(N-Gram Model).
马尔可夫过程: 随机过程是研究随机变量的时间序列s1,s2…s[t]. 符合马尔可夫假设的随机过程成为马尔可夫过程, 也成为马尔可夫链.
隐含马尔可夫模型: 任一时刻t的状态s[t]是不可见的, 所以观察者没有办法通过观察到一个状态序列s1,s2…s[t]来推测转移概率等参数, 但是隐含的状态s1,s2…s[t]是一个马尔可夫链. 同时每个时刻会输出一个符合o[t], 而且o[t]跟s[t]相关且仅跟s[t]相关. o[t]被称为独立假设输出. P(s1,s2…o1,o2…) = \PROD (P(s[t] | s[t-1]) * P(o[t] | s[t])). 针对不同应用,P(s1,s2..o1,o2…)的名称也各不相同: 在语音识别中它被成为"声学模型"(Acoustic Model), 在机器翻译中是"翻译模型"(Translation Model), 而在拼写校正中是"纠错模型"(Correction Model).

C6: 信息的度量和作用

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

信息熵(Entropy): H(x) = \SUM (-P(x) * log(P(x)))
条件熵(Conditional Entropy):
- P(x,y) # 联合概率分布(Joint Probability)
- P(x|y) # 条件概率分布(Conditional Probability)
- H(X|Y) = \SUM (-P(x,y) * log(P(x|y))) # 一个条件
- H(X|Y,Z) = \SUM (-P(x,y,z) * log(P(x|y,z))) # 两个条件
- H(X|Y,Z) <= H(X|Y) <= H(X) 说明X的不确定性在下降
互信息: 两个随机时间"相关性"的量化度量
- I(X;Y) = \SUM (P(x,y) * log(P(x,y) / (P(x) * P(y)))) = H(X) - H(X|Y)
- 所以如果事件X,Y是相互独立的话, 那么I(X;Y) = 0
相对熵(Relative Entropy): 也是用来衡量相关性, 但和变量的互信息不同, 它用来衡量两个取值为正数的函数的相似性
- KL(f(x) || g(x)) = \SUM (f(x) * log(f(x) / g(x)))
- Kullback Leibler Divergence.
- 两个完全相同函数, 相对熵 = 0
- 相对熵越大, 两个函数差异越大. 反之, 相对熵越小, 两个函数差异越小.
- 对于概率分布或者概率密度函数, 如果取值均大于0, 相对熵可以度量两个随机分布的差异性.
- 因为KL(f(x) || g(x)) != KL(g(x) || f(x)), 为了两边计算JS(f(x) || g(x)) = 1/2 * KL(f * g) + 1/2 * KL(g * f)

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

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

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

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

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

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

TF(Term Frequency)(D, w) = count(w) / # of words in D.
IDF(Inverse Document Frequency)(w) = log(Dw / D). w在Dw个文档出现过
然后以TF * IDF作为关键词权重来处理分类聚类问题等

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

假设有N个词, M篇文章, 我们可以得到M*N矩阵, 其中A(i,j)表示在第i篇文章中第j个词的权重
经过SVD可以分为三个矩阵, X * B * Y = A. 大小分别是: X是[M, k], B是[k,k], Y是[k, N]. k可以选择
文章被分为k个topic, 每篇文章和这些topcis之间相关性由X矩阵表示
词被分为k个词类, 每个词和这些词类之间相关性由Y矩阵表示
topci和词类之间的相关性由矩阵B表示, B(i,j)表示topic#i和词类#j之间的关系.

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大脑和人工神经网络

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

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

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

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

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

理论上讲，人工神经网络可以在多维空间“画出”各种形状的模式分类边界，因此它有很好的通用性。
虽然在过去的20多年里，各种机器学习的算法不断涌现，而且不断在改进，但是人工神经网络的算法非常稳定，几乎没有怎么变过。
并非所有的机器学习算法（比如贝叶斯网络）都容易并行化，人工神经网络的训练算法相对简单，容易并行实现。

Appendix. 计算复杂度

如果一个问题存在一个多项式复杂度的算法, 这个问题称为P问题(Polynomial), 这类问题被认为是计算机可以"有效"解决的.
如果一个算法计算量比N的多项式函数还高, 这时我们称它为非多项式问题(Non-polynomial).
但是很多问题不是非黑即白, 要么有多项式复杂度的算法, 要么没有. 有一些问题虽然迄今为止还没有找到多项式复杂度的解, 但是不等于以后找不到这样的解.
在非多项式问题中, 如果我们能够在多项式复杂度的时间证实一个答案正确与否, 无论目前这个问题是否能够找到多项式复杂度的算法, 那么称它为NP问题(Nondeterministic Polynomial).
NP问题中有一类特殊问题类称为NPC(NP-Complete). 所有NP问题都可以在多项式时间归约到NPC问题. 无疑NPC问题是NP问题中最难的问题, 因为如果任何一个NPC问题找到了多项式算法, 那么所有的NP问题都可以用这个算法解决了, 即NP=P.
对于计算复杂度至少是NPC甚至更大的问题, 我们称它NP-Hard问题.

Appendix. 第二版后记

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