Question

概率计算算法

Answer 1

由于已知马尔可夫模型参数和观察序列，所以有

所以，利用最后一条公式就可求出概率，但是此时运算次数为 (T+T+2)*N ^T ，时间复杂度为O(TN ^T )

把隐马模型想象成一个T×N个顶点的图，其意义为T个时刻，每个时刻都有N种可能的状态。每个点为T个时刻，N中状态集合中的一种，每条边为从 i 时刻某个状态到 i+1 时刻另外一个状态的转移。

每个点存储前向概率，每条边记录 a _{i T j T} *b _jk 。即 T 时刻是状态 i ，且从状态 i 转移到状态 j 的概率以及状态 j 产生观测 k 的概率。

前向概率定义：在此模型下，输入如此观测序列且当前状态为 q _i 的概率

算法：

后向概率：此刻状态为q _i ，后面序列出现的概率是多大。