一文带你了解隐马尔科夫模型

r囧r小猫 2023-01-18 05:29 99阅读 0赞

## 算法原理  ##

隐形马尔可夫模型，英文是 Hidden Markov Models，所以以下就简称 HMM。既是马尔可夫模型，就一定存在马尔可夫链，该马尔可夫链服从马尔可夫性质：即无记忆性。也就是说，这一时刻的状态，受且只受前一时刻的影响，而不受更往前时刻的状态的影响。  
    使用非常简单的天气模型来做说明

![20210501094639359.png_pic_center][]

在这个马尔可夫模型中，存在三个状态，Sunny， Rainy， Cloudy，同时图片上标的是各个状态间的转移概率（如果不明白什么是转移概率，那建议先去学习什么是马尔可夫再来看HMM）。现在我们要说明什么是 HMM。既是隐形，说明这些状态是观测不到的，相应的，我们可以通过其他方式来『猜测』或是『推断』这些状态，这也是 HMM 需要解决的问题之一。  
      举个例子，我女朋友现在在北京工作，而我还在法国读书。每天下班之后，她会根据天气情况有相应的活动：或是去商场购物，或是去公园散步，或是回家收拾房间。我们有时候会通电话，她会告诉我她这几天做了什么，而闲着没事的我呢，则要通过她的行为猜测这几天对应的天气最有可能是什么样子的。  
      以上就是一个简单的 HMM，天气状况属于状态序列，而她的行为则属于观测序列。天气状况的转换是一个马尔可夫序列。而根据天气的不同，有相对应的概率产生不同的行为。在这里，为了简化，把天气情况简单归结为晴天和雨天两种情况。雨天，她选择去散步，购物，收拾的概率分别是0.1，0.4，0.5， 而如果是晴天，她选择去散步，购物，收拾的概率分别是0.6，0.3，0.1。而天气的转换情况如下：这一天下雨，则下一天依然下雨的概率是0.7，而转换成晴天的概率是0.3；这一天是晴天，则下一天依然是晴天的概率是0.6，而转换成雨天的概率是0.4. 同时还存在一个初始概率，也就是第一天下雨的概率是0.6， 晴天的概率是0.4.

![20210501095710482.png_pic_center][]

根据以上的信息，我们得到了 HMM的一些基本要素：初始概率分布 π，状态转移矩阵 A，观测量的概率分布 B，同时有两个状态，三种可能的观测值。现在，重点是要了解并解决HMM 的三个问题。  
      问题1，已知整个模型，我女朋友告诉我，连续三天，她下班后做的事情分别是：散步，购物，收拾。那么，根据模型，计算产生这些行为的概率是多少。  
      问题2，同样知晓这个模型，同样是这三件事，我女朋友要我猜，这三天她下班后北京的天气是怎么样的。这三天怎么样的天气才最有可能让她做这样的事情。  
      问题3，最复杂的，我女朋友只告诉我这三天她分别做了这三件事，而其他什么信息我都没有。她要我建立一个模型，晴雨转换概率，第一天天气情况的概率分布，根据天气情况她选择做某事的概率分布。

而要解决这些问题，伟大的大师们分别找出了对应的算法。问题一，Forward Algorithm，向前算法，或者Backward Algo，向后算法。 问题二，Viterbi Algo，维特比算法。问题三，Baum-Welch Algo，鲍姆-韦尔奇算法。

问题1的解决1：遍历算法  
      要计算产生这一系列行为的概率，那我们把每一种天气情况下产生这些行为都罗列出来，那每种情况的和就是这个概率。有三天，每天有两种可能的天气情况，则总共有 2的三次=8种 情况.举例其中一种情况 ： P（下雨，下雨，下雨，散步，购物，收拾）=P（第一天下雨）P（第一天下雨去散步）P（第二天接着下雨）P（下雨去购物）P（第三天还下雨）P（下雨回家收拾）=0.6X0.1X0.7X0.4X0.7X0.5=0.00588当然，这里面的 P（第二天接着下雨）当然是已知第一天下雨的情况下，第二天下雨的概率，为0.7.将八种情况相加可得，三天的行为为\{散步，购物，收拾\}的可能性为0.033612. 看似简单易计算，但是一旦观察序列变长，计算量就会非常庞大（的复杂度，T 为观测序列的长度）

问题1 的解决2：向前算法

先计算 t=1时刻，发生『散步』一行为的概率，如果下雨，则为 P(散步，下雨)=P（第一天下雨）X P（散步 | 下雨）=0.6X0.1=0.06；晴天，P（散步，晴天）=0.4X0.6=0.24t=2 时刻，发生『购物』的概率，当然，这个概率可以从 t=1 时刻计算而来。如果t=2下雨，则 P（第一天散步，第二天购物， 第二天下雨）= 【P（第一天散步，第一天下雨）X P（第二天下雨 | 第一天下雨）+P（第一天散步，第一天晴天）X P(第二天下雨 | 第一天晴天)】X P（第二天购物 | 第二天下雨）=【0.06X0.7+0.24X0.3】X0.4=0.0552如果 t=2晴天，则 P（第一天散步，第二天购物，第二天晴天）=0.0486 （同理可得，请自行推理）如果 t=3，下雨，则 P（第一天散步，第二天购物，第三天收拾，第三天下雨）=【P（第一天散步，第二天购物，第二天下雨）X P（第三天下雨 | 第二天下雨）+ P（第一天散步，第二天购物，第二天天晴）X P（第三天下雨 | 第二天天晴）】X P（第三天收拾 | 第三天下雨）=【0.0552X0.7+0.0486X0.4】X0.5= 0.02904如果t=3，晴天，则 P（第一天散步，第二天购物，第三天收拾，第三天晴天）= 0.004572那么 P（第一天散步，第二天购物，第三天收拾），这一概率则是第三天，下雨和晴天两种情况的概率和。0.02904+0.004572=0.033612.以上例子可以看出，向前算法计算了每个时间点时，每个状态的发生观测序列的概率，看似繁杂，但在 T 变大时，复杂度会大大降低。  
问题1的解决3：向后算法  
      顾名思义，向前算法是在时间 t=1的时候，一步一步往前计算。而相反的，向后算法则是倒退着，从最后一个状态开始，慢慢往后推。  
      初始化：Β3（Raniny）=1，Β3（sunny）=1  
![20210501101125608.png_pic_center][]

问题2的解决：维特比算法  
      用维特比算法针对HMM三大问题中的解码问题(给定模型和观测序列，如何找到与此观测序列最匹配的状态序列的问题)进行求解。问题描述如下：

首先，我们已经知道状态序列X会产生观测序列O:  
![20210501104039613.png_pic_center][]

但是观测序列O对应的状态序列X有很多种可能，每种都有概率，如下所示，比如wo可能有三种可能：喔、我、沃

![20210501104129234.png_pic_center][]

那么其实问题就变成了最大概率问题，把概率最大的理解为路径最短，转换为了求解最短路径问题：(为了方便标记，标记为了下图中的字母)

![202105011042161.png_pic_center][]

算法解决：

接下来就用到了维特比算法求解最短路径，实质上是一种动态规划，把大问题化解为小问题：步骤1、A->B：

![20210501104316549.png_pic_center][]

步骤2、A->B->C：  
![20210501104411334.png_pic_center][]

步骤3、A->B->C->D：

![20210501104501306.png_pic_center][]

步骤4、A->B->C->D->E：

![20210501104556280.png_pic_center][]

最终就得到了A->E的最短路径A->B1->C2->D2->E1，至此，找到了wo ai zhong guo对应的概率最大的中文汉字组合为：我爱中国。

![20210501104648495.png_pic_center][]

问题3的解决：Baum-Welch 算法。

此问题的复杂度要远远高于前两种算法，不是简单解释就能说的清楚的了。  
![2021050111025042.png_pic_center][]  
![20210501110445663.png_pic_center][]

![20210501110603786.png_pic_center][]

python 工具包  
见链接

[HMM算例 python 有代码][HMM_ python]

![在这里插入图片描述][20210501110743823.jpg_pic_center]  
参考文献：  
[https://www.zhihu.com/question/20962240/answer/64187492][https_www.zhihu.com_question_20962240_answer_64187492]

![20210501110928124.jpg_pic_center][]

[20210501094639359.png_pic_center]: /images/20221021/e513ab5ccb8b43a7a82b0cd7a2d7366c.png
[20210501095710482.png_pic_center]: /images/20221021/5135659ec2734c94a51a7a3e2d96cc64.png
[20210501101125608.png_pic_center]: /images/20221021/bf44a914f4044e21af4c2f4295153de0.png
[20210501104039613.png_pic_center]: /images/20221021/c801403b0241460e88bff083e3b0e984.png
[20210501104129234.png_pic_center]: /images/20221021/35f6c7044a5e459d961ec6e2d9b2f07a.png
[202105011042161.png_pic_center]: /images/20221021/bfa93e5ebf1743ae8e023f7a58020874.png
[20210501104316549.png_pic_center]: /images/20221021/66bbe46252954adea26dc42d3cc7bad5.png
[20210501104411334.png_pic_center]: /images/20221021/9b91dfeeb1564d289bb4ae042730fc1e.png
[20210501104501306.png_pic_center]: /images/20221021/80a3ebd0e8cb4bcd90af3abbef787689.png
[20210501104556280.png_pic_center]: /images/20221021/3390af3b04a74a1fb47934bce9e8bcad.png
[20210501104648495.png_pic_center]: /images/20221021/16da089ede4243248b904fabf85ce6f8.png
[2021050111025042.png_pic_center]: /images/20221021/1d7641ab876548b484ff499cce1bbe73.png
[20210501110445663.png_pic_center]: /images/20221021/7f8145720e1648878884e2c2bf9fbcd6.png
[20210501110603786.png_pic_center]: /images/20221021/8ebf5ec4af704f888578412dc2328af6.png
[HMM_ python]: https://blog.csdn.net/kobeyu652453/article/details/106465344
[20210501110743823.jpg_pic_center]: /images/20221021/0aaf252707474ce5923c242aee4a66ec.png
[https_www.zhihu.com_question_20962240_answer_64187492]: https://www.zhihu.com/question/20962240/answer/64187492
[20210501110928124.jpg_pic_center]: /images/20221021/2de84ae064d2433999db17a16160422e.png