将技术分析进行到底
提供专业的程序化交易解决方案

《数学之美》第20章:不要把鸡蛋放到一个篮子里——谈谈最大熵模型

本文转自网络。来源:吴军博士所著《数学之美》一书的第20章。感兴趣的朋友可购买正版图书进行更深入研究。

亚马逊购书链接:《数学之美》


吴军著

我们在投资时常常讲不要把所有的鸡蛋放在一个篮子里,这样可以降低风险。在信息处理中,这个原理同样适用。在数学上,这个原理称为最大熵原理(The Maximum Entropy Principle)。这是一个非常有意思的题目,但也比较深奥,因此只能大致介绍它的原理。

 

在网络搜索排名中用到的信息有上百种,腾讯的工程师经常问我如何能把它们结合在一起用好。更普遍地讲,在信息处理中,我们常常知道各种各样的但是又不完全确定的信息,我们需要用一个统一的模型将这些信息综合起来。如何综合得好,是一门很大的学问。

 

让我们看一个拼音转汉字的简单的例子。假如输入的拼音是”Wang-Xiao-Bo”,利用语言模型,根据有限的上下文(比如前两个词),能给出两个最常见的名字“王小波”和“王晓波”。至于要唯一确定是哪个名字就难了,即使利用较长的上下文也做不到。当然,我们知道如果通篇文章是介绍文学的,作家王小波的可能性就较大;而在讨论两岸关系时,台湾学者王晓波的可能性会较大。在上面的例子中,只需要综合两类不同的信息,即主题信息和上下文信息。虽然有不少凑合的办法,比如:分成成千上万种的不同的主题单独处理,或者对每种信息的作用加权平均等等,但都不能准确而圆满地解决问题,这就好比以前谈到的行星运动模型中小圆套大圆打补丁的方法。在很多应用中,需要综合几十甚至上百种不同的信息,这种小圆套大圆的方法显然行不通。

 

1 最大熵原理和最大熵模型

 

数学上最漂亮的办法是最大熵(maximum entropy)模型,它相当于行星运动的椭圆模型。“最大熵”这个名词听起来很深奥,但是它的原理很简单,我们每天都在用。说白了,就是要保留全部的不确定性,将风险降到最小。让我们来看一个实际例子。

 

有一次,我去AT&T实验室作关于最大熵模型的报告,随身带了一个骰子。我问听众“每个面朝上的概率分别是多少”,所有人都说是等概率,即各点的概率均为1/6。这种猜测当然是对的。我问听众们为什么,得到的回答是一致的:对这个“一无所知”的骰子,假定它每一个面朝上概率均等是最安全的做法。(你不应该主观假设它像韦小宝的骰子一样灌了铅。)从投资的角度看,就是风险最小的做法。从信息论的角度讲,就是保留了最大的不确定性,也就是说让熵达到最大。接着,我又告诉听众,我的这个骰子被我特殊处理过,已知四点朝上的概率是三分之一,在这种情况下,每个面朝上的概率是多少?这次,大部分人认为除去四点的概率是 1/3,其余的均是 2/15,也就是说已知的条件(四点概率为 1/3)必须满足,而对其余各点的概率因为仍然无从知道,因此只好认为它们均等。注意,在猜测这两种不同情况下的概率分布时,大家都没有添加任何主观的假设,诸如四点的反面一定是三点等等。(事实上,有的骰子四点反面不是三点而是一点。)这种基于直觉的猜测之所以准确,是因为它恰好符合了最大熵原理。

 

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

 

回到刚才谈到的拼音转汉字的例子,我们已知两种信息,第一,根据语言模型,Wang-Xiao-Bo 可以被转换成王晓波和王小波;第二,根据主题,王小波是作家,《黄金时代》的作者等等,而王晓波是台湾研究两岸关系的学者。因此,就可以建立一个最大熵模型,同时满足这两种信息。现在的问题是,这样一个模型是否存在。匈牙利著名数学家、信息论最高奖香农奖得主希萨(I. Csiszar)证明,对任何一组不自相矛盾的信息,这个最大熵模型不仅存在,而且是唯一的。此外,它们都有同一个非常简单的形式 —— 指数函数。下面公式是根据上下文(前两个词)和主题预测下一个词的最大熵模型,其中 w3 是要预测的词(王晓波或者王小波),w1 和 w2 是它的前两个字(比如说它们分别是“出版”和“小说家”),也就是其上下文的一个大致估计,s表示主题。

6002.1

其中Z是归一化因子,保证概率加起来等于1。

 

在上面的公式中,有几个参数 lambda 和 Z,他们需要通过观测数据训练出来。我们将在延伸阅读中介绍如何训练最大熵模型的诸多参数。

 

最大熵模型在形式上是最漂亮、最完美的统计模型,在自然语言处理和金融方面有很多有趣的应用。早期,由于最大熵模型计算量大,试图使用这个模型的科学家一般用一些类似最大熵的近似模型。谁知这一近似,最大熵模型就从完美变得不完美了。结果可想而知,比打补丁的凑合的方法也好不了多少。于是,不少原来热衷于此的学者又放弃了这种方法。第一个在实际信息处理应用中验证了最大熵模型的优势的是宾夕法尼亚大学马库斯的高徒拉纳帕提(Adwait Ratnaparkhi),原IBM、现任微软的研究员。拉纳帕提的聪明之处在于他没有对最大熵模型进行近似,而是找到了几个最适合用最大熵模型而计算量相对不太大的自然语言处理问题,比如词性标注和语法分析。拉纳帕提成功地将上下文信息、词性、名词、动词和形容词等句子成分、主谓宾,通过最大熵模型结合起来,做出了当时世界上最好的词性标识系统和语法分析器。拉纳帕提的论文让人耳目一新。拉纳帕提的词性标注系统,至今仍是使用单一方法最好的系统。从拉纳帕提的成交中,科学家们又看到了用最大熵模型解决复杂的文字信息处理问题的希望。

 

在2000年前后,由于计算机速度的提升以及训练算法的改进,很多复杂的问题都可以采用最大熵模型了,包括句法分析、语言模型和机器翻译。最大熵模型和一些简单组合特征的模型相比,效果可以提升几个百分点。对于那些对产品质量不是很看重的人和公司来讲,这几个百分点或许不足以给使用者带来明显的感受,但是如果投资的收益能增长哪怕百分之一,获得的利润也是数以亿计的。因此,华尔街向来最喜欢使用新技术来提高他们交易的收益。而证券(股票、债券等)的交易需要考虑非常多的复杂因素,因此,很多对冲积极开始使用最大熵模型,并且取得了很好的效果。

 

 2 最大熵模型的训练

 

最大熵模型在形式上非常简单,但是在实现上却非常复杂,计算量非常大。假定我们搜索的排序需要考虑20中特征,{x1,x2, … ,x20},需要排序的网页是d,那么即使这些特征互相独立,对应的最大熵模型也是“很长”的

6002.2

其中归一化因子

6002.3

这个模型里有很多参数 lambda 需要通过模型的训练获得。

 

最原始的最大熵模型的训练方法是一种称为通用迭代算法GIS(Generalized Iterative Scaling)的迭代算法。GIS的原理并不复杂,大致可以概括为以下几个步骤:

  1. 假定第零次迭代的初始模型为等概率的均匀分布。
  2. 用第 N 次迭代的模型来估算每种信息特征在训练数据中的分布,如果超过了实际的,就把相应的模型参数变小;否则,将它们变大。
  3. 重复步骤 2 直到收敛。

 

GIS最早是由达诺奇(J. N. Darroch)和拉特克利夫(D. Ratcliff)在上世纪70年代提出的,它是一个典型的期望值最大化算法(Expectation Maximization,简称EM)。但是,这两人没能对这种算法的物理含义做出很好的解释。后来是由数学家西萨解释清楚的。因此人们在谈到这个算法时,总是同时引用达诺奇和拉特克利夫以及西萨的两篇论文。GIS算法每次迭代的时间都很长,需要迭代很多次才能收敛,而且不太稳定,即使在64位计算机上都会出现溢出。因此,在实际应用中很少有人真正使用GIS。大家只是通过它来了解最大熵模型的算法。

 

上世纪80年代,天赋异禀的达拉皮垂孪生兄弟(Della Pietra)在IBM对GIS算法做了两方面改进,提出了改进迭代算法IIS(Improved Iterative Scaling)。这使得最大熵模型的训练时间缩短到一到两个数量级。这样最大熵模型才有可能变得实用。即便如此,在当时也只有IBM有条件实用最大熵模型。

 

但是,最大熵模型的计算量仍是个拦路虎。我在学校时花了很长时间考虑如何简化最大熵模型的计算量。有很长一段时间里,我的研究方式就
和书呆子陈景润一样,每天一支笔,一沓纸,不停的推导。终于有一天,我对自己的导师说,我发现一种数学变换,可以将大部分最大熵模型的训练时间在IIS的基础上减少两个数量级。我在黑板上推导了一个多小时,他没有从我的推导中找出任何破绽。接着他又回去想了两天,然后确认我的算法是对的。从此,我们就构造了一些很大的最大熵模型。这些模型比修修补补的凑合的方法好不少。即使在我找到了快速训练算法以后,为了训练一个包含上下文信息、主题信息和语法信息的文法模型(Language Model),我并行使用了20台当时最快的SUN工作站,仍然计算了三个月。因此可见最大熵模型复杂的一面。最大熵模型快速算法的实现很复杂。到今天为止,世界上能有效实现这些算法的也不到一百人。有兴趣实现一个最大熵模型的读者可以阅读我的论文。

 

最大熵模型,可以说是集简繁于一体:形式简单,实现复杂。值得一提的是,在Google的很多产品,比如机器翻译中,都直接或间接地用到了最大熵模型。

 

讲到这里,读者也许会问,当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何事吗?他们在上世纪90年代初贾里尼克离开IBM后,也退出了学术界,而到金融界大显身手。他们两人和很多IBM做语音识别的同事一同到了一家当时还不大,但现在是世界上最成功的对冲基金(Hedge Fund)公司 —— 文艺复兴技术公司(Renaissance Technologies)。我们知道,决定股票涨落的因素可能有几十甚至上百种,而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。在那里,达拉皮垂兄弟等科学家用最大熵模型和其他一些先进的数学工具对股票进行预测,获得了巨大的成功。从该基金1988年创立至今,它的净回报率高达平均每年34%。也就是说,如果1988年你在该基金投入一块钱,20年后的2008年你能得到200多块钱。这个业绩,远远超过股神巴菲特的旗舰公司伯克希尔哈撒韦(Berkshire Hathaway)。同期,伯克希尔哈撒韦的总回报是16倍。而在金融危机的2008年,全球股市暴跌马文义复兴技术公司的回报却高达80%,可见数学模型的厉害。

 

 3 小结

 

最大熵模型可以将各种信息整合到一个统一的模型中。它有很多良好的特性:从形式上看,它非常简单,非常优美;从效果上看,它是唯一一种既可以满足各个信息源的限制条件,同时又能保证平滑(Smooth)性的模型。由于最大熵模型具有这些良好的特性,它的应用范围因而十分广泛。但是,最大熵模型计算量巨大,在工程上实现方法的好坏决定了模型的实用与否。

 

参考文献略,请阅读原著。

 

 

 

未经允许不得转载:文华程序化 » 《数学之美》第20章:不要把鸡蛋放到一个篮子里——谈谈最大熵模型
分享到: (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

横冲直撞 一直到最远方