• M 個(gè)隱狀態(tài) -
• 長(zhǎng)度為T的觀測(cè)序列 -
• 轉(zhuǎn)移矩陣 -
• 發(fā)射矩陣 -
• 初始概率分布 -

Evaluation Problem

給定 , 其中

方法：

• 找出所有的隱狀態(tài)荒揣，辉川， M是隱狀態(tài)的數(shù)目
• 從所有的隱狀態(tài)序列中重父，找到生成觀測(cè)序列的概率

數(shù)學(xué)表達(dá)：

上面的R=最大數(shù)目的關(guān)于隱狀態(tài)的可能序列
因此可以得到枯饿，1-T的時(shí)間位置上番川，每個(gè)時(shí)刻t都可能是上述M個(gè)隱狀態(tài)的任意一個(gè)取值，那么這個(gè)R的數(shù)目等于

為了計(jì)算序列長(zhǎng)度為T的可觀測(cè)序列的生成概率懈糯， 我們應(yīng)該采用每個(gè)可能的隱藏狀態(tài)序列，計(jì)算它們產(chǎn)生的概率单雾，然后將這些概率相加赚哗。

以一個(gè)具體的示例講解

Forward-and-Backward-Algorithm-in-Hidden-Markov-Model-adeveloperdiary.com_.jpg

上述通過(guò)隱狀態(tài)生成的觀測(cè)序列：可以計(jì)算生成概率

數(shù)學(xué)上：

但是不幸的是，我們真的不知道隱藏狀態(tài)的具體順序硅堆，這些順序會(huì)生成可觀測(cè)變量

我們可以計(jì)算和與之對(duì)應(yīng)的的聯(lián)合概率

Forward-and-Backward-Algorithm-in-Hidden-Markov-Model-adeveloperdiary.com-2.jpg

上述只是特定的一個(gè)隱狀態(tài)序列生成觀測(cè)序列的例子屿储，那么還有別的觀測(cè)序列生成這個(gè)可觀測(cè)序列，那么對(duì)所有的序列進(jìn)行上述的計(jì)算然后求和

假設(shè)只有兩種隱狀態(tài)sun, rain, 那么一共有三個(gè)時(shí)刻渐逃，所以隱狀態(tài)序列的大小一共有

數(shù)學(xué)上够掠，假設(shè)共有R種可能的序列

但是計(jì)算復(fù)雜度很高，需要優(yōu)化茄菊， 我們將采用動(dòng)態(tài)規(guī)劃來(lái)克服上述解決方案中的指數(shù)計(jì)算疯潭。 有兩種這樣的算法赊堪，F(xiàn)orward算法，backward算法,可以指數(shù)級(jí)復(fù)雜度降到多項(xiàng)式復(fù)雜度竖哩。

Forward算法

給定一系列可見(jiàn)狀態(tài)哭廉，則隱馬爾可夫模型在特定時(shí)間步長(zhǎng)t處在特定隱藏狀態(tài)s的概率是多少。

當(dāng)t=1時(shí)：

• 其中
• 上式中的表示t=1時(shí)刻的發(fā)射概率

如果通過(guò)向量的方式計(jì)算取不同的隱狀態(tài)j相叁，可以通過(guò)向量乘積計(jì)算遵绰，即

當(dāng)t=2時(shí)：

獲得t=1的結(jié)果后, t=2的計(jì)算公式中的一部分需要借助t=1的計(jì)算結(jié)果

如果通過(guò)向量的方式計(jì)算取不同的隱狀態(tài)j，可以通過(guò)向量乘積計(jì)算增淹，即

• 其中
• 
• 

解釋： 因?yàn)樵趖=1時(shí)刻的椿访，s(1)有M個(gè)狀態(tài)，所以從s(1)到s(2)需要把M種狀態(tài)都要考慮進(jìn)來(lái),在第二步的時(shí)候虑润，加了sum符號(hào)

進(jìn)一步得到通用公式

generalized-Equation.jpg

當(dāng)然也可以通過(guò)圖示的方式

Forward-and-Backward-Algorithm-in-Hidden-Markov-Model-adeveloperdiary.com-4.jpg

上圖如果用通用公式可以得到

如果把其他的也寫出來(lái)

總結(jié)：前向算法的遞推關(guān)系如下

recursive-forward-equation.jpg

Forward算法代碼實(shí)現(xiàn)

假設(shè)做出如下定義：

• 隱狀態(tài)共兩個(gè),分別是AAA成玫，BBB
• 觀測(cè)狀態(tài)取值為三個(gè)，分別是0端辱， 1梁剔， 2
• 假設(shè)已經(jīng)知道轉(zhuǎn)移矩陣A，和發(fā)射矩陣B

init_matrix.jpg

import pandas as pd
import numpy as np

data = pd.read_csv('data/data_python.csv')
 
V = data['Visible'].values

# Transition Probabilities
A = np.array(((0.54, 0.46), (0.49, 0.51)))
 
# Emission Probabilities
B = np.array(((0.16, 0.26, 0.58), (0.25, 0.28, 0.47)))
 
# Equal Probabilities for the initial distribution
π = np.array((0.5, 0.5))

def forward(V, A, B, π):
    alpha = np.zeros((a.shape[0], V.shape[0]))
    alpha[:, 0] = π*B[:, V[0]]
    T = len(V)
    M = A.shape[0]
    for t in range(1, T):
        for j in range(M):
            alpha[j, t] = B[j, V[t]]*alpha[:, t-1]@A[:, j]
    return alpha

alpha = forward(V, A, B, π)

Backward算法

• 其中表示t時(shí)刻到t+1時(shí)刻的轉(zhuǎn)移概率
• 表示t+1時(shí)刻舞蔽，單詞為k的發(fā)射概率
• 表示t+1時(shí)刻的后向概率

當(dāng)然也可以通過(guò)圖示的方式

Forward-and-Backward-Algorithm-in-Hidden-Markov-Model-adeveloperdiary.com-5.jpg

generialized-equation2.jpg

def backward(V, A, B):
    M = A.shape[0]
    T = len(V)
    beta = np.zeros((M, T))
    
    beta[:, -1] = np.ones(M)
    
    for t in range(T-2, 0, -1):
        for j in range(M):
            beta[j, t] = (B[:, V[t+1]]*beta[:, t+1])@A[j, :]
    return beta

beta = backward(V, A, B)