隐马尔科夫模型和词性标注.

Presentation on theme: "隐马尔科夫模型和词性标注."— Presentation transcript:

1 隐马尔科夫模型和词性标注

2 大纲 隐马尔科夫模型 词性标注 隐马尔科夫模型概述 任务1：计算观察序列的概率 任务2：计算能够解释观察序列的最大可能的状态序列
任务3：根据观察序列寻找最佳参数模型 词性标注

3 隐马尔科夫模型概述

4 马尔科夫链 状态序列: X1, X2, X3, … 常常是“时序”的 从Xt-1到Xt的转换只依赖于Xt-1 X1 X2 X3 X4

5 转移概率 Transition Probabilities
假设一个状态Xt有N个可能的值 Xt=s1, Xt=s2,….., Xt=sN. 转移概率的数量为：N2 P(Xt=si|Xt-1=sj), 1≤ i, j ≤N 转移概率可以表示为N×N的矩阵或者有向图

6 MM Bigram MM(一阶MM)

7 MM Trigram MM(二阶MM)

8 有限状态自动机 状态：输入输出字母表中的符号 弧：状态的转移 仍然是VMM (Visible MM)

9 HMM HMM，从状态产生输出

10 HMM HMM，不同状态可能产生相同输出

11 HMM HMM，从弧产生输出

12 HMM HMM，输出带有概率

13 HMM HMM，两个状态间有多条弧，具有不同的概率

14 隐马尔可夫模型 Hidden Markov Model
估算隐藏于表面事件背后的事件的概率 观察到一个人每天带雨伞的情况，反过来推测天气情况

15 Hidden Markov Model HMM是一个五元组(S, S0,Y, Ps, PY ).
S : {s1…sT }是状态集，S0是初始状态 Y : {y1…yV }是输出字母表 PS(sj|si):转移(transition)概率的分布，也表示为aij PY(yk|si,sj): 发射(emission)概率的分布，也表示为bijk 给定一个HMM和一个输出序列Y={y1,y2,…,yk) 任务1：计算观察序列的概率 任务2：计算能够解释观察序列的最大可能的状态序列 任务3：根据观察序列寻找最佳参数模型

16 任务1：计算观察序列的概率

17 计算观察序列的概率 前提：HMM模型的参数已经训练完毕 想知道：根据该模型输出某一个观察序列的概率是多少
应用：基于类的语言模型，将词进行归类，变计算词与词之间的转移概率为类与类之间的转移概率，由于类的数量比词少得多，因此一定程度避免了数据稀疏问题

18 Trellis or Lattice(栅格)

19 发射概率为1的情况 Y=“toe” P(Y)=0.6×0.88×1+0.4×0.1×1=0.568

20 算法描述 从初始状态开始扩展 在时间点t扩展得到的状态必须能够产生与观察序列在t时刻相同的输出
比如在t=1时，观察序列输出‘t’，因此只有状态A和C得到了扩展 在t+1时刻，只能对在t时刻保留下来的状态节点进行扩展 比如在t=2时，只能对t=1时刻的A和C两个状态进行扩展 每条路径上的概率做累乘，不同路径的概率做累加 直到观察序列全部考察完毕，算法结束

21 发射概率不为1的情况 就是在上述模型下“toe”出现的概率

22 Trigram的情况 以Bigram为状态

23 基于类的Trigram模型 N-gram class LM p(wi|wi-2,wi-1) p(wi|ci)p(ci|ci-2,ci-1)
C:Consonant(辅音)，V:Vowel(元音)

24 Class Trigram的Trellis
输出Y=“toy”

25 重叠(overlapping) 的Class Trigram
“r”有时是元音，有时是辅音，因此p(r|C)和p(r|V)都不为零

26 重叠的类Trigram的Trellis

27 讨论 我们既可以从左向右计算，也可以从右向左计算，甚至可以从中间向两头计算
Trellis的计算对于Forward-Backward（也称为Baum-Welch)参数估计很有用

28 任务2：计算能够解释观察序列的最大可能的状态序列

29 Viterbi算法 用于搜索能够生成观察序列的最大概率的状态序列 Sbest=argmaxSP(S|Y)
=argmaxSP(S,Y)/P(Y) =argmaxS∏i=1…kp(yi|si,si-1)p(si|si-1) Viterbi能够找到最佳解，其思想精髓在于将全局最佳解的计算过程分解为阶段最佳解的计算

30 示意 从D2返回Stage 1的最佳状态为C1 尽管搜索还没有完全结束，但是D2已经找到了最佳返回节点
因为p(A1-D2)=0.60.5=0.3 而p(C1-D2)=0.40.8=0.32 尽管搜索还没有完全结束，但是D2已经找到了最佳返回节点

31 Viterbi示例 argmaxXYZP(XYZ|rry)

32 Viterbi计算

33 Viterbi算法 三重循环 计算 输出 第一重：遍历每一个观察值 第二重：遍历当前观察值所对应的每一个状态
第三重：遍历能够到达当前观察值当前状态的上一时刻的每一个状态 计算 假设上一时刻为t，t时刻的的状态为i，t+1时刻的状态为j，t+1时刻的观察值为k，则计算： j(t+1)=max1iNi(t)aijbijk j(t+1)=argmax1iNi(t)aijbijk t+1时刻状态j的返回指针指向t时刻的状态j(t+1) 输出 三重循环都结束后，在最后时刻找到值最大的状态，并从该状态开始，根据返回指针查找各时刻的处于最佳路径上的状态，并反序输出。

34 N-best计算 保留n个最佳结果，而不是1个 最优解：VCV；次优解：CCV

35 N-Best Paths 以分词为例（MM模型） 例句：“结合成分子”
每条弧上的值是该弧所对应的词的Unigram概率的负对数，即-logp(w) 结 合 成 分 子

36 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre ∞ value pre ∞ value pre ∞ value pre ∞ value pre ∞

37 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre ∞ value pre ∞ value pre ∞ value pre ∞

38 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre 7.76 ∞ value pre ∞ value pre ∞ value pre ∞

39 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre 7.76 20.0 1 ∞ value pre ∞ value pre ∞ value pre ∞

40 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre 7.76 20.0 1 ∞ value pre 21.5 1 ∞ value pre ∞ value pre ∞

41 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre 7.76 20.0 1 ∞ value pre 14.4 2 21.5 1 27.6 ∞ value pre ∞ value pre ∞

42 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre 7.76 20.0 1 ∞ value pre 14.4 2 21.5 1 27.6 ∞ value pre 18.2 2 30.5 ∞ value pre ∞

43 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre 7.76 20.0 1 ∞ value pre 14.4 2 21.5 1 27.6 ∞ value pre 18.2 2 23.4 3 30.0 30.5 value pre ∞

44 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre 7.76 20.0 1 ∞ value pre 14.4 2 21.5 1 27.6 ∞ value pre 18.2 2 23.4 3 30.0 30.5 value pre 25.2 3 31.2 ∞

45 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre 7.76 20.0 1 ∞ value pre 14.4 2 21.5 1 27.6 ∞ value pre 18.2 2 23.4 3 30.0 30.5 value pre 25.2 3 29.1 4 31.2 33.9

46 N-Best Paths A sample The sentence “结合成分子 “. 结 合 成 分 子 value pre value
结 合 成 分 子 value pre value Pre 10.1 ∞ value pre 7.76 20.0 1 ∞ value pre 14.4 2 21.5 1 27.6 ∞ value pre 18.2 2 23.4 3 30.0 30.5 value pre 25.2 3 29.1 4 31.2 33.9

47 结果 四条最佳路径为： 时间复杂度 1. 结合/成/分子 2. 结合/成分/子 3. 结/合成/分子 4. 结合/成/分/子
假设搜索图中共有k条边 要求获得N条最佳路径 则时间复杂度为O(k*N2)

48 剪枝Pruning 在每一个时刻，如果Trellis上的状态过多，怎么办？ 答案是剪枝： 1、按的阈值剪枝， 太低的路径不再继续搜索
2、按状态的数量剪枝，超过多少个状态就不再扩展了

49 任务3：根据观察序列寻找最佳参数模型

50 问题 给定一个观察值序列，但是没有标注每个观察值所对应的状态（无指导），在这种条件下如何估计隐马尔可夫模型中的参数，包括转移概率的分布和发射概率的分布 例如：给定一个语料库，语料库只是一个词的序列，没有词性标记，能否估计出词性标注的HMM模型？ 是EM算法的特例，象一个魔法(MAGIC)！找到一个能够最佳地解释观察值序列的模型

51 Baum-Welch算法 也称为Forward-Backward算法
1. 初始化PS，PY 可能是随机给出的 2. 计算前向概率(Forward Probability) (s’,i)=∑ss’(s,i-1)×p(s’|s)×p(yi|s,s’) 从左到右搜索过程中的累积值 3. 计算后向概率(Backward Probability) (s’,i)=∑s’s (s,i+1)×p(s|s’)×p(yi+1|s’,s) 从右到左搜索过程中的累积值

52 前向概率后向概率示意图 bj(t+1) Xt+1=sj ai(t) Xt=si aijbijk t-1 t t+1 t+2 观察值为k

53 Baum-Welch算法（续） 4. 计数(pseudo count ) 5. 重新估算 6. 重复运行2-5，直至结果不再有较大变化
c(y,s,s’)= ∑i=0…k-1,y=yi+1(s,i)p(s’|s)p(yi+1|s,s’)(s’,i+1) c(s,s’)=∑y∈Yc(y,s,s’) c(s)=∑s∈Sc(s,s’) 5. 重新估算 p’(s’|s)=c(s,s’)/c(s), p’(y|s,s’)=c(y,s,s’)/c(s,s’) 6. 重复运行2-5，直至结果不再有较大变化

54 词性标注

55 词性(Part of Speech) 词的句法类别 名词、动词、形容词、副词、介词、助动词
分为开放词类(Open Class)和封闭词类(Closed Class) 也成为：语法类、句法类、POS标记、词类等

56 POS举例 N noun baby, toy V verb see, kiss
开放类 N noun baby, toy V verb see, kiss ADJ adjective tall, grateful, alleged ADV adverb quickly, frankly, ... P preposition in, on, near DET determiner the, a, that WhPron wh-pronoun who, what, which, … COORD coordinator and, or

57 替代性测试 两个词属于同一个词类，当且仅当它们相互替换时不改变句子的语法特征 The _____ is angry.（名词）
The ____ dog is angry.（形容词） Fifi ____ .（不及物动词） Fifi ____ the book.（及物动词）

58 POS Tags 不存在标准的词性标注集 有的是用比较粗糙的标记集，例如：N, V, A, Aux, ….
有的使用更细致的分类：(例如： Penn Treebank) PRP: personal pronouns (you, me, she, he, them, him, her, …) PRP$: possessive pronouns (my, our, her, his, …) NN: singular common nouns (sky, door, theorem, …) NNS: plural common nouns (doors, theorems, women, …) NNP: singular proper names (Fifi, IBM, Canada, …) NNPS: plural proper names (Americas, Carolinas, …)

59 Penn Treebank词性集 PRP PRP$

60 词性标注 词常常有多个词性，以back为例 词性标注问题就是针对确定词在一个特定实例中的词性 The back door = JJ
On my back = NN Win the voters back = RB Promised to back the bill = VB 词性标注问题就是针对确定词在一个特定实例中的词性

61 POS歧义 (在Brown语料库中) 无歧义的词(1 tag): 35,340个 有歧义的词 (2-7 tags): 4,100个
3,760 3 tags 264 4 tags 61 5 tags 12 6 tags 2 7 tags 1 (Derose, 1988)

62 词性标注的应用 文语转换 是句法分析的基础 辅助词义消歧 怎样朗读”lead” 等，动词等待 等，量词等级 动词一般形式：[li:d]
过去式：[led] 是句法分析的基础 辅助词义消歧 等，动词等待 等，量词等级

63 目前的性能 容易评价，只需计算标注正确的词性数量 目前准确率大约在97%左右 Baseline也可以达到90% Baseline算法:
对每一个词用它的最高频的词性进行标注 未登录词全部标为名词

64 词性标注 P(T|W)=P(W|T)P(T)/P(W) argmaxTp(T|W)=argmaxTp(W|T)p(T)
P(W|T)=∏i=1…dp(wi|w1,…,wi-1,t1,…,td) p(wi|w1,…,wi-1,t1,…,td) ≌p(wi|ti) P(T)=∏i=1…dp(ti|t1,…,ti-1) p(ti|t1,…,ti-1)=p(ti|ti-n+1,…,ti-1)

65 有指导的学习 训练时事先对语料库进行了人工的词性标注，因此在训练时看到了状态（词性），属于VMM，在测试时，只能看到观察值（词序列），因此属于HMM。 应用最大似然估计 p(wi|ti)=cwt(ti,wi)/ct(ti) p(ti|ti-n+1,…,ti-1) =ctn(ti-n+1,…,ti-1,ti)/ct(n-1)(ti-n+1,…,ti-1) 平滑 p(wi|ti)：加1平滑 p(ti|ti-n+1,…,ti-1)：线性差值

66 用带标记的语料进行训练 Pierre/NNP Vinken/NNP , , 61/CD years/NNS old/JJ ,/, will/MD join/VB the/DT board/NN as/IN a/DT nonexecutive/JJ director/NN Nov./NNP 29/CD ./. Mr./NNP Vinken/NNP is/VBZ chairman/NN of/IN Elsevier/NNP N.V./NNP ,/, the/DT Dutch/NNP publishing/VBG group/NN . . Rudolph/NNP Agnew/NNP ,/, 55/CD years/NNS old/JJ and/CC former/JJ chairman/NN of/IN Consolidated/NNP Gold/NNP Fields/NNP PLC/NNP ,/, was/VBD named/VBN a/DT nonexecutive/JJ director/NN of/IN this/DT British/JJ industrial/JJ conglomerate/NN ./. c(JJ)=7 c(JJ, NN)=4, P(NN|JJ)=4/7

67 无指导的学习 语料库只是词的序列，没有人工标注词性，是Plain Text。 完全无指导的学习是不可能的 使用Baum-Welch算法
至少要知道： 词性集 每个词可能的词性（据词典） 使用Baum-Welch算法

68 无指导学习的秘诀 语料库(只有两个句子) 我们能够学习到什么？ A lion ran to the rock D N V P D N
Aux V The cat slept on the mat D N V P D N V R 我们能够学习到什么？ D, N, V的概率大于D, V, V，Cat应该标注为N V, P, D的概率大于V, Aux, D或V, R, D，因此to和on应标为P

69 未登录词 考虑所有词性 只考虑开放类词性 根据未登录词的前缀和后缀猜测其词性 Uniform（平均分配概率）
Unigram（考虑每个词性独立出现的概率） 根据未登录词的前缀和后缀猜测其词性

70 运行词性标注器 无论是对有指导的学习，还是对无指导的学习，在搜索阶段都一样：使用Viterbi算法！

71 nh n n a n c 9.89 n n p v a d v v Πn=2.52 bn(人民)=7.37

72 nh n n a n c 9.89 20.02 n n p v a d v v bn(收入)=6.98 ann=2.76

73 60.02 nh n n a n c 9.89 20.02 n n p v a d v v bnh(和)=20 an nh=20

74 nh n n a n c n n p v a d v v bc(和)=1.72 an c=3.58 60.02 25.32 9.89
20.02 n n p v a d v v bc(和)=1.72 an c=3.58

75 nh n n a n c n n p v a d v v bn(生活)=5.75 anh n=20 60.02 85.77 25.32
9.89 20.02 n n 27.66 p v a d v 31.26 v bn(生活)=5.75 anh n=20

76 Viterbi算法举例

77 nh n n a n c 9.89 n n p v a d v v Πn=2.52 bn(人民)=7.37

78 nh n n a n c 9.89 20.02 n n p v a d v v bn(收入)=6.98 ann=2.76

79 60.02 nh n n a n c 9.89 20.02 n n p v a d v v bnh(和)=20 an nh=20

80 nh n n a n c n n p v a d v v bn(生活)=5.75 anh n=20 60.02 85.77 25.32
9.89 20.02 n n 27.66 p v a d v 31.26 v bn(生活)=5.75 anh n=20

81 nh n n a n c n n p v a d v v bn(生活)=5.75 ac n=1.84 60.02 85.77 25.32
9.89 20.02 32.91 n n 27.66 p v a d v 31.26 v bn(生活)=5.75 ac n=1.84

82 nh n n a n c n n p v a d v v bn(生活)=5.75 ap n=1.28 60.02 85.77 25.32
9.89 20.02 32.91 n n 27.66 p 34.69 v a d v 31.26 v bn(生活)=5.75 ap n=1.28

83 nh n n a n c n n p v a d v v bn(生活)=5.75 av n=1.92 60.02 85.77 25.32
9.89 20.02 32.91 n n 27.66 p 34.69 v a d v 31.26 v 38.93 bn(生活)=5.75 av n=1.92

84 60.02 nh 85.77 n n a n 25.32 c 9.89 20.02 32.91 n n 27.66 p 34.69 v a d v 31.26 v 38.93

85 60.02 nh 32.91 n n a n 25.32 c 9.89 20.02 n n 27.66 p v a d v 31.26 v

86 60.02 nh 32.91 n n a n 25.32 c 9.89 20.02 n n 27.66 p 34.6 v a d v 31.26 v

87 60.02 nh 32.91 43.16 55.71 68.15 n n a n 25.32 c 9.89 20.02 n n 27.66 p 34.6 56.74 52.67 60.76 v a d v 31.26 v

88 60.02 nh 32.91 43.16 55.71 68.15 n n a n 25.32 c 9.89 20.02 n n 27.66 p 34.6 56.74 52.67 60.76 v a d v 31.26 v 人民/n 收入/n 和/c 生活/n 水平/n 进一步/d 提高/v

89 p n a n n c v d v v

90 N-Best结果 p n a n n -1 6.98 c v d v v

91 p 00 14.62 n a n n -1 6.98 c 00 12.28 v d v v 00 18.22

92 p 00 14.62 n 10 19.87 00 21.65 20 25.89 a n n -1 6.98 c 00 12.28 v d v v 00 18.22

93 p 00 14.62 n 10 19.87 00 21.65 20 25.89 a n n -1 6.98 c 00 12.28 v 10 20.86 00 23.9 20 27.61 d v v 00 18.22

94 p 00 14.62 n 10 19.87 00 21.65 20 25.89 a 00 32.42 01 34.2 10 36.16 n n -1 6.98 c 00 12.28 v 10 20.86 00 23.9 20 27.61 d v v 00 18.22

95 p 00 14.62 n 10 19.87 00 21.65 20 25.89 a 00 32.42 01 34.2 10 36.16 n n -1 6.98 c 00 12.28 v 10 20.86 00 23.9 20 27.61 d 00 29.38 01 31.16 10 31.38 v v 00 18.22

96 p 00 14.62 n 10 19.87 00 21.65 20 25.89 a 00 32.42 01 34.2 10 36.16 n 10 44.59 00 44.88 11 46.37 n -1 6.98 c 00 12.28 v 10 20.86 00 23.9 20 27.61 d 00 29.38 01 31.16 10 31.38 v 10 37.47 11 39.25 12 39.47 v 00 18.22

97 p 00 14.62 n 10 19.87 00 21.65 20 25.89 a 00 32.42 01 34.2 10 36.16 n 10 44.59 00 44.88 11 46.37 n -1 6.98 c 00 12.28 v 10 20.86 00 23.9 20 27.61 d 00 29.38 01 31.16 10 31.38 v 10 37.47 11 39.25 12 39.47 v 00 18.22

98 p 00 14.62 n 10 19.87 00 21.65 20 25.89 a 00 32.42 01 34.2 10 36.16 n 10 44.59 00 44.88 11 46.37 n -1 6.98 c 00 12.28 v 10 20.86 00 23.9 20 27.61 d 00 29.38 01 31.16 10 31.38 v 10 37.47 11 39.25 12 39.47 v 00 18.22

99 p 00 14.62 n 10 19.87 00 21.65 20 25.89 a 00 32.42 01 34.2 10 36.16 n 10 44.59 00 44.88 11 46.37 n -1 6.98 c 00 12.28 v 10 20.86 00 23.9 20 27.61 d 00 29.38 01 31.16 10 31.38 v 10 37.47 11 39.25 12 39.47 v 00 18.22

100 N-Best Search结果 1)收入/n 和/c 生活/n 进一步/d 提高/v 37.47
2)收入/n 和/p 生活/n 进一步/d 提高/v 39.25 3)收入/n 和/c 生活/v 进一步/d 提高/v 39.47

101 谢谢！