隐马尔科夫模型教学PPT

隐马尔可夫模型HMM1随机过程2马尔科夫链34主要讲述的内容5三种问题及相应算法应用举例隐马尔科夫模型2.马尔科夫链设S是一个由有限个状态组成的集合。S={1,2,3,…,n-1,n}可以把马尔科夫链看做小球随时间在n种状态跳动的过程。TS123n......0123t......11220011|,,|ttttttttttPqiqiqiqiPqiqi由小球的跳动产生的状态序列X如果序列X在t时刻处在状态，若有tq则随机序列X构成一个一阶马尔科夫链。(MarkovChain)状态转移概率矩阵隐马尔科夫概括和简介•隐马尔可夫模型是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有响应概率密度分布的状态序列产生。所以，隐马尔可夫模型是一个双重随机过程----具有一定状态数的隐马尔可夫链和显示随机函数集。自20世纪80年代以来，HMM被应用于语音识别，取得重大成功。到了90年代，HMM还被引入计算机文字识别和移动通信核心技术“多用户的检测”。近年来，HMM在生物信息科学、故障诊断等领域也开始得到应用。隐马尔科夫模型可以用五个元素来描述λ=(N,M,A,B,π)其中：N={q1,...qN}：状态的有限集合，隐状态的数目M={v1,...,vM}：观察值的有限集合，可能的观测值A={aij}，aij=p(Xt+1=qj|Xt=qi)：状态转移概率B={bik}，bik=p(Ot=vk|Xt=qi)：观察值状态分布π={πi}，πi=p(X1=qi)：初始状态空间概率分布隐马尔可夫模型（HMM）的三个基本问题令λ={A,B,π}为给定HMM的参数，令σ=O1,...,OT为观察值序列，1、评估问题：对于给定模型，求某个观察值序列的概率p(σ|λ)；2、解码问题：对于给定模型和观察值序列，求可能性最大的状态序列；3、学习问题：对于给定的一个观察值序列，调整参数λ，使得观察值出现的概率p(σ|λ)最大。针对以上三个问题，人们提出了相应的算法•评估问题：向前算法–定义向前变量–采用动态规划算法，复杂度O(N2T)•解码问题：韦特比（Viterbi）算法–采用动态规划算法，复杂度O(N2T)•学习问题：向前向后算法EM算法的一个特例，带隐变量的最大似然估计HMM的应用领域•语音识别•机器视觉–人脸检测–机器人足球•图像处理–图像去噪–图像识别•生物医学分析–DNA/蛋白质序列分析•.HMM实例ObservedBallSequenceUrn3Urn1Urn2VeilHMM实例——描述•假设在一个房间中，有N个缸子，每个缸子里都装有不同颜色的小球，记小球的总颜色为M种，一个人在房间中首先随机地选择一个缸子，再从这个缸子中随机的选择一个小球，并把小球的颜色报告给房间外面的人记录下来作为观察值，记为O1，然后这个人再把球放回缸子中，以当前的缸子为条件再随机选择一个缸子，从中随机选择一个小球，并报告小球颜色，记为O2，长此以往，房间外的人会得到由这个过程产生的小球颜色的序列。•知道了小球颜色的序列，我们并不能直接确定缸子之间转换的序列。即如果给定一个观察序列，不能直接确定状态转换序列，因为状态转换的过程被隐藏起来了，所以这类随机过程称为隐马尔科夫过程。•在实验中可以看出，隐马尔科夫过程是比马尔科夫的更为复杂，在马尔科夫过程中，每个状态只有一个输出。而在这个实验中，可以从每个缸子中拿出不同颜色的小球，即每个状态能产生多个输出，观察到的事件并不是与一个状态一一对应，而是通过一组概率分布相联系。HMM实例——总结•在上述实验中，总结以下几个注意点：•不能直接观察缸间的转移•从缸中所选取的球的颜色和缸并不是•一一对应的•每次选取哪个缸由一组转移概率决定•HMM是一个双重随机过程，两个组成部分：–马尔可夫链：首先是缸子选择的过程，每一个缸子对应一个状态，就可以用一个一阶的马尔科夫过程来表示缸子的选择过程。–一般随机过程：另一个随机过程是小球颜色的观察值和缸子转换序列之间的对应关系，因为站在观察者的角度，只能看到观察值，不能直接看到状态，而是通过一个随机过程去感知状态的存在及其特性。HMM实例——总结HMM实例——总结•用模型五元组＝（N,M,π，A，B）用来描述HMM，或简写为=(π，A，B)参数含义实例N状态数目缸的数目M每个状态可能的观察值数目彩球颜色数目A与时间无关的状态转移概率矩阵在选定某个缸的情况下，选择另一个缸的概率B给定状态下，观察值概率分布每个缸中的颜色分布p初始状态空间的概率分布初始时选择某口缸的概率HMM的应用领域•语音识别•机器视觉–人脸检测–机器人足球•图像处理–图像去噪–图像识别•生物医学分析–DNA/蛋白质序列分析问题一•给定，以及状态转换序列产生的观测序列的概率可以通过下面的公式计算：),...,(21Tqqqq),...,(21TxxxX)()...()(),|(2211TqTqqxbxbxbqXP),...,(21TqqqqqTqTqqqqqaaaqp132211...)|(p)()...()()|,()|(122211,...,1121TqTqTqTqqqqqqqqqxbaxbaxbqXpXpTp)|(),|()|,(qpqXpqXp给定，状态转换序列的概率可以由下式计算：则联合概率为：考虑所有的状态转换序列，则：时间复杂度：O(NT)问题一（1）前向算法：前向变量：问题一（1）初始化迭代公式终止时间复杂度：O(N2T)问题一NumericalExample:问题一（2）后向算法（1）：后向变量：问题一（2）后向算法（2）：初始化迭代公式Viterbi算法•目的：给定观察序列O以及模型λ,如何选择一个对应的状态序列S，使得S能够最为合理的解释观察序列O？•N和T分别为状态个数和序列长度定义：我们所要找的，就是T时刻最大的所代表的那个状态序列1211211,2,,,,...()max[...,,|]tttttqqqiPqqqqiOOO…()TiViterbi算法(续)•初始化：•递归：•终结：•求S序列：Ni1,0)(Ni1),()(111　　　　iObiiipNjTtaijNjTtObaijijtNitijijtNit1,2],)([maxarg)(1,2),(])([max)(1111　　　　)]([maxarg)])([max1*1*iqiPTNiTTNi1,...,2,1),(*11*TTtqqttt　　Baum-Welch算法(模型训练算法)•目的：给定观察值序列O，通过计算确定一个模型，使得P(O|)最大。•算法步骤：1.初始模型（待训练模型）0,2.基于0以及观察值序列O，训练新模型；3.如果logP(X|)-log(P(X|0)Delta，说明训练已经达到预期效果，算法结束。4.否则，令0＝，继续第2步工作Baum-Welch算法(续)•定义：1111111i11i1ij(,)(,)(,|,)()()()()()()()(,)S()S(,)tttttijjttNNtijjttijNttjTtttijijPsisjXiabOjiabxjiijtiij给定模型和观察序列条件下，从到的转移概率定义为时刻处于状态的概率整个过程中从状态转出的次数(numberoftime)的预期1ij1SSTt从跳转到次数的预期Baum-Welch算法(续2)•参数估计：,Oexpectednumberoftimesinstateandobservingsymbolˆ()expectednumberoftimesinstate()()tjttkttjkbkjjjReestimate:expectedcountoftransitionsfromitojˆexpectedcountofstaysati(,)(,)ijttttjaijij1t1()iiSip当＝时处于的概率