统计学习方法——（第十章）隐马尔科夫模型详解
一、知识梳理
二、隐马尔可夫模型
1、相关概念
- 概率计算问题： 已知模型的条件下，计算观测序列O的概率。
- 学习问题：已知观测序列，估计模型参数。即最大化概率计算问题
- 预测问题：已知模型及观测序列，求对应的状态序列。
- 后向概率：定义在时刻t部状态为qi的条件下，从t+1到T的部分观测序列为ot+1,ot+2 ,... ,oT的概率为后向概率
- 前向概率：定义到时刻t部分观测序列o1,o2,... ,ot且状态为qi的概率为前向概率
2、定义
隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔可夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测而产生观测随机序列的过程。隐藏的马尔可夫链随机生成的状态的序列，称为状态序列(state sequence)：每个状态生成一个观测，而由此产生的观测的随机序列，称为观测序列(observation sequenoe )。序列的每一个位置又可以看作是一个时刻。隐马尔可夫模型由初始概率分布、状态转移概率分布以及观测概率分布确定。
3、模型
（1）要素
（2）模型
隐马尔可夫模型由初始状态概率向量pi、状态转移概率矩阵A和观测概率矩阵B决定。A，B，pi称为隐马尔可夫模型的三要素。状态转移概率矩阵A与初始状态概率向量pi确定了隐藏的马尔可夫链，生成不可观测的状态序列。观测概率矩阵B确定了如何从状态生成观测，与状态序列综合确定了如何产生观测序列。
（3）补充：隐马尔科夫模型假设：齐次马尔可夫性假设，观测独立性假设
（4）应用：观测序列生成
三、概率计算算法（使用隐马尔科夫模型计算观测序列O的概率）
1、直接计算法
按概率公式直接计算通过列举所有可能的长度为T的状态序列I=(i1,i2,... ,iT)，求各个状态序列I与观测序列O=(o1,o2,... ,oT)的联合概率P(O,I/)。然后对所有可能的状态序列求和，得到P(O/
)。
对于此种算法，需要列举所以状态，这几乎是不可能的，而且有些问题中我们是无法知道所以状态的。即使可以，但是，计算量很大，是O(TNT)阶的，这种算法不可行。因此，有前向后向算法。
2、前向-后向算法(forward-backward algorithm)
1）前向算法
（1）步骤
（2） 推导
首先，根据贝叶斯公式（乘法公式）有
再代入马尔科夫模型中，设
代入P(A,B,C/)
2）后向算法
（1）步骤：
（2）推导
首先，由后向概率有
设
代入后向概率公式有
3）前向后向算法
（1）步骤：合并公式
（2）推导
又因为
所以结合下式，得证
四、学习算法（解决学习问题）
已知观测序列，估计模型参数。隐马尔可夫模型的学习，根据训练数据是包括观测序列和对应的状态序列还是只有观测序列，可以分别由监督学习与非监督学习实现。
1、监督学习（极大似然估计法来估计隐马尔可夫模型的参数）
1）转移概率aij的估计 （求解见本人博客MLE，可以知道解是均值）
2）观测概率bj(k)的估计
2、无监督学习（EM算法）
1）为什么使用EM？
假设给定训练数据只包含S个长度为T的观测序列｛O1,...,OS)｝而没有对应的状态序列，目标是学习隐马尔可夫模型的参数。将观测序列数据看作观测数据O，状态序列数据看作不可观测的隐数据I，那么隐马尔可夫模型事实上是一个含有隐变量的概率模型。
2）EM算法：分两步（E与M）
（1）E步：（求Q函数）
（2） M步：（极大化Q函数求模型参参数）
五、预测算法
所谓预测问题，是已知模型参数以及“观测序列”的条件下，求最有可能出现的“状态序列”的问题。 如果将状态转移概率理解为距离的倒数，概率最大化等价于距离最小化，因此“预测问题”相当于“最短路径问题
1、近似算法
1）近似算法的想法是
在每个时刻t，选择在该时刻最有可能出现的状态it*，得到一个状态序列作为预测的结果。
2）近似算法的优点：
计算简单，其缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分。该方法得到的状态序列中有可能存在转移概率为0的相邻状态
2、维特比算法
维特比算法实际是用动态规划解隐马尔可夫模型预侧问题，即用动态规划(dynamic programming)求概率最大路径(最优路径)。一条路径对应着一个状态序列。
根据动态规划原理，最优路径具有这样的特性：如果最优路径在时刻t通过结点it*，那么这一路径从结点it*到终点iT*的部分路径，对于从it*到iT*的所有可能的部分路径来说，必须是最优的。依据这一原理，我们只需从时刻t=1开始，递推地计算在时刻t状态为i的各条部分路径的最大概率，直至得到时刻t=T状态为i的各条路径的最大概率。时刻t=T的最大概率即为最优路径的概率P*。最优路径的终结点iT*也同时得到。之后，从终结点iT*开始，由后向前逐步求得结点iT-1* , ... , i1*。