HMM学习一:前向和后向算法

一, 马尔科夫相关概念

马尔可夫过程 (Markov Process): 它因俄罗斯数学家安德烈·马尔可夫而得名，代表数学中具有马尔可夫性质的离散随机过程。该过程中，每个状态的转移只依赖于之前的 n 个状态，这个过程被称为1个 n 阶的模型，其中 n 是影响转移状态的数目。最简单的马尔科夫过程就是一阶过程，每一个状态的转移只依赖于其之前的那一个状态。注意这和确定性系统不一样，因为这种转移是有概率的，而不是确定性的.

马尔科夫假设: 假设这个模型的每个状态都只依赖于前一个的状态,这个假设可以极大简化这个问题。显然，这个假设也是一个非常糟糕的假设，导致很多重要的信息都丢失了。

马尔可夫链: 随机变量 X1, … , Xn 的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而 Xn 的值则是在时间 n 的状态。如果 Xn+1 对于过去状态的条件概率分布仅是 Xn 的一个函数，则

这里 x 为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。也就是说下一个状态只依赖与当前状态,与前面的多个状态无关.

*状态转移矩阵:*注意一个含有 N 个状态的一阶过程有 N2 个状态转移。每一个转移的概率叫做状态转移概率 (state transition probability)，就是从一个状态转移到另一个状态的概率。这所有的 N2 个概率可以用一个状态转移矩阵来表示，其表示形式如下：

下面就是海藻例子的状态转移矩阵：

隐马尔科夫过程: 然而，当马尔科夫过程不够强大的时候，我们又该怎么办呢？在某些情况下，马尔科夫过程不足以描述我们希望发现的模式。

例如，一个隐居的人可能不能直观的观察到天气的情况，但是民间传说告诉我们海藻的状态在某种概率上是和天气的情况相关的。在这种情况下我们有两个状态集合，一个可以观察到的状态集合（海藻的状态）和一个隐藏的状态（天气状况）。我们希望能找到一个算法可以根据海藻的状况和马尔科夫假设来预测天气的状况。

在上面的这些情况下，可以观察到的状态序列和隐藏的状态序列是概率相关的。于是我们可以将这种类型的过程建模为有一个隐藏的马尔科夫过程和一个与这个隐藏马尔科夫过程概率相关的并且可以观察到的状态集合。

假设1：马尔可夫假设（状态构成一阶马尔可夫链）:

假设2：不动性假设（状态与具体时间无关）:

假设3：输出独立性假设（输出仅与当前状态有关）:

隐藏的状态和可观察到的状态之间有一种概率上的关系，也就是说某种隐藏状态 H 被认为是某个可以观察的状态 O1 是有概率的，假设为 P(O1 | H)。如果可以观察的状态有3种，那么很显然 P(O1 | H)+P(O2 | H)+ P(O3 | H) = 1。

这样，我们也可以得到一个另一个矩阵，称为混淆矩阵 (confusion matrix)。这个矩阵的内容是某个隐藏的状态被分别观察成几种不同的可以观察的状态的概率，在天气的例子中，这个矩阵如下图：

上边的图示都强调了 HMM 的状态变迁。而下图则明确的表示出模型的演化，其中绿色的圆圈表示隐藏状态，紫色圆圈表示可观察到状态，箭头表示状态之间的依存概率，一个 HMM 可用一个5元组 { N, M, π，A，B } 表示，其中 N 表示隐藏状态的数量，我们要么知道确切的值，要么猜测该值，M 表示可观测状态的数量，可以通过训练集获得， π={πi} 为初始状态概率，A={aij} 为隐藏状态的转移矩阵 Pr(xt(i) | xt-1(j))，B={bik} 表示某个时刻因隐藏状态而可观察的状态的概率，即混淆矩阵，Pr(ot(i) | xt(j))。在状态转移矩阵和混淆矩阵中的每个概率都是时间无关的，即当系统演化时，这些矩阵并不随时间改变。对于一个 N 和 M 固定的 HMM 来说，用 λ={ π, A, B } 表示 HMM 参数。

HMM里面的三个经典问题:

1, 概率问题: 在给定模型λ={ π, A, B } 和 观测序列 O = (o1,o2,o3,o4,o5,…,oT).计算观测序列O下出现的概率P(O|λ).

2,学习问题: 已知观测序列 O = (o1,o2,o3,o4,o5,…,oT), 估计模型 λ={ π, A, B }等参数,使得最后输出观测序列O下出现的概率P(O|λ)最大,即是用极大似然估计法估计参数.

3,预测问题: 已知观测序列 O = (o1,o2,o3,o4,o5,…,oT) 和 估计模型 λ={ π, A, B }等参数, 求给定观测条件下条件概率P(O|λ)最大的状态序列 I = (i1,i2,i3,…iT), 即是给定观测序列,求最可能的状态序列.

我们先解决第一个问题,概率计算算法,这里有三个方法,分别是直接计算法,前向算法,后向算法.

如此一来,我们先对基本公式进行分析:

假设我们已经有一个特定的隐马尔科夫模型 λ 和一个可观察状态序列集。我们也许想知道在所有可能的隐藏状态序列下，给定的可观察状态序列的概率。当给定如下一个隐藏状态序列：

那么在 HMM 和这个隐藏状态序列的条件下，可观察状态序列的概率为：

注释: 其中q1,q2,q3…代表状态Q,例如为sun,cloud,rain, 而O1,O2,O3,…代表观测序列,如Dry,Dryish,Damp等

而隐藏状态序列在 HMM 条件下的概率为：

注释:其中本公式右边的第二个字母有错,应该是a(q1q2)

因此，隐藏状态序列和可观察状态序列的联合概率为：

注释:本公式中P(Q,λ )有错,应该是P(Q|λ ),对应的公式应该是P(AB) = P(A|B)P(B)

那么所有可能的隐藏状态序列上，可观察状态序列的概率为：

列一个公式推导:

直接穷举法

我们可以比较穷举和递归算法的复杂度。假设有一个 HMM，其中有 n 个隐藏状态，我们有一个长度为 T 的观察序列。

穷举算法的需要计算所有可能的隐藏序列：

需要计算：

很显然穷举算法的时间开销是和 T 指数相关的，即 NT，而如果采用递归算法，由于我们每一步都可以利用上一步的结果，所以是和 T 线性相关的，即复杂度是 N2T。

穷举算法例子:

给定隐马尔可夫模型，也就是在模型参数(π,A,B)已知的情况下，我们想找到观察序列的概率。

最直接的方法是列举出每种可能的转移，如下图所示：

图中展示了三天的海藻状态，第一列对应第一天海藻为dry时候三种可能的天气隐状态，第二列对应第二天海藻为damp时候三种可能的天气隐状态，第三列对应第三天海藻为soggy时候三种可能的天气隐状态；每个隐状态都有一个概率指向当前可能的海藻状态，由混淆矩阵给出；从第一天到第二天和第二天到第三天的天气隐状态之间都有转移概率，由转移概率矩阵给出。

计算观察序列概率的方法是找到所有的可能路径，因为每种海藻观察情况都有三种可能天气，所以共有33=27条路径，即27种不同的天气序列，然后将所有可能的观察序列的概率加和起来:

不适用于大的模型和较长的序列。可以利用概率的时间不变性减少问题的复杂性。

前向算法

理论推导:

如图所示:

举例说明:

盒中取球的实例
已知HMM模型参数：

转移概率矩阵A：

0.5 0.2 0.3
0.3 0.5 0.2
0.2 0.3 0.5
混淆矩阵B：

0.5 0.5
0.4 0.6
0.7 0.3
初始概率：

π=(0.2 , 0.4 , 0.4)

求解：三次取球颜色为（红、白、红）的概率P(O|λ)

提示：盒子相当于三种隐状态，两种颜色的球相当于观测情况，观测序列由（红、白、红）给出

（1）计算初值

（2）递推计算

（3）终止条件

后向算法:

后向概率：给定隐马尔可夫模型，定义在时刻t状态为的条件下，从t+1时刻到T的部分观测序列为后向概率

①初始化后向概率，最终时刻的所有状态qt规定

②对于t=T-1,T-2,…1递推计算，时刻 t 状态为条件下时刻t+1之后的观测序列为的后向概率，其实就是第t+1 时刻的N个状态到t 时刻状态的转移概率乘以t+1时刻每个隐状态对应的观察情况为o(t+1)的概率，再乘以状态j之后的观测序列的后向概率,此项能够递推得到

③计算一种加和，但是与前向算法的加和还不一样，它的含义是与步骤②一样的，只不过初始概率 π 代替了转移概率 a

统一写法;

关于后向算法，直接以盒子（隐）和球（观测)实例为例推导

（1）初始化第三次取球为红球时候，即最终时刻所有状态的概率为1

式中下标为观测情况，括号为隐状态，比如第一个式子意思就是第一个隐状态对应的观测到红球的概率

（2）逆推迭代倒数第二次观察情况为白球的情况

第一个式子表示的是第二次观测，如果状态为1，那么第二、三次观测为（白、红）的联合概率分布，a是第二层隐状态（第一个盒子）转移到第三层隐状态（三个盒子）的转移概率，b表示第三层的三个隐状态观测到红球的概率，β（等式右边）表示已知模型参数和第三层隐状态，求第三次观测到红球的概率，其实第（1）步计算是1

第二个式子表示的是第二次观测，如果状态为2，那么第二、三次观测为（白、红）的联合概率分布，a是第二层隐状态（第二个盒子）转移到第三层隐状态（三个盒子）的转移概率，b表示第三层的三个隐状态观测到红球的概率，β（等式右边）表示已知模型参数和第三层隐状态，求第三次观测到红球的概率，其实第（1）步计算是1

同理推导第一层的情况

（3）计算加和

可以发现前向算法和后向算法的结果相同.

参考文献为:
https://blog.****.net/zb1165048017/article/details/48577891

https://blog.****.net/continueoo/article/details/77893587#_61

https://blog.****.net/likelet/article/details/7056068

李航的<<统计学习方法>>