Hidden Markov Model

Markov Model

马尔科夫模型是用来描述序列的性质的，在马尔科夫模型中有两个假设。

1. 在序列中，当前时刻状态只依赖于前一时刻的状态，也就是P(z(t)|z(t-1), z(t-2), ..., z(1), z(0)) = P(z(t)|z(t-1))。

2. 状态转移的分布不随时间的改变而改变，也就是说任意时刻下的状态产生与时间无关，仅仅与前一状态有关。

马尔科夫模型中的状态转移情况我们可以用一个矩阵表示，那么第i行j列的元素表示从状态i转移到j的概率，当然矩阵中的元素需要满足概率的要求。

在马尔科夫模型中，我们需要解决两个问题：如果给定一个状态序列，如何求该序列的概率值？给定一些序列样本，我们如何训练参数？

解决第一个问题比较简单，直接使用联合概率转化成条件概率的连乘形式即可。而对于第二个问题，则可以使用maximum likely hood方法，当然列出状态序列的似然之后，需要对概率的合法性进行限制，于是将限制条件使用拉格朗日乘子加入到需要最优解的式子中，然后就变成了无限制条件的最优化问题了。

Hidden Markov Model

隐马尔科夫模型是说我们知道的只是观测序列，而这些观测序列是由内在的状态序列产生，于是在隐马模型中就有两个矩阵，一个表示状态转移概率的矩阵，另一个则表示从状态产生观察值概率矩阵。

隐马模型需要三个假设，前两个假设和MM是一样的，第三个假设是从状态产生观察值是条件独立的。

在隐马模型中，我们需要解决三个问题：对于一个观察值序列，如何计算该序列的概率？对于一个给定的观察序列，如何获得最有可能产生该观察序列的状态序列？对于给定的一些观察序列样本，如何进行参数训练得到隐马模型中的两个概率矩阵？

对于第一个问题，我们利用动态规划的办法进行求解，也就是大家熟知的前向算法（forward algorithm），对于这个问题有一个同样的方法就是后向算法（backward algorithm）。对于第二个问题，我们只需要将前向算法稍加修改即可，也就是说我们是求最有可能的状态序列，也就是说我们要记住当前状态最有可能的转移过来的前一状态，这点不同于我们在前向算法中计算的是所有转移到当前状态的概率之后，对于第二个问题的解法就是我们熟知的Viterbi algorithm。对于第三个问题，给定的观察值序列样本进行训练，由于具有隐层，所以我们不能直接使用maximum likely hood方法求解，而是使用EM算法进行求解；你会发现EM算法的Maximization的时候，求解两个状态矩阵中对应的概率很像是统计样本中出现对应事件的频率除以总频率，但是这里的频率并不是简单按照1来计数，而是按照在Expectation步计算得到的概率来计算，从而最大化likely-hood，进而重新得到新的估计的两个概率矩阵。

在使用EM算法求解参数的时候，注意0概率的情况，也就是需要采用平滑技术。