DP方法求解HMM观测序列概率

1. 引入

现实生活中我们常常遇到这种问题：存在一个可观察序列（o₁ o₂, o₃, ... o_t）和一个隐藏序列（h₁ h₂, h₃, ... h_t）（所谓隐藏序列就是我们无法得知的序列）问题是我们如何根据可观测序列来“猜”隐藏序列呢？这是一个很有实际意义的问题，比如：我们现在用的输入法，用户输入的是拼音字母，输入法的任务是“猜”你想输入的汉字；自动医疗诊断系统根据你说的话（%.##..*@）来"猜"你的病情（健康or感冒or发烧）。等等，隐马尔可夫模型（HHM）的应用场景实在太多了

2. 隐马尔可夫模型定义

设X是所有可观测状态的集合，集合大小为M；Y是所有隐藏状态的集合，集合大小为N。对于一个长度为T的序列，O（o₁ o₂, o₃, ... o_T）为对应的观测序列；H（h₁ h₂, h₃, ... h_T）为对应的隐藏序列。
HMM 做了两个假设：
(1)马尔科夫假设:任意时刻的隐藏状态只依赖于它前一个隐藏状态。（这个假设不够准确但是简化了问题，这个在该文不做讨论）如果在t时刻的隐藏状态为s_t = h_i在t+1时刻的隐藏状态为s_t+1 =h_j，从t时刻转到t+1时刻的状态转移概率为a_ij = P(s_t+1 =h_j|s_t = h_i)。这样就形成了一个大小为N x N的状态转移矩阵A = [a_ij]_{N x N}.
如下图：i、j、k三个隐藏状态及对应的状态转移概率矩阵：

(2) 观测独立性假设。即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态，这也是一个为了简化模型的假设。如果在t时刻的隐藏状态为s_t = h_i而对应的观察状态为p_t = o_j，则该时刻观察状态o_j在隐藏状态 h_i下生成的概率为b_ij = P(p_j = o_j|s_i = h_i)。这样就形成了一个大小为N x M的状态生成矩阵A = [b_ij]_{N x M}
另外一个HMM模型需要隐藏状态初始概率分布C=[c(𝑖)]_N。其中c(𝑖)=P(s = h_i)。因此，HMM模型可以由一个三元组𝜆表示如下：HHM =（A，B，C）

下面我们用一个简单的实例来描述上面抽象出的HMM模型。这是一个盒子与球的模型，例子来源于李航的《统计学习方法》。假设我们有3个盒子，每个盒子里都有红色和白色两种球，这三个盒子里球的数量分别是：

按照下面的方法从盒子里抽球，开始的时候，从第一个盒子抽球的概率是0.2，从第二个盒子抽球的概率是0.4，从第三个盒子抽球的概率是0.4。以这个概率抽一次球后，将球放回。然后从当前盒子转移到下一个盒子进行抽球。规则是：如果当前抽球的盒子是第一个盒子，则以0.5的概率仍然留在第一个盒子继续抽球，以0.2的概率去第二个盒子抽球，以0.3的概率去第三个盒子抽球。如果当前抽球的盒子是第二个盒子，则以0.5的概率仍然留在第二个盒子继续抽球，以0.3的概率去第一个盒子抽球，以0.2的概率去第三个盒子抽球。如果当前抽球的盒子是第三个盒子，则以0.5的概率仍然留在第三个盒子继续抽球，以0.2的概率去第一个盒子抽球，以0.3的概率去第二个盒子抽球。如此下去，直到重复三次，得到一个球的颜色的观测序列:𝑂={红，白，红}
注意在这个过程中，观察者只能看到球的颜色序列，却不能看到球是从哪个盒子里取出的。那么按照我们上一节HMM模型的定义，我们的观察集合是:𝑉={红，白}，𝑀=2。我们的状态集合是：𝑄={盒子1，盒子2，盒子3}，𝑁=3。而观察序列和状态序列的长度为3。初始状态分布为：C=(0.2,0.4,0.4)。

状态转移概率分布矩阵为：

观测状态生成概率矩阵为：

3.动态规划求解HMM观测序列概率

1. 暴力求解法

因为我们知道所有的隐藏状态之间的转移概率和所有从隐藏状态到观测状态生成概率，那么我们是可以暴力求解的。我们可以列举出所有可能出现的长度为𝑇的隐藏序列H=（h₁ h₂, h₃, ... h_T）（N^T种不同的序列）分布求出这些隐藏序列与观测序列𝑂=（o₁ o₂, o₃, ... o_t）的联合概率分布𝑃(𝑂,H|HMM)。这样我们就可以很容易的求出边缘分布𝑃(𝑂|HMM)了。

虽然上述方法有效，但是如果我们的隐藏状态数𝑁非常多的那就麻烦了，此时我们预测状态有𝑁^𝑇种组合，算法的时间复杂度是𝑂(𝑇𝑁^𝑇)阶的。因此对于一些隐藏状态数极少的模型，我们可以用暴力求解法来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。

2. 用前向算法求HMM观测序列的概率

前向算法本质上属于动态规划的算法，递归思想将大问题分解成小问题，小问题之间可能存在重叠；动态规划思想是先计算小问题累计到大问题。他们的共同特点是需要找到递推关系式。
接下来我们来寻找递推关系式将大问题分解为小问题：
假设我们只有一个观测状态这个观测状态的概率𝑃(o₁|HMM)= $\sum_{i=1}^N$ (𝑃(h_i|HMM)b_i1),即，产生观测状态o₁的隐藏状态有很多将每种隐藏状态乘它对应的生成观测状态概率然后求和。则当序列长度为T时𝑃(o₁ o₂, o₃, ... o_t|HMM)= $\sum_{i=1}^N$ (𝑃(o₁,o₂,o₃, ... o_t-1,h_i|HMM)b _{t-1 t,}),即将产生(o₁,o₂,o₃, ... o_t-1）状态序列的概率分别乘上h_t的状态转换概率然后乘上对应的生成概率再求和。我们以上面介绍的抽球实验为例求解观测序列概率：

球的颜色的观测序列:𝑂={红，白}

时刻1是红色球
隐藏状态是盒子1的概率：𝛼₁(1)=c₁𝑏₁₁=0.2×0.5=0.1;
隐藏状态是盒子2的概率：𝛼₁(2)=c₂𝑏₂₁=0.4×0.4=0.16;
隐藏状态是盒子3的概率：𝛼₁(3)=c𝑏₃₁=0.4×0.7=0.28
时刻2是白色球
隐藏状态是盒子1的概率：𝛼₂(1)=[ $\sum_{i=1}^3$ 𝛼₁(i)a_i1]b₁₂=[0.1∗0.5+0.16∗0.3+0.28∗0.2]×0.5=0.077;
隐藏状态是盒子2的概率：𝛼₂(2)=[ $\sum_{i=1}^3$ 𝛼₁(i)a_i2]b₂₂=[0.1∗0.2+0.16∗0.5+0.28∗0.3]×0.6=0.1104;
隐藏状态是盒子3的概率：𝛼₂(3)=[ $\sum_{i=1}^3$ 𝛼₁(i)a_i3]b₃₂=[0.1∗0.3+0.16∗0.2+0.28∗0.5]×0.3=0.0606;
最终我们求出观测序列:𝑂={红，白}的概率:𝑃(𝑂|𝜆)= $\sum_{i=1}^3$ 𝛼2(𝑖) = 0.248