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