第九讲隐马尔可夫模型初步Chapter9HiddenMarkovModel.ppt

第九讲 隐马尔可夫模型初步Chapter 9 Hidden Markov Model (Part A)徐从富xucongfu@xucongfu@浙江大学人工智能研究所浙江大学人工智能研究所浙江大学人工智能研究所浙江大学人工智能研究所20032003年年年年1010月第一稿月第一稿月第一稿月第一稿20052005年年年年9 9月修改补充月修改补充月修改补充月修改补充浙江大学计算机学院《人工智能引论》课件目 录n nHMM的由来n n马尔可夫性和马尔可夫链n nHMM实例n nHMM的三个基本算法n n主要参考文献HMM的由来的由来 n n1870年，俄国有机化学家Vladimir V. Markovnikov第一次提出马尔科夫模型n n马尔可夫模型n n马尔可夫链 n n隐马尔可夫模型马尔可夫性n n如果一个过程的“将来”仅依赖“现在”而不依赖“过去”，则此过程具有马马尔可夫性尔可夫性,或称此过程为马尔可夫过程马尔可夫过程n nX(t+1) = f( X(t) )马尔科夫链n n时时时时间间间间和和状状状状态态态态都都离离散散的的马马尔尔科科夫夫过过程程称称为为马马尔尔科科夫链夫链n n记作记作{ {X Xn n = X(n), n = 0,1,2,…} = X(n), n = 0,1,2,…}– –在在时时间间集集T T1 1 = = {0,1,2,…}{0,1,2,…}上上对对离离散散状状态态的的过过程程相相继继观观察的结果察的结果n n链的状态空间记做链的状态空间记做I = {aI = {a1 1, a, a2 2,…}, ,…}, a ai i∈∈R R. . n n条件概率条件概率P Pij ij ( ( m ,m ,m+nm+n) )= =P{XP{Xm+nm+n = = a aj j|X|Xmm = = a ai i} } 为马为马氏链在时刻氏链在时刻mm处于状态处于状态a ai i条件下，在时刻条件下，在时刻m+nm+n转转移到状态移到状态a aj j的的转移概率转移概率转移概率转移概率。

转移概率矩阵阴天阴天晴天晴天下雨下雨 晴天晴天 阴天阴天 下雨下雨晴天晴天 0.50 0.25 0.25阴天阴天 0.375 0.25 0.375下雨下雨 0.25 0.125 0.625转移概率矩阵(续) n n由于链在时刻m从任何一个状态ai出发，到另一时刻m+n，必然转移到a1，a2…，诸状态中的某一个，所以有n n当Pij(m,m+n)与m无关时，称马尔科夫链为齐次马尔科夫链齐次马尔科夫链，通常说的马尔科夫链都是指齐次马尔科夫链 HMM实例 Observed Ball SequenceUrn 3Urn 1Urn 2VeilHMM实例——描述n n设设有有N N个个缸缸，，每每个个缸缸中中装装有有很很多多彩彩球球，，球球的的颜颜色由一组概率分布描述实验进行方式如下色由一组概率分布描述实验进行方式如下– –根根据据初初始始概概率率分分布布，，随随机机选选择择N N个个缸缸中中的的一一个个开开始始实验实验– –根根据据缸缸中中球球颜颜色色的的概概率率分分布布，，随随机机选选择择一一个个球球，，记记球的颜色为球的颜色为O O1 1，并把球放回缸中，并把球放回缸中– –根根据据描描述述缸缸的的转转移移的的概概率率分分布布，，随随机机选选择择下下一一口口缸缸，，重复以上步骤。

重复以上步骤n n最后得到一个描述球的颜色的序列最后得到一个描述球的颜色的序列O O1 1,O,O2 2, ,……，，称为观察值序列称为观察值序列O O HMM实例——约束 在上述实验中，有几个要点需要注意：在上述实验中，有几个要点需要注意：n n缸间的转移不能被直接观察缸间的转移不能被直接观察n n每次选取哪个缸由一组转移概率决定每次选取哪个缸由一组转移概率决定n n从缸中所选取的球的颜色和缸并不是从缸中所选取的球的颜色和缸并不是 一一对应的一一对应的HMM概念n nHMM的状态是不确定或不可见的，只有通过观测序列的随机过程才能表现出来n n观察到的事件与状态并不是一一对应，而是通过一组概率分布相联系 n nHMM是一个双重随机过程，两个组成部分：– 马尔可夫链马尔可夫链：描述状态的转移，用转移概转移概率率描述– 一般随机过程一般随机过程：描述状态与观察序列间的关系， 用观察值概率观察值概率描述Markov链链（（ , A））随机过程随机过程（（B））状态序列状态序列观察值序列观察值序列q1, q2, ..., qTo1, o2, ..., oTHMM的组成示意图的组成示意图HMM组成HMM的基本要素n n用模型五元组用模型五元组 ＝（＝（ N, M, π N, M, π ，，A A，，B B）用来描）用来描述述HMMHMM，或简写为，或简写为 =(π =(π ，，A A，，B)B)参数参数参数参数含义含义含义含义实例实例实例实例N N状态数目状态数目缸的缸的数目数目MM每个状态可能的观察值数每个状态可能的观察值数目目彩球颜色数目彩球颜色数目A A与与时间无关的状态转移概时间无关的状态转移概率矩阵率矩阵在在选定某个缸的情况下，选定某个缸的情况下，选择另一个缸的概率选择另一个缸的概率B B给定状态下，观察值概率给定状态下，观察值概率分布分布每个缸中的颜色分布每个缸中的颜色分布p p初始状态空间的概率分布初始状态空间的概率分布初始时选择某口缸的概率初始时选择某口缸的概率HMM可解决的问题n n问题1：给定观察序列O=O1,O2,…OT,以及模型 , 如何计算P(O|λ)？n n问题2：给定观察序列O=O1,O2,…OT以及模型λ,如何选择一个对应的状态序列 S = q1,q2,…qT，使得S能够最为合理地解释观察序列O？n n问题3：如何调整模型参数 , 使得P(O|λ)最大？ 解决问题1—— 基础方法n n给定一个固定的状态序列S=(q1 1，q2 2，q3 3…)n n 表示在qt t状态下观测到Ot t的概率n n n nN=5, M=100, 其计算量为1072！解决问题1—— 前向法n n动态规划n n定义前向变量–初始化：初始化：–递归：递归：–终结：终结：前向法示意图 1 ... t t+1 ...a1jat1qN.qi.qj....q1atNatiaNjaij当当N=5, M=100N=5, M=100时时, , 其其计计算量算量为为30003000！！解决问题1 ——后向法n n与前向法类似n n定义后向变量–初始化：初始化：–递归：递归：–终结：终结：Viterbi算法算法n n目的：给定观察序列给定观察序列O O以及模型以及模型λ, λ,如何选择一如何选择一个对应的状态序列个对应的状态序列S S ，使得，使得S S能够最为合理的能够最为合理的解释观察序列解释观察序列O O？？n nN和T分别为状态个数和序列长度定义：我们所要找的，就是我们所要找的，就是T T时刻最大的时刻最大的 所代表所代表的那个状态序列的那个状态序列Viterbi算法算法(续续)n n初始化：n n递归：n n终结：n n求S序列：Baum-Welch算法算法(模型训练算法模型训练算法)n n目的：给定观察值序列目的：给定观察值序列O O，，通过计算确定一个模型通过计算确定一个模型l ，， 使得使得P(O| P(O| l) )最大。

最大n n算法步骤：算法步骤：1. 初始模型（待训练模型） l0,2. 基于l0 以及观察值序列O，训练新模型 l；3. 如果 log P(X|l) - log(P(X|l0) < Delta，说明训练已经达到预期效果，  算法结束4. 否则，令l0 ＝ l ，继续第2步工作 Baum-Welch算法算法(续续)n n定义：定义：Baum-Welch算法算法(续续2)n n参数估计：参数估计：几种典型形状的马尔科夫链n na. Aa. A矩阵没有零矩阵没有零值的值的MarkovMarkov链链n nb. Ab. A矩阵有零值矩阵有零值的的MarkovMarkov链链n nc./d. c./d. 左－右形式左－右形式的的MarkovMarkov链链HMM的应用领域n n语音识别语音识别n n机器视觉机器视觉– –人脸检测人脸检测– –机器人足球机器人足球n n图像处理图像处理– –图像去噪图像去噪– –图像识别图像识别n n生物医学分析生物医学分析– –DNA/DNA/蛋白质序列分析蛋白质序列分析主要参考文献n n1. Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings 1989.n nftp://10.11.11.111/课件/徐从富_AI/补充材料/隐Markov模型.pdf或ftp://10.214.1.200/课件/徐从富_AI/补充材料/隐Markov模型.pdf欢迎批评指正，谢谢！。