隐马尔可夫模型及其应用简介.ppt

第19讲 基于隐马尔可夫模型 的模式识别,要点:,Hidden Markov Models (HMM) 隐马尔可夫模型的结构示意图 隐马尔可夫模型的基本定义 隐马尔可夫模型的参数描述 隐马尔可夫模型的基本问题 隐马尔可夫模型的应用领域 隐马尔可夫模型的经典文献,隐马尔可夫模型的结构示意图,隐马尔可夫模型可以看作一个随机二元组(O,q)，其中O称为观察序列，q称为状态序列，可以分别表示为： O=(o1,o2,oT)， q=(q1,q2,qT) O和q之间的关系可以用状态转移观察生成图来描述： 返回,隐马尔可夫模型的基本定义,定义1：(O,q)是一个隐马尔可夫模型当且仅当 定义2： (O,q)是一个隐马尔可夫模型当且仅当 返回,隐马尔可夫模型的参数描述,如果在任意时刻t的状态qt只能从集合1,2,N，观察ot只能从集合v1,.,vM取值，那么为了完整描述一个隐马尔可夫模型需要确定下面的所有参数： 返回 (1) 转移概率：A=aij, aij=P(qt+1=j | qt=i); (2) 输出概率：B=bik, bi(vk)=bik=P(ot=vk | qt=i); (3) 初始状态分布：=i, i=P(q1=i) 。 =A,B,称为隐马尔可夫模型的参数描述。,转移概率举例,返回,输出概率举例,返回,初始状态分布举例,初始状态分布相当于状态的先验分布： 举例如下： =i=1/3,1/3,1/3 =i=0.2,0.6,0.2 =i=0.5,0.3,0.2 返回,隐马尔可夫模型的基本问题,(1) 评估问题：对于给定模型，求某个观察序列O的概率P(O|) ； (2) 解码问题：对于给定模型和观察序列O，求最可能的状态序列q； (3) 学习问题：对于给定观察值序列O，调整参数，使得概率P(O|)最大。 硬币投掷模型 返回,评估问题的解决,有两种基本的解决方案： (1)利用前向变量计算: (2)利用后向变量计算: 返回,利用前向变量解决评估问题,(1)初始化: (2)递归计算: (3)计算结果: 采用动态规划算法(示意图)，复杂度O(N2T) 返回,前向递归计算示意图,返回,利用后向变量解决评估问题,(1)初始化: (2)递归计算: (3)计算结果: 采用动态规划算法(示意图) ，复杂度O(N2T) 返回,后向递归计算示意图,返回,解码问题的解决,有两种基本的最优标准： (1)单个状态最优： (2)整个状态序列最优： 返回,单个最优状态求解,定义后验概率变量: 单个最优状态为： 返回,整个最优状态序列求解,定义路径变量： 韦特比（Viterbi）算法： (1)初始化： (2)递归计算： (3)终止： (4)路径反推： 返回,学习问题的解决,定义双状态变量： 学习(重估)公式(前向-后向算法)描述如下： 返回,双状态变量计算示意图,返回,硬币投掷模型,如果按照一定的概率分布随机投掷三枚硬币，假如每次投掷后你只被告知硬币的正反，但不被告知所投掷的硬币，那么硬币投掷对你来说就构成一个隐马尔可夫模型，描述如下： (1)三个状态：S1, S2, S3 (每个硬币构成一个状态) (2)两个观察值：H(Head，正面)，T(Tail，反面) (3)参数举例：i=1/3， aij=1/3 计算举例 返回,硬币投掷模型计算举例,设观察序列为O=(HHHHTHTTTT) P(O|)=(1/3)10(0.5+0.75+0.25)5(0.5+0.25+0.75)5=(0.5)10 整体最优状态序列计算如下(忽略状态转移的影响)： (1)初始化： (2)递归计算过程 (3)最优状态反推过程 想一想，单个最优状态是什么? 返回,递归计算过程示意图,递推公式： 返回,最优状态反推过程示意图,反推公式： 返回,隐马尔可夫模型的应用领域,词性标注（POS Tagging） 语音识别 音字转换 组块分析 基因和蛋白质序列分析 一般化：任何与线性序列相关的现象 返回,隐马尔可夫模型在词性标注中的应用,问题： 已知单词序列w1w2wn，求词性序列c1c2cn HMM模型： 将词性为理解为状态 将单词为理解为输出值 训练： 统计词性转移矩阵aij和词性到单词的输出矩阵bik 求解：Viterbi算法 返回,隐马尔可夫模型的经典文献,Rabiner, L. R., A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition, Proceedings of the IEEE, vol. 77, no. 2, Feb. 1989, pgs 257 - 285. Rabiner, L.R., B.H. Juang. 1993. Fundamentals of Sp