數(shù)學(xué)之美 系列十六 （下）－ 不要把所有的雞蛋放在一個(gè)籃子里　最大熵模型

我們上次談到用最大熵模型可以將各種信息綜合在一起。我們留下一個(gè)問(wèn)題沒(méi)有回答，就是如何構(gòu)造最大熵模型。我們已經(jīng)所有的最大熵模型都是指數(shù)函數(shù)的形式，現(xiàn)在只需要確定指數(shù)函數(shù)的參數(shù)就可以了，這個(gè)過(guò)程稱為模型的訓(xùn)練。

最原始的最大熵模型的訓(xùn)練方法是一種稱為通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不復(fù)雜，大致可以概括為以下幾個(gè)步驟：
1. 假定第零次迭代的初始模型為等概率的均勻分布。
2. 用第 N 次迭代的模型來(lái)估算每種信息特征在訓(xùn)練數(shù)據(jù)中的分布，如果超過(guò)了實(shí)際的，就把相應(yīng)的模型參數(shù)變小；否則，將它們便大。
3. 重復(fù)步驟 2 直到收斂。

GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是，這兩人沒(méi)有能對(duì)這種算法的物理含義進(jìn)行很好地解釋。后來(lái)是由數(shù)學(xué)家希薩（Csiszar)解釋清楚的，因此，人們?cè)谡劦竭@個(gè)算法時(shí)，總是同時(shí)引用 Darroch 和Ratcliff 以及希薩的兩篇論文。GIS 算法每次迭代的時(shí)間都很長(zhǎng)，需要迭代很多次才能收斂，而且不太穩(wěn)定，即使在 64 位計(jì)算機(jī)上都會(huì)出現(xiàn)溢出。因此，在實(shí)際應(yīng)用中很少有人真正使用 GIS。大家只是通過(guò)它來(lái)了解最大熵模型的算法。

八十年代，很有天才的孿生兄弟的達(dá)拉皮垂(Della Pietra)在 IBM 對(duì) GIS 算法進(jìn)行了兩方面的改進(jìn)，提出了改進(jìn)迭代算法 IIS（improved iterative scaling）。這使得最大熵模型的訓(xùn)練時(shí)間縮短了一到兩個(gè)數(shù)量級(jí)。這樣最大熵模型才有可能變得實(shí)用。即使如此，在當(dāng)時(shí)也只有 IBM 有條件是用最大熵模型。

由于最大熵模型在數(shù)學(xué)上十分完美，對(duì)科學(xué)家們有很大的誘惑力，因此不少研究者試圖把自己的問(wèn)題用一個(gè)類似最大熵的近似模型去套。誰(shuí)知這一近似，最大熵模型就變得不完美了，結(jié)果可想而知，比打補(bǔ)丁的湊合的方法也好不了多少。于是，不少熱心人又放棄了這種方法。第一個(gè)在實(shí)際信息處理應(yīng)用中驗(yàn)證了最大熵模型的優(yōu)勢(shì)的，是賓夕法尼亞大學(xué)馬庫(kù)斯的另一個(gè)高徒原 IBM 現(xiàn)微軟的研究員拉納帕提(Adwait Ratnaparkhi)。拉納帕提的聰明之處在于他沒(méi)有對(duì)最大熵模型進(jìn)行近似，而是找到了幾個(gè)最適合用最大熵模型、而計(jì)算量相對(duì)不太大的自然語(yǔ)言處理問(wèn)題，比如詞性標(biāo)注和句法分析。拉納帕提成功地將上下文信息、詞性（名詞、動(dòng)詞和形容詞等）、句子成分（主謂賓）通過(guò)最大熵模型結(jié)合起來(lái)，做出了當(dāng)時(shí)世界上最好的詞性標(biāo)識(shí)系統(tǒng)和句法分析器。拉納帕提的論文發(fā)表后讓人們耳目一新。拉納帕提的詞性標(biāo)注系統(tǒng)，至今仍然是使用單一方法最好的系統(tǒng)?？茖W(xué)家們從拉納帕提的成就中，又看到了用最大熵模型解決復(fù)雜的文字信息處理的希望。

但是，最大熵模型的計(jì)算量仍然是個(gè)攔路虎。我在學(xué)校時(shí)花了很長(zhǎng)時(shí)間考慮如何簡(jiǎn)化最大熵模型的計(jì)算量。終于有一天，我對(duì)我的導(dǎo)師說(shuō)，我發(fā)現(xiàn)一種數(shù)學(xué)變換，可以將大部分最大熵模型的訓(xùn)練時(shí)間在 IIS 的基礎(chǔ)上減少兩個(gè)數(shù)量級(jí)。我在黑板上推導(dǎo)了一個(gè)多小時(shí)，他沒(méi)有找出我的推導(dǎo)中的任何破綻，接著他又回去想了兩天，然后告訴我我的算法是對(duì)的。從此，我們就建造了一些很大的最大熵模型。這些模型比修修補(bǔ)補(bǔ)的湊合的方法好不少。即使在我找到了快速訓(xùn)練算法以后，為了訓(xùn)練一個(gè)包含上下文信息，主題信息和語(yǔ)法信息的文法模型(language model)，我并行使用了 20 臺(tái)當(dāng)時(shí)最快的 SUN 工作站，仍然計(jì)算了三個(gè)月。由此可見(jiàn)最大熵模型的復(fù)雜的一面。最大熵模型快速算法的實(shí)現(xiàn)很復(fù)雜，到今天為止，世界上能有效實(shí)現(xiàn)這些算法的人也不到一百人。有興趣實(shí)現(xiàn)一個(gè)最大熵模型的讀者可以閱讀我的論文。

最大熵模型，可以說(shuō)是集簡(jiǎn)與繁于一體，形式簡(jiǎn)單，實(shí)現(xiàn)復(fù)雜。值得一提的是，在Google的很多產(chǎn)品中，比如機(jī)器翻譯，都直接或間接地用到了最大熵模型。

講到這里，讀者也許會(huì)問(wèn)，當(dāng)年最早改進(jìn)最大熵模型算法的達(dá)拉皮垂兄弟這些年難道沒(méi)有做任何事嗎？他們?cè)诰攀甏踬Z里尼克離開(kāi) IBM 后，也退出了學(xué)術(shù)界，而到在金融界大顯身手。他們兩人和很多 IBM 語(yǔ)音識(shí)別的同事一同到了一家當(dāng)時(shí)還不大，但現(xiàn)在是世界上最成功對(duì)沖基金(hedge fund)公司----文藝復(fù)興技術(shù)公司 (Renaissance Technologies)。我們知道，決定股票漲落的因素可能有幾十甚至上百種，而最大熵方法恰恰能找到一個(gè)同時(shí)滿足成千上萬(wàn)種不同條件的模型。達(dá)拉皮垂兄弟等科學(xué)家在那里，用于最大熵模型和其他一些先進(jìn)的數(shù)學(xué)工具對(duì)股票預(yù)測(cè)，獲得了巨大的成功。從該基金 1988 年創(chuàng)立至今，它的凈回報(bào)率高達(dá)平均每年 34%。也就是說(shuō)，如果 1988 年你在該基金投入一塊錢，今天你能得到 200 塊錢。這個(gè)業(yè)績(jī)，遠(yuǎn)遠(yuǎn)超過(guò)股神巴菲特的旗艦公司伯克夏哈撒韋（Berkshire Hathaway)。同期，伯克夏哈撒韋的總回報(bào)是 16 倍。

值得一提的是，信息處理的很多數(shù)學(xué)手段，包括隱含馬爾可夫模型、子波變換、貝葉斯網(wǎng)絡(luò)等等，在華爾街多有直接的應(yīng)用。由此可見(jiàn)，數(shù)學(xué)模型的作用。

轉(zhuǎn)載于:https://www.cnblogs.com/tuyile006/archive/2009/09/11/1564809.html

總結(jié)

以上是生活随笔為你收集整理的数学之美 系列十六 （下）－ 不要把所有的鸡蛋放在一个篮子里　最大熵模型...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。