Baum-Welch 算法
假设给定训练数据只包含 S S S 个长度为 T T T 的观测序列 { O 1 , O 2 , ⋯ , O S } \{O_1, O_2, \cdots, O_S\} {O1,O2,⋯,OS} 而没有对应的状态序列，目标是学习隐马尔可夫模型 λ = ( A , B , π ) \lambda = (A, B, \pi) λ=(A,B,π) 的参数。我们将观测序列看作在观测数据 O O O ，状态序列数据看作不可观测的隐数据 I I I，那么隐马尔可夫模型事实上是一个含有隐变量的概率模型：
P ( O ∣ λ ) = ∑ I P ( O , I ∣ λ ) (10.32) P(O|\lambda) = \sum_{I} P(O, I|\lambda) \tag{10.32} P(O∣λ)=I∑P(O,I∣λ)(10.32)
它的参数学习可以由 EM 算法实现。
-
确定完全数据的对数似然函数
所有观测数据写成 O = ( o 1 , o 2 , ⋯ , o T ) O = (o_1, o_2, \cdots, o_T) O=(o1,o2,⋯,oT)，所有隐数据写成 I = ( i 1 , i 2 , ⋯ , i T ) I = (i_1, i_2, \cdots, i_T) I=(i1,i2,⋯,iT)，完全数据是 ( O , I ) = ( o 1 , o 2 , ⋯ , o T , i 1 , i 2 , ⋯ , i T ) (O, I) = (o_1, o_2, \cdots, o_T, i_1, i_2, \cdots, i_T) (O,I)=(o1,o2,⋯,oT,i1,i2,⋯,iT)。完全数据的对数似然函数是 log P ( O , I ∣ λ ) \log P(O, I|\lambda) logP(O,I∣λ)
-
EM 算法的 E 步：求 Q Q Q 函数 Q ( λ , λ ^ ) Q(\lambda, \hat{\lambda}) Q(λ,λ^)
Q ( λ , λ ^ ) = ∑ I log P ( O , I ∣ λ ) P ( I ∣ λ ^ ) (10.33) Q(\lambda, \hat{\lambda}) = \sum_{I} \log P(O, I|\lambda)P(I|\hat{\lambda}) \tag{10.33} Q(λ,λ^)=I∑logP(O,I∣λ)P(I∣λ^)(10.33)
其中， λ ^ \hat{\lambda} λ^ 是隐马尔可夫模型参数的当前估计值， λ \lambda λ 是要极大化的隐马尔可夫模型参数。
P ( O , I ∣ λ ) = π i 1 b i 1 ( o 1 ) a i 1 i 2 b i 2 ( o 2 ) ⋯ a i T − 1 i T b i T ( o T ) P(O, I|\lambda) = \pi_{i_1} b_{i_1}(o_1) a_{i_1i_2} b_{i_2}(o_2) \cdots a_{i_{T-1}i_T} b_{i_T}(o_T) P(O,I∣λ)=πi1bi1(o1)ai1i2bi2(o2)⋯aiT−1iTbiT(oT)
于是函数 Q ( λ , λ ^ ) Q(\lambda, \hat{\lambda}) Q(λ,λ^) 可以写成
Q ( λ , λ ^ ) = ∑ I log π i 1 P ( O , I ∣ λ ^ ) + ∑ I ( ∑ t = 1 T − 1 log a i t i t + 1 ) P ( O , I ∣ λ ^ ) + ∑ I ( ∑ t = 1 T log b i t ( o t ) ) P ( O , I ∣ λ ^ ) (10.34) Q(\lambda, \hat{\lambda}) = \sum_{I} \log \pi_{i_1} P(O, I|\hat{\lambda}) + \sum_{I} \left(\sum_{t=1}^{T-1} \log a_{i_t i_{t+1}}\right) P(O, I|\hat{\lambda}) + \sum_{I} \left(\sum_{t=1}^{T} \log b_{i_t}(o_t)\right) P(O, I|\hat{\lambda}) \tag{10.34} Q(λ,λ^)=I∑logπi1P(O,I∣λ^)+I∑(t=1∑T−1logaitit+1)P(O,I∣λ^)+I∑(t=1∑Tlogbit(ot))P(O,I∣λ^)(10.34)式中求和都是对所有数据的序列总长度 T T T 进行的。
-
EM 算法的 M 步：极大化 Q Q Q 函数 Q ( λ , λ ^ ) Q(\lambda, \hat{\lambda}) Q(λ,λ^) 求模型参数 A , B , π A, B, \pi A,B,π
由于要极大化的参数在式 (10.34) 中单独地出现在 3 个项中，所以只需将各项分别极大化。
(1) 式 (10.34) 的第 1 项可以写成
∑ I log π i 1 P ( O , I ∣ λ ^ ) = ∑ i = 1 N log π i P ( O , i 1 = i ∣ λ ^ ) \sum_{I} \log \pi_{i_1} P(O, I|\hat{\lambda}) = \sum_{i=1}^{N} \log \pi_i P(O, i_1 = i|\hat{\lambda}) I∑logπi1P(O,I∣λ^)=i=1∑NlogπiP(O,i1=i∣λ^)
注意 π i \pi_i πi 满足约束条件 ∑ i = 1 N π i = 1 \sum_{i=1}^{N} \pi_i = 1 ∑i=1Nπi=1，利用拉格朗日乘子法，写出拉格朗日函数：
∑ i = 1 N log π i P ( O , i 1 = i ∣ λ ^ ) + γ ( ∑ i = 1 N π i − 1 ) \sum_{i=1}^{N} \log \pi_i P(O, i_1 = i|\hat{\lambda}) + \gamma \left(\sum_{i=1}^{N} \pi_i - 1\right) i=1∑NlogπiP(O,i1=i∣λ^)+γ(i=1∑Nπi−1)对其求偏导数并令结果等于0：
∂ ∂ π i [ ∑ i = 1 N log π i P ( O , i 1 = i ∣ λ ^ ) + γ ( ∑ i = 1 N π i − 1 ) ] = 0 (10.35) \frac{\partial}{\partial \pi_i} \left[ \sum_{i=1}^{N} \log \pi_i P(O, i_1 = i|\hat{\lambda}) + \gamma \left(\sum_{i=1}^{N} \pi_i - 1\right) \right] = 0 \tag{10.35} ∂πi∂[i=1∑NlogπiP(O,i1=i∣λ^)+γ(i=1∑Nπi−1)]=0(10.35)得：
P ( O , i 1 = i ∣ λ ^ ) + γ π i = 0 P(O, i_1 = i|\hat{\lambda}) + \gamma \pi_i = 0 P(O,i1=i∣λ^)+γπi=0
对 i i i 求和得到 γ \gamma γ：
γ = − P ( O ∣ λ ^ ) \gamma = -P(O|\hat{\lambda}) γ=−P(O∣λ^)
代入式 (10.35) 即得：
π i = P ( O , i 1 = i ∣ λ ^ ) P ( O ∣ λ ^ ) (10.36) \pi_i = \frac{P(O, i_1 = i|\hat{\lambda})}{P(O|\hat{\lambda})} \tag{10.36} πi=P(O∣λ^)P(O,i1=i∣λ^)(10.36)
(2) 式 (10.34) 的第 2 项可以写成
∑ I ( ∑ t = 1 T − 1 log a i t i t + 1 ) P ( O , I ∣ λ ^ ) = ∑ i = 1 N ∑ j = 1 N ∑ t = 1 T − 1 log a i j P ( O , i t = i , i t + 1 = j ∣ λ ^ ) \sum_{I} \left(\sum_{t=1}^{T-1} \log a_{i_t i_{t+1}}\right) P(O, I|\hat{\lambda}) = \sum_{i=1}^{N} \sum_{j=1}^{N} \sum_{t=1}^{T-1} \log a_{ij} P(O, i_t = i, i_{t+1} = j|\hat{\lambda}) I∑(t=1∑T−1logaitit+1)P(O,I∣λ^)=i=1∑Nj=1∑Nt=1∑T−1logaijP(O,it=i,it+1=j∣λ^)
类似第 1 项，应用具有约束条件 ∑ j = 1 N a i j = 1 \sum_{j=1}^{N} a_{ij} = 1 ∑j=1Naij=1 的拉格朗日乘子法可以求出：
a i j = ∑ t = 1 T − 1 P ( O , i t = i , i t + 1 = j ∣ λ ^ ) ∑ t = 1 T − 1 P ( O , i t = i ∣ λ ^ ) (10.37) a_{ij} = \frac{\sum_{t=1}^{T-1} P(O, i_t = i, i_{t+1} = j|\hat{\lambda})}{\sum_{t=1}^{T-1} P(O, i_t = i|\hat{\lambda})} \tag{10.37} aij=∑t=1T−1P(O,it=i∣λ^)∑t=1T−1P(O,it=i,it+1=j∣λ^)(10.37)
(3) 式 (10.34) 的第 3 项为
∑ I ( ∑ t = 1 T log b i t ( o t ) ) P ( O , I ∣ λ ^ ) = ∑ j = 1 N ∑ t = 1 T log b j ( o t ) P ( O , i t = j ∣ λ ^ ) \sum_{I} \left(\sum_{t=1}^{T} \log b_{i_t}(o_t)\right) P(O, I|\hat{\lambda}) = \sum_{j=1}^{N} \sum_{t=1}^{T} \log b_j(o_t) P(O, i_t = j|\hat{\lambda}) I∑(t=1∑Tlogbit(ot))P(O,I∣λ^)=j=1∑Nt=1∑Tlogbj(ot)P(O,it=j∣λ^)
同样用拉格朗日乘子法，约束条件是 ∑ k = 1 M b j ( k ) = 1 \sum_{k=1}^{M} b_j(k) = 1 ∑k=1Mbj(k)=1。注意，只有在 o t = v k o_t = v_k ot=vk 时 b j ( o t ) b_j(o_t) bj(ot) 对 b j ( k ) b_j(k) bj(k) 的偏导数才不为 0，以 I ( o t = v k ) I(o_t = v_k) I(ot=vk) 表示。求得：
b j ( k ) = ∑ t = 1 T P ( O , i t = j ∣ λ ^ ) I ( o t = v k ) ∑ t = 1 T P ( O , i t = j ∣ λ ^ ) (10.38) b_j(k) = \frac{\sum_{t=1}^{T} P(O, i_t = j|\hat{\lambda}) I(o_t = v_k)}{\sum_{t=1}^{T} P(O, i_t = j|\hat{\lambda})} \tag{10.38} bj(k)=∑t=1TP(O,it=j∣λ^)∑t=1TP(O,it=j∣λ^)I(ot=vk)(10.38)