1 HMM 基本概念
1.1 定义
1.2 观测序列生成过程
1.3 HMM 的三个问题
2 概率计算算法
2.1 直接计算算法
2.2 前向算法 forward algorithm
2.3 后向算法
2.4 一些概率与期望值的计算
3 学习算法
3.1 监督学习
3.2 非监督学习 Baum-Welch 算法
3.3 Baum-Welch 模型参数估计公式
4 预测算法
4.1 近似算法
4.2 维特比算法 Viterbi algorithm
隐马尔可夫模型 (hidden Markov model,HMM) 是可用于标注问题的统计学习模型, 描述由隐藏马尔科夫链随机生成的观测序列的过程, 属于生成模型在语音识别, 自然语言处理, 生物信息, 模式识别有广泛的应用
1 HMM 基本概念
1.1 定义
马尔可夫链的定义: 随机过程中出现的字符, 每个字符出现的概率不是独立的而是依赖于此前的状态, 称为与之相对应的是独立链, 即每个字符出现的概率是独立的
参考链接: 马尔可夫和马尔可夫链
HMM 是关于时序的概率模型, 描述由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列, 再由各个状态生成一个观测随机序列的过程隐藏的马尔可夫链随机生成的状态的序列称为状态序列 (state sequence) 每个状态生成一个观测, 由此产生的观测的随机序列称为观测序列 (observation sequence) 序列的每个位置可以看做是一个时刻
很多术语:
设 Q 是所有可能状态的集合, V 是所有可能观测的集合 Q={q1,q2,,qN},V={v1,v2,,vM}, N 是可能的状态数, M 是可能的观测数
I 是长度为 T 的状态序列, O 是对应的观测序列, I=(i1,i2,,iT),O=(ν1,ν2,,νT)
A 是状态转移概率矩阵, A=[aij]NXN,αij=P(it+1=qj|it=qi),i=1,2,..,N;j=1,2,..N, 表明时刻 t 处于状态 qi 的条件下 t+1 转移状态的概率 qj
更好的理解状态转移概率: 知乎 PHD-Tasi 的回答
B 是观测概率矩阵, B=[bj(k)]NXM,
表明时刻 t 处于状态 qj 条件下生成的观测νk 的概率
π是初始状态向量,π=(πi), 其中,πi=P(i1=qi),i=1,2,N 表示时刻 t=1 时处于状态 qi 的概率
HMM 由初始状态概率向量π, 状态转移概率矩阵 A 和观测概率矩阵 B 决定,π和 A 决定状态序列, B 决定观测序列, 因此 HMM 用λ的三元符号表示为:λ=(A,B,π), 称为 HMM 的三要素
从定义出发, 发现 HMM 作了两个基本假设:
齐次马尔可夫假设: 隐藏的马尔可夫链在任意时刻 t 的状态只依赖于其前一时刻的状态, 与其他时刻的状态及观测无关, 也与时刻 t 无关
观测独立性假设: 假设任意时刻的观测只依赖于该时刻的马尔可夫链的状态, 与其他观测及状态无关
HMM 可用于标注, 这时状态对应着标记, 标注问题是给定观测的序列与其对应的标记序列假设标注问题的数据由 HMM 生成, 这样可用 HMM 的学习与预测算法进行标注
1.2 观测序列生成过程
算法:
1.3 HMM 的三个问题
概率计算的问题: 给定模型λ=(A,B,π)和观测序列 O=(o1,o2,,ot), 计算在模型λ下观测序列 O 出现的概率 P(O|λ)
学习问题: 已知观测序列 O=(o1,o2,,oT), 估计模型λ=(A,B,π)参数, 使得在该模型下观测序列的概率 P(O|λ)最大, 即用极大似然估计方法估计参数
预测问题: 也称解码 (decoding), 已知模型λ=(A,B,π) 和观测序列 O, 求对给定观测序列条件概率 P(I|O)最大的状态序列 I 即给定观测序列求最有可能的对应的状态序列
2 概率计算算法
计算观测序列的概率的算法
2.1 直接计算算法
给定模型λ=(A,B,π)和观测序列 O=(o1,o2,oT), 计算观测序列 O 出现的概率 P(O|λ)最直接的方法是按照概率公式直接计算通过列举所有可能的长度为 T 的状态序列 I=(i1,i2,,iT), 求各个状态序列 I 与观测序列 O 的联合概率 P(O,I|λ), 然后对所有可能的状态序列求和 (边缘概率) 得到 P(O|λ)
状态序列 I 的概率是:
对固定状态序列 I, 观测序列 O 的概率是:
O,I 同时出现的联合概率为:
然后对所有可能的状态 I 求和得到要求的概率:
但是计算量极大, 是 阶的
2.2 前向算法 forward algorithm
前向概率: 给定 HMM 模型λ, 定义到时刻 t 部分观测序列为 o1,o2,,oT 且状态为 qi 的概率为
可以递推的求前向概率及观测概率 P(O|λ)
算法:
步骤 1 中, 初始化前向概率, 是初始时刻的状态 i1=qi 和观测 o1 的联合概率;
步骤 2 中, 是前向概率的递推公式, 计算到时刻 t+1 部分观测序列为 o1,o2,,ot+1 且时刻 t+1 处于状态 qi 的前向概率;
步骤 3 中,
, 所有求和, 这里和上面直接求解的加和一个意思
2.3 后向算法
后向概率: 给定 HMM 的λ, 定义时刻 t 状态为 qi 的条件下, 从 t+1 到 T 的部分观测序列为 ot+1, ,oT, 称为
同样用递推的方法来求
算法:
因为前向算法和后向算法思路是一致的, 所以统一写成:
2.4 一些概率与期望值的计算
利用前向, 后向概率可以得到单个状态和两个状态概率的计算公式
给定模型λ和观测 O, 在时刻 t 处于状态 qi 的概率:
由前向概率可得:
于是,
给定模型λ和观测 O, 在时刻 t 处于状态 qi 且在时刻 t+1 处于状态 qj 的概率为:
由前向后向概率可得:
而
因此,
将 1,2 结合可对各个时刻 t 求和, 得到一些有用的期望值
观测 O 下状态 i 出现的期望值:;
观测 O 下状态 i 转移的期望值:;
观测 O 下状态 i 转移到 j 的期望值:
3 学习算法
根据训练数据是包括观测序列和对应状态序列还是只有观测序列分为监督学和非监督学习实现
3.1 监督学习
假设已知训练数据包含 S 个长度相同的观测序列和对应的状态序列{(O1,I1),(O2,I2),,(Os,Is)}, 那么就可以利用极大似然估计来估计 HMM 的参数具体方法如下,
转移概率 aij 的估计
设样本中时刻 t 处于状态 i, 时刻 t+1 转移到状态 j 的频数为 Aij, 那么转移状态概率估计为
观测概率 bj(k)的估计
设样本中状态为 j 并观测为 k 的频数为 Bjk, 那么状态为 j 观测为 k 的概率为估计为
初始状态概率πi 的估计πi hat 为 S 个样本中初始状态为 qi 的频率
由于监督学习的算法需要训练数据, 而人工标注的代价很大, 所以有时候需要非监督学习的方法, 如下节
3.2 非监督学习 Baum-Welch 算法
假设给定训练数据只包含 S 个, 长度为 T 的观测序列 {O1,O2,,Os} 而没对应的状态序列, 目标是学习 HMM 的λ=(A,B,π)的参数将观测序列看做测试数据 O, 状态序列数据看做不可观测的隐数据 I, 实际上 HMM 是一个含有隐变量的概率模型:
可以由 EM 算法实现
确定完全数据的对数似然函数
所有观测数据写成 O=(o1,o2,,oT), 所有隐数据写成 I=(i1,i2,,iT), 完全数据是(O,I)=(o1,o2,,oT,i1,i2,,iT), 完全数据的对数似然函数是
EM 算法的 E 步: 求 Q 函数
其中,是 HMM 当前参数的估计值,λ是要极大化的 HMM 参数
那么 Q 函数可化为:
求和是因为对所有序列总长度为 T 的训练数据上进行的
EM 算法的 M 步: 极大化 Q 函数求模型参数 A,B,π
观察 Q 函数最后的化简结果可发现, 三个参数分别单独出现在三项中, 故只需对三项分别极大化
第一项:
,πi 的约束条件是, 利用拉格朗日乘数法, 写出拉格朗日函数:
求偏导并令结果为 0, 得
==>
对 i 求和, 得到γ,
回代得到
;
第二项:
, 类似第一项约束条件, 利用拉格朗日乘数法求得:
第三项:
, 约束条件, 利用拉格朗日乘数法, 得到:
注意: 只有在 ot=νk 时, bj(ot)对 bj(k)的偏导才不为 0, 以 I(ot=νk)表示
3.3 Baum-Welch 模型参数估计公式
三个公式:
;
;;
BW 算法:
4 预测算法
这是 HMM 最后一个问题: 已知模型λ=(A,B,π)和观测序列 O, 求对给定观测序列条件概率 P(I|O)最大的状态序列 I 即给定观测序列求最有可能的对应的状态序列
4.1 近似算法
思想是: 在每个时刻 t 选择在该时刻最有可能出现的状态 it 从而得到一个状态序列
, 将它作为预测结果
给定 HMM 的λ和观测序列 O, 在此时刻 t 处于状态 qi 的概率为:
每一时刻最有可能的状态是
, 从而得到状态序列 I
近似算法的优点是计算简单, 缺点是不能保证预测的状态序列整体上是最有可能的状态序列, 因为预测的状态序列可能实际有不发生的部分此方法得到的序列有可能存在转移概率为 0 的相邻状态
4.2 维特比算法 Viterbi algorithm
实际上是运用动态规划 (dynamic programming) 求解 HMM 问题即动态规划求概率最大路径 (最优路径) 这时一条路径对应一个状态序列
什么是动态规划
根据动态规划原理, 最优路径特性: 时刻 t 通过的结点到最终结点时, 对于所有其他可能的路径来说一定是最优的, 如果不是, 那么则出现另外一条最优的, 与假设本路径最优矛盾, 因此, 我们只需, 从时刻 t=1 开始, 递推的计算在时刻 t 状态为 i 的各条部分路径的最大概率, 直到得到 t=T 状态为 i 的各条路径的最大概率时刻 t=T 的最大概率即为最优路径的概率 P, 最优路径的终结点 iT 同时得到为了找到最优路径的各个结点, 从 iT 开始, 由后向前逐步求得结点得到最优路径 I,
, 这就是 Viterbi 算法
定义在时刻 t 状态为 i 的所有单个路径 (i1,i2,,iT) 中概率最大值为:
可得变量δ的递推公式:
时刻 t 状态为 i 的所有单个路径概率最大的路径中第 t-1 个结点为:
Viterbi 算法:
来源: https://www.cnblogs.com/sxzhou/p/8535492.html