• M 个隐状态 -
• 长度为T的观测序列 -
• 转移矩阵 -
• 发射矩阵 -
• 初始概率分布 -

Evaluation Problem

给定 , 其中

方法：

• 找出所有的隐状态，， M是隐状态的数目
• 从所有的隐状态序列中，找到生成观测序列的概率

数学表达：

上面的R=最大数目的关于隐状态的可能序列
因此可以得到，1-T的时间位置上，每个时刻t都可能是上述M个隐状态的任意一个取值，那么这个R的数目等于

为了计算序列长度为T的可观测序列的生成概率， 我们应该采用每个可能的隐藏状态序列，计算它们产生的概率，然后将这些概率相加。

以一个具体的示例讲解

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

上述通过隐状态生成的观测序列：可以计算生成概率

数学上：

但是不幸的是，我们真的不知道隐藏状态的具体顺序，这些顺序会生成可观测变量

我们可以计算和与之对应的的联合概率

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

上述只是特定的一个隐状态序列生成观测序列的例子，那么还有别的观测序列生成这个可观测序列，那么对所有的序列进行上述的计算然后求和

假设只有两种隐状态sun, rain, 那么一共有三个时刻，所以隐状态序列的大小一共有

数学上，假设共有R种可能的序列

但是计算复杂度很高，需要优化， 我们将采用动态规划来克服上述解决方案中的指数计算。 有两种这样的算法，Forward算法，backward算法,可以指数级复杂度降到多项式复杂度。

Forward算法

给定一系列可见状态，则隐马尔可夫模型在特定时间步长t处在特定隐藏状态s的概率是多少。

当t=1时：

• 其中
• 上式中的表示t=1时刻的发射概率

如果通过向量的方式计算取不同的隐状态j，可以通过向量乘积计算，即

当t=2时：

获得t=1的结果后, t=2的计算公式中的一部分需要借助t=1的计算结果

如果通过向量的方式计算取不同的隐状态j，可以通过向量乘积计算，即

• 其中
• 
• 

解释： 因为在t=1时刻的，s(1)有M个状态，所以从s(1)到s(2)需要把M种状态都要考虑进来,在第二步的时候，加了sum符号

进一步得到通用公式

generalized-Equation.jpg

当然也可以通过图示的方式

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

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

如果把其他的也写出来

总结：前向算法的递推关系如下

recursive-forward-equation.jpg

Forward算法代码实现

假设做出如下定义：

• 隐状态共两个,分别是AAA，BBB
• 观测状态取值为三个，分别是0， 1， 2
• 假设已经知道转移矩阵A，和发射矩阵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时刻到t+1时刻的转移概率
• 表示t+1时刻，单词为k的发射概率
• 表示t+1时刻的后向概率

当然也可以通过图示的方式

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)