# 1. 隐马尔科夫模型
# 1.1. 语音识别概述
语音识别（Speak Recognition），和图像识别不同，它是连续行为的识别（视频行为分析也一样）。比如“你是谁”这句话，不知道这三个词所占的时间。
如何归一化快和慢？
- 隐含马尔科夫模型(HMM)，Hidden Markov Model
- 递归神经网络（RNN），Recurrent Neural Network
用3个状态表示3个词，用指向自己的循环来表示延续时间。
基于音素建模是有限的(就是单词组成，比如shui,分成sh和ui)，而基于单词的建模是无穷无尽的，
# 1.2. 隐马尔科夫模型
上面的输入状态也就是观测序列
aij表示的是，t时刻是si的前提下，t+1时刻是si+1的概率
马尔科夫链假设：
- 转移矩阵和t没有关系，不同时刻aij方程一样
- 下一状态只和上一状态有关，和更早之前没有关系
多步马尔科夫链：下一状态和前几个状态有关。
隐含马尔科夫中。马尔科夫指的是第二个，下一状态只和上一状态有关，并且和t无关，隐含指的是，输入的是O，状态q是隐藏的，需要被求出来。
# 1.3. 三个问题
# 1.3.1. 识别问题（概率计算问题）
我们已知HMM模型的参数𝜆=(𝐴,𝐵,π)。其中𝐴是隐藏状态转移概率的矩阵，𝐵是观测状态生成概率的矩阵，π是隐藏状态的初始概率分布。同时我们也已经得到了观测序列𝑂={𝑜1,𝑜2,...𝑜𝑇}, 现在我们要求观测序列𝑂在模型𝜆下出现的条件概率𝑃(𝑂|𝜆)。
比如识别1到10的系统，建立了10个隐含马尔可夫模型，然后输入一个数字，让系统检测。对每一个模型求一个概率，哪个模型的概率大，就认为这个数字属于哪个模型。
乍一看，这个问题很简单。因为我们知道所有的隐藏状态之间的转移概率和所有从隐藏状态到观测状态生成概率，那么我们是可以暴力求解的。
虽然上述方法有效，但是如果我们的隐藏状态数𝑁非常多的那就麻烦了，此时我们预测状态有𝑁𝑇种组合，算法的时间复杂度是𝑂(𝑇𝑁𝑇)阶的。
因此对于一些隐藏状态数极少的模型，我们可以用暴力求解法来得到观测序列出现的概率，但是如果隐藏状态多，则上述算法太耗时，我们需要寻找其他简洁的算法。
前向后向算法就是来帮助我们在较低的时间复杂度情况下求解这个问题的。
问题1的暴力破解方法：
问题1的简便算法：
第三步下面，遍历所有的Ot, 假设状态属于各个不同的s。然后乘以状态转移的概率数aij，然后乘状态转成观测的概率数bj(Ot+1)
α1(i)有p个，αt+1(j)也有p个，可以通过前一个α算出来。到了第T步，再把所有的加起来。
# 1.3.1.1. 前向算法
前向算法本质上属于动态规划的算法，也就是我们要通过找到局部状态递推的公式，这样一步步的从子问题的最优解拓展到整个问题的最优解。
# 1.3.1.2. 前向算法举例
如果t1时刻是观测状态1，t2时刻是观测状态2：
α1(1)=π1*b11，代表t1时刻隐藏状态是1
α1(2)=π2*b21, 代表t1时刻隐藏状态是2
α1(3)=π3*b31，代表t1时刻隐藏状态是3
α2(1)=(α1(1)*a11 + α1(2)*a21 + α1(3)*a31 ) * b12，代表t2时刻隐藏状态是1，可以来自t1时刻 状态1*a11+状态2*a21+状态3*a31。
α2(2)=(α1(1)*a12 + α1(2)*a22 + α1(3)*a32 ) * b22，代表t2时刻隐藏状态是2，
α2(3)=(α1(1)*a13 + α1(2)*a23 + α1(3)*a33 ) * b32，代表t2时刻隐藏状态是3
...
# 1.3.1.3. 后向算法
后向算法和前向算法非常类似，都是用的动态规划，唯一的区别是选择的局部状态不同，后向算法用的是“后向概率”，那么后向概率是如何定义的呢？
现在我们总结下后向算法的流程,注意下和前向算法的相同点和不同点：
此时我们的算法时间复杂度仍然是𝑂(𝑇𝑁2)。
# 1.3.1.4. HMM常用概率的计算
利用前向概率和后向概率，我们可以计算出HMM中单个状态和两个状态的概率公式。
上面这些常用的概率值在求解HMM问题二，即求解HMM模型参数的时候需要用到。
# 1.3.2. 预测问题
o1的状态下出现q1的概率是bq1(O1)，q1转移到q2的概率是aq1q2
到达每一个点找最大的值，还要记录从哪里来，到了最后获得最终最大值后，不断回推回去，找到最大的路径
δ记录从前来的累乘最大的值
# 1.3.2.1. 维特比算法实例
维特比算法也是寻找序列最短路径的一个通用方法，和dijkstra算法有些类似，但是dijkstra算法并没有使用动态规划，而是贪心算法。同时维特比算法仅仅局限于求序列最短路径，而dijkstra算法是通用的求最短路径的方法。
# 1.3.3. 训练问题（学习问题）
b参数的更新：
# 1.4. 隐马尔可夫举例
假设我们想知道某个固定的地区一些年来的平均年平均气温。
为了简化问题，仅会考虑两种年平均温度，"hot"和"cold"。
假设现代的证据证明hot year之后又是一个hot year的概率是0.7，cold year之后又是一个cold year的概率是0.6，而且这个概率在过去的岁月里都适用，那么目前的信息总结如下：
其中H代表"hot"，C代表''cold"。
另外，当前的研究证实树的年轮与温度相关。也为了简化起见，我们将树的年轮分为三种大小：small，medium和large，分别用S, M和L表示。
最后基于存在的证据显示，年平均温度与树的年轮之间的关系如下：
对于这个例子来说，状态(state)是年平均气温，H或C。
从一种状态到另一种状态的转移过程是马尔科夫过程(Markov process)。
因为下一个状态仅依赖于当前状态，而且符合如矩阵(1)的固定概率。
然而，真实的状态是隐藏的("hidden")，因为我们不能直接获取到过去那些年份的气温。
虽然我们不能观测到过去那些年的状态（气温），但是我们可以观测到树的年轮大小。
通过矩阵(2)，树的年轮告诉我们关于气温的概率信息。
因为状态是隐藏的，这种类型的系统我们称为隐马尔科夫模型(Hidden Markov Model，HMM)。
我们的目标是有效地，且高效地利用观测到的数据了解马尔科夫过程的不同特征。
我们称矩阵(1)为状态转移矩阵(state transition matrix)：
称矩阵(2)为观测矩阵(state transition matrix)：
在这个例子中，还需要知道一个初始状态分布(initial state distribution)，记为π，而且假设
这里的初始状态分布指关注的这几年中，最开始的那一年，高温的概率为0.6，低温的概率是0.4
A、B和π中每个元素都是概率值，矩阵中每行都是一个概率分布，每行之和为1。
现在我们关注的四年(例如2007-2010年)，我们观测到这四年树的年轮分别为S, M, S和L，且用0表示S，1表示M，2表示L，那么观测链如下：
通过观测到的年轮结果，我们想推测出最可能（most likely）的马尔科夫过程状态链(注：也即这四年气温情况分别是怎样的)，也就是问题2。
# 1.5. 参考资料
- https://www.cnblogs.com/pinard/p/6972299.html
- https://www.jianshu.com/p/716c182bf499