专栏首页NewBeeNLP概率图模型笔记(PART II)隐马尔科夫模型

概率图模型笔记(PART II)隐马尔科夫模型

前情提要:概率图模型笔记(PART I)

写在前面

隐马尔科夫模型(Hidden Markov Model,以下简称HMM)是比较经典的机器学习模型了,它在语音识别,自然语言处理,模式识别等领域得到广泛的应用。那么什么样的问题需要HMM模型来解决,一般有以下两个特征: (1)我们的问题是基于序列的,比如时间序列,或者状态序列; (2)我们的问题中有两类数据,一类序列数据是可以观测到的,即观测序列;而另一类数据是不能观察到的,即隐藏状态序列,简称状态序列。

HMM模型基础

首先,我们要了解下什么是马尔科夫模型。Markov Model很大,主要有四个细分领域。

这里最基础的就是Markov chain,这也是我们这篇博客的基础知识。那么什么是马尔科夫链模型呢?马尔科夫链是一种离散的随机过程,可以将其看成是一种有限自动机,但是其状态之间的转移并不是依赖于外界的输入,而是依赖于每个状态之间的转移概率。

而HMM是马尔科夫过程的一种扩展,除了一组观测序列,我们还有相对应的一组隐藏序列,还是用图来表示

对于HMM 模型,假设Q是所有可能的隐藏状态的集合,V是所有可能的观察状态的集合,

Q=\left\{q_{1}, q_{2}, \ldots, q_{N}\right\}, V=\left\{v_{1}, v_{2}, \ldots v_{M}\right\}

对于一个长度为T的序列,I对应状态序列,O对应观察序列,

I=\left\{i_{1}, i_{2}, \ldots, i_{T}\right\}, O=\left\{o_{1}, o_{2}, \ldots o_{T}\right\}

其中,任意一个隐藏状态 i 属于集合Q, 任意一个观察状态 o 属于集合V,如上图 HMM模型两个重要的假设:

  • 「齐次马尔科夫链假设」,即任意时刻的隐藏状态只依赖于它前一个隐藏状态。当然这样假设有点极端,因为很多时候我们的某一个隐藏状态不仅仅只依赖于前一个隐藏状态,可能是前两个或者是前三个。但是这样假设的好处就是模型简单,便于求解(但同时也限制了HMM模型的效果)。如果在时刻t的隐藏状态是,在时刻t+1的隐藏状态是, 则从时刻t到时刻t+1的HMM状态转移概率可以表示为:
a_{i j}=P\left(i_{t+1}=q_{j} | i_{t}=q_{i}\right)

这样可以组成马尔科夫链的状态转移矩阵A:

A=\left[a_{i j}\right]_{N \times N}
  • 「观测独立性假设」,即任意时刻的观察状态只仅仅依赖于当前时刻的隐藏状态,这也是一个为了简化模型的假设。如果在时刻t的隐藏状态是, 而对应的观察状态为, 则该时刻观察状态在隐藏状态下生成的概率为,满足:
b_{j}(k)=P\left(o_{t}=v_{k} | i_{t}=q_{j}\right)

这样可以组成观测状态生成的概率矩阵B:

B=\left[b_{j}(k)\right]_{N \times M}

除此之外,还需要一组在时刻t=1的隐藏状态概率分布Π:

\Pi=[\pi(i)]_{N}

一个HMM模型,可以由隐藏状态初始概率分布Π, 状态转移概率矩阵A和观测状态概率矩阵B决定。Π,A决定状态序列,B决定观测序列。因此,HMM模型可以由一个三元组λ表示如下:

\lambda=(A, B, \Pi)

HMM属于典型的生成式模型,即我们需要从训练数据中学到数据的分布,也就是上面介绍的HMM五要素:隐藏状态集合I,观测状态集合O, 初始隐状态概率分布Π,转移概率矩阵A以及发射概率矩阵B。

HMM观测序列的生成

那么HMM观测序列是怎么生成的呢?

输入:HMM模型参数, 观测序列的长度T; 输出:经HMM模型的观测序列 流程:

  • 根据初始状态概率分布生成隐藏状态
  • for t from 1 to T:
    • 按照隐藏状态的观测状态分布B生成观测状态;
    • 按照隐藏状态的状态转移概率分布A生成隐藏状态

所有的一起组合形成观测序列

HMM模型的三个问题

概率计算问题

即给定模型和观测序列,计算在模型λ下观测序列O出现的概率P(O|λ)。这个问题的求解需要用到前向后向算法。这个问题是HMM模型三个问题中最简单的。

  1. 直接计算法

直观地,我们只要知道模型参数,就可以按照概率公式计算出给定观测序列的出现概率。虽然这种方式理论上可行但是最后计算量太大,不过我们可以通过了解这个过程来理解HMM是怎么运行的。 首先明确问题,我们最后要求得是P(O|λ),于是可以写成下列等式:

P(O, I | \lambda)=P(I | \lambda) P(O | I, \lambda)=\pi_{i_{1}} b_{i_{1}}\left(o_{1}\right) a_{i_{1} i_{2}} b_{i_{2}}\left(o_{2}\right) \dots a_{i_{T-1}} b_{i_{T}} b_{i_{T}}\left(o_{T}\right)

其中,右侧第一项是通过转移矩阵求一个隐藏状态序列的概率公式,右侧第二项是通过发射矩阵求由隐藏序列到最后观测序列的概率,因为隐藏状态有I种,所以最后需要把所有可能情况进行加和求解。也就是

P(O | \lambda)=\sum_{I} P(O, I | \lambda)=\sum_{i_{1}, i_{2}, \ldots i_{T}} \pi_{i_{1}} b_{i_{1}}\left(o_{1}\right) a_{i_{1} i_{2}} b_{i_{2}}\left(o_{2}\right) \dots a_{i_{T-1}} i_{T} b_{i T}\left(o_{T}\right)

但是利用上述过程求解计算量非常大,是阶的,这种算法不可行。

  1. 前向算法

首先定义前项概率 α:给定HMM模型λ,定义到时刻t时部分观测序列为O1,O2,,,Ot,且隐藏状态为,即

\alpha_{t}(i)=P\left(o_{1}, o_{2}, \cdots, o_{t}, i_{t}=q_{i} | \lambda\right)

前向算法流程:输入:HMM模型和观测序列; 输出:观测序列概率λ

上面的公式可能不太好理解,结合下面的图:

解释一下算法流程中递推的那一部分,可以理解为在k时刻隐藏状态为到中的任意一个,可以根据转移矩阵将它们在k时刻无论是哪一种状态都可以计算出在k+1时刻状态为的概率,也就是,得到这个概率之后自然就可以根据发射概率来求出k+1时刻的观测状态。前向算法的复杂度为.

模型参数学习问题

即给定观测序列,估计模型的参数,使该模型下观测序列的条件概率P(O|λ)最大。这个问题的求解需要用到基于EM算法的「鲍姆-韦尔奇算法」。这个问题是HMM模型三个问题中最复杂的。

根据训练数据是包括观测序列和对应的隐藏序列还是只有观测序列可以分为有监督学习和非监督学习。

  1. 有监督学习

给定数据集,其实就是根据三元组参数的定义去数词的频数。。。

  • 转移概率
\hat{a}_{i j}=\frac{A_{y}}{\sum_{j=1}^{N} A_{i j}}, \quad i=1,2, \cdots, N ; j=1,2, \cdots, N
  • 观测概率
\hat{b}_{j}(k)=\frac{B_{j k}}{\sum_{k=1}^{M} B_{j k}}, \quad j=1,2, \cdots, N_{i}=1,2, \cdots, M
  • 初始状态概率
\Pi=\pi(i)=\frac{C(i)}{\sum_{s=1}^{N} C(s)}
  1. 非监督学习

可见有监督学习情况求解模型的参数还是比较直观简单的,但是在很多时候,我们无法得到观测序列对应的隐藏状态序列,此时求解HMM模型的参数就会复杂一些,就会用到「Baum-Welch算法」,其实也就EM算法,只不过那个时代EM算法还没有提出概念。

我们的训练数据为,对于任意一个样本d,观测序列,其对应的未知的隐藏状态序列为:

  • Baum-Welch算法第一步(EM算法的E步):求Q函数
Q(\lambda, \overline{\lambda})=\sum_{I} P(I | O, \overline{\lambda}) \log P(O, I | \lambda)

其中表示HMM模型参数的当前估计值.

在M步我们要极大化上式。由于,而分母是常数,因此我们要极大化的式子等价于:

\overline{\lambda}=\arg \max _{\lambda} \sum_{I} P(O, I | \overline{\lambda}) \log P(O, I | \lambda)

我们又有联合分布:

P(O,I|\lambda) = \prod_{d=1}^D\pi_{i_1^{(d)}}b_{i_1^{(d)}}(o_1^{(d)})a_{i_1^{(d)}i_2^{(d)}}b_{i_2^{(d)}}(o_2^{(d)})...a_{i_{T-1}^{(d)}i_T^{(d)}}b_{i_T^{(d)}}(o_T^{(d)})

将其代入上述需要极大化的式子:

\overline{\lambda}=\arg \max _{\lambda} \sum_{d=1}^{D} \sum_{I} P(O, I | \overline{\lambda})\left(\log \pi_{i_{1}}+\sum_{t=1}^{T-1} \log a_{i, i_{t+1}}+\sum_{t=1}^{T} b_{i_{t}}\left(o_{t}\right)\right)
  • Baum-Welch算法第二步(EM算法的M步)

极大化Q函数,求模型参数A, B, PAI。这里我们以对模型参数PAI求导为例,由于PAI只在上式括号里的第一项出现,因此对PAI的极大化式子为,

\overline{\pi_{i}}=\arg \max _{\pi_{i_{1}}} \sum_{I} P(O, I | \overline{\lambda}) \log \pi_{i_{1}}=\arg \max _{\pi_{i}} \sum_{d=1}^{D} \sum_{i=1}^{N} P\left(O, i_{1}^{(d)}=i | \overline{\lambda}\right) \log \pi_{i}

同时注意到还满足条件, 因此根据拉格朗日乘子法,可以写出关于的拉格朗日函数为:

\arg \max _{\pi_{i}} \sum_{d=1}^{D} \sum_{i=1}^{N} P\left(O, i_{1}^{(d)}=i | \overline{\lambda}\right) \log \pi_{i}+\gamma\left(\sum_{i=1}^{N} \pi_{i}-1\right)

求导得到:

\sum_{d=1}^{D} P\left(O, i_{1}^{(d)}=i | \overline{\lambda}\right)+\gamma \pi_{i}=0

令i分别从1到N,上式可以得到N个式子,然后把这N个式子相加和得到:

\sum_{d=1}^{D} P(O | \overline{\lambda})+\gamma=0

这样我们就得到了的表达式

\pi_i =\frac{\sum\limits_{d=1}^DP(O,i_1^{(d)} =i|\overline{\lambda})}{\sum\limits_{d=1}^DP(O|\overline{\lambda})} = \frac{\sum\limits_{d=1}^DP(O,i_1^{(d)} =i|\overline{\lambda})}{DP(O|\overline{\lambda})} = \frac{\sum\limits_{d=1}^DP(i_1^{(d)} =i|O, \overline{\lambda})}{D} = \frac{\sum\limits_{d=1}^DP(i_1^{(d)} =i|O^{(d)}, \overline{\lambda})}{D}

对模型参数A和B也是同样的思路求解。

Baum-Welch算法流程: 输入:D个观测序列样本 输出:HMM模型参数 流程: 1.随机初始化所有的参数 2.对于每个样本, 用前向后向算法计算 3.更新模型参数:

\pi_{i}=\frac{\sum_{d=1}^{D} \gamma_{1}^{(d)}(i)}{D}
a_{i j}=\frac{\sum_{d=1}^{D} \sum_{t=1}^{T-1} \xi_{t}^{(d)}(i, j)}{\sum_{d=1}^{D} \sum_{t=1}^{T-1} \gamma_{t}^{(d)}(i)}
b_{j}(k)=\frac{\sum_{d=1}^{D} \sum_{t=1, o_{l}^{(i)}=v_{k}}^{T} \gamma_{t}^{(d)}(j)}{\sum_{d=1}^{D} \sum_{t=1}^{T} \gamma_{t}^{(d)}(j)}

4.如果参数值已经收敛,则算法迭代结束,否则继续从第二步开始迭代

预测问题,也称为解码问题

即给定模型和观测序列,求给定观测序列条件下,最可能出现的对应的状态序列,这个问题的求解需要用到基于动态规划的维特比算法。这个问题是HMM模型三个问题中复杂度居中的算法。

「维特比算法概述」

需要注意的是维特比算法并不是HMM所独有的,它是一种通用的解码算法,是基于动态规划的来求序列最短路径的方法。

首先定义两个变量

  • 第一个是在时刻t隐藏状态为i所有可能的状态转移路径中的概率最大值,记为
\delta_{t}(i)=\max _{i_{1}, i_{2}, \ldots i_{t-1}} P\left(i_{t}=i, i_{1}, i_{2}, \ldots i_{t-1}, o_{t}, o_{t-1}, \ldots o_{1} | \lambda\right), i=1,2, \ldots N

由的定义可以得到的递推表达式:

\begin{aligned} \delta_{t+1}(i) &=\max _{i_{1}, i_{2}, \ldots . i_{t}} P\left(i_{t+1}=i, i_{1}, i_{2}, \ldots i_{t}, o_{t+1}, o_{t}, \ldots o_{1} | \lambda\right) \\ &=\max _{1 \leq j \leq N}\left[\delta_{t}(j) a_{j i}\right] b_{i}\left(o_{t+1}\right) \end{aligned}
  • 第二个变量是由第一个局部状态递推得到。我们定义在时刻t隐藏状态为i的所有单个状态转移路径中概率最大的转移路径中的第t-1个节点的隐藏状态为,其递推表达式为:
\Psi_{t}(i)=\arg \max _{1 \leq j \leq N}\left[\delta_{t-1}(j) a_{j i}\right]

有了这两个局部状态,我们就可以从时刻0一直递推到时刻T,然后利用记录的前一个最可能的状态节点回溯,直到找到最优的隐藏状态序列。

「维特比算法流程」

输入:HMM模型蚕食,观测序列 输出:最有可能的隐藏状态序列 流程: 1)初始化局部状态:

\delta_{1}(i)=\pi_{i} b_{i}\left(o_{1}\right), i=1,2 \ldots N
\Psi_{1}(i)=0, i=1,2 \ldots N

2)进行动态规划递推时刻t的局部状态:

\delta_{t}(i)=\max _{1 \leq j \leq N}\left[\delta_{t-1}(j) a_{j i}\right] b_{i}\left(0_{t}\right), i=1,2 \ldots N
\Psi_{t}(i)=\arg \max _{1 \leq j \leq N}\left[\delta_{t-1}(j) a_{j i}\right], i=1,2 \ldots N

3)计算时刻T最大的,即为最有可能的隐藏状态序列的概率。计算时刻T最大的,即为时刻T最有可能的隐藏状态

P *=\max _{1 \leq j \leq N} \delta_{T}(i)
i_{T}^{*}=\arg \max _{1 \leq j \leq N}\left[\delta_{T}(i)\right]

4)利用局部状态开始回溯,得到每个时刻的最优状态

i_{t}^{*}=\Psi_{t+1}\left(i_{t+1}^{*}\right)

最终得到最优路径,即最有可能的隐藏状态序列

- END -

本文分享自微信公众号 - NewBeeNLP(NewBeeNLP),作者:kaiyuan

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 详解ERNIE-Baidu进化史及应用场景

    ERNIE: Enhanced Representation through Knowledge Integration[1] 是百度在2019年4月的时候,基...

    kaiyuan
  • 实战必备!文本分类中的一些经验和 tricks

    最近在总结之前做的文本分类实验的一些经验和 tricks,同时也参考了网上的一些相关资料(见文末),其中有些 tricks 没尝试过,先在这里记下,或者日后能用...

    kaiyuan
  • Python中那些低调有趣的模块

    python语言上位成功的其中一个原因是其丰富的社区支持,不管你有什么奇奇怪怪的需求,大概率能在网上搜到一个库来便捷实现。这篇文章就列举了几个低调的python...

    kaiyuan
  • 医生必备技能,万字长文让你明白临床模型研究应该如何做

    对于大部分临床医生来说,往往是没有能力去做基础科研的,因为没有时间、经费和实验室。但是每家单位对文章的要求又是这么强硬,没有文章就无法进职称,该怎么办?

    用户6317549
  • 我眼中的模型评估

    逻辑回归模型的几个衡量指标如洛伦兹曲线、ROC曲线、lift曲线等皆来源于混淆矩阵,如果针对同一个问题构建不同的模型,当进行模型间效果比较时,经常会用到...

    许卉
  • 【时序预测】时间序列分析——时间序列的平稳化

    将非平稳时间序列转化成平稳时间序列,包含三种类型:结构变化、差分平稳、确定性去趋势。本文脉络框架如下:

    roganhuang
  • 学界 | 谷歌团队提出应用于噪声语音识别的在线序列到序列模型

    近日谷歌团队发布了一篇关于语音识别的在线序列到序列模型,该模型可以实现在线实时的语音识别功能,并且对来自不同扬声器的声音具有识别功能。 以下内容是 AI 科技评...

    AI科技评论
  • CVPR2018 | 直接建模视觉智能体?让「小狗」动起来~

    选自arXiv 作者:Kiana Ehsani 等 机器之心编译 参与:Pedro、路 近日,来自华盛顿大学和艾伦人工智能研究所的研究者在 arXiv 上发布论...

    机器之心
  • 解读:一种基于机器学习的数据驱动股票价格预测系统(附系统代码链接)

    “ 下面这篇文章的内容主要是来自论文《A novel data-driven stock price trend prediction system》,其提出了...

    量化小白
  • TCGA的数据还能这么挖!还发了9+分!

    今天和大家分享的是2020年3月发表在CANCER RESEARCH (IF=9.727) 的一篇文章"Computational staining of pa...

    科研菌

扫码关注云+社区

领取腾讯云代金券