隱馬爾可夫〔HiddenMarkovModel，HMM〕一、馬爾可夫過(guò)程〔MarkovProcess〕1、馬爾可夫過(guò)程介紹馬爾可夫過(guò)程(MarkovProcess)，它因俄羅斯數(shù)學(xué)家安德烈·馬爾可夫而得名，代表數(shù)學(xué)中具有馬爾可夫性質(zhì)的離散隨機(jī)過(guò)程。該過(guò)程中，每個(gè)狀態(tài)的轉(zhuǎn)移只依賴于之前的n個(gè)狀態(tài)，這個(gè)過(guò)程被稱為1個(gè)n階的模型，其中n是影響轉(zhuǎn)移狀態(tài)的數(shù)目。最簡(jiǎn)單的馬爾科夫過(guò)程就是一階過(guò)程，每一個(gè)狀態(tài)的轉(zhuǎn)移只依賴于其之前的那一個(gè)狀態(tài)。馬爾可夫鏈?zhǔn)请S機(jī)變量X1,…,Xn的一個(gè)數(shù)列。這些變量的范圍，即他們所有可能取值的集合，被稱為“狀態(tài)空間〞，而Xn的值那么是在時(shí)間n的狀態(tài)。如果Xn+1對(duì)于過(guò)去狀態(tài)的條件概率分布僅是Xn的一個(gè)函數(shù)，那么這里x為過(guò)程中的某個(gè)狀態(tài)。上面這個(gè)恒等式可以被看作是馬爾可夫性質(zhì)。2、馬爾可夫過(guò)程舉例以下圖展示了天氣這個(gè)例子中所有可能的一階轉(zhuǎn)移：注意一個(gè)含有N個(gè)狀態(tài)的一階過(guò)程有N2個(gè)狀態(tài)轉(zhuǎn)移。每一個(gè)轉(zhuǎn)移的概率叫做狀態(tài)轉(zhuǎn)移概率(statetransitionprobability)，即從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)的概率。這所有的N2個(gè)概率可以用一個(gè)狀態(tài)轉(zhuǎn)移矩陣來(lái)表示，其表示形式如下：對(duì)該矩陣有如下約束條件：下面就是海藻例子的狀態(tài)轉(zhuǎn)移矩陣：這個(gè)矩陣表示，如果昨天是晴天，那么今天有50%的可能是晴天，37.5%的概率是陰天，12.5%的概率會(huì)下雨，很明顯，矩陣中每一行的和都是1。為了初始化這樣一個(gè)系統(tǒng)，我們需要一個(gè)初始的概率向量：這個(gè)向量表示第一天是晴天。3、一階馬爾可夫過(guò)程定義如上述馬爾可夫過(guò)程例子可知，我們?yōu)橐浑A馬爾可夫過(guò)程定義了以下三個(gè)局部：狀態(tài)：晴天、陰天和下雨；初始向量：定義系統(tǒng)在時(shí)間為0的時(shí)候的狀態(tài)的概率；狀態(tài)轉(zhuǎn)移矩陣：每種天氣轉(zhuǎn)換的概率；所有的能被這樣描述的系統(tǒng)都是一個(gè)馬爾可夫過(guò)程。二、隱馬爾可夫過(guò)程〔HMM〕1、隱馬爾可夫模型介紹隱馬爾可夫模型(HMM)是一個(gè)輸出符號(hào)序列統(tǒng)計(jì)模型，具有T個(gè)狀態(tài)X1,X2.......Xt-1,它按一定的周期從一個(gè)狀態(tài)轉(zhuǎn)移到另一個(gè)狀態(tài)，每次轉(zhuǎn)移時(shí)，輸出一個(gè)符號(hào)〔觀測(cè)值〕。轉(zhuǎn)移到哪一個(gè)狀態(tài)，轉(zhuǎn)移時(shí)輸出什么符號(hào)，分別由狀態(tài)轉(zhuǎn)移概率和轉(zhuǎn)移時(shí)輸出概率來(lái)決定。因?yàn)橹荒苡^測(cè)到輸出符號(hào)的序列，而不能觀測(cè)到狀態(tài)轉(zhuǎn)移序列〔即模型的觀測(cè)序列是通過(guò)哪個(gè)狀態(tài)路徑是不知道的〕所以稱為隱馬爾可夫模型。2、隱馬爾可夫過(guò)程舉例下面是一個(gè)簡(jiǎn)單的例子。氣象學(xué)上，可通過(guò)年輪的寬窄了解各年的氣候狀況，利用年輪上的信息可推測(cè)出幾千年來(lái)的氣候變遷情況。年輪寬表示那年光照充足，風(fēng)調(diào)雨順；假設(shè)年輪較窄，那么表示那年溫度低、雨量少，氣候惡劣。為了簡(jiǎn)單起見(jiàn)，我們只考慮冷(code)，熱(hot)兩種溫度。根據(jù)現(xiàn)代的氣象知識(shí)可以知道，“冷〞的一年跟著下一年為熱的概率為0.4，為冷的概率為0.6；“熱〞的一年跟著下一年為熱的概率為0.7，為冷的概率為0.3?？梢院?jiǎn)單的歸納為下面規(guī)律：我們將樹(shù)的年輪簡(jiǎn)單分為小(small),中(middle),大(large)三種，或者分別寫(xiě)成S,M,L。根據(jù)現(xiàn)代的氣象知識(shí)可以知道，熱的一年樹(shù)木年輪為“小〞，“中〞，“大〞的概率分別為0.1,0.4,0.5；冷的一年樹(shù)木年輪為“小〞，“中〞，“大〞的概率分別為0.7,0.2,0.1。因此，冷(C)，熱(H)對(duì)年輪的影響可以簡(jiǎn)單歸納為下面規(guī)律：在這個(gè)系統(tǒng)中，狀態(tài)序列是每年的溫度H或者C。因?yàn)橄乱荒甑臏囟戎慌c上一年有關(guān)，所以從一個(gè)狀態(tài)(溫度)轉(zhuǎn)移到下一個(gè)狀態(tài)(溫度)可以看成是一個(gè)一階Markovprocess。因?yàn)闊o(wú)法觀測(cè)過(guò)去的溫度，狀態(tài)序列也被稱為隱藏狀態(tài)。盡管我們不能觀測(cè)過(guò)去的狀態(tài)(溫度)序列，但是可以通過(guò)樹(shù)的年輪給我們提供的信息預(yù)測(cè)溫度。我們的目標(biāo)就是充分利用可觀測(cè)的年輪序列，來(lái)預(yù)測(cè)那些年的溫度序列情況〔Markov過(guò)程〕。從上面規(guī)律可以得到，狀態(tài)轉(zhuǎn)移矩陣A:混淆矩陣(confusionmatrix)B:假設(shè)初始狀態(tài)矩陣π,(如本例中是初始狀態(tài)矩陣是最開(kāi)始產(chǎn)生Hot和Cold天氣的概率)這樣可以得到天氣與樹(shù)年輪的概率圖模型圖中最開(kāi)始產(chǎn)生Hot天氣的概率為0.6〔由初始狀態(tài)矩陣PI決定〕，Hot天氣產(chǎn)生樹(shù)年輪Small的概率為0.1，Hot狀態(tài)產(chǎn)生Hot狀態(tài)的概率為0.7，接著Hot產(chǎn)生Middle的概率為0.4以此類(lèi)推。因此可以得到隱藏天氣序列HHCC產(chǎn)生樹(shù)木年輪序列為SMSL的概率。使用這種方法我們就可以計(jì)算產(chǎn)生SMSL序列存在的所有天氣序列的概率。比擬可得P(CCCH)的概率為0.002822，是最大的。結(jié)論：假設(shè)樹(shù)木年輪序列為SMSL，那么最可能狀態(tài)序列〔Markovprocess〕是CCCH；產(chǎn)生樹(shù)木年輪序列為SMSL的概率為0.009629〔所有可能相加〕。3、HMM的三個(gè)重要假設(shè)以下圖顯示了天氣的例子中隱藏的狀態(tài)和可以觀察到的狀態(tài)之間的關(guān)系。我們假設(shè)隱藏的狀態(tài)是一個(gè)簡(jiǎn)單的一階馬爾可夫過(guò)程，并且他們兩兩之間都可以相互轉(zhuǎn)換。對(duì)HMM來(lái)說(shuō)，有如下三個(gè)重要假設(shè)，盡管這些假設(shè)是不現(xiàn)實(shí)的。假設(shè)1：馬爾可夫假設(shè)〔狀態(tài)構(gòu)成一階馬爾可夫鏈〕假設(shè)2：不動(dòng)性假設(shè)〔狀態(tài)與具體時(shí)間無(wú)關(guān)〕假設(shè)3：輸出獨(dú)立性假設(shè)〔輸出僅與當(dāng)前狀態(tài)有關(guān)〕4、HMM的根本元素一個(gè)HMM可用一個(gè)5元組{N,M,π，A，B}表示，其中：N表示隱藏狀態(tài)的數(shù)量，我們要么知道確切的值，要么猜想該值；M表示可觀測(cè)狀態(tài)的數(shù)量，可以通過(guò)訓(xùn)練集獲得；π={πi}為初始狀態(tài)概率；A={aij}為隱藏狀態(tài)的轉(zhuǎn)移矩陣Pr(xt(i)|xt-1(j))B={bik}表示某個(gè)時(shí)刻因隱藏狀態(tài)而導(dǎo)致可觀察狀態(tài)的概率，即混淆矩陣，Pr(ot(i)|xt(j))。在狀態(tài)轉(zhuǎn)移矩陣和混淆矩陣中的每個(gè)概率都是時(shí)間無(wú)關(guān)的，即當(dāng)系統(tǒng)演化時(shí)，這些矩陣并不隨時(shí)間改變。對(duì)于一個(gè)N和M固定的HMM來(lái)說(shuō)，用λ={π,A,B}表示HMM參數(shù)。三、HMM的三個(gè)根本問(wèn)題1、問(wèn)題1——識(shí)別問(wèn)題1.1問(wèn)題描述給定模型λ={π,A,B}和觀測(cè)序列O=〔O0,O1,…,OT-1〕,如何快速有效的找到P(O|λ)？解釋?zhuān)杭僭O(shè)我們已經(jīng)有一個(gè)特定的隱馬爾科夫模型λ和一個(gè)可觀察狀態(tài)序列集。我們也許想知道在所有可能的隱藏狀態(tài)序列下，給定的可觀察狀態(tài)序列的概率。問(wèn)題1可以歸納為：舉例：如2.2小節(jié)的例子中，模型λ，觀測(cè)序列O=〔SMSL〕，求產(chǎn)生SMSL年輪序列的概率。1.2解決方案1.2.1蠻力算法假設(shè)用圖表示可以得到如下：其中：然而，這種直接的計(jì)算的方法(蠻力算法)一般是不可行的，實(shí)際情況中，我們不可能知道每一種可能的路徑，而且這種計(jì)算的計(jì)算量也是十分驚人的，到達(dá)大約數(shù)量級(jí)。如，當(dāng)HMM的狀態(tài)數(shù)為5，觀測(cè)序列長(zhǎng)度為100時(shí)，計(jì)算量到達(dá)，是完全無(wú)法接受的。因此需要更有效的算法，這就是Baum等人提出的前向-后向算法。前向算法(a-pass)前向算法即按輸出觀察值序列的時(shí)間，從前向后遞推計(jì)算輸出概率。首先說(shuō)明以下符號(hào)的定義：由上面的符號(hào)的定義，那么at(i)可由下面遞推公式計(jì)算得到：解釋?zhuān)菏褂眠@種前向遞推計(jì)算算法的計(jì)算量大為減少，復(fù)雜度變?yōu)镹2T。同樣的1中例子，N=5,T=100時(shí)，只需要大約2500次乘法。1.2.3后向算法(β-pass)與前向算法類(lèi)似，向后算法即使按輸出觀察序列的時(shí)間，從后面向前遞推計(jì)算輸出概率的方法。首先說(shuō)明以下符號(hào)的定義：由遞推公式可得：解釋?zhuān)?、問(wèn)題2——解碼問(wèn)題2.1問(wèn)題描述給定模型λ={π,A,B}和觀測(cè)序列O=〔O0,O1,…,OT-1〕,找到最優(yōu)的隱藏狀態(tài)序列？解釋?zhuān)焊鶕?jù)可觀察狀態(tài)的序列找到一個(gè)最可能的隱藏狀態(tài)序列。問(wèn)題2可以歸納為：舉例：如2.2小節(jié)的例子中，模型λ，觀測(cè)序列O=〔SMSL〕，求最有可能產(chǎn)生SMSL序列的狀態(tài)序列CCCH。2.2解決方案2.2.1蠻力算法如中計(jì)算每一條可能狀態(tài)序列的概率，然后比擬找出其中概率最大的一條就為我們需要的狀態(tài)序列X。如開(kāi)始的例1中就是采用這種算法。這種算法雖然易理解，但是計(jì)算開(kāi)銷(xiāo)太大，一般不可取。2.2.2前向后向算法在4.1中我們?cè)敿?xì)的討論了前向算法以及后向算法，而前向后向算法就是綜合這兩種算法?？梢杂脕?lái)解決尋找最可能隱藏狀態(tài)序列X的問(wèn)題。首先我們說(shuō)明以下符號(hào)的定義：2.2.3維特比(Viterbi)算法在給定了一個(gè)可觀察序列和HMM的情況下，我們可以考慮遞歸的來(lái)尋找最可能的隱藏序列。我們可以先定義一個(gè)局部概率δ，即到達(dá)某個(gè)中間狀態(tài)的概率。接下來(lái)我們將討論如何計(jì)算t=1和t=n(n>1)的局部概率。注意這里的局部概率和前向算法中的局部概率是不一樣的，這里的局部概率表示的是在t時(shí)刻最可能到達(dá)某個(gè)狀態(tài)的一條路徑的概率，而不是所有概率之和。1)局部概率和局部最優(yōu)路徑考慮下面這個(gè)圖以及可觀察序列(dry,damp,soggy)的一階轉(zhuǎn)移。對(duì)于每一個(gè)中間狀態(tài)和終止?fàn)顟B(tài)(t=3)都有一個(gè)最可能的路徑。比方說(shuō)，在t=3時(shí)刻的三個(gè)狀態(tài)都有一個(gè)如下的最可能的路徑：我們可以稱這些路徑為局部最優(yōu)路徑。這些局部最優(yōu)路徑都有一個(gè)概率，也就是局部概率δ。和前向算法中的局部概率不一樣，這里的概率只是一個(gè)最可能路徑的概率，而不是所有路徑的概率和。我們可以用δ(i,t)來(lái)表示在t時(shí)刻，到狀態(tài)i的所有可能的序列〔路徑〕中概率最大的序列的概率，局部最優(yōu)路徑就是到達(dá)這個(gè)最大概率的路徑，對(duì)于每一個(gè)時(shí)刻的每一個(gè)狀態(tài)都有這樣一個(gè)概率和局部最優(yōu)路徑。最后，我們通過(guò)計(jì)算t=T時(shí)刻的每一個(gè)狀態(tài)的最大概率和局部最優(yōu)路徑，選擇其中概率最大的狀態(tài)和它的局部最優(yōu)路徑來(lái)得到全局的最優(yōu)路徑。2)計(jì)算t=1時(shí)刻的局部概率當(dāng)t=1時(shí)刻的時(shí)候，到達(dá)某個(gè)狀態(tài)最大可能的路徑還不存在，但是我們可以直接使用在t=1時(shí)刻某個(gè)狀態(tài)的概率和這個(gè)狀態(tài)到可觀察序列k1的轉(zhuǎn)移概率：3)計(jì)算t>1時(shí)刻的局部概率接下來(lái)我們可以根據(jù)t-1時(shí)刻的局部概率來(lái)求t時(shí)刻的局部概率。我們可以計(jì)算所有到狀態(tài)X的路徑的概率，找到其中最可能的路徑，也就是局部最優(yōu)路徑。注意到這里，到達(dá)X的路徑必然會(huì)經(jīng)過(guò)t-1時(shí)刻的A、B和C，所以我們可以利用之前的結(jié)果。到達(dá)X的最可能的路徑就是下面三個(gè)之一：(狀態(tài)序列)，...，A，X(狀態(tài)序列)，...，B，X(狀態(tài)序列)，...，C，X我們需要做的就是找到以AX、BX和CX結(jié)尾的路徑中概率最大的那個(gè)。根據(jù)一階馬爾科夫的假設(shè)，一個(gè)狀態(tài)的發(fā)生只和之前的一個(gè)狀態(tài)有關(guān)系，所以X在某個(gè)序列的最后發(fā)生的概率只依賴于其之前的一個(gè)狀態(tài)：Pr(到達(dá)A的最優(yōu)路徑).Pr(X|A).Pr(觀察狀態(tài)|X)有個(gè)了這個(gè)公式，我們就可以利用t-1時(shí)刻的結(jié)果和狀態(tài)轉(zhuǎn)移矩陣和混淆矩陣的數(shù)據(jù)：將上面這個(gè)表達(dá)式推廣一下，就可以得到t時(shí)刻可觀察狀態(tài)為kt的第i個(gè)狀態(tài)的最大局部概率的計(jì)算公式：其中aji表示從狀態(tài)j轉(zhuǎn)移到狀態(tài)i的概率，bikt表示狀態(tài)i被觀察成kt的概率。4)后向指針考慮以下圖在每一個(gè)中間狀態(tài)和結(jié)束狀態(tài)都有一個(gè)局部最優(yōu)概率δ(i,t)。但是我們的目的是找到最可能的隱藏狀態(tài)序列，所以我們需要一個(gè)方法去記住局部最優(yōu)路徑的每一個(gè)節(jié)點(diǎn)?？紤]到要計(jì)算t時(shí)刻的局部概率，我們只需要知道t-1時(shí)刻的局部概率，所以我們只需要記錄那個(gè)導(dǎo)致了t時(shí)刻最大局部概率的的狀態(tài)，也就是說(shuō)，在任意時(shí)刻，系統(tǒng)都必須處在一個(gè)能在下一時(shí)刻產(chǎn)生最大局部概率的狀態(tài)。如以下圖所示：我們可以利用一個(gè)后向指針φ來(lái)記錄導(dǎo)致某個(gè)狀態(tài)最大局部概率的前一個(gè)狀態(tài)，即這里argmax表示能最大化后面公式的j值，同樣可以發(fā)現(xiàn)這個(gè)公式和t-1時(shí)刻的局部概率和轉(zhuǎn)移概率有關(guān)，因?yàn)楹笙蛑羔樦皇菫榱苏业健拔覐哪睦飦?lái)〞，這個(gè)問(wèn)題和可觀察狀態(tài)沒(méi)有關(guān)系，所以這里不需要再乘上混淆矩陣因子。全局的行為如以下圖所示：5)優(yōu)點(diǎn)使用viterbi算法對(duì)一個(gè)可觀察狀態(tài)進(jìn)行解碼有兩個(gè)重要的優(yōu)點(diǎn)：a)通過(guò)使用遞歸來(lái)減少?gòu)?fù)雜度，這點(diǎn)和之前的前向算法是一樣的b)可以根據(jù)可觀察序列找到最優(yōu)的隱藏序列，這個(gè)的計(jì)算公式是：這里就是一個(gè)從左往右翻譯的過(guò)程，通過(guò)前面的翻譯結(jié)果得到后面的結(jié)果，起始點(diǎn)是初始向量π。6〕補(bǔ)充但在序列某個(gè)地方有噪聲干擾的時(shí)候，某些方法可能會(huì)和正確答案相差的較遠(yuǎn)。但是Viterbi算法會(huì)查看整個(gè)序列來(lái)決定最可能的終止?fàn)顟B(tài)，然后通過(guò)后向指針來(lái)找到之前的狀態(tài)，這對(duì)忽略孤立的噪聲非常有用。Viterbi算法提供了一個(gè)根據(jù)可觀察序列計(jì)算隱藏序列的很高效的方法，它利用遞歸來(lái)降低計(jì)算復(fù)雜度，并且使用之前全部的序列來(lái)做判斷，可以很好的容忍噪聲。在計(jì)算的過(guò)程中，這個(gè)算法計(jì)算每一個(gè)時(shí)刻每一個(gè)狀態(tài)的局部概率，并且使用一個(gè)后向指針來(lái)記錄到達(dá)當(dāng)前狀態(tài)的最大可能的上一個(gè)狀態(tài)。最后，最可能的終止?fàn)顟B(tài)就是隱藏序列的最后一個(gè)狀態(tài)，然后通過(guò)后向指針來(lái)查找整個(gè)序列的全部狀態(tài)。3、問(wèn)題3——模型訓(xùn)練問(wèn)題3.1問(wèn)題描述實(shí)際上是一個(gè)模型參數(shù)估計(jì)問(wèn)題，即對(duì)于初始模型和給定用于訓(xùn)練的觀測(cè)序列O=〔O0,O1,…,OT-1〕如何調(diào)整模型λ={π,A,B}的參數(shù)，使得輸出概率P(O|λ)最大？解釋?zhuān)焊鶕?jù)觀察到的序列集來(lái)找到一個(gè)最有可能的HMM。問(wèn)題3可以歸納為：3.2解決方案在很多實(shí)際的情況下，HMM不能被直接的判斷，這就變成了一個(gè)學(xué)習(xí)問(wèn)題，因?yàn)閷?duì)于給定的可