第3讲隐马尔可夫模型及其应用5VIP免费

隐Markov模型及其NLP应用网络智能信息技术研究所孙越恒第一页，共六十页。主要内容Markov模型1隐Markov模型(HMM)2隐Markov模型的三个基本问题及其算法34隐Markov模型的应用5隐Markov模型总结第二页，共六十页。一、Markov模型（1）现实生活中的例子传染病感染人数变化的过程人口增长的过程青蛙在荷叶上跳跃这些随机过程都可视为Markov过程！第三页，共六十页。一个系统有N个状态S1，S2，···，SN，随着时间推移，系统从某一状态转移到另一状态，设qt为时间t的状态，系统在时间t处于状态Sj的概率取决于其在时间1，2，···，t-1的状态，该概率为：如果系统在t时间的状态只与其在时间t-1的状态相关，则该系统构成一个一阶Markov过程：Markov模型（2）,...),|(21ktitjtSqSqSqP)|(,...),|(121itjtktitjtSqSqPSqSqSqP公式1.1公式1.2第四页，共六十页。如果只考虑独立于时间t的随机过程：称为状态转移概率，必须满足,且,则该随机过程称为Markov模型。ijaMarkov模型（3）NjiaSqSqPijitjt,1,)|(10ija11Njija公式1.3第五页，共六十页。Markov模型（4）Markov模型的实质Markov模型可视为随机有限状态自动机，该有限状态自动机的每一个状态转换过程都有一个相应的概率，表示自动机采用这一状态转换的可能性。表示成状态图的Markov链=转移弧上有概率的非确定的有限状态自动机第六页，共六十页。二、隐Markov模型（1）放有彩色球的罐子，每个罐子都有编号，随机地从罐子中摸出彩球…可观察序列猜测隐藏在幕后的罐子序列第七页，共六十页。隐Markov模型（2）双重的随机过程状态转移：从一个罐子转移到另一个罐子1可观察符号的输出：从某个罐子取出某种颜色的球2状态的转移过程是隐蔽的，而可观察符号的输出过程是状态转移过程的随机函数。第八页，共六十页。q1...o1...观察序列O状态序列QHMMλ隐Markov模型（3）q2q3q4qTo2o3o4oT第九页，共六十页。隐Markov模型（4）隐Markov模型的形式化描述1.状态集合：，以qt表示模型在t时刻的状态；2.输出符号集合：3.状态转移矩阵：A=aij（aij是从状态Si转移到状态Sj的概率），其中：12{,,...,}MOOOO以不同编号表示的不同罐子不同颜色的球罐子之间互相转移的概率NSSSSS,...,,,32110,,,1),|(N11jijijitjtijaaNjiSqSqPa其中第十页，共六十页。隐Markov模型（5）4.可观察符号的概率分布矩阵：B=bj(k)，表示在状态j时输出符号vk的概率，其中：5.初始状态概率分布：1()(|),1,1,()0,()=1MjtktjjjkbkPOvqSjNkMbkbk其中11(),1,0,1NiiiiiPqSiN其中从某个罐子取出某种颜色球的概率在初始时刻选择不同罐子的概率一般的，一个HMM可以表示为λ＝(S,O,A,B,π)或λ＝(A,B,π)第十一页，共六十页。三、隐Markov模型的三个基本问题及其算法（1）隐Markov模型涉及如下三个基本问题评估问题：给定一个观察序列和模型λ，如何计算给定模型λ下观察序列O的概率P(O|λ)。1解码问题：给定一个观察序列和模型λ，如何计算状态序列，使得该状态序列能“最好地解释”观察序列。2学习问题：给定一个观察序列，如何调节模型λ的参数，使得P(O|λ)最大。312...TOOOO12...TOOOO12...TQqqq12...TOOOO第十二页，共六十页。隐Markov模型的三个基本问题及其算法（2）问题1：评估问题解决之道：前向算法、后向算法、前向-后向算法前向算法前向变量：HMM在时间t输出序列O1…Ot，并且位于状态i的概率：则有：)|,...()(1itttSqOOPiNiiTiTTiiiiOPSqOPSqOOPiObSqOPi1T1T1111)()|()|,()|,...()()()|,()(公式3.1公式3.2第十三页，共六十页。前向算法：1.初始化：2.递归：3.终止：11()(),1iiibOiN111()[()]()NttijjtijibO1(|)()NTiPOi1111111111(...,|)(|)[(...,|)(|)]()[()]()ttjttjNttitjtijtiNtijjtiPOOqSPOqSPOOqSPqSqSbOiabO1111()(...,|)ttttjjPOOOqS隐Markov模型的三个基本问题及其算法（3...