HMM-Forward/Backward算法实现

作者: IntoTheVoid | 来源:发表于2021-03-03 17:39 被阅读0次

M 个隐状态 - $S^M$
长度为T的观测序列 - $V^T$
转移矩阵 - $A$
发射矩阵 - $B$
初始概率分布 - $\pi$

Evaluation Problem

给定 $\theta, V_M \to 估计 p(V_T|\theta)$ , 其中 $\theta \to s, v, a_{ij}, b_{jk}$

方法：

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

数学表达：

$p(V^T|\theta) = \sum_{r=1}^{R}p(V^T|S_{r}^{T})p(S_{r}^{T}) \\ where \quad S_{r}^{T} = \{s_1(1), s_2(2)... s_r(T)\}$

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

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

以一个具体的示例讲解

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

上述通过隐状态生成的观测序列： $(sun, sun, rain) \to (happy, sad, happy)$ 可以计算生成概率

$p(happy, sad, happy | sun, sun, rain ) = p(happy|sun) * p(sad|sun) * p(happy|rain)$

数学上：

$p(V^T|S_{r}^{T}) = \prod_{t=1}^{T}p(v(t)|s(t))$

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

我们可以计算 $V^T$ 和与之对应的 $S^T$ 的联合概率

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

$p(S^T) = p(sun|initial state) * p(sun|sun) * p(rain|sun) = \prod_{t=1}^{T}p(s(t)|s(t-1))$
$p(V^T|S^T) = p(happy|sun) * p(sad|sun) * p(happy|rain) = \prod_{t=1}^{T}p(v(t)|s(t))$

$p(V^T, S^T) = p(V^T|S^T)p(S^T) = \prod_{t=1}^{T}p(v(t)|s(t)) \prod_{t=1}^{T}p(s(t)|s(t-1))$

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

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

$p(happy,sad,happy|model) = p(happy,sad,happy,sun,sun,sun) + p(happy,sad,happy,sun,sun,rain) + p(happy,sad,happy,sun,rain,rain)+ . . .$

数学上，假设共有R种可能的序列 $R=M^T$

$\begin{equation} \label{eq1} \begin{split} p(V^T|\theta) & = \sum_{All Seq of S}p(V^T, S^T) \\ & = \sum_{All Seq of S}p(V^T|S^T)p(S^T) \\ & = \sum_{r=1}^{R}\prod_{t=1}^{T}p(v(t)|s(t)) \prod_{t=1}^{T}p(s(t)|s(t-1)) \\ & = \sum_{r=1}^{R}\prod_{t=1}^{T}p(v(t)|s(t))p(s(t)|s(t-1)) \end{split} \end{equation}$

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

Forward算法

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

$\alpha(t) = p(v(1)...v(t), s(t)=j) = p(v_{1:t}, s(t)=j)$

当t=1时：
$\begin{equation} \label{eq222} \begin{split} \alpha_{j}(1) & = p(v_{k}(1), s(1)=j) \\ & = p(v_{k}(1)|s(1)=j)p(s(1)=j) \\ & = \pi_{j}p(v_{k}(1)|s(1)=j)\\ & = \pi_{j}b_{jk} \end{split} \end{equation}$

其中 $\pi=初始状态分布$
上式中的 $b_{jk}$ 表示t=1时刻的发射概率

如果通过向量的方式计算取不同的隐状态j，可以通过向量乘积计算，即 $\mathrm{\alpha(1)} = \mathrm{\pi}\mathrm{B_{:,k}}$

当t=2时：

获得t=1的结果后, t=2的计算公式中的一部分需要借助t=1的计算结果
$\begin{equation} \label{eq333} \begin{split} \alpha_{j}(2) & = p(v_{k}(1),v_{k}(2), s(2)=j) \\ & = \sum_{i=1}^{M} p(v_{k}(1), v_{k}(2), s(1)=i, s(2)=j) \\ & = \sum_{i=1}^{M} p(v_{k}(2)|s(2)=j, v_{k}(1), s(1)=i)p(s(2)=j, v_{k}(1), s(1)=i) \\ & = \sum_{i=1}^{M} p(v_{k}(2)|s(2)=j, v_{k}(1), s(1)=i)p(s(2)=j|s(1)=i, v_{k}(1))p(v_{k}(1), s(1)=i) \\ & = \sum_{i=1}^{M} p(v_{k}(2)|s(2)=j)p(s(2)=j|s(1)=i)p(v_{k}(1), s(1)=i) \\ & = p(v_{k}(2)|s(2)=j)\sum_{i=1}^{M} p(s(2)=j|s(1)=i)p(v_{k}(1), s(1)=i) \\ & = b_{jkv(2)}\sum_{i=1}^{M} a_{i2}\alpha_{i}(1) \end{split} \end{equation}$

如果通过向量的方式计算取不同的隐状态j，可以通过向量乘积计算，即 $\mathrm{\alpha(2)} = \mathrm{B_{:, k}} \times (\mathrm{\alpha_{:,1}} \cdot \mathrm{a_{:, 2}})$

其中 $a_{i2} = 转移概率$
$b_{jkv(2)} = 发射概率在t=2时刻$
$\alpha_{i}(1) = 前向概率在t=1时刻$

解释：因为在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

上图如果用通用公式可以得到
$\alpha_{2}(t) = b_{2k}\sum_{i=1}^{M}\alpha_{i}(t-1)a_{i2}$
如果把其他的也写出来
$\alpha_{1}(t) = b_{1k}\sum_{i=1}^{M}\alpha_{i}(t-1)a_{i1}$
$\alpha_{3}(t) = b_{3k}\sum_{i=1}^{M}\alpha_{i}(t-1)a_{i3}$

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

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算法

$\begin{equation} \label{eq6} \begin{split} \beta_{i}(t) & = p(v_{k}(t+1),v_{k}(T)|s(t)=i) \\ & = \sum_{j=0}^{M} p(v_{k}(t+1)... v_{k}(T), s(t+1)=j|s(t)=i) \\ & = \sum_{j=0}^{M} p(v_{k}(t+2)... v_{k}(T)|v_{k}(t+1), s(t+1)=j, s(t)=i)p(v_{k}(t+1),s(t+1)=j|s(t)=i)\\ & = \sum_{j=0}^{M} p(v_{k}(t+2)... v_{k}(T)|v_{k}(t+1), s(t+1)=j, s(t)=i)p(v_{k}(t+1)|s(t+1)=j,s(t)=i)p(s(t+1)=j|s(t)=i)\\ & = \sum_{j=0}^{M} p(v_{k}(t+2)... v_{k}(T)|s(t+1)=j)p(v_{k}(t+1)|s(t+1)=j)p(s(t+1)=j|s(t)=i)\\ & = \sum_{j=0}^{M} \beta_{j}(t+1)b_{jk}(t+1)a_{ij} \end{split} \end{equation}$

其中 $a_{ij}$ 表示t时刻到t+1时刻的转移概率
$b_{jk}(t+1)$ 表示t+1时刻，单词为k的发射概率
$\beta_{j}(t+1)$ 表示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)

HMM-Forward/Backward算法实现

Evaluation Problem

Forward算法

Forward算法代码实现

Backward算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读