文章目錄
- Hidden Markov Model(HMM)介紹
-
- 例子：丢硬币
- 例子：Part of Speech Tagging(POS)
- Parameters of HMM
- 問題1
-
- Naive Approach
- Viterbi
- 問題2：Forward/Backward Algorithm
-
- Forward Algorithm
- Backward Algorithm
- FB算法估計參數π
- FB估計參數B
- 估計A
- Complete vs Incomplete Case
-
- Complete Case示例
- MLE for Complete and Incomplete Case
- EM推導
-
- EM小結
- K-means
- MLE for GMM
- HMM vs RNN
公式輸入請參考： Hidden Markov Model(HMM)介紹
綠色是觀測值，灰色是隐變量（隐狀态），每列是一個時間步，第一行是狀态鍊，狀态鍊是有向的。
HMM既可以看做判别模型，也可以看做生成模型。
例子：丢硬币
不能免俗，講下丢硬币的例子，現在有兩個硬币A和B，它們出現正面的機率分别是 μ 1 , μ 2 \mu_1,\mu_2 μ1,μ2（重量不均勻，是以機率不是0.5）
現在有一個叫小明的人丢硬币，而我隻能看到丢的結果，不知道丢的是A還是B。
針對這個描述，我們現在有幾個問題：
問題1（inference/decody問題）：通過觀測到的正反面，小明丢硬币的序列是什麼？
問題2（parameter estimate問題）： μ 1 , μ 2 \mu_1,\mu_2 μ1,μ2分别是什麼？也就是丢了A後，丢A的機率是多少？丢B的機率是多少？丢了B後，丢A的機率是多少？丢B的機率是多少？
表示起來就是一個矩陣（transition matrix）
問題三：如果計算某個觀測序列出現的邊界機率？例如：P(正反正正反)（通常是用DP來解決）
例子：Part of Speech Tagging(POS)
灰色的隐變量是詞性，綠色的觀測值是單詞。
問題一：給定句子，反推每個單詞的詞性（屬于inference/decoding問題）
問題一：維特比解決
問題二：參數估計。給定給定詞性，生成某個單詞的機率的過程叫emission probability（矩陣大小為詞性×單詞量），從某個詞性轉化為另外一個詞性的機率叫transition probability（矩陣大小為詞性×詞性）。
問題二：EM解決
問題三：求某個單詞序列 p ( w 1 w 2 ⋯ w n ) p(w_1w_2\cdots w_n) p(w1w2⋯wn)出現的邊緣機率
問題三：DP解決
Parameters of HMM
隐變量 z i z_i zi是離散型的，也就是它的隐狀态是有限的，例如丢硬币的例子中隐狀态是A或B，在語義分析中的隐狀态詞性也是有限的。假設其隐狀态有m個(m: # of states)
觀測變量 x i x_i xi可以是離散的（例如抛硬币），也可以是連續的（例如語音識别中的語音信号）。
HMM的參數 θ = ( A , B , π ) \theta=(A,B,\pi) θ=(A,B,π)，每一個參數如下：
A A A為轉移矩陣transition probability/matrix， A i j A_{ij} Aij是狀态 z i z_i zi到下一個時态轉化為 z j z_j zj的機率，矩陣大小是m×m。
B B B是emission probability/matrix，就是生成機率矩陣，就在狀态 z i z_i zi的情況下，生成觀測變量 x i x_i xi的機率，例如丢硬币的例子中，當用硬币A有2/3的幾率是正面，1/3的幾率是反面。矩陣大小是m×V，V為觀測變量的取值類型（連續型用GMM來處理）
π = [ π 1 , π 2 , . . . , π m ] , π 1 + π 2 + . . . + π m = 1 \pi=[\pi_1,\pi_2,...,\pi_m],\pi_1+\pi_2+...+\pi_m=1 π=[π1,π2,...,πm],π1+π2+...+πm=1，這裡是每個隐變量出現在第一個位置的機率。
問題1：給定 θ , x \theta,x θ,x估計 z z z（屬于inference/decoding問題）
問題2： 估計 θ \theta θ
2.1給定 x , z x, z x,z屬于complete case，可以用最大似然來解
2.2
給定 x x x屬于incomplete case，可以用EM來解
問題1
Naive Approach
最笨的方法，适合用于隐變量狀态較少的情況，把所有可能生出觀察變量的排列組合全部列舉出來，然後計算似然機率，取最大值。
三個可能性，序列長度是10，那麼可能性就是 3 10 3^{10} 310
Viterbi
使用維特比算法的一個前提是，某個狀态隻和它前後的狀态有關，與其他狀态無關。
上圖的 z i z_i zi是隐變量， 1 ∼ m 1\sim m 1∼m是隐變量可以的取值狀态，我們是想通過已知條件 θ , x \theta,x θ,x來估計 z i z_i zi
通俗的說就是 z 1 z_1 z1取 1 ∼ m 1\sim m 1∼m的某一個狀态， z 2 z_2 z2取 1 ∼ m 1\sim m 1∼m的某一個狀态，。。。
連起來就是上面的折線。
z 1 z_1 z1取2的機率 p ( z 1 = 2 ) p(z_1=2) p(z1=2)是參數 π \pi π決定的，另外還有一個因素要從 z 1 = 2 z_1=2 z1=2的狀态生成觀測變量 x 1 x_1 x1，是以數學表達就是： p ( z 1 = 2 ) p ( x 1 ∣ z 1 = 2 ) p(z_1=2)p(x_1|z_1=2) p(z1=2)p(x1∣z1=2)
對于 z 2 z_2 z2來說，它要在 z 1 = 2 z_1=2 z1=2條件下進行計算：
p ( z 2 = 1 ∣ z 1 = 2 ) p ( x 2 ∣ z 2 = 1 ) p(z_2=1|z_1=2)p(x_2|z_2=1) p(z2=1∣z1=2)p(x2∣z2=1)
以此類推，那麼整根折線的機率就是把上面的機率連乘：
p ( z 1 = 2 ) p ( x 1 ∣ z 1 = 2 ) p ( z 2 = 1 ∣ z 1 = 2 ) p ( x 2 ∣ z 2 = 1 ) . . . p(z_1=2)p(x_1|z_1=2)p(z_2=1|z_1=2)p(x_2|z_2=1)... p(z1=2)p(x1∣z1=2)p(z2=1∣z1=2)p(x2∣z2=1)...
機率越高越好。但是可以看到這個折線的組合是有很多種的，接下來看如何用DP來簡化。
假設第 k k k時刻，最好的機率（最優路徑）是 δ k ( i ) \delta_k(i) δk(i)，這個狀态取值是 i i i
那麼第 k + 1 k+1 k+1時刻，最好的路徑是前一個狀态乘上第 k + 1 k+1 k+1時刻的機率，這裡我們用log來把連乘轉換為連加，由于上一個狀态的取值可能是1~i，是以我們要取一個最大值：
δ k + 1 ( j ) = max { δ k ( 1 ) + log p ( z k + 1 = j ∣ z k = 1 ) + log p ( x k + 1 ∣ z k + 1 = j ) δ k ( 2 ) + log p ( z k + 1 = j ∣ z k = 2 ) + log p ( x k + 1 ∣ z k + 1 = j ) ⋮ δ k ( m ) + log p ( z k + 1 = j ∣ z k = m ) + log p ( x k + 1 ∣ z k + 1 = j ) \delta_{k+1}(j)=\max\begin{cases} &\delta_k(1)+\log p(z_{k+1}=j|z_k=1) +\log p(x_{k+1}|z_{k+1}=j)\\ & \delta_k(2)+\log p(z_{k+1}=j|z_k=2) +\log p(x_{k+1}|z_{k+1}=j) \\ &\vdots\\ & \delta_k(m)+\log p(z_{k+1}=j|z_k=m) +\log p(x_{k+1}|z_{k+1}=j) \end{cases} δk+1(j)=max⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧δk(1)+logp(zk+1=j∣zk=1)+logp(xk+1∣zk+1=j)δk(2)+logp(zk+1=j∣zk=2)+logp(xk+1∣zk+1=j)⋮δk(m)+logp(zk+1=j∣zk=m)+logp(xk+1∣zk+1=j)
上式可以簡化為：
δ k + 1 ( j ) = max i [ δ k ( i ) + log p ( z k + 1 = j ∣ z k = i ) + log p ( x k + 1 ∣ z k + 1 = j ] \delta_{k+1}(j)=\underset{i}{\max}[\delta_k(i)+\log p(z_{k+1}=j|z_k=i)+\log p(x_{k+1}|z_{k+1}=j] δk+1(j)=imax[δk(i)+logp(zk+1=j∣zk=i)+logp(xk+1∣zk+1=j]
可以看到，每次計算都可以确定出前一個時刻到目前時刻的最佳路徑，這樣從第一個時刻開始一次向後計算，并把路徑結果儲存下來就可以求出第k個時刻的最佳路徑。
問題2：Forward/Backward Algorithm
這個算法是用來估計： p ( z k ∣ x ) p(z_k|x) p(zk∣x)，這個機率可以拆分為：
Forward Algorithm：計算聯合機率： p ( z k , x 1 : k ) p(z_k,x_{1:k}) p(zk,x1:k)
Backward Algorithm：計算條件機率： p ( x ( k + 1 ) : n ∣ z k ) p(x_{(k+1):n}|z_k) p(x(k+1):n∣zk)
為什麼能這樣拆分？
p ( z k ∣ x ) = p ( z k , x ) p ( x ) ∝ p ( z k , x ) 前 面 是 貝 葉 斯 公 式 ， 後 面 是 因 為 p ( x ) 對 于 隐 變 量 而 言 是 常 數 ， 因 此 可 以 正 比 于 後 面 一 項 p(z_k|x)=\cfrac{p(z_k,x)}{p(x)}\propto p(z_k,x)\\前面是貝葉斯公式，後面是因為p(x)對于隐變量而言是常數，是以可以正比于後面一項 p(zk∣x)=p(x)p(zk,x)∝p(zk,x)前面是貝葉斯公式，後面是因為p(x)對于隐變量而言是常數，是以可以正比于後面一項
下面這個怎麼來的？不太清楚。。。。
p ( z k , x ) = p ( x ( k + 1 ) : n ∣ z k , x 1 : k ) B a c k w a r d A l g o r i t h m p ( z k , x 1 : k ) F o r w a r d A l g o r i t h m p(z_k,x)=\underset{Backward\space Algorithm}{p(x_{(k+1):n}|z_k,x_{1:k})}\underset{Forward\space Algorithm}{p(z_k,x_{1:k})} p(zk,x)=Backward Algorithmp(x(k+1):n∣zk,x1:k)Forward Algorithmp(zk,x1:k)
由于 x 1 : k x_{1:k} x1:k和 x ( k + 1 ) : n x_{(k+1):n} x(k+1):n都是條件獨立于 z k z_k zk的（就是 x 1 : k x_{1:k} x1:k的資訊是包含在 z k z_k zk裡面了），根據D-seperate定理， x 1 : k x_{1:k} x1:k可以去掉：
p ( z k , x ) = p ( x ( k + 1 ) : n ∣ z k ) p ( z k , x 1 : k ) p(z_k,x)=p(x_{(k+1):n}|z_k)p(z_k,x_{1:k}) p(zk,x)=p(x(k+1):n∣zk)p(zk,x1:k)
可以看到，前面一項是Backward Algorithm，後面一項是Forward Algorithm
但是由于 p ( z k , x ) p(z_k,x) p(zk,x)與 p ( z k ∣ x ) p(z_k|x) p(zk∣x)不是相等，而是正比關系而已，是以在計算的時候要用歸一化處理一下，例如：
p ( z 1 ∣ x ) = p ( z 1 , x ) ∑ j p ( z k = j , x ) p(z_1|x)=\cfrac{p(z_1,x)}{\sum_{j}p(z_k=j,x)} p(z1∣x)=∑jp(zk=j,x)p(z1,x)
Forward Algorithm
算法目标是求： p ( z k , x 1 : k ) p(z_k,x_{1:k}) p(zk,x1:k)，記作： α k ( z k ) \alpha_k(z_k) αk(zk)
也是利用動态規劃的思想來解決這個問題：
p ( z k , x 1 : k ) = ∑ z k − 1 p ( z k − 1 , z k , x 1 : k ) p(z_k,x_{1:k})=\sum_{z_{k-1}}p(z_{k-1},z_k,x_{1:k}) p(zk,x1:k)=zk−1∑p(zk−1,zk,x1:k)
上式是把 z k − 1 z_{k-1} zk−1邊緣化（這裡沒怎麼看懂，應該是利用邊緣化加入了一項 z k − 1 z_{k-1} zk−1，構造出DP的子問題），然後繼續構造 x 1 : k − 1 x_{1:k-1} x1:k−1，這裡用的是條件機率公式反推，上式等于：
= ∑ z k − 1 p ( z k − 1 , x 1 : k − 1 ) ⋅ p ( z k ∣ z k − 1 , x 1 : k − 1 ) ⋅ p ( x k ∣ z k , z k − 1 , x 1 : k − 1 ) (1) =\sum_{z_{k-1}}p(z_{k-1},x_{1:k-1})\cdot p(z_k|z_{k-1},x_{1:k-1})\cdot p(x_k|z_k,z_{k-1},x_{1:k-1})\tag1 =zk−1∑p(zk−1,x1:k−1)⋅p(zk∣zk−1,x1:k−1)⋅p(xk∣zk,zk−1,x1:k−1)(1)
可以看到公式1中： p ( z k ∣ z k − 1 , x 1 : k − 1 ) p(z_k|z_{k-1},x_{1:k-1}) p(zk∣zk−1,x1:k−1)和狀态轉移機率 p ( z k ∣ z k − 1 ) p(z_k|z_{k-1}) p(zk∣zk−1)很像，如下圖所示，其實 x 1 : k − 1 x_{1:k-1} x1:k−1的資訊都包含在了 z k − 1 z_{k-1} zk−1裡面（或者說 x 1 : k − 1 x_{1:k-1} x1:k−1和 z k z_k zk條件獨立于 z k − 1 z_{k-1} zk−1），是以：
p ( z k ∣ z k − 1 , x 1 : k − 1 ) = p ( z k ∣ z k − 1 ) p(z_k|z_{k-1},x_{1:k-1})=p(z_k|z_{k-1}) p(zk∣zk−1,x1:k−1)=p(zk∣zk−1)
同理，可以看到公式1中： p ( x k ∣ z k , z k − 1 , x 1 : k − 1 ) p(x_k|z_k,z_{k-1},x_{1:k-1}) p(xk∣zk,zk−1,x1:k−1)和生成機率 p ( x k ∣ z k ) p(x_k|z_k) p(xk∣zk)很像，如上圖所示，其實 z k − 1 , x 1 : k − 1 z_{k-1},x_{1:k-1} zk−1,x1:k−1的資訊都包含在了 z k z_k zk裡面，是以：
p ( x k ∣ z k , z k − 1 , x 1 : k − 1 ) = p ( x k ∣ z k ) p(x_k|z_k,z_{k-1},x_{1:k-1})=p(x_k|z_k) p(xk∣zk,zk−1,x1:k−1)=p(xk∣zk)
到了這裡，前向算法可以寫成：
p ( z k , x 1 : k ) = ∑ z k − 1 p ( z k − 1 , x 1 : k − 1 ) p ( z k ∣ z k − 1 ) p ( x k ∣ z k ) p(z_k,x_{1:k})=\sum_{z_{k-1}}p(z_{k-1},x_{1:k-1})p(z_k|z_{k-1})p(x_k|z_k) p(zk,x1:k)=zk−1∑p(zk−1,x1:k−1)p(zk∣zk−1)p(xk∣zk)
用DP的思想寫出來：
α k ( z k ) = ∑ z k − 1 α k − 1 ( z k − 1 ) p ( z k ∣ z k − 1 ) p ( x k ∣ z k ) \alpha_k(z_k)=\sum_{z_{k-1}}\alpha_{k-1}(z_{k-1})p(z_k|z_{k-1})p(x_k|z_k) αk(zk)=zk−1∑αk−1(zk−1)p(zk∣zk−1)p(xk∣zk)
以上就是DP的推導，然後初始條件：
α 1 ( z 1 ) = p ( z 1 , x 1 ) = p ( z 1 ) p ( x 1 ∣ z 1 ) \alpha_1(z_1)=p(z_1,x_1)=p(z_1)p(x_1|z_1) α1(z1)=p(z1,x1)=p(z1)p(x1∣z1)
Backward Algorithm
算法目标是求： p ( x ( k + 1 ) : n ∣ z k ) p(x_{(k+1):n}|z_k) p(x(k+1):n∣zk)，記作： β k ( z k ) \beta_k(z_k) βk(zk)
也是利用動态規劃的思想來解決這個問題：
和上面類似，先用邊緣機率加上一項 z k + 1 z_{k+1} zk+1
p ( x ( k + 1 ) : n ∣ z k ) = ∑ z k + 1 p ( x ( k + 1 ) : n , z k + 1 ∣ z k ) p(x_{(k+1):n}|z_k)=\sum_{z_{k+1}}p(x_{(k+1):n},z_{k+1}|z_k) p(x(k+1):n∣zk)=zk+1∑p(x(k+1):n,zk+1∣zk)
然後利用條件機率公式反推：
= ∑ z k + 1 p ( x ( k + 2 ) : n ∣ z k + 1 , z k , x k + 1 ) p ( x k + 1 ∣ z k + 1 , z k ) p ( z k + 1 ∣ z k ) =\sum_{z_{k+1}}p(x_{(k+2):n}|z_{k+1},z_k,x_{k+1})p(x_{k+1}|z_{k+1},z_k)p(z_{k+1}|z_k) =zk+1∑p(x(k+2):n∣zk+1,zk,xk+1)p(xk+1∣zk+1,zk)p(zk+1∣zk)
去掉條件獨立的項（ z k , x k + 1 z_k,x_{k+1} zk,xk+1條件獨立于 z k + 1 z_{k+1} zk+1），上式寫為：
= ∑ z k + 1 p ( x ( k + 2 ) : n ∣ z k + 1 ) p ( x k + 1 ∣ z k + 1 ) p ( z k + 1 ∣ z k ) =\sum_{z_{k+1}}p(x_{(k+2):n}|z_{k+1})p(x_{k+1}|z_{k+1})p(z_{k+1}|z_k) =zk+1∑p(x(k+2):n∣zk+1)p(xk+1∣zk+1)p(zk+1∣zk)
寫成DP的形式：
β k ( z k ) = ∑ z k + 1 β k + 1 ( z k + 1 ) p ( x k + 1 ∣ z k + 1 ) p ( z k + 1 ∣ z k ) \beta_k(z_k)=\sum_{z_{k+1}}\beta_{k+1}(z_{k+1})p(x_{k+1}|z_{k+1})p(z_{k+1}|z_k) βk(zk)=zk+1∑βk+1(zk+1)p(xk+1∣zk+1)p(zk+1∣zk)
兩個算法計算的方向不一樣，Forward 是從前向後，Backward 是從後向前。
下面将FB算法作為已知的條件，來對HMM模型的參數進行估計。
FB算法估計參數π
假定隐變量隻有三個狀态：1，2，3，那麼根據F/B算法有：參數 π = p ( z 1 ∣ x ) \pi=p(z_1|x) π=p(z1∣x)
對于第一個序列（這些機率是老師給出來的例子）：
p ( z 1 = 1 ∣ x 1 ) = 0.7 , p ( z 1 = 2 ∣ x 1 ) = 0.2 , p ( z 1 = 3 ∣ x 1 ) = 0.1 p(z_1=1|x_1)=0.7,p(z_1=2|x_1)=0.2,p(z_1=3|x_1)=0.1 p(z1=1∣x1)=0.7,p(z1=2∣x1)=0.2,p(z1=3∣x1)=0.1
那麼，第一個序列求出來的 z 1 z_1 z1為：
z 1 = [ 0.7 0.2 0.1 ] z_1=\begin{bmatrix} 0.7 \\ 0.2\\ 0.1 \end{bmatrix} z1=⎣⎡0.70.20.1⎦⎤
第二個序列：
p ( z 1 = 1 ∣ x 2 ) = 0.4 , p ( z 1 = 2 ∣ x 2 ) = 0.4 , p ( z 1 = 3 ∣ x 2 ) = 0.2 p(z_1=1|x_2)=0.4,p(z_1=2|x_2)=0.4,p(z_1=3|x_2)=0.2 p(z1=1∣x2)=0.4,p(z1=2∣x2)=0.4,p(z1=3∣x2)=0.2
z 1 = [ 0.4 0.4 0.2 ] z_1=\begin{bmatrix} 0.4 \\ 0.4\\ 0.2 \end{bmatrix} z1=⎣⎡0.40.40.2⎦⎤
第三個序列：
p ( z 1 = 1 ∣ x 3 ) = 0.6 , p ( z 1 = 2 ∣ x 3 ) = 0.3 , p ( z 1 = 3 ∣ x 3 ) = 0.1 p(z_1=1|x_3)=0.6,p(z_1=2|x_3)=0.3,p(z_1=3|x_3)=0.1 p(z1=1∣x3)=0.6,p(z1=2∣x3)=0.3,p(z1=3∣x3)=0.1
z 1 = [ 0.6 0.3 0.1 ] z_1=\begin{bmatrix} 0.6\\ 0.3\\ 0.1 \end{bmatrix} z1=⎣⎡0.60.30.1⎦⎤
把每個狀态的機率加起來，得到期望次數（不是實際次數）：
總 數 = [ 0.7 + 0.4 + 0.6 0.2 + 0.4 + 0.3 0.1 + 0.2 + 0.1 ] = [ 0.7 0.9 0.4 ] 總數=\begin{bmatrix} 0.7+0.4+0.6\\ 0.2+0.4+0.3\\ 0.1+0.2+ 0.1 \end{bmatrix}=\begin{bmatrix} 0.7\\ 0.9\\ 0.4 \end{bmatrix} 總數=⎣⎡0.7+0.4+0.60.2+0.4+0.30.1+0.2+0.1⎦⎤=⎣⎡0.70.90.4⎦⎤
然後轉換為機率：
π = [ 1.7 / 2.8 , 0.9 / 2.8 , 0.4 / 2.8 ] \pi=[1.7/2.8,0.9/2.8,0.4/2.8] π=[1.7/2.8,0.9/2.8,0.4/2.8]
FB估計參數B
參數B是emission probability matrix。
假設隐狀态有三個：1，2，3
觀測值有三個：a，b，c
隻知道綠色的觀測值，要算出灰色的隐狀态，每個狀态有3個取值，在參數已知的情況下可以估計機率值：
上圖中每列代表一個時間步，S1有6個時間步。
弄好了是這個樣子（三個樣本分别是S1-3），這裡用的是F/B算法，假定參數是已知的，是以可以算出下面的期望次數。
開始計算矩陣B：
這個1.4（這裡老師算錯了，應該是1.7，截圖不好改，就這樣吧）是從下面的綠色圈住的數字加起來得到的，表示從狀态1生成值a的期望次數之和：
然後把B期望次數轉換為機率：
估計A
A是狀态轉移矩陣，如果有m個狀态，那麼矩陣大小為m×m，矩陣某個元素 A i j A_{ij} Aij，表示從狀态i轉化為狀态j的機率，可以表示為下圖中的公式，然後根據條件機率公式可以變成中間的形式，然後又根據期望次數得到右邊的形式（任意時間步上，分母是狀态為i的期望次數，這個可以用F/B算法得到，分子是連續兩個狀态為i，j的期望次數，這個不好算，相對要算中間的分子的聯合機率）。
上圖公式中間的分子可以看做在第k時間步，觀測到x值時，目前狀态為i，下一狀态為j的機率：
p ( z k = i , z k + 1 = j ∣ x ) p(z_k=i,z_{k+1=j}|x) p(zk=i,zk+1=j∣x)
這個機率可以用F/B來算的。
下面就是如何算這個機率的過程：
在計算的過程中把x拆分成了三部分（對應上圖的三個紅框），然後得到4個機率，具體對應上圖相應的編号。
由于是正比于的關系，不能是直接用，要歸一化，把上面的結果記為： β k ( i , j ) \beta_k(i,j) βk(i,j)
是以，每個時刻有：
p ( z k = 1 , z k + 1 = 1 ∣ x ) ∝ β k ( 1 , 1 ) p(z_k=1,z_{k+1}=1|x)\propto \beta_k(1,1) p(zk=1,zk+1=1∣x)∝βk(1,1)
p ( z k = 1 , z k + 1 = 2 ∣ x ) ∝ β k ( 1 , 2 ) p(z_k=1,z_{k+1}=2|x)\propto \beta_k(1,2) p(zk=1,zk+1=2∣x)∝βk(1,2)
p ( z k = 1 , z k + 1 = 3 ∣ x ) ∝ β k ( 1 , 3 ) p(z_k=1,z_{k+1}=3|x)\propto \beta_k(1,3) p(zk=1,zk+1=3∣x)∝βk(1,3)
p ( z k = 2 , z k + 1 = 1 ∣ x ) ∝ β k ( 2 , 1 ) ⋮ p(z_k=2,z_{k+1}=1|x)\propto \beta_k(2,1)\\ \vdots p(zk=2,zk+1=1∣x)∝βk(2,1)⋮
p ( z k = 3 , z k + 1 = 3 ∣ x ) ∝ β k ( 3 , 3 ) p(z_k=3,z_{k+1}=3|x)\propto \beta_k(3,3) p(zk=3,zk+1=3∣x)∝βk(3,3)
歸一化：
p ( z k = 1 , z k + 1 = 1 ∣ x ) = β k ( 1 , 1 ) β k ( 1 , 1 ) + β k ( 1 , 2 ) + β k ( 1 , 3 ) + . . . + β k ( 3 , 3 ) p(z_k=1,z_{k+1}=1|x)=\cfrac{ \beta_k(1,1)}{ \beta_k(1,1)+\beta_k(1,2)+\beta_k(1,3)+...+\beta_k(3,3)} p(zk=1,zk+1=1∣x)=βk(1,1)+βk(1,2)+βk(1,3)+...+βk(3,3)βk(1,1)
以此類推。
下面看A怎麼計算（和B一樣，先算期望次數，然後算機率）
計算方法如下（例子）：
下面看具體例子，計算A不需要觀測值，是以綠色點沒有畫，藍色每個狀态的期望次數/機率 p ( z k = i ) , i = 1 , 2 , 3 p(z_k=i),i=1,2,3 p(zk=i),i=1,2,3（也就是算A的公式中的分母）：
然後算分子，分子是聯合機率，上面有推導，說明這個聯合機率可以分解為四個部分，然後可以計算出三個狀态轉移到下一個三個狀态的結果如下圖所示（為了簡單，省略了第二個狀态轉後面三個狀态、第三個狀态轉後面三個狀态，一種省略了6個綠色箭頭）：
計算矩陣：
這裡注意顔色（分子是黑圈，分母是紅框），還有就是最後一個狀态不算。
這樣就可以把A求出來。
Complete vs Incomplete Case
這兩個case前面有提過，這裡詳細講下。
Complete Case: ( z , x ) (z,x) (z,x) is observable，通常用MLE，SGD等方法來求解。
例如：
Incomplete Case: ( x ) (x) (x) is observable, z z z is unobservable.EM算法來求解
Complete Case示例
可以看到x有三個值：abc，z有三個值：123.都是離散的，現在要估計參數。
估計 π \pi π，從圖中可以看到有三個序列：
| 值 | 1 | 2 | 3 |
|---|---|---|---|
| 出現在第一個位置的次數 | 2 | 1 | |
| π \pi π取值 | 2/3 | 1/3 |
估計狀态轉移矩陣A，根據定義，A是3*3的矩陣，先寫出狀态轉移次數，例如左邊矩陣中的第一行第一列的數字代表從狀态1轉移到狀态1的次數一共有2次，第一行第二列的數字代表從狀态1轉移到狀态2的次數一共有1次，以此類推：
[ 2 1 2 1 2 1 0 2 1 ] \begin{bmatrix} 2 &1 &2 \\ 1 &2 & 1\\ 0 &2 &1 \end{bmatrix} ⎣⎡210122211⎦⎤
然後再計算出狀态轉移機率：
[ 2 / 5 1 / 5 2 / 5 1 / 4 2 / 4 1 / 4 0 2 / 3 1 / 3 ] \begin{bmatrix} 2/5 &1/5 &2/5 \\ 1/4 &2/4 &1/4\\ 0 &2/3 &1 /3 \end{bmatrix} ⎣⎡2/51/401/52/42/32/51/41/3⎦⎤
同理估計生成機率矩陣B，先寫次數（第一行第一清單示狀态為1的時候生成a的次數是3），再寫機率：
MLE for Complete and Incomplete Case
用最大似然來求解 θ \theta θ
Complete Case，這裡z和z都是已知的
l ( θ ; D ) = log p ( x , z ∣ θ ) = log p ( z ∣ θ z ) + log p ( x ∣ z , θ x ) l(\theta;D)=\text{log}p(x,z|\theta)=\text{log}p(z|\theta_z)+\text{log}p(x|z,\theta_x) l(θ;D)=logp(x,z∣θ)=logp(z∣θz)+logp(x∣z,θx)
Incomplete Case
l ( θ ; D ) = max log p ( x ) = log ∑ z p ( x , z ∣ θ ) = log ∑ z p ( z ∣ θ z ) p ( x ∣ z , θ x ) l(\theta;D)=\max\log p(x)=\text{log}\sum_zp(x,z|\theta)=\text{log}\sum_zp(z|\theta_z)p(x|z,\theta_x) l(θ;D)=maxlogp(x)=logz∑p(x,z∣θ)=logz∑p(z∣θz)p(x∣z,θx)
這裡用的累加實際上就是邊緣機率，要考慮所有z的可能，進而引入隐變量z，比較複雜，是以要引入EM算法來進行求解，第一步是求出z，再把z帶入後面一項，求最大似然。
EM推導
θ \theta θ:模型參數
x x x:觀測變量
z z z:隐變量
下面用MLE的方式來推導EM，是以按照MLE，寫出損失函數：
L ( θ ) = log p ( x ∣ θ ) L(\theta)=\log p(x|\theta) L(θ)=logp(x∣θ)
目标函數：
a r g max L ( θ ) = a r g max log p ( x ∣ θ ) arg\max L(\theta)=arg\max\log p(x|\theta) argmaxL(θ)=argmaxlogp(x∣θ)
假設第 n n n次疊代後得到了 θ n \theta_n θn，這個參數是已知的。那麼我們希望下一步找到的新參數 θ \theta θ與 θ n \theta_n θn差距越大越好（這裡的下一步的 θ \theta θ其實是 θ n + 1 \theta_{n+1} θn+1）：
a r g max θ ( L ( θ ) − L ( θ n ) ) = log p ( x ∣ θ ) − log p ( x ∣ θ n ) \underset{\theta}{arg\max}(L(\theta)-L(\theta_n))=\text{log}p(x|\theta)-\text{log}p(x|\theta_n) θargmax(L(θ)−L(θn))=logp(x∣θ)−logp(x∣θn)
然後把隐變量考慮進來：
L ( θ ) − L ( θ n ) = log ∑ z p ( x , z ∣ θ ) − log p ( x ∣ θ n ) = log ∑ z p ( x ∣ z , θ ) p ( z ∣ θ ) − log p ( x ∣ θ n ) = log ∑ z p ( x ∣ z , θ ) p ( z ∣ θ ) p ( z ∣ x , θ n ) p ( z ∣ x , θ n ) − log p ( x ∣ θ n ) = log ∑ z p ( z ∣ x , θ n ) p ( x ∣ z , θ ) p ( z ∣ θ ) p ( z ∣ x , θ n ) − log p ( x ∣ θ n ) L(\theta)-L(\theta_n)=\text{log}\sum_zp(x,z|\theta)-\text{log}p(x|\theta_n)\\ =\text{log}\sum_zp(x|z,\theta)p(z|\theta)-\text{log}p(x|\theta_n)\\ =\text{log}\sum_zp(x|z,\theta)p(z|\theta)\cfrac{p(z|x,\theta_n)}{p(z|x,\theta_n)}-\text{log}p(x|\theta_n)\\ =\text{log}\sum_zp(z|x,\theta_n)\cfrac{p(x|z,\theta)p(z|\theta)}{p(z|x,\theta_n)}-\text{log}p(x|\theta_n) L(θ)−L(θn)=logz∑p(x,z∣θ)−logp(x∣θn)=logz∑p(x∣z,θ)p(z∣θ)−logp(x∣θn)=logz∑p(x∣z,θ)p(z∣θ)p(z∣x,θn)p(z∣x,θn)−logp(x∣θn)=logz∑p(z∣x,θn)p(z∣x,θn)p(x∣z,θ)p(z∣θ)−logp(x∣θn)
根據jensen’s inequality，有
具體證明
當 ∑ i = 1 n λ i = 1 \sum_{i=1}^n\lambda_i=1 ∑i=1nλi=1時：
log ∑ i = 1 n λ i x i ≥ ∑ i = 1 n λ i log x i \text{log}\sum_{i=1}^n\lambda_ix_i\ge \sum_{i=1}^n\lambda_i\text{log}x_i logi=1∑nλixi≥i=1∑nλilogxi
是以上面我們構造了一個類似 λ i \lambda_i λi的這麼一個項： p ( z ∣ x , θ n ) p(z|x,\theta_n) p(z∣x,θn)，因為 ∑ z p ( z ∣ x , θ n ) = 1 \sum_zp(z|x,\theta_n)=1 ∑zp(z∣x,θn)=1，是以：
L ( θ ) − L ( θ n ) ≥ ∑ z p ( z ∣ x , θ n ) log p ( x ∣ z , θ ) p ( z ∣ θ ) p ( z ∣ x , θ n ) − log p ( x ∣ θ n ) L(\theta)-L(\theta_n)\ge \sum_zp(z|x,\theta_n)\text{log}\cfrac{p(x|z,\theta)p(z|\theta)}{p(z|x,\theta_n)}-\text{log}p(x|\theta_n) L(θ)−L(θn)≥z∑p(z∣x,θn)logp(z∣x,θn)p(x∣z,θ)p(z∣θ)−logp(x∣θn)
由于 log p ( x ∣ θ n ) \text{log}p(x|\theta_n) logp(x∣θn)和 z z z沒有關系，是以
log p ( x ∣ θ n ) = 1 ⋅ log p ( x ∣ θ n ) = ∑ z p ( z ∣ x , θ n ) ⋅ log p ( x ∣ θ n ) \text{log}p(x|\theta_n)=1\cdot\text{log}p(x|\theta_n)=\sum_zp(z|x,\theta_n)\cdot\text{log}p(x|\theta_n) logp(x∣θn)=1⋅logp(x∣θn)=z∑p(z∣x,θn)⋅logp(x∣θn)
上面的不等式就變成：
L ( θ ) − L ( θ n ) ≥ ∑ z p ( z ∣ x , θ n ) log p ( x ∣ z , θ ) p ( z ∣ θ ) p ( z ∣ x , θ n ) p ( x ∣ θ n ) = Δ ( θ θ n ) L(\theta)-L(\theta_n)\ge \sum_zp(z|x,\theta_n)\text{log}\cfrac{p(x|z,\theta)p(z|\theta)}{p(z|x,\theta_n)p(x|\theta_n)}=\Delta(\cfrac{\theta}{\theta_n}) L(θ)−L(θn)≥z∑p(z∣x,θn)logp(z∣x,θn)p(x∣θn)p(x∣z,θ)p(z∣θ)=Δ(θnθ)
是以：
L ( θ ) − L ( θ n ) ≥ Δ ( θ θ n ) → L ( θ ) ≥ L ( θ n ) + Δ ( θ θ n ) L(\theta)-L(\theta_n)\ge\Delta(\cfrac{\theta}{\theta_n})\to L(\theta)\ge L(\theta_n)+\Delta(\cfrac{\theta}{\theta_n}) L(θ)−L(θn)≥Δ(θnθ)→L(θ)≥L(θn)+Δ(θnθ)
這樣我們就找到了 L ( θ ) L(\theta) L(θ)的下界，求最大值的時候，我們可以不斷最大化下界，進而使得 L ( θ ) L(\theta) L(θ)最大化。
a r g max θ [ L ( θ n ) + Δ ( θ θ n ) ] = a r g max θ [ L ( θ n ) + ∑ z p ( z ∣ x , θ n ) log p ( x ∣ z , θ ) p ( z ∣ θ ) p ( z ∣ x , θ n ) p ( x ∣ θ n ) ] \underset{\theta}{arg\max}[L(\theta_n)+\Delta(\cfrac{\theta}{\theta_n})]\\ =\underset{\theta}{arg\max}[L(\theta_n)+ \sum_zp(z|x,\theta_n)\text{log}\cfrac{p(x|z,\theta)p(z|\theta)}{p(z|x,\theta_n)p(x|\theta_n)}] θargmax[L(θn)+Δ(θnθ)]=θargmax[L(θn)+z∑p(z∣x,θn)logp(z∣x,θn)p(x∣θn)p(x∣z,θ)p(z∣θ)]
這裡把和求極值的目标 θ \theta θ無關的東西都去掉，簡化：
= a r g max θ { ∑ z p ( z ∣ x , θ n ) log p ( x ∣ z , θ ) p ( z ∣ θ ) } = a r g max θ { ∑ z p ( z ∣ x , θ n ) log p ( x , z ∣ θ ) } =\underset{\theta}{arg\max}\left\{ \sum_zp(z|x,\theta_n)\text{log}p(x|z,\theta)p(z|\theta)\right\}\\ =\underset{\theta}{arg\max}\left\{ \sum_zp(z|x,\theta_n)\text{log}p(x,z|\theta)\right\} =θargmax{z∑p(z∣x,θn)logp(x∣z,θ)p(z∣θ)}=θargmax{z∑p(z∣x,θn)logp(x,z∣θ)}
根據機率公式： p ( A B ) = p ( A , B ) = p ( A ∣ B ) P ( B ) p(AB)=p(A,B)=p(A|B)P(B) p(AB)=p(A,B)=p(A∣B)P(B)
擴充一下： p ( A B ∣ C ) = p ( A , B ∣ C ) = p ( A ∣ B , C ) P ( B ∣ C ) p(AB|C)=p(A,B|C)=p(A|B,C)P(B|C) p(AB∣C)=p(A,B∣C)=p(A∣B,C)P(B∣C)
p ( A , B ∣ C ) p(A,B|C) p(A,B∣C)表示C發生的條件下，AB發生的機率
p ( A ∣ B , C ) p(A|B,C) p(A∣B,C)表示事件B，事件C都發生的條件下，A發生的機率
是以上式中： p ( x ∣ z , θ ) p ( z ∣ θ ) = p ( x , z ∣ θ ) p(x|z,\theta)p(z|\theta)=p(x,z|\theta) p(x∣z,θ)p(z∣θ)=p(x,z∣θ)
這裡的前面一項是一個z的期望值（數學期望概念），是以：
= a r g max θ [ E z ∣ x , θ n log p ( x , z ∣ θ ) ] =\underset{\theta}{arg\max}[E_{z|x,\theta_n}\text{log}p(x,z|\theta)] =θargmax[Ez∣x,θnlogp(x,z∣θ)]
以上就是EM算法的形式，它分兩個步驟：
求期望：E-step，求z的期望值，就是求 E z ∣ x , θ n E_{z|x,\theta_n} Ez∣x,θn在 log p ( x , z ∣ θ ) \text{log}p(x,z|\theta) logp(x,z∣θ)的條件下的期望。
求極值：M-step，最大化 log p ( x , z ∣ θ ) \text{log}p(x,z|\theta) logp(x,z∣θ)，這個時候 z z z是已知的。相當于Complete Case。
EM小結
E-step是求z
M-step是求 θ \theta θ
1、EM算法不是全局最優解，是局部最優解。通常我們使用不同的初始化，多重複幾次，以獲得較好效果。
2、EM算是嚴格遞增的，是以EM一定會converge。
K-means
K均值本質上也是屬于EM算法的一個特例。大概說一個這個算法的思想：
1、先标記兩個點，圖2中藍色和紅色的點，也叫prototype（中心點）
2、根據這兩個中心點計算距離，分類.圖3.
3、根據分類，重新計算分類的中心點。圖4.回到步驟2，知道完成收斂。
可以看到K均值算法中，有兩個未知的東西：
1、變量 r n k r_{nk} rnk，代表一個點屬于哪個分類，當 r n k = 1 r_{nk}=1 rnk=1代表 x n x_n xn屬于第 k k k個分類，不屬于則為0.那麼每個樣本 x n x_n xn的分類可以表示為一個k維向量 [ 0 , 0 , . . . , 1 , . . . 0 ] [0,0,...,1,...0] [0,0,...,1,...0]，屬于那一個分類那麼就是1，其他的都為0；
2、分類的中心點在什麼地方？這個我們可以用 μ k \mu_k μk代表k個分類的各自的中心點坐标。
目标函數表示為：
m i n i m i z e J = ∑ n = 1 N ∑ k = 1 K r n k ∣ ∣ x n − μ k ∣ ∣ 2 minimize\space J=\sum_{n=1}^N\sum_{k=1}^Kr_{nk}||x_n-\mu_k||^2 minimize J=n=1∑Nk=1∑Krnk∣∣xn−μk∣∣2
這裡 r n k r_{nk} rnk相當于隐變量。 μ k \mu_k μk相當于參數，從EM算法的角度來看
E-STEP計算 r n k r_{nk} rnk
M-STEM計算 μ k \mu_k μk
MLE for GMM
GMM(語音識别應用較多)在李宏毅的課裡面有講過，這裡不多展開，上圖。
The joint distribution between x x x and z z z (representing color) are:
p ( x , z = ′ r e d ′ ) = N ( x ∣ μ 1 , Σ 1 ) p(x,z='red')={\color{red}N(x|\mu_1,\Sigma_1)} p(x,z=′red′)=N(x∣μ1,Σ1)
p ( x , z = ′ b l u e ′ ) = N ( x ∣ μ 2 , Σ 2 ) p(x,z='blue')={\color{blue}N(x|\mu_2,\Sigma_2)} p(x,z=′blue′)=N(x∣μ2,Σ2)
p ( x , z = ′ g r e e n ′ ) = N ( x ∣ μ 3 , Σ 3 ) p(x,z='green')={\color{green}N(x|\mu_3,\Sigma_3)} p(x,z=′green′)=N(x∣μ3,Σ3)
在GMM中，每個樣本可以用以下數學公式表達：
p ( x ) = ∑ k = 1 K π k N ( x ∣ μ k , Σ k ) p(x)=\sum_{k=1}^K\pi_k N(x|\mu_k,\Sigma_k) p(x)=k=1∑KπkN(x∣μk,Σk)
π k \pi_k πk是每個分布的權重，屬于隐變量
μ k , Σ k \mu_k,\Sigma_k μk,Σk是模型的參數。
可以看到K均值算法就是GMM的一個特例。
每一個點是上面的公式，那麼所有的整體就是對所有點求和：
log p ( D ∣ π , μ , Σ ) = ∑ n = 1 N log { ∑ k = 1 K π k N ( x ∣ μ k , Σ k ) } \text{log}p(D|\pi,\mu,\Sigma)=\sum_{n=1}^N\text{log}\{\sum_{k=1}^K\pi_k N(x|\mu_k,\Sigma_k)\} logp(D∣π,μ,Σ)=n=1∑Nlog{k=1∑KπkN(x∣μk,Σk)}
HMM vs RNN
HMM的每個狀态之間進行轉移要用到轉移矩陣進行計算，這個和狀态次元有關，會變很大
至于優缺點對比可以直接參考分布式表示比獨熱表示的對比。