2022年隐马尔可夫总结 .pdf

隐马尔可夫 Hidden Markov Model， HMM 一、马尔可夫过程Markov Process 1、马尔可夫过程介绍马尔可夫过程(Markov Process)，它因俄罗斯数学家安德烈马尔可夫而得名，代表数学中具有 马尔可夫性质的离散随机过程。 该过程中， 每个状态的转移只依赖于之前的n个状态，这个过程被称为1 个 n 阶的模型， 其中 n 是影响转移状态的数目。最简单的马尔科夫过程就是一阶过程，每一个状态的转移只依赖于其之前的那一个状态。马尔可夫链是随机变量X1, , Xn的一个数列。这些变量的范围，即他们所有可能取值的集合，被称为“状态空间”，而 Xn的值则是在时间n 的状态。如果Xn+1对于过去状态的条件概率分布仅是Xn的一个函数，则这里 x 为过程中的某个状态。上面这个恒等式可以被看作是马尔可夫性质。2、马尔可夫过程举例以下图展示了天气这个例子中所有可能的一阶转移：注意一个含有N 个状态 的一阶过程有N2个状态转移。每一个转移的概率叫做状态转移概率(state transition probability) ，即从一个状态转移到另一个状态的概率。这所有的N2个概率可以用一个状态转移矩阵 来表示，其表示形式如下：对该矩阵有如下约束条件：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 16 页下面就是海藻例子的状态转移矩阵：这个矩阵表示， 如果昨天是晴天， 那么今天有50%的可能是晴天， 37.5%的概率是阴天，12.5%的概率会下雨，很明显，矩阵中每一行的和都是1。为了初始化这样一个系统，我们需要一个初始的概率向量：这个向量表示第一天是晴天。3、一阶马尔可夫过程定义如上述马尔可夫过程例子可知，我们为一阶马尔可夫过程定义了以下三个部分：状态 ：晴天、阴天和下雨；初始向量 ：定义系统在时间为0的时候的状态的概率；状态转移矩阵：每种天气转换的概率；所有的能被这样描述的系统都是一个马尔可夫过程。二、隐马尔可夫过程HMM 1、隐马尔可夫模型介绍隐马尔可夫模型(HMM) 是一个输出符号序列统计模型，具有T 个状态 X1,X2.Xt-1,它按一定的周期从一个状态转移到另一个状态，每次转移时，输出一个符号观测值。转移到哪一个状态， 转移时输出什么符号，分别由状态转移概率和转移时输出概率来决定。因为只能观测到输出符号的序列，而不能观测到状态转移序列即模型的观测序列是通过哪个状态路径是不知道的所以称为隐马尔可夫模型。2、隐马尔可夫过程举例下面是一个简单的例子。气象学上， 可通过年轮的宽窄了解各年的气候状况，利用年轮上的信息可推测出几千年来的气候变迁情况。年轮宽表示那年光照充足，风调雨顺； 假设年轮较窄，则表示那年温度低、雨量少，气候恶劣。为了简单起见，我们只考虑冷(code)，热精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 16 页(hot)两种温度。根据现代的气象知识可以知道，“冷”的一年跟着下一年为热的概率为，为冷的概率为； “热”的一年跟着下一年为热的概率为，为冷的概率为。可以简单的归纳为下面规律：我们将树的年轮简单分为小(small),中(middle), 大(large)三种，或者分别写成S,M,L 。根据现代的气象知识可以知道，热的一年树木年轮为“小”， “中” ， “大”的概率分别为；冷的一年树木年轮为“小” ， “中”， “大”的概率分别为。因此，冷(C)，热 (H) 对年轮的影响可以简单归纳为下面规律：在这个系统中， 状态序列是每年的温度H 或者 C。 因为下一年的温度只与上一年有关，所以从一个状态(温度 )转移到下一个状态(温度 )可以看成是一个一阶Markov process。因为无法观测过去的温度，状态序列也被称为隐藏状态。尽管我们不能观测过去的状态(温度 )序列，但是可以通过树的年轮给我们提供的信息预测温度。我们的目标就是充分利用可观测的年轮序列，来预测那些年的温度序列情况Markov 过程 。从上面规律可以得到，状态转移矩阵A:混淆矩阵(confusion matrix)B:假设初始状态矩阵, (如本例中是初始状态矩阵是最开始产生Hot 和 Cold 天气的概率 )这样可以得到天气与树年轮的概率图模型精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 16 页图中最开始产生Hot 天气的概率为由初始状态矩阵PI 决定 ，Hot 天气产生树年轮Small 的概率为， Hot 状态产生Hot 状态的概率为，接着Hot 产生 Middle 的概率为以此类推。因此可以得到隐藏天气序列HHCC 产生树木年轮序列为SMSL 的概率。使用这种方法我们就可以计算产生SMSL 序列存在的所有天气序列的概率。比较可得 P(CCCH) 的概率为，是最大的。结论：假设树木年轮序列为SMSL ，则最可能状态序列Markov process是 CCCH ；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 16 页产生树木年轮序列为SMSL 的概率为0.009629 所有可能相加 。3、HMM 的三个重要假设以下图显示了天气的例子中隐藏的状态和可以观察到的状态之间的关系。我们假设隐藏的状态是一个简单的一阶马尔可夫过程，并且他们两两之间都可以相互转换。对 HMM 来说，有如下三个重要假设，尽管这些假设是不现实的。假设 1： 马尔可夫假设状态构成一阶马尔可夫链假设 2： 不动性假设状态与具体时间无关假设 3： 输出独立性假设输出仅与当前状态有关4、HMM 的基本元素一个 HMM 可用一个5 元组 N, M, ， A，B 表示，其中：N 表示隐藏状态的数量，我们要么知道确切的值，要么猜测该值；M 表示可观测状态的数量，可以通过训练集获得；= i 为初始状态概率；A=aij 为隐藏状态的转移矩阵Pr(xt(i) | xt-1(j)B=bik 表示某个时刻因隐藏状态而导致可观察状态的概率，即混淆矩阵， Pr(ot(i) | xt(j) 。在状态转移矩阵和混淆矩阵中的每个概率都是时间无关的，即当系统演化时，这些矩阵并不随时间改变。对于一个N 和 M 固定的 HMM 来说，用 = , A, B 表示 HMM 参数。三、 HMM的三个基本问题1、问题 1识别问题1.1 问题描述给定模型 = , A, B 和观测序列O= O0, O1, , OT-1 ,如何快速有效的找到P(O|)？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 16 页解释： 假设我们已经有一个特定的隐马尔科夫模型和一个可观察状态序列集。我们也许想知道在所有可能的隐藏状态序列下，给定的可观察状态序列的概率。问题 1 可以归纳为：举例： 如小节的例子中，已知模型，观测序列O=SMSL ，求产生SMSL 年轮序列的概率。1.2 解决方案1.2.1 蛮力算法假设用图表示可以得到如下：其中：然而，这种直接的计算的方法(蛮力算法 )一般是不可行的，实际情况中，我们不可能知道每一种可能的路径，而且这种计算的计算量也是十分惊人的，到达大约数量级。如，当精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 16 页HMM 的状态数为5，观测序列长度为100 时，计算量到达，是完全无法接受的。因此需要更有效的算法，这就是Baum 等人提出的前向-后向算法。前向算法 (a-pass )前向算法即按输出观察值序列的时间，从前向后递推计算输出概率。首先说明以下符号的定义：由上面的符号的定义，则at(i)可由下面递推公式计算得到：解释：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 16 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 16 页使用这种前向递推计算算法的计算量大为减少，复杂度变为N2T。同样的 1 中例子，N=5,T=100 时，只需要大约2500 次乘法。1.2.3 后向算法 (-pass)与前向算法类似，向后算法即使按输出观察序列的时间，从后面向前递推计算输出概率的方法。首先说明以下符号的定义：由递推公式可得：解释：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 16 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 16 页2、问题 2解码问题2.1 问题描述给定模型 = , A, B 和观测序列O=O0, O1, , OT-1,找到最优的隐藏状态序列？解释： 根据可观察状态的序列找到一个最可能的隐藏状态序列。问题2 可以归纳为：举例： 如小节的例子中，已知模型，观测序列O=SMSL ，求最有可能产生SMSL序列的状态序列CCCH。2.2 解决方案2.2.1 蛮力算法如中计算每一条可能状态序列的概率，然后比较找出其中概率最大的一条就为我们需要的状态序列X。如开始的例1 中就是采用这种算法。这种算法虽然易理解，但是计算开销太大，一般不可取。2 前向后向算法在中我们详细的讨论了前向算法以及后向算法，而前向后向算法就是综合这两种算法。可以用来解决寻找最可能隐藏状态序列X 的问题。首先我们说明以下符号的定义：2.2.3 维特比 (Viterbi) 算法在给定了一个可观察序列和HMM的情况下，我们可以考虑递归的来寻找最可能的隐藏序列。 我们可以先定义一个部分概率，即到达某个中间状态的概率。接下来我们将讨论如何计算t=1 和 t=n (n1) 的部分概率。注意这里的部分概率和前向算法中的部分概率是不一样的，这里的部分概率表示的是在t 时刻最可能到达某个状态的一条路径的概率，而不是所有概率之和。1) 部分概率和部分最优路径考虑下面这个图以及可观察序列(dry, damp, soggy) 的一阶转移。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 16 页对于每一个中间状态和终止状态(t=3) 都有一个最可能的路径。比方说，在t=3 时刻的三个状态都有一个如下的最可能的路径：我们可以称这些路径为部分最优路径。这些部分最优路径都有一个概率，也就是部分概率。 和前向算法中的部分概率不一样，这里的概率只是一个最可能路径的概率，而不是所有路径的概率和。我们可以用(i, t) 来表示在t 时刻，到状态i 的所有可能的序列路径中概率最大的序列的概率， 部分最优路径就是到达这个最大概率的路径，对于每一个时刻的每一个状态都有这样一个概率和部分最优路径。最后，我们通过计算t=T 时刻的每一个状态的最大概率和部分最优路径，选择其中概率最大的状态和它的部分最优路径来得到全局的最优路径。2) 计算t=1 时刻的部分概率当 t=1 时刻的时候，到达某个状态最大可能的路径还不存在，但是我们可以直接使用在 t=1 时刻某个状态的概率和这个状态到可观察序列k1的转移概率：3) 计算t1 时刻的部分概率接下来我们可以根据t-1 时刻的部分概率来求t 时刻的部分概率。我们可以计算所有到状态X 的路径的概率，找到其中最可能的路径，也就是局部最优路径。注意到这里，到达X 的路径必然会经过t-1 时刻的A、B 和 C，所以我们可以利用精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 16 页之前的结果。到达X 的最可能的路径就是下面三个之一：(状态序列 )，. . .，A，X (状态序列 )， . . .，B，X (状态序列 )，. . .，C，X我们需要做的就是找到以AX 、 BX 和 CX 结尾的路径中概率最大的那个。根据一阶马尔科夫的假设，一个状态的发生只和之前的一个状态有关系，所以X 在某个序列的最后发生的概率只依赖于其之前的一个状态：Pr (到达 A 的最优路径 ) . Pr (X | A) . Pr ( 观察状态| X)有个了这个公式，我们就可以利用t-1 时刻的结果和状态转移矩阵和混淆矩阵的数据：将上面这个表达式推广一下，就可以得到t 时刻可观察状态为kt的第 i 个状态的最大部分概率的计算公式：其中aji 表示从状态j 转移到状态i 的概率， bikt表示状态i 被观察成kt的概率。4) 后向指针考虑以下图在每一个中间状态和结束状态都有一个部分最优概率(i, t)。但是我们的目的是找到最可能的隐藏状态序列，所以我们需要一个方法去记住部分最优路径的每一个节点。考虑到要计算t 时刻的部分概率，我们只需要知道t-1 时刻的部分概率，所以我们只需要记录那个导致了t 时刻最大部分概率的的状态，也就是说，在任意时刻，系统都必须处在一个能在下一时刻产生最大部分概率的状态。如以下图所示：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 16 页我们可以利用一个后向指针 来记录导致某个状态最大局部概率的前一个状态，即这里argmax 表示能最大化后面公式的j 值，同样可以发现这个公式和t-1 时刻的部分概率和转移概率有关，因为后向指针只是为了找到“我从哪里来”，这个问题和可观察状态没有关系，所以这里不需要再乘上混淆矩阵因子。全局的行为如以下图所示：5) 优点使用viterbi 算法对一个可观察状态进行解码有两个重要的优点：a) 通过使用递归来减少复杂度，这点和之前的前向算法是一样的b) 可以根据可观察序列找到最优的隐藏序列，这个的计算公式是：这里就是一个从左往右翻译的过程，通过前面的翻译结果得到后面的结果，起始点是初始向量。6补充但在序列某个地方有噪声干扰的时候，某些方法可能会和正确答案相差的较远。但是Viterbi 算法会查看整个序列来决定最可能的终止状态，然后通过后向指针来找到之前的状态，这对忽略孤立的噪声非常有用。Viterbi 算法提供了一个根据可观察序列计算隐藏序列的很高效的方法，它利用递归来降低计算复杂度，并且使用之前全部的序列来做判断，可以很好的容忍噪声。在计算的过程中，这个算法计算每一个时刻每一个状态的部分概率，并且使用一个后向指针来记录到达当前状态的最大可能的上一个状态。最后， 最可能的终止状态就是隐藏序列的最后一个状态，然后通过后向指针来查找整个序列的全部状态。3、问题 3模型训练问题3.1 问题描述实际上是一个模型参数估计问题，即对于初始模型和给定用于训练的观测序列O=O0, O1, , OT-1如何调整模型= , A, B 的参数，使得输出概率P(O|)最大？解释： 根据观察到的序列集来找到一个最有可能的HMM 。问题 3 可以归纳为：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 16 页3.2 解决方案在很多实际的情况下，HMM 不能被直接的判断，这就变成了一个学习问题，因为对于给定的可观察状态序列O 来说，没有任何一种方法可以精确地找到一组最优的HMM 参数 使 P(O | ) 最大，于是人们寻求使其局部最优的解决方法，而前向后向算法也称为 Baum-Welch 算法就成了HMM 学习问题的一个近似的解决方法。前向后向算法首先对于HMM 的参数进行一个初始的估计，但这个很可能是一个错误的猜测，然后通过对于给定的数据评估这些参数的的有效性并减少它们所引起的错误来更新HMM参数，使得和给定的训练数据的误差变小，这其实是机器学习中的梯度下降的思想。Baum-Welch算法首先我们说明以下符号的定义：根据前向 -后向算法，可以得到：由此可以推出重估公式：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 15 页，共 16 页精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 16 页