专栏首页深度学习自然语言处理如何用简单易懂的例子解释隐马尔可夫模型?(进阶篇)

如何用简单易懂的例子解释隐马尔可夫模型?(进阶篇)

阅读大概需要10分钟 跟随小博主,每天进步一丢丢

作者:Yang Eninala 链接:https://www.zhihu.com/question/20962240/answer/33438846

昨天通俗易懂的讲解了什么是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。

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

同样,我们计算第三个骰子分别是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.掷一串骰子出来,让我猜猜你是谁

(这个问题以后等讲了EM算法小博主再普及O.O)

一些话

上述算法呢,其实用到了递归,逆向推导,循环这些方法,我只不过用很直白的语言写出来了。如果你们去看专业书籍呢,会发现更加严谨和专业的描述。毕竟,我只做了会其意,要知其形,还是要看书的。

本文分享自微信公众号 - 深度学习自然语言处理(zenRRan),作者:Yang Eninala

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-02

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【论文笔记】命名实体识别论文

    其实实体识别这块看了挺久了的,今天就来好好聊一聊它。实体识别(Name Entity Recognition)是属于NLP任务中的序列标注问题:给定一个输入句子...

    zenRRan
  • EMNLP 2018 | 为什么使用自注意力机制?

    作者:Gongbo Tang、Mathias Muller、Annette Rios、Rico Sennrich

    zenRRan
  • 深度学习之RNN、LSTM及正向反向传播原理

    总说 RNN( Recurrent Neural Network 循环(递归)神经网络) 跟人的大脑记忆差不多。我们的任何决定,想法都是根据我们之前已经学到的...

    zenRRan
  • 【机器学习 基本概念】隐马尔可夫模型

    隐形马尔可夫模型,英文是 Hidden Markov Models,所以以下就简称 HMM。 既是马尔可夫模型,就一定存在马尔可夫...

    魏晓蕾
  • 用简单易懂的例子解释隐马尔可夫模型

    隐马尔可夫(HMM)好讲,简单易懂不好讲。我希望我的读者不是专家,而是对这个问题感兴趣的入门者,所以我会多阐述数学思想,少写公式。霍金曾经说过,你多写一个公式,...

    AI研习社
  • PIKOCUBE:带 LED、陀螺仪,WiFi 控制的可编程骰子

    今天给大家带来一个非常好玩的项目,带有 54 颗 LED、陀螺仪,支持 WiFi 控制的可编程骰子。

    MCU起航
  • DNSPod 域名 1 元购,全场 1 折起!

    ? ? ? ? ? ? 点此立即抢购 错过再等亿年 ---- ? ↓ 疯抢中,手慢无~

    腾讯云DNSPod团队
  • (22)Bash环境变量

    用户自定义变量只在当前的Shell中生效,而环境变量会在当前Shell和这个Shell的所有子Shell当中生效。如果把环境变量写入相应的配置文件,那么这个环境...

    生信real
  • spring boot 2 上传附件文件过大时,没法捕捉异常

    在做项目中,使用了spring boot 的文件上传功能,但当上传的文件超出指定大小时,报以下错误.

    星痕
  • 安装数据库很痛苦?试试这个SQL在线编辑器,省掉你的安装烦恼

    经常有小伙伴因为数据库安装报错给我私信。发给我的报错各式各样,有些我能解决,有些报错真的我也没见过,不知如何作答。这导致很多初学SQL的爱好者自信心受到打击。

    披头

扫码关注云+社区

领取腾讯云代金券