您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
如何用简单易懂的例子隐马尔可夫模型研讨.docx 48页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：350 &&
你可能关注的文档：
··········
··········
如何用简单易懂的例子解释隐马尔可夫模型？-知乎?隐马尔可夫（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次）：这串数字叫做可见状态链。但是在隐马尔可夫模型中，我们不仅仅有这么一串可见状态链，还有一串隐含状态链。在这个例子里，这串隐含状态链就是你用的骰子的序列。比如，隐含状态链有可能是：D6D8D8D6D4D8D6D6D4D8一般来说，HMM中说到的马尔可夫链其实是指隐含状态链，因为隐含状态（骰子）之间存在转换概率（transitionprobability）。在我们这个例子里，D6的下一个状态是D4，D6，D8的概率都是1/3。D4，D8的下一个状态是D4，D6，D8的转换概率也都一样是1/3。这样设定是为了最开始容易说清楚，但是我们其实是可以随意设定转换概率的。比如，我们可以这样定义，D6后面不能接D4，D6后面是D6的概率是0.9，是D8的概率是0.1。这样就是一个新的HMM。同样的，尽管可见状态之间没有转换概率，但是隐含状态和可见状态之间有一个概率叫做输出概率（emissionprobability）。就我们的例子来说，六面骰（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）还是知道骰子有几种（隐含状态数量），每种骰子是什么（转换概率），根据掷骰子掷出的结果（可见状态链），我想知道掷出
正在加载中，请稍后...当前位置： >>
隐马尔科夫模型在多序列比对中的应用
隐马尔科夫模型在多序列比对中的应用摘要：序列比对是生物信息学研究中的一个重要的方法, 是生物信息学的基础。随着测序技术及生物信息学的高速发展， 目前已经获得了大量的生物序列和数据结构， 传统研究生物 序列的方法已经无法再满足人们的需求，而隐马尔科夫模型（HMM）也渐渐在生物序列分析 中脱颖而出。 隐马尔科夫模型是一个双重随机过程， 具有一定状态数的隐马尔科
夫链和显示 随机函数集，该模型用于生物序列分析是生物信息学(Bioinformatics) 研究的新领域。本 文主要介绍了 HMM 在多序列比对中的应用。关键词：隐马尔科夫模型（HMM） ；生物信息学；多序列比对 1 生物序列比对的意义及概念序列比对是生物信息学中最基本、 最重要的操作， 通过序列比对可以发现生物序列中的 功能、结构和进化的信息。序列比对的根本任务是：通过比较生物分子序列，发现它们的相 似性， 找出序列之间共同的区域， 同时辨别序列之间的差异。 研究序列相似性的目的之一是， 通过相似序列的序列得到相似的结构或相似的功能。 序列比对的理论基础是进化学说。 许多 生物学的事实表明： 不同的核酸或蛋白质序列可能源于同一原始序列， 经过序列内残基的取 代、残基或序列片段的缺失、以及序列重组等遗传变异过程分别演化而来。在残基-残基比 对中， 可以明显看到序列中某些残基比其他位置上的残基更保守， 这些信息揭示了这些保守 位点上的残基对序列的结构和功能是至关重要的。 因此， 序列比对可用于蛋白质的功能域识 别、二级结构预测、基因识别以及分子系统发育分析等方面的研究。 序列比对根据同时进行比对的数目分为双序列比对（Pair-Wise Sequence Alignment） 和多重序列比对(Multiple Sequence Alignment)。双序列比对是将两个序列的各个字符按 照对应等同或者置换的关系进行对比排列， 其结果是找出两个序列共有的排列顺序， 这是学 列相似程度的一种定性描述。 与序列两两比对不一样， 多重序列比对研究的是多个序列的相 似性。 序列的多重比对可用来搜索基因组序列的功能区域， 也可用于研究一组蛋白质之间的 进化关系。2隐马尔科夫模型隐马尔科夫模型（Hidden Markov Models, HMM）是一种概率论模型，这种方法已经成 功地应用于多个领域，如语音识别、光学字符识别等。HMM 在生物信息学领域中也有着重要 的应用，如基因识别、序列分析、进化发育分析及蛋白质结构预测研究等。 隐马尔科夫模型可以用五个元素来描述： （1）N，模型的隐状态数目。虽然这些状态是 隐含的，但在许多实际应用中，模型的状态通常有具体的物理意义； （2）M，每个状态的不 同观测值的数目； （3）A ， 状态转移概率矩阵。描述了 HMM 模型中各个状态之间的转移概 率。其中 A_{IJ}= P(A_{T+1} =S_{J} | Q_{T}=S_{I}),1≤I,J≤N. 表示在 T 时刻、状态为 SI 的条件下，在 T+1 时刻状态是 SJ 的概率； （4）B ，观测概率矩阵。其中 BJ(K) = P[VK(T) | QT = SJ]; 1≤J≤N,1≤K≤M.表示在 T 时刻、状态是 SJ 条件下，观察符号为 VK(T)的概 率； （5）π 初始状态概率矩阵 π ={π _{J}| π _{J}= P[Q_{1} = S_{J}];1≤J≤N.表示在 初始 T=1 时刻状态为 SJ 的概率。 一般的， 可以用λ =(A,B,π )来简洁的表示一个隐马尔科夫 模型。给定了 N,M,A,B,π 后，隐马尔科夫模型可以产生一个观测序列 O=O1O2O3?OT。表示 DNA 序列的 HMM 如图 1 所示（方框表示各种状态，方框之间的连线表示状态转换） ：1图 1 DNA 序列的 HMM3基于隐马尔科夫模型的多重序列比对算法迭代比对是另一类有效的多重序列比对策略。 它基于一个能产生比对的算法， 并通过一 系列的迭代方式改进多重序列比对， 直到比对结果不再改善为止。 这类算法根据改善比对的 策略可以分为确定型和随机迭代比对方法。 最简单的迭代比对类型是确定性。 随机迭代方法 包括 Prrp,隐马尔科夫模型,模拟退火，遗传算法以及其他方法。某些方法可能是渐进方法 和迭代方法的混合。 隐马尔科夫模型是最近几年在机器学习领域都得到成功应用的关于序列分析的重要统 计模型。隐马尔科夫模型最早用于语音识别，在 80 年代末 90 年代初开始用于生物信息学， 目前已经用于 DNA 模型构建，多重序列比对，蛋白质二级结构预测，基因预测等方向。 生物的基因组可以认为是某祖先基因经过若干代的进化而来的， 这个祖先基因经过插入、 删除和匹配而不断进化，最终衍变为一个基因家族。因此，隐马尔科夫模型之所以在生物序 列分析中得到普遍应用是因为它正好模拟了生物基因的突变、插入、缺失、匹配过程。 3.1 基于隐马尔科夫模型的多重序列比对具体实现过程 解决多重序列比对问题，就是通过对序列碱基的匹配、插入和删除操作，获得一个在某 个评价模型下比分最优的结果集。基于隐马尔科夫模型具体实现过程为： （1）预处理即序列特征统计。由于生物序列本身的统计学特征，在某一位置出现字母 表中字符的概率并不是均等的， 因此需要获得一组给定相似序列组 S （i） 的序列特征统计， 一般被称为统计图谱或特征统计矩阵； （2）训练模型。即以一组给定序列相似组 S（i）作为训练序列，采用期望最大算法获 取该序列组的隐马尔科夫模型参数Θ ，构建隐马尔科夫模型 M； （3）新序列评估。即采用前向-后向算法将未知序列 X（i）与 M 比对，根据其相似成 素，所得到的比对融入多重比对以完善模型； （4）构造多重比对。根据 M 进行多重序列的比对，及采用 Viterbi 算法求解在模型 M 条件下生成未知序列 X（i）的状态序列，并根据状态序列构造多重序列比对结果 X（i） ＇ 。 3.2DNA 序列的比对中的隐马尔科夫模型 定义一个长度为 L 的序列特征统计 P 是一系列的概率集合 ei(b) , ei(b)表示在第 i(1≤i≤L) 个位置上出现字母表中字符 b 的概率，并定义 p(b)是字母 b 的背景出现频率。一个基因的 HMM 模型，有 L 个“匹配”状态的 M1，M2，? ? ? ，ML，它们对应于特征统计的匹配。所有这 些状态顺序连接起来，即状态 MJ 连接到后继 MJ+1，如下图所示。其中，从状态 MJ 释放字 符 b 的概率为 eJ(b)。为了在比对中允许插入“空格”操作，在上述基本模型中加入“插入” 状态 I0 ，I1，? ? ? ，IL，并假设 Θ?b ∈A eIj(b)=p(b)2对于每个插入状态 IJ，有一个来自相应匹配状态 MJ 的连接，有一个匹配到状态 MJ+1 的连接， 还有一个自循环连接。 根据 “空位” 的惩罚原则， 给这些状态转换赋予适当的概率。 为了允许“删除”操作，可以进一步加入“删除”状态 D1，D2，? ? ? ，DL，这些状态不能释 放任何字符。删除状态依然顺序裂解，同时增加从 D1 到 IJ 的连接以及从 IJ 到 DJ+1 的连接。 完整的 HMM 模型如下图所示。图 2 多重序列比对问题 HMM 图 对于 DNA 多重序列比对，隐马尔科夫链可以看成在 DNA 序列上运动，从一个起始状态开始， 以某概率进入配对、插入、删除状态之间的某一个，其中配对和插入状态将产生一个新的碱 基，删除状态从原始 DNA 序列中去掉一个特定的碱基。每个状态结束之后，模型转换到下一 个状态，同样，在新的状态，又可以进入配对、插入、删除状态。于是当隐马尔科夫链经历 了从起始状态到结束状态时，便可得到两个学列，一是状态序列（观察不到） ，而是 A,C,G,T 组成的字母序列（可观察到） 。对于与模型想复合的序列，能以较大的概率产生该序列；若 不与该模型符合的序列，则按此模型产生改序列的概率会较小。 采用上述模型具有以下优点： （1）模型中采用的是位置序列，每一个位置都考虑了所有 氨基酸的分布； （2）在连续的两个位置之间考虑了忽略某一位置及插入额外的氨基酸； （3） 允许连续的插入碱基。 3.3DNA 序列观察概率的计算:前向―后向算法 设 O =O1,O2,?, OT 是一个观察序列( DNA 序列) ,记 t 时刻的状态为 qt ,q0= s0 = Begin ,qT+1 = ST+1 = End。该序列 O =O1,O2,?, OT 的概率 P( O|λ) 的计算可用前向―后向算法解决。 ?定义前向变量: αt( i) = P(O1,O2,?, Ot ，qt = si | λ) (1) 这就是说,前向变量α t ( i) 是指在给定模型λ 的条件下,产生 t 以前的部分观察序列 { O1,O2,?, Ot } ,且 t 时又处于状态 si 的概率,前向变量 αt( i) 可按下列步骤进行迭代计 算: 1) 初始化 α1( i) = α0ibi(O1) 1≤i≤N (3) 2) 迭代计算 αt+1(j) = [ N t = 1,2,? ? ? , T ? 1 1 ≤ j ≤ N (4) i=1 αt i αij ]bj ot+1 ?后向算法与前向算法相类似,定义后向变量: βt( i) = P(Ot+1,Ot+2,?, Ot，qt = si | λ) (5) 即在给定模型 λ 和 t 时状态为 si 的条件下 , 从 t + 1 时到最后的部分观察序列3{Ot+1,Ot+2,? ? ? , Ot} 的概率, 可按下步骤进行迭代计算: 1) 初始化 ΒT(i)= αi,T+1 1 ≤ i ≤ N (6) 2)迭代计算 βt i = N t = T ? 1, T ? 2,? ? ?,1 j=1 αij bj ot+1 βt+1 j ?在给定模型λ 下,产生观察序列 O 的概率 P Oλ = N 1≤t≤T i=1 αt i βt i N 特别 P O λ = i=1 αT i αi,T+1 (9) (8)1 ≤ i ≤ N (7)3.4 现有算法分析 在理论上基于动态规划的同步算法可以求得多序列的精确解。 但是， 随着序列数量的增 加，算法复杂度也不断增加，呈指数规律增长，因此这类方法对于计算机的系统资源要求较 高。 在实际应用中， 比对三台哦序列是很容易实现。 如果仅仅搜索 N 维空间上有限的区域 （序 列长度在 100 之内） ，7 条和 8 条序列比对是可以管理的，但超过这个限度之后，组合数将 剧增，外加上存储空间和计算时间的限制，通常不能满足大而长的序列比对需求。所以，同 步法只能进行序列数目在 10 条之内，长度不超过 100 的少量、短序列的比对。 CLUSTAL 算法作为渐进比对算法中比较成功的算法，已经发展很成熟了，它的优点是算 法简单，运算速度快，但仍然存在着一些不足之处。在给出的两条序列按照双序列的全局比 对算法得到祖先序列的过程中，当对应位置的残基不用时，CLUSTAL 算法的解决办法是任意 取其中一个，这样就丢失了另一个序列中的信息。因此，其缺点是在这样进行选择的过程中 往往要丢失一些信息，导致结果不很可靠，使其容易陷入局部最优化，这一点是它最致命的 缺陷。 基于隐马尔科夫模型的迭代比对算法是搜索全局最小值的随机方法，它是个概率模拟算法， 在迭代步骤无限大， 具有陷入局部最小值的危险。 而采用并行隐马尔科夫模型算法可以大大 提高运算速度，在一定程度上避免陷入局部最小值得危险。 基于隐马尔科夫模型的多重序列比对算法的优点是： 模型采用的是位置序列， 每一个位 置都考虑了所有残基的分布； 对于进化过程中残基的缺失能更有效的修复。 缺点是模型本身 需要大量相似序列进行训练， 在根据训练结果对目标序列进行匹配， 需要占用大量的系统资 源。 4 总结 随着测序技术的发展及生物信息学的广泛应用， 大量的数据生物序列及生物数据不断积 累，对于多重序列比对的需求也将逐渐上升，隐马尔科夫模型的应用将会越来越广泛。隐马 尔科夫模型在生物信息学中的应用仍在不断深入, 并将出现新的模型结构以适应各种新的 生物学问题,同时隐马尔科夫模型方法,还可以与其它一些序列分析手段相结合 , 如, 贝叶 斯方法、 神经网络方法和形式语言方法等, 使得隐马尔科夫模型方法在生物信息学中应用的 范围不断扩展,随着研究的不断深入,隐马尔科夫模型将在生物信息学中发挥了越来越大的 作用。参考文献：[1] 杜世平，李海.隐马尔可夫模型在多序列比对中的应用[J].四川教育学院学报，） ：90-92. [2] 罗泽举，宋丽红.隐马尔可夫模型的多序列比对研究[J].计算机工程与应用，） ：171-174. [3] 周海延.隐马尔科夫过程在生物信息学中的应用[J]，生命科学研究，） ：204-210. 4[4] 邓志超.基于隐马尔可夫模型的并行多重序列比对[D]，东北师范大学，2007. [5] 蒋红敬.HMM 及其在生物信息学中应用[D]，中南大学，2009. [6] 曹晓燕，徐安龙.生物信息学中的马尔可夫模型[J]，中山大学学报论丛，） ：1-9. [7] 张敏.生物序列比对算法研究现状与展望[J]，大连学报，-78. [8] 罗泽举，朱思铭，何淼.基于隐马尔可夫模型的多重序列分析[J]，中山大学学报，-12. [9] 刘河生，高小榕，杨福生.隐马尔可夫模型的原理与实现[J]，国外医学生物医学工程分册，2002，25 （6） ：254-259. [10] LAWRENCE R A. Tutorial on hidden Markov models and selected applicationsin speech recognition[J].Proceedings of the IEEE, ) : 257- 286. [11] KROGH M. Hidden Markov models in computational biology: Applications toprotein modeling[J] . JMol Biol, : . [12] HUGHEY R, KROGH A.Hidden Markov models for sequence analysis: Extensionand analysis of the basic method[J].CABIOS, - 107. [13] Eld D G ， Cient E.Methods for multiple sequence alignment with guaranteed error bounds[J].Bulletin of Mathematical Biology ，1-154. [14] Knapp K ， Chen Y P.An evaluation of contemporary hidden Markovmodel genefinders with a predicted exon taxonomy[J].Nucleic AcidsResearch，） ：317-324. [15] Birney E. Hidden Markov Models in biologicalsequence analysis [ J ]. IBM Journal of Research andDevelopment V olume 45 , N umbers 3/ 4 ,2001.5如何用简单易懂的例子解释隐马尔可夫模型？ - 知乎10759被浏览628217分享邀请回答3.5K258 条评论分享收藏感谢收起19532 条评论分享收藏感谢收起更多10 个回答被折叠（）随笔 - 34&
文章 - 0&评论 - 10&trackbacks - 0
原文地址：/jacklu/p/6225073.html
隐马尔可夫模型（Hidden Markov Model，HMM）是结构最简单的动态贝叶斯网，这是一种著名的有向图模型，主要用于时序数据建模（语音识别、自然语言处理等）。
假设有三个不同的骰子（6面、4面、8面），每次先从三个骰子里选一个，每个骰子选中的概率为，如下图所示，重复上述过程，得到一串数字[1 6 3 5 2 7]。这些可观测变量组成可观测状态链。
同时，在隐马尔可夫模型中还有一条由隐变量组成的隐含状态链，在本例中即骰子的序列。比如得到这串数字骰子的序列可能为[D6 D8 D8 D6 D4 D8]。
隐马尔可夫模型示意图如下所示：
图中，箭头表示变量之间的依赖关系。在任意时刻，观测变量（骰子点数）仅依赖于状态变量（哪类骰子），“观测独立性假设”。
同时，。这就是马尔可夫链，即系统的下一时刻的状态仅由当前状态决定不依赖以往的任何状态（无记忆性），“齐次马尔可夫性假设”。
2 隐马尔可夫模型三要素
对于一个隐马尔可夫模型，它的所有N个可能的状态的集合，所有M个可能的观测集合
隐马尔可夫模型三要素：
状态转移概率矩阵A， 下一时刻t+1状态为的概率
观测概率矩阵B，，生成观测值的概率
初始状态概率向量π，
一个隐马尔可夫模型可由λ=(A, B, π)来指代。
3 隐马尔可夫模型的三个基本问题
（1） 给定模型λ=(A, B, π)，计算其产生观测序列的概率P(O|λ)；
计算掷出点数163527的概率
（2） 给定模型λ=(A, B, π)和观测序列，推断能够最大概率产生此观测序列的状态序列，即使P(I|O)最大的I；
推断掷出点数163527的骰子种类
（3） 给定观测序列，估计模型λ=(A, B, π)的参数，使P(O|λ)最大；
已知骰子有几种，不知道骰子的种类，根据多次掷出骰子的结果，反推出骰子的种类
这三个基本问题在现实应用中非常重要，例如根据观测序列推测当前时刻最有可能出现的观测值，这就转换成基本问题（1）；
在语音识别中，观测值为语音信号，隐藏状态为文字，根据观测信号推断最有可能的状态序列，即基本问题(2)；
在大多数应用中，人工指定参数模型已变得越来越不可行，如何根据训练样本学得最优参数模型，就是基本问题(3)。
4 三个基本问题的解法
基于两个条件独立假设，隐马尔可夫模型的这三个基本问题均能被高效求解。
4.1 基本问题（1）解法
4.1.1 直接计算法(概念上可行，计算上不可行)
通过列举所有可能的长度为T的状态序列，求各个状态序列I与观测序列O同时出现的联合概率P(I,O|λ)，然后对所有可能求和得到P(O|λ)。
状态序列的概率是P(I|λ)=
对于固定状态序列 I，观测序列的概率P(O|I,λ)=
I 和 O同时出现的联合概率P(I,O|λ)= P(I|λ) P(O|I,λ)
然后对所有可能的 I 求和，得到P(O|λ)
这种方法计算量很大，算法不可行。
4.1.2 前向算法(t=1,一步一步向前计算)
前向概率，表示模型λ，时刻 t，观测序列为且状态为的概率。
（1） 初始化前向概率
状态为和观测值为的联合概率
（2） 递推t=1,2,…,T-1
根据下图，得到
（3） 终止
前向算法高效的关键是其局部计算前向概率，根据路径结构，如下图所示，每次计算直接利用前一时刻计算结果，避免重复计算，减少计算量。
4.1.3 后向算法
（1）初始化后向概率
（2）递推t=T-1,T-2,…,1
（4） 终止
前向算法高效的关键是其局部计算前向概率，根据路径结构，如下图所示，每次计算直接利用前一时刻计算结果，避免重复计算，减少计算量。
4.2 基本问题（2）解法
4.2.1 近似算法
选择每一时刻最有可能出现的状态，从而得到一个状态序列。这个方法计算简单，但是不能保证整个状态序列的出现概率最大。因为可能出现转移概率为0的相邻状态。
4.2.2 Viterbi算法
使用动态规划求解概率最大（最优）路径。t=1时刻开始，递推地计算在时刻t状态为i的各条部分路径的最大概率，直到计算到时刻T，状态为i的各条路径的最大概率，时刻T的最大概率即为最优路径的概率，最优路径的节点也同时得到。
如果还不明白，看一下李航《统计学习方法》的186-187页的例题就能明白算法的原理。
状态[3 3 3]极为概率最大路径。
4.3 基本问题（3）解法
4.3.1 监督学习方法
给定S个长度相同的（观测序列，状态序列）作为训练集，使用极大似然估计法来估计模型参数。
的估计:样本中t时刻处于状态i，t+1时刻转移到状态j的频数为，则
观测概率和初始状态概率的估计类似。
4.3.2 Baum-Welch算法
使用EM算法得到模型参数估计式
EM算法是常用的估计参数隐变量的利器，它是一种迭代方法，基本思想是：
（1） 选择模型参数初始值；
（2） (E步)根据给定的观测数据和模型参数，求隐变量的期望；
（3） (M步)根据已得隐变量期望和观测数据，对模型参数做极大似然估计，得到新的模型参数，重复第二步。
参考资料：
《机器学习》周志华
《统计学习方法》李航
如何用简单易懂的例子解释隐马尔可夫模型/question/
阅读(...) 评论()