HMM模型和词性标注.ppt

HMM模型 和词性标注,徐志明 哈工大语言技术中心,目录,Markov模型 HMM 词性标注,Markov模型,描述： 一个随机过程上的随机变量序列，X = X1, X2Xt 随机变量取值于有限集 S = s1,s2 sN。S称为状态空间。,X,X,X,X,状态序列,Markov模型,模型描述 一个随机过程，存在着一个随机变量序列 X = X1, X2Xt 随机变量的取值于有限集 S = s1,s2 sN, S称为状态空间。 两个假设： 有限视野： P(Xt+1| X1, X2Xt) = P(Xt+1|Xt) 时间不变性: 这种条件依赖，不随时间的改变而改变。 若随机过程满足上述假设，则是一个Markov 过程（链）。,Markov模型,模型表示： 三元组(S, p , A) S ：状态的集合， S = s1,s2 sN。 p：初始状态的概率。 p =p1,p2pN; pi =P(X1= si) A ：状态转移概率矩阵。 A=aij; aij = P(Xt+1=sj|Xt=si) 状态图 相当于一个有限状态自动机 转移弧上有概率,Markov模型,状态空间 S=t,i,p,a,h,e 初始概率 p =1.0,0,0,0,0 状态转移概率矩阵,Markov模型,计算状态序列的概率 例子：,The Markov Chain Ex 2,例：Markov模型描述道琼斯工业指数。,5 个连续上涨交易日的概率,Markov模型,Bigram：一阶Markov模型.,HMM,HMM，从状态产生输出,HMM,HMM，不同状态可能产生相同输出,HMM,HMM，从弧中产生输出,HMM,HMM，输出带有概率,Hidden Markov Model（HMM）,模型原理 表层事件：可观察序列； 底层事件：隐藏的、不可见的；状态序列。 表层事件是由底层事件引起的。根据表层事件的可观察序列，推测生成它的底层事件的序列。 例子：观察一个人每天带雨伞情况，推测天气情况。,隐藏的状态序列,表层的可观察序列,HMM应用例子,例子：,HMM假设,一个随机过程，有一个观察序列 O=O1 , O2.OT ，该过程隐含着一个状态序列 X=X1 , X2 . XT 假设 Markov假设 假设1：有限历史假设：P(Xi|X1 , X2Xi-1) = P(Xi|Xi-1) 假设2：时间不动性假设 输出条件独立性假设 输出仅与当前状态有关 P(O1 , O2.OT | X1 , X2 . XT) = t P(Ot|Xt),HMM模型图示,两个随机过程,Markov链 （, A）,符号输出 过程（B）,状态序列,观察值序列,X1, X2 . XT,O1 , O2 . OT,HMM的组成示意图,HMM模型图示,状态空间,观察序列,时间,状态序列 X1 X2 XT-1 XT-1,HMM模型图示,HMM模型表示,模型表示 五元组(S, V, p ,A,B) 符号表 S ：状态集合， s1, , sN。 V：输出字母表， v1, , vM 模型参数 p ：初始状态概率。 p = pi; A ：状态转移概率。 A = aij; B ：符号输出概率。 B = bjk; 序列 状态序列： X = X1 , X2XT 输出序列： O = O1 , O2 OT,HMM过程,HMM过程描述,t = 1； 初始状态概率分布为。从状态si开始的概率为i； Forever do 从状态si 向状态sj转移,并输出观察符号Ot = k 。 其中，状态转移概率为aij。符号输出概率为 bjk t = t+1 End,HMM的三个基本问题,给定一个观察序列O = O1, O2OT和模型=(A,B,) 问题1： 如何有效计算观察序列 O = O1, O2OT 的概率P(O|) ？ 评价问题 问题2： 如何寻找最佳的状态序列 X = X1, X2 XT ？ 解码问题 问题3： 如何训练模型参数=(A,B,) ，使得P(O|)概率最大？ 模型参数学习、训练问题,HMM相关的算法,评价问题：向前算法 定义向前变量 采用动态规划算法 解码问题：Viterbi算法 采用动态规划算法 模型参数训练、学习问题： 向前-向后算法 EM算法,问题1：评价（Evaluation）,给定一个模型= (A,B,) ， 计算某一观察序列 O = O1, O2OT 的概率P(O|),HMM例子,假设： 某一时刻只有一种疾病，且只依赖于上一时刻疾病（有限历史假设） 一种疾病只有一种症状，且只依赖于当时的疾病（输出条件独立性假设） 症状(观察值)： O = O1, O2 OT 发烧，咳嗽，咽喉肿痛，流涕 疾病(状态值)： X = X1 , X2XT 感冒，肺炎，扁桃体炎 转移概率：A 从一种疾病转变到另一种疾病的概率 输出概率：B 某一疾病呈现出某一症状的概率 初始分布 ：初始疾病的概率 问题： 给定：某人症状为：咳嗽咽喉痛流涕发烧。 O = O1, O2 OT 计算：这个观察序列的概率P(O),HMM例子,方案1,输出条件独立假设,有限历史假设,P(A,B|C) = P(A|B,C)P(B|C),方案1,算法时间复杂度太高，需要,O(T*NT),方案2-向前算法,使用动态规划方法实现更加高效的算法 定义:向前变量 t时刻，输出序列O1, O2 Ot且状态xt=si的概率。,方案2-向前算法,P(A,B|C) = P(A|B,C)P(B|C),输出条件独立假设&有限历史假设,向前算法：图示,方案2-向前算法,1、初始化 2、递归 3、总合,2(1),2(2),2(3),2(N),3(1),向前算法图示,Trellis or Lattice(栅格),算法描述,从初始状态开始扩展 在t时刻扩展得到的状态必须能够产生观察序列在t时刻的输出 在t+1时刻，只能对在t时刻保留下来的状态节点进行扩展 每条路径上的概率做累乘，不同路径的概率做累加 直到观察序列全部考察完毕，算法结束,向前算法例,向前算法的计算复杂性,一般的计算方法的计算复杂性为O( T*NT ) 向前算法的计算复杂性为 O(N2T),方案3-向后算法,与向前算法类似，计算顺序相反。 定义向后变量 t时刻，状态xt = si情况下，模型输出序列Ot+1, ,OT 的概率。,P(A,B|C) = P(A|B,C)P(B|C),输出条件独立假设,向后算法图示,方案3-向后算法,后向算法 1、初始化 2、递归 3、总合,P(A,B|C) = P(A|B,C)P(B|C),向后算法的计算复杂性,向后算法的计算复杂性，与向前算法相同。 向后算法的计算复杂性为 O(N2T),问题2: Decoding（解码）,给定一个观察序列O = O1, O2OT ，模型=(A,B,) 解码问题：如何寻找最佳的状态序列 X=X1, X2XT 如果要枚举所有的状态序列，时间复杂度是O(NT) 解码算法 和向前算法相似，解码算法定义一个向前变量， 意义：t时刻沿着某一条路径到达状态si，且输出观察值O1Ot的最大概率 解码算法和向前算法区别：不是求和，而是最大值。,区别,Viterbi 算法,初始化： 递归： 结束： 路径回朔：,累计变量，记忆节点概率,返回指针，记忆返回路径,最优路径的概率,最优路径的终点状态,从终点状态，进行回朔，生成最优路经,1,2,3,states,Viterbi算法例,Viterbi算法思想,Viterbi能够找到最佳解，其思想精髓在于将全局最佳解的计算过程分解为阶段最佳解的计算。 Viterbi算法的时间复杂度：O(N2T),Viterbi算法思想,三重循环 第一重：遍历每一个观察值 第二重：遍历当前观察值所对应的每一个状态 第三重：遍历能够到达当前观察值当前状态的上一时刻的每一个状态 计算 假设上一时刻为t-1，t-1时刻的的状态为i，t时刻的状态为j，t时刻的观察值为k，则计算： t时刻状态j的返回指针指向t-1时刻的状态 输出 三重循环都结束后，在最后时刻找到值最大的终点状态，并从该状态开始，根据返回指针查找各时刻的处于最佳路径上的状态，反序输出。,问题3：HMM模型参数训练,根据： 可观察序列 初始的模型 优化模型参数： 寻找更好的模型 ，满足 优化三种模型参数 初始状态概率分布： 状态转移概率： 输出符号概率：,HMM：有监督学习,有监督学习方法： 最大似然估计方法（MLE） 在 上，标注状态 进行统计。 统计对象： 符号输出次数 状态转移次数 状态出现次数 用于计算 模型参数,HMM：无监督学习,HMM的状态序列通常是不可见的。换言之，由于缺少人工标注的状态数据，实际上很难用MLE直接估计模型参数。 HMM的参数训练一般采用无监督的参数学习方法。 Baum-Welch算法（向前-向后算法） 是一种EM (Expectation-Maximization)算法的特例 EM算法： 1、初始化模型参数 2、E 步骤：根据 ，遍历所有可能的状态序列，计算期望值。 3、M步骤：根据期望值，重估新的模型参数 4、新模型 代替旧模型 5、如果 ，训练结束。,E 步骤定义一组概率,状态转移概率： 定义：给定了整个观察序列O，在t时刻从状态si到状态sj转移的概率。 数学推导,P(A,B|C) = P(A|B,C)P(B|C),Baum-Welch算法图示,E 步骤定义一组概率,状态概率： 定义：给定了整个观察序列O，在t时刻，状态xt=si的出现概率。 数学推导,P(A,B|C) = P(A|B,C)P(B|C),E 步骤期望值,可观察到,M 步骤重估公式,词性标注,词性(Part of Speech),词的句法类别 词性集合： 名词、动词、形容词、副词、介词、助动词 开放词类(Open Class)和封闭词类(Closed Class) 可称为：语法类、句法类、POS标记、词类等 词的兼类现象 例如 打人 = 动词 一打衬衫 = 量词 词性标注 确定每个词在特定的句子中词性,POS举例,Penn Treebank词性集,POS歧义(在Brown语料库中),目前的性能,容易评价，只需计算标注正确的词性数量 目前准确率大约在97%左右 Baseline也可以达到90% Baseline算法: 对每一个词用它的最高频的词性进行标注 未登录词全部标为名词,词性标注的常用方法,词性标注（Part-of-Speech tagging） 回顾： 作用：句法分析的前期步骤 难点：兼类词处理 基于规则的词性标注 基于转换的错误驱动的词性标注 基于HMM的词性标注,基于HMM的词性标注,HMM模型 五元组(S, V, p ,A,B) S： 状态集合；词性集合 S=t1, tm. V ：输出符号集；词典 V=w1,wv. 模型参数= (A,B,) i : P(x1 = ti) 词性ti的初始概率 aij : P(tj|ti) 从词性ti到词性tj的转移概率 bjk: P(wk| tj) 从词性tj到词wk的输出概率 序列 观察序列：词汇序列：W = w1,w2wn 状态序列：词性序列： T = t1,t2tn,基于HMM的词性标注,词性标注 属于HMM的解码问题 给定观察序列和模型，求解最佳的状态序列。 具体任务 给定一个词序列 W = w1,w2wn 求解最佳的词性序列 T = t1,t2tn,基于HMM的词性标注,数学推导,输出条件独立性假设,有限历史假设,HMM：有指导的参数学习,模型的参数未知 假设有已经标注好的语料库: W = w1,w2wn T = t1,t2tn 如何从语料库中得到这样的参数 使用最大似然估计（MLE）,用带标记的语料进行训练,HMM：无指导的参数学习,语料库只是词的序列，没有人工标注词性。 完全无指导的学习是不可能的 至少要知道： 词性集 每个词可能的词性（根据词典） 使用Baum-Welch算法,词网