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

本题已收录至知乎圆桌:机器之能 X 语言之美,更多「人工智能」相关话题欢迎关注讨论。
关注者
12,277
被浏览
767,291

37 个回答

收录于 编辑推荐知乎圆桌 ·
×××××11月22日已更新×××××

隐马尔可夫(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.一个简单问题
其实这个问题实用价值不高。由于对下面较难的问题有帮助,所以先在这里提一下。

知道骰子有几种,每种骰子是什么,每次掷的都是什么骰子,根据掷骰子掷出的结果,求产生这个结果的概率。
解法无非就是概率相乘:
P=P(D6)*P(D6\rightarrow 1)*P(D6\rightarrow D8)*P(D8\rightarrow 6)*P(D8\rightarrow D8)*P(D8\rightarrow 3)
=\frac{1}{3} *\frac{1}{6} *\frac{1}{3} *\frac{1}{8} *\frac{1}{3} *\frac{1}{8}

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的最大概率是
P2(D6)=P(D4)*P(D4\rightarrow 1)*P(D4\rightarrow D6)*P(D6\rightarrow 6)
=\frac{1}{3} *\frac{1}{4} *\frac{1}{3} *\frac{1}{6}
同样的,我们可以计算第二个骰子是D4或D8时的最大概率。我们发现,第二个骰子取到D6的概率最大。而使这个概率最大时,第一个骰子为D4。所以最大概率骰子序列就是D4 D6。

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

同样,我们计算第三个骰子分别是D6,D4,D8的最大概率。我们再次发现,要取到最大概率,第二个骰子必须为D6。这时,第三个骰子取到D4的最大概率是P3(D4)=P2(D6)*P(D6\rightarrow D4)*P(D4\rightarrow 3)
=\frac{1}{216} *\frac{1}{3} *\frac{1}{4}
同上,我们可以计算第三个骰子是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这个号称算法的方法)

上述算法呢,其实用到了递归,逆向推导,循环这些方法,我只不过用很直白的语言写出来了。如果你们去看专业书籍呢,会发现更加严谨和专业的描述。毕竟,我只做了会其意,要知其形,还是要看书的。
(手机码字,继续欠修改)
WARNING:这篇文章是给零基础人士看的。目标是让普通初中生以及只有初中基础人士无障碍理解HMM框架。追求数学严谨性人士、追求用简洁符号表达模型的同学以及数理基础良好的大神请自行移步参阅文献。

讲这种东西就得先搞清HMM到底干了什么,初学者很容易对“模型在干嘛”这个问题上犯晕。我个人特别讨厌跟初学者上来就讲state space/transition matrix/emission probability云云的讲法(注:比如《统计学习方法》李航博士那种讲法。虽然用来准备面试很方便,但初学者肯定会被符号和几个概念绕晕了;另外,私以为他换掉符号和前人文献不保持一致的做法又会让初学者又多了一道坎去翻。总之,不太厚道)。因为初学时,对大多非理科出身的人而言,用抽象的名词与符号描述的“语言系统”还没固化在脑袋里。用抽象符号在那儿讲就好比“一群人还没学会走,就逼着他们快点跑”。这是不太现实的。

综上,用复杂抽象的语言描述不合适的,这个学习曲线过于陡峭,别人需要时间消化。基于此原因,我发现,对零基础小伙伴们用游戏的例子去类比地解释往往比较容易降低学习难度,比如这样讲:

我是一战士,修炼出了三种战斗形态,分别为暴怒态正常状态防御态。同时我也会三个被动技能,分别是普通平A,爆击(攻击伤害翻倍),吸血(生命汲取)。
我在暴怒状态下打出暴击的概率是80%,打出吸血概率为5%;
在平衡形态下,打出暴击的比率为30%,打出吸血的概率是20%;
在防御形态下,暴击成功概率为5%,吸血概率为60%。
总结一下,战士在不同状态下能打出技能的概率不一样

本来,战士这个职业在暴怒态时,身边会有一圈红光环;防御态时,会有一圈蓝光环。但是,现在我正在玩游戏,游戏突然出了个bug:有个傻x程序员改了游戏的代码,他给写崩了,从此战士身边光环都看不见了。那我没法通过看脚下的光环知道战士在爆什么状态了。

话说,现在问题来了:由于看不到脚下光环,我只能估计“战士”在爆什么状态;但我现在打一boss,砍10次,发现8次都是暴击,血哗哗地翻倍在掉,你觉得我这战士最可能是爆了什么状态?

(每次用这个不规范的例子和新手讲,他们立刻就懂了;而且他们接下来还会问:"’暴怒状态’不能总持续吧?这不科学,应该限定个一段时间后,暴怒状态消失的概率为50%...."你瞧瞧连状态转换的transition prob自己都能假设出来了,都会抢答了都lol...“HMM的在干什么”的问题很容易地让他们就理解了)

综上,一个战士的状态会不断随时间变化;然后他的被动技能发动概率会因为所处不同状态而不同。这就是HMM想表达的东西。并且我们还可以通过它回答一些有趣的问题:通过战士发动的技能来推测战士所出的状态。

这个例子只是个感性认识,它其实只是告诉了我们hmm比较“像什么东西”。显然,我们还需要更规范更严谨地去介绍什么是HMM,去规范化这个模型。这个例子里的“战士”可以换成其它答案里的天气,换成硬币等等。但无论用什么说法,我们已经能通过这个例子抓住核心问题了:HMM模型就是这样一个系统——它有一个能不断改变的隐藏的状态(在这个例子里就是战士爆的状态。它会变,而且由于一个码农的缘故,状态变得不可见)在持续地影响它的外在表现(在这个例子里就是战士打出的技能是暴击、平a、还是吸血的概率)。再重复一遍:HMM模型就是这样一个系统——它有一个会随时间改变的隐藏的状态,在持续地影响它的外在表现。

现在我们再继续规范一下这个例子,让它更贴近那种严谨描述。
因为我们知道战士打人总爆击,角色特别bug,这没法玩啊。所以我们要限制一下战士爆状态。
我们在游戏里做了个限制:
我们设定,战士一开始进入游戏世界时是正常状态的。而且,每过一段时间(比如1分钟),战士就会自动爆一次状态。最后,每一次爆发还和上一次状态爆的状态是什么有关:
1.上一次如果是正常状态,那下次变为暴怒的概率比较大下次转换成暴怒状态平衡状态防御状态的概率我们假设分别为60%,30%,10%。这保证了战士职业下次能有较大的概率能打出暴击!
2.同理,若当我们上次在暴怒态时,下次继续保持暴怒态的概率就得限制一下。下次继续保持暴怒的概率就设为10%,而转换成正常状态的概率是60%,转换成防御态的概率是30%;
3.如果上次是防御态,那么我们也让它下次也尽量变正常。(不然总吸血啊)那他下次转成其它三态的概率(三态和以上对应书写顺序一致)分别为为10%,60,30%。
这样服务器就能限制战士的爆暴怒态的次数,让它不那么imba。

顺便提一下,其实以上的这种限定——让战士下一次爆不同状态的概率只和上次处在什么状态有关系——叫马尔可夫性质(markov property)。
经过这样的设定后,不仅仅战士这个职业不会那么imba,而且,我们可以靠以上这些数字来计算之前只能感性理解的问题了。比如:我这个战士在第一分钟的时候是正常状态,那么我第二分钟赶去死亡谷打一个boss能暴击的概率是多少?(这个当作思考题,提示:想想两个问题,上一状态和下一状态间转换的概率是多少?不同状态下发不同技能的概率是多少?)

最后总结一下。以上例子中讲明了HMM的五样“要素”:
1.状态和状态间转换的概率
2.不同状态下,有着不同的外在表现的概率。
3.最开始设置的初始状态
4.能转换的所有状态的集合
5.能观察到外在表现的结合


Hidden 说明的是状态的不可见性;Markov说明的是状态和状态间是markov chain。这就是为什么叫Hidden Markov Model。

我相信你们再去看其它答案里写的就明白多了。

ps:懂了是什么之后再去看paper就好多了。没记错的话去,看《A tutorial on Hidden Markov Models and selected applications in Speech recognition》。另外,HMM除了上文提到的“五要素”,还有“三个基本问题”。这文章将hmm的三个基本问题讲得很清楚。

其它扯淡回答:
如何通俗易懂地介绍Gaussian Process? - 知乎用户的回答
什么是狄利克雷分布?狄利克雷过程又是什么? - 知乎用户的回答