機率圖模型1：隐馬爾科夫(1)

作者：相國大人

• 機率圖模型系列博文目錄實時更新點此處
• 導讀
  • 隐馬爾科夫模型
    • 兩個基本假設
  • 基本定義
    • 隐馬爾科夫模型的3個基本問題
    • 機率計算問題
      • 前向算法
      • 後向算法

寫這篇博文用了很多時間和精力，如果這篇博文對你有幫助，希望您可以打賞給部落客相國大人。哪怕隻捐1毛錢，也是一種心意。通過這樣的方式，也可以培養整個行業的知識産權意識。我可以和您建立更多的聯系，并且在相關領域提供給您更多的資料和技術支援。

賞金将用于拉薩兒童圖書公益募捐

手機掃一掃，即可：

附：《春天裡，我們的拉薩兒童圖書館，需要大家的幫助》

機率圖模型系列博文目錄（實時更新,點此處）

1. 導讀

參考文獻

• 《機器學習鄭捷》第11章
• 機器學習周志華 14章
• 《統計學系方法》第10章
• 《機率圖模型》第3章貝葉斯網表示和馬爾科夫
• 《駕馭文本》

隐馬爾科夫模型

兩個基本假設：

1. 齊次馬爾科夫性假設：隐藏的馬爾科夫鍊在任意時刻 t 的狀态隻依賴于前一時刻的狀态，與其他時刻的狀态及觀測無關，也與時刻t無關。
2. 觀測獨立性假設：任意時刻的觀測隻依賴于該時刻的馬爾科夫鍊的狀态，與其他觀測及狀态無關。

說人話，就下面這個圖，其中箭頭和連邊表示機率依賴。

從這個圖中，我們可以很輕松的對後面的一些公式做推導。比如：

(ot+1|o1:t,It+1=qi)=(ot+1|It+1=qi)(1.1)

上面的公式為了書寫簡便，我們省略掉了機率符号 P （下同），并且用o1:t表示 (o1,⋯,ot) (下同)。

(It+1=qi|o1:t,It=qj)=(It+1=qi|It=qj)(1.2)

(ot+1:T|It+1=qi,It=qi)=(ot+1:T|It+1=qi)(1.3)

(ot+2:T|It+1=qj,ot+1)=(ot+2:T|It+1=qj)(1.4)

(It+1|o1:t,It)=(It+1|It)(1.5)

(ot+1|It+1,o1:t,It)=(ot+1|It+1)(1.6)

基本定義：

轉移機率 aij=(It+1=qj|It=qi)

觀測機率 bj(ot)=(ot|It=qj)

初始狀态機率 πi=P(I1=qi)

隐馬爾科夫模型的3個基本問題

1. 機率計算
2. 學習問題
3. 預測問題/解碼問題

機率計算問題

前向算法

前向機率 αt(i)=(o1:t,It=qi)

轉移機率 aij=(It+1=qj|It=qi)

觀測機率 bj(ot)=(ot|It=qj)

初始狀态機率 πi=P(I1=qi)

初始前向機率：

α1(i)=(o1,I1=qi)=(I1=qi)(o1|I1=qi)=πibi(o1)(1.8)

前向機率的疊代推導：

αt+1(i)=(o1:t+1,It+1=qi)=(o1:t,It+1=qi)(ot+1|o1:t,It+1=qi)=(o1:t,It+1=qi)(ot+1|It+1=qi)(由公式(1.1)得來)=(o1:t,It+1=qi)bi(ot+1)=⎛⎝∑j(o1:t,It=qj,It+1=qi)⎞⎠bi(ot+1)=⎛⎝∑j(o1:t,It=qj)(It+1=qi|o1:t,It=qj)⎞⎠bi(ot+1)=⎛⎝∑j(o1:t,It=qj)(It+1=qi|It=qj)⎞⎠bi(ot+1)(由公式(1.2)得來)=⎛⎝∑jαt(j)aji⎞⎠bi(ot+1)(1.9)

終止狀态推導：

P(O|λ)=(o1:T|λ)=∑iN(o1:t,IT=qi)=∑iNαT(i)(1.10)

算法1.1(觀測序列機率的前向算法)

輸入：隐馬爾科夫模型 λ ，觀測序列 O ；

輸出：觀測序列機率P(O|λ)。

1. 根據公式 (1.8) ，設定初值。
2. 根據公式 (1.9) 遞推。其中 t=1,2,⋯,T−1 。
3. 終止。根據公式 (1.10) 得到輸出。

python實作（李航《統計學習方法》177頁例題10.2）：

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
"""
@author: XiangguoSun
@contact: [email protected]
@file: forward_prob.py
@time: 2017/3/13 8:53
@software: PyCharm
"""
import numpy as np


def forward_prob(model, Observe, States):
    '''
    馬爾科夫前向算法
    '''

    A, B, pi = model
    N = States.size
    T = Observe.size

    alpha = pi*B[:, Observe[]]
    print "（1）計算初值alpha_1(i):   ",alpha

    print "(2) 遞推..."
    for t in xrange(, T-):
        print "t=", t+,"   alpha_",t+,"(i):",alpha
        alpha = alpha.dot(A)*B[:, Observe[t+]]

    print "(3)終止。alpha_",T,"(i):    ", alpha
    print "輸出Prob:  ",alpha.sum()
    return alpha.sum()


if __name__ == '__main__':
    A = np.array([[, , ],
                  [, , ],
                  [, , ]])

    B = np.array([[, ],
                  [, ],
                  [, ]])

    pi = np.array([, , ])

    model = (A, B, pi)

    Observe = np.array([, , ])

    States = np.array([, , ])

    forward_prob(model,Observe,States)
           

後向算法

後向機率： βt(i)=(ot+1:T|It=qi)

初始後向機率： βT(i)=1,i=1,2,⋯,N

後向機率疊代推導：

βt(i)=(ot+1:T|It=qi)=∑jN(ot+1:T,It+1=qj|It=qi)=∑jN(It+1=qj|It=qi)(ot+1:T|It+1=qj,It=qi)=∑jN(It+1=qj|It=qi)(ot+1:T|It+1=qj)(由公式(1.3)得到)=∑jN(It+1=qj|It=qi)(ot+1|It+1=qj)(ot+2:T|It+1=qj，ot+1)=∑jNaijbj(ot+1)βt+1(j)(1.11)

終止狀态推導：

P(O|λ)=(o1:T|λ)=∑i=1N(o1:T,I1=qi)=∑i=1N(I1=qi)(o1:T|I1=qi)=∑i=1N(I1=qi)(o1|I1=qi)(o2:T|o1,I1=qi)=∑i=1Nπibi(oi)(o2:T|I1=qi)=∑i=1Nπibi(oi)β1(i)(1.12)

算法1.2(觀測序列機率的後向算法)

輸入：隐馬爾科夫模型 λ ，觀測序列 O ；

輸出：觀測序列機率P(O|λ)。

1. 設定後向機率初值為1。
2. 根據公式 (1.11) 遞推。其中 t=T−1,T−2,⋯,1 。
3. 終止。根據公式 (1.12) 得到輸出。

python實作（李航《統計學習方法》177頁例題10.2）：

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
"""
@author: XiangguoSun
@contact: [email protected]
@file: markov.py
@time: 2017/3/13 8:53
@software: PyCharm
"""
import numpy as np


def forward_prob(model, Observe, States):
    '''
    馬爾科夫前向算法
    '''

    A, B, pi = model
    N = States.size
    T = Observe.size

    alpha = pi*B[:, Observe[]]
    print "（1）計算初值alpha_1(i):   ",alpha

    print "(2) 遞推..."
    for t in xrange(, T-):
        alpha = alpha.dot(A)*B[:, Observe[t+]]
        print "t=", t + , "   alpha_", t + , "(i):", alpha

    print "(3)終止。alpha_",T,"(i):    ", alpha
    print "輸出Prob:  ",alpha.sum()
    return alpha.sum()


def backward_prob(model,Observe,States):
    '''
      馬爾科夫後向算法
      '''

    A, B, pi = model
    N = States.size
    T = Observe.size

    beta = np.ones((N,))  # beta_T
    print "（1）計算初值beta_",T,"(i):   ", beta

    print "(2) 遞推..."
    for t in xrange(T - , -, -):  # t=T-2,...,0
        beta = A.dot(B[:, Observe[t + ]] * beta)
        print "t=", t + , "   beta_", t + , "(i):", beta

    print "(3)終止。alpha_", , "(i):    ", beta
    prob = pi.dot(beta * B[:, Observe[]])
    print "輸出Prob:  ", prob
    return prob


if __name__ == '__main__':


    A = np.array([[, , ],
                  [, , ],
                  [, , ]])

    B = np.array([[, ],
                  [, ],
                  [, ]])

    pi = np.array([, , ])

    model = (A, B, pi)

    Observe = np.array([, , ])

    States = np.array([, , ])

    forward_prob(model,Observe,States)

    backward_prob(model, Observe, States)
           

實驗結果：