最大熵模型

我們在投資時常常講不要把所有的雞蛋放在一個籃子里，這樣可以降低風(fēng)險。在信息處理中，這個原理同樣適用。在數(shù)學(xué)上，這個原理稱為最大熵原理(the maximum entropy principle)。

讓我們看一個拼音轉(zhuǎn)漢字的簡單的例子。假如輸入的拼音是"wang-xiao-bo"，利用語言模型，根據(jù)有限的上下文(比如前兩個詞)，我們能給出兩個最常見的名字“王小波”和“王曉波 ”。至于要唯一確定是哪個名字就難了，即使利用較長的上下文也做不到。當(dāng)然，我們知道如果通篇文章是介紹文學(xué)的，作家王小波的可能性就較大；而在討論兩岸關(guān)系時，臺灣學(xué)者王曉波的可能性會較大。在上面的例子中，我們只需要綜合兩類不同的信息，即主題信息和上下文信息。雖然有不少湊合的辦法，比如：分成成千上萬種的不同的主題單獨處理，或者對每種信息的作用加權(quán)平均等等，但都不能準(zhǔn)確而圓滿地解決問題，這樣好比以前我們談到的行星運動模型中的小圓套大圓打補丁的方法。在很多應(yīng)用中，我們需要綜合幾十甚至上百種不同的信息，這種小圓套大圓的方法顯然行不通。

數(shù)學(xué)上最漂亮的辦法是最大熵(maximum entropy)模型，它相當(dāng)于行星運動的橢圓模型?！白畲箪亍边@個名詞聽起來很深奧，但是它的原理很簡單，我們每天都在用。說白了，就是要保留全部的不確定性，將風(fēng)險降到最小。

回到我們剛才談到的拼音轉(zhuǎn)漢字的例子，我們已知兩種信息，第一，根據(jù)語言模型，wangxiao-bo可以被轉(zhuǎn)換成王曉波和王小波；第二，根據(jù)主題，王小波是作家，《黃金時代》的作者等等，而王曉波是臺灣研究兩岸關(guān)系的學(xué)者。因此，我們就可以建立一個最大熵模型，同時滿足這兩種信息?，F(xiàn)在的問題是，這樣一個模型是否存在。匈牙利著名數(shù)學(xué)家、信息論最高獎香農(nóng)獎得主希薩（Csiszar）證明，對任何一組不自相矛盾的信息，這個最大熵模型不僅存在，而且是唯一的。而且它們都有同一個非常簡單的形式 — 指數(shù)函數(shù)。下面公式是根據(jù)上下文（前兩個詞）和主題預(yù)測下一個詞的最大熵模型，其中 w3 是要預(yù)測的詞（王曉波或者王小波）w1 和 w2 是它的前兩個字（比如說它們分別是“出版”，和“”），也就是其上下文的一個大致估計，subject 表示主題。

我們看到，在上面的公式中，有幾個參數(shù) lambda 和 Z ，他們需要通過觀測數(shù)據(jù)訓(xùn)練出來。最大熵模型在形式上是最漂亮的統(tǒng)計模型，而在實現(xiàn)上是最復(fù)雜的模型之一。

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

最原始的最大熵模型的訓(xùn)練方法是一種稱為通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不復(fù)雜，大致可以概括為以下幾個步驟：?

1. 假定第零次迭代的初始模型為等概率的均勻分布。?
2. 用第 N 次迭代的模型來估算每種信息特征在訓(xùn)練數(shù)據(jù)中的分布，如果超過了實際的，就把相應(yīng)的模型參數(shù)變??；否則，將它們便大。?
3. 重復(fù)步驟 2 直到收斂。

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

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

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

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

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

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

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