数学应用-不要把所有的鸡蛋放在一个篮子里–最大熵模型(下)

发表者: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 Ratnaparkhi)。拉纳帕提的聪明之处在于他没有对最大熵 模型进行近似,而是找到了几个最适合用最大熵模型、而计算量相对不太大的自 然语言处理问 题,比如词性标注和句法分析。拉纳帕提成功地将上下文信息、 词性(名词、动词和形容词等)、句子成分(主谓宾)通过最大熵模型结合起来, 做出了当时世界上 最好的词性标识系统和句法分析器。拉纳帕提的论文发表后 让人们耳目一新。拉纳帕提的词性标注系统,至今仍然是使用单一方法最好的系 统。科学家们从拉纳帕提 的成就中,又看到了用最大熵模型解决复杂的文字信 息处理的希望。

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

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

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

值得一提的是,信息处理的很多手段,包括隐含马尔可夫模型、子波变换、 贝叶斯网络等等,在华尔街多有直接的应用。由此可见,数学模型的作用。

声明: 除非转自他站(如有侵权,请联系处理)外,本文采用 BY-NC-SA 协议进行授权 | 智乐兔
转载请注明:转自《数学应用-不要把所有的鸡蛋放在一个篮子里–最大熵模型(下)
本文地址:https://www.zhiletu.com/archives-2810.html
关注公众号:智乐兔

赞赏

wechat pay微信赞赏alipay pay支付宝赞赏

上一篇
下一篇

相关文章

在线留言

你必须 登录后 才能留言!

在线客服
在线客服 X

售前: 点击这里给我发消息
售后: 点击这里给我发消息

智乐兔官微