隐马尔科夫模型

隐马尔科夫模型(Hidden Markov Model, HMM)是可用于标注问题的统计学习模型，描述由隐藏的马尔科夫链随机生成观测序列的过程，属于生成模型。

1. 的基本概念

1.1 的定义

是关于时序的概率模型，描述一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔科夫链随机生成的状态的序列，称为状态序列(State Sequence);每一个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列(Observation Seqyence).序列的每一个位置又可以看作一个时刻。

由初始概率分布、状态转移概率分布以及观测概率分布确定。HMM的形式如下:

设 是所有可能的状态集合， 是所有可能的观测的集合。

其中， 是可能的状态数， 是可能的观测数。

是长度为 的状态序列， 是对应的观测序列:

是状态转移矩阵:

其中，

是在时刻 处于状态 的条件下在时刻 转移到状态 的概率。

是观测概率矩阵:

其中，

是在时刻 处于状态 的条件下生成观测 的概率。

是初始状态概率向量:

其中，

是时刻 处状态 的概率。

由初始状态概率向量 、状态转移概率矩阵 和观测概率矩阵 决定。 和 决定状态序列， 决定观测序列。因此， 可以用三元符号表示，即

称为 的三要素。

状态转移矩阵 与初始状态概率向量 确定了隐马尔科夫链，生成不可观测的状态序列。观测概率矩阵 确定了如何从状态生成观测，与状态序列综合取得了如何产生观测序列。

作了两个基本假设:

1. 齐次马尔科夫性假设，即假设隐藏的马尔科夫链在任意时刻 的状态值依赖于前一时刻的状态，与其他时刻的状态及观测无关，也与时刻 无关。

2. 观测独立性假设，即假设任意时刻的观测只依赖于该时刻的马尔科夫链的状态，与其他观测及状态无关。

可用于标注，这时状态对应着标记。标注问题是给定观测的序列预测去对应的标记序列。可以假设标注问题的数据是由 生成的。这样就可以利用 的学习与预测算法进行标注。

例(盒子和球模型)

假设有4个盒子，每个盒子里都装有红白两种颜色的球，盒子里的红白球数如下表:

盒子	1号	2号	3号	4号
红球数	5	3	6	8
白球数	5	7	4	2

抽球方法:开始，以等概率随机从4个盒子里选取1个盒子，从盒子里随机抽出1个球，记录颜色后放回；然后从当前盒子转移到下一个盒子，规则:如果当前盒子是1号，那么 下一个盒子一定是2号，如果当前盒子是2号或3号，那么分别以概率0.4和0.6转移到左边或右边的盒子，如果当前盒子是4号，那么各以0.5的概率停留在盒子4或转移到盒子3；确定转移的盒子后，再从这个盒子里随机抽出1个求，记录其颜色并放回；如此下去重复5次，得到 一个球的颜色的观测序列:

在这个过程中，只能观测到求颜色的序列，不能观测到球是从哪个盒子取出的，即观测不到盒子的序列。

这个例子中有两个随机序列，一个是盒子的序列(状态序列)，一个是球颜色的观测序列(观测序列)。前者是隐藏的，只有后者是可观测的。这是 的例子:

盒子对应状态，状态的集合:

球的颜色对应观测。观测序列集合:

状态序列和观测序列长度 .

初始概率分布:

状态转移概率分布

观测概率分布

1.2 观测序列的生成过程

根据 的定义，可以将一个长度为 的观测序列 的生成过程描述如下:

输入: ，观测序列长度 ;

输出：观测序列 。

1. 按照初始状态分布 产生状态

2. 令

3. 按照状态 的观测概率分布 生成

4. 按照状态 的状态转移概率分布

产生状态

5. 令 ；如果 ，转(3);否则，终止

1.3 的三个基本问题

(1)概率计算问题，给定模型 和观测序列 ，计算在模型 下观测序列 出现的概率

(2)学习问题。已知观测序列 ，估计模型 参数，使得在该模型下观测序列概率 最大.即用极大似然估计参数。

(3)预测问题，也称为解码(decoding)问题。已知模型 和观测序列 ，求给定观测序列条件概率 最大的状态序列 .即给定观测序列，求最有可能的对应的状态序列。

2. 概率计算算法

2.1 直接计算

给定模型 和观测序列 ，计算观测序列 出现的概率 .最直接的方法是按概率公式直接计算。通过列举所有可能的长度为 的状态序列 ，求各个状态序列 与观测序列 的联合概率 ,然后对所有可能的状态序列求和，得到 。

状态序列 的概率是

对固定状态序列 ，观测序列 的概率是

和 同时出现的联合概率为

然后对所有可能的状态序列 求和，得到观测序列 的概率：

上式的计算量是 阶的，计算量过大，此方法不可行。

2.2 前向算法

前向概率: 给定 ，定义到时刻 部分观测序列为 且状态为 的概率为前向概率，记作

可以递推地求前向概率 及观测序列概率 .

观测序列概率的前向算法

输入: ,观测序列 ；

输出: 观测序列概率 .

(1)初值

(2)递推 对

(3)终止

(1)初始化前向概率，是初始时刻的状态 和观测 的联合概率。(2)是前向概率的递推公式，计算到时刻 部分观测序列为 且在时刻 处于状态 的前向概率，如图。

在递推公式的方括号里, 是时刻 观测到 并在时刻 处于状态 的前向概率，那么乘积 就是是时刻 观测到 并在时刻 处于状态 而在时刻 到达状态 的联合概率。对于这个乘积在时刻 的所有可能的 个状态 求和，其结果解释到时刻 观测为 并在时刻 处于状态 的联合概率。方括号里的值与观测概率 的乘积恰好就是是到时刻 观测到 并在时刻 处于状态 的前向概率 .

(3)因为

所以

如上图，前向算法实际是基于状态序列的路径结构递推计算 的算法。前向算法高效的关键是其具备计算前向概率，然后利用路径结构将前向概率递推到全局，得到 .具体地，在时刻 ，计算 的 个值 ；在各个时刻 ，计算 的 个值, 而且每个 的计算利用前一时刻 个 .减少计算量的原因在于每一次计算直接引用前一时刻的计算结果，避免重复计算。这样利用前向概率计算 的计算量是 阶的。

例

考虑盒子和球模型 ，状态集合

观测集合

设 ,用前向算法计算

解

(1)计算初值

(2)递推计算

(3)终止

2.3 后向算法

后向概率: 给定 ，定义在时刻 状态为 的条件下，从 到 的部分观测序列为 的概率为后向概率，记作

可以用递推地方法求得后向概率 及观测序列概率 。

观测序列概率的后向算法

输入: ,观测序列 ；

输出: 观测序列概率 .

(1)初值

(2)递推 对

(3)终止

(1)初始化后向概率，对最终时刻的所有状态 规定 。(2)是后向概率的递推公式。

如上图，为了计算在时刻 状态为 条件下时刻 之后的观测序列为 的后向概率 ，只需考虑在时刻 所有可能的 个状态 的转移概率 ( 项)，以及在此状态下的观测 的观测概率( 项)，然后考虑状态 之后的观测序列的后向概率( 项)。(3)求 的思路与步骤(2) 一致，只是初始概率 代替转移概率。

利用前向概率和后向概率的定义可以将观测序列概率 统一写成

此式当 和 时分别代表前向概率和后向概率所求的观测序列概率。从 时刻不断向前递推，将得到前向算法的计算公式，从 时刻不断向后递推，将得到后向算法的计算公式。

把 代入，得

由于 是对 的累加，与 无关，于是上式可变化为：

由 的递推公式:

得

由 的递推公式得

在前向算法和后向算法中，给每一个 时刻的隐含状态结点定义了实际的物理含义，即 两个中间变量分别从两边进行有向加权和有向边汇聚，形成一种递归结构，并且不断传播至两端，对任意 时刻，分别进行累加就能求得

2.4 概率与期望的计算

利用前向概率和后向概率，可以得到关于单个状态和两个状态概率的计算公式。

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

可以通过前向后向概率计算，

由前向概率 和后向概率 定义可知, 为在 下，由前向和后向算法导出同一个中间节点 ， 且 时刻状态为 的概率。

于是有

2.给定模型 和观测 ,在时刻 处于状态 且在时刻 处于状态 的概率：

通过前向后向概率计算:

而 ,其物理含义：从 时刻出发由前向算法导出的中间节点 和从 时刻出发，由后向算法导出的中间节点 ,且节点 中间还有一条加权有向边的关系 ，如下图:

所以

3.将 和 对各个时刻 求和,可以得到一些有用的期望值:

(1)在观测 下状态 出现的期望

(2)在观测 下由状态 转移的期望

(3)在观测 下由状态 转移到状态 的期望值

3. 学习算法

3.1 监督学习算法

假设已给训练数据包含 个长度相同的观测序列和对应的状态序列

那么可以利用极大似然估计法来估计 的参数:

1.转移概率 的估计

设样本中时刻 处于状态 时刻 转移到状态 的频数为 ,那么状态转移概率 的估计是

2.观测概率 的估计

设样本中状态为 并观测为 的频数是 ,那么状态为 观测为 的概率 的估计是

3.初始状态概率 的估计 为 个样本中初始化状态为 的频率

由于监督学习需要使用训练数据，而人工标注训练数据代价很高，有时就会用非监督学习的方法。

3.2 Baum-Welch算法

假设给定训练数据只包含 个长度为 的观测序列

而没有对应的状态序列，目标是学习隐马尔科夫模型 的参数。将观测序列数据看作观测数据 ，状态序列数据看作不可观测的隐数据 ，那么 事实上是一个含有隐变量的概率模型

它的参数学习可以由 算法实现。

1.确定完全数据的对数似然函数

所有观测数据写成 ，所有隐数据写成 ，完全数据是 。完全数据的对数似然函数是

2. 算法的 步: 求 函数

其中， 是 参数的当前估计值， 是要极大化的 参数，对于 来说

为常数因子，可省略。

于是有:

式中求和都是对所有训练数据的序列总长度 进行的。

3. 算法的 步：极大化 函数求模型参数

由于要极大化的参数在 函数中单独地出现在3个项中，所以只需对各项分别极大化

(1)推导出的 函数中的第一项可写成

注意到 满足约束条件 ，利用拉格朗日乘子法，写出拉格朗日函数:

对其求偏导，并令结果为 0

得

对 求和得到

则 为

(2)推导出的 函数的第二项可以写成

类似第一项，应用具有约束条件 的拉格朗日乘子法可以求出

(3)推导出的 函数的第三项为：

同样用拉格朗日乘子法，约束条件是 .注意只有在 时 对 的偏导数才不为 0 ，以 表示，求得

3.3 Baum-Welch模型参数估计公式

由

可将上节估计出的参数写成:

以上三个结果就是 Baum-Welch 算法，它是 算法在 学习中的具体实现，由 Baum 和 Welch 提出。

Baum-Welch 算法流程

输入: 观测数据 ;

输出: 参数

(1)初始化

对 ,选取 ，得到模型 .

(2)递推。 对

右端各值按观测 和模型 计算。

3. 终止，得到模型参数

4. 预测算法

4.1 近似算法

近似算法思想是，在每个时刻 选择在该时刻最有可能出现的状态,从而得到一个状态序列,将它作为预测的结果。

给定 和观测序列 ，在时刻 处于状态 的概率 是

在每一时刻 最有可能的状态是

而得到状态序列.

近似算法的优点是计算简单，其缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分。事实上，上述方法得到的状态序列中有可能存在转移概率为 0 的相邻状态，即对某些 时，尽管如此，近似算法仍然是有用的。

4.2 维特比算法

维特比算法是用动态规划解 的预测问题，用动态规划(Dynamic Programming)求概率最大路径。这时一条路径对应一个状态序列。

根据动态规划原理，最优路径具有如下特性:如果最优路径在时刻 通过结点,那么这一路径从结点到终点的部分路径，对于从到的所有可能的部分路径来说，必须是最优的。因为如果从到有另一条更好的部分路径存在，那么把它和从到的部分路径连接起来，就会形成一条比原来更优的路径，这是矛盾的。依据这一原理，我们只需从时刻 开始，递推地计算在时刻 状态为 的各条部分路径的最大概率，直至得到时刻 状态为 的各条路径的最大概率。时刻 的最大概率即为最优路径的概率,最优路径的终结点也同时得到。之后，为了找出最优路径的各个结点，从终结点开始，由后向前逐步求得结点，得到最优路径.以上即为维特比算法。

首先导入两个变量 和 .定义在时刻 状态为 的所有单个路径 中概率最大值为

由定义可得变量 的递推公式:

定义在时刻 状态为 的所有单个路径 中概率最大的路径的第 个结点为

维特比算法流程

输入：模型 和观测 ;

输出：最优路径

(1)初始化

(2)递推。对

(3)终止

(4)最优路径回溯。对

求得最优路径

例

考虑盒子和球模型 ，状态集合

观测集合

设 ,试求最优状态序列，即最优路径

解 如下图，

要在所有可能路径中选择一个最优路径，按以下处理:

(1)初始化。在 时，对每一个状态 ，求状态为 观测 为红的概率，记为 ,则

代入实际数据

记

(2)在 时，对每一个状态 ，求在 时状态为 观测为红并且在 时状态为 观测为 为白的路径最大概率，记为 ,则

同时，对每个状态 ，记录概率最大路径的前一个状态 :

计算：

同样，在 时，

(3)以表示最优路径的概率，则

最优路径的终点是：

(4)由最优路径的终点,逆向找到:

于是求得最优路径，即最优状态序列

参考

1. 周志华 《机器学习》
2. 隐马尔可夫模型
3. 隐马尔可夫模型之Baum-Welch算法详解
4. 隐马尔可夫模型（HMM）攻略