第9章_隐马尔可夫模型

Date:19.12.2019File:ML11.1MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering第9章隐马尔可夫模型(HiddenMarkovModels)Date:19.12.2019File:ML11.2MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering主要内容•马尔可夫模型•隐马尔可夫模型•隐马尔可夫模型的三个基本问题•三个基本问题的求解算法1.前向算法2.Viterbi算法3.向前向后算法•隐马尔可夫模型的应用•隐马尔可夫模型的一些实际问题•隐马尔可夫模型总结Date:19.12.2019File:ML11.3MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering马尔可夫链一个系统有N个状态S1，S2，···，Sn，随着时间推移，系统从某一状态转移到另一状态，设qt为时刻t的状态，系统在时刻t处于状态Sj的概率取决于其在时间1，2，···，t-1的状态，该概率为：如果系统在t时间的状态只与其在时间t-1的状态相关，则该系统构成一个离散的一阶马尔可夫链(马尔可夫过程)：即：给定当前的状态，未来的系统状态独立于过去的状态Date:19.12.2019File:ML11.4MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering马尔可夫模型如果只考虑独立于时间t的随机过程：其中状态转移概率aij必须满足aij=0,且，则该随机过程称为马尔可夫模型。jia,独立于时间t：从状态Si到状态Sj的状态转移具有相同的概率，无论这个转移在观测序列中的何时或何地发生。Date:19.12.2019File:ML11.5MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering马尔可夫模型可视为随机有限状态自动机•该有限状态自动机的每一状态转换都有一相应概率，表示自动机采样这状态转换的可能性Date:19.12.2019File:ML11.6MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering假定一段时间的气象可由一个三状态的马尔可夫模型M描述，S1：下雨，S2：多云，S3：晴天，状态转移概率矩阵为：多云下雨晴天例：Date:19.12.2019File:ML11.7MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering例（续）如果第一天为晴天，根据这一模型，在今后七天中天气为O=“晴晴雨雨晴云晴”的概率为：Date:19.12.2019File:ML11.8MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering可观测状态序列观测概率•定义初始概率πi，表示序列是Si的概率：•有:•若有一可观测序列O，它是状态序列O=Q=｛q1,q2,q3,…,qT｝的概率为：1111122(|,)()(|)...TTNttqqqqqiPOQAPqPqqaa11Nii1()iiPqSDate:19.12.2019File:ML11.9MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering如何学习得到π、A•给定K个长度为T的序列，初始概率估计：•转移概率的估计：1ik()#{}#{}kiiqSSK)以始的序列＝序列11ijk11ik1()#{}()TkktitjtijTktitqSandqSSSaqS)到的移＝＃{S移}Date:19.12.2019File:ML11.10MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering隐马尔可夫模型•在MM中，每一个状态代表一个可观察的事件•在HMM中观察到的事件是状态的随机函数，因此该模型是一双重随机过程，其中状态转移过程是不可观测（隐蔽）的(马尔可夫链)，而可观测的事件的随机过程是隐蔽的状态转换过程的随机函数(一般随机过程)。Date:19.12.2019File:ML11.11MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering实例一房间有N只容器，每只容器中有M种不同颜色的球。根据某一概率分布随机地选择一个初始容器，根据不同颜色球的概率分布从中随机取出一个球，并报告球的颜色。然后根据某一概率分布随机地选择另一只容器，再根据不同颜色球的概率分布从中随机取出一个球，并报告球的颜色，⋯。对房间外的观察者，可观察的过程是不同颜色球的序列，而容器的序列是不可观察的。这里每只容器对应HMM模型中的状态，球的颜色对应于状态的输出符号，从一只容器转向另一只容器对应于状态转换，从一只容器中取球对应于从一状态输出观察符号。Date:19.12.2019File:ML11.12MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering实例（续）Date:19.12.2019File:ML11.13MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering实验中几个要点不能直接观察容器间的转移；从容器中所选取的球的颜色和容器并不是一一对应的；每次选取哪个容器由一组转移概率决定。Date:19.12.2019File:ML11.14MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineeringHMM的三个假设对于一个随机事件，有一观察值序列：O=O1,O2,…OT该事件隐含着一个状态序列：Q=q1,q2,…qT。假设1：马尔可夫性假设（状态构成一阶马尔可夫链）P(qi|qi-1…q1)=P(qi|qi-1)假设2：不动性假设（状态与具体时间无关）P(qi+1|qi)=P(qj+1|qj)，对任意i，j成立假设3：输出独立性假设（输出仅与当前状态有关）p(O1,...,OT|q1,...,qT)=Πp(Ot|qt)Date:19.12.2019File:ML11.15MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineeringHMM的组成一个隐马尔可夫模型(HMM)是由一个五元组描述的：λ＝（N，M，A，B，π）其中：S={q1,...qN}：N为模型状态个数V={v1,...,vM}：M为不同观测符号个数A={aij}，aij=P(qt=Sj|qt-1=Si)：状态转移概率矩阵B={bjk}，bjk=P(Ot=vk|qt=Sj)：给定状态下，观察值概率分布矩阵π={πi}，πi=P(q1=Si)：初始状态概率分布Date:19.12.2019File:ML11.16MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering状态转移概率矩阵Date:19.12.2019File:ML11.17MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering观察值概率分布矩阵Date:19.12.2019File:ML11.18MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering初始状态概率分布Date:19.12.2019File:ML11.19MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering观察序列产生步骤•给定HMM模型λ=(A，B，π)，则观察序列O=O1,O2,…,OT可由以下步骤产生：•1.根据初始状态概率分布π=πi,选择一初始状态q1=Si；•2.设t=1；•3.根据状态Si的输出概率分布bjk,输出Ot=vk；•4.根据状态转移概率分布aij,转移到新状态qt+1=Sj；•5.设t=t+1,如果tT，重复步骤3、4，否则结束。Date:19.12.2019File:ML11.20MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineeringHMM的三个基本问题令λ={π，A，B}为给定HMM的参数，令O=O1,...,OT为观测值序列，则有关于隐马尔可夫模型（HMM）的三个基本问题：1.评估问题：对于给定模型，求某个观测值序列的概率P(O|λ)；2.解码问题：对于给定模型和观测值序列，求可能性最大的状态序列maxQ{P(Q|O,λ)}；3.学习问题：对于给定的一个观测值序列O，调整参数λ，使得观测值出现的概率P(O|λ)最大。Date:19.12.2019File:ML11.21MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering骰子A骰子B1点1/602点1/61/83点1/61/84点1/63/165点1/63/166点1/63/8公平骰子A与灌铅骰子B的区别:Date:19.12.2019File:ML11.22MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering例:赌场的欺诈某赌场在掷骰子根据点数决定胜负时,暗中采取了如下作弊手段:在连续多次掷骰子的过程中,通常使用公平骰子AB0.90.1A,偶而混入一个灌铅骰子B.0.80.2公平骰子灌铅骰子Date:19.12.2019File:ML11.23MachineLearningPengKaixiang2014.Allrightsreserved.MachineLearningforControlEngineering时间1234567骰子AAABAAA掷出点数3345162一次连续掷骰子的过程模拟隐序列明序列查封赌场后,调查人员发现了一些连续掷骰子的记录,其中有一个骰子掷出的点数记录如下:124552646214614613613666