1. 隐马尔科夫模型(HMM)
隐马尔可夫模型(Hidden Markov Model),简称HMM, 是一种基于 概率统计 的模型,是一种结构最简单的 动态贝叶斯网 ,是一种重要的 有向图模型 。它用来描述一个含有隐含未知参数的 马尔可夫过程(Markov Process) 。其难点是从 可观察参数 中确定该过程的 隐参数 ,然后利用这些参数来作进一步的分析。
马尔可夫过程 (Markov Process),它因俄罗斯数学家安德烈·马尔可夫而得名,代表数学中具有马尔可夫性质的离散 随机过程 。它的原始模型马尔可夫链,由安德烈·马尔可夫于1907年提出。
X1, … , Xn,每个状态值取决于前面有限个状态。如果 Xn+1 对于过去状态的条件概率分布仅是 Xn 的一个函数,则
在马尔科夫链中,每一个圆圈代表相应时刻的状态,有向边代表了可能的状态转移,权值表示状态转移概率。
这里“隐”指的是马尔科夫链中任意时刻的状态变量是不可见的,也就是说状态序列S0,S1,...,St无法直接观测到。但是HMM中每时刻有一个可见的观测值Ot与之对应,而且Ot有且仅于当前时刻隐状态St有关,St外化表现为Ot的概率称为输出概率,因此隐马尔科夫模型的结构图如下所示。
因此,隐马尔科夫模型中马尔科夫链指的是隐状态S0,S1,...,St序列。
HMM模型可以用五元组(O,S,A,B,π)表示。其中
根据以上HMM模型五元组表示,我们可以归纳出HMM模型解决的三个经典的问题。
如何用简单易懂的例子解释隐马尔可夫模型? https://www.zhihu.com/question/20962240
2. 02 隐马尔可夫模型 - HMM的三个问题 - 概率计算问题
01 隐马尔可夫模型 - 马尔可夫链、HMM参数和性质
假设有三个盒子,编号为1,2,3;每个盒子都装有黑白两种颜色的小球,球的比例。如下:
按照下列规则的方式进行有放回的抽取小球,得到球颜色的观测序列: 1、按照π的概率选择一个盒子,从盒子中随机抽取出一个球,记录颜色后放回盒子中; 2、按照某种条件概率选择新的盒子,重复该操作; 3、最终得到观测序列:“白黑白白黑”
例如: 每次抽盒子按一定的概率来抽,也可以理解成随机抽。 第1次抽了1号盒子①,第2次抽了3号盒子③,第3次抽了2号盒子②.... ; 最终如下: ①→③→②→②→③ 状态值 白→黑→白→白→黑 观测值
1、 状态集合: S={盒子1,盒子2,盒子3} 2、 观测集合: O={白,黑} 3、 状态序列和观测序列的长度 T=5 (我抽了5次) 4、 初始概率分布: π 表示初次抽时,抽到1盒子的概率是0.2,抽到2盒子的概率是0.5,抽到3盒子的概率是0.3。 5、 状态转移概率矩阵 A:a11=0.5 表示当前我抽到1盒子,下次还抽到1盒子的概率是0.5; 6、 观测概率矩阵 - 混淆矩阵 - 为了不和之前的混淆矩阵概念冲突,可以称之为发射矩阵,即从一个状态发射到另一个状态: B:如最初的图,b11=第一个盒子抽到白球概率0.4,b12=第一个盒子抽到黑球概率0.6;
在给定参数π、A、B的时候,得到观测序列为“白黑白白黑”的概率是多少?
这个时候,我们不知道隐含条件,即不知道状态值:①→③→②→②→③ ; 我们如何根据π、A、B求出测序列为“白黑白白黑”的概率? 下面给出解决方案。
前向-后向算法 给定模型λ=(A,B,π)和观测序列Q={q1,q2,...,qT},计算模型λ下观测到序列Q出现的概率P(Q|λ);
回顾上面的案例 ,λ=(A,B,π)已知。观测到序列 Q=白→黑→白→白→黑,但我们不知道 状态序列 I=①→③→②→②→③;我们要求解 P(Q|λ) ,即Q=白→黑→白→白→黑 这个观测序列发生的概率。 可以用前向-后向算法来实现 。
Baum-Welch算法(状态未知) 已知观测序列Q={q1,q2,...,qT},估计模型λ=(A,B,π)的参数,使得在该模型下观测序列P(Q|λ)最大。
Baum-Welch算法是EM算法的一个特例,专门用来 求解 隐马尔科夫中隐状态参数 λ=(A,B,π) 。即:根据已知的 观测到序列 Q=白→黑→白→白→黑,去寻找整个模型的一组隐状态参数λ=(A,B,π),使得在模型中 观测序列 发生的可能性P(Q|λ)最大。
Viterbi算法 给定模型λ=(A,B,π)和观测序列Q={q1,q2,...,qT},求给定观测序列条件概率P(I|Q,λ)最大的状态序列I。
已知 观测到序列 Q=白→黑→白→白→黑,当我们得到λ=(A,B,π)后,我们用 Viterbi算法 求出在哪一种 状态序列 发生的可能性最大,即,求出 状态序列 I=①→③→②→②→③;即,抽取什么样的盒子顺序,更可能得到白→黑→白→白→黑这种结果。
1、直接计算法(暴力算法) 2、前向算法 3、后向算法
类似KNN计算最近邻时候的算法。《 01 KNN算法 - 概述 》 也就是说, 暴力算法 需要一个个遍历所有的状态去计算当前状态发生的概率。
按照概率公式,列举所有可能的长度为T的状态序列I={i1,i2,...,iT},求各个状态序列I与观测序列Q={q1,q2,...,qT}的联合概率P(Q,I;λ),然后对所有可能的状态序列求和,从而得到最终的概率P(Q;λ);
分析: 先思考这样一个问题:生成“白-黑-白-白-黑”这样的结果,是不是会有很多种盒子组合的序列来抽取,都会生成这样一个结果?我把这些可能出现“白-黑-白-白-黑”结果的盒子序列的联合概率求出来-P(Q,I;λ),即∑P(Q,I) = P(Q) ,P(Q) 是我们观测到“白-黑-白-白-黑”结果时,符合这个结果的所有状态序列I出现的概率。
公式运用:
设状态序列 I=③→②→①→①→②; T=5; P(I;λ) = π 3 a 32 a 21 a 11 a 12
因为: 在给定状态序列I后,Q中的每个观测值都独立。(贝叶斯网络原理) 贝叶斯网络 所以: P(Q|I;λ)可以用联乘的方式表示 (独立可以使用联合概率) I = ③→②→①→①→② Q=白→黑→白→白→黑 P(Q|I;λ) = b 3白 b 2黑 b 1白 b 1白 b 2黑
P(Q,I;λ) = P(Q|I;λ) × P(I;λ) = b 3白 b 2黑 b 1白 b 1白 b 2黑 × π 3 a 32 a 21 a 11 a 12
若: I 1 = ③→②→①→①→② I 2 = ①→②→③→①→② ... I T = ②→②→①→③→② 都能得出: Q = 白→黑→白→白→黑 因为我所有的盒子都能取出黑球和白球,所以T的值=3 5 ;
∑P(Q,I;λ) 计算的是 I 1 ~ I T 这些状态序列情况下,求出的P(Q,I;λ)的和。
前向 和 后向 算法是运用某种递归(递推)的方式,帮助我们尽快得求解最终结果。
解析: 如果 t 这一时刻观察到的状态是 q t = 雨天;其中y={干,湿,湿... 湿}共t个状态。 先不考虑λ。 α t 是 1时刻~t时刻 所有观测值y1,y2,...yt ,qt 出现的联合概率。 β t 是 t+1时刻~T时刻 所有观测值y t+1 ,y t+2 ,...y T 出现的联合概率。
前向概率-后向概率 指的其实是在一个观测序列中,时刻t对应的状态为si的概率值转换过来的信息。
分析2~3步的推导: 因为q 1 ~ q t 这些条件对 q t+1 ~ q T 的产生没有影响 (理由:贝叶斯网络),所以这些条件可以去掉。
定义:给定λ,定义到时刻t部分观测序列为q1,q2,...,qt且状态为si的概率为 前向概率 。 记做:
在给定参数π、A、B的时候,得到观测序列为“白黑白白黑”的概率是多少?
定义:给定λ,定义到时刻t状态为si的前提下,从t+1到T部分观测序列为qt+1,qt+2,...,qT的概率为 后向概率 。 记做:
分析上面的公式: 如果一共只有t个时间点,t+1的时刻不存在。那么t+1以后发生的是必然事件。 所以 β t (i) = P(q t+1 ,q t+2 ,...,q T ) = 1; 如果实在不理解也没关系,我们姑且认为认为定义了一个初始值,即 β T (i) = 1 ;
从T-1时刻,倒推到1时刻。 首先,β t+1 (j)是什么?是t+1时刻,在状态sj的前提下,下图中圈起来这部分的联合概率。
β t (j)是什么?是t时刻,在状态sj的前提下,下图中圈起来这部分的联合概率。
求给定模型λ和观测序列Q的情况下,在时刻t处于状态si的概率,记做:
单个状态概率的意义主要是用于判断在每个时刻最可能存在的状态,从而可以得到一个状态序列作为最终的预测结果。
求给定模型λ和观测序列Q的情况下,在时刻t处于状态si并时刻t+1处于状态sj概率,记做:
03 隐马尔可夫模型 - HMM的三个问题 - 学习问题
3. 隐马尔可夫模型
隐马尔可夫模型是关于时序的概率模型,描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测从而产生观测随机序列的过程。
隐马尔可夫模型的形式定义如下:
设 是所有可能 状态的集合 , 是所有可能 观测的集合 :
其中 为可能状态数, 为可能观测数。
是长度为 的 状态序列 , 是对应的 观测序列 :
是 状态转移概率矩阵 :
其中:
是 观测概率矩阵 :
其中:
是 初始状态概率向量 :
其中:
隐马尔可夫模型由初始状态概率向量 、状态转移概率矩阵 和观测概率矩阵 决定。 因此隐马尔可夫模型 可表示为:
具体来说,长度为 的观测序列的生成过程如下:按照初始状态分布 产生状态 ,按状态 的观测概率分布 生成 ,按状态 的状态转移概率分布 产生状态 ,依次递推。
(1) 齐次马尔可夫性假设 ,即隐藏的马尔科夫链在任意时刻 的状态只依赖于其前一时刻的状态,与其他时刻状态及观测无关,也与时刻 无关。
(2) 观测独立性假设 ,即任意时刻的观测只依赖于该时刻的马尔科夫链状态,与其它观测状态无关。
(1) 概率计算问题 :给定模型 和观测序列 ,计算在模型 下序列 出现的概率 。
(2) 学习问题 :已知观测序列 ,估计模型 参数,使得在该模型下观测序列 最大。
(3) 预测问题 :已知模型 和观测序列 ,求使得 最大的状态序列 。
接下来分别阐述这三个问题的解决方法。
状态 的概率是:
对固定的 观测序列 的概率是:
同时出现的联合概率为:
从而:
可以看到,上式是对所有可能的 序列求和,而长度为 的 序列的数量是 数量级的,而 的计算量是 级别的,因此计算量为 ,非常大, 这种算法在实际中不可行 。
首先定义 前向概率 :给定隐马尔可夫模型 ,定义到时刻 部分观测序列为 且状态为 的概率为前向概率,记作:
观测序列概率的前向算法 如下:
(1)初值:
(2)递推,对 :
(3)终止:
前向算法高效的关键是 局部计算前向概率,然后利用路径结构将前向概率递推到全局,得到 。前向概率算法计算量是 级别的。
首先定义 后向概率 :给定隐马尔可夫模型 ,定义在时刻 状态为 的条件下,从 到 部分观测序列为 的概率为后向概率,记作:
观测序列概率的后向算法 如下:
(1)初值:
(2)递推,对 :
(3)终止:
若有 个长度相同观测序列和对应状态序列 则可利用极大似然估计得到隐马尔可夫模型参数:
设样本中时刻 处于状态 时刻 转移到状态 的频数为 ,那么状态转移概率 的估计为:
设样本中状态为 观测为 的频数为 ,那么观测概率 的估计为:
初始状态 的估计 为 个样本中初始状态为 的频率。
假设给定训练数据只包含 个长度为 的观测序列 而没有对应状态序列,我们可以把状态数据看作不可观测的隐数据 ,则隐马尔可夫模型事实上是一个含有隐变量的概率模型:
其参数可由EM算法实现。
近似算法的思想是,在每个时刻 选择在该时刻最有可能出现的状态 ,从而得到一个状态序列 。
近似算法的优点是计算简单,缺点是不能保证预测的状态序列整体是最有可能的状态序列,因为预测的状态序列可能有实际不发生的部分,比如存在转移概率为0的相邻状态。尽管如此,近似算法还是有用的。
维特比算法实际上是用动态规划解隐马尔可夫模型预测问题,即用动态规划求概率最大路径(最优路径),此路径对应一个状态序列。
定义 在时刻 状态为 的所有单个路径 中概率最大值 为:
由定义得递推式:
定义 在时刻 状态为 的所有单个路径 中概率最大路径的第 个结点 为:
维特比算法 如下:
(1)初始化:
(2)递推,对 :
(3)终止:
(4)回溯,对 :
最优路径为
4. 隐马尔可夫模型的基本算法
针对以下三个问题,人们提出了相应的算法*1 评估问题: 前向算法*2 解码问题: Viterbi算法*3 学习问题: Baum-Welch算法(向前向后算法)
5. 马尔科夫的隐马尔可夫模型
隐马尔可夫模型(Hidden Markov Model,HMM)是统计模型,它用来描述一个含有隐含未知参数的马尔可夫过程。其难点是从可观察的参数中确定该过程的隐含参数。然后利用这些参数来作进一步的分析,例如模式识别。
6. 隐马尔可夫模型的基本概述
一种HMM可以呈现为最简单的动态贝叶斯网络。隐马尔可夫模型背后的数学是由LEBaum和他的同事开发的。它与早期由RuslanL.Stratonovich提出的最优非线性滤波问题息息相关,他是第一个提出前后过程这个概念的。在简单的马尔可夫模型(如马尔可夫链),所述状态是直接可见的观察者,因此状态转移概率是唯一的参数。在隐马尔可夫模型中,状态是不直接可见的,但输出依赖于该状态下,是可见的。每个状态通过可能的输出记号有了可能的概率分布。因此,通过一个HMM产生标记序列提供了有关状态的一些序列的信息。注意,“隐藏”指的是,该模型经其传递的状态序列,而不是模型的参数;即使这些参数是精确已知的,我们仍把该模型称为一个“隐藏”的马尔可夫模型。隐马尔可夫模型以它在时间上的模式识别所知,如语音,手写,手势识别,词类的标记,乐谱,局部放电和生物信息学应用。隐马尔可夫模型可以被认为是一个概括的混合模型中的隐藏变量(或变量),它控制的混合成分被选择为每个观察,通过马尔可夫过程而不是相互独立相关。最近,隐马尔可夫模型已推广到两两马尔可夫模型和三重态马尔可夫模型,允许更复杂的数据结构的考虑和非平稳数据建模。
7. 隐马尔可夫模型的模型表达
隐马尔可夫模型(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,π)三元组来简洁的表示一个隐马尔可夫模型。隐马尔可夫模型实际上是标准马尔可夫模型的扩展,添加了可观测状态集合和这些状态与隐含状态之间的概率关系。
8. 隐马尔可夫模型(基础)
假设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)建模,因此是一个生成式模型。