隐马尔可夫模型的基本问题
2024-05-09
1. 隐马尔可夫模型的基本问题
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的概率最大？
2. 隐马尔可夫模型的模型表达
隐马尔可夫模型（HMM）可以用五个元素来描述，包括2个状态集合和3个概率矩阵：1. 隐含状态 S这些状态之间满足马尔可夫性质，是马尔可夫模型中实际所隐含的状态。这些状态通常无法通过直接观测而得到。（例如S1、S2、S3等等)2. 可观测状态 O在模型中与隐含状态相关联，可通过直接观测而得到。(例如O1、O2、O3等等，可观测状态的数目不一定要和隐含状态的数目一致。）3. 初始状态概率矩阵 π表示隐含状态在初始时刻t=1的概率矩阵，(例如t=1时，P(S1)=p1、P(S2)=P2、P(S3)=p3，则初始状态概率矩阵 π=[ p1 p2 p3 ].4. 隐含状态转移概率矩阵 A。描述了HMM模型中各个状态之间的转移概率。其中Aij = P( Sj | Si ),1≤i,,j≤N.表示在 t 时刻、状态为 Si 的条件下，在 t+1 时刻状态是 Sj 的概率。5. 观测状态转移概率矩阵 B （英文名为Confusion Matrix，直译为混淆矩阵不太易于从字面理解）。令N代表隐含状态数目，M代表可观测状态数目，则：Bij = P( Oi | Sj ), 1≤i≤M,1≤j≤N.表示在 t 时刻、隐含状态是 Sj 条件下，观察状态为 Oi 的概率。总结：一般的，可以用λ=(A,B,π)三元组来简洁的表示一个隐马尔可夫模型。隐马尔可夫模型实际上是标准马尔可夫模型的扩展，添加了可观测状态集合和这些状态与隐含状态之间的概率关系。
3. 从马尔可夫模型到隐马尔可夫模型
马尔可夫模型个人认为这个概念应该是从 随机过程 里面提出来的，由马尔可夫过程过来的概念。实际上掌握了随机过程里面对马尔可夫过程的特殊情况：离散参数离散状态的马尔可夫链的数学运算的话。就能够很好解决马尔可夫模型上面的计算问题，包括隐马尔科夫模型。讲马尔可夫模型以及过程重点在于其满足的性质-马尔可夫性。 随机过程： 现实中时常出现，某个事物满足一定的随机分布，但是其随机分布会随着时间的变化而变化。我们假设其在时刻 符合随机分布 并且用随机变量 来表示。假设 。但是在时间 的时候就符合随机分布 并且用随机变量 来表示。假设 。也就是说某个事物的某个特征会随着时间的变化其对应的分布也会发生变化。这样一个总体的过程，称之为 随机过程。 具体例子： 灯泡寿命问题，灯泡其实在每个时间点上都有一定的可能性会损坏，在这个时间点上损坏的可能性符合一个具体的正态分布（其 是确定的），而随着时间的久远，灯泡损坏的可能性就变大了。所以在之后的某个时间点上灯泡损坏的可能性可能就符合另外一个具体的正态分布（其 就和先前不一样了，会有变坏的趋势）。灯泡损坏在传统的概率论中也是一个经典例子，可能传统的概率论会认为灯泡的寿命长短符合一个随机分布，并且用一个随机变量来表示，我们研究这个分布的特征。这里和传统的概率论中不一样，可以发现的是，引入了随机过程，可以对随机现象更加深入彻底地描述和研究。 定义随机过程中的一些量。 参数：也就是上述的时间，如果是和时间有关，往往叫做时间序列。但是很多的现象研究不是和时间相关的。 状态：也就是上述的随着时间变化的随机变量。 马尔可夫过程：满足马尔科夫性的随机过程。 以后再解释 马尔可夫性： 马尔可夫链： 马尔可夫模型和上述的关系。 具体讲一下 隐马尔可夫模型。 和普通的马尔可夫不一样，马尔可夫模型是可以确定状态序列的。也就是说序列上的每个项的分布是怎么样的是已知的。而隐马尔可夫模型是连序列上的每个项的是什么分布都不能够知道，都是随机的。 对于这样的一个随机模型。 经常要解决三个基本问题： 1). 给定 和 ，求解 。 又叫作 计算问题。 2). 给定 和 ，求解一个状态转换序列 ，使得最优可能产生上面的序列。又叫做估计问题。 3). 在模型参数（A或者B）未知或者参数不准确的情况下，由 来调整参数。又叫做训练问题。 状态一定是按着产生了部分观察序列来的。考虑前缀。 表示处理到了n,观察序列到n为止都是答案的概率。但是不好转移，转移的时候要枚举前后隐藏状态，考虑把隐藏状态也表示出来。 表示处理到了n，并且第n个状态为j的概率。 范围： 结果： 初始化： 转移： 知道 和 ，求Q，状态序列，使得产生 的可能性最大。 定义： 这个函数的含义是： 模型在时刻t处于状态i，观察到 的最佳状态转换序列的概率。 从而有了转移方程： 而 就是 因此 的转移过程构成了一个图，而Q就是上面的最优路径。 利用 观察数据进行对模型参数 或者 或者 进行预测和修正，训练问题，又可以叫做预测问题。 并且这个问题其实是带有隐变量的最大似乎估计，也就是EM算法。 直接讲EM,用数学角度来引入 或者 用递归式来求解含有隐变量的参数估计 都是可以的，后者会比较清楚。 但是课上老师给出了另外一种比较好的解释： 考虑第三个问题，实际上应该分两种情况。 1：带指导的参数学习。 给出的数据是这样的： 状态/观察数据。 硬币中的例子就是 H/1 H/1 T/1 T/2 H/3 T/3 T/2 H/1 T/2 H/3 H/3 H/1 其实当拥有了数据 状态/观察数据 是可以直接对参数进行估计的。 假设是齐次的（一般也是齐次的，概率只和状态有关，和时间关系不大，放在词句中就是词语所在的句子的部位关系不是很大，而是上下文内容关系比较大。）， 考虑aij 指的是在状态i和状态j的转移概率。 可以直接对上面2个2个统计进行参数估计。 考虑bi(o_j)也就是状态为i输出为o_j的。 一个一个枚举来即可。 考虑pi_i。也就是初始状态。 一个一个枚举状态即可。 带有指导的是有缺点的： 数据上不可行，状态这样的数据其实都是人工标注的。 数据量要求比较大。 但是在NLP中这个方法是很重要的。因为效果比较好。 2：不带指导的参数学习 数据上只给出了 观察序列，没有状态序列。 实际上1中就出了答案。没有状态序列，我们就枚举状态序列。 比如上述。如果观察出来了 1 2 2 那么我们就考虑以下 1 2 2 HHH HHT HTH HTT THH THT TTH TTT 所有情况。 所以就产生了 H/1 H/2 H/2 H/1 H/2 T/2 .... 然后分组进行统计参数估计即可。 但是这里有两个问题： 1：状态太多了。N^T。 2：给每个状态的权重是一样的。不是很科学。（实际上还行，如果使用熵最大原理。） 那么怎么办？解决2考虑给不同状态加权重，那么要有一个先验的的知识： 咱们先给出先验的 模型参数。 那么就可以计算P(Q|O,人)P（Q,O|人）这样的东西了。 明显可以用P(Q|O,人)作为一个路径序列的权重。 但是这样计算的时候，路径序列很长。并且转移路径还是N^T条。 不可行。 避开对路径的考虑。考虑参数abt最多只有涉及两个时间点的。 我们如果只关注两个时间点之间的状态。那么就可以变成二维的。 使Q不是一个路径的。而是只是两个时间点之间的状态。 q_t = i q_t+1 = j 。把这个概率计算出来的话。就能直接对aij这样的进行估计了。 （实际上只是换了一种计数方式，就减少了问题规模，因为咱们关注的也只是路径上两个点两个点之间的。） 由此引出Baum_Welch算法： 定义以下： 这样就能对参数们进行评估了。有以下： 这样只要挑一个满足条件的初始值，然后迭代求解即可。
4. 马尔科夫的隐马尔可夫模型
隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。
5. 隐马尔可夫模型
隐马尔可夫模型是关于时序的概率模型，描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列，再由各个状态生成一个观测从而产生观测随机序列的过程。
隐马尔可夫模型的形式定义如下：
设 是所有可能 状态的集合 ， 是所有可能 观测的集合 ：
其中 为可能状态数， 为可能观测数。
是长度为 的 状态序列 ， 是对应的 观测序列 ：
是 状态转移概率矩阵 ：
其中：
是 观测概率矩阵 ：
其中：
是 初始状态概率向量 ：
其中：
隐马尔可夫模型由初始状态概率向量 、状态转移概率矩阵 和观测概率矩阵 决定。 因此隐马尔可夫模型 可表示为：
具体来说，长度为 的观测序列的生成过程如下：按照初始状态分布 产生状态 ，按状态 的观测概率分布 生成 ，按状态 的状态转移概率分布 产生状态 ，依次递推。
（1） 齐次马尔可夫性假设 ，即隐藏的马尔科夫链在任意时刻 的状态只依赖于其前一时刻的状态，与其他时刻状态及观测无关，也与时刻 无关。
（2） 观测独立性假设 ，即任意时刻的观测只依赖于该时刻的马尔科夫链状态，与其它观测状态无关。
（1） 概率计算问题 ：给定模型 和观测序列 ，计算在模型 下序列 出现的概率 。
（2） 学习问题 ：已知观测序列 ，估计模型 参数，使得在该模型下观测序列 最大。
（3） 预测问题 ：已知模型 和观测序列 ，求使得 最大的状态序列 。
接下来分别阐述这三个问题的解决方法。
状态 的概率是：
对固定的 观测序列 的概率是：
同时出现的联合概率为：
从而：
可以看到，上式是对所有可能的 序列求和，而长度为 的 序列的数量是 数量级的，而 的计算量是 级别的，因此计算量为 ，非常大， 这种算法在实际中不可行 。
首先定义 前向概率 ：给定隐马尔可夫模型 ，定义到时刻 部分观测序列为 且状态为 的概率为前向概率，记作：
观测序列概率的前向算法 如下：
（1）初值：
（2）递推，对 ：
（3）终止：
前向算法高效的关键是 局部计算前向概率，然后利用路径结构将前向概率递推到全局，得到 。前向概率算法计算量是 级别的。
首先定义 后向概率 ：给定隐马尔可夫模型 ，定义在时刻 状态为 的条件下，从 到 部分观测序列为 的概率为后向概率，记作：
观测序列概率的后向算法 如下：
（1）初值：
（2）递推，对 ：
（3）终止：
若有 个长度相同观测序列和对应状态序列 则可利用极大似然估计得到隐马尔可夫模型参数：
设样本中时刻 处于状态 时刻 转移到状态 的频数为 ，那么状态转移概率 的估计为：
设样本中状态为 观测为 的频数为 ，那么观测概率 的估计为：
初始状态 的估计 为 个样本中初始状态为 的频率。
假设给定训练数据只包含 个长度为 的观测序列 而没有对应状态序列，我们可以把状态数据看作不可观测的隐数据 ，则隐马尔可夫模型事实上是一个含有隐变量的概率模型：
其参数可由EM算法实现。
近似算法的思想是，在每个时刻 选择在该时刻最有可能出现的状态 ，从而得到一个状态序列 。
近似算法的优点是计算简单，缺点是不能保证预测的状态序列整体是最有可能的状态序列，因为预测的状态序列可能有实际不发生的部分，比如存在转移概率为0的相邻状态。尽管如此，近似算法还是有用的。
维特比算法实际上是用动态规划解隐马尔可夫模型预测问题，即用动态规划求概率最大路径（最优路径），此路径对应一个状态序列。
定义 在时刻 状态为 的所有单个路径 中概率最大值 为：
由定义得递推式：
定义 在时刻 状态为 的所有单个路径 中概率最大路径的第 个结点 为：
维特比算法 如下：
（1）初始化：
（2）递推，对 :
（3）终止：
（4）回溯，对 ：
最优路径为
6. 隐马尔可夫模型的介绍
隐马尔可夫模型（Hidden Markov Model，HMM）是统计模型，它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析，例如模式识别。是在被建模的系统被认为是一个马尔可夫过程与未观测到的（隐藏的）的状态的统计马尔可夫模型。
7. 隐马尔可夫模型的引言
隐马尔可夫模型（Hidden Markov Model，HMM）作为一种统计分析模型，创立于20世纪70年代。80年代得到了传播和发展，成为信号处理的一个重要方向，现已成功地用于语音识别，行为识别，文字识别以及故障诊断等领域。
8. 隐马尔可夫模型的历史
隐马尔可夫模型最初是在20世纪60年代后半期Leonard E. Baum和其它一些作者在一系列的统计学论文中描述的。HMM最初的应用之一是开始于20世纪70年代中期的语音识别。在1980年代后半期，HMM开始应用到生物序列尤其是DNA的分析中。此后，在生物信息学领域HMM逐渐成为一项不可或缺的技术。
最新文章
热门文章
推荐阅读