词性标注与隐马尔可夫模型

1词性标注与隐马尔可夫模型戴新宇2006-11-172概要词性标注HMM模型HMM模型用于词性标注相关问题讨论3词性标注定义及任务描述词性标注的问题－标注歧义（兼类词）词性标注之重要性词性标注方法4词性标注任务描述什么叫词性？词性又称词类，是指词的语法分类，或者说是按照其各自的语法功能的不同而分出来的类别划分词类的依据词的形态、词的语法意义、词的语法功能汉语的词类划分词性标注：给某种语言的词标注上其所属的词类Theleadpaintisunsafe.The/Detlead/Npaint/Nis/Vunsafe/Adj.他有较强的领导才能。他/代词有/动词较/副词强/形容词的/助词领导/名词才能/名词。5词性标注问题－词性标注歧义（兼类词）一个词具有两个或者两个以上的词性英文的Brown语料库中，10.4%的词是兼类词ThebackdoorOnmybackPromisetobackthebill汉语兼类词把门锁上，买了一把锁他研究与自然语言处理相关的研究工作汉语词类确定的特殊难点对兼类词消歧－词性标注的任务6词性标注的应用及重要性机器翻译Text–Speech词法句法规则－词性组合句法分析的预处理统计自然语言处理的基础7词性标注常见方法规则方法：词典提供候选词性人工整理标注规则统计方法寻找概率最大的标注序列如何建立统计模型P(tag,word)HMM方法（Garsideetal.1987,Church1988）决策树方法（Schmid1994）最大墒方法（Ratnaparkhi1996）基于错误驱动的方法错误驱动学习规则利用规则重新标注词性8词性标注的性能指标性能指标：标注准确率当前方法正确率可以达到97%正确率基线(Baseline)可以达到90%基线的做法：给每个词标上它最常见的词性所有的未登录词标上名词词性9决定一个词词性的因素从语言学角度：由词的用法以及在句中的语法功能决定统计学角度：和上下文的词性（前后词的标注）相关和上下文单词（前后词）相关10隐马尔可夫模型－概要背景马尔可夫模型隐马尔可夫模型模型评估解码模型参数学习11背景俄国统计学家AndreiMarkov（1856-1922）提出StudiedtemporalprobabilitymodelsReal-worldObservedoutput(signals)SignalModels–stimulatethesignalssourceandlearnasmuchaspossiblethroughsimulations12马尔可夫模型举例说明马尔可夫模型马尔可夫假设13马尔可夫模型示例－天气预报状态：雨、多云、晴给定不同天气之间的转换概率，预测未来数天的天气通过如右图所示的矩阵描述状态之间的转移概率0.40.30.3{}0.20.60.20.10.10.8ijAa14马尔可夫模型示例－天气预报通过有限状态自动机描述状态转移概率15预测－计算未来天气（序列的概率）晴-晴-雨-雨-晴-多云-晴，未来七天天气是这种情况的概率3311323333131131233233331111332(|)(,,,,,,|)(|)*(|)*(|)**(|)*(|)*(|)*(|)******POModelPSSSSSSSModelPSBeginPSSPSSPSSPSSPSSPSSaaaaa2350.33*0.8*0.1*0.4*0.3*0.1*0.26.336*10a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隐马尔可夫模型－HiddenMarkovModel(HMM)介绍定义隐马模型应用于词性标注18HMM模型的简单介绍“隐”在何处？状态（序列）是不可见的（隐藏的）HMM是一阶马尔可夫模型的扩展观察值与状态之间存在概率关系隐藏的状态序列满足一阶马尔可夫模型相对于markov模型的又一假设：输出独立性11(,...|,...)(|)TTttTPOOSSOSP19HMM的定义定义：一个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：SVABπS：预先定义的词性标注集V：文本中的词汇A：词性之间的转移概率B：某个词性生成某个词的概率例，P(我|“代词”)π：初始概率基于构建的HMM，利用某些算法，寻找一个最合适的词性标注序列，即为一个词串上的每个词标注上词性。注：可见的观察序列为w1w2…wT21PostaggingusingHMM模型解码(Decoding)给定模型和一个观测序列，寻求一个产生这个观测序列的可能性最大的状态序列给定词序列w1w2…wT（可见的观察序列），寻求产生这个词序列的最可能的词性标注序列Pos1Pos2…PosT（隐藏的状态序列）如何发现“最优”状态序列能够“最好地解释”观察序列需要高效算法，Viterbi算法模型参数学习(Learning)22TrellisrepresentationofanHMMs1s2sisNs1s2sisNs1s2sjsNs1s2sisNa1ja2jaijaNjTime=1w1twtt+1wt+1TwT23计算观察序列对应某一状态序列的概率模型λ，观察序列O，假设对应状态序列为Q，计算该状态序列存在的可能性：简单的方法，计算所有可能的状态序列，O(NT)11112(,|)(|)(|,)()()tttTqqqqqttPOQPQPOQboabo24Viterbi算法一种更有效率的利用动态规划思想的算法定义一个变量t(i)，指在时间t时，HMM沿着某一条路径到达Si，并输出序列为w1w2…wt的最大概率111()max(...,,...)tttitiPPosPosPossww25利用Viterbi算法的求解过程初始化：迭代：迭代结束回溯记录最优路径：1111()max(,)(),1iiiiPPosswbwiN111121111121()max(...,,...)max[()max(...,,...)]max[()()],1,11tttjtiijjtttitiijjttjPPosPosPossmax[()]iTi26Viterbi算法时间复杂度每计算一个，必须考虑从t-1时刻所有的N个状态转移到状态的si概率，时间复杂度为O(N)，对应每个时刻t，要计算N个中间变量时间复杂度为O(N2)，又t从1…T，因此整个前向算法时间复杂度为O(N2T)()ti(1)...()ttN27模型参数学习给定状态集S和观察集V，学习模型参数A、B、π模型参数学习过程就是构建模型的过程有指导的学习－最大似然估计（标注了词性的语料库）无指导的学习－Welch-Baum（未标注词性的语料库）28有指导学习模型参数－从标注语料中学习最大似然估计对于无标注的语料库（状态不可见）如何获取模型参数？ijikiiNumberoftransitionsfromstatestostaes(|)NumberoftranstionoutofstaesNumberoftimesobservationvoccursinstates()(|)NumberoftimesinstatesijjiikkiaPssbvPvs29无指导学习模型参数－Welch-Baum算法迭代估计参数，使得此时λ最能拟合训练数据Baum证明：随着迭代过程，argmax(|)trainingPOijikiExpectedNumberoftransitionsfromstatestostaes(|)ExpectedNumberoftranstionsoutofstatesExpectedNumberoftimesobservationvoccursinstates()(|)ExpectedNumbijjiikkiaPssbvPvsiieroftimesinstates()ExpectedFrequencyinstatesattime(t=1)iiPsˆ(|)(|)PP30无指导学习模型参数－Welch-Baum算法基本思想：随机给出模型参数的初始化值，得到最初的模型λ0，然后利用初始模型λ0得到某一状态转移到另一状态的期望次数，然后利用期望次数对模型模型进行重新估计，由此得到模型λ1，如此循环迭代，重新估计，直至模型参数收敛（模型最优）。通过对模型的评估实现模型的最优化－模型使得训练数据存在概率最大化评估能够反映模型预测生成观察序列的能力31HMM模型的评估给定一个HMMλ和一个观察序列，计算该序列存在的概率－对所有可能生成该序列的状态序列的概率求和计算复杂度高1111121121(|)(,|)(|)(|,)()()()|log(|)log(|)|ttttttQQTTqqqqtQttTqqqqqtQtiiPPOQPQPOQaboboaboPP32评估模型类似Veterbi动态规划算法前向算法：定义前向概率:观察值为o1o2…ot,t时刻对应的状态值为si的概率迭代模型评估结果后向算法：定义后向概率:观察值为otot+1…oT,t时刻对应的状态值为si的概率迭代模型评估结果1()(...,|)tttiiPooqs111()()(),1j11NttijjtijiaboNtT1(|)()NTiPOi()(...,|)ttTtiiPooqs11()()(),1j11NttijjtijiaboNtT11(|)()NiPOi33Welch-Baum算法的参数估计HowtocalculateExpectedNumber?定义一个变量，对应于观察序列o1o2…oT，假设在t时刻的状态是si，t+1时刻的状态是sj的概率。112112121212112(,)(,|...)(,,...)(...)(,...)()(...,)(...)ttitjTtitjTTtitijjttTtjTijPqsqsoooPqsqsoooPoooPqsoooaboPooqsPooo1111()()()()()()tijjtttijjttijiabojiaboj(,)tij34Welch-Baum算法的参数估计（续）定义一个变量，对应于观察序列o1o2…oT，假设在t时刻的状态是si的概率。1212121()(|...)(,...)(...)()()()()ttiTtiTTttttiiPqsoooPqsoooPoooiiii()ti35无指导学习模型参数－Welch-Baum算法（二）赋aij,bi(vk)的初始值反复迭代，直到收敛ijik(,)ExpectedNumberoftransitionsfromstatestostaes