跳至內容

鮑姆-韋爾奇算法

維基百科,自由的百科全書

在電氣工程、計算機科學、統計計算和生物信息學中,鮑姆-韋爾奇算法是用於尋找隱馬爾可夫模型未知參數的最大期望算法,它利用前向-後向算法來計算E-Step的統計信息。

歷史

鮑姆-韋爾奇算法是以其發明者倫納德·埃紹·鮑姆勞埃德·理察·韋爾奇的名字命名的。鮑姆-韋爾奇算法和隱馬爾可夫模型在20世紀60年代末和70年代初由鮑姆和他的同事在國防分析研究所的一系列文章中首次描述。HMMs最初主要應用於語音處理領域。20世紀80年代,HMMs開始成為分析生物系統和信息,特別是遺傳信息的有用工具。此後,它們成為基因組序列概率建模的重要工具。

介紹

隱馬爾可夫模型描述了一組「隱含」變量和可觀測到的離散隨機變量的聯合概率。它依賴於假設:第個隱藏變量只與第個隱含變量相關,而與其他先前的隱藏變量無關,而當前觀測到的狀態僅依賴於當前的隱藏狀態。

鮑姆-韋爾奇算法利用最大期望算法,在給定一組觀測特徵向量的情況下,求出隱馬爾可夫模型參數的最大似然估計。

記離散的隱含隨機變量為,它總共有種狀態(個不同的值)。設與時間無關,得到與時間無關的隨機變量轉移矩陣:


初始的狀態(即)分布由下式給出:

記觀測到的變量為,總共有種取值。同樣假設由隱含變量得到的可觀測變量與時間無關。在時間,由隱含變量得到的可觀察變量的概率是:

由所有可能得的取值,我們可以得到的矩陣,其中屬於所有可能得隱含狀態,屬於所有的可觀測狀態。

給出可觀測序列:

我們可以用描述隱馬爾科夫鏈,鮑姆-韋爾奇算法尋找的局部極大值,也就是能夠使得觀測到的序列出現的概率最大的HMM的參數

算法

初始化參數,可以隨機初始化,或者根據先驗知識初始化。

前向過程

是參數的條件下,觀測的序列是,時刻的狀態是的概率。可以通過遞歸計算:

後向過程

是參數是,在時刻的狀態是的條件下,餘下部分的觀測序列是的概率。

更新

  • 根據貝葉斯公式計算臨時變量。
    • 在給定觀測序列和參數的情況下,在時間狀態是的概率:
    • 在給定觀測序列和參數的情況下,在時間狀態是,在時間狀態是的概率:
    • 的分母一樣,表示給定參數得到觀測序列的概率。
  • 然後更新參數:
    • ,在時間狀態是的概率
    • ,等於期望的從狀態轉換到狀態的數量除以從狀態開始的轉換的總數。
    • ,其中是期望的從狀態得到的觀察值等於的數量除以從 狀態開始的轉換的總數。
  • 重複上面的步驟直到收斂。算法可能過擬合,也不保證收斂到全局最大值。
  • 其中計算相當於最大期望算法的E-Step,而更新的過程相當於最大期望算法的M-Step。


例子

假設我們有一隻會下蛋的雞,每天中午我們都會去拾取雞蛋。而雞是否下蛋依賴於一些未知的隱含狀態,這裡我們簡單的假設只有兩種隱含狀態會決定它是否下蛋。我們不知道這些隱含狀態的初始值,不知道他們之間的轉換概率,也不知道在每種狀態下雞會下蛋的概率。我們隨機初始化他們來開始猜測。

Transition
State 1 State 2
State 1 0.5 0.5
State 2 0.3 0.7
Emission
No Eggs Eggs
State 1 0.3 0.7
State 2 0.8 0.2
Initial
State 1 0.2
State 2 0.8

假設我們得到的觀測序列是(E=eggs, N=no eggs): N, N, N, N, N, E, E, N, N, N。

這樣我們同時也得到了觀測狀態的轉移:NN, NN, NN, NN, NE, EE, EN, NN, NN。

通過上面的信息來重新估計狀態轉移矩陣。

Observed sequence Probability of sequence and state is then Highest Probability of observing that sequence
NN 0.024 0.3584 ,
NN 0.024 0.3584 ,
NN 0.024 0.3584 ,
NN 0.024 0.3584 ,
NE 0.006 0.1344 ,
EE 0.014 0.0490 ,
EN 0.056 0.0896 ,
NN 0.024 0.3584 ,
NN 0.024 0.3584 ,
Total 0.22 2.4234

重新估計的轉移概率為(下表中的"Pseudo probabilities"),重新計算所有的轉移概率,得到下面的轉移矩陣:

Old Transition Matrix
State 1 State 2
State 1 0.5 0.5
State 2 0.3 0.7
New Transition Matrix (Pseudo Probabilities)
State 1 State 2
State 1 0.0598 0.0908
State 2 0.2179 0.9705
New Transition Matrix (After Normalization)
State 1 State 2
State 1 0.3973 0.6027
State 2 0.1833 0.8167

接下來重新估計Emission Matrix:

Observed Sequence Highest probability of observing that sequence
if E is assumed to come from
Highest Probability of observing that sequence
NE 0.1344 , 0.1344 ,
EE 0.0490 , 0.0490 ,
EN 0.0560 , 0.0896 ,
Total 0.2394 0.2730

重新估計從隱含狀態得到觀察結果E的概率是,得到新的Emission Matrix

Old Emission Matrix
No Eggs Eggs
State 1 0.3 0.7
State 2 0.8 0.2
New Emission Matrix (Estimates)
No Eggs Eggs
State 1 0.0876 0.8769
State 2 1.0000 0.7385
New Emission Matrix (After Normalization)
No Eggs Eggs
State 1 0.0908 0.9092
State 2 0.5752 0.4248

為了估計初始狀態的概率,我們分別假設序列的開始狀態是,然後求出最大的概率,再歸一化之後更新初始狀態的概率。

一直重複上面的步驟,直到收斂。

代碼

from hmmlearn import hmm
import numpy as np

X = np.array([1, 1, 1, 1, 1, 0, 0, 1, 1, 1]).reshape(-1, 1)
model = hmm.GaussianHMM(n_components=2, covariance_type='full')
model.fit(X)

model.monitor_.history

# pi
model.startprob_

# state transform matrix
model.transmat_

# emission_matrix
np.power(np.e, model._compute_log_likelihood(np.unique(X).reshape(-1, 1)))