隐马尔可夫模型：观察序列概率估计（前向后向算法）

解码（decoding）问题（估计问题）：给定观察序列$O = O_{1} O_{2} \cdots O_{T}$O=O1​O2​⋯OT​和模型$\mu = (\mathbf{A}, \mathbf{B}, \mathbf{\pi})$μ=(A,B,π)，计算观察序列$O$O的概率，即$P(O | \mu)$P(O∣μ)。

穷举法：对于任意的状态序列$Q = q_{1} q_{2} \cdots q_{T}$Q=q1​q2​⋯qT​，有

$\begin{aligned} P(O| Q ; \mu) & = \prod_{t = 1}^{T - 1} P(O_{t} | q_{t}, q_{t - 1}; \mu) \\ & = b_{q_{1}}(O_{1}) b_{q_{2}}(O_{2}) \cdots b_{q_{T}}(O_{T}) \end{aligned} \tag {6-8}$P(O∣Q;μ)​=t=1∏T−1​P(Ot​∣qt​,qt−1​;μ)=bq1​​(O1​)bq2​​(O2​)⋯bqT​​(OT​)​(6-8)

$\begin{aligned} P(Q ; \mu) & = \pi_{q_{1}} a_{q_{1} q_{2}} a_{q_{2} q_{3}} \cdots a_{q_{T - 1} q_{T}} \end{aligned} \tag {6-9}$P(Q;μ)​=πq1​​aq1​q2​​aq2​q3​​⋯aqT−1​qT​​​(6-9)

$\begin{aligned} P(O ; \mu) & = \sum_{Q} P(O, Q; \mu) \\ & = \sum_{Q} P(O | Q; \mu) P(Q ; \mu) \\ & = \sum_{Q} \left( \pi_{q_{1}} b_{q_{1}}(O_{1}) \prod_{t = 1}^{T - 1} a_{q_{t} q_{t + 1}} b_{q_{t + 1}}(O_{t + 1}) \right) \end{aligned} \tag {6-11}$P(O;μ)​=Q∑​P(O,Q;μ)=Q∑​P(O∣Q;μ)P(Q;μ)=Q∑​(πq1​​bq1​​(O1​)t=1∏T−1​aqt​qt+1​​bqt+1​​(Ot+1​))​(6-11)

该方式的问题是计算时间复杂度呈指数增长，假高模型$\mu = (\mathbf{A}, \mathbf{B}, \mathbf{\pi})$μ=(A,B,π)有$N$N个不同的状态，时间长度为$T$T，则可能状态序列数量为$N^{T}$NT。前向算法（前向计算过程，forward procedure）通过动态规划方式使“指数爆炸”问题可以在时间复杂度为$\mathcal{O}(N^{2} T)$O(N2T)的范围内解决。HMM的动态规划问题–般用格架[Manning、Schitze，1999]（trellis，lattice）组织形式描述。对于一个在某一时间结束在一定状态的HMM，每一个格（结点）记录该HMM所有输出符号的概率，较长子路径的概率可以由较短子路径的概率计算出来。

定义6-1（前向变量$\alpha_{t}(i)$αt​(i)）：在$t$t时刻，HMM输出序列为$O = O_{1} O_{2} \cdots O_{t}$O=O1​O2​⋯Ot​，并且状态为$s_{i}$si​的概率：

$\alpha_{t}(i) = P(O_{1} O_{2} \cdots O_{t}, q_{t} = s_{t}; \mu) \tag {6-12}$αt​(i)=P(O1​O2​⋯Ot​,qt​=st​;μ)(6-12)

由于$P(O ; \mu)$P(O;μ)是在所有状态$q_{T}$qT​下观察到序列$O = O_{1} O_{2} \cdots O_{T}$O=O1​O2​⋯OT​的概率：

$P(O ; \mu) = \sum_{s_{i}} P(O_{1} O_{2} \cdots O_{T}, q_{t} = s_{i}; \mu) = \sum_{i = 1}^{N} \alpha_{T}(i) \tag {6-13}$P(O;μ)=si​∑​P(O1​O2​⋯OT​,qt​=si​;μ)=i=1∑N​αT​(i)(6-13)

因此，对$P(O ; \mu)$P(O;μ)的计算可转变为前向变量$\alpha_{t}(i)$αt​(i)的快速计算。

在格架结构中，$\alpha_{t + 1}(j)$αt+1​(j)存放在结点$(s_{j}, t + 1)$(sj​,t+1)处，表示在已知观察序列$O = O_{1} O_{2} \cdots O_{t + 1}$O=O1​O2​⋯Ot+1​的情况下，从$t$t时刻到达$t + 1$t+1时刻的状态为$s_{j}$sj​的概率。从初始时刻到$t + 1$t+1时刻，HMM到达状态$s_{j}$sj​，并且输出观察序列为$O = O_{1} O_{2} \cdots O_{t + 1}$O=O1​O2​⋯Ot+1​的过程可以分解为两个步骤：

1. 从初始时刻到$t$t时刻，HMM到达状态$s_{i}$si​并输出观察序列$O = O_{1} O_{2} \cdots O_{t}$O=O1​O2​⋯Ot​，概率为$\alpha_{t}(i)$αt​(i)；

2. 从状态$s_{i}$si​转移到状态$s_{j}$sj​，并在状态$s_{j}$sj​输$O_{t + 1}$Ot+1​，概率为$a_{ij} b_{j}(O_{t + 1})$aij​bj​(Ot+1​)。

由于HMM可以从$N$N个不同的$s_{i}$si​转移到$s_{j}$sj​，因此，$t + 1$t+1时刻的前向变量可由$t$t时刻前向变量$\alpha_{t}(1), \alpha_{t}(2), \cdots, \alpha_{t}(N)$αt​(1),αt​(2),⋯,αt​(N)归纳计算：

$\alpha_{t + 1}(j) = \left( \sum_{i = 1}^{N} \alpha_{t}(i) a_{ij} \right) b_{j}(O_{t + 1}) \tag {6-14}$αt+1​(j)=(i=1∑N​αt​(i)aij​)bj​(Ot+1​)(6-14)

前向变量$\alpha_{t}(i)$αt​(i)可采用动态规划方法计算。

算法6-1（前向算法，forward procedure）：

1. 初始化

$\alpha_{1}(i) = \pi_{i} b_{i}(O_{1}), 1 \leq i \leq N$α1​(i)=πi​bi​(O1​),1≤i≤N

2. 归纳计算

$\alpha_{t + 1}(j) = \left( \sum_{i = 1}^{N} \alpha_{t}(i) a_{ij} \right) b_{j}(O_{t + 1}), \ 1 \leq t \leq T - 1$αt+1​(j)=(i=1∑N​αt​(i)aij​)bj​(Ot+1​), 1≤t≤T−1

3. 求和：

$P(O | \mu) = \sum_{i = 1}^{N} \alpha_{T}(i)$P(O∣μ)=i=1∑N​αT​(i)

前向算法总体时间复杂度为$\mathcal{O}(N^{2}T)$O(N2T)。

$P(O ; \mu)$P(O;μ)还可以转变为后向变量$\beta_{t}(i)$βt​(i)，通过动态规划快速计算。

定义6-2（后向变量$\beta_{t}(i)$βt​(i)）：给定模型$\mu = (\mathbf{A}, \mathbf{B}, \mathbf{\pi})$μ=(A,B,π)，并且在$t$t时刻状态为$s_{i}$si​的条件下，HMM输出观察序列$O = O_{t + 1} O_{t + 2} \cdots O_{T}$O=Ot+1​Ot+2​⋯OT​的概率：

$\beta_{t}(i) = P(O_{t + 1} O_{t + 2} \cdots O_{T} | q_{t} = s_{t}; \mu) \tag {6-15}$βt​(i)=P(Ot+1​Ot+2​⋯OT​∣qt​=st​;μ)(6-15)

在$t$t时刻状态为$s_{i}$si​的条件下，HMM输出观察序列为$O = O_{t + 1} O_{t + 2} \cdots O_{T}$O=Ot+1​Ot+2​⋯OT​的过程可以分解为两个步骤：

1. 从$t$t时刻到$t + 1$t+1时刻，HMM由状态$s_{i}$si​转移至状态$s_{j}$sj​，并从状态$s_{j}$sj​输出$O_{t + 1}$Ot+1​，概率为$a_{ij} b_{j}(O_{t + 1})$aij​bj​(Ot+1​)；

2. 在$t + 1$t+1时刻、状态$s_{j}$sj​的条件下，HMM输出观察序列$O = O_{t + 2} \cdots O_{T}$O=Ot+2​⋯OT​，概率为$\beta_{t + 1}(j)$βt+1​(j)。

因此：

$\beta_{t}(i) = \sum_{j = 1}^{N} a_{ij} b_{j}(O_{t + 1}) \beta_{t + 1}(j) \tag {6-16}$βt​(i)=j=1∑N​aij​bj​(Ot+1​)βt+1​(j)(6-16)

算法6-2（后向算法，backward procedure）：

1. 初始化

$\beta_{T}(i) = 1, 1 \leq i \leq N$βT​(i)=1,1≤i≤N

2. 归纳计算

$\beta_{t}(i) = \sum_{j = 1}^{N} a_{ij} b_{j}(O_{t + 1}) \beta_{t + 1}(j), \ T - 1 \geq t \geq 1$βt​(i)=j=1∑N​aij​bj​(Ot+1​)βt+1​(j), T−1≥t≥1

3. 求和：

$P(O | \mu) = \sum_{i = 1}^{N} \pi_{i} b_{i}(O_{1}) \beta_{1}(i)$P(O∣μ)=i=1∑N​πi​bi​(O1​)β1​(i)

后向算法的时间复杂度为$\mathcal{O}(N^{2}T)$O(N2T)。

一般采用前向、后向算法结合的方法计算观察序列的概率：

$\begin{aligned} P(O, q_{t} = s_{i}; \mu) & = P(O_{1} O_{2} \cdots O_{T}, q_{t} = s{i}; \mu) \\ & = P(O_{1} O_{2} \cdots O_{t}, q_{t} = s{i}, O_{t + 1} O_{t + 2} \cdots O_{T}; \mu) \\ & = P(O_{1} O_{2} \cdots O_{t}, q_{t} = s{i}; \mu) P(O_{t + 1} O_{t + 2} \cdots O_{T} | O_{1} O_{2} \cdots O_{t}, q_{t} = s{i}; \mu) \\ & = P(O_{1} O_{2} \cdots O_{t}, q_{t} = s{i}; \mu) P(O_{t + 1} O_{t + 2} \cdots O_{T} | q_{t} = s{i}; \mu) \\ & = \alpha_{t}(i) \beta_{t}(i) \end{aligned} \tag {6-17}$P(O,qt​=si​;μ)​=P(O1​O2​⋯OT​,qt​=si;μ)=P(O1​O2​⋯Ot​,qt​=si,Ot+1​Ot+2​⋯OT​;μ)=P(O1​O2​⋯Ot​,qt​=si;μ)P(Ot+1​Ot+2​⋯OT​∣O1​O2​⋯Ot​,qt​=si;μ)=P(O1​O2​⋯Ot​,qt​=si;μ)P(Ot+1​Ot+2​⋯OT​∣qt​=si;μ)=αt​(i)βt​(i)​(6-17)

因此

$\begin{aligned} P(O; \mu) = \sum_{i = 1}^{N} \alpha_{t}(i) \beta_{t}(i), \ 1 \leq t \leq T \end{aligned} \tag {6-18}$P(O;μ)=i=1∑N​αt​(i)βt​(i), 1≤t≤T​(6-18)