一、知识梳理

参考链接，参考链接

二、隐马尔可夫模型

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*。

                                                                                        具体请看这里