隐马尔科夫模型（HMM）
隐马尔科夫模型（Hidden Markov Model，简称HMM）是经典的机器学习模型。首先设置两个状态集合：隐藏状态 S 和观测状态 V。
n是所有可能的隐藏状态数，m是所有可能的观察状态数。定义输入序列X，输出序列Y：
状态转移矩阵A：包含了一个隐藏状态到另一个隐藏状态的条件概率。
观测概率矩阵B：包含了一个隐藏状态到一个观察状态的概率。
HMM 模型做了两个假设：
马尔科夫假设：输出序列 Y 中，每个时刻 t 的隐藏状态只依赖于前一个时刻 t - 1 的隐藏状态。
观测独立性假设：输入序列 X 中，每个时刻 t 的观测状态只依赖于 Y 中当前时刻 t 的隐藏状态。
举个序列词性预测的例子：
所以概率 p(x,y) 就为如下连乘的形式：
那模型的关键就是要得到状态转移矩阵和观测概率矩阵，这两个矩阵可以从数据集中统计出来。
HMM的训练过程就是对有标签的数据进行统计处理。之后就可以直接进行解码了,解码的目标是找出能使 p(y|x) 概率最大的那个序列 Y：
按上式转换之后，最终就要求我们找到一个序列 Y 能使 p(x,y) 概率最大。具体的找法就是穷举所有的序列 y，计算它们的概率 p(x,y)，最大的那个就是结果。穷举的量非常大，寻常的算法时间复杂度很高，HMM 使用的解码算法是维特比，其时间复杂度为 O(T*|S|*|S|)，T 表示序列 y 的长度, |S| 表示隐藏状态数。我们借助一个网络图来理解维特比算法：
红线表示一条可能的 y 序列，网络图最前面还应该有一个start节点，最后面有一个end节点，这里未画出。根据上面那个公式（写到下面了）来考虑每个节点和每条边该怎么定义概率：
可以看到，每条边上应该定义隐藏状态之间的转移概率，每个节点上应该定义观测状态到隐藏状态的转移概率。对于每个节点，都有 |S| 条输入，会有一个走到此处的路径概率（边上定义的概率和节点上定义的概率的连乘），显然没有必要保留全部的前缀路径概率，只需要保留最大的那条就可以了，走到最后的end节点后，所保留的那个概率就是最大的，然后根据路径回溯就可以得到对应的序列Y。
