什么是熵(Entropy)
簡(jiǎn)單來說，熵是表示物質(zhì)系統(tǒng)狀態(tài)的一種度量家破，用它老表征系統(tǒng)的無序程度颜说。熵越大购岗，系統(tǒng)越無序，意味著系統(tǒng)結(jié)構(gòu)和運(yùn)動(dòng)的不確定和無規(guī)則门粪；反之喊积，，熵越小庄拇，系統(tǒng)越有序注服，意味著具有確定和有規(guī)則的運(yùn)動(dòng)狀態(tài)。熵的中文意思是熱量被溫度除的商措近。負(fù)熵是物質(zhì)系統(tǒng)有序化溶弟，組織化，復(fù)雜化狀態(tài)的一種度量瞭郑。
熵最早來原于物理學(xué). 德國(guó)物理學(xué)家魯?shù)婪颉た藙谛匏故状翁岢鲮氐母拍罟加脕肀硎救魏我环N能量在空間中分布的均勻程度，能量分布得越均勻屈张，熵就越大擒权。
一滴墨水滴在清水中，部成了一杯淡藍(lán)色溶液
熱水晾在空氣中阁谆，熱量會(huì)傳到空氣中碳抄，最后使得溫度一致
更多的一些生活中的例子:
熵力的一個(gè)例子是耳機(jī)線，我們將耳機(jī)線整理好放進(jìn)口袋场绿，下次再拿出來已經(jīng)亂了剖效。讓耳機(jī)線亂掉的看不見的“力”就是熵力，耳機(jī)線喜歡變成更混亂焰盗。
熵力另一個(gè)具體的例子是彈性力璧尸。一根彈簧的力，就是熵力熬拒。 胡克定律其實(shí)也是一種熵力的表現(xiàn)爷光。
萬有引力也是熵力的一種(熱烈討論的話題)。
渾水澄清[1]
于是從微觀看澎粟，熵就表現(xiàn)了這個(gè)系統(tǒng)所處狀態(tài)的不確定性程度蛀序。香農(nóng)，描述一個(gè)信息系統(tǒng)的時(shí)候就借用了熵的概念捌议，這里熵表示的是這個(gè)信息系統(tǒng)的平均信息量(****平均不確定程度****)哼拔。
最大熵模型
我們?cè)谕顿Y時(shí)常常講不要把所有的雞蛋放在一個(gè)籃子里，這樣可以降低風(fēng)險(xiǎn)瓣颅。在信息處理中倦逐，這個(gè)原理同樣適用。在數(shù)學(xué)上，這個(gè)原理稱為最大熵原理(the maximum entropy principle)檬姥。
讓我們看一個(gè)拼音轉(zhuǎn)漢字的簡(jiǎn)單的例子曾我。假如輸入的拼音是"wang-xiao-bo"，利用語(yǔ)言模型健民，根據(jù)有限的上下文(比如前兩個(gè)詞)抒巢，我們能給出兩個(gè)最常見的名字“王小波”和“王曉波 ”。至于要唯一確定是哪個(gè)名字就難了秉犹，即使利用較長(zhǎng)的上下文也做不到蛉谜。當(dāng)然，我們知道如果通篇文章是介紹文學(xué)的崇堵，作家王小波的可能性就較大型诚；而在討論兩岸關(guān)系時(shí)，臺(tái)灣學(xué)者王曉波的可能性會(huì)較大鸳劳。在上面的例子中狰贯，我們只需要綜合兩類不同的信息，即主題信息和上下文信息赏廓。雖然有不少湊合的辦法涵紊，比如：分成成千上萬種的不同的主題單獨(dú)處理，或者對(duì)每種信息的作用加權(quán)平均等等幔摸，但都不能準(zhǔn)確而圓滿地解決問題摸柄，這樣好比以前我們談到的行星運(yùn)動(dòng)模型中的小圓套大圓打補(bǔ)丁的方法。在很多應(yīng)用中既忆，我們需要綜合幾十甚至上百種不同的信息塘幅，這種小圓套大圓的方法顯然行不通。
數(shù)學(xué)上最漂亮的辦法是最大熵(maximum entropy)模型尿贫，它相當(dāng)于行星運(yùn)動(dòng)的橢圓模型√ごВ“最大熵”這個(gè)名詞聽起來很深?yuàn)W庆亡，但是它的原理很簡(jiǎn)單，我們每天都在用捞稿。說白了又谋，就是要保留全部的不確定性，將風(fēng)險(xiǎn)降到最小娱局。
回到我們剛才談到的拼音轉(zhuǎn)漢字的例子彰亥，我們已知兩種信息，第一衰齐，根據(jù)語(yǔ)言模型任斋，wangxiao-bo可以被轉(zhuǎn)換成王曉波和王小波；第二耻涛，根據(jù)主題废酷，王小波是作家瘟檩，《黃金時(shí)代》的作者等等，而王曉波是臺(tái)灣研究?jī)砂蛾P(guān)系的學(xué)者澈蟆。因此墨辛，我們就可以建立一個(gè)最大熵模型，同時(shí)滿足這兩種信息∨糠現(xiàn)在的問題是睹簇，這樣一個(gè)模型是否存在。匈牙利著名數(shù)學(xué)家寥闪、信息論最高獎(jiǎng)香農(nóng)獎(jiǎng)得主希薩（Csiszar）證明太惠，對(duì)任何一組不自相矛盾的信息，這個(gè)最大熵模型不僅存在橙垢，而且是唯一的垛叨。而且它們都有同一個(gè)非常簡(jiǎn)單的形式 -- 指數(shù)函數(shù)。下面公式是根據(jù)上下文（前兩個(gè)詞）和主題預(yù)測(cè)下一個(gè)詞的最大熵模型柜某，其中 w3 是要預(yù)測(cè)的詞（王曉波或者王小波）w1 和 w2 是它的前兩個(gè)字（比如說它們分別是“出版”嗽元，和“”），也就是其上下文的一個(gè)大致估計(jì)喂击，subject 表示主題剂癌。
我們看到，在上面的公式中翰绊，有幾個(gè)參數(shù) lambda 和 Z 佩谷，他們需要通過觀測(cè)數(shù)據(jù)訓(xùn)練出來。最大熵模型在形式上是最漂亮的統(tǒng)計(jì)模型监嗜，而在實(shí)現(xiàn)上是最復(fù)雜的模型之一谐檀。
我們上次談到用最大熵模型可以將各種信息綜合在一起。我們留下一個(gè)問題沒有回答裁奇，就是如何構(gòu)造最大熵模型桐猬。我們已經(jīng)所有的最大熵模型都是指數(shù)函數(shù)的形式，現(xiàn)在只需要確定指數(shù)函數(shù)的參數(shù)就可以了刽肠，這個(gè)過程稱為模型的訓(xùn)練溃肪。
最原始的最大熵模型的訓(xùn)練方法是一種稱為通用迭代算法 GIS(generalized iterative scaling) 的迭代 算法。GIS 的原理并不復(fù)雜音五，大致可以概括為以下幾個(gè)步驟：
- 假定第零次迭代的初始模型為等概率的均勻分布惫撰。
- 用第 N 次迭代的模型來估算每種信息特征在訓(xùn)練數(shù)據(jù)中的分布，如果超過了實(shí)際的躺涝，就把相應(yīng)的模型參數(shù)變谐辍；否則，將它們便大莉撇。
- 重復(fù)步驟 2 直到收斂呢蛤。
GIS 最早是由 Darroch 和 Ratcliff 在七十年代提出的。但是棍郎，這兩人沒有能對(duì)這種算法的物理含義進(jìn)行很好地解釋其障。后來是由數(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。大家只是通過它來了解最大熵模型的算法午笛。 八十年代惭蟋，很有天才的孿生兄弟的達(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é)家們有很大的誘惑力围辙，因此不少研究者試圖把自己的問題用一個(gè)類似最大熵的近似模型去套我碟。誰知這一近似，最大熵模型就變得不完美了姚建，結(jié)果可想而知怎囚，比打補(bǔ)丁的湊合的方法也好不了多少。于是桥胞，不少熱心人又放棄了這種方法。第一個(gè)在實(shí)際信息處理應(yīng)用中驗(yàn)證了最大熵模型的優(yōu)勢(shì)的考婴，是賓夕法尼亞大學(xué)馬庫(kù)斯的另一個(gè)高徒原 IBM 現(xiàn)微軟的研究員拉納帕提(Adwait Ratnaparkhi)贩虾。拉納帕提的聰明之處在于他沒有對(duì)最大熵模型進(jìn)行近似，而是找到了幾個(gè)最適合用最大熵模型沥阱、而計(jì)算量相對(duì)不太大的自然語(yǔ)言處理問題缎罢，比如詞性標(biāo)注和句法分析。拉納帕提成功地將上下文信息、詞性（名詞策精、動(dòng)詞和形容詞等）舰始、句子成分（主謂賓）通過最大熵模型結(jié)合起來，做出了當(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)師說，我發(fā)現(xiàn)一種數(shù)學(xué)變換澳淑，可以將大部分最大熵模型的訓(xùn)練時(shí)間在 IIS 的基礎(chǔ)上減少兩個(gè)數(shù)量級(jí)比原。我在黑板上推導(dǎo)了一個(gè)多小時(shí)，他沒有找出我的推導(dǎo)中的任何破綻偶惠，接著他又回去想了兩天春寿，然后告訴我我的算法是對(duì)的。從此忽孽，我們就建造了一些很大的最大熵模型绑改。這些模型比修修補(bǔ)補(bǔ)的湊合的方法好不少。即使在我找到了快速訓(xùn)練算法以后兄一，為了訓(xùn)練一個(gè)包含上下文信息厘线，主題信息和語(yǔ)法信息的文法模型(language model)，我并行使用了20 臺(tái)當(dāng)時(shí)最快的 SUN 工作站出革，仍然計(jì)算了三個(gè)月造壮。由此可見最大熵模型的復(fù)雜的一面。
最大熵模型骂束，可以說是集簡(jiǎn)與繁于一體耳璧，形式簡(jiǎn)單，實(shí)現(xiàn)復(fù)雜展箱。值得一提的是旨枯，在Google的很多產(chǎn)品中，比如機(jī)器翻譯混驰，都直接或間接地用到了最大熵模型攀隔。 講到這里皂贩，讀者也許會(huì)問，當(dāng)年最早改進(jìn)最大熵模型算法的達(dá)拉皮垂兄弟這些年難道沒有做任何事嗎昆汹？他們?cè)诰攀甏踬Z里尼克離開 IBM 后明刷，也退出了學(xué)術(shù)界，而到在金融界大顯身手满粗。他們兩人和很多 IBM 語(yǔ)音識(shí)別的同事一同到了一家當(dāng)時(shí)還不大辈末，但現(xiàn)在是世界上最成功對(duì)沖基金(hedge fund)公司----文藝復(fù)興技術(shù)公司 (Renaissance Technologies)。我們知道败潦，決定股票漲落的因素可能有幾十甚至上百種本冲，而最大熵方法恰恰能找到一個(gè)同時(shí)滿足成千上萬種不同條件的模型。達(dá)拉皮垂兄弟等科學(xué)家在那里劫扒，用于最大熵模型和其他一些先進(jìn)的數(shù)學(xué)工具對(duì)股票預(yù)測(cè)檬洞，獲得了巨大的成功。從該基金 1988 年創(chuàng)立至今沟饥，它的凈回報(bào)率高達(dá)平均每年 34%添怔。也就是說，如果 1988 年你在該基金投入一塊錢贤旷，今天你能得到 200 塊錢广料。這個(gè)業(yè)績(jī)，遠(yuǎn)遠(yuǎn)超過股神巴菲特的旗艦公司伯克夏哈撒韋（Berkshire Hathaway)幼驶。同期艾杏，伯克夏哈撒韋的總回報(bào)是 16 倍。 值得一提的是盅藻，信息處理的很多數(shù)學(xué)手段购桑，包括隱含馬爾可夫模型、子波變換氏淑、貝葉斯網(wǎng)絡(luò)等等勃蜘，在華爾街多有直接的應(yīng)用。由此可見假残，數(shù)學(xué)模型的作用缭贡。
HMM（隱馬爾可夫模型）
隱馬爾可夫模型（Hidden Markov Model，HMM）是統(tǒng)計(jì)模型辉懒，它用來描述一個(gè)含有隱含未知參數(shù)的馬爾可夫過程阳惹。其難點(diǎn)是從可觀察的參數(shù)中確定該過程的隱含參數(shù)。然后利用這些參數(shù)來作進(jìn)一步的分析眶俩，例如模式識(shí)別穆端。
是在被建模的系統(tǒng)被認(rèn)為是一個(gè)馬爾可夫過程與未觀測(cè)到的（隱藏的）的狀態(tài)的統(tǒng)計(jì)馬爾可夫模型。
下面用一個(gè)簡(jiǎn)單的例子來闡述：
假設(shè)我手里有三個(gè)不同的骰子仿便。第一個(gè)骰子是我們平常見的骰子（稱這個(gè)骰子為D6）体啰，6個(gè)面，每個(gè)面（1嗽仪，2荒勇，3，4闻坚，5沽翔，6）出現(xiàn)的概率是1/6。第二個(gè)骰子是個(gè)四面體（稱這個(gè)骰子為D4）窿凤，每個(gè)面（1仅偎，2，3雳殊，4）出現(xiàn)的概率是1/4橘沥。第三個(gè)骰子有八個(gè)面（稱這個(gè)骰子為D8），每個(gè)面（1夯秃，2伟叛，3稚虎，4，5，6学搜，7，8）出現(xiàn)的概率是1/8奠旺。
假設(shè)我們開始擲骰子宦棺，我們先從三個(gè)骰子里挑一個(gè)，挑到每一個(gè)骰子的概率都是1/3箕戳。然后我們擲骰子某残，得到一個(gè)數(shù)字，1漂羊，2驾锰，3，4走越，5椭豫，6，7旨指，8中的一個(gè)赏酥。不停的重復(fù)上述過程，我們會(huì)得到一串?dāng)?shù)字谆构，每個(gè)數(shù)字都是1裸扶，2，3搬素，4呵晨，5魏保，6，7摸屠，8中的一個(gè)谓罗。例如我們可能得到這么一串?dāng)?shù)字（擲骰子10次）：1 6 3 5 2 7 3 5 2 4
這串?dāng)?shù)字叫做可見狀態(tài)鏈。但是在隱馬爾可夫模型中季二，我們不僅僅有這么一串可見狀態(tài)鏈檩咱，還有一串隱含狀態(tài)鏈。在這個(gè)例子里胯舷，這串隱含狀態(tài)鏈就是你用的骰子的序列刻蚯。比如，隱含狀態(tài)鏈有可能是：D6 D8 D8 D6 D4 D8 D6 D6 D4 D8
一般來說桑嘶，HMM中說到的馬爾可夫鏈其實(shí)是指隱含狀態(tài)鏈炊汹，因?yàn)殡[含狀態(tài)（骰子）之間存在轉(zhuǎn)換概率（transition probability）。在我們這個(gè)例子里不翩，D6的下一個(gè)狀態(tài)是D4兵扬，D6，D8的概率都是1/3口蝠。D4器钟，D8的下一個(gè)狀態(tài)是D4，D6妙蔗，D8的轉(zhuǎn)換概率也都一樣是1/3傲霸。這樣設(shè)定是為了最開始容易說清楚，但是我們其實(shí)是可以隨意設(shè)定轉(zhuǎn)換概率的眉反。比如昙啄，我們可以這樣定義，D6后面不能接D4寸五，D6后面是D6的概率是0.9梳凛，是D8的概率是0.1。這樣就是一個(gè)新的HMM梳杏。
同樣的韧拒，盡管可見狀態(tài)之間沒有轉(zhuǎn)換概率，但是隱含狀態(tài)和可見狀態(tài)之間有一個(gè)概率叫做輸出概率（emission probability）十性。就我們的例子來說叛溢，六面骰（D6）產(chǎn)生1的輸出概率是1/6。產(chǎn)生2劲适，3楷掉，4，5霞势，6的概率也都是1/6烹植。我們同樣可以對(duì)輸出概率進(jìn)行其他定義斑鸦。比如，我有一個(gè)被賭場(chǎng)動(dòng)過手腳的六面骰子草雕，擲出來是1的概率更大鄙才，是1/2，擲出來是2促绵，3，4嘴纺，5败晴，6的概率是1/10。
其實(shí)對(duì)于HMM來說栽渴，如果提前知道所有隱含狀態(tài)之間的轉(zhuǎn)換概率和所有隱含狀態(tài)到所有可見狀態(tài)之間的輸出概率尖坤，做模擬是相當(dāng)容易的。但是應(yīng)用HMM模型時(shí)候呢闲擦，往往是缺失了一部分信息的慢味，有時(shí)候你知道骰子有幾種，每種骰子是什么墅冷，但是不知道擲出來的骰子序列纯路；有時(shí)候你只是看到了很多次擲骰子的結(jié)果，剩下的什么都不知道寞忿。如果應(yīng)用算法去估計(jì)這些缺失的信息驰唬，就成了一個(gè)很重要的問題。這些算法我會(huì)在下面詳細(xì)講腔彰。
××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××× 如果你只想看一個(gè)簡(jiǎn)單易懂的例子叫编，就不需要往下看了∨祝×××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××××
說兩句廢話搓逾，答主認(rèn)為呢，要了解一個(gè)算法杯拐，要做到以下兩點(diǎn)：會(huì)其意霞篡，知其形。答主回答的藕施，其實(shí)主要是第一點(diǎn)寇损。但是這一點(diǎn)呢，恰恰是最重要裳食，而且很多書上不會(huì)講的矛市。正如你在追一個(gè)姑娘，姑娘對(duì)你說“你什么都沒做錯(cuò)诲祸！”你要是只看姑娘的表達(dá)形式呢浊吏，認(rèn)為自己什么都沒做錯(cuò)而昨，顯然就理解錯(cuò)了。你要理會(huì)姑娘的意思找田，“你趕緊給我道歉歌憨！”這樣當(dāng)你看到對(duì)應(yīng)的表達(dá)形式呢，趕緊認(rèn)錯(cuò)墩衙，跪地求饒就對(duì)了务嫡。數(shù)學(xué)也是一樣，你要是不理解意思漆改，光看公式心铃，往往一頭霧水。不過呢挫剑，數(shù)學(xué)的表達(dá)頂多也就是晦澀了點(diǎn)去扣，姑娘的表達(dá)呢，有的時(shí)候就完全和本意相反樊破。所以答主一直認(rèn)為理解姑娘比理解數(shù)學(xué)難多了愉棱。
回到正題，和HMM模型相關(guān)的算法主要分為三類哲戚，分別解決三種問題：
** 1）知道骰子有幾種（隱含狀態(tài)數(shù)量）奔滑，每種骰子是什么（轉(zhuǎn)換概率），根據(jù)擲骰子擲出的結(jié)果（可見狀態(tài)鏈）惫恼，我想知道每次擲出來的都是哪種骰子（隱含狀態(tài)鏈）档押。**
這個(gè)問題呢，在語(yǔ)音識(shí)別領(lǐng)域呢祈纯，叫做解碼問題令宿。這個(gè)問題其實(shí)有兩種解法，會(huì)給出兩個(gè)不同的答案腕窥。每個(gè)答案都對(duì)粒没，只不過這些答案的意義不一樣。第一種解法求最大似然狀態(tài)路徑簇爆，說通俗點(diǎn)呢癞松，就是我求一串骰子序列，這串骰子序列產(chǎn)生觀測(cè)結(jié)果的概率最大入蛆。第二種解法呢响蓉，就不是求一組骰子序列了，而是求每次擲出的骰子分別是某種骰子的概率哨毁。比如說我看到結(jié)果后枫甲，我可以求得第一次擲骰子是D4的概率是0.5，D6的概率是0.3，D8的概率是0.2.第一種解法我會(huì)在下面說到想幻，但是第二種解法我就不寫在這里了粱栖，如果大家有興趣，我們另開一個(gè)問題繼續(xù)寫吧脏毯。
2）還是知道骰子有幾種（隱含狀態(tài)數(shù)量）闹究，每種骰子是什么（轉(zhuǎn)換概率），根據(jù)擲骰子擲出的結(jié)果（可見狀態(tài)鏈）食店，我想知道擲出這個(gè)結(jié)果的概率渣淤。
看似這個(gè)問題意義不大，因?yàn)槟銛S出來的結(jié)果很多時(shí)候都對(duì)應(yīng)了一個(gè)比較大的概率吉嫩。問這個(gè)問題的目的呢砂代，其實(shí)是檢測(cè)觀察到的結(jié)果和已知的模型是否吻合。如果很多次結(jié)果都對(duì)應(yīng)了比較小的概率率挣，那么就說明我們已知的模型很有可能是錯(cuò)的，有人偷偷把我們的骰子給換了露戒。
3）知道骰子有幾種（隱含狀態(tài)數(shù)量）椒功，不知道每種骰子是什么（轉(zhuǎn)換概率），觀測(cè)到很多次擲骰子的結(jié)果（可見狀態(tài)鏈）智什，我想反推出每種骰子是什么（轉(zhuǎn)換概率）动漾。
這個(gè)問題很重要，因?yàn)檫@是最常見的情況荠锭。很多時(shí)候我們只有可見結(jié)果旱眯，不知道HMM模型里的參數(shù)，我們需要從可見結(jié)果估計(jì)出這些參數(shù)证九，這是建模的一個(gè)必要步驟删豺。
問題闡述完了，下面就開始說解法愧怜。（0號(hào)問題在上面沒有提呀页，只是作為解決上述問題的一個(gè)輔助）
0.一個(gè)簡(jiǎn)單問題
其實(shí)這個(gè)問題實(shí)用價(jià)值不高。由于對(duì)下面較難的問題有幫助拥坛，所以先在這里提一下蓬蝶。 知道骰子有幾種，每種骰子是什么猜惋，每次擲的都是什么骰子丸氛，根據(jù)擲骰子擲出的結(jié)果，求產(chǎn)生這個(gè)結(jié)果的概率著摔。
解法無非就是概率相乘：
1.看見不可見的缓窜，破解骰子序列 這里我說的是第一種解法，解最大似然路徑問題。 舉例來說雹洗，我知道我有三個(gè)骰子香罐，六面骰，四面骰时肿，八面骰庇茫。我也知道我擲了十次的結(jié)果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那種骰子螃成，我想知道最有可能的骰子序列旦签。
其實(shí)最簡(jiǎn)單而暴力的方法就是窮舉所有可能的骰子序列，然后依照第零個(gè)問題的解法把每個(gè)序列對(duì)應(yīng)的概率算出來寸宏。然后我們從里面把對(duì)應(yīng)最大概率的序列挑出來就行了宁炫。如果馬爾可夫鏈不長(zhǎng)，當(dāng)然可行氮凝。如果長(zhǎng)的話羔巢，窮舉的數(shù)量太大，就很難完成了罩阵。 另外一種很有名的算法叫做Viterbi algorithm. 要理解這個(gè)算法竿秆，我們先看幾個(gè)簡(jiǎn)單的列子。 首先稿壁，如果我們只擲一次骰子：
看到結(jié)果為1.對(duì)應(yīng)的最大概率骰子序列就是D4幽钢，因?yàn)镈4產(chǎn)生1的概率是1/4，高于1/6和1/8. 把這個(gè)情況拓展傅是，我們擲兩次骰子：
結(jié)果為1匪燕，6.這時(shí)問題變得復(fù)雜起來，我們要計(jì)算三個(gè)值喧笔，分別是第二個(gè)骰子是D6帽驯，D4，D8的最大概率书闸。顯然界拦，要取到最大概率，第一個(gè)骰子必須為D4梗劫。這時(shí)享甸，第二個(gè)骰子取到D6的最大概率是
同樣择示，我們計(jì)算第三個(gè)骰子分別是D6束凑，D4，D8的最大概率栅盲。我們?cè)俅伟l(fā)現(xiàn)汪诉，要取到最大概率，第二個(gè)骰子必須為D6谈秫。這時(shí)扒寄，第三個(gè)骰子取到D4的最大概率是
寫到這里稠氮，大家應(yīng)該看出點(diǎn)規(guī)律了。既然擲骰子一二三次可以算半开，擲多少次都可以以此類推。我們發(fā)現(xiàn)赃份，我們要求最大概率骰子序列時(shí)要做這么幾件事情寂拆。首先，不管序列多長(zhǎng)抓韩，要從序列長(zhǎng)度為1算起纠永，算序列長(zhǎng)度為1時(shí)取到每個(gè)骰子的最大概率。然后谒拴，逐漸增加長(zhǎng)度尝江，每增加一次長(zhǎng)度，重新算一遍在這個(gè)長(zhǎng)度下最后一個(gè)位置取到每個(gè)骰子的最大概率英上。因?yàn)樯弦粋€(gè)長(zhǎng)度下的取到每個(gè)骰子的最大概率都算過了炭序，重新計(jì)算的話其實(shí)不難。當(dāng)我們算到最后一位時(shí)苍日，就知道最后一位是哪個(gè)骰子的概率最大了惭聂。然后，我們要把對(duì)應(yīng)這個(gè)最大概率的序列從后往前推出來相恃。
2.誰動(dòng)了我的骰子辜纲？ 比如說你懷疑自己的六面骰被賭場(chǎng)動(dòng)過手腳了，有可能被換成另一種六面骰，這種六面骰擲出來是1的概率更大耕腾，是1/2见剩，擲出來是2，3扫俺，4苍苞，5，6的概率是1/10牵舵。你怎么辦么柒啤？答案很簡(jiǎn)單，算一算正常的三個(gè)骰子擲出一段序列的概率畸颅，再算一算不正常的六面骰和另外兩個(gè)正常骰子擲出這段序列的概率担巩。如果前者比后者小，你就要小心了没炒。 比如說擲骰子的結(jié)果是：
要算用正常的三個(gè)骰子擲出這個(gè)結(jié)果的概率涛癌，其實(shí)就是將所有可能情況的概率進(jìn)行加和計(jì)算。同樣送火，簡(jiǎn)單而暴力的方法就是把窮舉所有的骰子序列拳话，還是計(jì)算每個(gè)骰子序列對(duì)應(yīng)的概率，但是這回种吸，我們不挑最大值了弃衍，而是把所有算出來的概率相加，得到的總概率就是我們要求的結(jié)果坚俗。這個(gè)方法依然不能應(yīng)用于太長(zhǎng)的骰子序列（馬爾可夫鏈）镜盯。 我們會(huì)應(yīng)用一個(gè)和前一個(gè)問題類似的解法，只不過前一個(gè)問題關(guān)心的是概率最大值猖败，這個(gè)問題關(guān)心的是概率之和速缆。解決這個(gè)問題的算法叫做前向算法（forward algorithm）。 首先恩闻，如果我們只擲一次骰子：
看到結(jié)果為1.產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算艺糜，總概率為0.18：
把這個(gè)情況拓展，我們擲兩次骰子：
看到結(jié)果為1幢尚，6.產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算破停，總概率為0.05：
繼續(xù)拓展，我們擲三次骰子：
看到結(jié)果為1尉剩，6辱挥，3.產(chǎn)生這個(gè)結(jié)果的總概率可以按照如下計(jì)算，總概率為0.03：
同樣的边涕，我們一步一步的算晤碘，有多長(zhǎng)算多長(zhǎng)褂微，再長(zhǎng)的馬爾可夫鏈總能算出來的。用同樣的方法园爷，也可以算出不正常的六面骰和另外兩個(gè)正常骰子擲出這段序列的概率宠蚂，然后我們比較一下這兩個(gè)概率大小，就能知道你的骰子是不是被人換了童社。
Viterbi algorithm
HMM（隱馬爾可夫模型）是用來描述隱含未知參數(shù)的統(tǒng)計(jì)模型求厕，舉一個(gè)經(jīng)典的例子：一個(gè)東京的朋友每天根據(jù)天氣{下雨，天晴}決定當(dāng)天的活動(dòng){公園散步,購(gòu)物,清理房間}中的一種扰楼，我每天只能在twitter上看到她發(fā)的推“啊呀癣，我前天公園散步、昨天購(gòu)物弦赖、今天清理房間了项栏！”，那么我可以根據(jù)她發(fā)的推特推斷東京這三天的天氣蹬竖。在這個(gè)例子里沼沈，顯狀態(tài)是活動(dòng)，隱狀態(tài)是天氣币厕。
任何一個(gè)HMM都可以通過下列五元組來描述：
:param obs:觀測(cè)序列
:param states:隱狀態(tài)
:param start_p:初始概率（隱狀態(tài)）
:param trans_p:轉(zhuǎn)移概率（隱狀態(tài)）
:param emit_p: 發(fā)射概率 （隱狀態(tài)表現(xiàn)為顯狀態(tài)的概率）
偽碼如下：
states = ('Rainy', 'Sunny')
observations = ('walk', 'shop', 'clean')
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
transition_probability = {
'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
}
emission_probability = {
'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}
求解最可能的天氣
求解最可能的隱狀態(tài)序列是HMM的三個(gè)典型問題之一列另，通常用維特比算法解決。維特比算法就是求解HMM上的最短路徑（-log(prob)旦装，也即是最大概率）的算法页衙。
稍微用中文講講思路，很明顯阴绢，第一天天晴還是下雨可以算出來：
定義V[時(shí)間][今天天氣] = 概率店乐，注意今天天氣指的是，前幾天的天氣都確定下來了（概率最大）今天天氣是X的概率旱函，這里的概率就是一個(gè)累乘的概率了。
因?yàn)榈谝惶煳业呐笥讶ド⒉搅嗣杼希缘谝惶煜掠甑母怕蔞[第一天][下雨] = 初始概率[下雨] * 發(fā)射概率[下雨][散步] = 0.6 * 0.1 = 0.06棒妨，同理可得V[第一天][天晴] = 0.24 。從直覺上來看含长，因?yàn)榈谝惶炫笥殉鲩T了券腔，她一般喜歡在天晴的時(shí)候散步，所以第一天天晴的概率比較大拘泞，數(shù)字與直覺統(tǒng)一了纷纫。
從第二天開始，對(duì)于每種天氣Y陪腌，都有前一天天氣是X的概率 * X轉(zhuǎn)移到Y(jié)的概率 * Y天氣下朋友進(jìn)行這天這種活動(dòng)的概率辱魁。因?yàn)榍耙惶焯鞖釾有兩種可能烟瞧，所以Y的概率有兩個(gè)，選取其分別解決三種問題中較大一個(gè)作為V[第二天][天氣Y]的概率染簇，同時(shí)將今天的天氣加入到結(jié)果序列中
比較V[最后一天][下雨]和[最后一天][天晴]的概率参滴，找出較大的哪一個(gè)對(duì)應(yīng)的序列，就是最終結(jié)果锻弓。
算法的代碼可以在github上看到砾赔，地址為：
https://github.com/hankcs/Viterbi
運(yùn)行完成后根據(jù)Viterbi得到結(jié)果：
Sunny Rainy Rainy
Viterbi被廣泛應(yīng)用到分詞，詞性標(biāo)注等應(yīng)用場(chǎng)景青灼。
轉(zhuǎn)自一文搞懂HMM（隱馬爾可夫模型）
