機(jī)器學(xué)習(xí) - 隱馬爾可夫模型

1 隱馬爾可夫模型 - 定義

  • 隱馬爾可夫模型（hidden markov model, HMM）是可用于標(biāo)注問題 [自動(dòng)分詞、詞性標(biāo)注、命名實(shí)體識(shí)別等] 的統(tǒng)計(jì)學(xué)習(xí)模型，描述由隱藏的馬爾可夫鏈隨機(jī)生成觀測序列的過程，屬于生成模型；
  • 隱馬爾可夫模型定義如下：隱馬爾可夫模型是一種有向概率圖模型。描述由一個(gè)隱藏的馬爾科夫鏈生成不可觀測的狀態(tài)隨機(jī)序列（狀態(tài)序列，state sequence），再由各個(gè)狀態(tài)序列生成一個(gè)觀測從而產(chǎn)生觀測隨機(jī)序列（觀測序列，observation sequence）的過程。

2 隱馬爾可夫模型 - 用于中文分詞

2.1 中文分詞例子

  • 輸入：我想去烏魯木齊
  • 輸出：我/S 想/S 去/S 烏/B 魯/M 木/M 齊/E

注意： B表示一個(gè)詞的開始；M表示一個(gè)詞的中間；E表示一個(gè)詞的結(jié)尾；S表示單獨(dú)成詞；

2.2 中文分詞 - 問題建模

  • x 表示輸入的將要分詞的句子（觀測序列）；
  • y 表示輸出的句子分詞結(jié)果（狀態(tài)序列）；
  • 中文分詞問題就是：給定 x 的情況下，找到一個(gè) y 使得條件概率 p(y|x) 最大化；

隱馬爾可夫模型，使用貝葉斯公式將條件概率 p(y|x) 的求解問題，轉(zhuǎn)換成對聯(lián)合概率p(x,y)的求解：
\begin{align} \hat{y} &= \mathop{\arg\max}_{y} p(y|x) \\ &= \mathop{\arg\max}_{y} \frac{p(x,y)}{ p(x)} \\ &= \mathop{\arg\max}_{y} p(x,y) \end{align}
注意：x 是給定的，因此對于任意的 y 而言 p(x) 都是一樣的；

2.3 隱馬爾可夫模型三要素

  • 觀測序列（待分詞的句子）：x_1, x_2, ..., x_L；
  • 狀態(tài)序列（分詞結(jié)果）：y_1, y_2, ..., y_L；
  • 觀測空間 \mathcal{X}，表示所有可能的觀測集合；即中文中所有可能的詞，大小為 M；
  • 狀態(tài)空間 \mathcal{ Y}，表示所有可能的狀態(tài)集合；即分詞標(biāo)簽 B, M, E, S，大小為 N；
  • 初始概率分布 \pi \in \mathbb{R}^{ 1 \times N }：p(y_1 | start)；
  • 發(fā)射概率分布 B \in \mathbb{R}^{ N \times M }：p(x_l | y_l)；
  • 轉(zhuǎn)移概率分布 A \in \mathbb{ R}^{ (N+1) \times (N+1) }：p(y_{l+1} | y_l)；包含一個(gè)結(jié)束符end；
  • 隱馬爾可夫模型： \lambda = (A, B, \pi)
隱馬爾可夫模型.png

3 隱馬爾可夫模型 - 兩個(gè)基本假設(shè)

  1. 齊次馬爾科夫假設(shè)： 即假設(shè)隱藏的馬爾可夫鏈在任意時(shí)刻 t 的狀態(tài)只依賴于其前一時(shí)刻的狀態(tài)，與其他時(shí)刻的狀態(tài)及觀測無關(guān)；
    p(y_t|y_{t-1}, x_{t-1}, ..., y_1, x_1) = p(y_t|y_{t-1})
  2. 觀測獨(dú)立性假設(shè)： 即假設(shè)任意時(shí)刻的觀測只依賴于該時(shí)刻的馬爾可夫鏈的狀態(tài)，與其他觀測及狀態(tài)無關(guān)；
    p(x_t|y_T, x_T, y_{T-1}, x_{T-1}, ..., y_1, x_1) = p(x_t|y_t)

4 隱馬爾可夫模型 - 3個(gè)基本問題

  1. 概率計(jì)算問題： 給定模型 \lambda = (A, B, \pi) 和觀測序列 x_1, x_2, ..., x_L ，計(jì)算在模型 \lambda 下觀測序列 x出現(xiàn)的概率 p(x | \lambda)；
  2. 學(xué)習(xí)問題： 已知觀測序列 x_1, x_2, ..., x_L，估計(jì)模型 \lambda = (A, B, \pi) 參數(shù)，使得在該模型下序列概率 p(x | \lambda) 最大；
  3. 預(yù)測問題： 也稱為解碼問題。已知模型 \lambda = (A, B, \pi) 和觀測序列 x_1, x_2, ..., x_L，求對給定觀測序列條件概率 p(y | x) 最大的狀態(tài)序列 y_1, y_2, ..., y_L。即給定觀測序列，求最有可能對應(yīng)的狀態(tài)序列；

4.1 概率計(jì)算問題

  • 可使用前向（forward）、后向（backward）算法計(jì)算 p(x | \lambda)；為后續(xù)學(xué)習(xí)問題做鋪墊；

4.2 學(xué)習(xí)問題

  • 隱馬爾可夫模型的學(xué)習(xí)，根據(jù)訓(xùn)練數(shù)據(jù)是包括 觀測序列 和對應(yīng)的 狀態(tài)序列 還是只有觀測序列，可以分別由 監(jiān)督學(xué)習(xí) 與 無監(jiān)督學(xué)習(xí) 實(shí)現(xiàn)；

4.2.1 監(jiān)督學(xué)習(xí)方法

  • 使用極大似然估計(jì)法來估計(jì)隱馬爾可夫模型的參數(shù)。
  1. 轉(zhuǎn)移概率 p(y_{l+1} | y_l) 的估計(jì)：
    p(y_{l+1} | y_l) = \frac{Count(y_l, y_{l+1}) }{ Count(y_l) }
  2. 發(fā)射概率 p(x_l | y_l) 的估計(jì)：
    p(x_l | y_l) = \frac{ Count(x_l, y_l) }{ Count(y_l) }
  3. 初始概率 p(y_1 | start) 的估計(jì)：Count(start)，訓(xùn)練語料總數(shù)；
    p(y_1 | start) = \frac{ Count(start, y_1) }{ Count(start) }

4.2.2 無監(jiān)督方法 [Baum-Welch 算法]

  • 由于監(jiān)督學(xué)習(xí)需要使用標(biāo)注的訓(xùn)練數(shù)據(jù)，而人工標(biāo)注訓(xùn)練數(shù)據(jù)往往代價(jià)很高，有時(shí)就會(huì)利用無監(jiān)督學(xué)習(xí)方法；
  • 隱馬爾可夫模型實(shí)際上是一個(gè)含有隱變量的概率模型：p(x|\lambda) = \sum_y {logp(x|y, \lambda) p(y|\lambda)} 它的參數(shù)學(xué)習(xí)可以由 EM算法 實(shí)現(xiàn)。

4.3 預(yù)測問題

  • HMM模型問題定義如下，找出\hat{y}使得聯(lián)合概率p(x,y)最大化； 最直觀的思路是窮舉所有可能的y，但是時(shí)間復(fù)雜度為O(N^L)；一般使用viterbi算法求解，其時(shí)間復(fù)雜度為O(L \times N^2)；
    \begin{align} \hat{y} &= \mathop{\arg\max}_{y} p(y|x) \\ &= \mathop{\arg\max}_{y} \frac{p(x,y)}{ p(x)} \\ &= \mathop{\arg\max}_{y} p(x,y) \end{align}
  • 隱馬爾可夫的預(yù)測問題，一般使用維特比算法求解。維特比算法實(shí)際是動(dòng)態(tài)規(guī)劃（Dynamic Programming）解隱馬爾可夫模型預(yù)測問題，即用動(dòng)態(tài)規(guī)劃求概率最大路徑（最優(yōu)路徑）。這時(shí)一條路徑對應(yīng)著一個(gè)狀態(tài)序列。
  • 維特比算法解HMM預(yù)測問題：

輸入：模型 \lambda = (A, B, \pi)和觀測 X=(x_1, x_2, ..., x_L)；
輸出：最優(yōu)路徑 Y^* = (y_1^*, y_2^*, ..., y_L^*)；
（1）初始化
\begin{align} \delta_1(i) &= \pi_i b_i(x_1), \quad i=1,2,...,N \\ \Psi_1(i) &= 0, \quad i=1,2,...,N \end{align}
（2）開始遞推，對l = 2,3,...,L；注意：a_{ji}表示轉(zhuǎn)移概率，b_i(x_l)表示發(fā)射概率；
\begin{align} \delta_l(i) &= \max_{1 \leq j \leq N} \left[ \delta_{l-1}(j) a_{ji} \right] b_i(x_l), \quad i=1,2,...,N \\ \Psi_l(i) &= \arg\max_{1 \leq j \leq N} \left[ \delta_{l-1}(j) a_{ji} \right], \quad i=1,2,...,N \end{align}
（3）終止
\begin{align} P^* &= \max_{1 \leq i \leq N} \delta_L(i) \\ y_L^* &= \arg\max_{1 \leq i \leq N}\delta_L(i) \end{align}
（4）最優(yōu)路徑回溯，對l = L-1, L-2,..., 1
y_l^* = \Psi_{l+1}(y_{l+1}^*)
求得最優(yōu)路徑：Y^* = (y_1^*, y_2^*, ..., y_L^*)

4.3.1 HMM預(yù)測過程例子

  • 隱馬爾可夫模型的三個(gè)概率矩陣如下：


    HMM三個(gè)概率矩陣.png
  • Viterbi算法解碼過程：維特比算法時(shí)間復(fù)雜度為：O(L \times N^2)
    維特比算法.png

5. HMM算法總結(jié)

  • HMM算法總結(jié)如下：
    （1）HMM對聯(lián)合概率進(jìn)行建模：F(x,y) = P(x,y) = p(y)p(x|y)；
    （2）HMM inference目標(biāo)為：\hat{y} = \mathop{\arg\max}_{y} p(x,y)；
    （3）HMM參數(shù)估計(jì)p(y), p(x|y)：可以采用簡單的統(tǒng)計(jì)方法，或者采用無監(jiān)督式的方式使用EM算法學(xué)習(xí)網(wǎng)絡(luò)參數(shù)；
  • HMM的缺點(diǎn)：HMM算法并不一定能夠保證p(x,\hat{y}) > p(x,y)；
    HMM算法缺點(diǎn).png

參考資料

最后編輯于 ：
?著作權(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)容