专栏首页爬蜥的学习之旅HMM(隐马尔科夫模型)与维特比算法

HMM(隐马尔科夫模型)与维特比算法

马尔科夫假设:假设模型的当前状态仅仅依赖于前面的几个状态,这被称为马尔科夫假设

真实情况当前的状态可能会和前面的状态没有关系,或者有更多的可能性。

比如:预测天气,马尔科夫假设假定今天的天气只能通过过去几天已知的天气情况进行预测——而对于其他因素,譬如风力、气压等则没有考虑。

n阶马尔科夫模型

一个马尔科夫过程是状态间的转移仅依赖于前n个状态的过程。这个过程被称之为n阶马尔科夫模型,其中n是影响下一个状态选择的(前)n个状态

最简单的马尔科夫过程是一阶模型,它的状态选择仅与前一个状态有关。

状态转移概率

从一个状态转移到另一个状态的概率

状态转移矩阵

有M个状态的一阶马尔科夫模型,共有M^2个状态转移,因为任何一个状态都有可能是所有状态的下一个转移状态.所有的M^2个概率可以用一个状态转移矩阵表示

这些概率并不随时间变化而不同——这是一个非常重要(但常常不符合实际)的假设。

也就是说,如果昨天是晴天,那么今天是晴天的概率为0.5,是多云的概率为0.375。注意,每一行的概率之和为1。

一阶马尔科夫过程示例

要初始化这样一个系统,我们需要确定起始日天气的(或可能的)情况,定义其为一个初始概率向量,称为pi向量。

第一天为晴天的概率为1

我们定义一个一阶马尔科夫过程如下:   

  • 状态:三个状态——晴天,多云,雨天。   
  • pi向量:定义系统初始化时每一个状态的概率。   
  • 状态转移矩阵:给定前一天天气情况下的当前天气概率。

任何一个可以用这种方式描述的系统都是一个马尔科夫过程

马尔科夫过程的局限性

无法直接获取要测试的状态的变迁,但是存在一个可以观察的东西,它能够反映要测试的东西的状态变迁,这里要测试的状态变迁为隐藏状态,能够观察的为观察的状态

一个隐士也许不能够直接获取到天气的观察情况,但是他有一些水藻。民间传说告诉我们水藻的状态与天气状态有一定的概率关系——天气和水藻的状态是紧密相关的。希望为隐士设计一种算法,在不能够直接观察天气的情况下,通过水藻和马尔科夫假设来预测天气。

观察到的状态序列与隐藏过程有一定的概率关系。我们使用隐马尔科夫模型对这样的过程建模,这个模型包含了一个底层隐藏的随时间改变的马尔科夫过程,以及一个与隐藏状态某种程度相关的可观察到的状态集合。

隐藏状态和观察状态的关系

隐藏状态(实际的天气)由一个简单的一阶马尔科夫过程描述

隐藏状态和观察状态之间的连接表示:在给定的马尔科夫过程中,一个特定的隐藏状态生成特定的观察状态的概率,有

Sum_{Obs=Dry,Dryish,Damp,Soggy}(Obs|Sun) = 1;
Sum_{Obs=Dry,Dryish,Damp,Soggy}(Obs|Cloud) = 1;
Sum_{Obs=Dry,Dryish,Damp,Soggy}(Obs|Rain) = 1;
复制代码

混淆矩阵

包含了给定一个隐藏状态后得到的观察状态的概率

假设是晴天,那么海藻是 干 稍干 潮湿 湿润 的概率分别为 0.6 0.2 0.15 0.05 他们的和为1

隐马尔科夫模型(Hidden Markov Models)

一个隐马尔科夫模型是在一个标准的马尔科夫过程中引入一组观察状态,以及其与隐藏状态间的一些概率关系。

这个模型包含两组状态集合和三组概率集合:  

  • 隐藏状态:一个系统的(真实)状态,可以由一个马尔科夫过程进行描述(例如,天气)。  
  • 观察状态:在这个过程中‘可视’的状态(例如,海藻的湿度)。  
  • pi向量:包含了(隐)模型在时间t=1时一个特殊的隐藏状态的概率(初始概率) 
  • 状态转移矩阵:包含了一个隐藏状态到另一个隐藏状态的概率  
  • 混淆矩阵:包含了给定隐马尔科夫模型的某一个特殊的隐藏状态,观察到的某个观察状态的概率。

观察状态的数目可以和隐藏状态的数码不同。

HMM定义

一个隐马尔科夫模型是一个三元组(pi, A, B)

在状态转移矩阵及混淆矩阵中的每一个概率都是时间无关的——也就是说,当系统演化时这些矩阵并不随时间改变

这是马尔科夫模型关于真实世界最不现实的一个假设。

应用

  1. 模式识别:
    • 给定HMM求一个观察序列的概率(评估)
    • 搜索最有可能生成一个观察序列的隐藏状态序列(解码)
  2. 给定观察序列生成一个HMM(学习)

评估

有一些描述不同系统的隐马尔科夫模型(也就是一些( pi,A,B)三元组的集合)及一个观察序列。我们想知道哪一个HMM最有可能产生了这个给定的观察序列。

对于海藻来说,我们也许会有一个“夏季”模型和一个“冬季”模型,因为不同季节之间的情况是不同的——我们也许想根据海藻湿度的观察序列来确定当前的季节。

使用前向算法(forward algorithm)来计算给定隐马尔科夫模型(HMM)后的一个观察序列的概率,并因此选择最合适的隐马尔科夫模型(HMM)。

解码

在许多情况下我们对于模型中的隐藏状态更感兴趣,因为它们代表了一些更有价值的东西,而这些东西通常不能直接观察到。

一个盲人隐士只能感觉到海藻的状态,但是他更想知道天气的情况,天气状态在这里就是隐藏状态。

使用Viterbi 算法(Viterbi algorithm)确定(搜索)已知观察序列及HMM下最可能的隐藏状态序列。

学习

根据一个观察序列(来自于已知的集合),以及与其有关的一个隐藏状态集,估计一个最合适的隐马尔科夫模型(HMM),也就是确定对已知序列描述的最合适的(pi,A,B)三元组。

当矩阵A和B不能够直接被(估计)测量时,前向-后向算法(forward-backward algorithm)被用来进行学习(参数估计)

前向算法

  1. 穷举搜索 我们有一个用来描述天气及与它密切相关的海藻湿度状态的隐马尔科夫模型(HMM),另外我们还有一个海藻的湿度状态观察序列。假设连续3天海藻湿度的观察结果是(干燥、湿润、湿透)——而这三天每一天都可能是晴天、多云或下雨。

每一列都显示了可能的的天气状态,并且每一列中的每个状态都与相邻列中的每一个状态相连。而其状态间的转移都由状态转移矩阵提供一个概率。 在每一列下面都是某个时间点上的观察状态,给定任一个隐藏状态所得到的观察状态的概率由混淆矩阵提供。 现在要计算当前HMM能够得到观察序列是 dry,damp,soggy 的概率。 找到每一个可能的隐藏状态,并且将这些隐藏状态下的观察序列概率相加,也就是穷举所有的隐藏概率发生的情况下,是现有观察状态的概率 Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy) 复制代码 用到的是当前的HMM 缺点:计算观察序列概率极为昂贵,特别对于大的模型或较长的序列 应用:利用概率的时间不变性来减少问题的复杂度。

  1. 递归降低问题复杂度【动态规划思想】 计算过程中将计算到达网格中某个中间状态的概率作为所有到达这个状态的可能路径的概率求和问题。

同样对于穷举的计算方法,可以拆分成多个从当前状态转移到下一个局部状态,再把所有的局部状态求和就得到定隐马尔科夫模型(HMM)后的观察序列概率。概率为 αt ( j )= Pr( 观察状态 | 隐藏状态j ) x Pr(t时刻所有指向j状态的路径) 复制代码 j 表示局部状态;αt ( j )表示处于这个状态的概率;t表示时间;Pr( 观察状态 | 隐藏状态j )即混淆矩阵;Pr(t时刻所有指向j状态的路径)即状态转移矩阵

要计算t=2时,局部状态为b的概率,必须要计算所有 t=1时刻,从a,b,c到t=2时状态为b的概率,而要得到t=1时刻的所有概率,已经在前一步从t=0运转到t=1的时候计算过了。 也就是说 t=2时,观察序列前提下,局部隐藏状态为b的概率为t=1状态所有的概率和再乘以混淆矩阵转移到当前观察变量的概率。即

维特比算法(Viterbi Algorithm)

 对于一个特殊的隐马尔科夫模型(HMM)及一个相应的观察序列,我们常常希望能找到生成此序列最可能的隐藏状态序列

  1. 穷举搜索

对于网格中所显示的观察序列,最可能的隐藏状态序列是下面这些概率中最大概率所对应的那个隐藏状态序列: Pr(dry,damp,soggy | sunny,sunny,sunny), Pr(dry,damp,soggy | sunny,sunny,cloudy), Pr(dry,damp,soggy | sunny,sunny,rainy), . . . . Pr(dry,damp,soggy | rainy,rainy,rainy) 复制代码 但是太昂贵了

  1. 递归降低复杂度 定义局部概率,它是到达网格中的某个特殊的中间状态时的概率  

对于网格中的每一个中间及终止状态,都有一个到达该状态的最可能路径。称这些路径局部最佳路径(partial best paths)。其中每个局部最佳路径都有一个相关联的概率,即局部概率或 与前向算法中的局部概率不同,是到达该状态(最可能)的一条路径的概率。 因而(i,t)是t时刻到达状态i的所有序列概率中最大的概率, 特别地,在t=T时每一个状态都有一个局部概率和一个局部最佳路径。这样我们就可以通过选择此时刻包含最大局部概率的状态及其相应的局部最佳路径来确定全局最佳路径(最佳隐藏状态序列)。

反向指针

目标是在给定一个观察序列的情况下寻找网格中最可能的隐藏状态序列——因此,我们需要一些方法来记住网格中的局部最佳路径。

计算t时刻的's我们仅仅需要知道t-1时刻的's。在这个局部概率计算之后,就有可能记录前一时刻哪个状态生成了(i,t)——也就是说,在t-1时刻系统必须处于某个状态,该状态导致了系统在t时刻到达状态i是最优的。这种记录(记忆)是通过对每一个状态赋予一个反向指针完成的,这个指针指向最优的引发当前状态的前一时刻的某个状态。

其中argmax运算符是用来计算使括号中表达式的值最大的索引j的。

维特比算法的优点

  1. 通过使用递归减少计算复杂度——这一点和前向算法使用递归减少计算复杂度是完全类似的。
  2. 维特比算法有一个非常有用的性质,就是对于观察序列的整个上下文进行了最好的解释(考虑)。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链路层是做什么的?

    最大传输单元。链路层[以太网(1500字节)和802.3(1492字节)]对数据帧的长度存在限制。

    爬蜥
  • Java中常见死锁与活锁的实例

    可以看到bThread持有锁0x00000007aaee5758,同时等待0x00000007aaee5748,然而恰好aThread持有锁0x00000007...

    爬蜥
  • 从源码看redis的sorted set与skipList详解

    其中0表示它是当前排序集合里面分数最小的。 在redis的底层实现中,就用到了skiplist作为实现排序集合的数据结构

    爬蜥
  • 隐马尔可夫模型攻略

    隐马尔可夫模型 (Hidden Markov Model,HMM) 最初由 L. E. Baum 和其它一些学者发表在一系列的统计学论文中,随后在语言识别,自然...

    机器学习AI算法工程
  • 【机器学习研究】隐马尔可夫模型 (HMM) 最认真研究

    隐马尔可夫模型 (Hidden Markov Model,HMM) 最初由 L. E. Baum 和其它一些学者发表在一系列的统计学论文中,随后在语言识别,自然...

    量化投资与机器学习微信公众号
  • python 伯努利分布详解

    伯努利分布 是一种离散分布,有两种可能的结果。1表示成功,出现的概率为p(其中0<p<1)。0表示失败,出现的概率为q=1-p。这种分布在人工智能里很有用,比如...

    砸漏
  • 动手学深度学习(七) 梯度下降

    致Great
  • 利用C#迭代器的一个杨辉三角示例

    身边有个朋友在跟着廖雪峰的教程学习python,途中遇到了“在Python中使用迭代器打印杨辉三角”的问题,我在帮忙解决的同时顺手写了个简单的C#版本以供补充。...

    潘成涛
  • C++ 条件变量(condition_variable)

           先贴一个condition_variable的讲解:https://en.cppreference.com/w/cpp/thread/condit...

    Ch_Zaqdt
  • Spring Boot+Gradle+ MyBatisPlus3.x搭建企业级的后台分离框架

    阿里JSON解析器,详细文档请看官方 https://github.com/alibaba/fastjson

    全栈自学社区

扫码关注云+社区

领取腾讯云代金券