概率圖模型之隱馬爾科夫模型(HMM)

??首先抄下《統(tǒng)計(jì)學(xué)習(xí)方法》中HMM的定義和相關(guān)知識(shí)點(diǎn)：隱馬爾科夫模型是關(guān)于時(shí)序的概率模型，描述由一個(gè)隱藏的馬爾科夫鏈隨機(jī)生成不可觀測的狀態(tài)隨機(jī)序列，再由各個(gè)狀態(tài)生成一個(gè)觀測而產(chǎn)生觀測隨機(jī)序列的過程。隱馬爾科夫模型由初始狀態(tài)概率向量\pi、狀態(tài)轉(zhuǎn)移概率矩陣A和觀測概率矩陣B（也可稱為發(fā)射概率矩陣）組成。隱馬爾科夫模型做了兩個(gè)基本假設(shè)——一是任意時(shí)刻的隱狀態(tài)只與前一時(shí)刻的隱狀態(tài)有關(guān)，二是任意時(shí)刻的觀測只與當(dāng)前時(shí)刻的隱狀態(tài)有關(guān)。隱馬爾科夫模型如下圖所示：

隱馬爾科夫模型.png

其中，
x
就是隱狀態(tài)，而
y
就是觀測狀態(tài)。隱馬爾科夫模型有3個(gè)基本問題：

  1. 概率計(jì)算問題。給定模型參數(shù)\lambda = (A,B,\pi)和觀測序列O，計(jì)算在模型\lambda下觀測序列O出現(xiàn)的概率
  2. 學(xué)習(xí)問題。也就是模型的訓(xùn)練，已知觀測序列O，估計(jì)模型參數(shù)\lambda
  3. 預(yù)測問題。也稱為decode，給定觀測序列O，求最有可能的對(duì)應(yīng)的隱狀態(tài)

這3個(gè)問題都需要計(jì)算概率并進(jìn)行對(duì)比得到結(jié)果，當(dāng)數(shù)據(jù)很龐大的時(shí)候，算法的關(guān)鍵就是如何對(duì)概率的計(jì)算進(jìn)行優(yōu)化。首先，我們將模型中的隱狀態(tài)轉(zhuǎn)移在時(shí)間上展開，得到隱狀態(tài)的晶格圖，如下：

隱馬爾科夫中的隱狀態(tài)轉(zhuǎn)移圖.png
每一時(shí)刻的狀態(tài)與前一時(shí)刻的所有狀態(tài)和下一時(shí)刻的所有狀態(tài)都有關(guān)。顯然，如果能夠記住中間每一時(shí)刻的所有狀態(tài)的轉(zhuǎn)移概率，對(duì)下一時(shí)刻的狀態(tài)概率（或者上一時(shí)刻的狀態(tài)概率）的計(jì)算是很有幫助的。
??對(duì)于概率預(yù)測問題，我們假設(shè)前向概率為
\alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda)
，后向概率為
\beta_t(i)=P(o_{t+1},o_{t+2},...,o_T|i_t=q_i,\lambda)
，其中
o
表示觀測序列，
i
表示隱狀態(tài)。我們可以用
\alpha_t
來推導(dǎo)
\alpha_{t+1}
（前向算法），也可以用
\beta_{t+1}
來推導(dǎo)
\beta_t
（后向算法）。完整的前向算法可以分為3步：

  1. 初值，\alpha_1(i)=\pi_ib_i(o_1),i=1,2,...,N
  2. 遞歸，對(duì)t=1,2,...,T-1有，\alpha_{t+1}(i)=[\sum_{j=1}^N\alpha_t(j)a_{ji}]b(o_{t+1}),i=1,2,...,N
  3. 終止，P(O|\lambda)=\sum_{i=1}^N\alpha_T(i)

完整的后向算法也是分為3步：

  1. 初值，\beta_T(i)=1,i=1,2,...,N
  2. 遞歸，對(duì)t=T-1,T-2,...,1有，\beta|t(i)=\sum_{j=1}^Na_{ij}b_j(o_{t+1})\beta_{t+1}(j),i=1,2,...,N
  3. 終止，P(O|\lambda)=\sum_{i=1}^N\pi_ib_i(o_1)\beta_1(i)

??對(duì)于學(xué)習(xí)問題，可以分為兩種情況進(jìn)行計(jì)算。一種是已知隱狀態(tài)，那么直接使用極大似然估計(jì)算法就可以得到；一種是不知隱狀態(tài)，這種是常見情況，此時(shí)就沒法用極大似然估計(jì)算法了，似然函數(shù)是P(O|\lambda)=\sum_IP(O,I|\lambda)=\sum_IP(O|I,\lambda)P(I|\lambda)，但是I是未知的，P(I|\lambda)是沒法得到，所以也就沒法直接使用極大似然估計(jì)算法了。此時(shí)就應(yīng)該用EM算法，依靠EM算法的迭代訓(xùn)練達(dá)到一個(gè)比較好的效果。EM算法中不是對(duì)P(O|\lambda)直接最大似然估計(jì)，而是最優(yōu)化完全數(shù)據(jù)的似然函數(shù)P(O,I|\lambda)，所以新似然函數(shù)可寫成Q(\lambda,\overline{\lambda})=\sum_I \log P(O,I|\lambda) \approx \sum_I \log P(O,I|\lambda)P(O,I|\overline{\lambda})（這里的公式推導(dǎo)請看PRML的9.4節(jié)），然后就可以利用極大似然估計(jì)算法得到新的模型參數(shù)\lambda，接著將\lambda作為新一輪的\overline{\lambda}，并迭代訓(xùn)練模型，這樣就可以得到最終的模型參數(shù)\lambda。這種方法稱為Baum-Welch算法。具體每一輪如何得到\lambda，《統(tǒng)計(jì)學(xué)習(xí)方法》中181頁有著詳細(xì)的講解，這里就不抄上了。
??對(duì)于預(yù)測問題，也是分為兩種方法。一種是近似算法，計(jì)算公式為：\begin{align}\gamma_t(i) &= \frac{\alpha_t(i)\beta_t(i)}{P(O|\lambda)}=\frac{\alpha_t(i)\beta_t(i)}{\sum_{j=1}^{N}\alpha_t(j)\beta_t(j)} \\ i_t^* &= \mathop{\arg\min}_{1\leq i \leq N}[\gamma_t(i)],t=1,2,...,T \end{align}但是這種算法預(yù)測的狀態(tài)序列可能有不發(fā)生的部分，即對(duì)某些i，j有a_{ij}=0。分析一下，根據(jù)定義來看，\alpha_t(i)=P(o_1,o_2,...,o_t,i_t=q_i|\lambda)，\beta_t(i)=P(o_{t+1},o_{t+2},...,o_T|i_t=q_i,\lambda)，\alpha_t中考慮了1到t的連續(xù)性，\beta_t中考慮了t+1到T的連續(xù)性，但是它們都沒有考慮t和t+1之間的連續(xù)性。所以最好就是求一條完整的路徑，此時(shí)就可以采用第二種方法——維特比算法。維特比算法是采用了動(dòng)態(tài)規(guī)劃來求解最優(yōu)路徑，每個(gè)時(shí)刻都保存了每個(gè)隱狀態(tài)的最大可能概率和對(duì)應(yīng)的上一時(shí)刻的最優(yōu)隱狀態(tài)。詳細(xì)的維特比算法偽代碼如下圖：

維特比算法.png
其中第一個(gè)for循環(huán)是為了初始化中間變量
T_1
和
T_2
，這兩個(gè)變量就是為了保存中間時(shí)刻的每個(gè)隱狀態(tài)的最大累積概率和該隱狀態(tài)對(duì)應(yīng)的上一時(shí)刻的最優(yōu)隱狀態(tài)。第二個(gè)for循環(huán)就是根據(jù)每個(gè)時(shí)刻的觀察變量找到當(dāng)前時(shí)刻的每個(gè)隱狀態(tài)的累積概率和該隱狀態(tài)對(duì)應(yīng)的上一時(shí)刻的最優(yōu)隱狀態(tài)。最后再根據(jù)
T_2
得到最終的最優(yōu)隱狀態(tài)路徑。我再結(jié)合上文中提到的隱狀態(tài)展開圖（也稱為晶格圖）來解釋下維特比算法：
隱馬爾科夫中的隱狀態(tài)轉(zhuǎn)移展開圖.png
假設(shè)我們已經(jīng)得到了n-1時(shí)刻的
T_1
，即
T_1[:,n-1]
，那么對(duì)于時(shí)刻n的每個(gè)隱狀態(tài)k，都會(huì)用偽代碼中的第二個(gè)for循環(huán)來計(jì)算時(shí)刻n是隱狀態(tài)k的最大概率（保存在
T_1[k,n]
中）和對(duì)應(yīng)的上一時(shí)刻n-1的最優(yōu)隱狀態(tài)（保存在
T_2[k,n]
中）。最后通過回溯
T_2
就可以得到最優(yōu)路徑。

??hmmlearn源碼中實(shí)現(xiàn)3種模型——GaussianHMM、GMMHMM和MultinomialHMM。其中GaussianHMM假設(shè)觀測狀態(tài)是連續(xù)型且滿足高斯分布，GMMHMM假設(shè)觀測狀態(tài)是連續(xù)型且滿足混合高斯分布，MultinomialGMM假設(shè)觀測狀態(tài)是離散型。
??在代碼實(shí)現(xiàn)上，hmmlearn在base.py中定義了基本HMM模型baseHMM類，類中定義了2個(gè)重要參數(shù)——self.startprob（HMM的初始狀態(tài)\pi，維度是[n_components]）和self.transmat_（HMM的狀態(tài)轉(zhuǎn)移矩陣A，維度是[n_components, n_components]），基類中并沒有定義發(fā)射矩陣B，因?yàn)橹挥杏^測狀態(tài)是離散型的HMM模型才有發(fā)射矩陣（代碼在MultinomialGMM類中單獨(dú)定義了self.emissionprob_）。而HMM中的3個(gè)基本問題則對(duì)應(yīng)了類中的3個(gè)函數(shù)：

  1. 概率計(jì)算問題，對(duì)應(yīng)了_baseHMM類中的score函數(shù)。代碼中利用前向算法來計(jì)算概率，核心部分如下：
for i, j in iter_from_X_lengths(X, lengths):
    framelogprob = self._compute_log_likelihood(X[i:j])
    logprobij, _fwdlattice = self._do_forward_pass(framelogprob)
    logprob += logprobij

其中，_do_forward_pass函數(shù)實(shí)現(xiàn)了前向算法中的\alpha_{t+1}(i)=[\sum_{j=1}^N\alpha_t(j)a_{ji}]b(o_{t+1}),i=1,2,...,N，代碼在https://github.com/hmmlearn/hmmlearn/blob/master/lib/hmmlearn/_hmmc.pyx中。具體核心代碼如下：

for t in range(1, n_samples):
    for j in range(n_components):
        for i in range(n_components):
            work_buffer[i] = fwdlattice[t - 1, i] + log_transmat[i, j]  # 由于取log操作，這里的*運(yùn)算變成了+運(yùn)算
        fwdlattice[t, j] = _logsumexp(work_buffer) + framelogprob[t, j]

hmmlearn在計(jì)算概率時(shí)都對(duì)結(jié)果進(jìn)行了取log操作，是為了防止序列過長而導(dǎo)致計(jì)算過程中出現(xiàn)數(shù)值下溢的情況，這在PRML的13.2.4節(jié)中有提到。當(dāng)然，代碼中也是實(shí)現(xiàn)了后向算法，可見_do_backward_pass函數(shù)：

for t in range(n_samples - 2, -1, -1):
    for i in range(n_components):
        for j in range(n_components):
            work_buffer[j] = (log_transmat[i, j] + framelogprob[t + 1, j] + bwdlattice[t + 1, j])
        bwdlattice[t, i] = _logsumexp(work_buffer)
  1. 學(xué)習(xí)問題，對(duì)應(yīng)了_baseHMM類中的fit函數(shù)。核心代碼如下：
for i, j in iter_from_X_lengths(X, lengths):
    framelogprob = self._compute_log_likelihood(X[i:j])
    logprob, fwdlattice = self._do_forward_pass(framelogprob)
    curr_logprob += logprob
    bwdlattice = self._do_backward_pass(framelogprob)
    posteriors = self._compute_posteriors(fwdlattice, bwdlattice)
    self._accumulate_sufficient_statistics(stats, X[i:j], framelogprob, posteriors, fwdlattice, bwdlattice)

其中，framelogprob就是發(fā)射概率（如果觀測狀態(tài)是離散型就是矩陣B，如果觀測狀態(tài)是連續(xù)型就是高斯對(duì)數(shù)密度），fwdlattice和bwdlattice分別是前向概率\alpha_t(i)和后向概率\beta_t(i)，posteriors就是P(i_t=q_i, O|\lambda)=\alpha_t(i)\beta_t(i)。

  1. 預(yù)測問題，對(duì)應(yīng)了_baseHMM類中的predict函數(shù)（也可以說是對(duì)應(yīng)decode函數(shù)）。核心部分代碼如下：
for i, j in iter_from_X_lengths(X, lengths):
    logprobij, state_sequenceij = decoder(X[i:j])
    logprob += logprobij
    state_sequence[i:j] = state_sequenceij

其中最重要的維特比算法實(shí)現(xiàn)代碼部分如下：

for t in range(1, n_samples):
    for i in range(n_components):
        for j in range(n_components):
            work_buffer[j] = (log_transmat[j, i] + viterbi_lattice[t - 1, j])
        viterbi_lattice[t, i] = _max(work_buffer) + framelogprob[t, i]

其中，viterbi_lattice保存的就是每個(gè)中間時(shí)刻的隱狀態(tài)的最大累積概率。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容