概率计算算法

1.1 直接计算法

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

1. 模型产生某一状态序列的概率

   
   

2. 模型产生某一状态序列时得到某一观测序列的概率

   
   

3. 上面两概率可求得，在该模型下，产生状态序列I同时产生观测序列O的概率：

   
   

4. 目标求解概率，该模型下，产生观测序列O的概率：
   即所有可能产生观测序列O的状态序列I，产生O的概率之和。

   
   

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

1.2 前向算法

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

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

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

算法：

1. 初始化：第一个时刻，状态 i 的初始前置

   
   

2. 递推:从 t 时刻的所有顶点，求出 t + 1时刻所有顶点的前向概率，从而求出所有点的前向概率。

3. 终止：最终T时刻所有可能性加起来就是观测序列O出现的概率

   
   

1.3 后向算法

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

1. 初始化：

2. 递推

3. 计算

   
   

1.4 利用前后向概率计算一些细节

1. 给定模型和观测序列，t时刻处于状态 q_i 的概率

2. 给定模型和观测序列O，在时刻 t 处于状态 q_i 且在 t+1 处于状态 q_j 概率