隐马尔科夫知识点（HMM）总结

对有监督机器学习算法熟悉的朋友知道，我们监督学习研究的对象往往满足独立同分布（i.i.d）条件，也即样本点与样本点之间 不存在依赖关系。但现实当中，独立同分布的假设往往不成立，比如说，英语句子当中的字符、股票交易各个时间点的状态等等。对于这一类数据，我们可以使用马尔可夫模型解决相关问题。当然，现阶段再各种应用上马尔可夫模型都有可以被RNN取代，但是仍然有其可以发挥作用的场景。下面我就对隐马尔可夫的知识点做一下总结。

1. 隐马尔可夫链

为了解隐马尔可夫链，有兴趣的话可以先简单回顾一下马尔可夫链，不过这不是必须的。

一个隐马尔可夫模型可以生成不可观测的状态随机序列（可以理解为一系列的随机变量），我们称其为状态序列；但是我们了解这些状态通过什么途径呢？各个状态会单独生成一个可观测的观测量。每个状态生成一个观测，由此产生的序列，我们称之为观测序列。

我们设 Q 是所有可能的状态的集合，V 是所有可能的观测集合：

假设隐马尔可夫链的长度为T，那么，如果 I 是状态序列、O是观测序列，有：

A是状态转移矩阵（代表各个状态相互转化的概率）：

其中，

是在时刻 t 处于状态  的条件下在 t + 1 时刻转移到状态的概率，容易得出，矩阵的每一行求和都为1。

B是观测矩阵（代表某状态产生某观测的概率）：

其中，

表示在t时刻处于状态的情况下，观测到的概率。

除此之外，要完全描述一个HMM模型，还需要一个初始状态：

其中，

是时刻 t = 1时, 状态为  的概率。

 并称为隐马尔可夫的三要素。

隐马尔可夫链自身有特定的假设，首先，其任一时刻的状态只依赖于前一个时刻的状态（齐次马尔可夫性假设）：

再者，任意时刻的观测值仅依赖于当前状态（观测独立性假设）：

以上两个特点在解决隐马尔可夫的 3 个基本问题将会用到。

HMM的三个基本问题

（1）概率计算问题：给定HMM模型  和观测序列 ，计算该参数情况下，观测序列O出现的概率 

  (2) 学习问题：已知观测序列，估计模型参数

  (3) 预测问题：也称作解码问题(decoding)，已知和，求最大可能的状态序列                                 

下面我们分别讨论这3个问题的解决方法。

2. 概率计算算法

如果我们知道了HMM的模型，那么得到某一个观测序列的概率是多少呢？即已知和计算，首先我们知道可以通过一个比较直接但非常低效的方法解决：

对于所有可能的状态序列 ，有：

但是，所有可能的状态序列 累加起来计算量太大，所以这个算法不实用（时间复杂度）。下面我们介绍另外两种方法。

(1) 前向算法

输入： 隐马尔可夫模型参数，观测序列 

输出：观测序列概率

定义前向概率：

1) 初始值

2) 递推 对 

3) 终止

下面对算法做一下解释，事实上该算法更像是一个动态规划算法，因为可以以归纳递推的方式得到：

由HMM的齐次性

再由HMM观测独立性

由以上可以知道，由归纳法我们可以从（所有可能i）开始，一直前向计算出。 和   都是已知的，容易得到，计算 ... 的时间复杂度是

(1) 后向算法

类似于前向算法，我们还可以定义后向算法。我们定义后向概率

后向算法如下：

1)  

2) 对于 

3)

（3）一些概率的计算

后面的章节将会使用到一些概率，我们在次列出。

1. 给定模型 和观测O，在时刻t处于状态的概率，记为：

我们知道

所以有

2. 给定模型 和观测O，在时刻t处于状态且在时刻t+1处于状态的概率，记为：

因为

有

且

3. 学习算法

现实中，我们往往是掌握着数据，要通过数据来反推HMM的参数。话句话说，我们的任务是已知观测序列，估计模型参数。

Baum-Welch算法

我们知道光有观测序列的话，是无法使用有监督的方式估计参数，因为状态变量是隐变量，所以这里我们使用无监督的EM算法来实现。

设观测数据为，隐藏状态为，完全数据为 ，完全数据的对数似然函数是。其算法步骤如下：

(1) 初始化

对 n = 0，选取，得到模型。

(2) 递推. 对 n = 1,2,...

(3) 终止。得到模型参数

4. 预测算法

我这里介绍一种非常重要的算法——维特比算法。

已知和，求最大可能的状态序列，容易看出这是一个搜索优化问题，搜索空间为所有状态变量组合。

输入：

输出：计算 

如果按找穷举搜索的方法，我们能够以时间复杂度得出结果。但这样太慢了，接下来我们使用动态规划的方法来简化搜索。首先，我们对原始问题做一下变换

以及引入结论：

我们假设 表示HMM在第k步状态为时，的最大化概率。那么，由HMM的两个性质以及上述引理，我们容易得出状态方程：

另外，我们定义。这样都是已知的，我们可以依次求取任意得。也因此，我们可以求取原始问题序列中最后一步第T步状态:

以及最大概率

最后一步的状态已经得出，那么之前的状态怎么得到呢？这要用到HMM状态网络的一个性质：如果是原始我问题的最优解，那么是原始问题子问题（序列长度由T变为T-1，且最终状态固定为）的最优解（该性质的证明目前在网上还没有找到）。T-1步如果有k个状态，我们可以求出每一个状态对应的子问题最优概率，而对于每个状态通过状态转移概率矩阵，我们都可以得到其到达(已知)的概率。进而，我们也已得到这k个状态对应的整体最优解。我们取其中的最大值即可。之后只要一直向前回溯就可以得到整个状态序列。

个人见解，HMM做预测的维特比算法和原始维特比算法（见吴军博士的《数学之美》）还是有区别的，原始维特比算是是纯粹意义上的图算法，而这里因为概率计算的缘故，算法看上去也复杂一些。

参考文献：

[1] 统计学习原理

[2] https://www.youtube.com/watch?v=RwwfUICZLsA

[3] 数学之美