隐马尔科夫模型 Hidden Markov model

隐马尔可夫模型HiddenMarkovmodel徐从富浙江大学人工智能研究所2003年10月第一稿2005年9月修改补充Modifiedbysiuleung目录HMM的由来马尔可夫性和马尔可夫链HMM实例HMM的三个基本算法主要参考文献HMM的由来1870年，俄国有机化学家VladimirV.Markovnikov第一次提出马尔科夫模型马尔可夫模型马尔可夫链隐马尔可夫模型马尔可夫性如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马尔可夫性,或称此过程为马尔可夫过程X(t+1)=f(X(t))马尔科夫链时间和状态都离散的马尔科夫过程称为马尔科夫链记作{Xn=X(n),n=0,1,2,…}–在时间集T1={0,1,2,…}上对离散状态的过程相继观察的结果链的状态空间记做I={a1,a2,…},ai∈R.条件概率Pij(m,m+n)=P{Xm+n=aj|Xm=ai}为马氏链在时刻m处于状态ai条件下，在时刻m+n转移到状态aj的转移概率。转移概率矩阵阴天晴天下雨晴天阴天下雨晴天0.500.250.25阴天0.3750.250.375下雨0.250.1250.625转移概率矩阵(续)由于链在时刻m从任何一个状态ai出发，到另一时刻m+n，必然转移到a1，a2…，诸状态中的某一个，所以有当Pij(m,m+n)与m无关时，称马尔科夫链为齐次马尔科夫链，通常说的马尔科夫链都是指齐次马尔科夫链。1(,)1,1,2,ijjPmmniHMM实例ObservedBallSequenceUrn3Urn1Urn2VeilHMM实例——描述设有N个缸，每个缸中装有很多彩球，球的颜色由一组概率分布描述。实验进行方式如下–根据初始概率分布，随机选择N个缸中的一个开始实验–根据缸中球颜色的概率分布，随机选择一个球，记球的颜色为O1，并把球放回缸中–根据描述缸的转移的概率分布，随机选择下一口缸，重复以上步骤。最后得到一个描述球的颜色的序列O1,O2,…，称为观察值序列O。HMM实例——约束在上述实验中，有几个要点需要注意：不能被直接观察缸间的转移从缸中所选取的球的颜色和缸并不是一一对应的每次选取哪个缸由一组转移概率决定HMM概念HMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系HMM是一个双重随机过程，两个组成部分：–马尔可夫链：描述状态的转移，用转移概率描述。–一般随机过程：描述状态与观察序列间的关系，用观察值概率描述。Markov链（,A）随机过程（B）状态序列观察值序列q1,q2,...,qTo1,o2,...,oTHMM的组成示意图HMM组成HMM的基本要素用模型五元组＝（N,M,π，A，B）用来描述HMM，或简写为=(π，A，B)参数含义实例N状态数目缸的数目M每个状态可能的观察值数目彩球颜色数目A与时间无关的状态转移概率矩阵在选定某个缸的情况下，选择另一个缸的概率B给定状态下，观察值概率分布每个缸中的颜色分布初始状态空间的概率分布初始时选择某口缸的概率HMM可解决的问题问题1：给定观察序列O=O1,O2,…OT,以及模型,如何计算P(O|λ)？问题2：给定观察序列O=O1,O2,…OT以及模型λ,如何选择一个对应的状态序列S=q1,q2,…qT，使得S能够最为合理的解释观察序列O？问题3：如何调整模型参数,使得P(O|λ)最大？(,,)AB(,,)AB解决问题1基础方法给定一个固定的状态序列S=(q1，q2，q3…)表示在qt状态下观测到Ot的概率N=5,M=100,=计算量10^72TtTqqqttObObObqOPSOPt121)()()(),/(),/(21)(tqObtS)/(),/()/(所有SPSOPOP解决问题1前向法动态规划定义前向变量–初始化：–递归：–终结：TtqOOOPiittt1)/,,,()(21　　　TtObiii1)()(11　　　NjTtObaijtjijNiit1,11)(])([)(111　　　NiTiOP1)()/(前向法示意图1...tt+1...a1jt1qN.qi.qj..q1tNtiaNjaij1jtN=5,M=100,=计算量3000解决问题1后向法与前向法类似定义后向变量–初始化：–递归：–终结：11)/,,,()(21TtqOOOPiitTttt　　　TtiT11)(　　　NiTTtjObaittNijijt1,1,...,2,1)()()(111　NiiOP11)()/(Viterbi算法目的：给定观察序列O以及模型λ,如何选择一个对应的状态序列S，使得S能够最为合理的解释观察序列O？N和T分别为状态个数和序列长度定义：我们所要找的，就是T时刻最大的所代表的那个状态序列1211211,2,,,,...()max[...,,|]tttttqqqiPqqqqiOOO…()TiViterbi算法(续)初始化：递归：终结：求S序列：Ni1,0)(Ni1),()(111　　　　iObiii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()iiSi当＝时处于的概率几种典型形状的马尔科夫链a.A矩阵没有零值的Markov链b.A矩阵有零值的Markov链c./d.左－右形式的Markov链HMM的应用领域语音识别机器视觉–人脸检测–机器人足球图像处理–图像去噪–图像识别生物医学分析–DNA/蛋白质序列分析主要参考文献1.LawrenceR.Rabiner,ATutorialonHiddenMarkovModelsandSelectedApplicationsinSpeechRecognition.Proceedings1989.课件/徐从富_AI/补充材料/隐Markov模型.pdf或课件/徐从富_AI/补充材料/隐Markov模型.pdf欢迎批评指正，谢谢！