《如何用简单易懂的例子解释隐马尔可夫模型(45页).doc》由会员分享，可在线阅读，更多相关《如何用简单易懂的例子解释隐马尔可夫模型(45页).doc（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-如何用简单易懂的例子解释隐马尔可夫模型-第 44 页如何用简单易懂的例子解释隐马尔可夫模型？ - 知乎隐马尔可夫（HMM）好讲，简单易懂不好讲。我想说个更通俗易懂的例子。我希望我的读者是对这个问题感兴趣的入门者，所以我会多阐述数学思想，少写公式。霍金曾经说过，你多写一个公式，就会少一半的读者。还是用最经典的例子，掷骰子。假设我手里有三个不同的骰子。第一个骰子是我们平常见的骰子（称这个骰子为D6），6个面，每个面（1，2，3，4，5，6）出现的概率是1/6。第二个骰子是个四面体（称这个骰子为D4），每个面（1，2，3，4）出现的概率是1/4。第三个骰子有八个面（称这个骰子为D8），每个面（1，
2、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
3、 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 probabilit
4、y）。就我们的例子来说，六面骰（D6）产生1的输出概率是1/6。产生2，3，4，5，6的概率也都是1/6。我们同样可以对输出概率进行其他定义。比如，我有一个被赌场动过手脚的六面骰子，掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。其实对于HMM来说，如果提前知道所有隐含状态之间的转换概率和所有隐含状态到所有可见状态之间的输出概率，做模拟是相当容易的。但是应用HMM模型时候呢，往往是缺失了一部分信息的，有时候你知道骰子有几种，每种骰子是什么，但是不知道掷出来的骰子序列；有时候你只是看到了很多次掷骰子的结果，剩下的什么都不知道。如果应用算法去估计这些缺失的信息，就成了一
5、个很重要的问题。这些算法我会在下面详细讲。如果你只想看一个简单易懂的例子，就不需要往下看了。说两句废话，答主认为呢，要了解一个算法，要做到以下两点：会其意，知其形。答主回答的，其实主要是第一点。但是这一点呢，恰恰是最重要，而且很多书上不会讲的。正如你在追一个姑娘，姑娘对你说“你什么都没做错！”你要是只看姑娘的表达形式呢，认为自己什么都没做错，显然就理解错了。你要理会姑娘的意思，“你赶紧给我道歉！”这样当你看到对应的表达形式呢，赶紧认错，跪地求饶就对了。数学也是一样，你要是不理解意思，光看公式，往往一头雾水。不过呢，数学的表达顶多也就是晦涩了点，姑娘的表达呢，有的时候就完全和本意相反。所以答主一
6、直认为理解姑娘比理解数学难多了。回到正题，和HMM模型相关的算法主要分为三类，分别解决三种问题：1）知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道每次掷出来的都是哪种骰子（隐含状态链）。这个问题呢，在语音识别领域呢，叫做解码问题。这个问题其实有两种解法，会给出两个不同的答案。每个答案都对，只不过这些答案的意义不一样。第一种解法求最大似然状态路径，说通俗点呢，就是我求一串骰子序列，这串骰子序列产生观测结果的概率最大。第二种解法呢，就不是求一组骰子序列了，而是求每次掷出的骰子分别是某种骰子的概率。比如说我看到结果后，我可以求得第一次掷骰子是
7、D4的概率是0.5，D6的概率是0.3，D8的概率是0.2.第一种解法我会在下面说到，但是第二种解法我就不写在这里了，如果大家有兴趣，我们另开一个问题继续写吧。2）还是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道掷出这个结果的概率。看似这个问题意义不大，因为你掷出来的结果很多时候都对应了一个比较大的概率。问这个问题的目的呢，其实是检测观察到的结果和已知的模型是否吻合。如果很多次结果都对应了比较小的概率，那么就说明我们已知的模型很有可能是错的，有人偷偷把我们的骰子給换了。3）知道骰子有几种（隐含状态数量），不知道每种骰子是什么（转换概率
8、），观测到很多次掷骰子的结果（可见状态链），我想反推出每种骰子是什么（转换概率）。这个问题很重要，因为这是最常见的情况。很多时候我们只有可见结果，不知道HMM模型里的参数，我们需要从可见结果估计出这些参数，这是建模的一个必要步骤。问题阐述完了，下面就开始说解法。（0号问题在上面没有提，只是作为解决上述问题的一个辅助）其实这个问题实用价值不高。由于对下面较难的问题有帮助，所以先在这里提一下。知道骰子有几种，每种骰子是什么，每次掷的都是什么骰子，根据掷骰子掷出的结果，求产生这个结果的概率。解法无非就是概率相乘：1.看见不可见的，破解骰子序列这里我说的是第一种解法，解最大似然路径问题。举例来说，我知
9、道我有三个骰子，六面骰，四面骰，八面骰。我也知道我掷了十次的结果（1 6 3 5 2 7 3 5 2 4），我不知道每次用了那种骰子，我想知道最有可能的骰子序列。其实最简单而暴力的方法就是穷举所有可能的骰子序列，然后依照第零个问题的解法把每个序列对应的概率算出来。然后我们从里面把对应最大概率的序列挑出来就行了。如果马尔可夫链不长，当然可行。如果长的话，穷举的数量太大，就很难完成了。另外一种很有名的算法叫做Viterbi algorithm. 要理解这个算法，我们先看几个简单的列子。首先，如果我们只掷一次骰子：看到结果为1.对应的最大概率骰子序列就是D4，因为D4产生1的概率是1/4，高于1/6
10、和1/8.把这个情况拓展，我们掷两次骰子：结果为1，6.这时问题变得复杂起来，我们要计算三个值，分别是第二个骰子是D6，D4，D8的最大概率。显然，要取到最大概率，第一个骰子必须为D4。这时，第二个骰子取到D6的最大概率是同样的，我们可以计算第二个骰子是D4或D8时的最大概率。我们发现，第二个骰子取到D6的概率最大。而使这个概率最大时，第一个骰子为D4。所以最大概率骰子序列就是D4 D6。继续拓展，我们掷三次骰子：同样，我们计算第三个骰子分别是D6，D4，D8的最大概率。我们再次发现，要取到最大概率，第二个骰子必须为D6。这时，第三个骰子取到D4的最大概率是同上，我们可以计算第三个骰子是D6或
11、D8时的最大概率。我们发现，第三个骰子取到D4的概率最大。而使这个概率最大时，第二个骰子为D6，第一个骰子为D4。所以最大概率骰子序列就是D4 D6 D4。写到这里，大家应该看出点规律了。既然掷骰子一二三次可以算，掷多少次都可以以此类推。我们发现，我们要求最大概率骰子序列时要做这么几件事情。首先，不管序列多长，要从序列长度为1算起，算序列长度为1时取到每个骰子的最大概率。然后，逐渐增加长度，每增加一次长度，重新算一遍在这个长度下最后一个位置取到每个骰子的最大概率。因为上一个长度下的取到每个骰子的最大概率都算过了，重新计算的话其实不难。当我们算到最后一位时，就知道最后一位是哪个骰子的概率最大了。
12、然后，我们要把对应这个最大概率的序列从后往前推出来。2.谁动了我的骰子？比如说你怀疑自己的六面骰被赌场动过手脚了，有可能被换成另一种六面骰，这种六面骰掷出来是1的概率更大，是1/2，掷出来是2，3，4，5，6的概率是1/10。你怎么办么？答案很简单，算一算正常的三个骰子掷出一段序列的概率，再算一算不正常的六面骰和另外两个正常骰子掷出这段序列的概率。如果前者比后者小，你就要小心了。比如说掷骰子的结果是：要算用正常的三个骰子掷出这个结果的概率，其实就是将所有可能情况的概率进行加和计算。同样，简单而暴力的方法就是把穷举所有的骰子序列，还是计算每个骰子序列对应的概率，但是这回，我们不挑最大值了，而是把
13、所有算出来的概率相加，得到的总概率就是我们要求的结果。这个方法依然不能应用于太长的骰子序列（马尔可夫链）。我们会应用一个和前一个问题类似的解法，只不过前一个问题关心的是概率最大值，这个问题关心的是概率之和。解决这个问题的算法叫做前向算法（forward algorithm）。首先，如果我们只掷一次骰子：看到结果为1.产生这个结果的总概率可以按照如下计算，总概率为0.18：把这个情况拓展，我们掷两次骰子：看到结果为1，6.产生这个结果的总概率可以按照如下计算，总概率为0.05：继续拓展，我们掷三次骰子：看到结果为1，6，3.产生这个结果的总概率可以按照如下计算，总概率为0.03：同样的，我们一步
14、一步的算，有多长算多长，再长的马尔可夫链总能算出来的。用同样的方法，也可以算出不正常的六面骰和另外两个正常骰子掷出这段序列的概率，然后我们比较一下这两个概率大小，就能知道你的骰子是不是被人换了。3.掷一串骰子出来，让我猜猜你是谁（答主很懒，还没写，会写一下EM这个号称算法的方法）上述算法呢，其实用到了递归，逆向推导，循环这些方法，我只不过用很直白的语言写出来了。如果你们去看专业书籍呢，会发现更加严谨和专业的描述。毕竟，我只做了会其意，要知其形，还是要看书的。编辑于 2014-11-25173 条评论感谢分享收藏没有帮助举报作者保留权利摘自我的博客1. 赌场风云(背景介绍)最近一个赌场的老板发现
15、生意不畅，于是派出手下去赌场张望。经探子回报，有位大叔在赌场中总能赢到钱，玩得一手好骰子，几乎是战无不胜。而且每次玩骰子的时候周围都有几个保镖站在身边，让人不明就显示全部摘自我的博客1. 赌场风云(背景介绍)最近一个赌场的老板发现生意不畅，于是派出手下去赌场张望。经探子回报，有位大叔在赌场中总能赢到钱，玩得一手好骰子，几乎是战无不胜。而且每次玩骰子的时候周围都有几个保镖站在身边，让人不明就里，只能看到每次开局，骰子飞出，沉稳落地。老板根据多年的经验，推测这位不善之客使用的正是江湖失传多年的偷换骰子大法”(编者注:偷换骰子大法，用兜里自带的骰子偷偷换掉均匀的骰子)。老板是个冷静的人，看这位大叔也
16、不是善者，不想轻易得罪他，又不想让他坏了规矩。正愁上心头，这时候进来一位名叫HMM帅哥，告诉老板他有一个很好的解决方案。不用近其身，只要在远处装个摄像头，把每局的骰子的点数都记录下来。然后HMM帅哥将会运用其强大的数学内力，用这些数据推导出1. 该大叔是不是在出千?2. 如果是在出千，那么他用了几个作弊的骰子?还有当前是不是在用作弊的骰子。3. 这几个作弊骰子出现各点的概率是多少?天呐，老板一听，这位叫HMM的甚至都不用近身，就能算出是不是在作弊，甚至都能算出别人作弊的骰子是什么样的。那么，只要再当他作弊时，派人围捕他，当场验证骰子就能让他哑口无言。2. HMM是何许人也?在让HMM开展调查活
17、动之前，该赌场老板也对HMM作了一番调查。HMM(Hidden Markov Model), 也称隐性马尔可夫模型，是一个概率模型，用来描述一个系统隐性状态的转移和隐性状态的表现概率。系统的隐性状态指的就是一些外界不便观察(或观察不到)的状态, 比如在当前的例子里面, 系统的状态指的是大叔使用骰子的状态，即正常骰子, 作弊骰子1, 作弊骰子2,.隐性状态的表现也就是, 可以观察到的，由隐性状态产生的外在表现特点。这里就是说, 骰子掷出的点数.1,2,3,4,5,6HMM模型将会描述，系统隐性状态的转移概率。也就是大叔切换骰子的概率,下图是一个例子，这时候大叔切换骰子的可能性被描述得淋漓尽致。很
18、幸运的，这么复杂的概率转移图，竟然能用简单的矩阵表达, 其中a_ij代表的是从i状态到j状态发生的概率当然同时也会有，隐性状态表现转移概率。也就是骰子出现各点的概率分布, (e.g. 作弊骰子1能有90%的机会掷到六，作弊骰子2有85%的机会掷到小). 给个图如下,隐性状态的表现分布概率也可以用矩阵表示出来，把这两个东西总结起来，就是整个HMM模型。这个模型描述了隐性状态的转换的概率，同时也描述了每个状态外在表现的概率的分布。总之，HMM模型就能够描述扔骰子大叔作弊的频率(骰子更换的概率)，和大叔用的骰子的概率分布。有了大叔的HMM模型，就能把大叔看透，让他完全在阳光下现形。3. HMM能干什
19、么!总结起来HMM能处理三个问题，3.1 解码(Decoding)解码就是需要从一连串的骰子中，看出来哪一些骰子是用了作弊的骰子，哪些是用的正常的骰子。比如上图中，给出一串骰子序列(3,6,1,2.)和大叔的HMM模型, 我们想要计算哪一些骰子的结果(隐性状态表现)可能对是哪种骰子的结果(隐性状态).3.2学习(Learning)学习就是，从一连串的骰子中，学习到大叔切换骰子的概率，当然也有这些骰子的点数的分布概率。这是HMM最为恐怖也最为复杂的招数！3.3 估计(Evaluation)估计说的是，在我们已经知道了该大叔的HMM模型的情况下，估测某串骰子出现的可能性概率。比如说，在我们已经知道
20、大叔的HMM模型的情况下，我们就能直接估测到大叔扔到10个6或者8个1的概率。4. HMM是怎么做到的?4.1 估计估计是最容易的一招，在完全知道了大叔的HMM模型的情况下，我们很容易就能对其做出估计。现在我们有了大叔的状态转移概率矩阵A,B就能够进行估计。比如我们想知道这位大叔下一局连续掷出10个6的概率是多少? 如下这表示的是，在一开始隐性状态(s0)为1，也就是一开始拿着的是正常的骰子的情况下，这位大叔连续掷出10个6的概率。现在问题难就难在，我们虽然知道了HMM的转换概率，和观察到的状态V1:T, 但是我们却不知道实际的隐性的状态变化。好吧，我们不知道隐性状态的变化，那好吧，我们就先假
21、设一个隐性状态序列, 假设大叔前5个用的是正常骰子, 后5个用的是作弊骰子1.好了，那么我们可以计算，在这种隐性序列假设下掷出10个6的概率.这个概率其实就是，隐性状态表现概率B的乘积.但是问题又出现了，刚才那个隐性状态序列是我假设的，而实际的序列我不知道，这该怎么办。好办，把所有可能出现的隐状态序列组合全都试一遍就可以了。于是,R就是所有可能的隐性状态序列的集合。的嗯，现在问题好像解决了，我们已经能够通过尝试所有组合来获得出现的概率值，并且可以通过A,B矩阵来计算出现的总概率。但是问题又出现了，可能的集合太大了, 比如有三种骰子，有10次选择机会, 那么总共的组合会有310次.这个量级O(c
22、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是H
23、MM状态转移概率矩阵)(公式太多，请具体看我博客中的推导机器学习 - 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面),计算出最有可能的模型参数.(公式太多，请具体看我博客中的推导机器学习 -
24、4. 大内密探HMM(隐马尔可夫)围捕赌场老千)5. HMM 的应用以上举的例子是用HMM对掷骰子进行建模与分析。当然还有很多HMM经典的应用，能根据不同的应用需求，对问题进行建模。但是使用HMM进行建模的问题，必须满足以下条件,1.隐性状态的转移必须满足马尔可夫性。(状态转移的马尔可夫性:一个状态只与前一个状态有关)2. 隐性状态必须能够大概被估计。在满足条件的情况下,确定问题中的隐性状态是什么,隐性状态的表现可能又有哪些.HMM适用于的问题在于，真正的状态(隐态)难以被估计，而状态与状态之间又存在联系。5.1 语音识别语音识别问题就是将一段语音信号转换为文字序列的过程. 在个问题里面隐性状
25、态就是: 语音信号对应的文字序列而显性的状态就是: 语音信号.HMM模型的学习(Learning): 语音识别的模型学习和上文中通过观察骰子序列建立起一个最有可能的模型不同.语音识别的HMM模型学习有两个步骤:1. 统计文字的发音概率,建立隐性表现概率矩阵2. 统计字词之间的转换概率(这个步骤并不需要考虑到语音,可以直接统计字词之间的转移概率即可)语音模型的估计(Evaluation): 计算是十四”,四十四等等的概率,比较得出最有可能出现的文字序列.5.2 手写识别这是一个和语音差不多,只不过手写识别的过程是将字的图像当成了显性序列.5.3 中文分词“总所周知，在汉语中，词与词之间不存在分隔
26、符（英文中，词与词之间用空格分隔，这是天然的分词标记），词本身也缺乏明显的形态标记，因此，中文信息处理的特有问题就是如何将汉语的字串分割为合理的词语序。例如，英文句子：you should go to kindergarten now 天然的空格已然将词分好，只需要去除其中的介词“to”即可；而“你现在应该去幼儿园了”这句表达同样意思的话没有明显的分隔符，中文分词的目的是，得到“你/现在/应该/去/幼儿园/了”。那么如何进行分词呢？主流的方法有三种：第1类是基于语言学知识的规则方法，如：各种形态的最大匹配、最少切分方法；第2类是基于大规模语料库的机器学习方法，这是目前应用比较广泛、效果较好的解
27、决方案用到的统计模型有N元语言模型、信道噪声模型、最大期望、HMM等。第3类也是实际的分词系统中用到的，即规则与统计等多类方法的综合。”1使用HMM进行中文分词.5.4 HMM实现拼音输入法拼音输入法,是一个估测拼音字母对应想要输入的文字(隐性状态)的过程(比如, pingyin - 拼音)使用HMM实现简单拼音输入法楼上的大神都说得很好了，我来补充一个有意思HMM的用法，是用来给定钢琴谱，自动决定指法的用法。这个HMM的应用是来自于東京大学（東大真是所神奇的学校）的一个研究组在IJCAI 2007年的一篇文章，日文版的标题是隠基運指自显示全部楼上的大神都说得很好了，我来补充一个有意思HMM的
28、用法，是用来给定钢琴谱，自动决定指法的用法。这个HMM的应用是来自于東京大学（東大真是所神奇的学校）的一个研究组在IJCAI 2007年的一篇文章，日文版的标题是隠基運指自動決定，英文版的标题是Automatic Determination of Piano Fingering based on Hidden Markov Model，论文的网页在这里：Sagayama & Ono Lab。从网页可以知道，这篇文中的工作其实至少从2005年就开始了。愚以为在我目前能做到的范围内最好的学习一篇论文并让其对自己有用的方法就是重现之，所以此答案也按照现在回看当时重现过程的过程的顺序写。对于这个问题，
29、我觉得比较重要的一点是“如何将HMM模型套用到这个问题上”，什么是HMM中的“因”，什么是HMM中的“果”，这个HMM在解决与琴键指法有关的问题是如何对应到HMM的三大任务=Scoring, Matching, Training的。然后你就很容易知道问题的输入是什么、输出是什么，然后将其转化为一个用程序员思维能解决的问题。所以就开始俺们的钢琴运指自动决定之旅吧：为了先有一个印象并明确问题的背景和定义，先看开门见山的介绍图：这个图的意思是说，“你有一个HMM模型，往里面丢入琴谱，它就能给你输出指法。”这图，首先大致说明了这个HMM里面有哪些变量：HMM中的“Hidden State（隐藏状态）”
30、的是右手的五个手指编号（1=大拇指，2=食指，3=中指，4=无名指，5=小指）。HMM的“Emission（可见输出状态链）”是“所弹奏出来的音符”。在这篇论文的问题描述中，“弹奏的音符”是知道的，“所用的指法”是不知道的。因为不知道，所以就需要用算法去算出来。所以这里和事实上的过程其实是反过来的：在此论文中，“指法”是原因，“音符”是结果，“事情发生”就是“指法导致了弹奏出这些音符”；这个过程在英文版论文中称为“fingering-to-performance conversion”，与事情看起来发生的顺序是相反的（一个人是先看到琴谱，然后才有指法的，这种现实中的发生顺序来说的过程在英文版论
31、文中称为“score-to-fingering conversion”）。此论文中的概率用贝叶斯术语的名字来说就是：P(指法)是先验概率（Prior Probability事前確率）、P(音符|指法)是似然度（Likelihood尤度関数）、P(音符，指法)是联合概率（Joint Probability結合確率）、P(音符)是边缘概率（Marginal Probability周辺確率）、P(指法|音符)是后验概率（Posterior Probability事後確率）。【通过改变指法来最大化这个概率的过程，就是MAP，即Maximum A-Posteriori过程，即是Viterbi Searc
32、h法做的事情。】然后，它说明了这个HMM的性质：这个HMM是一个“Mealy Machine”，因为它是在转换的过程中输出的，而不是当处于某个状态时输出的（在某个状态输出，就应是Moore Machine）。“Mealy Machine”的输出概率函数是关于边的起始结点和终止结点的函数。所以，图右方的“High probability emission”意思是，“当我先用右手无名指弹奏了#F之后，再用右手小指弹奏#F右边的G的概率比较高”；图右下角的“Low probability emission”的意思是，“当我先用右手的无名指弹奏了G之后，再用右手小指弹奏G左边的#F的概率比较低”。也就
33、是说，输出某个音符的概率可以写成，用语言解释就是“在我现在用第f_i-1个手指弹奏y_i-1这个音时，我接下来要用第f_i个手指奏y_i这个音的概率”。1至于状态转换概率则是不分Moore Machine和Mealy Machine的，都是，也就是当前用了某个手指之后，会转而使用下一个手指的概率。这个概率表可以用来对某些现象进行建模，譬如说：“中指和无名指连续交替按键很不灵活”，就可以通过使得赋给与更低的值来达成。有了这些定义，我们就能知道如何完成HMM中的三个任务：Scoring：给定一个指法，通过打分看它好弹还是不好弹。输入是指法，输出是分数。Matching：给定一个琴谱，给出最好的指法
34、。输入是琴谱，输出是指法。Training：给定琴谱和指法组成的测试用例，通过改变HMM中的参数，来使得这个HMM能“学习”到测试用例中潜藏的规则。首先是Scoring，就是这个HMM是如何计算某个指法安排出现的概率的，以上面的图为例：图中的红箭头经过的结点表示状态转换，也就是“5、2、3、1、4、2、1”。在处于某个状态时，所进行的状态转换只依赖于当前的状态是什么。红箭头经过的边表示所输出的可见状态，也就是右上角的音符：E5, B4, C5, A4, B4, #G4, E。除了第一个音符以外，其它的音符都是按照上面的输出概率公式计算的。比如说用此指法弹奏第二个B4的条件概率就是。这就是“给定
35、一个指法和所弹奏的音符，计算出它被弹奏出来的概率是多少”的过程。如果只给定音符，再罗列出所有可能的指法，就能从中计算出概率最大的指法。但是直接罗列速度会慢，所以可以用Viterbi Search来更快地计算出来。那么就来到了第二点，Matching，就是给定一个谱子后，如何知道在当前的HMM中，最好的指法是什么？这是计算最大后验概率 P(指法|音符) 的问题。如前所述这其实是一个通过动态规划来达到比枚举高效很多的编程问题，其基本的样子是从给定的谱子的第一个音符开始，一直往后走，在每一步都保存“弹到当前的音符时最好的指法是什么”的信息供下一步使用，省掉计算时间的。此算法称为Viterbi Sea
36、rch（Viterbi algorithm），它所搜索的空间可称为Trellis Graph （Trellis (graph)）。因为维基百科上的Viterbi算法的Python代码是可以直接拷贝下来运行的，为了有所不同，以下就以图中的片段来举个例子，运行一遍论文中所述的演算法（这里强制第一个音符必须用5指，所以开始概率是设成了0.01, 0.01, 0.01, 0.01, 1.00）：图中t表示输出状态链的“时间”，也就是音符的下标，从0开始。当t=0的时候弹奏的概率就是开始概率。t0时弹奏的概率就涉及输出概率与转换概率。以下和论文中一样，只考虑只用右手、只有单音（没有和弦）的情况。t=0,
37、 1时的概率，就表示弹奏前两个音符所用的各种指法的概率。图中的网状图就是一个Trellis graph，每条边对应一次HMM状态转换同时也对应着（在t0时的）弹出一个音符的动作；每个结点对应着一个手指，也就是能够用以弹奏某个音的某个手指。每条有颜色的路径就表示某个片段中的指法安排。Viterbi算法是一种动态规划，所以它在每一步时都需要把“对于每个手指，从开始到这一步时，这一步必用这个手指的最高的概率和对应的指法”存在动态规划表里，以供下一步的计算使用。从这个图所反映的动态规划表中可以看出，用右手小拇指弹第一个音E5，然后再用右手食指弹第二个音B4的概率是所有25种可能中概率最高的，其概率高达
38、10(-2.31009)。这个概率并没有什么实际意义，只在对所有指法间进行比较有意义。相比起来，用右手大拇指弹奏第一个音E5再用右手小拇指弹奏第二个音B4的概率就低多了，只有10(-13.0603)，这是个穿指的动作，而穿指从大拇指穿到小拇指也比从食指、中指和无名指穿到小指要简单，所以指向t=1时的5的箭头是从1指向5的。这是Viterbi算法在构建动态规划表中的规则。这个表的内容会用到t=0,1,2的情况，如下：指的就是此图在t=0,1中的箭头都是在上一张中出现过的箭头的意思。再继续一步：将这个过程重复到最后，就得到了这一段谱子的指法：在这张动态规划表中，概率最大的是5231421这个指法，
39、也就是图中所示的。以上就是这篇论文中所描述的“用HMM来计算给定的一段乐谱的最佳指法”的方法。最后，就是Training阶段如何通过训练HMM参数的方法来“学到”测试用例呢？在实现此论文的过程中我对于具体计算输出概率的方法是用了一些猜测的，所以与原文可能有所不符，所以将论文中所出现的7个乐谱片段输入后，有3、4个音符的指法与文中提及的结果不同。所以我想通过调整参数的方法让我的HMM的输出结果能与论文中相符。说是Bonus阶段是，因为论文中没有明示这一阶段是如何做的，但是有提及根据常理是可以把这个训练过程做成的。这回用于训练用的是随机梯度下降法（Stochastic gradient desce
40、nt），这种方法可以用于参数都是连续变量、目标函数也是连续变量的模型。其最基本的更新规则是，其中w是参数，alpha是学习速率，p是Viterbi算法算出的最佳指法与训练用例指法的分数之差，当梯度下降完成时，训练用例中的指法就会变成所有指法中最优的并被Viterbi找到，也就是p会等于0 。训练过程中给HMM模型不停地出示正确的指法就像是不停背诵英语单词强化记忆一样。以下示出用论文中出现的7个片段用作训练的样子。训练中能修正的HMM参数有以下这些：转换概率（25个）五个手指与黑白键的接触点的Y轴坐标（10个）一共是35个可以调整的参数。在训练前，我们猜测出来的参数做成的HMM输出的指法能够符合
41、这7个训练用例中的5个（以下为论文中的谱子的截图，黑色的圈是在论文中用作指法合理性的讨论的，和此回需要进行的重现算法的任务没有关系）：可以看到图中有两处红字是我们当前的HMM输出的指法与训练用例的指法不同之处。现在将这七个片段放入Stochastic Descent过程中，随着其进行，可以将参数的变化和目标函数的变化画在下图中：三栏中，最上栏是分数之差，也就是对每个训练用例，给定的训练指法与当前最好的指法的分数之差，为0表示给定的训练指法就是最佳指法。中间栏是转换概率。最下栏是10个接触点的Y轴坐标。可以看到分数之差随着训练的进行总体上的趋势是在接近0。当训练完成后，这个HMM就能复制出图中所
42、示的7个片段中的指法啦！O如果再展开还有许多问题：对于Stochastic Descent还可以通过自动调整学习速率的方法来加快计算；训练过程不一定是Consistent的，意即总会到某个时候不可能完全复制出训练用例中的指法；和弦和双手两个声部的处理，但是这些就是不同于此问题的另一问题了，而且我也不是非常理解，所以就不在这里写啦。1：在重现这篇论文的结果时我们认为尽管原论文并没有说，但是y_i-1还是有必要出现在竖线的右边的。按我们的理解，原文并非是完全没有说，而是隐含地用了y_i-1来得到计算输出概率时高斯分布的中心点的位置。 (手机码字，继续欠修改)WARNING：这篇文章是给零基础人士看
43、的。目标是让普通初中生以及只有初中基础人士无障碍理解HMM框架。追求数学严谨性人士、追求用简洁符号表达模型的同学以及数理基础良好的大神请自行移步参阅文献。讲这种东西就得先搞清HMM到底干了显示全部(手机码字，继续欠修改)WARNING：这篇文章是给零基础人士看的。目标是让普通初中生以及只有初中基础人士无障碍理解HMM框架。追求数学严谨性人士、追求用简洁符号表达模型的同学以及数理基础良好的大神请自行移步参阅文献。讲这种东西就得先搞清HMM到底干了什么，初学者很容易对“模型在干嘛”这个问题上犯晕。我个人特别讨厌跟初学者上来就讲state space/transition matrix/emissi
44、on probability云云的讲法(注：比如统计学习方法李航博士那种讲法。虽然用来准备面试很方便，但初学者肯定会被符号和几个概念绕晕了；另外，私以为他换掉符号和前人文献不保持一致的做法又会让初学者又多了一道坎去翻。总之，不太厚道)。因为初学时，对大多非理科出身的人而言，用抽象的名词与符号描述的“语言系统”还没固化在脑袋里。用抽象符号在那儿讲就好比“一群人还没学会走，就逼着他们快点跑”。这是不太现实的。综上，用复杂抽象的语言描述不合适的，这个学习曲线过于陡峭，别人需要时间消化。基于此原因，我发现，对零基础小伙伴们用游戏的例子去类比地解释往往比较容易降低学习难度，比如这样讲:我是一战士，修炼出
45、了三种战斗形态，分别为暴怒态，正常状态和防御态。同时我也会三个被动技能，分别是普通平A，爆击(攻击伤害翻倍)，吸血(生命汲取)。我在暴怒状态下打出暴击的概率是80%,打出吸血概率为5%；在平衡形态下，打出暴击的比率为30%，打出吸血的概率是20%；在防御形态下，暴击成功概率为5%，吸血概率为60%。总结一下，战士在不同状态下能打出技能的概率不一样。本来，战士这个职业在暴怒态时，身边会有一圈红光环；防御态时，会有一圈蓝光环。但是，现在我正在玩游戏，游戏突然出了个bug：有个傻x程序员改了游戏的代码，他给写崩了，从此战士身边光环都看不见了。那我没法通过看脚下的光环知道战士在爆什么状态了。话说，现在
46、问题来了：由于看不到脚下光环，我只能估计“战士”在爆什么状态；但我现在打一boss，砍10次，发现8次都是暴击，血哗哗地翻倍在掉，你觉得我这战士最可能是爆了什么状态？(每次用这个不规范的例子和新手讲，他们立刻就懂了；而且他们接下来还会问：暴怒状态不能总持续吧？这不科学，应该限定个一段时间后，暴怒状态消失的概率为50%.你瞧瞧连状态转换的transition prob自己都能假设出来了，都会抢答了都lol.“HMM的在干什么”的问题很容易地让他们就理解了)综上，一个战士的状态会不断随时间变化；然后他的被动技能发动概率会因为所处不同状态而不同。这就是HMM想表达的东西。并且我们还可以通过它回答一些有趣的问题：通过战士发动的技能来推测战士所出的状态。这个例子只是个感性认识，它其实只是告诉了我们hmm比较“像什么东西”。显然，我们还需要更规范更严谨地去介绍什么是HMM，去规范化这个模型。这个例子里的“战士”可以换成其它答案里的天气，换成硬币等等。但无论用什么说法，我们已经能通过这个例子抓住核心问题了：HMM模型就是这样一个系统它有一个能不断改变的隐藏的状态（在这个例子里就是战士爆的状态。它会变，而且由于一个码农的缘故，状态变得不可见）在持