HMM-維特比算法理解與實(shí)現(xiàn)(python)

解碼問題

給定觀測序列 \(O=O_1O_2...O_T\) ，模型 \(\lambda (A,B,\pi)\) ，找到最可能的狀態(tài)序列 \(I^?=\{i^?_1,i^?_2,...i^?_T\}\)

近似算法

在每個時刻 \(t\) 選擇最可能的狀態(tài)，得到對應(yīng)的狀態(tài)序列

根據(jù)HMM-前向后向算法計(jì)算時刻 \(t\) 處于狀態(tài) \(i^*_t\) 的概率：

\[i^?_t=argmax[\gamma_t(i)],t=1,2,...T\\ \gamma_t(i) = \frac{\alpha_{i}(t) \beta_{i}(t)}{\sum_{i=1}^{N} \alpha_{i}(t) \beta_{i}(t)} \]

但是無法保證得到的解是全局最優(yōu)解

維特比算法

維特比算法的基礎(chǔ)可以概括為下面三點(diǎn)(來源于吳軍：數(shù)學(xué)之美)：

如果概率最大的路徑經(jīng)過籬笆網(wǎng)絡(luò)的某點(diǎn)，則從起始點(diǎn)到該點(diǎn)的子路徑也一定是從開始到該點(diǎn)路徑中概率最大的。

假定第 t 時刻有 k 個狀態(tài)，從開始到 t 時刻的 k 個狀態(tài)有 k 條最短路徑，而最終的最短路徑必然經(jīng)過其中的一條。

根據(jù)上述性質(zhì)，在計(jì)算第 t+1 時刻的最短路徑時，只需要考慮從開始到當(dāng)前的 k 個狀態(tài)值的最短路徑和當(dāng)前狀態(tài)值到第 t+1 時刻的最短路徑即可。如求 t=3 時的最短路徑，等于求 t=2 時,從起點(diǎn)到當(dāng)前時刻的所有狀態(tài)結(jié)點(diǎn)的最短路徑加上 t=2 到 t=3 的各節(jié)點(diǎn)的最短路徑。

通俗理解維特比算法，對上面三點(diǎn)加深理解

假如你從S和E之間找一條最短的路徑，最簡單的方法就是列出所有可能的路徑 ( \(O(T^N)\) )，選出最小的，顯然時間復(fù)雜度太高。怎么辦？(摘自[3])

使用維特比算法

S到A列的路徑有三種可能： S-A1,S-A2,S-A3 ，如下圖

S-A1,S-A2,S-A3 中必定有一個屬于全局最短路徑。繼續(xù)往右，到了B列

對B1：

會產(chǎn)生3條路徑：

S-A1-B1，S-A2-B1，S-A3-B1

假設(shè) S-A3-B1 是最短的一條，刪掉其他兩條。得到

對B2:

會產(chǎn)生3條路徑：

S-A1-B2，S-A2-B2，S-A3-B2

假設(shè) S-A1-B2 是最短的一條，刪掉其他兩條。得到

對B3：

會產(chǎn)生3條路徑：

S-A1-B3，S-A2-B3，S-A3-B3

假設(shè) S-A2-B3 是最短的一條，刪掉其他兩條。得到

現(xiàn)在我們看看對B列的每個節(jié)點(diǎn)有哪些，回顧維特比算法第二點(diǎn)

假定第 t 時刻有 k 個狀態(tài)，從開始到 t 時刻的 k 個狀態(tài)有 k 條最短路徑，而最終的最短路徑必然經(jīng)過其中的一條

B列有三個節(jié)點(diǎn)，所以會有三條最短路徑，最終的最短路徑一定會經(jīng)過其中一條。如下圖

同理，對C列，會得到三條最短路徑，如下圖

到目前為止，仍然無法確定哪條屬于全局最短。最后，我們繼續(xù)看E節(jié)點(diǎn)

最終發(fā)現(xiàn)最短路徑為 S-A1-B2-C3-E

數(shù)學(xué)描述

在上述過程中，對每一列(每個時刻)會得到對應(yīng)狀態(tài)數(shù)的最短路徑。在數(shù)學(xué)上如何表達(dá)？記錄路徑的 最大概率值 $ \delta_t(i)$ 和對應(yīng)路徑 經(jīng)過的節(jié)點(diǎn) \(\psi_t(i)\) 。

定義在時刻 \(t\) 狀態(tài)為 \(i\) 的所有單條路徑中概率最大值為

\[\delta_{t}(i)=\max _{i_{1}, i_{2}, \ldots, i_{t-1}} P\left(i_{t}=i, i_{t-1}, \ldots, i_{1}, o_{t}, \ldots, o_{1} | \lambda\right), i=1,2, \ldots, N \]

遞推公式

\[\begin{aligned} \delta_{t+1}(i) &=\max _{i_{1}, i_{2}, \ldots, i_{t}} P\left(i_{t+1}=i, i_{t}, \ldots, i_{1}, o_{t+1}, \ldots, o_{1} | \lambda\right) \\ &=\max _{1 \leq j \leq N}\left[\delta_{t}(j) a_{j i}\right] b_{i}\left(o_{t+1}\right), i=1,2, \ldots, N ; t=1,2, \ldots, T-1 \end{aligned} \]

定義在時刻 \(t\) 狀態(tài)為 \(i\) 的所有單條路徑中，概率最大路徑的第 \(t - 1\) 個節(jié)點(diǎn)為

\[\psi_{t}(i)=\arg \max _{1 \leq j \leq N}\left[\delta_{t-1}(j) a_{j i}\right], i=1,2, \ldots, N \]

維特比算法步驟：

? step1：初始化

\[\begin{aligned}&\delta_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right), i=1,2, \ldots, N\\&\psi_{1}(i)=0, i=1,2, \ldots, N\\\end{aligned} \]

? step2：遞推，對 \(t=2,3,...,T\)

\[\delta_{t}(i)=\max _{1 \leq j \leq N}\left[\delta_{t-1}(j) a_{j i}\right] b_{i}\left(o_{t}\right), i=1,2, \ldots, N \\\psi_{t}(i)=\arg \max _{1 \leq j \leq N}\left[\delta_{t-1}(j) a_{j i}\right], i=1,2, \ldots, N \\ \]

? step3：計(jì)算時刻 \(T\) 最大的 $ \delta _T(i) \(,即為最可能隱藏狀態(tài)序列出現(xiàn)的概率。計(jì)算時刻\) T \(最大的\) \psi_T(i) \(,即為時刻\) T$最可能的隱藏狀態(tài)。

\[P^{*}=\max _{1 \leq i \leq N} \delta_{T}(i) \quad i_{T}^{*}=\arg \max _{1 \leq i \leq N} \delta_{T}(i) \]

? step4：最優(yōu)路徑回溯，對 \(t=T-1,...,1\)

\[i_{t}^{*}=\psi_{t+1}\left(i_{t+1}^{*}\right)\\I^*=(i_{1}^{*},i_{2}^{*},...,i_{T}^{*}) \]

代碼實(shí)現(xiàn)

假設(shè)從三個 袋子 {1,2,3} 中 取出 4 個球 O={red,white,red,white} ，模型參數(shù) \(\lambda = (A,B,\pi)\) 如下，計(jì)算狀態(tài)序列，即取出的球來自哪個袋子

#狀態(tài) 1 2 3

A = [[0.5,0.2,0.3],

[0.3,0.5,0.2],

[0.2,0.3,0.5]]

pi = [0.2,0.4,0.4]

# red white

B = [[0.5,0.5],

[0.4,0.6],

[0.7,0.3]]

def hmm_viterbi(A,B,pi,O):

T = len(O)

N = len(A[0])

delta = [[0]*N for _ in range(T)]

psi = [[0]*N for _ in range(T)]

#step1: init

for i in range(N):

delta[0][i] = pi[i]*B[i][O[0]]

psi[0][i] = 0

#step2: iter

for t in range(1,T):

for i in range(N):

temp,maxindex = 0,0

for j in range(N):

res = delta[t-1][j]*A[j][i]

if res>temp:

temp = res

maxindex = j

delta[t][i] = temp*B[i][O[t]]#delta

psi[t][i] = maxindex

#step3: end

p = max(delta[-1])

for i in range(N):

if delta[-1][i] == p:

i_T = i

#step4：backtrack

path = [0]*T

i_t = i_T

for t in reversed(range(T-1)):

i_t = psi[t+1][i_t]

path[t] = i_t

path[-1] = i_T

return delta,psi,path

A = [[0.5,0.2,0.3],[0.3,0.5,0.2],[0.2,0.3,0.5]]

B = [[0.5,0.5],[0.4,0.6],[0.7,0.3]]

pi = [0.2,0.4,0.4]

O = [0,1,0,1]

hmm_viterbi(A,B,pi,O)

結(jié)果

references：

總結(jié)

以上是生活随笔為你收集整理的维特比算法 python_用python实现与理解HMM-维特比算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。