HMM(隐马尔可夫模型)

1. 1.    HMM与概率图

概率图用图的形式来表示概率分布：其中结点表示变量，结点之间直接相连的边表示相应变量之间的概率关系。

基于有向图的概率模型称为贝叶斯网络，基于无向图的概率模型称作马尔科夫随机场。

隐马尔科夫模型是有向概率图的一种，在静态贝叶斯网络中加入时序的考虑，其本身基于马尔科夫链

2.    马尔科夫链

马尔科夫链是有向概率图的一种，用于描述一个序列的随机变量的概率分布，变量的值可以是任意状态集合，比如天气冷暖（左图）或文字序列（右图）。

马尔科夫链遵循马尔科夫假设：如果我们想预测将来的状态，那么它只与现在的状态的有关，而与过去的状态无关。

拿天气来说，如果明天的天气状态只和今天有关，而和昨天以及过去的天气无关。

假设变量序列为 q1，q2，q3，......，qN。其中 qi 代表第 i 的天气.那么它只与前一天天气 qi-1有关。

根据上图，变量 q 有三种状态，记为集合

S：{“HOT”,”COLD”,”WARM”}。

三种状态之间的转换概率在图中以有向图的方式描述。

如果 qi-1 的状态值为“WARM”，那么第i天的天气状态 qi 只与 qi-1 有关，即在图中，从“WARM出发“：

有0.6的概率是”WARM”，

有0.3的概率是”HOT”，

有0.1的概率是”COLD”.

可以看出，上图中描述了各个状态之间的转移关系，把它以矩阵形式表示，记为矩阵 A：

除了这个转移概率矩阵，在第一天 q1 的状态无转移来源，必须给它一个初始状态，记为向量

通常，上述的状态集合s，状态矩阵A，和初始状态 PI ，共同定义了一个马尔科夫链（markov chain）。

但在实际生活中，有些状态我们是可以观测到的，比如一个人穿衣服的颜色；但是有些状态是观测不到的，比如一个人的心情。

好在的衣服的颜色一定程度上可以暴露主人的心情。也就是观测数据和隐藏状态有一定的联系，或者可以说，隐藏状态某种程度决定了观测数据。

因此，比起马尔科夫链的定义，隐马尔科夫模型（HMM）的定义中，多一个观测状态O，和从隐藏状态到观测状态的“发射概率“矩阵B

3.    隐马尔科夫模型（HMM）

上面说到。可以观测到的状态是衣服的颜色，而隐藏的状态为主人的心情。隐藏状态之间相互按一定概率分布转换，隐藏状态按一定概率分布决定观测状态

假设，心情状态有2种.S={happy,sad}

其中状态转移矩阵A为：

衣服颜色有3种状态 O={red,blue,yellow}。

其中发射矩阵B为：

很显然，根据马尔科夫假设，主人今天的心情受昨天心情的影响，今天的心情会决定今天穿什么颜色的衣服。

比如，主人昨天很高兴，那么他有0.7的概率今天也高兴，有0.3的概率今天不高兴。如果他今天高兴，你可能有0.8的概率看到他穿红色衣服，0.1的概率看到他穿绿色或蓝色衣服。

而昨天的心情又取决于前天的心情……

假设他第一天的心情概率是这样的，也就是初始状态 PI 为

4.    隐马尔科夫模型的推断问题

那么，隐马尔可夫要解决的问题之一就是，虽然你不知道接下来他每天是什么心情，但是你根据你的观测，他第一天穿绿色衣服，第二天穿蓝色衣服，第三天穿红色衣服，那么你需要计算出这三天的他的心情是怎么样的。

我们设三天的观测状态组成的序列为 x1,x2,x3，显然  x1=grenn,x2=blue,x3=red

我们需要求的是隐藏序列 z1,z2,z3。

那么假设我们已经找到了这个隐藏序列  z1,z2,z3，这个隐藏序列必定使我们观测到的观测序列 x1,x2,x3, 出现的概率最高。

那么反过来，求隐藏序列 z1,z2,z3，  就是使x1,x2,x3, z1,z2,z3 的联合概率P最大

即：

其中

又根据马尔科夫假设

我们可以根据上述的初始状态PI，状态转移矩阵A，以及发射矩阵B中的取值拿来进行组合测试，找到是上述概率取值最大的组合。

这个组合下的 z1,z2,z3,就是所需要求得的隐藏序列：{sad,sad,happy}。

显然这种尝试的组合时间复杂度的指数级的，随着状态的增多和时序的增长，计算量将非常庞大。为此我们引入一种算法——维特比算法