初学者也能看懂的隐马尔科夫模型介绍

初学者也能看懂的隐马尔科夫模型介绍点击上方“小白学视觉”,选择加”星标”或“置顶”重磅干货,第一时间送达隐马尔科夫模型是(hiddenMarkovmodel,HMM)是可用于标注问题的统计学习模型,描述由隐藏的马尔科夫链随机生成观测序列的过程。隐马尔可夫模型(hiddenMarkovmodel,HMM)是时间序列的概率模型,常用于词性标注,语音识别,文本分析等领域。HMM是基于马尔科夫链进行标注的…

大家好,欢迎来到IT知识分享网。

点击上方“小白学视觉”,选择加”星标“或“置顶

重磅干货,第一时间送达82d25278e9aea5fc9cca238270b91be1.png

隐马尔科夫模型是(hidden Markov model,HMM)是可用于标注问题的统计学习模型,描述由隐藏的马尔科夫链随机生成观测序列的过程。

隐马尔可夫模型(hidden Markov model,HMM)是时间序列的概率模型,常用于词性标注,语音识别,文本分析等领域。HMM是基于马尔科夫链进行标注的,我们对已经观察的数据序列O进行标注,标注序列I相当于不可观测序列(隐变量),如何求解概率最大的标注序列 I 是HMM的核心问题,我们以图解的方式形象的描述HMM问题。

已知观测序列0520ec1996ba41f650cdc63985be0c70.png,标注序列9616d85f78c8d325216ede88f3819bc9.png,其中观测序列是相互独立的且与对应的标注序列相关,标注序列符合马尔科夫链模型,如下图:

eb2906b9108b4e9265c85386ecd8cfda.png

再次强调下隐马尔科夫模型假设的场景,1)观测序列是相互独立的,2)标注序列符合马尔科夫链模型,3)观测序列由标注序列决定。

HMM模型主要处理以下三个问题:

1)已知观测序列O,如何求解HMM模型参数d3cae7f6692d4e3990a7b2bda01d94c0.png

2)已知观测序列O和模型参数d2096b621eb5b6b7df7dc7fecd4a1768.png,如何求解最有可能的标注序列 I 。

3)已知观测序列O和模型参数5b9e28b6560ed696bb51653e03f12dc7.png,如何求解观测序列O出现的概率2ade4a1f3683182a7c957ffbc47cdba1.png

下面给出大致的解决方案:

1) 已知观测序列O,如何求解模型参数5990c1b1a1b3aeab3ed65544550e4d91.png

8869d7bfc4a732dcd60247f60c3e051c.png

其中I为标注序列,在上式中的含义为隐变量,因此可用EM算法求解上式的模型参数00d3e8714685a01e226f766ad12d3b51.png

2) 已知观测序列O和模型参数e8f1933ff1c4178dde099861d41c4e85.png,如何求解最有可能的标注序列 I 

3)已知观测序列O和模型参数6f27c79f53cfd2eac1407ceac5c79dfe.png,如何求解观测序列O出现的概率概率34cf5291ac6b65310e82af085bc5897a.png

后续内容会给出具体的算法和实例。

介绍到这里,相信大家对HMM有了初步的理解了吧,举一个例子来说明HMM的应用场景:

小明每天穿的服装为a7c0a6e08087b042f8fcc248063b828a.png,假设小明穿的服装与前一天穿的服装是相互独立的,且服装的选择受精神状态的影响,当天的精神状态受到前一天精神状态的影响,精神状态为d14d93f69500f74a747dc07884ceeb53.png,已知观察序列f4064ac944a40f050c9e4742dc308178.png,求对应的精神状态序列,这类问题我们可以用HMM来解决。

介绍到这里,相信大家对HMM的基本概念和应用场景有了一定的概念,如果对HMM还不是很理解的话,先别慌,下面循环渐进的介绍HMM,数学要求不高的人也能很好的理解。

1.概率与随机过程的区别

概率是反映随机事件发生的可能性,大学课程《概率论与数理统计》全文内容是基于概率介绍的。若随机事件发生的概率随时间而改变,我们在考虑时间因素或空间因素的情况下去分析随机事件发生的概率,称为随机过程。

若我们每次抛掷硬币且正面向上的概率为0.5,正面向上的概率不随抛掷次数而改变,我们可以用概率来描述这一事件,如P(X),其中X表示硬币正面向上的随机事件。

若我们每次抛掷硬币,硬币落在地上会导致形状的改变,正面向上的概率随抛掷次数的改变而改变,我们用随机过程来描述这一事件,如4e9d2fb48a09f1ee563882b287ce2fe9.png,其中f6419258fb4d15b7caafeb5300a774dd.png表示第i次抛掷硬币正面向上的随机事件。笼统的讲,概率是分析一个随机变量,而随机过程是分析一组随机变量。

2.马尔科夫过程的概念

当随机过程的变量满足马尔科夫性的无记忆性质时,则称为马尔科夫过程。

我们定义cb0879619e7f569290f91901102b1885.png为第i个时刻的随机变量,如下图的随机过程:

379d0f49345b2d3ac6378556889b0922.png

若随机变量满足:

f791cfd59df47b0b7ef12630c6ae49d4.png

上式的含义为t时刻的随机变量只依赖于t-1时刻的随机变量,与其他时刻无关,则称该过程为马尔科夫过程。

3.马尔科夫模型与隐马尔科夫模型的区别

马尔科夫模型与隐马尔科夫模型的区别在于是否含有隐变量,本节还是用小明穿服装的例子来形象的说明马尔科夫模型与隐马尔可夫模型的区别:

若小明每天的服装只受到前一天所穿服装的影响, 下图为小明最近N天所穿服装的序列:

3fa8df5c98220679c1b30be7aa0a4b4a.png

由上节介绍可知服装序列为马尔科夫过程,基于马尔科夫过程的统计模型则称为马尔科夫模型。

若小明每天的服装与前一天所穿服装是相互独立的,且每天所穿的服装是受到当天的精神状态影响,精神状态符合马尔科夫链原理,令服装序列为b4251d352f2270aadb70cd904b35b294.png,精神状态序列为839e80241e64449192daf845d93ea467.png,用下图描述这一过程:

9c3cfa634daaa9f1ce6edcd1e0af6019.png

其中服装序列是可观测序列且观测变量是相互独立的,精神状态序列是不可观测序列(隐变量)且状态变量符合马尔科夫模型,基于上述过程的统计模型称为隐马尔科夫模型。

4.隐马尔科夫模型参数介绍

由上节介绍可知,隐马尔科夫模型包含了观测序列和未观测的状态序列,其中状态序列由初始状态概率向量π和状态转移概率矩阵A决定,观测序列由观测概率矩阵B决定。

还是用小明作为例子,假设小明可选的服装为三件,分别为3817ee57a40360df17e67ae40341e14f.png。小明的精神状态有两种,分别为98ebbe2d306ea5dee129c5071c3875b0.png

因此状态转移概率矩阵A表示为:

4a6c9d908d0d258c3076da6b8ad6de01.png

其中,

e8033a1972258ba1d87e1ba84e048aa2.png

是在时刻t处于状态f416b122ba911cb03607818ae6dfa652.png的条件下在时刻t+1转移到ddd2a1cd135fa9e5f03ef40190f8dca0.png的概率。

观测概率矩阵B表示为:

4f9c1ab6965435df4d6f441f191772f2.png

其中,

4003483a623bf972dc444e03149e84dd.png

是在时刻t处于状态2b660a291de1847241e333d107a4b4d1.png的条件下生成观测7b11af839df70598f87be8cc252944ce.png的概率。

初始状态概率向量729c6f9f8a8116e30fe8318ed0a59044.png表示为:

87ade63b68df3a25070850c25a6ddbf7.png

其中,

63ca7fd5d1c09c4df210cf0c059a017c.png

是时刻t=1处于状态146dbd6f6fcad446e4a816838d0e5993.png的概率。

我们用参数λ表示隐马尔科夫模型参数,即:

8c2121c3b82c5e8730d59d6d84a3839c.png

A,B,π称为隐马尔可夫模型的三要素。

5. 隐马尔可夫模型参数求解算法

上节我们介绍了隐马尔可夫模型参数的含义,如何仅通过观测序列f82163f214f81840dc97482d8de4c06d.png,求解模型参数cdf3361a5a20979763c37ef7dabaca7a.png

我们知道隐马尔可夫过程包含了隐变量 I,那么隐马尔可夫模型事实上是一个含有隐变量的概率模型:

9ae545aa428f6378ca23fe3478b2805f.png

当构建包含隐变量的模型参数时,我们首先想到用EM(期望最大值)算法实现,算法可参考文章(一文让你完全入门EM算法

模型参数求解步骤:

1)初始化隐马尔可夫模型参数d25df5d4cd7dba0450668afda4e61e19.png

2)确定模型完全数据的对数似然函数,隐马尔可夫模型的完全数据包含了观测数据

e6b3a086dd936f1935cbe0ff8597cc6b.png和隐数据a8d7e87fb275375eb61482fe4f3f8bf8.png,完全数据是5d5db4290b8eb5a44ae27ef6fd0672c4.png

因此完全数据的对数似然函数为:c6e1b0c47c8e7ace29f20fe678d362ed.png

3)EM算法的E步,即求完全对数似然函数下隐变量的期望,称为Q函数0f2d6592b328ea3ac8560f5eda052f45.png

有:

7502c0cde948b3f8a619ddbd5e9f090f.png

其中8c16ca0129521fcd2a83990236ed476d.png是隐马尔科夫模型的当前估计值,dffa6ecd5c2e6220dc66a774628865b1.png是马尔科夫模型参数。

根据上节介绍的隐马尔可夫模型参数418ae394040946dad9799243cd0ab367.png的含义,完全数据的似然函数可展开为:

d1a4bb5f4834af2ddfc3b3cbf872818a.png

因此Q函数1d1fe75f480c12e4cf0d392f49779ae2.png可写成:

b43a733a94262d60723deb0fec7c8d26.png

4) EM算法的M步,求Q函数的最大值,得到模型参数c074854a073d0720334735a442cdfd02.png,由上节可知模型参数

8750925b4c1ff93881678deb4fbba283.png

即令:

eb9d62af5241dd43fcb6fab2e5d322ed.png

dad3fd53688a30047f899d7e7ac4425c.png

6467c4a75699ceca3b96f87afdace6e5.png

约束条件为初始状态概率分布的和等于1,即:

103dded91894d32522cdadf1325321b2.png

状态已知的情况下,观测概率分布的和等于1,即:

908588eb95371e8061a0011795b57878.png

由上面的等式得到模型参数9c5e05a69136b05ccf96085ea4cee1be.png,即更新了模型参数20920bdc83480194dd784690cabf2cd9.png的值。具体计算过程这里不再详细描述了,具体可参考李航老师的《统计学习方法》,若有不懂欢迎交流。

5)重复步骤(3)(4),直到函数8de3bdb8a02816a7fad48f9d97322e50.png收敛,得到最终的模型参数7c072e47102ae02a54931073356f06f2.png

6.观测序列概率计算算法

上一节介绍了如何通过观测序列去估计模型参数e90b01b5f592df9573d3d3c7336453b9.png,当模型参数107864f8ddbe6eaf38a89d51d58c821d.png已知时,隐马尔可夫模

型也相应的确定了,观测序列的概率可以通过模型参数计算出来。下面介绍两种观测序列概

率计算算法:

1)枚举法

给定模型1831e83a0f40a6d65cce8929fe3eef4f.png和观测序列10fc785502a8c6b31d8b1481811776f1.png,计算观测序列O出现的概率0f7872c111313652c689b70c27bc6612.png。假设状态序列a7efc2fd3a1e47c22d02e25502d5571a.png,可能的状态数是N,因此每个观测变量都可能由N个状态生成,且模型参数已知,我们就能算出每个可能的状态序列生成观测序列的概率。如下图:

f8a0605aa221f06363dce27ec106edb3.png

这种列举所有可能的状态数来计算观测序列的概率理论上是可行的,但是计算量非常大,如上图对于长度为T的观测序列,复杂度达到了5ad341b1a282bfda971679a8f2d4357c.png

2)递推法

隐马尔科夫具有时间序列的特点,因此我们可以用递推的方法去计算观测序列出现的概率。给定马尔科夫模型7af67b5ecc6dab4ec34a8662c0ee37a0.png ,定义到时刻t部分观测序列为5f328326422d63dbf1d584695c2617f3.png且状态为dd30e059c5bea9ef2d0cbe784773003c.png的前向概率为c62497424bc2a9a569794f2d5957cb00.png

52e49edf66f3b78301f19b7f81da26d7.png

1)时刻t=1时刻的观测概率为:

784d52ed2f378f7c1c52c30dc08b5d39.png

2)递推,对于d7ab2b05d2ff0602213d524471e9a050.png,有:

7f7fb32fb772ef1f429e2f5a0a47c846.png

3)当t=T时,

7a66c82feb6f7bb70c6917597ab86e5d.png

算法复杂度研究:因为该算法考虑的是用递推关系求观测序列的概率,递推过程如下图:

507aa91fd47126c6e5008580c5b17a2d.png

方程表示为:

be1ddd112689e786fd43d8216a8f8b14.png

由上式可知,计算t+1时刻状态为 i 的计算量为N次相乘求和,且t+1时刻状态的可能数为N,因此由t时刻递推到t+1时刻的计算量为4373251c6f803dd2a94f0eae5c188af2.png 阶,观测序列的长度为T,那么计算量为4acf38641e7e7c204968d6febe9d3d70.png阶,与之前枚举法相比,计算量大大降低了。

7.状态序列预测算法

给定模型参数57494366c7b19b16351957212e0cbd62.png 和观测序列21e02379fbcebff9ccc70f0be95d58ba.png,如何预测最有可能的状态序列,这是隐马尔科夫模型的应用最广的场景,如词性标注,给定一个句子,标注每个单词的特性;

本节介绍维特比算法(Viterbi algorithm)来预测状态序列。维特比算法是一种动态规划算法,用于寻找最有可能产生的状态序列。

通过节点

算法的核心思想是:若t时刻最有可能的状态序列1ceea7faf1844c0797304cd23f4089ee.png通过节点4c7c676093161b5fb8e885ce168e37fa.pngc9ddaaadeb270a91acfc6731ea3d1f60.png为t时刻的状态),那么从t时刻到T时刻的最优路径一定包括9273abcd273fab5ed317c0a22ae3d0f3.png。我们利用这一思想确定了最优状态序列的最后一个时刻的状态4c88ad1d3e3913f32910b7b0e43667b4.png,然后利用该状态回溯时刻58c908ab92c4a1d38fef26384454ee27.png的最优状态。用一个例子说明维特比算法:

已知模型625cecae3544efba090d44c1e19732ba.png,观测集合V={红,白},状态集合Q={1,2,3},其中

418a056f9a2fae7fb23c3cac8a8ca67c.png

若观测序列O=(红,白,红),求最优状态序列5a8a67481b4edd5143e9fc1edc9b8443.png

解:定义c8cc36c748c1e6030c9549db3ca8dcc8.png为时刻t状态为 i 的所有单个路径f44c813695739fc434ee2795d67442d3.png中概率的最大值,含义为给定前t-1时刻的状态和前t时刻的观测序列,求最优路径t时刻的状态,即:

dec79e67fc6b8fdbf55581ba67562753.png

定义cea775fa4aefa1828ac2c13143c4abbc.png为时刻t状态为 i 的所有单个路径b077c2eac7521b28ed1c910086ee38b8.png中概率最大路径的第t-1个节点为:

9c0a1c9bf6c8f3bf9c66b05cdc35f8fc.png

根据维特比算法的核心思想,我们计算观测序列下的最优路径:

1)t=1时,令8df12df7aa7c6e2892f945413b3daec6.png是观测为2d11fe3bc7c3263fc668c350f9233047.png状态为i的概率,由题目可知a2810d4507d71baed65dd33839faa45f.png为红色,有:

4e61a879efe1567d1adbf774fee941c4.png

代入已知条件得:

d2c3c586ba01d585dfca89fca53abf5c.png

ca0bd476ebf9267433eaaadf8f272d6d.png

2)t=2时,

ec42d3e2773ae5da69da3ffe7f21e625.png

由上面两式得:

dfa386e3ded0c2168aedbf085b7895d3.png

d184655484abe2a6d830c3872b22a36a.png

2)t=3时,

73aa24eced34a9364be470b7f15cfe91.png

得:

c6b7c2b28ff8151c6eff8a1331791c27.png

ceb7807406a2489ea7d974c484a91251.png表示最优路径的概率,最优路径的终点774e32ac26a9585ef45feec1e8d94171.png

2ae4731ee57bf8c0b81d404e6bf0abcb.png

5115a679b9f5f7cac8fb70a7effdc303.png

因此最优状态序列:

4488f92f8e5dbc7106bfce30ad651e29.png

8.小结

本文首先用一个例子通俗的讲解了隐马尔可夫模型的适用场景以及隐马尔可夫模型的三个主要处理问题,然后循序渐进的介绍了隐马尔可夫模型的概念和相关问题的解决方法,所用的例子选取了《统计学习方法》的内容。后续文章会介绍另一种相似的算法——条件随机场以及两者的区别,希望对初学者能有所帮助。

下载1:OpenCV-Contrib扩展模块中文版教程

在「小白学视觉」公众号后台回复:扩展模块中文教程即可下载全网第一份OpenCV扩展模块教程中文版,涵盖扩展模块安装、SFM算法、立体视觉、目标跟踪、生物视觉、超分辨率处理等二十多章内容。

下载2:Python视觉实战项目52讲

在「小白学视觉」公众号后台回复:Python视觉实战项目即可下载包括图像分割、口罩检测、车道线检测、车辆计数、添加眼线、车牌识别、字符识别、情绪检测、文本内容提取、面部识别等31个视觉实战项目,助力快速学校计算机视觉。

下载3:OpenCV实战项目20讲

在「小白学视觉」公众号后台回复:OpenCV实战项目20讲即可下载含有20个基于OpenCV实现20个实战项目,实现OpenCV学习进阶。

交流群

欢迎加入公众号读者群一起和同行交流,目前有SLAM、三维视觉、传感器、自动驾驶、计算摄影、检测、分割、识别、医学影像、GAN、算法竞赛等微信群(以后会逐渐细分),请扫描下面微信号加群,备注:”昵称+学校/公司+研究方向“,例如:”张三 + 上海交大 + 视觉SLAM“。请按照格式备注,否则不予通过。添加成功后会根据研究方向邀请进入相关微信群。请勿在群内发送广告,否则会请出群,谢谢理解~

3f145638bb93275ec0252a94e664aaa0.png

91daf9404b37836121fd9d4cb86e8860.png

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/14927.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信