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

阅读大概需要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)

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

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

手把手教你用 Keras 实现 LSTM 预测英语单词发音

我近期在研究一个 NLP 项目,根据项目的要求,需要能够通过设计算法和模型处理单词的音节 (Syllables),并对那些没有在词典中出现的单词找到其在词典中对...

962
来自专栏绿巨人专栏

机器学习中的基本数学知识

7897
来自专栏智能算法

向量化与HashTrick在文本挖掘中预处理中的体现

前言 在(文本挖掘的分词原理)中,我们讲到了文本挖掘的预处理的关键一步:“分词”,而在做了分词后,如果我们是做文本分类聚类,则后面关键的特征预处理步骤有向量化或...

3355
来自专栏机器学习算法与Python学习

向量化与HashTrick在文本挖掘中预处理中的体现

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 前言 在(文本挖掘的分词原理)中,我...

4017
来自专栏AI研习社

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

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

3425
来自专栏量化投资与机器学习

七步理解深度学习

原文链接请点击阅读原文。 There are many deep learning resources freely available online,but...

2089
来自专栏tkokof 的技术,小趣及杂念

对于"矩阵连乘问题"的一点想法

在算法设计的学习中,每到“动态规划”一节,一般都会涉及到“矩阵连乘”问题(例如《Algorithms》,中文译名《算法概论》),可想而知该题的经典程度 :)

1353
来自专栏人工智能头条

TensorFlow快餐教程:程序员快速入门深度学习五步法

1472
来自专栏数说工作室

文本分析 | 常用距离/相似度 一览

这个系列打算以文本相似度为切入点,逐步介绍一些文本分析的干货,包括分词、词频、词频向量、TF-IDF、文本匹配等等。 第一篇中,介绍了文本相似度是干什么的; 第...

4874
来自专栏AI科技大本营的专栏

如何快速优化机器学习的模型参数

【导读】一般来说机器学习模型的优化没什么捷径可循。用什么架构,选择什么优化算法和参数既取决于我们对数据集的理解,也要不断地试错和修正。所以快速构建和测试模型的能...

1212

扫码关注云+社区

领取腾讯云代金券