隐马尔可夫模型
接下来是隐马尔可夫模型，隐马尔可夫模型是一种经典的概率图模型，应用非常广泛。
在马尔可夫模型中，每个状态代表了一个可观察的事件，所以马尔可夫模型有时又可称作可视马尔可夫模型（VMM），这在某种程度上限制了模型的适应性。
在隐马尔可夫模型（HMM）中，有两个序列，一个序列是状态序列，类似于VMM中的状态转换过程，状态序列是隐蔽的；另一个是观察序列，可以观察到，观察序列由状态序列经过相应的随机函数得到。也即隐马尔可夫模型是一个双重的随机过程，隐蔽的状态转换是一个随机过程，由状态序列得到观察序列又是一个随机过程。
举个例子，一个暗室中有N个口袋，每个口袋中有M种不同颜色的球。一个实验员根据概率分布随机选择了一个口袋，再根据口袋中不同颜色球的概率分布，随机的取出一个球，向室外报告球的颜色，然后再根据口袋的概率分布选择另一个口袋，根据不同颜色球的概率分布从中随机选择另外一个球，重复进行这个过程。
对于暗室外面的人，他不知道口袋的序列，只知道球的序列。
描述一个HMM需要五个部分，通过上例也可以看出来：
- 模型中状态的数目N（上例中口袋的数目）
- 每个状态可能输出的不同符号的数目M（上例中球的不同颜色数）
- 状态转移矩阵A={
aij}（上例中口袋的转换概率） - 从状态观察到符号的概率分布矩阵B={
bj(k)}，即从第j个口袋取出第k种颜色的球的概率，观察符号的概率又称符号发射概率。 - 初始状态概率分布π={
πi}，所有πi之和为1。
观察序列的产生步骤如下：
- 根据初始状态的概率分布
πi选择一个初始状态 - 假定时间t=1
- 根据状态的输出概率分布输出观察符号
- 根据状态转移概率分布，由当前时刻t的状态
qt转移到新的状态q(t+1) - 重复执行上两步直到t到达总时间长度T
HMM中有三个假设：
- 有限历史性假设：也即一阶马尔可夫模型，认定t时刻出现的状态只与t-1时刻的状态有关
- 齐次性假设：假定P(
s(i+1)|si)=P(s(j+1),sj) - 输出独立性假设：假定输出仅与当前状态有关
HMM中有三个基本问题：
- 估计问题：给定一个观察序列O=O1O2...OT和模型μ=(A, B, π)，如何快速地计算出给定模型μ的情况下，观察序列O的概率，即P(O|µ)？
- 解码问题：给定一个观察序列O=O1O2...OT和模型μ=(A, B, π)，如何快速有效地选择在一定意义下的最优状态序列Q=q1q2...qT，使得该状态序列最好地解释观察序列？
- 训练问题或参数估计问题：给定一个观察序列O=O1O2...OT，如何根据最大似然估计来求模型的参数值？即如何调节模型μ=(A, B, π)的参数，使得P(O|µ)最大？
先说第一个估计问题，也即求解观察序列的概率，我们先来想一种最直接的推导方式：假设状态序列Q已经给定，那我们将Q到O对应位置上的符号发射概率依次相乘即可得到观察序列的概率。但是因为目前不知道Q，我们应该将给定模型µ下，所有可能的Q都列举出来，然后将其得到O的概率全部相加。也即下式：
不过这样存在一个很大的问题，就是复杂度过高，如果模型中有N个状态，时间长度为T，那就有N^T种可能的序列，当T很大时，几乎不可能有效的执行这个过程。
为了解决这个问题，我们利用动态规划算法的思想，这里我们提出前向算法。
