图解隐马尔科夫模型【会其意】

隐马尔可夫(HMM)好讲,简单易懂不好讲。少写公式。霍金曾经说过,你多写一个公式,就会少一半的读者。所以时间简史这本关于物理的书和麦当娜关于性的书卖的一样好。我会效仿这一做法,写最通俗易懂的答案。

还是用最经典的例子,掷骰子。假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子(称这个骰子为D6),6个面,每个面(1,2,3,4,5,6)出现的概率是1/6。第二个骰子是个四面体(称这个骰子为D4),每个面(1,2,3,4)出现的概率是1/4。第三个骰子有八个面(称这个骰子为D8),每个面(1,2,3,4,5,6,7,8)出现的概率是1/8。

假设我们开始掷骰子,我们先从三个骰子里挑一个,挑到每一个骰子的概率都是1/3。然后我们掷骰子,得到一个数字,1,2,3,4,5,6,7,8中的一个。不停的重复上述过程,我们会得到一串数字,每个数字都是1,2,3,4,5,6,7,8中的一个。例如我们可能得到这么一串数字(掷骰子10次):1 6 3 5 2 7 3 5 2 4

这串数字叫做可见状态链。但是在隐马尔可夫模型中,我们不仅仅有这么一串可见状态链,还有一串隐含状态链。在这个例子里,这串隐含状态链就是你用的骰子的序列。比如,隐含状态链有可能是:D6 D8 D8 D6 D4 D8 D6 D6 D4 D8

一般来说,HMM中说到的马尔可夫链其实是指隐含状态链,因为隐含状态(骰子)之间存在转换概率(transition probability)。在我们这个例子里,D6的下一个状态是D4,D6,D8的概率都是1/3。D4,D8的下一个状态是D4,D6,D8的转换概率也都一样是1/3。这样设定是为了最开始容易说清楚,但是我们其实是可以随意设定转换概率的。比如,我们可以这样定义,D6后面不能接D4,D6后面是D6的概率是0.9,是D8的概率是0.1。这样就是一个新的HMM。

同样的,尽管可见状态之间没有转换概率,但是隐含状态和可见状态之间有一个概率叫做输出概率(emission probability)。就我们的例子来说,六面骰(D6)产生1的输出概率是1/6。产生2,3,4,5,6的概率也都是1/6。我们同样可以对输出概率进行其他定义。比如,我有一个被赌场动过手脚的六面骰子,掷出来是1的概率更大,是1/2,掷出来是2,3,4,5,6的概率是1/10。

其实对于HMM来说,如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率,做模拟是相当容易的。但是应用HMM模型时候呢,往往是缺失了一部分信息的,有时候你知道骰子有几种,每种骰子是什么,但是不知道掷出来的骰子序列;有时候你只是看到了很多次掷骰子的结果,剩下的什么都不知道。如果应用算法去估计这些缺失的信息,就成了一个很重要的问题。

和HMM模型相关的算法主要分为三类,分别解决三种问题:

1)知道骰子有几种(隐含状态数量),每种骰子是什么(转换概率),根据掷骰子掷出的结果(可见状态链),我想知道每次掷出来的都是哪种骰子(隐含状态链)。
这个问题呢,在语音识别领域呢,叫做解码问题。这个问题其实有两种解法,会给出两个不同的答案。每个答案都对,只不过这些答案的意义不一样。第一种解法求最大似然状态路径,说通俗点呢,就是我求一串骰子序列,这串骰子序列产生观测结果的概率最大。第二种解法呢,就不是求一组骰子序列了,而是求每次掷出的骰子分别是某种骰子的概率。比如说我看到结果后,我可以求得第一次掷骰子是D4的概率是0.5,D6的概率是0.3,D8的概率是0.2.第一种解法我会在下面说到。

2)还是知道骰子有几种(隐含状态数量),每种骰子是什么(转换概率),根据掷骰子掷出的结果(可见状态链),我想知道掷出这个结果的概率。
看似这个问题意义不大,因为你掷出来的结果很多时候都对应了一个比较大的概率。问这个问题的目的呢,其实是检测观察到的结果和已知的模型是否吻合。如果很多次结果都对应了比较小的概率,那么就说明我们已知的模型很有可能是错的,有人偷偷把我们的骰子給换了。

3)知道骰子有几种(隐含状态数量),不知道每种骰子是什么(转换概率),观测到很多次掷骰子的结果(可见状态链),我想反推出每种骰子是什么(转换概率)
这个问题很重要,因为这是最常见的情况。很多时候我们只有可见结果,不知道HMM模型里的参数,我们需要从可见结果估计出这些参数,这是建模的一个必要步骤。

问题阐述完了,下面就开始说解法。(0号问题在上面没有提,只是作为解决上述问题的一个辅助)

0.一个简单问题
其实这个问题实用价值不高。由于对下面较难的问题有帮助,所以先在这里提一下。

知道骰子有几种,每种骰子是什么,每次掷的都是什么骰子,根据掷骰子掷出的结果,求产生这个结果的概率。

解法无非就是概率相乘:

1.看见不可见的,破解骰子序列
这里我说的是第一种解法,解最大似然路径问题。
举例来说,我知道我有三个骰子,六面骰,四面骰,八面骰。我也知道我掷了十次的结果(1 6 3 5 2 7 3 5 2 4),我不知道每次用了那种骰子,我想知道最有可能的骰子序列。

其实最简单而暴力的方法就是穷举所有可能的骰子序列,然后依照第零个问题的解法把每个序列对应的概率算出来。然后我们从里面把对应最大概率的序列挑出来就行了。如果马尔可夫链不长,当然可行。如果长的话,穷举的数量太大,就很难完成了。

另外一种很有名的算法叫做Viterbi algorithm. 要理解这个算法,我们先看几个简单的列子。

首先,如果我们只掷一次骰子:

看到结果为1.对应的最大概率骰子序列就是D4,因为D4产生1的概率是1/4,高于1/6和1/8.

把这个情况拓展,我们掷两次骰子:

结果为1,6.这时问题变得复杂起来,我们要计算三个值,分别是第二个骰子是D6,D4,D8的最大概率。显然,要取到最大概率,第一个骰子必须为D4。这时,第二个骰子取到D6的最大概率是


同样的,我们可以计算第二个骰子是D4或D8时的最大概率。我们发现,第二个骰子取到D6的概率最大。而使这个概率最大时,第一个骰子为D4。所以最大概率骰子序列就是D4 D6。

继续拓展,我们掷三次骰子:

作者:Yang Eninala
链接:https://www.zhihu.com/question/20962240/answer/33438846
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

同样,我们计算第三个骰子分别是D6,D4,D8的最大概率。我们再次发现,要取到最大概率,第二个骰子必须为D6。这时,第三个骰子取到D4的最大概率是

同上,我们可以计算第三个骰子是D6或D8时的最大概率。我们发现,第三个骰子取到D4的概率最大。而使这个概率最大时,第二个骰子为D6,第一个骰子为D4。所以最大概率骰子序列就是D4 D6 D4。

写到这里,大家应该看出点规律了。既然掷骰子一二三次可以算,掷多少次都可以以此类推。我们发现,我们要求最大概率骰子序列时要做这么几件事情。首先,不管序列多长,要从序列长度为1算起,算序列长度为1时取到每个骰子的最大概率。然后,逐渐增加长度,每增加一次长度,重新算一遍在这个长度下最后一个位置取到每个骰子的最大概率。因为上一个长度下的取到每个骰子的最大概率都算过了,重新计算的话其实不难。当我们算到最后一位时,就知道最后一位是哪个骰子的概率最大了。然后,我们要把对应这个最大概率的序列从后往前推出来。

2.谁动了我的骰子?
比如说你怀疑自己的六面骰被赌场动过手脚了,有可能被换成另一种六面骰,这种六面骰掷出来是1的概率更大,是1/2,掷出来是2,3,4,5,6的概率是1/10。你怎么办么?答案很简单,算一算正常的三个骰子掷出一段序列的概率,再算一算不正常的六面骰和另外两个正常骰子掷出这段序列的概率。如果前者比后者小,你就要小心了。

比如说掷骰子的结果是:

要算用正常的三个骰子掷出这个结果的概率,其实就是将所有可能情况的概率进行加和计算。同样,简单而暴力的方法就是把穷举所有的骰子序列,还是计算每个骰子序列对应的概率,但是这回,我们不挑最大值了,而是把所有算出来的概率相加,得到的总概率就是我们要求的结果。这个方法依然不能应用于太长的骰子序列(马尔可夫链)。

我们会应用一个和前一个问题类似的解法,只不过前一个问题关心的是概率最大值,这个问题关心的是概率之和。解决这个问题的算法叫做前向算法(forward algorithm)。

首先,如果我们只掷一次骰子:

看到结果为1.产生这个结果的总概率可以按照如下计算,总概率为0.18:

把这个情况拓展,我们掷两次骰子:

看到结果为1,6.产生这个结果的总概率可以按照如下计算,总概率为0.05:

继续拓展,我们掷三次骰子:

看到结果为1,6,3.产生这个结果的总概率可以按照如下计算,总概率为0.03:

同样的,我们一步一步的算,有多长算多长,再长的马尔可夫链总能算出来的。用同样的方法,也可以算出不正常的六面骰和另外两个正常骰子掷出这段序列的概率,然后我们比较一下这两个概率大小,就能知道你的骰子是不是被人换了。

3.掷一串骰子出来,让我猜猜你是谁

(正文描述,略去)

郑重说明,此博文,来自知乎网(https://www.zhihu.com/question/20962240),我为了自己研究学习,方便查询,转帖在自己的博客,若原博主不同意,请在我的博客留言告知,我将删去!

时间: 06-15

图解隐马尔科夫模型【会其意】的相关文章

隐马尔科夫模型—2

二 定义 (1) 基本定义 在上一篇中,我们通过一个给母亲打电话预测天气的例子,来引入隐马尔科夫模型.下面我们将结合一中的例子来形式化的定义隐马尔可夫模型.隐马尔科夫模型是关于时序的概率模型,描述的由一个隐藏的马尔科夫链随机生成不可观测的状态随机序列,再由各个状态生成一个观测而产生观测随机序列的过程.在我们这个例子中,就是由一个隐藏的马尔科夫链生成每天的天气(状态),再由每天的天气决定每天母亲下班以后做什么(观测)的随机过程.隐藏的马尔科夫链随机生成的状态的序列,称为状态序列,也就是最近一段时间

隐马尔科夫模型

特征向量:跟踪框位置相对轨迹中心的比值,角度,速度. 马尔科夫模型: State Sequence, q1 q2 ...... qT t个状态之间的转移可见,则这个时间序列的概率是πq1 × aq1q2 × ...... × aqT-1qT 隐马尔科夫模型: 状态不可见(隐藏),只能从观察值推测出,所以由观察值推测该时刻的状态有个观察值概率b. πq1 × bq1( o1 ) × aq1q2 × bq2( o2 ) × ...... × aqT-1qT × bqT( oT ), 三个问题: 1.

HMM基本原理及其实现(隐马尔科夫模型)

HMM(隐马尔科夫模型)基本原理及其实现 HMM基本原理 Markov链:如果一个过程的“将来”仅依赖“现在”而不依赖“过去”,则此过程具有马尔可夫性,或称此过程为马尔可夫过程.马尔可夫链是时间和状态参数都离散的马尔可夫过程.HMM是在Markov链的基础上发展起来的,由于实际问题比Markov链模型所描述的更为复杂,观察到的时间并不是与状态一一对应的,而是通过一组概率分布相联系,这样的模型称为HMM.HMM是双重随机过程:其中之一是Markov链,这是基本随机过程,它描述状态的转移,是隐含的.

隐马尔科夫模型HMM(三)鲍姆-韦尔奇算法求解HMM参数

隐马尔科夫模型HMM(一)HMM模型 隐马尔科夫模型HMM(二)前向后向算法评估观察序列概率 隐马尔科夫模型HMM(三)鲍姆-韦尔奇算法求解HMM参数(TODO) 隐马尔科夫模型HMM(四)维特比算法解码隐藏状态序列(TODO) 在本篇我们会讨论HMM模型参数求解的问题,这个问题在HMM三个问题里算是最复杂的.在研究这个问题之前,建议先阅读这个系列的前两篇以熟悉HMM模型和HMM的前向后向算法,以及EM算法原理总结,这些在本篇里会用到.在李航的<统计学习方法>中,这个算法的讲解只考虑了单个观测

炎热天气看书还是钓鱼?隐马尔科夫模型教你预测!

高温天气与行为概率 夏季是一年最热的时候,气温普遍偏高,一般把日最高气温达到35℃以上的天气叫作高温天气,但是一般情况下高温天气分为两类.  (1)干热型高温.一般是指气温较高.太阳辐射强而且空气的湿度较小的高温天气.  (2)闷热型高温.一般是指水汽丰富,但是气温相对而言并不算太高,给人感受闷热.  小张在不同类型下的高温天气下会有不同的行为,但是归纳起来为主要为散步.垂钓.看书三类,分别在干热型高温和闷热型高温下对应行为的概率见下表.  假设干热型高温和闷热型高温之间会进行相互转变,每天可能

七月算法-12月机器学习在线班--第十七次课笔记-隐马尔科夫模型HMM

七月算法-12月机器学习--第十七次课笔记-隐马尔科夫模型HMM 七月算法(julyedu.com)12月机器学习在线班学习笔记http://www.julyedu.com 隐马尔科夫模型 三个部分:概率计算,参数估计,模型预测 1,HMM定义 HMM由初始概率分布π.状态转移概率分布A以及观测概率分布B确定. Eg:以中文分词为例子 隐状态为="2",是不是终止字,是/否?(Y/N)即是不是最后一个字. A矩阵:第一个:当前是终止字,下一个也是终止字的概率 B是当前的隐状态是终止词,

隐马尔科夫模型HMM

隐马尔科夫模型HMM 作者:樱花猪 摘要: 本文为七月算法(julyedu.com)12月机器学习第十七次课在线笔记.隐马尔可夫模型(Hidden Markov Model,HMM)是统计模型,它用来描述一个含有隐含未知参数的马尔科夫过程.其难点是从可观察的参数中确定该过程的隐含参数,然后利用这些参数来作进一步的分析.在早些年HMM模型被非常广泛的应用,而现在随着机器学习的发展HMM模型的应用场景越来越小然而在图像识别等领域HMM依然起着重要的作用. 引言: 隐马尔科夫模型是马尔科夫链的一种,它

隐马尔科夫模型python实现简单拼音输入法

在网上看到一篇关于隐马尔科夫模型的介绍,觉得简直不能再神奇,又在网上找到大神的一篇关于如何用隐马尔可夫模型实现中文拼音输入的博客,无奈大神没给可以运行的代码,只能纯手动网上找到了结巴分词的词库,根据此训练得出隐马尔科夫模型,用维特比算法实现了一个简单的拼音输入法.githuh地址:https://github.com/LiuRoy/Pinyin_Demo 原理简介 隐马尔科夫模型 抄一段网上的定义: 隐马尔可夫模型 (Hidden Markov Model) 是一种统计模型,用来描述一个含有隐含

隐马尔科夫模型(HMM)

HMM简介 HMM用于研究非确定性生成模式,HMM是一个与时间无关的模型(有待改进),并且n阶HMM模型是指下一个状态只与前n个有关,通常只研究一阶HMM模型(有待改进).从可观察的参数中确定该过程的隐含参数,然后利用这些参数来作进一步的分析,例如模式识别. 下面可以使用一个案例来解释HMM模型. 假设有三种色子,分别是标有123456的立方体.标有1234的三菱锥.标有12345678的八面体.它们分别记为D6.D4.D8,假设我们从三个色子中任意挑一个色子的概率为1/3,然后我们可以随意掷色