最大熵算法筆記

最大熵算法筆記最大熵，就是要保留全部的不確定性，將風(fēng)險(xiǎn)降到最小，從信息論的角度講，就是保留了最大的不確定性。最大熵原理指出，當(dāng)我們需要對(duì)一個(gè)隨機(jī)事件的概率分布進(jìn)行預(yù)測(cè)時(shí)，我們的預(yù)測(cè)應(yīng)當(dāng)滿足全部已知的條件，而對(duì)未知的情況不要做任何主觀假設(shè)。在這種情況下，概率分布最均勻，預(yù)測(cè)的風(fēng)險(xiǎn)最小。因?yàn)檫@時(shí)概率分布的信息熵最大，所以人們稱這種模型叫"最大熵模型"。匈牙利著名數(shù)學(xué)家、信息論最高獎(jiǎng)香農(nóng)獎(jiǎng)得主希薩（Csiszar）證明，對(duì)任何一組不自相矛盾的信息，這個(gè)最大熵模型不僅存在，而且是唯一的。而且它們都有同一個(gè)非常簡(jiǎn)單的形式--指數(shù)函數(shù)。我們已經(jīng)知道所有的最大熵模型都是指數(shù)函數(shù)的形式，現(xiàn)在只需要確定指數(shù)函數(shù)的參數(shù)就可以了，這個(gè)過(guò)程稱為模型的訓(xùn)練。最原始的最大熵模型的訓(xùn)練方法是一種稱為通用迭代算法GIS（generalizediterativescaling）的迭代算法。GIS的原理并不復(fù)雜，大致可以概括為以下幾個(gè)步驟：假定第零次迭代的初始模型為等概率的均勻分布。用第N次迭代的模型來(lái)估算每種信息特征在訓(xùn)練數(shù)據(jù)中的分布，如果超過(guò)了實(shí)際的，就把相應(yīng)的模型參數(shù)變??；否則，將它們便大。重復(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á)拉皮垂(DellaPietra)在IBM對(duì)GIS算法進(jìn)行了兩方面的改進(jìn)，提出了改進(jìn)迭代算法IIS(improvediterativescaling)。這使得最大熵模型的訓(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)微軟的研究員拉納帕提(AdwaitRatnaparkhi)。拉納帕提的聰明之處在于他沒(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)。科學(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ǔ)法信息的文法模型(languagemodel)，我并行使用了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ì)沖基金(hedgefund)公司----文藝復(fù)興技術(shù)公司(RenaissanceTechnologies)。我們知道，決定股票漲落的因素可能有幾十甚至上百種，而最大熵方法恰恰能找到一個(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ò)股神巴菲特的旗艦公司伯克夏哈撒韋(BerkshireHathaway)。同期，伯克夏哈撒韋的總回報(bào)是16倍。最大熵模型做為一個(gè)數(shù)學(xué)模型有一些特殊的或者通用的訓(xùn)練算法，比較常見(jiàn)的有GIS，SCGIS，IIS，LBFGS等，這里我根據(jù)自己的經(jīng)驗(yàn)對(duì)他們做一番比較，僅供參考。收斂速度：既然是最優(yōu)化算法，那么收斂速度是重要的性能衡量標(biāo)準(zhǔn)之一。GIS算法在這方面的表現(xiàn)不敢令人恭維，在大的數(shù)據(jù)模型上大家可能只能用最大迭代次數(shù)來(lái)限制訓(xùn)練時(shí)間了。SCGIS是在GIS算法的基礎(chǔ)上做了優(yōu)化，使減速因子變小，從而收斂速度能提高幾十倍左右。LBFGS算法是一種通用的最優(yōu)化方法，其基于牛頓算法的思想，收斂速度自也不慢，比SCGIS稍快一些。單次迭代速度：?jiǎn)未蔚俣纫彩怯绊懹?xùn)練算法性能的重要因素之一，否則一次迭代就耗上半日，任你收斂再快，也是無(wú)用GIS算法單次迭代是最快的，時(shí)間復(fù)雜度和特征數(shù)量成線性關(guān)系，但其實(shí)就時(shí)間復(fù)雜度來(lái)說(shuō)三種算法都差不多SCGIS算法單次迭代速度比GIS慢，在我們的系統(tǒng)中大概是3倍左右，主要由于SCGIS算法中數(shù)學(xué)運(yùn)算比較多，所以其實(shí)現(xiàn)起來(lái)要特別注意針對(duì)數(shù)學(xué)運(yùn)算的優(yōu)化，不過(guò)終究是比GIS要慢的LBFGS算法單次迭代速度比GIS算法稍慢，因?yàn)樵谒惴▋?nèi)部除了和GIS算法類似的求模型期望外還多了一些線掃描之類的東西，但通常情況下這些操作都是很快的穩(wěn)定性：這個(gè)純粹是我們根據(jù)對(duì)特定數(shù)據(jù)上結(jié)果的觀測(cè)總結(jié)出來(lái)的經(jīng)驗(yàn)結(jié)果，無(wú)任何理論根據(jù)GIS算法由于訓(xùn)練過(guò)慢故在實(shí)驗(yàn)中放棄掉了SCGIS算法在用不同的