一、目的
主要以实例讲解HMM，防止公式吓跑大家
二、实例
假设生活中的天气只有三种状态：sun，cloud，rain，并且我们知道他们之间相互转换的概率，也就是说：
昨天是sun，今天天气转换成sun，cloud，rain的概率我们知道
昨天是cloud，今天天气转换成sun，cloud，rain的概率我们知道
昨天是rain，今天天气转换成sun，cloud，rain的概率我们知道
别问我咋知道，我知道也不告诉你（当然可以根据历史进行统计出来）
上图进行了四舍五入，其实概率和应该是1
现在还知道一些信息-天气状态对海藻的影响，如天气是sun的情况下，我们观测到的海藻可能是：
海藻为干燥的概率为0.6，微湿的概率为0.2，湿润的概率为0.15，湿透的概率为0.05，这些观测的结果汇总概率为1
我们还知道天气初始状态概率：
好了，隐马尔科夫模型三要素$(A, B, pi)$，你已经都知道了，可以毕业了（毕业管什么用，照样啥都不会，哈哈），那么到底什么是HMM：
上图的天气状态就是一个隐马尔科夫链：这三天我们不知道天气的隐藏态，但是我们观察到了海藻的干湿程度啦
那么请思考：我们观察到海藻的结果分别为Dry，Damp，Soggy，请问这三天的天气状态最有可能是什么天气状态（其实是HMM预测问题）？
三、HMM的三个基本问题
1）概率计算问题
给定模型$lambda = (A, B, pi)$和观察序列$O=(o_1, o_2, o_3, ..., o_T)$，计算在模型$lambda $下观察序列$O$出现的概率：$P(O|lambda)$
如上面的图片：我们想知道在模型$lambda = (A, B, pi)$下$O=(Dry, Damp, Soggy)$出现的概率$P(O|lambda)$
先介绍概念上可行但是计算上不可行的直接计算法：因为每种隐藏状态序列（天气状态）都能产生$O=(Dry, Damp, Soggy)$的观测结果，我们需要列举出所有可能的状态序列，然后求出每种状态序列产生$O=(Dry, Damp, Soggy)$的概率，然后进行加和，看下面
我们先假设隐藏的天气状态是：sun，sun，sun（这里隐藏的天气状态排列组合数目是：3 * 3 * 3 = 27）
由于初始天气状态概率分布为：$pi = {1, 0, 0}$
所以第一天（t = 1）的天气状态就变成了：$pi * A = [0.5, 0.375, 0.125]$，也就是下面：
所以第一天出现海藻Dry的概率是：$P = 0.5 * P(Dry|sun) = 0.5 * 0.6 = 0.3$（我们已经假设第一天的天气为sun-可能性是0.5）
第二天（t = 2）的天气状态依赖于第一天的天气状态（$[0.5, 0.375, 0.125]$：我们可以将其赋值给$pi$，即$pi = [0.5, 0.375, 0.125]$）
所以第二天的天气状态是：$pi * A = [0.375, 0.281, 0.344]$
第二天出现海藻Damp的概率是：$P = 0.375 * P(Damp|sun) = 0.375 * 0.15 = 0.056$
同理，第三天（t=3）的天气状态依赖于第二天的天气状态：（$[0.375, 0.281, 0.344]$，我们可以将其赋值给$pi$，即$pi = [0.375, 0.281, 0.344]$）
所以第三天的天气状态是：$pi * A = [0.344, 0.305, 0.352]$
第三天出现海藻Soggy的概率是：$P = 0.344 * P(Soggy|sun) = 0.344 * 0.05 = 0.017$
所以我们列举的第一个状态序列：sun, sun, sun产生海藻Dry，Damp，Soggy结果的概率就是：
$P(Dry, Damp, Soggy | sun,sun,sun) = 0.3 * 0.056 * 0.017 = 0.0002856$
小规律：就是我们每一天的天气状态可以用$pi * A^t$，我们的$t$就是第$t$天
这种列举的方法是不可取的，因为我们的天气状态集合目前只有三个，序列也只有三天，如果我们序列再长些，天气状态再多些，你都无法一一列举每种隐藏状态序列：（目前是$3^3=27$，还好一一列举）
解决方案是：前向与后向算法（暂时没研究）
2）学习问题
3）预测问题-也叫解码（decoding）问题
就是给定了观测序列（如上面的Dry, Damp, Soggy），求最有可能的对应的状态序列（如上面：求最有可能的天气状态序列-你可以像概率计算问题中的直接计算方法一样，求出每种状态序列的概率，然后挑出来最大的概率对应的状态序列，但是计算是海量的，无法操作的）
求最大可能的状态序列的方法就是-动态规划之维特比算法
HMM应用维特比算法不同的地方在于状态转移都是概率了，最可能的状态序列是概率相乘最大，而不是我们看到的路径相加最短
1）初始化
其实这里我们还看不出来走哪条路径概率最大，因为他们要和后面的概率相乘才能看出哪条最优
接下来我们让第一天的三种天气状态转移到sun状态，我们找出其中的最大概率
可见最大概率是sun ---> sun，我们删掉其他两条路径
接下来我们让第一天的三种天气状态转移到cloud状态，我们找出其中的最大概率
可见最大概率是sun ---> cloud，我们删掉其他两条路径
接下来我们让第一天的三种天气状态转移到rain状态，我们找出其中的最大概率
可见最大概率是sun ---> rain，我们删掉其他两条路径
然后我们将第二天的三种最优结果进行合并：
到这里我们还不能确定哪条路径概率最大（虽然sun --> cloud的概率是0.056，目前最大，但是不一定说最优路径一定经过该路径），我们继续
接下来我们让第二天的三种天气状态转移到第三天的sun状态，我们找出其中的最大概率
可见，sun --> sun概率最大，我们删掉其他路径
接下来我们让第二天的三种天气状态转移到第三天的cloud状态，我们找出其中的最大概率
可见，sun --> cloud概率最大，我们删掉其他路径
接下来我们让第二天的三种天气状态转移到第三天的rain状态，我们找出其中的最大概率
可见，cloud --> rain概率最大，我们删掉其他路径
然后我们将第三天的三种最优结果进行合并：
通过回溯，我们找到全局最优路径，也就是最佳的天气状态序列：
最优天气状态序列是：sun --> cloud --> rain
这个结果比直接计算每种天气状态序列的概率，然后比较概率大小，取最大概率对应的天气状态序列一致，但是速度更快
三、参考
https://www.cnblogs.com/sss-justdDoIt/p/10218852.html
https://zhuanlan.zhihu.com/p/87573049
http://bluewhale.cc/2016-06-02/hidden-markov-model-1.html
https://www.cnblogs.com/zyb993963526/p/9087036.html