7、HMM模型和词性标注.ppt

基于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,w2…wn 状态序列：词性序列： T = t1,t2…tn 基于HMM的词性标注 词性标注 属于HMM的解码问题 给定观察序列和模型，求解最佳的状态序列。 具体任务 给定一个词序列 W = w1,w2…wn 求解最佳的词性序列 T = t1,t2…tn 基于HMM的词性标注 数学推导 输出条件独立性假设 有限历史假设 HMM：有指导的参数学习 模型的参数未知 假设有已经标注好的语料库: W = w1,w2…wn T = t1,t2…tn 如何从语料库中得到这样的参数 使用最大似然估计（MLE） 用带标记的语料进行训练 HMM：无指导的参数学习 语料库只是词的序列，没有人工标注词性。 完全无指导的学习是不可能的 至少要知道： 词性集 每个词可能的词性（根据词典） 使用Baum-Welch算法 词网格 词网格： 对于输入的词序列，根据语法词典，列出每个词可能的词性候选，构成词网格，即状态空间。（是完整的栅格状态空间的子空间） 采用Viterbi算法有哪些信誉好的足球投注网站词网格，有哪些信誉好的足球投注网站最佳路径（词性序列、状态序列）。 计算相关概率时，取-log对数形式，目的是将乘法运算变成加法运算。 同时，将求最大概率的路径问题转换成求最小费用的路径问题。 词网格 Viterbi解码算法 定义向前变量： 计算第一列 计算第t列 选择最优路径 路径回朔 Viterbi有哪些信誉好的足球投注网站——例子 3.15 小结 谢谢！ 本课件参考了哈工大关毅教授和刘挺教授的课件 向前算法：图示 方案2-向前算法 1、初始化 2、递归 3、总合 State T 1 2 3 1 2 3 N ?2(1) ?2(2) ?2(3) ?2(N) ?3(1) ?3(2) ?3(3) ?3(N) ?1(1) ?1(2) ?1(N) ?1(3) ?T(N) ?T(3) ?T(2) ?T(1) 向前算法——图示 Trellis or Lattice(栅格) 算法描述 从初始状态开始扩展 在t时刻扩展得到的状态必须能够产生观察序列在t时刻的输出 在t+1时刻，只能对在t时刻保留下来的状态节点进行扩展 每条路径上的概率做累乘，不同路径的概率做累加 直到观察序列全部考察完毕，算法结束 向前算法例 R R G B 1×.6 .6 0×.2 .0 0×.0 .0 .6 .2 .2 .2 .5 .3 .0 .3 .7 R G B .5 .6 .4 .4 .1 ? =[1 0 0]T .5×.6 .18 .6×.2 .048 .0 .4×.2 .1×.0 .4×.0 .5×.2 .018 .6×.5 .0504 .01116 .4×.5 .1×.3 .4×.3 .5×.2 .0018 .6×.3 .01123 .01537 .4×.3 .1×.7 .4×.7 向前算法的计算复杂性 一般的计算方法的计算复杂性为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, O2…OT ，模型μ=(A,B,?) 解码问题：如何寻找最佳的状态序列 X=X1, X2…XT 如果要枚举所有的状态序列，时间复杂度是O(NT) 解码算法 和向前算法相似，解码算法定义一个向前变量， 意义：t时刻沿着某一条路径到达状态si，且输出观察值O1…Ot的最大概率 解码算法和向前算法区别：不是求和，而是最大值。 区别 Viterbi 算法 初始化： 递归： 结束： 路径回朔： 累计变量，记忆节点概率 返回指针，记忆返回路径 最优路径的概率 最优路径的终点状态 从终点状态，进行回朔，生成最优路经 1 2 3 states Viterbi算法例 .6 .2 .