在本篇我們會讨論HMM模型參數求解的問題，這個問題在HMM三個問題裡算是最複雜的。在研究這個問題之前，建議先閱讀這個系列的前兩篇以熟悉HMM模型和HMM的前向後向算法，以及EM算法原理總結，這些在本篇裡會用到。在李航的《統計學習方法》中，這個算法的講解隻考慮了單個觀測序列的求解，是以無法用于實際多樣本觀測序列的模型求解，本文關注于如何使用多個觀測序列來求解HMM模型參數。
1. HMM模型參數求解概述
HMM模型參數求解根據已知的條件可以分為兩種情況。
第一種情況較為簡單，就是我們已知$D$個長度為$T$的觀測序列和對應的隐藏狀态序列，即$\{(O_1, I_1), (O_2, I_2), ...(O_D, I_D)\}$是已知的，此時我們可以很容易的用最大似然來求解模型參數。
假設樣本從隐藏狀态$q_i$轉移到$q_j$的頻率計數是$A_{ij}$,那麼狀态轉移矩陣求得為：
$$
A = \Big[a_{ij}\Big], \;其中a_{ij} = \frac{A_{ij}}{\sum\limits_{s=1}^{N}A_{is}}
假設樣本隐藏狀态為$q_j$且觀測狀态為$v_k$的頻率計數是$B_{jk}$,那麼觀測狀态機率矩陣為：
B= \Big[b_{j}(k)\Big], \;其中b_{j}(k) = \frac{B_{jk}}{\sum\limits_{s=1}^{M}B_{js}}
假設所有樣本中初始隐藏狀态為$q_i$的頻率計數為$C(i)$,那麼初始機率分布為：
\Pi = \pi(i) = \frac{C(i)}{\sum\limits_{s=1}^{N}C(s)}
可見第一種情況下求解模型還是很簡單的。但是在很多時候，我們無法得到HMM樣本觀察序列對應的隐藏序列，隻有$D$個長度為$T$的觀測序列，即$\{(O_1), (O_2), ...(O_D)\}$是已知的，此時我們能不能求出合适的HMM模型參數呢？這就是我們的第二種情況，也是我們本文要讨論的重點。它的解法最常用的是鮑姆-韋爾奇算法，其實就是基于EM算法的求解，隻不過鮑姆-韋爾奇算法出現的時代，EM算法還沒有被抽象出來，是以我們本文還是說鮑姆-韋爾奇算法。
2. 鮑姆-韋爾奇算法原理
鮑姆-韋爾奇算法原理既然使用的就是EM算法的原理，那麼我們需要在E步求出聯合分布$P(O,I|λ)$基于條件機率$P(I|O,\overline{\lambda})$的期望，其中$\overline{\lambda}$為目前的模型參數，然後再M步最大化這個期望，得到更新的模型參數$λ$。接着不停的進行EM疊代，直到模型參數的值收斂為止。
首先來看看E步，目前模型參數為$\overline{\lambda}$, 聯合分布$P(O,I|\lambda)$基于條件機率$P(I|O,\overline{\lambda})$的期望表達式為：
L(\lambda, \overline{\lambda}) = \sum\limits_{I}P(I|O,\overline{\lambda})logP(O,I|\lambda)
在M步，我們極大化上式，然後得到更新後的模型參數如下：
\overline{\lambda} = arg\;\max_{\lambda}\sum\limits_{I}P(I|O,\overline{\lambda})logP(O,I|\lambda)
通過不斷的E步和M步的疊代，直到$\overline{\lambda}$收斂。下面我們來看看鮑姆-韋爾奇算法的推導過程。
3. 鮑姆-韋爾奇算法的推導
我們的訓練資料為$\{(O_1, I_1), (O_2, I_2), ...(O_D, I_D)\}$，其中任意一個觀測序列$O_d = \{o_1^{(d)}, o_2^{(d)}, ... o_T^{(d)}\}$,其對應的未知的隐藏狀态序清單示為：$I_d = \{i_1^{(d)}, i_2^{(d)}, ... i_T^{(d)}\}$
首先看鮑姆-韋爾奇算法的E步，我們需要先計算聯合分布$P(O,I|λ)$的表達式如下：
P(O,I|\lambda) = \prod_{d=1}^D\pi_{i_1^{(d)}}b_{i_1^{(d)}}(o_1^{(d)})a_{i_1^{(d)}i_2^{(d)}}b_{i_2^{(d)}}(o_2^{(d)})...a_{i_{T-1}^{(d)}i_T^{(d)}}b_{i_T^{(d)}}(o_T^{(d)})
我們的E步得到的期望表達式為：
在M步我們要極大化上式。由于$P(I|O,\overline{\lambda}) = P(I,O|\overline{\lambda})/P(O|\overline{\lambda})$,而$P(O|\overline{\lambda})$是常數，是以我們要極大化的式子等價于：
\overline{\lambda} = arg\;\max_{\lambda}\sum\limits_{I}P(O,I|\overline{\lambda})logP(O,I|\lambda)
我們将上面$P(O,I|λ)$的表達式帶入我們的極大化式子，得到的表達式如下：
\overline{\lambda} = arg\;\max_{\lambda}\sum\limits_{d=1}^D\sum\limits_{I}P(O,I|\overline{\lambda})(log\pi_{i_1} + \sum\limits_{t=1}^{T-1}log\;a_{i_t}a_{i_{t+1}} + \sum\limits_{t=1}^Tb_{i_t}(o_t))
我們的隐藏模型參數$λ=(A,B,Π)$,是以下面我們隻需要對上式分别對$A,B,Π$求導即可得到我們更新的模型參數$\overline{\lambda}$
首先我們看看對模型參數ΠΠ的求導。由于ΠΠ隻在上式中括号裡的第一部分出現，是以我們對于ΠΠ的極大化式子為：
\overline{\pi_i} = arg\;\max_{\pi_{i_1}} \sum\limits_{d=1}^D\sum\limits_{I}P(O,I|\overline{\lambda})log\pi_{i_1} = arg\;\max_{\pi_{i}} \sum\limits_{d=1}^D\sum\limits_{i=1}^NP(O,i_1^{(d)} =i|\overline{\lambda})log\pi_{i}
由于$π_i$還滿足$\sum\limits_{i=1}^N\pi_i =1$，是以根據拉格朗日子乘法，我們得到$π_i$要極大化的拉格朗日函數為：
arg\;\max_{\pi_{i}}\sum\limits_{d=1}^D\sum\limits_{i=1}^NP(O,i_1^{(d)} =i|\overline{\lambda})log\pi_{i} + \gamma(\sum\limits_{i=1}^N\pi_i -1)
其中，$γ$為拉格朗日系數。上式對$π_i$求偏導數并令結果為0， 我們得到：
\sum\limits_{d=1}^DP(O,i_1^{(d)} =i|\overline{\lambda}) + \gamma\pi_i = 0
令$i$分别等于從1到$N$，從上式可以得到$N$個式子，對這$N$個式子求和可得：
\sum\limits_{d=1}^DP(O|\overline{\lambda}) + \gamma = 0
從上兩式消去$γ$,得到$π_i$的表達式為：
\pi_i =\frac{\sum\limits_{d=1}^DP(O,i_1^{(d)} =i|\overline{\lambda})}{\sum\limits_{d=1}^DP(O|\overline{\lambda})}\frac{\sum\limits_{d=1}^DP(O,i_1^{(d)} =i|\overline{\lambda})}{DP(O|\overline{\lambda})} =
\frac{\sum\limits_{d=1}^DP(i_1^{(d)} =i|O, \overline{\lambda})}{D} = \frac{\sum\limits_{d=1}^DP(i_1^{(d)} =i|O^{(d)}, \overline{\lambda})}{D}
利用我們在隐馬爾科夫模型HMM（二）前向後向算法評估觀察序列機率裡第二節中前向機率的定義可得：
P(i_1^{(d)} =i|O^{(d)}, \overline{\lambda}) = \gamma_1^{(d)}(i)
是以最終我們在M步$π_i$的疊代公式為：
\pi_i = \frac{\sum\limits_{d=1}^D\gamma_1^{(d)}(i)}{D}
現在我們來看看$A$的疊代公式求法。方法和$Π$的類似。由于$A$隻在最大化函數式中括号裡的第二部分出現，而這部分式子可以整理為：
\sum\limits_{d=1}^D\sum\limits_{I}\sum\limits_{t=1}^{T-1}P(O,I|\overline{\lambda})log\;a_{i_t}a_{i_{t+1}} = \sum\limits_{d=1}^D\sum\limits_{i=1}^N\sum\limits_{j=1}^N\sum\limits_{t=1}^{T-1}P(O,i_t^{(d)} = i, i_{t+1}^{(d)} = j|\overline{\lambda})log\;a_{ij}
由于$a_{ij}$還滿足$\sum\limits_{j=1}^Na_{ij} =1$。和求解$π_i$類似，我們可以用拉格朗日子乘法并對$a_{ij}$求導，并令結果為0，可以得到$a_{ij}$的疊代表達式為：
a_{ij} = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}P(O^{(d)}, i_t^{(d)} = i, i_{t+1}^{(d)} = j|\overline{\lambda})}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}P(O^{(d)}, i_t^{(d)} = i|\overline{\lambda})}
利用隐馬爾科夫模型HMM（二）前向後向算法評估觀察序列機率裡第二節中前向機率的定義和第五節$\xi_t(i,j)$的定義可得們在M步$a_{ij}$的疊代公式為：
a_{ij} = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}\xi_t^{(d)}(i,j)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T-1}\gamma_t^{(d)}(i)}
現在我們來看看$B$的疊代公式求法。方法和$Π$的類似。由于$B$隻在最大化函數式中括号裡的第三部分出現，而這部分式子可以整理為：
\sum\limits_{d=1}^D\sum\limits_{I}\sum\limits_{t=1}^{T}P(O,I|\overline{\lambda})log\;b_{i_t}(o_t) = \sum\limits_{d=1}^D\sum\limits_{j=1}^N\sum\limits_{t=1}^{T}P(O,i_t^{(d)} = j|\overline{\lambda})log\;b_{j}(o_t)
由于$b_{j}(o_t)$還滿足$\sum\limits_{k=1}^Mb_{j}(o_t =v_k) =1$。和求解$\pi_i$類似，我們可以用拉格朗日子乘法并對$b_{j}(k)$求導，并令結果為0，得到$b_{j}(k)$的疊代表達式為：
b_{j}(k) = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T}P(O,i_t^{(d)} = j|\overline{\lambda})I(o_t^{(d)}=v_k)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T}P(O,i_t^{(d)} = j|\overline{\lambda})}
其中$I(o_t^{(d)}=v_k)$當且僅當$o_t^{(d)}=v_k$時為1，否則為0. 利用隐馬爾科夫模型HMM（二）前向後向算法評估觀察序列機率裡第二節中前向機率的定義可得$b_{j}(o_t)$的最終表達式為：
b_{j}(k) = \frac{\sum\limits_{d=1}^D\sum\limits_{t=1, o_t^{(d)}=v_k}^{T}\gamma_t^{(d)}(i)}{\sum\limits_{d=1}^D\sum\limits_{t=1}^{T}\gamma_t^{(d)}(i)}
有了$\pi_i, a_{ij},b_{j}(k)$的疊代公式，我們就可以疊代求解HMM模型參數了。
4. 鮑姆-韋爾奇算法流程總結
這裡我們概括總結下鮑姆-韋爾奇算法的流程。
輸入： $D$個觀測序列樣本$\{(O_1), (O_2), ...(O_D)\}$
輸出：HMM模型參數
1)随機初始化所有的$\pi_i, a_{ij},b_{j}(k)$
2) 對于每個樣本$d=1,2,...D$，用前向後向算法計算$gamma_t^{(d)}(i)，xi_t^{(d)}(i,j), t =1,2...T$
3) 更新模型參數：
4) 如果$\pi_i, a_{ij},b_{j}(k)$的值已經收斂，則算法結束，否則回到第2）步繼續疊代。
以上就是鮑姆-韋爾奇算法的整個過程。
摘自：
https://www.cnblogs.com/pinard/p/6972299.html![Javascript建構Bingo卡片遊戲[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)