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

pgl147258 2014-11-20

展开全文

【YangEninala的回答(227票)】:

隐马尔可夫（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中说到的马尔可夫链其实是指隐含量链，因为隐含量（骰子）之间存在转换概率的。在我们这个例子里，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的emission probability是1/6。产生2，3，4，5，6的概率也都是1/6。我们同样可以对emission probability进行其他定义。比如，我有一个被赌场动过手脚的六面骰子，掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。

其实对于HMM来说，如果提前知道转换概率矩阵（包括所有的转换概率）和emission probability matrix(包含所有的emission probability)，做模拟是相当容易的。但是HMM的用途则一般是，我知道结果（多串可见量链），怎么返回去寻找转换概率和emission probability。这时要用到forward algorithm和backward algorithm。如果大家感兴趣，我可以接着讲。

【庞雨秾的回答(206票)】:

摘自我的博客http://blog.csdn.net/ppn029012

1. 赌场风云(背景介绍)

最近一个赌场的老板发现生意不畅，于是派出手下去赌场张望。经探子回报，有位大叔在赌场中总能赢到钱，玩得一手好骰子，几乎是战无不胜。而且每次玩骰子的时候周围都有几个保镖站在身边，让人不明就里，只能看到每次开局，骰子飞出，沉稳落地。老板根据多年的经验，推测这位不善之客使用的正是江湖失传多年的"偷换骰子大法”(编者注:偷换骰子大法，用兜里自带的骰子偷偷换掉均匀的骰子)。老板是个冷静的人，看这位大叔也不是善者，不想轻易得罪他，又不想让他坏了规矩。正愁上心头，这时候进来一位名叫HMM帅哥，告诉老板他有一个很好的解决方案。

不用近其身，只要在远处装个摄像头，把每局的骰子的点数都记录下来。

然后HMM帅哥将会运用其强大的数学内力，用这些数据推导出

1. 该大叔是不是在出千?

2. 如果是在出千，那么他用了几个作弊的骰子? 还有当前是不是在用作弊的骰子。

3. 这几个作弊骰子出现各点的概率是多少?

天呐，老板一听，这位叫HMM的甚至都不用近身，就能算出是不是在作弊，甚至都能算出别人作弊的骰子是什么样的。那么，只要再当他作弊时，派人围捕他，当场验证骰子就能让他哑口无言。

2. HMM是何许人也?

在让HMM开展调查活动之前，该赌场老板也对HMM作了一番调查。

HMM(Hidden Markov Model), 也称隐性马尔可夫模型，是一个概率模型，用来描述一个系统隐性状态的转移和隐性状态的表现概率。

系统的隐性状态指的就是一些外界不便观察(或观察不到)的状态, 比如在当前的例子里面, 系统的状态指的是大叔使用骰子的状态，即

{正常骰子, 作弊骰子1, 作弊骰子2,...}

隐性状态的表现也就是, 可以观察到的，由隐性状态产生的外在表现特点。这里就是说, 骰子掷出的点数.

{1,2,3,4,5,6}

HMM模型将会描述，系统隐性状态的转移概率。也就是大叔切换骰子的概率,下图是一个例子，这时候大叔切换骰子的可能性被描述得淋漓尽致。

很幸运的，这么复杂的概率转移图，竟然能用简单的矩阵表达, 其中a_{ij}代表的是从i状态到j状态发生的概率

当然同时也会有，隐性状态表现转移概率。也就是骰子出现各点的概率分布, (e.g. 作弊骰子1能有90%的机会掷到六，作弊骰子2有85%的机会掷到'小’). 给个图如下,

隐性状态的表现分布概率也可以用矩阵表示出来，

把这两个东西总结起来，就是整个HMM模型。

这个模型描述了隐性状态的转换的概率，同时也描述了每个状态外在表现的概率的分布。总之，HMM模型就能够描述扔骰子大叔作弊的频率(骰子更换的概率)，和大叔用的骰子的概率分布。有了大叔的HMM模型，就能把大叔看透，让他完全在阳光下现形。

3. HMM能干什么!

总结起来HMM能处理三个问题，3.1 解码(Decoding)

解码就是需要从一连串的骰子中，看出来哪一些骰子是用了作弊的骰子，哪些是用的正常的骰子。

比如上图中，给出一串骰子序列(3,6,1,2..)和大叔的HMM模型, 我们想要计算哪一些骰子的结果(隐性状态表现)可能对是哪种骰子的结果(隐性状态).

3.2学习(Learning)

学习就是，从一连串的骰子中，学习到大叔切换骰子的概率，当然也有这些骰子的点数的分布概率。这是HMM最为恐怖也最为复杂的招数！！3.3 估计(Evaluation)

估计说的是，在我们已经知道了该大叔的HMM模型的情况下，估测某串骰子出现的可能性概率。比如说，在我们已经知道大叔的HMM模型的情况下，我们就能直接估测到大叔扔到10个6或者8个1的概率。

4. HMM是怎么做到的?

4.1 估计

估计是最容易的一招，在完全知道了大叔的HMM模型的情况下，我们很容易就能对其做出估计。

现在我们有了大叔的状态转移概率矩阵A,B就能够进行估计。比如我们想知道这位大叔下一局连续掷出10个6的概率是多少? 如下

这表示的是，在一开始隐性状态(s0)为1，也就是一开始拿着的是正常的骰子的情况下，这位大叔连续掷出10个6的概率。

现在问题难就难在，我们虽然知道了HMM的转换概率，和观察到的状态V{1:T}, 但是我们却不知道实际的隐性的状态变化。

好吧，我们不知道隐性状态的变化，那好吧，我们就先假设一个隐性状态序列, 假设大叔前5个用的是正常骰子, 后5个用的是作弊骰子1.

好了，那么我们可以计算，在这种隐性序列假设下掷出10个6的概率.

这个概率其实就是，隐性状态表现概率B的乘积.

但是问题又出现了，刚才那个隐性状态序列是我假设的，而实际的序列我不知道，这该怎么办。好办，把所有可能出现的隐状态序列组合全都试一遍就可以了。于是,

R就是所有可能的隐性状态序列的集合。的嗯，现在问题好像解决了，我们已经能够通过尝试所有组合来获得出现的概率值，并且可以通过A,B矩阵来计算出现的总概率。

但是问题又出现了，可能的集合太大了, 比如有三种骰子，有10次选择机会, 那么总共的组合会有3^10次...这个量级O(c^T)太大了，当问题再大一点时候，组合的数目就会大得超出了计算的可能。所以我们需要一种更有效的计算P(V(1:T)概率的方法。

比如说如下图的算法可以将计算P(V1:T)的计算复杂度降低至O(cT).

有了这个方程，我们就能从t=0的情况往前推导，一直推导出P(V1:T)的概率。下面让我们算一算，大叔掷出3,2,1这个骰子序列的可能性有多大(假设初始状态为1, 也就是大叔前一次拿着的是正常的骰子)?

4.2 解码(Decoding)

解码的过程就是在给出一串序列的情况下和已知HMM模型的情况下，找到最可能的隐性状态序列。

用数学公式表示就是, (V是Visible可见序列, w是隐性状态序列, A,B是HMM状态转移概率矩阵)(公式太多，请具体看我博客中的推导机器学习 --- 4. 大内密探HMM(隐马尔可夫)围捕赌场老千)

然后又可以使用估计(4.1)中的前向推导法，计算出最大的P(w(1:T), V(1:T)).

在完成前向推导法之后，再使用后向追踪法(Back Tracking)，对求解出能令这个P(w(1:T), V(1:T))最大的隐性序列.这个算法被称为维特比算法(Viterbi Algorithm).

4.3 学习(Learning)

学习是在给出HMM的结构的情况下(比如说假设已经知道该大叔有3只骰子，每只骰子有6面),计算出最有可能的模型参数.(公式太多，请具体看我博客中的推导机器学习 --- 4. 大内密探HMM(隐马尔可夫)围捕赌场老千)

5. HMM 的应用

以上举的例子是用HMM对掷骰子进行建模与分析。当然还有很多HMM经典的应用，能根据不同的应用需求，对问题进行建模。

但是使用HMM进行建模的问题，必须满足以下条件,

1.隐性状态的转移必须满足马尔可夫性。(状态转移的马尔可夫性:一个状态只与前一个状态有关)

2. 隐性状态必须能够大概被估计。

在满足条件的情况下,确定问题中的隐性状态是什么,隐性状态的表现可能又有哪些.

HMM适用于的问题在于，真正的状态(隐态)难以被估计，而状态与状态之间又存在联系。

5.1 语音识别

语音识别问题就是将一段语音信号转换为文字序列的过程. 在个问题里面

隐性状态就是: 语音信号对应的文字序列

而显性的状态就是: 语音信号.

HMM模型的学习(Learning): 语音识别的模型学习和上文中通过观察骰子序列建立起一个最有可能的模型不同. 语音识别的HMM模型学习有两个步骤:

1. 统计文字的发音概率,建立隐性表现概率矩阵Ｂ

2. 统计字词之间的转换概率(这个步骤并不需要考虑到语音,可以直接统计字词之间的转移概率即可)

语音模型的估计(Evaluation): 计算"是十四”,"四十四"等等的概率,比较得出最有可能出现的文字序列.

5.2 手写识别

这是一个和语音差不多,只不过手写识别的过程是将字的图像当成了显性序列.

5.3 中文分词

“总所周知，在汉语中，词与词之间不存在分隔符（英文中，词与词之间用空格分隔，这是天然的分词标记），词本身也缺乏明显的形态标记，因此，中文信息处理的特有问题就是如何将汉语的字串分割为合理的词语序。例如，英文句子：you should go to kindergarten now 天然的空格已然将词分好，只需要去除其中的介词“to”即可；而“你现在应该去幼儿园了”这句表达同样意思的话没有明显的分隔符，中文分词的目的是，得到“你/现在/应该/去/幼儿园/了”。那么如何进行分词呢？主流的方法有三种：第1类是基于语言学知识的规则方法，如：各种形态的最大匹配、最少切分方法；第2类是基于大规模语料库的机器学习方法，这是目前应用比较广泛、效果较好的解决方案．用到的统计模型有N元语言模型、信道—噪声模型、最大期望、HMM等。第3类也是实际的分词系统中用到的，即规则与统计等多类方法的综合。”[1]使用HMM进行中文分词.5.4 HMM实现拼音输入法

拼音输入法,是一个估测拼音字母对应想要输入的文字(隐性状态)的过程(比如, ‘pingyin’ -> 拼音)

使用HMM实现简单拼音输入法

参考:

http://ai.stanford.edu/~serafim/CS262_2007/notes/lecture5.pdf

【者也的回答(11票)】:

隐马尔科夫模型（Hidden Markov Model）经常被用在时间序列（例如一段时间内的声音信号，运动物体的位置等你所感兴趣的物理量）的建模与分析。

它有三个要素，

1. 可见随机变量：用来描述你所感兴趣的物理量，随时间变化

2. 隐含的状态变量：一个假设的存在，每个时间点的物理量背后都对应一个状态量

3. 变量间的关系：用概率的方法（通常是概率密度函数）描述以下三个关系或变量：初始状态量，当前的隐含状态量与下一个隐含状态量间关系（此处还用到马尔科夫假设：当前隐含状态只取决于前一个隐含状态），当前的隐含状态量与可见随机量间关系

举例说，我用HMM去描述一组不同类型的手部动作，每个动作有一种特定的模式，例如用手打拍子，2/4拍（上下上），3/4拍（上下右上），4/4拍（上下左右上），现实中，即使重复同样的拍子，手所划过的轨迹还是会有差别，但不同的拍子，其模式完全不同，用HMM去描述一种动作，所对应的可见随机变量就是手的位置，隐含状态变量就是上下左右四个大致位置，变量间关系用你假设的的概率密度函数描述。至于参数估计，推断等技术问题，有成熟高效的算法可以处理，这也是HMM受欢迎的原因。详细内容参考Rabiner的经典论文：An introduction to hidden Markov models。

补充：

1. 隐含状态变量是假设的存在，并不一定有对应的物理解释，此例状态值取上下左右四个值是为了好理解，实现模型时可以取任意数量的状态值，是一个可调参数。

2. 隐含状态变量通常是离散的，可见状态变量可离散可连续。

【婷婷孙的回答(7票)】:

有个黑屋子关了一个小妖怪，并且里面有N个坛子，每个坛子里有M种不同颜色的小球。

小妖怪随意碰到一个坛子，从里面拿出一个小球出来，把小球从窗子递出来，外面能看到小球的颜色。之后把小球放回去，再重复这个过程，就能得到一个序列。

在这个过程中存在两个随机过程，选择坛子和从坛子里选择小球，而中间的状态转移过程是被隐藏的。

其中重要的参数包含：一组状态的集合（不同坛子）；输出符号的集合（不同颜色的小球）；状态转移矩阵（从某个坛子跑到下一个坛子的概率）；输出符号的概率分布（某个坛子抓出某种颜色小球的概率）；初始状态概率分布（随机选择第一个坛子的概率）。

在课上听老师这么讲的……

【刘润涛的回答(2票)】:

讲这种东西就得先搞清HMM到底是啥，怎样运作；我个人特别讨厌跟初学者上来就讲state space/transition matrix/emission matrix云云的讲法，因为那时候大多人抽象的名词的概念还没固化在脑袋里，会说得他们很晕。用复杂抽象的语言描述是不合适的，这是根本不打算让外行人听懂。基于此原因，我之前发现对零基础小伙伴们常常用游戏的例子比较好，比如这样讲:

我是一战士，修炼出了三种战斗形态，分别为暴怒态，平衡态和防御态。同时我也会三个技能，分别是普通平A，爆击(攻击伤害翻倍)，吸血(生命偷取)。

我在暴怒状态下打出暴击的概率是80%,打出吸血概率为5%；

在平衡形态下，打出暴击的比率为30%，打出吸血的概率是20%；

在防御形态下，暴击成功概率为5%，吸血概率为60%。

我现在a你10次，发现8次都是暴击，血翻倍在掉，你觉得我最可能是爆了什么状态？(每次用这个不规范的例子和男生讲，他们立刻就懂了；而且他们接下来还会问："’暴怒状态’不能总持续吧？这不科学，应该限定个暴怒状态消失的概率为50%...."你瞧瞧连状态转换的transition prob自己都能假设出来了，都会抢答了都...HMM的第一个问题很容易地就解决了)

ps:懂了是什么之后再去看paper就好多了。没记错的话去，看Introduction to hidden markov chain with applications。这文章将hmm的三个基本问题讲得很清楚。

【BoonLee的回答(1票)】:

看吴军博士的《数学之美》，里面有简单的说明。然后看下HMM的三个计算问题和对应的解答，基本就是动态规划的思想。

【songwang的回答(0票)】:

维基百科上的例子——通过朋友的行为去预测当地天气的变化

英文网址：Hidden Markov model

中文网址：隐马尔可夫模型

其实 Hagnesta 已在题目的评论里提到了。

【王宇的回答(0票)】:

你有两枚硬币：一枚叫A，head的几率是0.5，另一枚叫B，head的几率是0.7，接下来denote head为H， tail为T。

假设我们知道第一次投掷时用的是硬币A，这就叫最initial state。每下一轮投掷之前，硬币都有可能被从A换成B，或者从B换成A，也有可能不变，有个傻B说：“这就叫最transition probability吧”。

好，在这种情况下，你观察到硬币在10次flip 中出现了如下pattern：HTHTTTTHHT