HMM了解以及相關算法

1、MM  

    先有馬爾可夫模型，再有隐馬爾可夫模型，什麼叫馬爾可夫模型呢，也就是具有馬爾可夫性質的模型，而馬爾可夫性質用概念來講，就是：一個過程的“将來”隻取決于“現在”，而不取決于“過去”。這就叫馬爾可夫性，具有馬爾可夫性的過程叫做馬爾可夫過程。

     （下面來一段數學定義：

           設在時刻t的随機變量用St 表示，其觀察值用st表示，則如果當S1=s1,S2=s2，……St=st的前提下 ，S(t+1)=s（t+1）的機率為：

         當n=1時就是一階馬爾可夫模型了，這個式子就是表明：系統在任一時刻所處的狀态隻與此時刻的前一時刻所處的狀态有關 （注意，跟上面的“過去”、“現在”、“将來”要了解開來），後面還有一些時間無關性、轉移機率相關的數學函數，在此先不列出，重在了解馬爾可夫模型的思想先。  

）

2、HMM

         HMM與一階MM形式差不多，而H則展現在HMM是由兩個随機過程組成，一個是狀态轉移序列，它對應着一個單純Markov過程；另一個是每次轉移時輸出的符号組成的符号序列。這兩個随機過程，其中狀态轉移随機過程是不可觀測的，隻能通過另一個随機過程的輸出觀察序列觀測。

        例如，容器與彩球的模型：有若幹個容器，每個容器中按已知比例放入各色的彩球（這樣，選擇了容器後，我們可以用機率來預測取出各種彩球的可能性）；我們做這樣的實驗，實驗者從容器中取彩球——先選擇一個容器，再從中抓出某一個球，隻給觀察者看球的顔色；這樣，每次取取出的球的顔色是可以觀測到的，即o1, o2,…，但是每次選擇哪個容器是不暴露給觀察者的，容器的序列就組成了隐藏狀态序列S1, S2,…Sn。這是一個典型的可以用HMM描述的實驗。

         以語音識别為例講講HMM模型，HMM一般可用六個參數來定義，M={S,O,A,B,PI,F};

         S:模型中狀态的有限集合，記t時刻模型所處狀态為St

        O：輸出的觀察值符号集合,t時刻模型觀察到的觀察值為Ot

        A：狀态轉移機率的集合

        B：輸出觀測值機率的集合，根據B将HMM分為離散型和連續型

        PI：系統初始狀态機率的集合

        F：系統終了狀态的集合

        為了便于表示，常用下面的形式表示一個HMM，即簡寫為M={A,B,pi }。HMM可以分為兩部分，一個是Markov鍊，由pi ，A描述，産生的輸出為

狀态序列。另一個随機過程，由B描述，産生的輸出為觀察符号序列。

3、HMM的三個基本問題

        a.已知觀測序列O={ o1 , o2 …… oT }和模型 U{A,B,pi },如何有效計算在給定模型的條件下産生觀測序列O的條件機率P(O/U)最大。

        b.已知觀測序列O=O={ o1 , o2 …… oT }和模型U {A,B,pi },如何選擇相應的在某種意義上最佳的(能最好解釋觀測序列的)狀态序列S。

        c.如何調整模型參數U {A,B,pi }以使條件機率P(O|U)最大。

4、3中abc問題的解決方案

      a問題由上一篇文章中的前向算法解決

      b問題由viterbi算法解決

      c問題後續繼續說明，其使用的算法是Baum-Welch算法

5、viterbi算法的例子

    假設你有一個朋友在外地，每天你可以通過電話來了解他每天的活動。他每天隻會做三種活動之一——Walk, Shop, Clean。你的朋友從事哪一種活動的機率與當地的氣候有關，這裡，我們隻考慮兩種天氣——Rainy, Sunny。我們知道，天氣與運動的關系如下：

P(o|state)	Rainy	Sunny
Walk	0.1	0.6
Shop	0.4	0.3
Clean	0.5	0.1

例如，在下雨天出去散步的可能性是0.1。

而天氣之前互相轉換的關系如下，（從行到列）

p(state—>next_state)	Rainy	Sunny
Rainy	0.7	0.3
Sunny	0.4	0.6

例如，從今天是晴天而明天就開始下雨的可能性是0.4 。

    同時為了求解問題我們假設初始情況：通話開始的第一天的天氣有0.6的機率是Rainy，有0.4機率是Sunny。OK，現在的問題是，如果連續三天，你發現你的朋友的活動是：Walk->Shop->Clean(觀測序列)；那麼，如何判斷你朋友那裡這幾天的天氣(隐藏狀态序列)是怎樣的？

    解決這個問題的python僞代碼如下：

def forward_viterbi(y, X, sp, tp, ep):

T = {}

for state in X:

## prob. V. path V. prob.

T[state] = (sp[state], [state], sp[state])

for output in y:

U = {}

for next_state in X:

    total = 0

    argmax = None

    valmax = 0

    for source_state in X:

        (prob, v_path, v_prob) = T[source_state]

        p = ep[source_state][output] * tp[source_state][next_state]

        prob *= p

        v_prob *= p

        total += prob

        if v_prob > valmax:

            argmax = v_path + [next_state]

            valmax = v_prob

    U[next_state] = (total, argmax, valmax)

T = U

## apply sum/max to the final states:

total = 0

argmax = None

valmax = 0

for state in X:

(prob, v_path, v_prob) = T[state]

total += prob

if v_prob > valmax:

    argmax = v_path

    valmax = v_prob

return (total, argmax, valmax)幾點說明：

    算法對于每一個狀态要記錄一個三元組：(prob, v_path, v_prob)，其中，prob是從開始狀态到目前狀态所有路徑（不僅僅

是最有可能的viterbi路徑）的機率加在一起的結果（作為算法附産品，它可以輸出一個觀察序列在給定HMM下總的出現機率，即forward算法的輸出），v_path是從開始狀态一直到目前狀态的viterbi路徑，v_prob則是該路徑的機率。

    算法開始，初始化T （T是一個Map，将每一種可能狀态映射到上面所說的三元組上） 三重循環，對每個一活動y，考慮下一步每一個可能的狀态next_state，并重新計算若從T中的目前狀态state躍遷到next_state機率會有怎樣的變化。躍遷主要考慮天氣轉移（tp[source_state][next_state]）與該天氣下從事某種活動（ep[source_state][output]）的聯合機率。所有下一步狀态考慮完後，要從T中找出最優的選擇viterbi路徑——即機率最大的viterbi路徑，即上面更新Map U的代碼U[next_state] = (total, argmax, valmax)。

    算法最後還要對T中的各種情況總結，對total求和，選擇其中一條作為最優的viterbi路徑。

算法輸出四個天氣狀态，這是因為，計算第三天的機率時，要考慮天氣轉變到下一天的情況。

通過程式的輸出可以幫助了解這一過程：{p=p(observation|state)*p(state—>next_state)}

observation=Walk

next_state=Sunny

    state=Sunny

        p=0.36

        triple=(0.144,Sunny->,0.144)

    state=Rainy

        p=0.03

        triple=(0.018,Rainy->,0.018)

Update U[Sunny]=(0.162,Sunny->Sunny->,0.144)

next_state=Rainy

    state=Sunny

        p=0.24

        triple=(0.096,Sunny->,0.096)

    state=Rainy

        p=0.07

        triple=(0.042,Rainy->,0.042)

Update U[Rainy]=(0.138,Sunny->Rainy->,0.096)

observation=Shop

next_state=Sunny

    state=Sunny

        p=0.18

        triple=(0.02916,Sunny->Sunny->,0.02592)

    state=Rainy

        p=0.12

        triple=(0.01656,Sunny->Rainy->,0.01152)

Update U[Sunny]=(0.04572,Sunny->Sunny->Sunny->,0.02592)

next_state=Rainy

    state=Sunny

        p=0.12

        triple=(0.01944,Sunny->Sunny->,0.01728)

    state=Rainy

        p=0.28

        triple=(0.03864,Sunny->Rainy->,0.02688)

Update U[Rainy]=(0.05808,Sunny->Rainy->Rainy->,0.02688)

observation=Clean

next_state=Sunny

    state=Sunny

        p=0.06

        triple=(0.0027432,Sunny->Sunny->Sunny->,0.0015552)

    state=Rainy

        p=0.15

       triple=(0.008712,Sunny->Rainy->Rainy->,0.004032)

Update U[Sunny]=(0.0114552,Sunny->Rainy->Rainy->Sunny->,0.004032)

next_state=Rainy

    state=Sunny

        p=0.04

        triple=(0.0018288,Sunny->Sunny->Sunny->,0.0010368)

    state=Rainy

        p=0.35

        triple=(0.020328,Sunny->Rainy->Rainy->,0.009408)

Update U[Rainy]=(0.0221568,Sunny->Rainy->Rainy->Rainy->,0.009408)

final triple=(0.033612,Sunny->Rainy->Rainy->Rainy->,0.009408)是以，最終的結果是，朋友那邊這幾天最可能的天氣情況是Sunny->Rainy->Rainy->Rainy，它有0.009408的機率出現。而我們算法的另一個附帶的結論是，我們所觀察到的朋友這幾天的活動序列：Walk->Shop->Clean在我們的隐馬可夫模型之下出現的總機率是0.033612。