词性标注与隐马尔可夫模型 戴新宇 2006-11-17.

Presentation on theme: "词性标注与隐马尔可夫模型 戴新宇 2006-11-17."— Presentation transcript:

1 词性标注与隐马尔可夫模型 戴新宇

2 概要 词性标注 HMM模型 HMM模型用于词性标注 相关问题讨论

3 词性标注 定义及任务描述 词性标注的问题 － 标注歧义 （兼类词） 词性标注之重要性 词性标注方法

4 词性标注任务描述 什么叫词性？ 划分词类的依据 汉语的词类划分 词性标注：给某种语言的词标注上其所属的词类
词性又称词类，是指词的语法分类，或者说是按照其各自的语法功能的不同而分出来的类别 划分词类的依据 词的形态、词的语法意义、词的语法功能 汉语的词类划分 词性标注：给某种语言的词标注上其所属的词类 The lead paint is unsafe. The/Det lead/N paint/N is/V unsafe/Adj. 他有较强的领导才能。 他/代词 有/动词 较/副词 强/形容词 的/助词 领导/名词 才能/名词。

5 词性标注问题 － 词性标注歧义（兼类词） 一个词具有两个或者两个以上的词性 英文的Brown语料库中，10.4%的词是兼类词 汉语兼类词
词性标注问题 － 词性标注歧义（兼类词） 一个词具有两个或者两个以上的词性 英文的Brown语料库中，10.4%的词是兼类词 The back door On my back Promise to back the bill 汉语兼类词 把门锁上， 买了一把锁 他研究与自然语言处理相关的研究工作 汉语词类确定的特殊难点 对兼类词消歧－ 词性标注的任务

6 词性标注的应用及重要性 机器翻译 Text – Speech 词法句法规则 － 词性组合 句法分析的预处理 统计自然语言处理的基础

7 词性标注常见方法 规则方法： 统计方法 基于错误驱动的方法 词典提供候选词性 人工整理标注规则 决策树方法（Schmid 1994）
寻找概率最大的标注序列 如何建立统计模型 P( tag, word ) HMM方法（Garside et al. 1987,Church 1988） 决策树方法（Schmid 1994） 最大墒方法（Ratnaparkhi 1996） 基于错误驱动的方法 错误驱动学习规则 利用规则重新标注词性

8 词性标注的性能指标 性能指标：标注准确率 当前方法正确率可以达到97% 正确率基线(Baseline)可以达到90% 基线的做法：
给每个词标上它最常见的词性 所有的未登录词标上名词词性

9 决定一个词词性的因素 从语言学角度：由词的用法以及在句中的语法功能决定 统计学角度： 和上下文的词性（前后词的标注）相关
和上下文单词（前后词）相关

10 隐马尔可夫模型 － 概要 背景 马尔可夫模型 隐马尔可夫模型 模型评估 解码 模型参数学习

11 背景 俄国统计学家Andrei Markov（1856-1922）提出
Studied temporal probability models Real-world Observed output (signals) Signal Models – stimulate the signals source and learn as much as possible through simulations

12 马尔可夫模型 举例说明马尔可夫模型 马尔可夫假设

13 马尔可夫模型示例 － 天气预报 状态：雨、多云、晴 给定不同天气之间的转换概率，预测未来数天的天气
通过如右图所示的矩阵描述状态之间的转移概率

14 马尔可夫模型示例 － 天气预报 通过有限状态自动机描述状态转移概率

15 预测 － 计算未来天气 （序列的概率） 晴-晴-雨-雨-晴-多云-晴，未来七天天气是这种情况的概率

16 马尔可夫假设 假设1 有限视野 P(Ot+1=Sk|O1,…Ot) = P(Ot+1=Sk|Ot-(n-1),…Ot)
(n-1)th 阶马尔可夫链 → n 元语言模型 假设2 时间独立性 P(Ot+1=Sk|Ot) = P(O2=Sk|O1)

17 隐马尔可夫模型 － Hidden Markov Model (HMM)
介绍 定义 隐马模型应用于词性标注

18 HMM模型的简单介绍 “隐”在何处？ HMM是一阶马尔可夫模型的扩展 相对于markov模型的又一假设：输出独立性
状态（序列）是不可见的（隐藏的） HMM是一阶马尔可夫模型的扩展 观察值与状态之间存在概率关系 隐藏的状态序列满足一阶马尔可夫模型 相对于markov模型的又一假设：输出独立性

19 HMM的定义 定义：一个HMM模型 λ=(A,B,π) S是状态集， S=(S1,S2,…SN) V是观察集， V=(V1,V2,…VM)
状态序列Q = q1q2…qT （隐藏） ，观察序列O=o1o2…oT （可见） A是状态转移概率分布A=[aij], aij=P(qt=sj|qt-1=si) (满足假设1.) B是观察值生成概率分布B=[bj(vk)], bj(vk)=P(ot=vk|qt=si) (满足假设2、3) 初始观察值概率分布 Π= [πi], πi =P(q1=si)

20 词性标注的HMM模型定义 HMM：S V A B π S：预先定义的词性标注集 V：文本中的词汇 A：词性之间的转移概率
例，P(我|“代词”) π ：初始概率 基于构建的HMM，利用某些算法，寻找一个最合适的词性标注序列，即为一个词串上的每个词标注上词性。 注：可见的观察序列为w1w2…wT

21 Pos tagging using HMM 模型解码(Decoding) 模型参数学习(Learning)
给定模型和一个观测序列，寻求一个产生这个观测序列的可能性最大的状态序列 给定词序列w1w2…wT （可见的观察序列），寻求产生这个词序列的最可能的词性标注序列Pos1Pos2…PosT （隐藏的状态序列） 如何发现“最优”状态序列能够“最好地解释”观察序列 需要高效算法，Viterbi算法 模型参数学习(Learning)

22 Trellis representation of an HMM
si sN s1 s2 si sN s1 s2 sj sN s1 s2 si sN a1j a2j aij aNj Time= w t wt t+1 wt T wT

23 计算观察序列对应某一状态序列的概率 模型λ，观察序列O，假设对应状态序列为Q，计算该状态序列存在的可能性：
简单的方法，计算所有可能的状态序列，O(NT)

24 Viterbi算法 一种更有效率的利用动态规划思想的算法
定义一个变量t(i) ，指在时间t时，HMM沿着某一条路径到达Si，并输出序列为w1w2…wt 的最大概率

25 利用Viterbi算法的求解过程 初始化： 迭代： 迭代结束 回溯记录最优路径：

26 Viterbi算法时间复杂度 每计算一个 ，必须考虑从t-1时刻所有的N个状态转移到状态的si概率，时间复杂度为O(N)，对应每个时刻t，要计算N个中间变量 时间复杂度为O(N2)，又t从1…T，因此整个前向算法时间复杂度为O(N2T)

27 模型参数学习 给定状态集S和观察集V，学习模型参数A、B、π 模型参数学习过程就是构建模型的过程
有指导的学习－最大似然估计（标注了词性的语料库） 无指导的学习－Welch-Baum （未标注词性的语料库）

28 有指导学习模型参数 － 从标注语料中学习 最大似然估计 对于无标注的语料库（状态不可见）如何获取模型参数？

29 无指导学习模型参数 － Welch-Baum 算法
迭代估计参数，使得 此时λ最能拟合训练数据 Baum证明：随着迭代过程，

30 无指导学习模型参数 － Welch-Baum 算法
基本思想：随机给出模型参数的初始化值，得到最初的模型λ0，然后利用初始模型λ0得到某一状态转移到另一状态的期望次数，然后利用期望次数对模型模型进行重新估计，由此得到模型λ1，如此循环迭代，重新估计，直至模型参数收敛（模型最优）。 通过对模型的评估实现模型的最优化 － 模型使得训练数据存在概率最大化 评估能够反映模型预测生成观察序列的能力

31 HMM模型的评估 给定一个HMM λ和一个观察序列，计算该序列存在的概率 － 对所有可能生成该序列的状态序列的概率求和 计算复杂度高

32 评估模型 类似Veterbi动态规划算法 前向算法： 后向算法： 定义前向概率:观察值为o1o2…ot,t时刻对应的状态值为si的概率 迭代
模型评估结果 后向算法： 定义后向概率:观察值为otot+1…oT,t时刻对应的状态值为si的概率

33 Welch-Baum算法的参数估计 How to calculate Expected Number?
定义一个变量 ，对应于观察序列o1o2…oT，假设在t时刻的状态是si，t+1时刻的状态是sj的概率。

34 Welch-Baum算法的参数估计（续）
定义一个变量 ，对应于观察序列o1o2…oT，假设在t时刻的状态是si的概率。

35 无指导学习模型参数 － Welch-Baum 算法（二）
赋aij , bi(vk)的初始值 反复迭代，直到收敛

36 词性标注HMM的参数估计 状态转移概率（词性－词性的概率） e.g. P(N|V) 生成概率（词性－词的概率）
利用词性标注语料库获取状态转移概率和生成概率（最大似然估计） 利用无标注语料库获取状态转移概率和生成概率（ Welch-Baum 算法） 平滑 未登录词处理

37 隐马模型的其它应用 语音识别 基因排序 乐谱生成 ……

38 HMM HMM model λ 评估 建模(参数估计) 解码(寻求最有序列) Viterbi 前向后向算法 最大似然估计
Welch-Baum Viterbi 解码(寻求最有序列)

39 讨论的几个问题 最大似然估计的效果 词性标注中S、V的选取，为何选择词性标注集作为状态集S？选择词汇集作为观察集V？
如何利用词典减少计算量？ 如何处理未登录词？平滑

40 Project 利用隐马尔可夫模型进行汉语词性标注 （提供词性标注训练集）