機器學習（1）——機率圖模型之隐馬爾科夫模型

1、概念

在機率模型( probabilistic model )中，利用已知變量 “推斷( inference )” 未知變量的條件分布。

假定未知變量為 Y Y Y ，已知變量為 X X X ，其他變量為 R R R，生成式模型考慮聯合分布 P ( Y , R , X ) P(Y,R,X) P(Y,R,X),判别式模型考慮條件分布 P ( Y , R ∣ X ) P(Y,R|X) P(Y,R∣X) 。推斷就是根據 P ( Y , R , X P(Y,R,X P(Y,R,X 或 P ( Y , R ∣ X ) P(Y,R|X) P(Y,R∣X) 得到條件機率分布 P ( Y ∣ X ) P(Y|X) P(Y∣X) 。

機率圖模型( probabilistic graphical model ) 是一類用圖表達變量相關關系的機率模型。一個節點表示一個或一組随機變量，節點之間的邊表示變量間的機率相關關系。根據邊的性質不同，機率圖模型可以分為兩種：第一類使用有向無環圖表示變量之間的依賴關系，稱為有向圖模型或貝葉斯網( Bayesian network )；第二類是使用無向圖表示變量之間的相關關系，成為無向圖模型或馬爾可夫網( Markov network )。

這裡依賴關系是指函數關系，當一個或幾個變量取一定值時，另一個變量有确定值與之對應。當變量X取某個值時，變量Y的取值可能有若幹個，這些數值表現為一定的波動性，但總是圍繞着它們的平均數，并遵循一定的規律變動。變量之間存在的這種不确定的數量關系稱為相關關系。特點：Y與X的值不一一對應；Y與X的關系不能用函數式嚴格表達，但有規律可循。

區分相關關系與函數關系的依據全憑因變量取值的确定性：若因變量的取值是确定的、唯一的，則兩個變量之間的關系稱為函數關系；若因變量的取值是不确定的，則兩個變量之間的關系稱為相關關系。

2、隐馬爾科夫模型

隐馬爾科夫模型（HMM）是結構最簡單的動态貝葉斯網，是一種著名的有向圖模型。

馬爾可夫鍊（Markov chain）：系統下一時刻的狀态僅由目前狀态決定，不依賴于以往的任何狀态。

隐馬爾科夫模型中，狀态變量可分為兩組。第一組為隐藏的狀态變量 y t ∈ { s 1 , s 2 , ⋯   , s N } y_t \in \left\{ s_1,s_2,\cdots,s_N \right\} yt​∈{s1​,s2​,⋯,sN​} ， y t y_t yt​ 表示 t t t 時刻的狀态，共 N N N 個狀态，此狀态變量為未知變量（也稱為隐變量） S S S 。第二組為可觀測的狀态變量， x t = { o 1 , o 2 , ⋯   , o M } x_t = \left\{ o_1,o_2,\cdots,o_M \right\} xt​={o1​,o2​,⋯,oM​} , x t x_t xt​ 表示 t t t 時刻的觀測狀态，此狀态變量為已知變量 O O O 。

2.1、《機器學習》（周志華著）中的例子

觀測值 x t ∈ O x_t \in O xt​∈O 由 y t ∈ S y_t \in S yt​∈S 決定，狀态值 y t y_t yt​ 由 y t − 1 y_{t-1} yt−1​ 決定, t t t 為時刻。箭頭所指方向為狀态可轉變的方向（依賴關系）。

所有變量的聯合機率分布如下：

P ( x 1 , y 1 , ⋯   , x n , y n ) = P ( y 1 ) P ( x 1 ∣ y 1 ) ∏ t = 2 n P ( y t ∣ y t − 1 ) P ( x t ∣ y t ) P(x_1,y_1,\cdots,x_n,y_n) = P(y_1)P(x_1|y_1)\prod_{t=2}^n P(y_t|y_{t-1})P(x_t|y_t) P(x1​,y1​,⋯,xn​,yn​)=P(y1​)P(x1​∣y1​)t=2∏n​P(yt​∣yt−1​)P(xt​∣yt​)

在等式1中， P ( x t ∣ x 1 , y 1 , ⋯   , x t − 1 , y t − 1 , y t ) = P ( x t ∣ y t ) P(x_t|x_1,y_1,\cdots,x_{t-1},y_{t-1},y_t) = P(x_t|y_t) P(xt​∣x1​,y1​,⋯,xt−1​,yt−1​,yt​)=P(xt​∣yt​) , x t x_t xt​ 與其他變量無關，僅與 y t y_t yt​ 有關。這裡涉及馬爾可夫模型的另一個假設，獨立性假設：假設任意時刻的觀測隻依賴于該時刻的馬爾可夫鍊的狀态，與其它觀測狀态無關。欲求 x t x_t xt​ ,隻能先求與其相關的 y t y_t yt​ 。

P ( x t ∣ y 1 , ⋯   , y t , x 1 , ⋯   , x t − 1 ) = P ( x t ∣ y t ) P(x_t|y_1,\cdots,y_t,x_1,\cdots,x_{t-1}) = P(x_t|y_t) P(xt​∣y1​,⋯,yt​,x1​,⋯,xt−1​)=P(xt​∣yt​)

是以可以将 ( x t , y t ) (x_t,y_t) (xt​,yt​) 看作一組變量 s t s_t st​，其聯合機率分布為 P ( s t ) = P ( y t ∣ y t − 1 ) P ( x t ∣ y t ) P(s_t) = P(y_t|y_{t-1})P(x_t|y_t) P(st​)=P(yt​∣yt−1​)P(xt​∣yt​) 。

所有 s s s 變量的聯合機率分布如下：

P ( s 1 , s 2 , ⋯   , s t , s n ) = P ( s 1 ) ∏ t = 2 n P ( s t ) P(s_1,s_2,\cdots,s_t,s_n) = P(s_1)\prod_{t=2}^n P(s_t) P(s1​,s2​,⋯,st​,sn​)=P(s1​)t=2∏n​P(st​)

2.2、更為一般的HMM模型

隐藏的狀态變量 S = { s 1 , s 2 } y t ∈ S S = \left\{ s_1,s_2 \right\} \quad y_t \in S S={s1​,s2​}yt​∈S ，可觀測的狀态變量 O = { o 1 , o 2 , o 3 } x t ∈ O O = \left\{ o_1,o_2,o_3 \right\}\quad x_t \in O O={o1​,o2​,o3​}xt​∈O ,箭頭所指方向為狀态可轉變的方向（依賴關系）。

觀測值 x t x_t xt​ 由 y t y_t yt​ 決定，狀态值 y t y_t yt​ 僅由 y t − 1 y_{t-1} yt−1​ 決定（這裡再強調一遍）。

馬爾可夫機率公式如下：

P ( s 1 , s 2 , ⋯   , s n ) = P ( s 1 , s 2 , ⋯   , s n − 1 ) P ( s n ∣ s 1 , s 2 , ⋯   , s n − 1 ) P(s_1,s_2,\cdots,s_n) = P(s_1,s_2,\cdots,s_{n-1})P(s_n|s_1,s_2,\cdots,s_{n-1}) P(s1​,s2​,⋯,sn​)=P(s1​,s2​,⋯,sn−1​)P(sn​∣s1​,s2​,⋯,sn−1​)

此處的 s s s 與等式3中的 s s s 不同，僅将其當作一個狀态變量，包含隐藏狀态變量和觀測狀态變量。等式3求所有變量的聯合機率分布，即所有變量狀态同時存在的機率。等式4求某一狀态基于其他狀态存在的機率，這一狀态可以是隐藏狀态，也可以是觀測狀态。等式3、4本質相同。

若可觀測狀态序列為 { o 1 , o 2 , o 3 } \left\{ o_1, o_2, o_3 \right\} {o1​,o2​,o3​} ,其 P ( O ) P(O) P(O) 機率為：

t = 1 t=1 t=1 時，觀測狀态為 x 1 = o 1 x_1=o_1 x1​=o1​ 的機率：

P ( o 1 , y 1 ) = P ( y 1 ) P ( o 1 ∣ y 1 ) P(o_1,y_1) = P(y_1)P(o_1|y_1) P(o1​,y1​)=P(y1​)P(o1​∣y1​)

如果 y 1 = s 1 y_1=s_1 y1​=s1​：

P ( o 1 , s 1 ) = p ( s 1 ) P ( o 1 ∣ s 1 ) P(o_1,s_1) = p(s_1)P(o_1|s_1) \\ P(o1​,s1​)=p(s1​)P(o1​∣s1​)

如果 y 1 = s 2 y_1=s_2 y1​=s2​：

P ( o 1 , s 2 ) = p ( s 2 ) P ( o 1 ∣ s 2 ) P(o_1,s_2) = p(s_2)P(o_1|s_2) P(o1​,s2​)=p(s2​)P(o1​∣s2​)

t = 2 t=2 t=2 時，觀測狀态為 x 2 = o 2 x_2=o_2 x2​=o2​ 的機率：

P ( o 1 , o 2 , y 2 ) = P ( o 1 , o 2 , y 1 , y 2 ) = P ( o 1 , y 1 ) P ( y 2 ∣ y 1 ) P ( o 2 ∣ y 2 ) \begin{aligned} P(o_1,o_2,y_2) & = P(o_1,o_2,y_1,y_2) \\ & = P(o_1,y_1)P(y_2|y_1)P(o_2|y_2) \end{aligned} P(o1​,o2​,y2​)​=P(o1​,o2​,y1​,y2​)=P(o1​,y1​)P(y2​∣y1​)P(o2​∣y2​)​

如果 y 2 = s 1 y_2=s_1 y2​=s1​：

P ( o 1 , o 2 , s 1 ) = P ( o 1 , s 1 ) P ( s 1 ∣ s 1 ) P ( o 2 ∣ s 1 ) + P ( o 1 , s 2 ) P ( s 1 ∣ s 2 ) P ( o 2 ∣ s 1 ) P(o_1,o_2,s_1) = P(o_1,s_1)P(s_1|s_1)P(o_2|s_1) + P(o_1,s_2)P(s_1|s_2)P(o_2|s_1) P(o1​,o2​,s1​)=P(o1​,s1​)P(s1​∣s1​)P(o2​∣s1​)+P(o1​,s2​)P(s1​∣s2​)P(o2​∣s1​)

如果 y 2 = s 2 y_2 = s_2 y2​=s2​ ：

P ( o 1 , o 2 , s 2 ) = P ( o 1 , s 1 ) P ( s 2 ∣ s 1 ) P ( o 2 ∣ s 2 ) + P ( o 1 , s 2 ) P ( s 2 ∣ s 2 ) P ( o 2 ∣ s 2 ) P(o_1,o_2,s_2) = P(o_1,s_1)P(s_2|s_1)P(o_2|s_2) + P(o_1,s_2)P(s_2|s_2)P(o_2|s_2) P(o1​,o2​,s2​)=P(o1​,s1​)P(s2​∣s1​)P(o2​∣s2​)+P(o1​,s2​)P(s2​∣s2​)P(o2​∣s2​)

t = 3 t=3 t=3 時，觀測狀态為 x 3 = o 3 x_3=o_3 x3​=o3​ 的機率：

P ( o 1 , o 2 , o 3 , y 3 ) = P ( o 1 , o 2 , o 3 , y 1 , y 2 , y 3 ) = P ( o 1 , o 2 , y 1 , y 2 ) P ( y 3 ∣ y 2 ) P ( o 3 ∣ y 3 ) \begin{aligned} P(o_1,o_2,o_3,y_3) & = P(o_1,o_2,o_3,y_1,y_2,y_3)\\ & = P(o_1,o_2,y_1,y_2)P(y_3|y_2)P(o_3|y_3) \end{aligned} P(o1​,o2​,o3​,y3​)​=P(o1​,o2​,o3​,y1​,y2​,y3​)=P(o1​,o2​,y1​,y2​)P(y3​∣y2​)P(o3​∣y3​)​

如果 y 3 = s 1 y_3=s_1 y3​=s1​：

P ( o 1 , o 2 , o 3 , s 1 ) = P ( o 1 , o 2 , y 2 ) P ( s 1 ∣ s 1 ) P ( o 3 ∣ s 1 ) + P ( o 1 , o 2 , y 2 ) P ( s 1 ∣ s 2 ) P ( o 3 ∣ s 1 ) P(o_1,o_2,o_3,s_1) = P(o_1,o_2,y_2)P(s_1|s_1)P(o_3|s_1) + P(o_1,o_2,y_2)P(s_1|s_2)P(o_3|s_1) P(o1​,o2​,o3​,s1​)=P(o1​,o2​,y2​)P(s1​∣s1​)P(o3​∣s1​)+P(o1​,o2​,y2​)P(s1​∣s2​)P(o3​∣s1​)

如果 y 3 = s 2 y_3=s_2 y3​=s2​：

P ( o 1 , o 2 , o 3 , s 2 ) = P ( o 1 , o 2 , y 2 ) P ( s 2 ∣ s 1 ) P ( o 3 ∣ s 2 ) + P ( o 1 , o 2 , y 2 ) P ( s 2 ∣ s 2 ) P ( o 3 ∣ s 2 ) P(o_1,o_2,o_3,s_2) = P(o_1,o_2,y_2)P(s_2|s_1)P(o_3|s_2) + P(o_1,o_2,y_2)P(s_2|s_2)P(o_3|s_2) P(o1​,o2​,o3​,s2​)=P(o1​,o2​,y2​)P(s2​∣s1​)P(o3​∣s2​)+P(o1​,o2​,y2​)P(s2​∣s2​)P(o3​∣s2​)

等式16中 P ( o 1 , o 2 , y 2 ) P(o_1,o_2,y_2) P(o1​,o2​,y2​) 為 t = 2 t=2 t=2 時的機率，如等式9 。

綜上：

P ( o 1 , o 2 , o 3 ) = P ( o 1 , o 2 , o 3 , s 1 ) + P ( o 1 , o 2 , o 3 , s 2 ) P(o_1,o_2,o_3) = P(o_1,o_2,o_3,s_1) + P(o_1,o_2,o_3,s_2) P(o1​,o2​,o3​)=P(o1​,o2​,o3​,s1​)+P(o1​,o2​,o3​,s2​)

2.3、參數

一個隐馬爾科夫模型包含三個參數 λ = { A , B , Π } \lambda = \left\{ A,B,\Pi \right\} λ={A,B,Π} ,或将 λ \lambda λ 表示為 R R R。

狀态轉移機率矩陣 A = [ a i j ] N × N A = [a_{ij}]_{N \times N} A=[aij​]N×N​ ，表示模型在各個狀态中轉移的機率。

a i j = P ( y t + 1 = s j ∣ y t = s i ) 1 ≤ i , j ≤ N a_{ij} = P(y_{t+1}=s_j | y_t = s_i) \quad 1 \leq i, j \leq N aij​=P(yt+1​=sj​∣yt​=si​)1≤i,j≤N

表示在任意時刻 t t t ，若狀态為 s i s_i si​ ，則下一時刻狀态為 s j s_j sj​ 的機率。

在2.2中的例子， N = 2 N=2 N=2

A = [ 0.1 0.9 0.8 0.2 ] A = \begin{bmatrix} 0.1 & 0.9 \\ 0.8 & 0.2\\ \end{bmatrix} A=[0.10.8​0.90.2​]

行向量表示 t t t 時刻，縱向量表示 t + 1 t+1 t+1 時刻。橫向量累加和為 1 1 1 。

此矩陣表示隐藏狀态，也就是 S S S 之間專業的機率。

輸出觀測機率矩陣 B = [ b i j ] N × M B = [b_{ij}]_{N \times M} B=[bij​]N×M​ ，表示模型根據目前狀态獲得各個觀測值的機率。

b i j = P ( x t = o j ∣ y t = s i ) 1 ≤ i ≤ N , 1 ≤ j ≤ M b_{ij} = P(x_{t}=o_j | y_t = s_i) \quad 1 \leq i\leq N,1\leq j \leq M bij​=P(xt​=oj​∣yt​=si​)1≤i≤N,1≤j≤M

表示在任意時刻 t t t ，若狀态為 s i s_i si​ ，則觀測值 o j o_j oj​ 的機率。

在2.2中的例子， N = 2 ， M = 3 N=2 ，M = 3 N=2，M=3

B = [ 0.7 0.1 0.2 0.3 0.5 0.2 ] B = \begin{bmatrix} 0.7 & 0.1 & 0.2 \\ 0.3 & 0.5 & 0.2\\ \end{bmatrix} B=[0.70.3​0.10.5​0.20.2​]

行向量表示隐藏狀态，縱向量表示觀測狀态。橫向量累加和為 1 1 1 。

初始狀态機率矩陣 π = ( π 1 , π 2 , ⋯   , π n ) \pi = (\pi_1 ,\pi_2,\cdots,\pi_n) π=(π1​,π2​,⋯,πn​) ，模型在初始時刻隐藏狀态出現的機率。

π i = P ( y 1 = s i ) 1 ≤ i ≤ N \pi_i = P(y_1 = s_i) \quad 1 \leq i \leq N πi​=P(y1​=si​)1≤i≤N

表示模型的初始狀态為 s i s_i si​ 的機率。

在2.2中的例子， N = 2 N=2 N=2

Π = [ 0.3 0.9 ] Π = [ 0.3 0.7 ] \Pi = \begin{bmatrix} 0.3 & 0.9 \\ \end{bmatrix}\Pi = \begin{bmatrix} 0.3 & 0.7 \\ \end{bmatrix} Π=[0.3​0.9​]Π=[0.3​0.7​]

3、參考

隐馬爾可夫模型（一）

周志華《機器學習》