1、馬爾科夫過程馬爾科夫過程可以看做是一個自動機，以一定的概率在各個狀態之間跳轉。考慮一個系統，在每個時刻都可能處于N個狀態中的一個，N個狀態集合 是S1,S2,S3，SN。我們現在用q1，q2，q3,qn來表示系統在t=1,2,3，n時刻下的 狀態。在t=1時，系統所在的狀態q取決于一個初始概率分布PI，PI(SN)表示t=1 時系統狀態為SN的概率。馬爾科夫模型有兩個假設：.系統在時刻t的狀態只與時刻t-1處的狀態相關；(也稱為無后效性).狀態轉移概率與時間無關；(也稱為齊次性或時齊性)第一條具體可以用如下公式表示：P(qt=Sj%=Si,qt-2=Sk,尸胴=用%尸1)其中，t為大于1的任意

2、數值，Sk為任意狀態第二個假設則可以用如下公式表示：P(qt=Sj|qt-1=S尸 P(qk=Sj|qk-1=Si)其中，k為任意時刻。下圖是一個馬爾科夫過程的樣例圖：可以把狀態轉移概率用矩陣A表示，矩陣的行列長度均為狀態數目，2弓表 示 P(SilSi-1)隱馬爾科夫過程與馬爾科夫相比，隱馬爾科夫模型則是雙重隨機過程，不僅狀態轉移之間是 個隨機事件，狀態和輸出之間也是一個隨機過程，如下圖所示：一狀態轉移觀察值輸出此圖是從別處找來的，可能符號與我之前描述馬爾科夫時不同，相信大 家也能理解。該圖分為上下兩行，上面那行就是一個馬爾科夫轉移過程，下面這一行則是 輸出，即我們可以觀察到的值，現在，我們

3、將上面那行的馬爾科夫轉移過程中的 狀態稱為隱藏狀態，下面的觀察到的值稱為觀察狀態，觀察狀態的集合表示為 O=O1,O2,O3，0M。相應的，隱馬爾科夫也比馬爾科夫多了一個假設，即輸出僅與當前狀態有關， 可以用如下公式表示：P(O1,O2，,0tIS1S2,S尸P(O1IS1)*P(O21s2)*.*P(OtISt)其中，O1,O2,0t為從時刻1到時刻t的觀測狀態序列，S1,S2,St則為隱 藏狀態序列。另外，該假設又稱為輸出獨立性假設。舉個例子舉個常見的例子來引出下文，同時方便大家理解！比如我在不同天氣狀態下 去做一些事情的概率不同，天氣狀態集合為下雨，陰天，晴天，事情集合為宅 著，自習，游

4、玩。假如我們已經有了轉移概率和輸出概率，即P(天氣AI天氣 B)和P(事情al天氣A)的概率都已知道，那么則有幾個問題要問(注意，假設一 天我那幾件事情中的一件)，.假如一周內的天氣變化是下雨。晴天。陰天。下雨。陰天。晴天-陰天，那么我這一周自習。宅著。游玩- 自習。游玩。宅著- 自習的概率是多 大？.假如我這一周做事序列是自習。宅著。游玩- 自習。游玩。宅著- 自習，不知道天氣狀態的情況下這個做事序列的概率是多大？.假如一周內的天氣變化是下雨。晴天。陰天。下雨。陰天。晴天- 陰天， 那我們這一周最有可能的做事序列是什么？.假如我這一周做事序列是自習。宅著。游玩- 自習。游玩。宅著- 自習，

5、那么這一周的天氣變化序列最有可能是什么？對于第一個問題，我想大家應該都能很快知道怎么算。（啥？不知道，答案 在本文最后）隱馬模型基本要素及基本三問題綜上所述，我們可以得到隱馬爾科夫的基本要素，即一個五元組S,N,A,B,PI； S：隱藏狀態集合；N：觀察狀態集合；A：隱藏狀態間的轉移概率矩陣；B：輸出矩陣（即隱藏狀態到輸出狀態的概率）；PI：初始概率分布（隱藏狀態的初始概率分布）；其中，A、B、PI稱為隱馬爾科夫的參數，用X表示。由上述問題可以引出隱馬爾科夫的三個基本問題的其中兩個，下文中為了簡 便，將隱馬爾科夫模型簡稱為HMM（Hiden Markov Model）。HMM的三個基本問題是：

6、給定模型（五元組），求某個觀察序列O的概率（樣例問題2）（即已知模型參數，計算某一特定輸出序列的概率.通常使用forward算 法解決.）給定模型和觀察序列O,求可能性最大的隱藏狀態序列（樣例問題4）。 （即已知模型參數，尋找最可能的能產生某一特定輸出序列的隱含狀態 的序列.通常使用Viterbi算法解決.）對于給定的觀察序列O,調整HMM的參數，使觀察序列出現的概率 最大。（即已知輸出序列，尋找最可能的狀態轉移以及輸出概率.通常 使用Baum-Welch算法以及Reversed Viterbi算法解決.）前向算法對于第一個基本問題，計算公式為：p（o|x） = W 尸。SM = W 尸6 團

7、SS即對于觀察序列O,我們需要找出所有可能的隱藏狀態序列S，計算出在給 定模型下S輸出為O的概率（就是樣例問題一啊），然后計算概率之和。直觀上看，假如序列O的長度為T，模型的隱藏狀態集合大小為N，那么一 共有NT個可能的隱藏狀態序列，計算復雜度極高O（NT），暴力算法太慢了。解決方案就是動態規劃(Dynamic Programming )。假設觀察序列為O1,O2,O3,0t在時刻i (1i=t)時，定義C為產生序列 O1,O2，,0i且Si=Sk的概率：C(if5；) = Ptfil, 02,.f Qi, Si = Skg)其中，sk為任意一個隱藏狀態值。則C(i+1,Sr)的計算公式為:N

8、c(i + lfSr)=幺。&耳乂帚印口k= 1其中，Sr為任意一個隱藏狀態值。A為轉移概率。B為隱藏狀態到觀察狀態 的概率。為了便于理解，還是看圖：E.臼刁土宅卷f丸游玩- -f也自習C(3,下雨)考慮了 t=1和t=2的所有組合情況，同時也是C(4,下雨陰天I晴天) 的子問題。C(3,陰天)和C(3,晴天)也是如此計算，而C(i+1,Sr)計算公式則可以表由圖知：C（4,陰天）=C（3,下雨）*A（下雨，陰天）+C（3,陰天）*A（陰天，陰天）+C（3, 晴天）*A（晴天，陰天）廣B（陰天,自習）。通過圖片，大家應該能直觀的理解該算法了，該算法又稱為前向算法，那還 有后向算法？是的，后向算

9、法就是這個算法倒過來嘛，也是動態規劃，這里就不 贅述了，有興趣的看參考文獻。另外，這里沒有講解如何初始化概率，也可以去 參考文獻里查證。維特比算法現在，HMM的第一個基本問題解決了，下面開始解決第二個問題，第二個 問題又稱為解碼問題，同樣的，暴力算法是計算所有可能性的概率，然后找出擁 有最大概率值的隱藏狀態序列。與問題一的暴力解決方案類似，復雜度為O（NT）。那應該用什么方案呢？毫無疑問，還是動態規劃啊！假設觀察序列為O1,O2,O3,0t.在時刻i（1i=2 時，節點中保存著一些小節點，這些小節點的數目即為上一個狀態的狀態數目， 小節點的值意義為到達該時刻狀態為Sr且前一時刻狀態為Sk時能夠產生狀態序 列的最大概率。比如背景為綠色的小節點的值的意義為時刻3為下雨，時刻2 為下雨時去自習。宅著。游玩的最大概率。（注意，節點表示時刻i時某個狀態， 小節點表示節點中保存的前一狀態的節點，比如綠色的那個節點）。對于時刻i（i2），每個小節點的概率為DR,St,SQ = m改0LQ2，- 1） = S/燈那么對于時刻i+1,小節點的概率為：D（i 十 L$wSq）=* 山（工及用） * %馬以然后，從時刻t中尋找最大的小節點回溯即可。樣例問題一答案上面樣例問題中第一問的答案是：概率：P=P（下雨）*P（晴天下雨）*P（陰天|晴天）*自習下雨）*P（宅著|晴