用隐马尔可夫模型实现词性标注

1目录•隐马尔可夫模型•词性标注•编码实现2目录•隐马尔可夫模型•词性标注•编码实现3显马尔可夫模型(VMM)•显马尔可夫模型的性质–有限视野–时间不变性111(|,,)(|)tkttktPXsXXPXsX21(|)kPXsX4隐马尔可夫模型(HMM)•隐马尔可夫模型可以由一个五元组(S,K,∏,A,B)表示–状态集合–输出字母表–初始状态概率–状态转移概率–符号发射概率5HMM的例子•某朋友在纽约，我在国内。通过电话，我知道他每天的活动：远足、散步、打扫房间通过HMM，我可以估计出纽约每天的天气情况6HMM图示o1=kmo2o3……X1=s1……P(o1=km|X1=s1,X2=s1)=b11m观察序列隐藏的状态序列X1=s2……b21mX2=s2……P(X2=s1|X1=s1)=a11a21X3=s1Xt=s1X2=s1X1=sNXt+1=s1……Xt+1=sNot=knb11n……7HMM的三个基本问题•给出一个模型，怎样有效计算某个观测序列发生的概率，即？•给出观测序列和模型，怎样选择一个状态序列，以便能够最好的解释观测序列？•给定观测序列，以及通过改变模型的参数而得到的模型空间，怎样找到一个最好的解释这个观测序列的模型？(,,)AB(|)PO8计算观测序列的概率11(|,)(|,,)TttttPOXPoXX121232T1TTXXoXXoXXobbb11223T1(|)TXXXXXXXPXaaa(,|)(|,)(|)POXPOXPX(|)(|,)(|)XPOPOXPX111111tttttTTXXXXXoXXtab•给定观测序列，和模型对于任意状态序列1(,,)TOoo(,,)AB1,1(,,)TTXXXX1(21)TTN次乘法9计算观测序列的概率（续）•利用格路算法，降低算法的复杂度………………………………s1s2s3sn123T+1……T……10计算观测序列的概率（续）•前向过程前向变量表示t时刻以状态si结束时总的概率，可通过对格路节点的所有入弧的概率进行求和计算得到1.初始化2.推导3.求和i(1),1iiNi121()(,,,,|)tttPoooXiji11,1(1)(),tNijijoitTjNttabi1(|)(1)NiPOT次乘法22NT11确定最佳状态序列•Viterbi算法在前向过程中，前向变量表示t时刻以状态si结束时总的概率。在Viterbi算法中，格路中每个节点变量存储了到这个节点的最可能路径的概率，存储了导致这条最可能路径的入弧节点。关键在于，从节点Node(si,t)往后找路径时，我们只需知道，到这个节点的最可能路径以及该路径的概率，而并不需要关心该路径外其他节点。()it()jt()jt12确定最佳状态序列（续）1.初始化2.推导存储回溯路径3.终止以及路径读出(1),1jjjN111ˆ1ˆargmax(1)ˆ(1)ˆ()max(1)TTiiNtXiiNXTXtPXT11,1(1)max(),tjiijijoiNtTjNttab11,1(1)argmax(),tjiijijoiNtTjNttab13HMM的参数估计•目前没有已知的解析方法来选择，使得最大，但我们可以通过迭代爬山算法使得它局部最大化。这种算法被称为Baum-Welch或前向后向算法。•工作方式如下：–使用某个模型（也许是随机选取的）算出观测序列的概率–查看计算过程，即可发现哪个状态转移或符号发射可能出现的次数最多–通过增加它们的概率，就可以选择一个修改后的模型，使得它可以为观测序列给出更高的概率(|)PO14目录•隐马尔可夫模型•词性标注•编码实现15怎样确定文本中一个词的词性？•词本身提供的信息词语的不同词性的使用分布极不均匀，比如，flour可以被用作动词，但更多是作为名词出现。Charniaketal.设计了一个dumb标注器，简单的把最常用的标注分配给每个词，准确率达到90%。•观察该词上下文中其他词的标注很多词性序列是常见的，比如ATJJNN，相应的词序列可以是agoodstudent等。16以HMM作为词性标注的概率模型•将句子的词形序列对应为观察序列•将句子的词性序列对应为隐藏状态序列•有限视野假设一个词语的标记只依赖于前面的标记•时间不变性假设词性转换概率与其在句子中的位置无关11,1(|)(|)iiiiPttPtt121(|)(|)jjiiPXtXPXtX17参数估计•状态转移概率•符号发射概率(,)(|)()jkkjjCttPttCt(,)(|)()ljljjCwtPwtCt18为句子寻找最佳标记序列1,1,1,1,1,1,1,1,(|)()argmax(|)argmax()nnnnnnnnttPwtPtPtwPw1,1,1,1,argmax(|)()nnnntPwtPt1,1,1,1,1,1,11,111111argmax(|)()argmax(|)()argmax(|)(|)argmax(|)(|)nnnnninntiniintinniiiitiiniiiitiPwtPtPwtPtPwtPttPwtPtt词语互相独立词语的出现只依赖于它本身的标注有限视野并引入P(t1|t0)=119使用Viterbi算法降低算法的复杂度20目录•隐马尔可夫模型•词性标注•编码实现21总体流程•训练–以GATE标注过的文本作为训练数据–在训练数据上进行各种统计，得到状态转移概率和符号发射概率•标注–先用GATE分词、分句–对每个句子，根据Viterbi算法，计算这个句子最可能的词性标注序列•评估–对于测试数据，以GATE的标注作为金标准–输出程序标注结果–输出统计结果，包括准确率、未登录词准确率等（程序以Java语言编写）22训练•状态转移概率–状态（词性）以int表示–状态计数矩阵，以int[]存储–状态转移计数矩阵，以int[][]存储–状态转移概率矩阵，以double[][]存储–在右上角公式中，如果分母为零，则分子肯定为零–在右上角公式中，如果分子为零，则给状态转移概率赋予一个很小的值（怎样确定？）(,)(|)()jkkjjCttPttCt23训练（续）•符号发射概率–符号，即为词形，取小写，保留词缀，以String表示–一般来说，一个词只有有限的几个词性，有的词只有一个词性，如“the”–符号发射计数表和符号发射概率表的图示：HashMaptheArrayListDT,108bankArrayListNN,23VB,10……HashMaptheArrayListDT,0.6bankArrayListNN,0.8VB,0.2……(,)(|)()ljljjCwtPwtCt24标注•初始概率–假设句子的前面是一个句点，取句点的词性到当前词性的转移概率即可（句点只有一种词性）25标注（续）•“简化”的Viterbi算法–对于已登录词，假设其所有词性均已在训练数据中出现………………………………s1s2s3sn123T+1……T根据以上假设，我们不关心已登录词的没有在训练数据中出现的词性？正面、负面影响分析26未登录词处理•Weischedeletal.基于三种信息估计了词语生成概率–一个标注可以生成一个未登录词的可能性有多大，这个概率对于某些标注是0，如介词、人称代词、冠词–生成大写词或者小写词的概率–生成连字符或者特殊后缀的可能性–其中Z是一个归一化常数–资料称，这个模型把未登录词的错误率从40%以上降低到了20%以下1(|)(_|)(|)(/|)ljjjjPwtPunknownwordtPcapitalizedtPendingshythtZ27Viterbi算法中的乘法用对数加实现•Viterbi算法只涉及到乘积，而且选择的是最大的元素，因此采用对数来运行整个过程。•这不仅解决了浮点数下溢问题，而且还加快了计算速度，因为加法比乘法快得多。•在实践中，一个快速的Viterbi算法是非常重要的，因为这是一个实时算法。•训练时得到的各种概率，均以对数存储。28实验结果数据组总词数词形数组数准确率未登录词准确率未登录词/总词数训练时间（分钟）标注时间（分钟）小说220819128253896.35%72.85%2.95%4.20.9新闻5888473226594.06%83.79%10.33%2.00.5•采用留一法，对两组数据进行实验，实验结果如下：•实验数据为纯文本格式•小说组所有的数据是同一篇小说的不同章节•新闻组的数据取自3个网站首页上的链接，一共大约100篇新闻，无特定分类和主题•关于未登录词大小写特征的分类，做了两组实验，结果相当，如下：分类1分类2分类3分类4未登录词准确率Weischedeletal.全小写，句首全小写，非句首非全小写，句首非全小写，非句首72.82%作者全小写全大写其他，句首其他，非句首72.85%29关于性能•考虑到工作量和程序的复杂性，有些可以优化的地方未优化。•通过优化，训练时间可以压缩为现在的1/3左右。•GATE标注过的文档含有大量标注信息，如果文档过长，那么GATE标注后，会占用大量内存。对于长文档，可以先分割，再处理。•文档用GATE处理完后，应该用Factory.deleteResource(Resourceresource)清理资源。•Java提供序列化方法，可以很方便的将内存中的对象写到文件；也可以读取文件，实例化对象。用这种方法，可以将内存中的数据写到文件，达到释放内存、保存数据的目的。30参考资料•统计自然语言处理基础ChristopherD.ManningHinrichSchütze•CopingwithAmbiguityandUnknownWordsthroughProbabilisticModelsRalphWeischedel等31下一阶段做什么？•句法分析•使用标准数据集，进行更大规模实验•词性标注领域的论文•HMM的论文•中文词性标注•中文分词32谢谢您的关注！