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

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

隐马尔科夫模型概述

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

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

MM Bigram MM(一阶MM)

MM Trigram MM(二阶MM)

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

HMM HMM，从状态产生输出

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

HMM HMM，从弧产生输出

HMM HMM，输出带有概率

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

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

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：根据观察序列寻找最佳参数模型

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

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

Trellis or Lattice(栅格)

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

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

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

Trigram的情况 以Bigram为状态

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

Class Trigram的Trellis 输出Y=“toy”

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

重叠的类Trigram的Trellis

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

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

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

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

Viterbi示例 argmaxXYZP(XYZ|rry)

Viterbi计算

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) 输出 三重循环都结束后，在最后时刻找到值最大的状态，并从该状态开始，根据返回指针查找各时刻的处于最佳路径上的状态，并反序输出。

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

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

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

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

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 ∞

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 ∞

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 ∞

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 ∞

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 ∞

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 ∞

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 ∞

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

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

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

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

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

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

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) 从右到左搜索过程中的累积值

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

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，直至结果不再有较大变化

词性标注

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

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

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

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, …)

Penn Treebank词性集 PRP PRP$

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

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)

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

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

词性标注 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)

有指导的学习 训练时事先对语料库进行了人工的词性标注，因此在训练时看到了状态（词性），属于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)：线性差值

用带标记的语料进行训练 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

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

无指导学习的秘诀 语料库(只有两个句子) 我们能够学习到什么？ 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

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

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

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

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

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

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

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

Viterbi算法举例

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

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

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

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

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

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

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

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

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

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

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

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

p n a n n c v d v v

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

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

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

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

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

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

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

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

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

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

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

谢谢！