- 引言
- 回顾：隐马尔可夫模型
- 概念介绍
- 模型参数表示
- 隐马尔可夫模型的核心假设
- 关于 P ( O ∣ λ ) P(\mathcal O \mid \lambda) P(O∣λ)求解过程中的问题
- 前向算法
上一节对隐马尔可夫模型(Hidden Markov Model,HMM)进行了归纳介绍。本节将详细介绍使用前向算法(Forward Algorithm)对处理求值(Evaluation)问题。
回顾：隐马尔可夫模型隐马尔可夫模型是一个动态模型(Dynamic Model)。其主要特点是系统状态(System State)任意一个状态元素(隐变量)，其取值范围是离散的。 以系统状态中 t t t时刻的状态元素 Z ( t ) \mathcal Z^{(t)} Z(t)为例，存在 K \mathcal K K个离散结果供 Z ( t ) \mathcal Z^{(t)} Z(t)进行选择。即： Z ( t ) ∈ { z 1 , z 2 , ⋯ , z K } \mathcal Z^{(t)} \in \{z_1,z_2,\cdots,z_{\mathcal K}\} Z(t)∈{z1,z2,⋯,zK}
概念介绍隐马尔可夫模型由状态序列与观测序列两部分构成： I = { i 1 , i 2 , ⋯ , i t , i t + 1 , ⋯ , i T } O = { o 1 , o 2 , ⋯ , o t , o t + 1 , ⋯ , o T } \mathcal I = \{i_1,i_2,\cdots,i_t,i_{t+1},\cdots,i_T\} \\ \mathcal O = \{o_1,o_2,\cdots,o_t,o_{t+1},\cdots,o_T\} I={i1,i2,⋯,it,it+1,⋯,iT}O={o1,o2,⋯,ot,ot+1,⋯,oT} 其中状态序列中状态变量 i t ∈ I i_{t} \in \mathcal I it∈I的取值范围是离散的，并且状态变量可取到的状态值集合 Q \mathcal Q Q表示如下： Q = { q 1 , q 2 , ⋯ , q K } \mathcal Q = \{q_1,q_2,\cdots,q_{\mathcal K}\} Q={q1,q2,⋯,qK} 观测序列中的观测变量 o t ∈ O o_t \in \mathcal O ot∈O的取值范围同样是离散的，并且观测变量可取到的观测值集合 V \mathcal V V表示如下： V = { v 1 , v 2 , ⋯ , v M } \mathcal V = \{v_1,v_2,\cdots,v_\mathcal M\} V={v1,v2,⋯,vM}
模型参数表示隐马尔可夫模型的模型参数 λ \lambda λ具体包含三项： λ = ( π , A , B ) \lambda = (\pi,\mathcal A,\mathcal B) λ=(π,A,B)
- π \pi π称作 初始概率分布(基于状态变量)，是一个 K \mathcal K K维向量。向量各元素表示初始状态变量 i 1 i_1 i1取到各离散结果 q 1 , q 2 , ⋯ , q K q_1,q_2,\cdots,q_{\mathcal K} q1,q2,⋯,qK 的概率值。即： π = ( P ( i 1 = q 1 ) P ( i 1 = q 2 ) ⋮ P ( i 1 = q K ) ) K × 1 ∑ k = 1 K P ( i 1 = q k ) = 1 \pi = \begin{pmatrix}P(i_1 = q_1) \\ P(i_1 = q_2) \\ \vdots \\ P(i_1 = q_{\mathcal K})\end{pmatrix}_{\mathcal K \times 1} \sum_{k=1}^{\mathcal K} P(i_1 = q_k) = 1 π=⎝ ⎛P(i1=q1)P(i1=q2)⋮P(i1=qK)⎠ ⎞K×1k=1∑KP(i1=qk)=1
- A \mathcal A A称作状态转移矩阵。具体表示如下： A = [ a i j ] K × K \mathcal A = [a_{ij}]_{\mathcal K \times \mathcal K} A=[aij]K×K 其中 a i j a_{ij} aij表示 t t t时刻下的状态变量 i t = q i i_t = q_i it=qi的条件下， t + 1 t+1 t+1时刻的状态变量 i t + 1 = q j i_{t+1}=q_j it+1=qj的概率。数学符号表示如下： a i j = P ( i t + 1 = q j ∣ i t = q i ) i , j ∈ { 1 , 2 , ⋯ , K } a_{ij} = P(i_{t+1} = q_j \mid i_t = q_i) \quad i,j \in \{1,2,\cdots,\mathcal K\} aij=P(it+1=qj∣it=qi)i,j∈{1,2,⋯,K}
- B \mathcal B B称作发射矩阵。具体表示如下： B = [ b j ( k ) ] K × M \mathcal B = [b_j(k)]_{\mathcal K\times \mathcal M} B=[bj(k)]K×M 其中 b j ( k ) b_j(k) bj(k)表示 t t t时刻下状态变量 i t = q j i_t=q_j it=qj的条件下， t t t时刻下的观测变量 o t = v k o_t=v_k ot=vk的概率。数学符号表示如下： b j ( k ) = P ( o t = v k ∣ i t = q j ) j ∈ { 1 , 2 , ⋯ , K } ; k ∈ { 1 , 2 , ⋯ , M } b_j(k) = P(o_t = v_k \mid i_t = q_j) \quad j \in \{1,2,\cdots,\mathcal K\};k \in \{1,2,\cdots,\mathcal M\} bj(k)=P(ot=vk∣it=qj)j∈{1,2,⋯,K};k∈{1,2,⋯,M}
- 齐次马尔可夫假设： 某时刻 t t t条件下，状态变量 i t i_t it的后验概率，只和前一时刻状态变量 i t − 1 i_{t-1} it−1相关，与其他变量无关； 数学符号表达如下： P ( i t ∣ i t − 1 , ⋯ , i 1 , o t − 1 , o 1 ) = P ( i t ∣ i t − 1 ) P(i_{t} \mid i_{t-1},\cdots,i_1,o_{t-1},o_1) = P(i_t \mid i_{t-1}) P(it∣it−1,⋯,i1,ot−1,o1)=P(it∣it−1)
- 观测独立性假设： 某时刻 t t t条件下，观测变量 o t o_t ot的后验概率，只和 t t t时刻的状态变量 i t i_t it相关，与其他变量无关。 数学符号表达如下： P ( o t ∣ i t , ⋯ , i 1 , o t − 1 , ⋯ , o 1 ) = P ( o t ∣ i t ) P(o_t \mid i_t,\cdots,i_1,o_{t-1},\cdots,o_1) = P(o_t \mid i_t) P(ot∣it,⋯,i1,ot−1,⋯,o1)=P(ot∣it)
求值问题描述：已知给定参数
λ
\lambda
λ的隐马尔可夫模型，求解观测序列
O
=
{
o
1
,
o
2
,
⋯
,
o
T
}
\mathcal O = \{o_1,o_2,\cdots,o_T\}
O={o1,o2,⋯,oT}的后验概率结果
P
(
O
∣
λ
)
P(\mathcal O \mid \mathcal \lambda)
P(O∣λ)。 或者可理解为’观测序列‘
O
=
{
o
1
,
o
2
,
⋯
,
o
T
}
\mathcal O = \{o_1,o_2,\cdots,o_T\}
O={o1,o2,⋯,oT}通过HMM模型的计算所发生的概率。
首先，类似于高斯混合模型引入隐变量的方式，将将状态变量
I
\mathcal I
I引入到
P
(
O
∣
λ
)
P(\mathcal O \mid \lambda)
P(O∣λ)： 因为'状态变量'
I
\mathcal I
I的取值范围是离散的，因此积分方式是
∑
\sum
∑;
P
(
O
∣
λ
)
=
∑
I
P
(
I
,
O
∣
λ
)
=
∑
I
P
(
O
∣
I
,
λ
)
P
(
I
∣
λ
)
\begin{aligned} P(\mathcal O \mid \lambda) & = \sum_{\mathcal I} P(\mathcal I,\mathcal O \mid \lambda) \\ & = \sum_{\mathcal I} P(\mathcal O \mid \mathcal I,\lambda)P(\mathcal I \mid \lambda) \end{aligned}
P(O∣λ)=I∑P(I,O∣λ)=I∑P(O∣I,λ)P(I∣λ)
- 观察
P
(
I
∣
λ
)
P(\mathcal I \mid \lambda)
P(I∣λ)，它是关于状态变量
I
\mathcal I
I的概率分布。因此使用 状态转移矩阵
A
\mathcal A
A中的元素 进行表示：
- 将 P ( I ∣ λ ) P(\mathcal I \mid \lambda) P(I∣λ)展开成 P ( i 1 , i 2 , ⋯ , i T ∣ λ ) P(i_1,i_2,\cdots,i_{T}\mid \lambda) P(i1,i2,⋯,iT∣λ)的格式，并将其看作联合概率分布的形式，分解成条件概率的形式： P ( I ∣ λ ) = P ( i 1 , i 2 , ⋯ , i T ∣ λ ) = P ( i T ∣ i 1 , i 2 , ⋯ , i T − 1 , λ ) ⋅ P ( i 1 , i 2 , ⋯ , i T − 1 ∣ λ ) \begin{aligned} P(\mathcal I \mid \lambda) & = P(i_1,i_2,\cdots,i_{T}\mid \lambda) \\ & = P(i_T \mid i_1,i_2,\cdots,i_{T-1},\lambda) \cdot P(i_1,i_2,\cdots,i_{T-1} \mid \lambda) \end{aligned} P(I∣λ)=P(i1,i2,⋯,iT∣λ)=P(iT∣i1,i2,⋯,iT−1,λ)⋅P(i1,i2,⋯,iT−1∣λ)
- 观察上述公式的后项 P ( i 1 , i 2 , ⋯ , i T − 1 ∣ λ ) P(i_1,i_2,\cdots,i_{T-1} \mid \lambda) P(i1,i2,⋯,iT−1∣λ)，它实际上就是个缩小版的 P ( I ∣ λ ) P(\mathcal I \mid \lambda) P(I∣λ)，和 P ( I ∣ λ ) P(\mathcal I \mid \lambda) P(I∣λ)相比，只少了一个 i T i_{T} iT项。因此，可以将 P ( I ∣ λ ) P(\mathcal I \mid \lambda) P(I∣λ)看成迭代式子。即： P ( I ∣ λ ) = P ( i T ∣ i 1 , i 2 , ⋯ , i T − 1 , λ ) ⋅ P ( i 1 , i 2 , ⋯ , i T − 1 ∣ λ ) = P ( i T ∣ i 1 , i 2 , ⋯ , i T − 1 , λ ) ⋅ P ( i T − 1 ∣ i 1 , i 2 , ⋯ , i T − 2 , λ ) ⋅ P ( i 1 , i 2 , ⋯ , i T − 2 ∣ λ ) = ⋯ = P ( i T ∣ i 1 , i 2 , ⋯ , i T − 1 , λ ) ⋅ P ( i T − 1 ∣ i 1 , i 2 , ⋯ , i T − 2 , λ ) ⋯ P ( i 2 ∣ i 1 , λ ) ⋅ P ( i 1 ∣ λ ) \begin{aligned} P(\mathcal I \mid \lambda) & = P(i_T \mid i_1,i_2,\cdots,i_{T-1},\lambda) \cdot P(i_1,i_2,\cdots,i_{T-1} \mid \lambda) \\ & = P(i_T \mid i_1,i_2,\cdots,i_{T-1},\lambda) \cdot P(i_{T-1} \mid i_1,i_2,\cdots,i_{T-2},\lambda)\cdot P(i_1,i_2,\cdots,i_{T-2} \mid \lambda)\\ & = \cdots \\ & = P(i_T \mid i_1,i_2,\cdots,i_{T-1},\lambda) \cdot P(i_{T-1} \mid i_1,i_2,\cdots,i_{T-2},\lambda) \cdots P(i_2 \mid i_1,\lambda) \cdot P(i_1 \mid \lambda) \end{aligned} P(I∣λ)=P(iT∣i1,i2,⋯,iT−1,λ)⋅P(i1,i2,⋯,iT−1∣λ)=P(iT∣i1,i2,⋯,iT−1,λ)⋅P(iT−1∣i1,i2,⋯,iT−2,λ)⋅P(i1,i2,⋯,iT−2∣λ)=⋯=P(iT∣i1,i2,⋯,iT−1,λ)⋅P(iT−1∣i1,i2,⋯,iT−2,λ)⋯P(i2∣i1,λ)⋅P(i1∣λ)
- 观察上式中的每一项，我们都可以使用 齐次马尔可夫假设 对每一项进行简化。例如： P ( i T ∣ i 1 , i 2 , ⋯ , i T − 1 , λ ) = P ( i T ∣ i T − 1 ) P(i_T \mid i_1,i_2,\cdots,i_{T-1},\lambda) = P(i_T \mid i_{T-1}) P(iT∣i1,i2,⋯,iT−1,λ)=P(iT∣iT−1)，以此类推。 其中最后一项 P ( i 1 ∣ λ ) P(i_1 \mid \lambda) P(i1∣λ)，即初始概率分布 π \pi π。最终 P ( I ∣ λ ) P(\mathcal I \mid \lambda) P(I∣λ)表示如下： P ( I ∣ λ ) = P ( i T ∣ i T − 1 ) ⋅ P ( i T − 1 ∣ i T − 2 ) ⋯ P ( i 2 ∣ i 1 ) ⋅ π P(\mathcal I \mid \lambda) = P(i_T \mid i_{T-1}) \cdot P(i_{T-1} \mid i_{T-2}) \cdots P(i_2 \mid i_1) \cdot \pi P(I∣λ)=P(iT∣iT−1)⋅P(iT−1∣iT−2)⋯P(i2∣i1)⋅π
- 观察状态转移过程图，
P
(
i
T
∣
i
T
−
1
)
P(i_T \mid i_{T-1})
P(iT∣iT−1)使用 状态转移矩阵
A
\mathcal A
A中的元素进行表示：
P
(
I
∣
λ
)
=
a
i
T
−
1
,
i
T
⋅
a
i
T
−
2
,
i
T
−
1
⋯
a
i
1
,
i
2
⋅
π
=
π
⋅
∏
t
=
2
T
a
i
t
−
1
,
i
t
\begin{aligned} P(\mathcal I \mid \lambda) & = a_{i_{T-1},i_{T}} \cdot a_{i_{T-2},i_{T-1}} \cdots a_{i_1,i_2} \cdot \pi \\ & = \pi \cdot \prod_{t=2}^{T}a_{i_{t-1},i_{t}} \end{aligned}
P(I∣λ)=aiT−1,iT⋅aiT−2,iT−1⋯ai1,i2⋅π=π⋅t=2∏Tait−1,it
- 继续观察
P
(
O
∣
I
,
λ
)
P(\mathcal O \mid \mathcal I,\lambda)
P(O∣I,λ)，和
P
(
I
∣
λ
)
P(\mathcal I \mid \lambda)
P(I∣λ)相似，但依据的是 观测独立性假设。
- P ( O ∣ I , λ ) P(\mathcal O \mid \mathcal I,\lambda) P(O∣I,λ)中的 O , I \mathcal O,\mathcal I O,I进行展开，得到如下形式： P ( O ∣ I , λ ) = P ( o 1 , ⋯ , o T ∣ i 1 , ⋯ , i T , λ ) = P ( o T ∣ o 1 , ⋯ , o T − 1 , i 1 , ⋯ , i T , λ ) ⋅ P ( o 1 , ⋯ , o T − 1 , i 1 , ⋯ , i T ∣ λ ) \begin{aligned} P(\mathcal O \mid \mathcal I ,\lambda) & = P(o_1,\cdots,o_T \mid i_1,\cdots,i_T,\lambda) \\ & = P(o_T \mid o_1,\cdots,o_{T-1},i_1,\cdots,i_{T},\lambda) \cdot P(o_1,\cdots,o_{T-1},i_1,\cdots,i_{T} \mid \lambda) \end{aligned} P(O∣I,λ)=P(o1,⋯,oT∣i1,⋯,iT,λ)=P(oT∣o1,⋯,oT−1,i1,⋯,iT,λ)⋅P(o1,⋯,oT−1,i1,⋯,iT∣λ)
- 将上式展开成迭代形式： P ( O ∣ I , λ ) = P ( o T ∣ o 1 , ⋯ , o T − 1 , i 1 , ⋯ , i T , λ ) ⋅ P ( o T − 1 ∣ o 1 , ⋯ , o T − 2 , i 1 , ⋯ , i T , λ ) ⋯ P ( o 1 ∣ i 1 , ⋯ i T , λ ) P(\mathcal O \mid \mathcal I ,\lambda) = P(o_T \mid o_1,\cdots,o_{T-1},i_1,\cdots,i_{T},\lambda) \cdot P(o_{T-1} \mid o_1,\cdots,o_{T-2},i_1,\cdots,i_{T},\lambda) \cdots P(o_1 \mid i_1,\cdots i_T,\lambda) P(O∣I,λ)=P(oT∣o1,⋯,oT−1,i1,⋯,iT,λ)⋅P(oT−1∣o1,⋯,oT−2,i1,⋯,iT,λ)⋯P(o1∣i1,⋯iT,λ)
- 根据观测独立性假设，上述迭代形式表示如下： P ( o T ∣ i T ) ⋅ P ( o T − 1 ∣ i T − 1 ) ⋯ P ( o 1 ∣ i 1 ) P(o_T \mid i_T) \cdot P(o_{T-1} \mid i_{T-1}) \cdots P(o_1 \mid i_1) P(oT∣iT)⋅P(oT−1∣iT−1)⋯P(o1∣i1)
- 基于发射过程图，
P
(
o
T
∣
i
T
)
P(o_T \mid i_T)
P(oT∣iT)使用发射矩阵
B
\mathcal B
B结果进行表示：
P
(
O
∣
I
,
λ
)
=
b
i
1
(
o
1
)
⋅
b
i
2
(
o
2
)
⋯
b
i
T
(
o
T
)
=
∏
t
=
1
T
b
i
t
(
o
t
)
\begin{aligned} P(\mathcal O \mid \mathcal I, \lambda) & = b_{i_1}(o_1) \cdot b_{i_2}(o_2) \cdots b_{i_T}(o_T) \\ & = \prod_{t=1}^T b_{i_t}(o_t) \end{aligned}
P(O∣I,λ)=bi1(o1)⋅bi2(o2)⋯biT(oT)=t=1∏Tbit(ot)
至此， P ( O ∣ λ ) P(\mathcal O \mid \lambda) P(O∣λ)可以表示如下： P ( O ∣ λ ) = ∑ I P ( O ∣ I , λ ) P ( I ∣ λ ) = ∑ I π ⋅ ∏ t = 2 T a i t − 1 , i t ⋅ ∏ t = 1 T b i t ( o t ) \begin{aligned} P(\mathcal O \mid \lambda) & = \sum_{\mathcal I} P(\mathcal O \mid \mathcal I,\lambda)P(\mathcal I \mid \lambda) \\ & = \sum_{\mathcal I} \pi \cdot \prod_{t=2}^T a_{i_{t-1},i_{t}} \cdot\prod_{t=1}^T b_{i_t}(o_t) \end{aligned} P(O∣λ)=I∑P(O∣I,λ)P(I∣λ)=I∑π⋅t=2∏Tait−1,it⋅t=1∏Tbit(ot) 将上式中的 ∑ I \sum_{\mathcal I} ∑I部分展开，展开结果如下： P ( O ∣ λ ) = ∑ i 1 ⋯ ∑ i T ( π ⋅ ∏ t = 2 T a i t − 1 , i t ⋅ ∏ t = 1 T b i t ( o t ) ) P(\mathcal O \mid \lambda) = \sum_{i_1} \cdots\sum_{i_T}\left(\pi \cdot \prod_{t=2}^T a_{i_{t-1},i_{t}} \cdot\prod_{t=1}^T b_{i_t}(o_t)\right) P(O∣λ)=i1∑⋯iT∑(π⋅t=2∏Tait−1,it⋅t=1∏Tbit(ot)) 观察，大括号内的项均可以通过查找初始概率分布 π \pi π，状态转移矩阵 A \mathcal A A，发射矩阵 B \mathcal B B 得到。但括号外的 ∑ i 1 ⋯ ∑ i T \sum_{i_1} \cdots\sum_{i_T} ∑i1⋯∑iT中的每一项由于状态变量 i t ( t = 1 , 2 , ⋯ , T ) i_t(t=1,2,\cdots,T) it(t=1,2,⋯,T)均存在 K \mathcal K K种选择，因此上式的时间复杂度至少为 O ( K T ) O(\mathcal K^{T}) O(KT)。 即：状态序列 { i 1 , i 2 , ⋯ , i T } \{i_1,i_2,\cdots,i_T\} {i1,i2,⋯,iT}随着序列长度 T T T的增加，时间复杂度指数级别增长。下面将介绍关于求解 P ( O ∣ λ ) P(\mathcal O \mid \lambda) P(O∣λ)的优化算法——前向算法(Forward Algorithm)。
前向算法重新观察隐马尔可夫模型的概率图形式： 
- 我们记 α t ( i ) \alpha_t(i) αt(i)表示 在 t t t时刻，状态变量 i t = q i i_t = q_i it=qi的条件下， t t t时刻之前的所有观测变量(含 t t t时刻) o 1 , o 2 , ⋯ , o t o_1,o_2,\cdots,o_t o1,o2,⋯,ot与 i t i_t it的联合概率分布。数学符号表示如下： α t ( i ) = P ( o 1 , ⋯ o t , i t = q i ∣ λ ) \alpha_t(i) = P(o_1,\cdots o_t,i_t = q_i \mid \lambda) αt(i)=P(o1,⋯ot,it=qi∣λ)
- 基于上式，
T
T
T时刻的
α
T
(
i
)
\alpha_{T}(i)
αT(i)表示如下：
即图中‘红色框’包含的变量。α T ( i ) = P ( o 1 , ⋯ o T , i T = q i ∣ λ ) = P ( O , i T = q i ∣ λ ) \begin{aligned} \alpha_T(i) &= P(o_1,\cdots o_T,i_T = q_i \mid \lambda) \\ & =P(\mathcal O,i_T = q_i \mid \lambda) \end{aligned} αT(i)=P(o1,⋯oT,iT=qi∣λ)=P(O,iT=qi∣λ) - 如果求解
P
(
O
∣
λ
)
P(\mathcal O \mid \lambda)
P(O∣λ)，只需求解
α
T
(
i
)
\alpha_T(i)
αT(i)，然后将
i
T
i_T
iT执行条件概率密度积分即可。数学符号表示如下：
同上,i T i_T iT自身存在K \mathcal K K种选择。P ( O ∣ λ ) = ∑ i T P ( O , i T = q i ∣ λ ) = ∑ i = 1 K P ( O , i T = q i ∣ λ ) = ∑ i = 1 K α T ( i ) \begin{aligned} P(\mathcal O \mid \lambda) & = \sum_{i_T} P(\mathcal O,i_T = q_i \mid \lambda) \\ & = \sum_{i=1}^{\mathcal K} P(\mathcal O,i_T = q_i \mid \lambda) \\ & = \sum_{i=1}^{\mathcal K} \alpha_T(i) \end{aligned} P(O∣λ)=iT∑P(O,iT=qi∣λ)=i=1∑KP(O,iT=qi∣λ)=i=1∑KαT(i)
基于上述对 α t ( i ) \alpha_t(i) αt(i)的描述，我们尝试 观察 α t + 1 ( j ) \alpha_{t+1}(j) αt+1(j)和 α t ( i ) \alpha_t(i) αt(i)之间的关系。
- α t + 1 ( j ) \alpha_{t+1}(j) αt+1(j)具体表达如下： α t + 1 ( j ) = P ( o 1 , ⋯ , o t , o t + 1 , i t + 1 = q j ∣ λ ) \alpha_{t+1}(j) = P(o_1,\cdots,o_t,o_{t+1},i_{t+1} = q_j \mid \lambda) αt+1(j)=P(o1,⋯,ot,ot+1,it+1=qj∣λ)
- 但是上式中并不包含 i t i_t it项，因此，使用条件概率密度积分的方式将 i t i_t it加到公式中： α t + 1 ( j ) = ∑ i t P ( o 1 , ⋯ , o t , o t + 1 , i t = q i , i t + 1 = q j ∣ λ ) = ∑ i = 1 K P ( o 1 , ⋯ , o t , o t + 1 , i t = q i , i t + 1 = q j ∣ λ ) \begin{aligned} \alpha_{t+1}(j) & = \sum_{i_t} P(o_1,\cdots,o_t,o_{t+1},i_t = q_i,i_{t+1} = q_j \mid \lambda) \\ & = \sum_{i=1}^{\mathcal K} P(o_1,\cdots,o_t,o_{t+1},i_t = q_i,i_{t+1} = q_j \mid \lambda) \end{aligned} αt+1(j)=it∑P(o1,⋯,ot,ot+1,it=qi,it+1=qj∣λ)=i=1∑KP(o1,⋯,ot,ot+1,it=qi,it+1=qj∣λ)
- 但上述式子中仍包含 o t + 1 o_{t+1} ot+1项。因此，使用条件概率将上式分解，提出 o t + 1 o_{t+1} ot+1： ∑ i = 1 K [ P ( o t + 1 ∣ o 1 , ⋯ , o t , i t = q i , i t + 1 = q j , λ ) ⋅ P ( o 1 , ⋯ , o t , i t = q i , i t + 1 = q j ∣ λ ) ] \sum_{i=1}^{\mathcal K} \left[P(o_{t+1} \mid o_1,\cdots,o_t,i_t = q_i,i_{t+1} = q_j,\lambda) \cdot P(o_1,\cdots,o_t,i_t = q_i,i_{t+1} = q_j \mid \lambda)\right] i=1∑K[P(ot+1∣o1,⋯,ot,it=qi,it+1=qj,λ)⋅P(o1,⋯,ot,it=qi,it+1=qj∣λ)] 观察中括号内的第一项，可以使用观测独立性假设进行处理。并将上式改写如下形式： ∑ i = 1 K [ P ( o t + 1 ∣ i t + 1 = q j , λ ) ⋅ P ( o 1 , ⋯ , o t , i t = q i , i t + 1 = q j ∣ λ ) ] \sum_{i=1}^{\mathcal K} \left[P(o_{t+1} \mid i_{t+1}=q_j,\lambda) \cdot P(o_1,\cdots,o_t,i_t = q_i,i_{t+1} = q_j \mid \lambda)\right] i=1∑K[P(ot+1∣it+1=qj,λ)⋅P(o1,⋯,ot,it=qi,it+1=qj∣λ)]
- 此时继续观察中括号内的后项： P ( o 1 , ⋯ , o t , i t = q i , i t + 1 = q j ∣ λ ) P(o_1,\cdots,o_t,i_t = q_i,i_{t+1} = q_j \mid \lambda) P(o1,⋯,ot,it=qi,it+1=qj∣λ)，它和 α t ( i ) \alpha_t(i) αt(i)仅差一项： i t + 1 = q j i_{t+1} = q_j it+1=qj。 和 o t + 1 o_{t+1} ot+1项处理方式相同，继续使用条件概率将上式分解，提出 i t + 1 i_{t+1} it+1： P ( o 1 , ⋯ , o t , i t = q i , i t + 1 = q j ∣ λ ) = P ( i t + 1 = q j ∣ o 1 , ⋯ , o t , i t = q i , λ ) ⋅ P ( o 1 , ⋯ , o t , i t = q i ∣ λ ) \begin{aligned} & P(o_1,\cdots,o_t,i_t = q_i,i_{t+1} = q_j \mid \lambda) \\ & = P(i_{t+1} = q_j \mid o_1,\cdots,o_t,i_t = q_i,\lambda) \cdot P(o_1,\cdots,o_t,i_t = q_i\mid \lambda) \end{aligned} P(o1,⋯,ot,it=qi,it+1=qj∣λ)=P(it+1=qj∣o1,⋯,ot,it=qi,λ)⋅P(o1,⋯,ot,it=qi∣λ) 观察上述式子第一项，可以使用齐次马尔科夫假设进行处理。并将上式改写成如下形式： P ( i t + 1 = q j ∣ i t = q i , λ ) ⋅ P ( o 1 , ⋯ , o t , i t = q i ∣ λ ) = P ( i t + 1 = q j ∣ i t = q i , λ ) ⋅ α t ( i ) P(i_{t+1} = q_j \mid i_t = q_i,\lambda) \cdot P(o_1,\cdots,o_t,i_t = q_i\mid \lambda) = P(i_{t+1} = q_j \mid i_t = q_i,\lambda) \cdot \alpha_{t}(i) P(it+1=qj∣it=qi,λ)⋅P(o1,⋯,ot,it=qi∣λ)=P(it+1=qj∣it=qi,λ)⋅αt(i)
至此，整理 α t + 1 ( j ) \alpha_{t+1}(j) αt+1(j)和 α t ( i ) \alpha_{t}(i) αt(i)之间的关联关系： α t + 1 ( j ) = ∑ i = 1 K [ P ( o t + 1 ∣ i t + 1 = q j ) ⋅ P ( i t + 1 = q j ∣ i t = q i , λ ) ⋅ α t ( i ) ] \alpha_{t+1}(j) = \sum_{i=1}^{\mathcal K} \left[P(o_{t+1} \mid i_{t+1}=q_j) \cdot P(i_{t+1} = q_j \mid i_t = q_i,\lambda) \cdot \alpha_{t}(i)\right] αt+1(j)=i=1∑K[P(ot+1∣it+1=qj)⋅P(it+1=qj∣it=qi,λ)⋅αt(i)] 如果使用模型参数进行表示： α t + 1 ( j ) = ∑ i = 1 K b j ( o t + 1 ) ⋅ a i j ⋅ α t ( i ) \alpha_{t+1}(j) = \sum_{i=1}^{\mathcal K}b_j(o_{t+1}) \cdot a_{ij} \cdot \alpha_{t}(i) αt+1(j)=i=1∑Kbj(ot+1)⋅aij⋅αt(i) 最后观察它的时间复杂度：每次迭代的时间复杂度是 O ( N ) O(N) O(N)，迭代 T T T次的时间复杂度即 O ( K × T ) O(\mathcal K \times T) O(K×T)。 而上述时间复杂度 描述的是 α 1 ( i ) → α T ( i ) \alpha_1(i) \to \alpha_T(i) α1(i)→αT(i)的时间复杂度，而 P ( O ∣ λ ) = ∑ i = 1 K α T ( i ) P(\mathcal O \mid \lambda) = \sum_{i=1}^{\mathcal K} \alpha_{T}(i) P(O∣λ)=∑i=1KαT(i)。因此， P ( O ∣ λ ) P(\mathcal O\mid \lambda) P(O∣λ)的时间复杂度为： O ( K 2 × T ) O(\mathcal K^2 \times T) O(K2×T)，相比于 O ( K T ) O(\mathcal K^{T}) O(KT)还是要优化一些的。
下一节将介绍： 使用后向算法处理 P ( O ∣ λ ) P(\mathcal O \mid \lambda) P(O∣λ)问题。
相关参考： 机器学习-隐马尔可夫模型3-Evaluation问题-前向算法
