Saturday, 14. April 2007, 09:02:06
数学
2007年4月13日 下午 07:03:00
发表者：Google 研究员，吴军
我们在前面的系列中介绍和提到了一些年轻有为的科学家，迈克尔·柯林斯，艾里克·布莱尔，大卫·雅让斯基，拉纳帕提等等，他们都出自宾夕法尼亚计算机系米奇·马库斯(Mitch Marcus)名下。就像许多武侠小说中描写的，弟子都成了各派的掌门，师傅一定了不得。的确，马库斯虽然作为第一作者发表的论文并不多，但是从很多角度上讲，他可以说是自然语言处理领域的教父。
马库斯教授长期当任宾夕法尼亚大学计算机系主任，直到他在几年前从 AT&T 找到皮耶尔替代他为止。作为一个管理者，马库斯显示出在自然处理和计算机科学方面的卓识的远见。在指导博士生时，马库斯发现语料库在自然语言处理中的重要性。马库斯呕心沥血，花了十几年工夫建立了一系列标准的语料库，提供给全世界的学者使用。这套被称为 LDC 的语料库，是当今全世界自然语言处理的所有学者都使用的工具。我们在以前的系列中讲到，当今的自然语言处理几乎都是使用给予统计的方法。要做统计，就需要大量有代表性的数据。利用这些数据开发一个自然语言处理系统的过程，可以统称为训练。比如，我们要训练一个汉语分词系统，我们需要一些已经分好词的中文句子。当然这些句子需要有代表性。如果想知道一个分词系统的准确性，我们也需要一些人工分好词的句子进行测试。这些人工处理好的文字数据库，成为语料库(corpus)。如果每个研究室都人工建立几个语料库，不仅浪费时间精力，而且发表文章时，数据没有可比性。因此，马库斯想到了建立一系列标准的语料库为全世界的学者用。他利用自己的影响力让美国自然科学基金会和 DARPA 出钱立项，联络的多所大学和研究机构，建立的数百个标准的语料库。其中最著名的是 PennTree
Bank 的语料库。PennTree Bank 覆盖多种语言（包括中文）。每一种语言，它有几十万到几百万字的有代表性的句子，每个句子都有的词性标注，语法分析树等等。LDC 语料库如今已成为全世界自然语言处理科学家共用的数据库。如今，在自然语言处理方面发表论文，几乎都要提供基于 LDC 语料库的测试结果。
马库斯给予他的博士生研究自己感兴趣的课题的自由，这是他之所以桃李满天下的原因。马库斯对几乎所有的自然语言处理领域有独到的见解。和许多教授让博士生去做他拿到基金的项目，马库斯让博士生提出自己有兴趣的课题，或者用他已有的经费支持学生，或者为他们的项目区申请经费。马库斯高屋建瓴，能够很快的判断一个研究方向是否正确，省去了博士生很多 try-and-error 的时间。因此他的学生有些很快地拿到的博士学位。
作为系主任，马库斯在专业设置方面显示出卓识的远见。我有幸和他在同一个校务顾问委员会任职，一起讨论计算机系的研究方向。马库斯在几年前互联网很热门、很多大学开始互联网研究时，看到 bioinformatics (生物信息学）的重要性，在宾夕法利亚大学设置这个专业，并且在其他大学还没有意识到时，开始招聘这方面的教授。马库斯还建议一些相关领域的教授，包括后来的系主任皮耶尔把一部分精力转到生物信息学方面。马库斯同时向他担任顾问的其他一些大学提出同样的建议。等到网络泡沫破裂以后，很多大学的计算机系开始向生物信息学转向，但是发现已经很难找到这些方面好的教授了。我觉得，当今中国的大学，最需要的就是马库斯这样卓有远见的管理者。
过几天我又要和马库斯一起开顾问委员会的会议了，不知道这次他对计算机科学的发展有什么见解。
Monday, 19. February 2007, 14:31:34
数学, 学习
1/28/2007 09:53:00 下午
发表者：Google 研究员，吴军
我们在前面的系列中多次提到
马尔可夫链 (Markov
Chain)，它描述了一种状态序列，其每个状态值取决于前面有限个状态。这种模型，对很多实际问题来讲是一种很粗略的简化。在现实生活中，很多事物相互的关系并不能用一条链来串起来。它们之间的关系可能是交叉的、错综复杂的。比如在下图中可以看到，心血管疾病和它的成因之间的关系是错综复杂的。显然无法用一个链来表示。
我们可以把上述的
有向图看成一个网络，它就是贝叶斯网络。其中每个圆圈表示一个状态。状态之间的连线表示它们的因果关系。比如从心血管疾病出发到吸烟的弧线表示心血管疾病可能和吸烟有关。当然，这些关系可以有一个量化的可信度 (belief)，用一个概率描述。我们可以通过这样一张网络估计出一个人的心血管疾病的可能性。在网络中每个节点概率的计算，可以用贝叶斯公式来进行，贝叶斯网络因此而得名。由于网络的每个弧有一个可信度，贝叶斯网络也被称作信念网络 (belief networks)。
和马尔可夫链类似，贝叶斯网络中的每个状态值取决于前面有限个状态。不同的是，贝叶斯网络比马尔可夫链灵活，它不受马尔可夫链的链状结构的约束，因此可以更准确地描述事件之间的相关性。可以讲，马尔可夫链是贝叶斯网络的特例，而贝叶斯网络是马尔可夫链的推广。
使用贝叶斯网络必须知道各个状态之间相关的概率。得到这些参数的过程叫做训练。和训练马尔可夫模型一样，训练贝叶斯网络要用一些已知的数据。比如在训练上面的网络，需要知道一些心血管疾病和吸烟、家族病史等有关的情况。相比马尔可夫链，贝叶斯网络的训练比较复杂，从理论上讲，它是一个 NP-complete 问题，也就是说，对于现在的计算机是不可计算的。但是，对于某些应用，这个训练过程可以简化，并在计算上实现。
值得一提的是 IBM Watson 研究所的茨威格博士 (Geoffrey Zweig) 和西雅图华盛顿大学的比尔默 (Jeff Bilmes) 教授完成了一个通用的贝叶斯网络的工具包，提供给对贝叶斯网络有兴趣的研究者。
贝叶斯网络在图像处理、文字处理、支持决策等方面有很多应用。在文字处理方面，语义相近的词之间的关系可以用一个贝叶斯网络来描述。我们利用贝叶斯网络，可以找出近义词和相关的词，在 Google 搜索和 Google 广告中都有直接的应用。
Thursday, 4. January 2007, 11:27:45
数学
完备性的讨论在初等数学分析中已经初现端倪，并且在泛函分析中占了更大的分量，但是很多上课的老师从不谈论完备到底是什么东西，为什么要讨论它，这里我就给出一个简单的解释， 希望对在这一被人为复杂化的数学领域学习的人有所帮助。
在最早开始学数学分析时就会碰到连续统（这个词不知道是哪个猪翻译过来的，完全看不出是 什么意思）的问题。在实数轴上我们将其分为自然数，有理数，无理数等。注意这种划分不是 随意的，或者出于某个变态在学术上的需要，而是根据人类对数的认知过程来划分的。而实际上完备性正是从最初在讨论这种实数的过程中产生的。完备性就是指所使用的数域的完整性。举例来说，当人们最早是会数1，2，3时很多问题是无法解决的，因为当他们碰到存在某个方式（f(x)）将1映射到1和2之间就变得无能为力了。这个时候自然数这个数域对他们来说是不完备的，这个数域太小了，数和数之间缺了很多其它的数。随着时间的流逝，人们渐渐认识了在实数上所有的数，这个时候整个实数领域才变得完备了，因为它完美无缺了（如果有缺陷，整个高等的抽象数学都要重新来建立理论），再也找不到什么数是被目前所认识的实数所遗漏的了。不过这时候随着数学的抽象话，这个完备的理论才开始被人们重视。
在实际应用中我们常常不会用到整个实数领域，而可能只是用到其中的一小部分，这是完备性 在解方程特别是积分方程中变得重要了起来。举一个例子：很可能我们要研究的一些问题，它 们只被限制在（0，1]这样一个区间里，而我们正好又要研究在这个区间中(1/n)序列的特性，显然这个序列在这个区间中无法研究，因为我们无法达到当n趋于无穷时的值（这里是0），所 以对于这个研究来说这个数域是不完备的。当然完备性不是针对某个特定的应用来说的，而是 对某个数域（从抽象的角度来说就是空间）来说的，这里只是举个例子来说明。实际上在我们 普通的日常经验或者初等数学的知识上来说，只有整个实数域是完备的，或者实数域上的连续数的闭区间是完备的，如[0,1]。因为在以他们为约束的条件下研究问题是不会遇到达不到的数的。
到了抽象领域，这一概念实际上才体现出了其真正的作用。不过要先清除，抽象的定义，这里不是完备这个词被抽象了，它的定义完全没有变，而只是对我们研究的问题抽象了。比如现在我们可以研究一些不是数的东西，比如电视机，或者录像机。当然先要用数字来表现他们的特征。更重要的在这里我们甚至可以将诸如‘规则’这样抽象的东西来当作数字处理。比如我们可以研究函数f1(x)和f2(x)中f1和f2的关系，而抛开其具体在x上的取值不谈。从抽象的角度来说，我们将f1和f2看作某个以规则为数域的其中的两个数。就像1和2是R中的两个数，如果我们把这个以规则作为数域的空间称作X，那么f1和f2也只是X中的两个数而已。这时讨论完备性就是讨论目前这个空间X是不是完整的，会不会只是一个象有理数在实数中占的地位那样。如果不完备我们应尽力将其完备，以方便对它的研究，就像把Q扩展为R后我们就可以计算无理数了，或者可以真正的计算积分了（当然不完备也可以积分，但是总觉得怪怪的）。
在实际应用中，我们可以不像书上那样去一个一个的证明完备性，但是最好要心里清楚我们取得这个空间是不是完备的。比如将一个有限维空间的连续周期函数拆分为傅立叶级数的表示方法，如果空间不完备，那么有可能就无法用这个空间的基来表示这个傅立叶级数，失去了傅立叶级数这个强大的工具，实际应用就会变得很困难，因为我们很难得知这个函数的性质了。更重要地，在用傅立叶变换上就更要注意这个问题了，对于基来说变得不可数了，要想了解对于不完备的空间这个基群到底有多少是目前空间所达不到的，几乎就变得不可能了，当然可能可以在这上面定义某种类似L测度的概念从而能够了解他们比值的关系（不可达到的基比上整个不可数的基群）。
附注：这里对很多泛函的书的用语给个解释，否则很容易搞迷糊（至少我就是）。有这样一句句子：
“H空间有一个可数的稠密子集。”
这里稠密子集指的不是稠密集的子集，而是指H的子集，这个子集是个稠密集。也就是如果当这个稠密集封闭的化，就是H空间了。赫，汉语的优点不是吗，能把你理直气壮的搞糊涂，而突显出某些专家的高深。
下面是我的想法，可以不看。
其实数学如果只是针对实际应用是一门不难的学问，如果我们对于一些普遍性的数学理论能从一个实际例子来理解，那么就会发现一些普遍的数学概念是那么的简单，它只是看上去复杂罢了（不过证明就是另外一回事了）。对于那些被称为简单的数学记法，从一个不学数学的人的角度出发来看，简直就是那些变态的数学家人为设置的障碍。如果记号真的那么好，还要语言干嘛，大家都用甲骨文算了。世界大概也会变得和平点了。
Tuesday, 2. January 2007, 06:20:42
数学
2007年1月1日 下午 03:10:00
发表者：Google 研究员，吴军
我在大学学习线性代数时，实在想不出它除了告诉我们如何解线性方程外，还能有什么别的用途。关于矩阵的许多概念，比如特征值等等，更是脱离日常生活。后来在数值分析中又学了很多矩阵的近似算法，还是看不到可以应用的地方。当时选这些课，完全是为了混学分的学位。我想，很多同学都多多少少有过类似的经历。直到后来长期做自然语言处理的研究，我才发现数学家们提出那些矩阵的概念和算法，是有实际应用的意义的。
在自然语言处理中，最常见的两类的分类问题分别是，将文本按主题归类（比如将所有介绍亚运会的新闻归到体育类）和将词汇表中的字词按意思归类（比如将各种体育运动的名称个归成一类）。这两种分类问题都可用通过矩阵运算来圆满地、同时解决。为了说明如何用矩阵这个工具类解决这两个问题的，让我们先来来回顾一下我们在余弦定理和新闻分类中介绍的方法。
分类的关键是计算相关性。我们首先对两个文本计算出它们的内容词，或者说实词的向量，然后求这两个向量的夹角。当这两个向量夹角为零时，新闻就相关；当它们垂直或者说正交时，新闻则无关。当然，夹角的余弦等同于向量的内积。从理论上讲，这种算法非常好。但是计算时间特别长。通常，我们要处理的文章的数量都很大，至少在百万篇以上，二次回标有非常长，比如说有五十万个词（包括人名地名产品名称等等）。如果想通过对一百万篇文章两篇两篇地成对比较，来找出所有共同主题的文章，就要比较五千亿对文章。现在的计算机一秒钟最多可以比较一千对文章，完成这一百万篇文章相关性比较就需要十五年时间。注意，要真正完成文章的分类还要反复重复上述计算。
在文本分类中，另一种办法是利用矩阵运算中的奇异值分解（Singular Value Decomposition，简称 SVD)。现在让我们来看看奇异值分解是怎么回事。首先，我们可以用一个大矩阵A来描述这一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章，每一列对应一个词。
在上面的图中，M=1,000,000，N=500,000。第 i 行，第 j 列的元素，是字典中第 j 个词在第 i 篇文章中出现的加权词频（比如，TF/IDF)。读者可能已经注意到了，这个矩阵非常大，有一百万乘以五十万，即五千亿个元素。
奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，如下图所示。比如把上面的例子中的矩阵分解成一个一百万乘以一百的矩阵X，一个一百乘以一百的矩阵B，和一个一百乘以五十万的矩阵Y。这三个矩阵的元素总数加起来也不过1.5亿，仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数量级以上。
三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因此，我们只要对关联矩阵A进行一次奇异值分解，w 我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。
现在剩下的唯一问题，就是如何用计算机进行奇异值分解。这时，线性代数中的许多概念，比如矩阵的特征值等等，以及数值分析的各种算法就统统用上了。在很长时间内，奇异值分解都无法并行处理。（虽然 Google 早就有了MapReduce 等并行计算的工具，但是由于奇异值分解很难拆成不相关子运算，即使在 Google 内部以前也无法利用并行计算的优势来分解矩阵。）最近，Google 中国的张智威博士和几个中国的工程师及实习生已经实现了奇异值分解的并行算法，我认为这是 Google 中国对世界的一个贡献。
Thursday, 7. December 2006, 07:47:45
数学
2006年11月28日 上午 03:18:00
Google 研究员 吴军
自从有了搜索引擎，就有了针对搜索引擎网页排名的作弊(SPAM)。以至于用户发现在搜索引擎中排名靠前的网页不一定就是高质量的，用句俗话说，闪光的不一定是金子。
搜索引擎的作弊，虽然方法很多，目的只有一个，就是采用不正当手段提高自己网页的排名。早期最常见的作弊方法是重复关键词。比如一个卖数码相机的网站，重复地罗列各种数码相机的品牌，如尼康、佳能和柯达等等。为了不让读者看到众多讨厌的关键词，聪明一点的作弊者常用很小的字体和与背景相同的颜色来掩盖这些关键词。其实，这种做法很容易被搜索引擎发现并纠正。
在有了网页排名(page rank)以后，作弊者发现一个网页被引用的连接越多，排名就可能越靠前，于是就有了专门卖链接和买链接的生意。比如，有人自己创建成百上千个网站，这些网站上没有实质的内容，只有到他们的客户网站的连接。这种做法比重复关键词要高明得多，但是还是不太难被发现。因为那些所谓帮别人提高排名的网站，为了维持生意需要大量地卖链接，所以很容易露马脚。（这就如同造假钞票，当某一种假钞票的流通量相当大以后，就容易找到根源了。）再以后，又有了形形色色的作弊方式，我们就不在这里一一赘述了。
几年前，我加入Google做的第一件事就是消除网络作弊。在Google最早发现搜索引擎作弊的是Matt Cutts，他在我加入Google前几个月开始研究这个问题，后来，辛格，马丁和我先后加入进来。我们经过几个月的努力，清除了一半的作弊者。(当然，以后抓作弊的效率就不会有这么高了。）其中一部分网站从此"痛改前非"，但是还是有很多网站换一种作弊方法继续作弊，因此，抓作弊成了一种长期的猫捉老鼠的游戏。虽然至今还没有一个一劳永逸地解决作弊问题的方法，但是，Google基本做到了对于任何已知的作弊方法，在一定时间内发现并清除它，从而总是将作弊的网站的数量控制在一个很小的比例范围。
抓作弊的方法很像信号处理中的去噪音的办法。学过信息论和有信号处理经验的读者可能知道这么一个事实，我们如果在发动机很吵的汽车里用手机打电话，对方可能听不清；但是如果我们知道了汽车发动机的频率，我们可以加上一个和发动机噪音相反的信号，很容易地消除发动机的噪音，这样，收话人可以完全听不到汽车的噪音。事实上，现在一些高端的手机已经有了这种检测和消除噪音的功能。消除噪音的流程可以概括如下：
在图中，原始的信号混入了噪音，在数学上相当于两个信号做卷积。噪音消除的过程是一个解卷积的过程。这在信号处理中并不是什么难题。因为第一，汽车发动机的频率是固定的，第二，这个频率的噪音重复出现，只要采集几秒钟的信号进行处理就能做到。从广义上讲，只要噪音不是完全随机的、并且前后有相关性，就可以检测到并且消除。（事实上，完全随机不相关的高斯白噪音是很难消除的。）
搜索引擎的作弊者所作的事，就如同在手机信号中加入了噪音，使得搜索结果的排名完全乱了。但是，这种人为加入的噪音并不难消除，因为作弊者的方法不可能是随机的（否则就无法提高排名了）。而且，作弊者也不可能是一天换一种方法，即作弊方法是时间相关的。因此，搞搜索引擎排名算法的人，可以在搜集一段时间的作弊信息后，将作弊者抓出来，还原原有的排名。当然这个过程需要时间，就如同采集汽车发动机噪音需要时间一样，在这段时间内，作弊者可能会尝到些甜头。因此，有些人看到自己的网站经过所谓的优化（其实是作弊），排名在短期内靠前了，以为这种所谓的优化是有效的。但是，不久就会发现排名掉下去了很多。这倒不是搜索引擎以前宽容，现在严厉了，而是说明抓作弊需要一定的时间，以前只是还没有检测到这些作弊的网站而已。
还要强调一点，Google抓作弊和恢复网站原有排名的过程完全是自动的(并没有个人的好恶），就如同手机消除噪音是自动的一样。一个网站要想长期排名靠前，就需要把内容做好，同时要和那些作弊网站划清界限。
Monday, 20. November 2006, 07:24:26
数学
2006年11月16日 上午 06:50:00
发表者：Google 研究员，吴军
我们上次谈到用最大熵模型可以将各种信息综合在一起。我们留下一个问题没有回答，就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式，现在只需要确定指数函数的参数就可以了，这个过程称为模型的训练。
最原始的最大熵模型的训练方法是一种称为通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不复杂，大致可以概括为以下几个步骤：
1. 假定第零次迭代的初始模型为等概率的均匀分布。
2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布，如果超过了实际的，就把相应的模型参数变小；否则，将它们便大。
3. 重复步骤 2 直到收敛。
GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是，这两人没有能对这种算法的物理含义进行很好地解释。后来是由数学家希萨（Csiszar)解释清楚的，因此，人们在谈到这个算法时，总是同时引用 Darroch 和Ratcliff 以及希萨的两篇论文。GIS 算法每次迭代的时间都很长，需要迭代很多次才能收敛，而且不太稳定，即使在 64 位计算机上都会出现溢出。因此，在实际应用中很少有人真正使用 GIS。大家只是通过它来了解最大熵模型的算法。
八十年代，很有天才的孪生兄弟的达拉皮垂(Della Pietra)在 IBM 对 GIS 算法进行了两方面的改进，提出了改进迭代算法 IIS（improved iterative scaling）。这使得最大熵模型的训练时间缩短了一到两个数量级。这样最大熵模型才有可能变得实用。即使如此，在当时也只有 IBM 有条件是用最大熵模型。
由于最大熵模型在数学上十分完美，对科学家们有很大的诱惑力，因此不少研究者试图把自己的问题用一个类似最大熵的近似模型去套。谁知这一近似，最大熵模型就变得不完美了，结果可想而知，比打补丁的凑合的方法也好不了多少。于是，不少热心人又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的，是宾夕法尼亚大学马库斯的另一个高徒原 IBM 现微软的研究员拉纳帕提(Adwait Ratnarpakhi)。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似，而是找到了几个最适合用最大熵模型、而计算量相对不太大的自然语言处理问题，比如词性标注和句法分析。拉纳帕提成功地将上下文信息、词性（名词、动词和形容词等）、句子成分（主谓宾）通过最大熵模型结合起来，做出了当时世界上最好的词性标识系统和句法分析器。拉纳帕提的论文发表后让人们耳目一新。拉纳帕提的词性标注系统，至今仍然是使用单一方法最好的系统。科学家们从拉纳帕提的成就中，又看到了用最大熵模型解决复杂的文字信息处理的希望。
但是，最大熵模型的计算量仍然是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型的计算量。终于有一天，我对我的导师说，我发现一种数学变换，可以将大部分最大熵模型的训练时间在 IIS 的基础上减少两个数量级。我在黑板上推导了一个多小时，他没有找出我的推导中的任何破绽，接着他又回去想了两天，然后告诉我我的算法是对的。从此，我们就建造了一些很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以后，为了训练一个包含上下文信息，主题信息和语法信息的文法模型(language model)，我并行使用了 20 台当时最快的 SUN 工作站，仍然计算了三个月。由此可见最大熵模型的复杂的一面。最大熵模型快速算法的实现很复杂，到今天为止，世界上能有效实现这些算法的人也不到一百人。有兴趣实现一个最大熵模型的读者可以阅读我的论文。
最大熵模型，可以说是集简与繁于一体，形式简单，实现复杂。值得一提的是，在Google的很多产品中，比如机器翻译，都直接或间接地用到了最大熵模型。
讲到这里，读者也许会问，当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何事吗？他们在九十年代初贾里尼克离开 IBM 后，也退出了学术界，而到在金融界大显身手。他们两人和很多 IBM 语音识别的同事一同到了一家当时还不大，但现在是世界上最成功对冲基金(hedge fund)公司----文艺复兴技术公司 (Renaissance Technologies)。我们知道，决定股票涨落的因素可能有几十甚至上百种，而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。达拉皮垂兄弟等科学家在那里，用于最大熵模型和其他一些先进的数学工具对股票预测，获得了巨大的成功。从该基金 1988 年创立至今，它的净回报率高达平均每年 34%。也就是说，如果 1988 年你在该基金投入一块钱，今天你能得到 200 块钱。这个业绩，远远超过股神巴菲特的旗舰公司伯克夏哈撒韦（Berkshire Hathaway)。同期，伯克夏哈撒韦的总回报是 16 倍。
值得一提的是，信息处理的很多数学手段，包括隐含马尔可夫模型、子波变换、贝叶斯网络等等，在华尔街多有直接的应用。由此可见，数学模型的作用。
Monday, 9. October 2006, 07:29:09
数学
[我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里，这样可以降低风险。在信息处理中，这个原理同样适用。在数学上，这个原理称为
最大熵原理(the maximum entropy principle)。这是一个非常有意思的题目，但是把它讲清楚要用两个系列的篇幅。]
前段时间，Google 中国研究院的刘骏总监谈到在网络搜索排名中，用到的信息有上百种。更普遍地讲，在自然语言处理中，我们常常知道各种各样的但是又不完全确定的信息，我们需要用一个统一的模型将这些信息综合起来。如何综合得好，是一门很大的学问。
让我们看一个拼音转汉字的简单的例子。假如输入的拼音是"wang-xiao-bo"，利用语言模型，根据有限的上下文(比如前两个词)，我们能给出两个最常见的名字“王小波”和“王晓波”。至于要唯一确定是哪个名字就难了，即使利用较长的上下文也做不到。当然，我们知道如果通篇文章是介绍文学的，作家王小波的可能性就较大；而在讨论两岸关系时，台湾学者王晓波的可能性会较大。在上面的例子中，我们只需要综合两类不同的信息，即主题信息和上下文信息。虽然有不少凑合的办法，比如：分成成千上万种的不同的主题单独处理，或者对每种信息的作用加权平均等等，但都不能准确而圆满地解决问题，这样好比以前我们谈到的行星运动模型中的
小圆套大圆打补丁的方法。在很多应用中，我们需要综合几十甚至上百种不同的信息，这种小圆套大圆的方法显然行不通。
数学上最漂亮的办法是最大熵(maximum entropy)模型，它相当于行星运动的椭圆模型。“最大熵”这个名词听起来很深奥，但是它的原理很简单，我们每天都在用。说白了，就是要保留全部的不确定性，将风险降到最小。让我们来看一个实际例子。
有一次，我去 AT&T 实验室作关于最大熵模型的报告，我带去了一个色子。我问听众“每个面朝上的概率分别是多少”，所有人都说是等概率，即各点的概率均为1/6。这种猜测当然是对的。我问听众们为什么，得到的回答是一致的：对这个“一无所知”的色子，假定它每一个朝上概率均等是最安全的做法。（你不应该主观假设它象韦小宝的色子一样灌了铅。）从投资的角度看，就是风险最小的做法。从信息论的角度讲，就是保留了最大的不确定性，也就是说让熵达到最大。接着，我又告诉听众，我的这个色子被我特殊处理过，已知四点朝上的概率是三分之一，在这种情况下，每个面朝上的概率是多少？这次，大部分人认为除去四点的概率是 1/3，其余的均是 2/15，也就是说已知的条件（四点概率为 1/3）必须满足，而对其余各点的概率因为仍然无从知道，因此只好认为它们均等。注意，在猜测这两种不同情况下的概率分布时，大家都没有添加任何主观的假设，诸如四点的反面一定是三点等等。（事实上，有的色子四点反面不是三点而是一点。）这种基于直觉的猜测之所以准确，是因为它恰好符合了最大熵原理。
最大熵原理指出，当我们需要对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设。（不做主观假设这点很重要。）在这种情况下，概率分布最均匀，预测的风险最小。因为这时概率分布的信息熵最大，所以人们称这种模型叫“最大熵模型”。我们常说，不要把所有的鸡蛋放在一个篮子里，其实就是最大熵原理的一个朴素的说法，因为当我们遇到不确定性时，就要保留各种可能性。
回到我们刚才谈到的拼音转汉字的例子，我们已知两种信息，第一，根据语言模型，wang-xiao-bo 可以被转换成王晓波和王小波；第二，根据主题，王小波是作家，《黄金时代》的作者等等，而王晓波是台湾研究两岸关系的学者。因此，我们就可以建立一个最大熵模型，同时满足这两种信息。现在的问题是，这样一个模型是否存在。匈牙利著名数学家、信息论最高奖香农奖得主希萨（Csiszar）证明，对任何一组不自相矛盾的信息，这个最大熵模型不仅存在，而且是唯一的。而且它们都有同一个非常简单的形式 -- 指数函数。下面公式是根据上下文（前两个词）和主题预测下一个词的最大熵模型，其中 w3 是要预测的词（王晓波或者王小波）w1 和 w2 是它的前两个字（比如说它们分别是“出版”，和“”），也就是其上下文的一个大致估计，subject 表示主题。
我们看到，在上面的公式中，有几个参数 lambda 和 Z ，他们需要通过观测数据训练出来。
最大熵模型在形式上是最漂亮的统计模型，而在实现上是最复杂的模型之一。我们在将下一个系列中介绍如何训练最大熵模型的诸多参数，以及最大熵模型在自然语言处理和金融方面很多有趣的应用。
Thursday, 28. September 2006, 11:31:59
技术, 数学, 学习
Friday, 25. August 2006, 03:15:09
学习, 数学
发表者：吴军，Google 研究员
我在数学之美系列中一直强调的一个好方法就是简单。但是，事实上，自然语言处理中也有一些特例，比如有些学者将一个问题研究到极致，执著追求完善甚至可以说完美的程度。他们的工作对同行有很大的参考价值，因此我们在科研中很需要这样的学者。在自然语言处理方面新一代的顶级人物麦克尔 · 柯林斯 (
Michael Collins) 就是这样的人。
柯林斯：追求完美
柯林斯从师于自然语言处理大师马库斯 (Mitch Marcus)（我们以后还会多次提到马库斯），从宾夕法利亚大学获得博士学位，现任麻省理工学院 (MIT) 副教授（别看他是副教授，他的水平在当今自然语言处理领域是数一数二的），在作博士期间，柯林斯写了一个后来以他名字命名的自然语言文法分析器 (sentence parser)，可以将书面语的每一句话准确地进行文法分析。文法分析是很多自然语言应用的基础。虽然柯林斯的师兄布莱尔 (Eric Brill) 和 Ratnaparkhi 以及师弟 Eisnar 都完成了相当不错的语言文法分析器，但是柯林斯却将它做到了极致，使它在相当长一段时间内成为世界上最好的文法分析器。柯林斯成功的关键在于将文法分析的每一个细节都研究得很仔细。柯林斯用的数学模型也很漂亮，整个工作可以用完美来形容。我曾因为研究的需要，找柯林斯要过他文法分析器的源程序，他很爽快地给了我。我试图将他的程序修改一下来满足我特定应用的要求，但后来发现，他的程序细节太多以至于很难进一步优化。
柯林斯的博士论文堪称是自然语言处理领域的范文。它像一本优秀的小说，把所有事情的来龙去脉介绍的清清楚楚，对于任何有一点计算机和自然语言处理知识的人，都可以轻而易举地读懂他复杂的方法。
柯林斯毕业后，在 AT&T 实验室度过了三年快乐的时光。在那里柯林斯完成了许多世界一流的研究工作诸如隐含马尔科夫模型的区别性训练方法，卷积核在自然语言处理中的应用等等。三年后，AT&T 停止了自然语言处理方面的研究，柯林斯幸运地在 MIT 找到了教职。在 MIT 的短短几年间，柯林斯多次在国际会议上获得最佳论文奖。相比其他同行，这种成就是独一无二的。柯林斯的特点就是把事情做到极致。如果说有人喜欢“繁琐哲学”，柯林斯就是一个。
布莱尔：简单才美
在研究方法上，站在柯林斯对立面的典型是他的师兄艾里克 · 布莱尔 (
Eric Brill) 和雅让斯基，后者我们已经介绍过了，这里就不再重复。与柯林斯从工业界到学术界相反，布莱尔职业路径是从学术界走到工业界。与柯里斯的研究方法相反，布莱尔总是试图寻找简单得不能再简单的方法。布莱尔的成名作是基于变换规则的机器学习方法 (transformation rule based machine learning)。这个方法名称虽然很复杂，其实非常简单。我们以拼音转换字为例来说明它：
第一步，我们把每个拼音对应的汉字中最常见的找出来作为第一遍变换的结果，当然结果有不少错误。比如，“常识”可能被转换成“长识”；
第二步，可以说是“去伪存真”，我们用计算机根据上下文，列举所有的同音字替换的规则，比如，如果 chang 被标识成“长”，但是后面的汉字是“识”，则将“长”改成“常”；
第三步，应该就是“去粗取精”，将所有的规则用到事先标识好的语料中，挑出有用的，删掉无用的。然后重复二三步，直到找不到有用的为止。
布莱尔就靠这么简单的方法，在很多自然语言研究领域，得到了几乎最好的结果。由于他的方法再简单不过了，许许多多的人都跟着学。布莱尔可以算是我在美国的第一个业师，我们俩就用这么简单的方法作词性标注 (part of speech tagging)，也就是把句子中的词标成名词动词，很多年内无人能超越。（最后超越我们的是后来加入 Google 的一名荷兰工程师，用的是同样的方法，但是做得细致很多）布莱尔离开学术界后去了微软研究院。在那里的第一年，他一人一年完成的工作比组里其他所有人许多年做的工作的总和还多。后来，布莱尔又加入了一个新的组，依然是高产科学家。据说，他的工作真正被微软重视要感谢 Google，因为有了 Google，微软才对他从人力物力上给于了巨大的支持，使得布莱尔成为微软搜索研究的领军人物之一。在研究方面，布莱尔有时不一定能马上找到应该怎么做，但是能马上否定掉一种不可能的方案。这和他追求简单的研究方法有关，他能在短时间内大致摸清每种方法的好坏。
由于布莱尔总是找简单有效的方法，而又从不隐瞒自己的方法，所以他总是很容易被包括作者我自己在内的很多人赶上和超过。好在布莱尔很喜欢别人追赶他，因为，当人们在一个研究方向超过他时，他已经调转船头驶向它方了。一次，艾里克对我说，有一件事我永远追不上他，那就是他比我先有了第二个孩子 ：）
在接下来了系列里，我们还会介绍一个繁与简结合的例子。
Showing posts 1 -
10 of
28.
