我们上次谈到用最大熵模型可以将各种信息综合在一起,我们留下一个问题没有回答,就是如何构造最大熵模型。我们已经所有的最大熵模型都是指数函数的形式,现在只需要确定指数函数的参数就可以了。这个过程称为模型的训练。
最原始的最大熵模型的训练方法是一种称为通用迭代算法 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 工作站,仍然计算了三个月,由此可见最大熵模型的复杂的一面。最大熵模型快速算法的实现很复杂,到今天为止,世界上能有效实现这些算法的人也不到一百人。有兴趣实现一个最大熵模型的读者可以阅读我的论文。http://www.cs.jhu.edu/~junwu/publications/ch3.pdf
最大熵模型,可以说是集简与繁于一体,形式简单,实现复杂。值得一提的是,在 Google 的很多产品中,比如机器翻译,都直接或间接地用到了最大熵模型。
讲到这里,读者也许会问,当年最早改进最大熵模型算法的达拉皮垂兄弟这些年难道没有做任何事吗?他们在九十年代初贾里尼克离开 IBM 后,也退出了学术界,而到在金融界大显身手。他们两人和很多 IBM 语音识别的同事一同到了一家当时还不大,但现在是世界上最成功对冲基金(hedge fund)公司 -- 文艺复兴技术公司(Renaissance
Technologies)。我们知道,决定股票涨落的因素可能有几十甚至上百种,而最大熵方法恰恰能找到一个同时满足成千上万种不同条件的模型。达拉皮垂兄弟等科学家在那里,用于最大熵模型和其他一些先进的数学工具对股票预测,获得了巨大的成功。从该基金 1988 年创立至今,它的净回报率高达平均每年 34%。也就是说,如果 1988 年你在该基金投入一块钱,今天你能得到 200 块钱。这个业绩,远远超过股神巴菲特的旗舰公司伯克夏哈撒韦(Berkshire
Hathaway)。同期,伯克夏哈撒韦的总回报是 16 倍。
值得一提的是,信息处理的很多数学手段,包括隐含马尔可夫模型、子波变换、贝叶斯网络等等,在华尔街多有直接的应用,由此可见,数学模型的作用。
分享到:
相关推荐
数据分析与模型讲义-第三章最大熵模型.pdf
最大熵模型(maximum entropy model, MaxEnt)也是很典型的分类算法了,它和逻辑回归类似,都是属于对数线性分类模型。在损失函数优化的过程中,使用了和支持向量机类似的凸优化...本文就对最大熵模型的原理做一个小结。
最大熵模型(Maximum Entropy Model,以下简称MaxEnt),MaxEnt 是概率模型学习中一个准则,其思想为:在学习概率模型时,所有可能的模型中熵最大的模型是最好的模型;若概率模型需要满足一些约束,则最大熵原理就是...
最大熵模型及其应用 最大熵模型及其应用 最大熵模型及其应用 代码+说明文档
最大熵模型(Maximum Entropy Models, MEMs)是基于最大熵理论的统计模型, 广泛应用于模式识别和统计评估中。最大熵原理有一个很长的历史,其中最大熵理论方面的 先驱E.T.Jaynes 在1990 年给出了最大熵原理的基本...
最大熵模型代码
实现了最大熵模型!可以直接被调用。从而进行文本分类
挺好的,基于最大熵模型的分词技术研究基于最大熵模型的分词技术研究
揭开机器学习的面纱:最大熵模型100行代码实现[Python版] - 纯净的天空.pdf
介绍matlab中最大熵模型及解法,并进行详细介绍和学习!
最大熵模型与EM算法
翻译的关于最大熵模型的文章,并加入自己的相关推导。
最大熵模型简介【例子+推导+GIS求解】.pdf 最大熵模型
在分析酒店评论文本倾向性过程中,针对某些评价词语所产生的歧义性问题,提出一种基于最大熵的评价搭配识别的方法。该方法通过构建极性词表,挖掘出评价词语类别作为语义特征,将其与词、词性、距离、否定词特征结合...
Steven J. Phillips 基于最大熵理论在Java环境下创建的模型,主要用于物种生态位的模拟,国内多用于物种分布模型的研究。
针对传统的文本分类算法存在着各特征词对分类的结果影响相同、分类准确率较低、造成算法时间复杂度增加的问题,提出了一种改进的最大熵C-均值聚类文本分类方法。该方法充分结合了C-均值聚类和最大熵值算法的优点,以...
最大熵模型工具包 c++代码 还有那个什么phyon
最大熵模型 分词方法 ,这个是我自己总结的最大熵模型。如果换成条件概率,就是随机场了