隐马尔可夫模型(HMM)来龙去脉(二) 单智能体、多智能体强化学习基本概念及算法分类?为啥提出多智能体强化学习,现状? 张量网络算法基础(八、张量网络机器学习【上】) MapReduce 简介 Python爬虫入门教程 81-100 小众爬虫框架looter,框架作者竟然在官方手册开车 机器人二维导航教程汇总 mapper 使用示例 Redis的概念及关系型与非关系型数据库对比 MySQL必知必会:使用WHERE、正则表达式、通配符过滤数据 Solr的增量更新和全量更新对比 MYSQL数据库维护 MATLAB与Mysql数据库连接并数据交换(基于ODBC) 数据库:PostgreSQL:基础功能使用介绍 MYSQL 5.7 高级SQL语句(3)——数据库函数和存储过程 mysql导出数据到表格讲解大全(导出数据带表头,导出数据中文乱码问题解决) SpringBoot升级/指定jackson版本 JAVA - EnumMap与EnumSet简单总结 js获取主机mac等信息【亲测有效】-- 附执行结果&代码 [记录六] Vue(全家桶)+node+koa2+mysql+nginx+redis,博客全栈项目之node后台连接mysql和redis,登陆接口的编写 C# 读取XML配置文件 MongoDB数据库设置密码 Redis之重设密码及开启远程访问 本地Navicat连接阿里云MySQL数据库注意要点 PHP Windows系统实现定时任务的两种方式bat版 面试官让我手写promise,我这样写,他很满意 超级码力在线编程大赛初赛 第二场 UML类图的依赖和关联详解(含代码) 【C语言】新手实现简单的石头剪刀布人机对战 Codeforces Round #666 (Div. 2)题解ABC Codeforces Round #666 (Div. 2)E Monster Invaders 华为今年不会推出运行鸿蒙OS的手机;Deno 1.3.2发布|极客头条 异或在笔试题中的超神表现 超级码力在线编程大赛初赛 第2场 T1-T4题解 1397D. Stoned Game(博弈) Codeforces Round #666(Div.2)A~D题题解 高性能微服务架构技术选型 阿里饿了么Java4面:(数据结构+框架源码+JVM+分布式) 2020java面试总结 使用ffmpeg提取mp4内部日期重命名文件(需lua) 【剑指Offer】56.2 数组中只出现一次的数字,其他出现3次 JAVA二三事-使用IO+Properties实现动态读取文本信息 排序算法的C语言实现C代码(未更完) RT-Thread 内核学习--信号量的初步使用 【剑指Offer】57.2 和为S的连续正数序列 Qt三方库开发技术:QXlsx介绍、编译和使用 4G DTU模块的作用和功能说明 【Tips】- Wifi模块和4G无线通信 【5G核心网】 Identifiers 身份标识 DPDK支持的硬件:CPU、网卡NIC、加密引擎、基带加速器 如何根据普通ip地址获取当前地理位置
您的位置:首页 >物联网 >

隐马尔可夫模型(HMM)来龙去脉(二)

目录

前言

预备知识 

一、估计问题

1、问题推导

2、前向算法/后向算法

二、序列问题

1、问题推导

2、维特比算法

三、参数估计问题

1、问题推导

2、期望最大化算法(前向后向算法)

总结


前言

HMM隐马尔可夫模型,这个名字看起来熟悉,其实很是陌生。它给人一种很神秘高深的感觉,确实,很强大的一个模型,在概率论统计学应该是应用广泛而且很重要的;虽说很高深强大的一个模型,其原理确实我们最基础的理论知识不断推导计算来的。

上一篇《原创 隐马尔可夫模型(HMM)来龙去脉(一)》,从HMM基础理论开始,我们可以学习得知,其原理来源于概率论基本重要知识,包括了条件概率、贝叶斯公式、概率分布函数...

而这一篇将继续探索隐马尔可夫模型,深入理解模型背后解决的各种问题,力求基本弄懂这个似乎熟悉而又陌生深奥的模型。接下来探索HMM三个经典的基本问题的解决方案,逐步通过问题推导,公式解析,算法实现,有章可循地真正来理解来龙去脉!


预备知识 

 建议先翻看前一篇《原创 隐马尔可夫模型(HMM)来龙去脉(一)》逐步详细介绍的内容。

一般的,将HMM简单表示为一个三元组\mu=(A,B,\pi) , π是初始状态的概率分布,A是状态转移概率,B是符号发射概率。

由此观察序列O=O_1O_2...O_T可以通过以下步骤产生:

根据初识状态的概率分布\pi_i 选择一个初识状态q_1=s_i.设t=1.根据状态s_i的符号发射概率分布b_i(k)输出O_t=v_k.根据状态转移概率分布a_{ij},将此时 t 的状态转移到新的状态 q_{t+1}=s_j.t=t+1,如果 t<T ,重复执行步骤3和4,否则结束算法。

一、估计问题

1、问题推导

估计问题:给定一个观察序列O=O_1O_2...O_T 和模型\mu=(A,B,\pi),如何快速计算序列O的概率。即P(O ?

我们很直观知道,这其实就是一个条件概率的计算问题。在给定的模型条件下,可以推导以下:

首先根据预备知识可以计算任意状态序列Q下,观察序列O的概率:

P(O

而且 P(Q)=\pi_{q_1}a_{q_1q_2}...a_{q_{T-1}q_T} ,

另外根据条件概率P(O,Q)=P(O.

综上公式,求得在模型\mu=(A,B,\pi)下,

 P(O)=\sum_{Q}P(O,Q)=\sum_{Q}P(O .

然而,这个直观简单的推导公式,计算时间复杂度达到指数级爆炸!N^{T} ! ! ! ,所以呢,需要寻找更高效的计算方法来解决指数级时间问题。


由此,引出HMM中的动态规划方法,一般用格架的组织形式描述。格架算法示意图如下:

思想是:对于一个个状态下的HMM,某一时刻结束时,每个格子能够记录HMM所有输出符号的概率,较长子路径概率可以由较短子路径概率计算出来。

2、前向算法/后向算法

第一步,定义一个前向变量\alpha_t(i)=P(O_1O_2O_3...O_t,q_t=s_i),表示在时间 t ,HMM在状态 s_i 输出一个序列的概率。

第二步,根据动态规划思想,在时间 t+1 的概率计算为:\alpha_{t+1}=(\sum_{i=1}^{N}\alpha_{t}a_{ij})b_j(O_{t+1})  , 其中表示从状态 i 转移到状态 j 并输出观察符号O的概率。

第三步,根据前向变量,可以计算P(O,就是在所有状态下观察到序列O的概率:

P(O

前向变量归纳关系图:

前向算法总结:

1、初始化:\alpha_t(i)=\pi_ib_i(O_1),1\leqslant i\leqslant N

2、归纳计算:\alpha_{t+1}=(\sum_{i=1}^{N}\alpha_{t}a_{ij})b_j(O_{t+1}),1\leqslant t \leqslant T-1

3、求和:P(O

复杂度分析:步骤1计算每个前向变量需要考虑N个状态转移,步骤2计算N个前向变量,所以时间复杂度O(N*N),步骤3在时间1~T过程中,计算量为O(T),所以总时间复杂度为O(N^2T). 因此,使用该算法解决在多项式时间内计算问题。

后向算法方法类似,使用动态规划方法计算,后向变量定义为 \beta _t(i)=P(O_{t+1}...O_T,归纳关系图如下:

后向算法总结:

1、初始化:\beta _T(i)=1,1\leqslant i\leqslant N

2、归纳计算:\beta_{t}=\sum_{j=1}^{N}a_{ij}b_j(O_{t+1})\beta_{t+1}(j),1\leqslant t \leqslant T-1;1\leqslant i\leqslant N

3、求和:P(O. 同理,时间复杂度也是O(N^2T)。  

二、序列问题

1、问题推导

序列问题:给定一个观察序列O=O_1O_2...O_T 和模型\mu=(A,B,\pi),如何快速选择最优状态序列Q,使之最好地解释观察序列O?

对该问题的正确理解就是,给定观察序列和模型后,使条件概率P(O最大的状态序列,即\hat{Q}=argmaxP(Q.

因此,维比特算法定义了一个维比特变量\delta _t(i). 在时间 t 时,HMM沿着某一路径到达状态 s_i,使观察序列O概率最大化。

\delta _t(i)=maxP(q_1,q_2,...,q_t=s_i.

2、维特比算法

\delta _t(i)有如下递归关系,\delta _t(i)=max[\delta_t(j)a_{ij}]b_i(O_{t+1}),根据这个递归关系,所以可以运用动态规划搜索技术。

另外,为了记录时间 t 时,HMM通过的一条概率最大的路径达到状态s_i ,算法设置了另外一个变量\varphi _t(i)来记录前一个时间的状态。

维比特算法如下:

三、参数估计问题

1、问题推导

参数估计问题:给定一个观察序列和模型,使得P(O最大化。

我们知道,HMM中的状态序列是不可见的,所以这里采用期望最大化法(EM),它可以用于含有隐变量的统计模型的参数最大似然估计。

基本思想:从\mu_0得到从某一个状态转移到另一个状态的期望次数,由此得到模型\mu_1,然后,重新估计模型的参数,执行这个迭代过程,直到参数收敛于最大似然估计值。

2、期望最大化算法(前向后向算法)

这种EM方法的具体实现使用到了前向后向算法(forward-backward algorithm)。

这里需要用到几个变量表示概率:

公式(6-24):在时间 t 位于状态s_i ,时间 t+1位于状态s_j的概率\varepsilon _t(i,j)=P(q_t=s_i,q_{t+1}=s_j,O.

公式(6-25):另外,在时间 t 位于状态s_i的概率\gamma _t(i)=\sum_{j=1}^{N}\varepsilon _t(i,j)

\mu 的参数估计公式:

公式(6-26):\bar{\pi_i}=P(q_1=s_i

公式(6-27):\bar{a_{ij}}=\frac{\sum_{t=1}^{T-1}\varepsilon_t(i,j) }{\sum_{t=1}^{T-1}\gamma_t(i)}

公式(6-28.):\bar{b_j(k)}=\frac{\sum_{t=1}^{T}\gamma _t(j)\times \delta (O_t,v_k)}{\sum_{t=1}^{T}\gamma _t(j)}

由上述公式,得出前向后向算法:

总结

至此,我们对隐马尔可夫模型(HMM)有了比较深入的理解,从原理上全面认识HMM实现思想,这一篇非常抽象的展示许多公式,虽然对这些公式不能够完全掌握,但是最重要的是,能够理解HMM三个基本问题解决方案的思想方法,这些经典奇妙的算法也是人们在不断探索中发现的并完善。所以,对于初学者来说,思想方法最重要,原理需要理明白,具体应用实现是利用已经封装好的工具。

这一篇将探索HMM三个经典的基本问题的解决方案,逐步通过问题推导,公式解析,算法实现,对于HMM理解不再天马行空般,来龙去脉基本理清!希望能帮助到像我一样初学者的伙伴,欢迎大佬交流指正!

两篇内容深入理解HMM:

隐马尔可夫模型(HMM)来龙去脉(一)隐马尔可夫模型(HMM)来龙去脉(二)

我的CSDN博客:https://blog.csdn.net/Charzous/article/details/108311177

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/Charzous/article/details/108311177

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。