【机器学习】隐马尔可夫模型(HMM)

2020/06/14 16:46
阅读数 117

1.部分参考内容

2.引言

Alice和Bob住的很远,只能通过电话交流。
在这里插入图片描述
Bob的心情会随天气的好坏而变化,天气sunny的时候,他就happy,天气rainy的说话,他就grumpy。Bob通过电话告诉Alice他很happy,Alice就可以推测Bob那的天气是sunny,反之,也可以推测出rainy。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
那么,如果问题再稍微复杂一点呢。
假如Bob的心情在sunny的时候并不总是happy,也有可能是grumpy,而天气是rainy的时候,Bob的心情也可能是happy。那么即便Alice知道了Bob的心情,她也不能确定Bob所在地的天气到底怎样。






假设Alice已经计算出sunny的时候Bob心情为happy的概率和grumy的概率,还有rainy时候happy和grumpy的概率。那么,Alice虽然不像之前那样可以百分百确定天气,但是还是可以有较大概率推测出天气的。
在这里插入图片描述
现在假如Bob连续三天告诉了Alice自己的心情,Alice就可以猜测出这三天的天气,比如下图这样:
在这里插入图片描述
如果Bob连续一星期每天向Alice汇报自己的心情,像下面这样:
在这里插入图片描述
这样Alice根据上面的概率只能推测出天气可能是:sunny,rainy,sunny,rainy,sunny,rainy。这样的天气似乎很不正常,一天晴一天雨,实际生活中前一天晴,后一天晴的概率应该更大一些。
所以,我们假设已知更多的概率,两个天气之间的相互转化的概率也知道。如下图:
在这里插入图片描述







现在,我们就有了一个隐马尔可夫模型,它包含两种观测(Alice可以知道的Bob的心情),两种状态(Bob所在地的天气),以及一些概率。

在这里插入图片描述

有了上面的这些概率,当Bob再向Alice说出连续几天的心情后,Alice可以通过一定的公式计算出这几天的天气是怎样的。

其中,Bob通过电话告诉Alice自己一段时间内的心情,即为可见状态连,而Bob所在地的天气就是隐藏状态链马尔科夫链通常就是指的隐藏状态链。

3.隐马尔可夫模型

之前讲过贝叶斯网络,其实隐马尔可夫也可以视为特殊的贝叶斯网络。

下面两个基本问题各有一道例题,把他们弄明白,有助于更好地理解HMM

3.1 马尔可夫过程

马尔可夫过程(Markov process)是一类随机过程。它的原始模型马尔可夫链,由俄国数学家A.A.马尔可夫于1907年提出。该过程具有如下特性:在已知目前状态(现在)的条件下,它未来的演变(将来)不依赖于它以往的演变 (过去 )。例如森林中动物头数的变化构成——马尔可夫过程。在现实世界中,有很多过程都是马尔可夫过程,如液体中微粒所作的布朗运动、传染病受感染的人数、车站的候车人数等,都可视为马尔可夫过程。

每个状态的转移只依赖于之前的n个状态,这个过程被称为1个n阶的模型,其中n是影响转移状态的数目。最简单的马尔可夫过程就是一阶过程, 每一个状态的转移只依赖于其之前的那一个状态 ,这个也叫作 马尔可夫性质 。用数学表达式表示就是下面的样子:

假设这个模型的每个状态都只依赖于之前的状态,这个假设被称为 马尔科夫假设 ,这个假设可以大大的简化这个问题。显然,这个假设可能是一个非常糟糕的假设,导致很多重要的信息都丢失了。

P ( X n + 1 ∣ X 1 = x 1 , X 2 = x 2 , . . . , X n = x n ) = P ( X n + 1 = x ∣ X n = x n ) ) P(X_{n+1} |X_1 =x_1, X_2=x_2,...,X_n=x_n) =P(X_{n+1}=x|X_n=x_n)) P(Xn+1X1=x1,X2=x2,...,Xn=xn)=P(Xn+1=xXn=xn))

引言中的天气的例子就是一个马尔可夫过程,
在这里插入图片描述
也就是说:

  • 如果今天是晴天,明天还是晴天的概率是0.8,明天下雨的概率是0.2
  • 加入今天下雨,明天还下雨的概率是0.6,明天是晴天的概率是0.4

概率转移对应的表如下:

晴天 雨天
晴天 0.8 0.2
雨天 0.4 0.6

状态转移矩阵就是:
A = ( 0.8 0.2 0.4 0.6 ) A=\begin{pmatrix} 0.8 & 0.2 \\ 0.4 & 0.6 \end{pmatrix} A=(0.80.40.20.6)

一阶马尔可夫过程定义了下面三个部分:

  • 状态:晴天和雨天
  • 初始向量:定义系统在时间为0时候的状态的概率
  • 状态转移矩阵:每种天气转换的概率

3.2 隐马尔可夫模型

Alice在不知道Bob心情的情况下,是不可能知道Bob所在地的天气的。但是如果知道了Bob的心情,进行推理之后,是可以推出天气的概率的。

这种方法就是隐马尔可夫模型

隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型,用来描述一个含有隐含未知参数的马尔可夫过程。 它是结构最简单的动态贝叶斯网络,这是一种著名的有向图模型 ,主要用于时序数据建模,在语音识别、自然语言处理等领域有广泛应用。

具体的推理过程先不说,先说一下隐马尔可夫模型的三个问题:

  • 评估问题:Bob告诉Alice连续几天的心情,Alice推测出现这个心情序列的概率是多少。
  • 解码问题:Bob告诉Alice连续几天的心情,Alice推测这几天Bob所在地的天气。
  • 学习问题:调整模型的参数,使得观测序列在给定模型条件下出现的概率最大。(最难的问题)

三大问题的解法分别是:

  • 前向算法(Forward Algorithm)、后向算法(Backward Algorithm)
  • 维特比算法(Viterbi Algorithm)
  • 鲍姆-韦尔奇算法(Baum-Welch Algorithm) (约等于EM算法)

例子:
小明现在有三天的假期,他为了打发时间,可以在每一天中选择三件事情来做,这三件事情分别是散步、购物、打扫卫生( 对应着可观测序列 ),可是在生活中我们所做的决定一般都受到天气的影响,可能晴天的时候想要去购物或者散步,可能下雨天的时候不想出门,留在家里打扫卫生。而天气(晴天、下雨天)就属于隐藏状态
那么,我们提出三个问题,分别对应马尔可夫的三大问题:

  • 已知整个模型,我观测到连续三天做的事情是:散步,购物,收拾。那么,根据模型,计算产生这些行为的概率是多少。
  • 同样知晓这个模型,同样是这三件事,我想猜,这三天的天气是怎么样的。
  • 最复杂的,我只知道这三天做了这三件事儿,而其他什么信息都没有。我得建立一个模型,晴雨转换概率,第一天天气情况的概率分布,根据天气情况选择做某事的概率分布。

现在大家应该明白隐马尔可夫模型大概是什么和要解决什么问题了。

3.3 HMM模型的五元组

一个隐马尔可夫模型有五个部分组成:

  • 要素N:状态集合S={S1,S2,…,SN},模型中状态的个数。(Bob所在地天气的种类)
  • 要素M:表示每个状态可以观察到的不同符号数。(一周天气下Bob的心情种类),一般用V={V1,V2,…,VM}表示。
  • 状态转移矩阵A={aij}:其中aij=P[qt+1=Sj | qt=Si]
  • 状态 S j S_j Sj中可见符号的概率分布B={bj(k)}:其中bj(k)=P[在t时刻出现符号Vk|qt=sj]
  • 初始状态分布π={πj}:其中πj=p[q0=sj],j=1,2,…,N

4.评估问题

定义:已知观测序列 O = o 1 , o 2 , . . . , o T O={o_1, o_2,..., o_T } O=o1,o2,...,oT,和模型λ=(π, A, B),如何计算给定模型的情况下,产生观测序列O的概率。

在这里插入图片描述
先看一个定义
路径:隐马尔可夫模型 P ( O ∣ λ ) P(O|λ) P(Oλ)中从初始状态到终止状态的一个依次到达的状态序列,成为一个路径。也就是马尔科夫链。

4.1 直接方法

直接方法:列举出长度为T的所有可能的状态序列,考察一个固定状态序列 Q = q 1 , q 2 , . . . , q T Q=q_1,q_2,...,q_T Q=q1,q2,...,qT,对于Q,并假设观察序列是统计独立的,则有观察序列的概率为:
在这里插入图片描述
状态序列Q出现的概率为:
在这里插入图片描述
O与Q的联合概率分布为:在这里插入图片描述
很明显的一个问题是:上式的计算复杂度为2T*NT。(2T-1次乘法运算,每次NT个序列)




显然,复杂度太高,需要更好的算法。

4.2前向算法

直接算法在计算过程中,有一些结果是重复计算了的,所以计算起来,复杂度很高,如果把之前计算的保存起来,之后需要用到时直接拿来用,虽然占用了一些内存,但是却可以降低时间复杂度。

在这里插入图片描述
用图表示就是:
在这里插入图片描述
复杂度为: N2*T


例题:
在这里插入图片描述
在这里插入图片描述

4.3后向算法

跟前向算法相反,我们知道总的概率肯定是1,那么B_t=1,也就是最后一个时刻的概率合为1,先计算前三天的各种可能的概率,在计算前两天、前一天的数据,跟前向算法相反的计算路径。
在这里插入图片描述
在这里插入图片描述

4.4前向后向算法

在这里插入图片描述

5.解码问题

已知模型λ和观察序列O,如何确定每一个Ot是哪一个状态Si产生的。
图来自:HMM 解码问题
在这里插入图片描述
HMM的解码可以用维特比解码,核心思想是在前向后向算法的基础上保留最优节点,并通过回溯找到最优路径。
在这里插入图片描述



例子:(来源于隐马尔科夫模型HMM(四)维特比算法解码隐藏状态序列)
问题为: 
假设我们有3个盒子,每个盒子里都有红色和白色两种球,这三个盒子里球的数量分别是:
在这里插入图片描述
按照下面的方法从盒子里抽球,开始的时候,从第一个盒子抽球的概率是0.2,从第二个盒子抽球的概率是0.4,从第三个盒子抽球的概率是0.4。以这个概率抽一次球后,将球放回。然后从当前盒子转移到下一个盒子进行抽球。规则是:如果当前抽球的盒子是第一个盒子,则以0.5的概率仍然留在第一个盒子继续抽球,以0.2的概率去第二个盒子抽球,以0.3的概率去第三个盒子抽球。如果当前抽球的盒子是第二个盒子,则以0.5的概率仍然留在第二个盒子继续抽球,以0.3的概率去第一个盒子抽球,以0.2的概率去第三个盒子抽球。如果当前抽球的盒子是第三个盒子,则以0.5的概率仍然留在第三个盒子继续抽球,以0.2的概率去第一个盒子抽球,以0.3的概率去第二个盒子抽球。



在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

6.学习问题

这个比较复杂,待更。

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部