隐马尔可夫模型三个基本问题以及相应的算法

⑴ 隐马尔可夫模型

隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。

隐马尔可夫模型的形式定义如下：

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

其中 为可能状态数， 为可能观测数。

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

是 状态转移概率矩阵 ：

其中：

是 观测概率矩阵 ：

其中：

是 初始状态概率向量 ：

其中：

隐马尔可夫模型由初始状态概率向量 、状态转移概率矩阵 和观测概率矩阵 决定。 因此隐马尔可夫模型 可表示为：

具体来说，长度为 的观测序列的生成过程如下：按照初始状态分布 产生状态 ，按状态 的观测概率分布 生成 ，按状态 的状态转移概率分布 产生状态 ，依次递推。

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

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

（1） 概率计算问题 ：给定模型 和观测序列 ，计算在模型 下序列 出现的概率 。

（2） 学习问题 ：已知观测序列 ，估计模型 参数，使得在该模型下观测序列 最大。

（3） 预测问题 ：已知模型 和观测序列 ，求使得 最大的状态序列 。

接下来分别阐述这三个问题的解决方法。

状态 的概率是：

对固定的 观测序列 的概率是：

同时出现的联合概率为：

从而：

可以看到，上式是对所有可能的 序列求和，而长度为 的 序列的数量是 数量级的，而 的计算量是 级别的，因此计算量为 ，非常大， 这种算法在实际中不可行 。

首先定义 前向概率 ：给定隐马尔可夫模型 ，定义到时刻 部分观测序列为 且状态为 的概率为前向概率，记作：

观测序列概率的前向算法 如下：

（1）初值：

（2）递推，对 ：

（3）终止：

前向算法高效的关键是 局部计算前向概率，然后利用路径结构将前向概率递推到全局，得到 。前向概率算法计算量是 级别的。

首先定义 后向概率 ：给定隐马尔可夫模型 ，定义在时刻 状态为 的条件下，从 到 部分观测序列为 的概率为后向概率，记作：

观测序列概率的后向算法 如下：

（1）初值：

（2）递推，对 ：

（3）终止：

若有 个长度相同观测序列和对应状态序列 则可利用极大似然估计得到隐马尔可夫模型参数：

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

设样本中状态为 观测为 的频数为 ，那么观测概率 的估计为：

初始状态 的估计 为 个样本中初始状态为 的频率。

假设给定训练数据只包含 个长度为 的观测序列 而没有对应状态序列，我们可以把状态数据看作不可观测的隐数据 ，则隐马尔可夫模型事实上是一个含有隐变量的概率模型：

其参数可由EM算法实现。

近似算法的思想是，在每个时刻 选择在该时刻最有可能出现的状态 ，从而得到一个状态序列 。

近似算法的优点是计算简单，缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分，比如存在转移概率为0的相邻状态。尽管如此，近似算法还是有用的。

维特比算法实际上是用动态规划解隐马尔可夫模型预测问题，即用动态规划求概率最大路径（最优路径），此路径对应一个状态序列。

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

由定义得递推式：

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

维特比算法 如下：

（1）初始化：

（2）递推，对 :

（3）终止：

（4）回溯，对 ：

最优路径为

⑵ 隐马尔可夫模型的基本问题

1. 评估问题。
给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，怎样有效计算某一观测序列的概率，进而可对该HMM做出相关评估。例如，已有一些模型参数各异的HMM，给定观测序列O=O1O2O3…Ot，我们想知道哪个HMM模型最可能生成该观测序列。通常我们利用forward算法分别计算每个HMM产生给定观测序列O的概率，然后从中选出最优的HMM模型。
这类评估的问题的一个经典例子是语音识别。在描述语言识别的隐马尔科夫模型中，每个单词生成一个对应的HMM，每个观测序列由一个单词的语音构成，单词的识别是通过评估进而选出最有可能产生观测序列所代表的读音的HMM而实现的。
2.解码问题
给定观测序列 O=O1O2O3…Ot 和模型参数λ=(A,B,π)，怎样寻找某种意义上最优的隐状态序列。在这类问题中，我们感兴趣的是马尔科夫模型中隐含状态，这些状态不能直接观测但却更具有价值，通常利用Viterbi算法来寻找。
这类问题的一个实际例子是中文分词，即把一个句子如何划分其构成才合适。例如，句子“发展中国家”是划分成“发展-中-国家”，还是“发展-中国-家”。这个问题可以用隐马尔科夫模型来解决。句子的分词方法可以看成是隐含状态，而句子则可以看成是给定的可观测状态，从而通过建HMM来寻找出最可能正确的分词方法。
3. 学习问题。
即HMM的模型参数λ=(A,B,π)未知，如何调整这些参数以使观测序列O=O1O2O3…Ot的概率尽可能的大。通常使用Baum-Welch算法以及Reversed Viterbi算法解决。
怎样调整模型参数λ=(A,B,π)，使观测序列 O=O1O2O3…Ot的概率最大？

⑶ 隐马尔可夫模型（基础）

假设t时刻的状态只与t-1时刻的状态有关，与更早的时刻无关，这一假设称为一阶马尔可夫假设。如果状态有n种取值，在t时刻取任何一个值与t-1时刻取任何一个值的条件概率构成了一个n×n的矩阵A，称为状态转移概率矩阵。无论t时刻的状态值是什么，在下一时刻一定会转向n个状态种一个，因此他们的转移概率和必须为1。

在实际应用种，人们不能直接观察到状态的值，即状态的值是隐含的，只能得到观测的值。因此对模型进行扩充，得到隐马模型。

观测序列是能得到的值。

状态序列是因，观测序列是果，因为处于某种状态才有了某一观测值。

定义状态观测矩阵B，表示t时刻状态值为s时的观测值为v的概率

t时刻的状态z=i的概率最大状态序列中，t-1时刻的状态值，有了这两个变量，就可以得到维特比算法。

训练时给定一组样本，确定状态转移矩阵和观测矩阵，通过最大似然估计实现。如果已知训练样本集中每个观测序列对应的状态序列，给定初始状态如：p0=[0.5, 0.2, 0.3], k步转化过程为：p0=p0*pk。计算机程序需要利用迭代变量，借助循环实现。经过多步转化p0收敛于固定值(稳态)。可以通过最大似然估计得到模型参数。

状态空间：隐状态S的取值范围

观测空间：观测状态O的取值范围

转移概率：矩阵各元素都是用概率表示。其值非负，并且各行元素之和等于1。在一定条件下是互相转移的，故称为转移概率矩阵。矩阵中的行数与列数可以相等，也可以不等。当它们相等时，矩阵就是一个方阵。由转移概率组成的矩阵就是转移概率矩阵。也就是说构成转移概率矩阵的元素是一个个的转移概率不同状态之间的转移概率，可以用转移矩阵表示，记做a

发射概率：初始状态的概率分布，在知道当前标签的情况下，发射的概率，记做π

输出概率：基于当前状态，不同输出的概率分布，记做b

模型参数λ = (a, b, π)

1、 齐次假设：即马尔科夫假设

2、 观测独立性假设：观测值只取决于对应的状态值，与其他状态无关

（1）首先, HMM模型表示为: lambda = HMM(A, B, pi), 其中A, B, pi都是模型的参数, 分别称作: 转移概率矩阵, 发射概率矩阵和初始概率矩阵.

（2）接着, 我们开始训练HMM模型, 语料就是事先准备好的一定数量的观测序列及其对应的隐含序列, 通过极大似然估计求得一组参数, 使由观测序列到对应隐含序列的概率最大.

（3）在训练过程中, 为了简化计算, 马尔可夫提出一种假设: 隐含序列中每个单元的可能性只与上一个单元有关. 这个假设就是着名的隐含假设.

（4）训练后, 我们就得到了具备预测能力的新模型: lambda = HMM(A, B, pi), 其中的模型参数已经改变.

（5）之后给定输入序列(x1, x2, ..., xn), 经过模型计算lambda(x1, x2, ..., xn)得到对应隐含序列的条件概率分布.

（6）最后, 使用维特比算法从隐含序列的条件概率分布中找出概率最大的一条序列路径就是我们需要的隐含序列: (y1, y2, ..., yn).

状态转移矩阵通过训练样本学习得到，采用最大似然估计。

初始状态取每种值的概率Π，状态转移概率矩阵A，观测概率矩阵B

隐马尔可夫模型需要解决以下三个问题：

（1）估值问题（观测序列出现的概率）。给定隐马尔可夫模型的参数A和B，计算一个观测序列x出现的概率值p（x）。前向后向算法

（2）解码问题（观测序列最大化的隐含序列）。给定隐马尔可夫模型的参数A和B以及一个观测序列x，计算最有可能产生此观测序列的状态序列z。

已知一个观测序列，寻找最有可能产生它的状态序列。维特比算法

（3）学习问题。给定隐马尔可夫模型的结构，但参数未知，给定一组训练样本，确定隐马尔可夫模型的参数A和B。

保姆韦尔奇算法

隐马尔可夫模型对条件概率p（x|z）建模，因此是一个生成式模型。