求模型的参数:λ=(A,B,π)
已知:观测序列O
未知:隐藏状态序列I
那么: P(O∣λ)=∑IP(O∣I,λ)P(I∣λ) .
M步: 如《统计学习方法》,上上式三个子项逐一用拉格朗日函数求解。
最后的解πi=P(O∣λˉ)P(O,i1=i∣λˉ)中有个式子P(O∣λˉ) ,如何高效计算?前向后向算法。
若给定λ=(A,B,π)和观测序列,计算观测序列O出现的概率P(O∣λ) . 具体Status未知,此时计算量很大。
最简单的:αt(k)=P(o1:t,st=k)=∑s1:t−1P(o1:t,s1:t−1,St=k) 。
但是,看看求和的集合,这个时间复杂度不可接受。
于是乎想到了一种利用αt−1(l)结果的算法: