（计算机应用技术专业论文）应用于词性标注的隐马尔可夫模型参数评估.pdf

大连理工大学硕士学位论文 摘要 在自然语言处理中，词性标注是最基础的课题。由于基于统计的方法具有不需要人 工总结语言学规则、识别正确率高等优点，已逐渐成为研究的热点。在基于统计的方法 中，隐马尔可夫模型( h i d d e nm a r k o vm o d e l 简称h m m ) 是最主要的算法模型之一。 参数是隐马尔可夫模型的重要组成部分，参数评估也成为构建隐马尔可夫模型的必 要前提。在分析前人工作及研究现状的基础上，本文对有指导的隐马尔可夫模型参数评 估方法做出两个方面的改进：一是评估词的出现概率时，增加了前词词性；二是利用感 知器算法对隐马尔可夫模型参数进行修正。 传统的隐马尔可夫模型的输出独立性假设为：词的出现概率只与它的词性有关，与 前词或后词的词性无关。本文在评估词的出现概率时，增加了前词词性，即：词的出现 概率不仅与它的词性有关，而且与前词词性有关。使隐马尔可夫模型在词性标注中，能 够利用更多的语言学信息。 感知器算法是一种能根据输出与所期望的输出间的差别来调整模型参数的算法。本 文利用感知器算法对隐马尔可夫模型参数进行修正：首先用v i t e r b i 算法对输入句子进 行自动分词及词性标注，然后将输出结果与正确的词性序列比较，若不相同，则调整隐 马尔可夫模型参数。 实验结果如下：在封闭测试中，采用新的参数评估模型，f 值达到9 6 7 8 ，与采用 传统参数评估的隐马尔可夫模型相比，f 值提高1 8 4 。在开放测试中，采用新的参数 评估模型，f 一值达到9 2 7 9 ，与采用传统的参数评估的隐马尔可夫模型相比，提高 3 4 4 。实验表明：经过上述改进后的隐马尔可夫模型参数评估系统，能有效地提高隐 马尔可夫模型参数的质量。 关键词：闹性标注；隐马尔可夫模型；参数评估；感知器算法 大连理工大学硕士学位论文 h i d d e nm a r k o vm o d e lp a r a m e t e r se s t i m a t i o nf o rp a r t - o f - s p e e c ht a g g i n g a b s t r a c t p a r t - o f - s p e e c ht a g g i n gi st h ef u n d a m e n t a lp r o b l e m si nn a t u r a ll a n g u a g ep r o c e s s i n g b e c a u s ei tr e q u i r e sn om a n u a lr u l e so fn a t u r a ll a n g u a g ea n dh a sah i g hl e v e lo fa c c u r a c y ，t h e s t a t i s t i c a ll a n g u a g em o d e lh a sg r a d u a l l yb e c o m eah o tt o p i c f o ri t sb e t t e rp e r f o r m a n c e ， h i d d e nm a r k o vm o d e l ( h m m ) ，o n eo ft h es t a f f s t i e a lm o d e l s ，h a sb e e nt h er e c e n tt r e n di n p a r t - o f - s p e e c ht a g g i n g i nah m m ，p a r a m e t e r sa r ev e r yi m p o r t a n tc o n s t i t u e n tp a r t s a sar e s u l t ，p a r a m e t e r s e s t i m a t i o nb e c o m e sap r e m i s et ob u i l dah m m b a s e do nt h ew o r ko fp r e v i o u sa n a l y s i so f c u r r e n th m mr e s e a r c h e s ，t w oi m p r o v e m e n t sf o rt h es u p e r v i s e dp a r a m e t e r se s t i m a t i o na r e p r e s e n t e di n t h i sp a p e r o n ei sa d d i n gp r e v i o u st a gw h i l ee s t i m a t i n gt h ew o r d s o u t p u t p r o b a b i l i t y ；t h eo t h e ri sa d j u s t i n gt h eh m mp a r a m e t e r su s i n gp e m e p t r o na l g o r i t h m c o n t r a r yt ot h eo m p md e p e n d e n c ya s s u m p t i o no fa t r a d i t i o n a lh m m ，w h i c hi st h a tt h e p r o b a b i l i t yo faw o r dd e p e n d so n l yo ni t so w t it a g ，w ea s s u m et h a tt h ep r o b a b i l i t yo faw o r d d e p e n d sn o to n l yo ni t so w nt a g ，b u ta l s oo nt h ep r e v i o u st a gw h i l ee s t i m a t i n gt h ew o r d s o u t p u tp r o b a b i l i t y b yd o i n gt h i s ，w ec a ne m p l o ym o r eg r a m m a t i c a li n f o r m a t i o ni nt h eh m m 1 1 1 ep e r c e p t r o na l g o r i t h mi so n eo ft h ea l g o r i t h m st h a tc a l la d j u s tt h ep a r a m e t e r so fa m o d e lb yc o m p a r i n gt h er e s u l t sp r o d u c e db yt h em o d e la n dt h ee x p e c t e do u t p u tr e s u l t s i nt h i s p a p e r ，t h i sa l g o r i t h mi su s e dt oi m p r o v et h eq u a l i t yo ft h eh m mp a r a m e t e r s a tf i r s t ，w eu s e v i t e r b ia l g o r i t h mt og e tt h ew o r d sa n dt h e i rt a g s ，t h e n ，b yc o m p a r i n gt h e s er e s u l t sa n dt h e c o r r e c to n e s ，w ec a no p t i m i z et h ep a r a m e t e r si f t h e r ei sa n yd i f f e r e n c e w i t ht h ep a r a m e t e r sp r o d u c e db yt h ei m p r o v e dh m mp a r a m e t e r se s t i m a t i o nm o d e l i n c l o s et e s t s ，t h ef v m u eo f t h eh m mc a na r r i v ea t9 6 7 8 ，w h i c hi s1 8 4 h i g h e rt h a nt h a to f t h et r a d i t i o n a lh m m 诵t ht h eu n i m p r o v e do n e s ，i no p e nt e s t s ，t h ef v a l u eo ft h eh m mc a n a r r i v ea t9 2 7 9 w h i c hi s 3 4 4 h i g h e rt h a nt h a to ft h et r a d i t i o n a lh m m 谢mt h e u n i m p r o v e do n e s t h er e s u l t so ft h ee x p e r i m e n t sa l s os h o wt h a tt h eq u a l i t yo ft h eh m m p a r a m e t e r s c a l l i m p r o v eal o t ，b ym o d i f y i n gt h eo u t p u td e p e n d e n c ya s s u m p t i o na n d a d j u s t i n gt h eh m mp a r a m e t e r sw i t hp e r c e p t r o na l g o r i t h m k e yw o r d s ：p a r t - o f - s p e e c ht a g g i n g ；h i d d e nm a r k o vm o d e l ；p a r a m e t e r se s t i m a t i o n ； p e r e e p t r o na l g o r i t h m 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：瘟睥日期：竺2 笸：，左，己 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 导师签名 壶i ( 聿瑾 垂参参? 趔年丘月巧 大连理工大学硕士学位论文 1 绪论 1 1 词性标注方法简介 网络的普及使人类社会真正进入了信息化社会，每天都有海量的数字化信息在生 成、存储、传播和转换，同现实社会一样，语言交流方面的障碍越来越成为网络社会的 一个严重问题。这些困难的克服，有待于自然语言处理技术，特别是机器翻译技术的进 一步发展。 机器翻译是自然语言处理研究领域的一个分支，它的发展可以分三个阶段：第一个 阶段，机器翻译系统普遍采用直接翻译的方法，一般都没有进行很好的源语言句法结构 分析，主要用词典中的语法和语义特征来实现翻译。第二个阶段，机器翻译系统以基于 转换的方法为代表【l 2 】，普遍采用以词法分析为主，并辅以语义规则的方法，采用有抽 象转换表示的分层次实现策略。这一阶段的机器翻译系统综合了多种技术：语言学数据 ( 规则) 与算法分开，模块化程序设计，多种句法分析策略如扩充转移网络a t n 、表分 析c h a r t 、树置换等，以及语义分析等等。第三阶段，机器翻译系统以大规模真实文本 为基础，主要方法为基于统计的机器翻译方法【3 ，4 】和基于实例的机器翻译方法1 5 1 。其中， 基于统计的方法不需任何先验知识，只需要收集足够多的高质量语料，然后在特定模型 中训练，统计得到语言模型的参数。与基于规则的方法相比，基于统计的方法具有无需 先验知识、数据驱动、知识获取成本低等优点，使低成本的自然语言处理系统的建立成 为可能。 词性是词汇最重要的属性，也是句法分析的基础。通常句法分析都是从词性已确定 的句子开始，语料库加工的基本层次就是确定词性。因此，词性标注是自然语言处理包 括机器翻译的基本处理步骤。因为在一个特定的句子中，每个词的词性是确定的，所以， 词性标注的任务是对句子中的每个词都标上对应的词性。对于机器翻译来说，词性标注 不仅为后续句法分析奠定了基础，而且缩小了译文的选择范围，为译文生成做出了贡献。 常用的词性标注方法可分为基于规则的方法和基于统计的方法。 基于规则的方法一般分为两部分1 9 】：首先利用己生成的词典，对语料库进行静态标 注( 可能含有歧义) ，并对一些特殊词进行处理，例如数字、度量单位、专有名词等。其 次为歧义消除。利用人工总结的上下文有关规则，规则的左部由首尾两个词类惟一的词 定界，中间由兼类词组成，右部是在左部模式限制下可能产生的标记串集。当语料中出 现了某种和左部规则相匹配的模式时，则利用所有可能的标注作为一个集合，和规则的 右部作交集。如果只剩下一个元素，则认为歧义消除成功，这个元素也就作为标注的结 应用于词性标注的隐马尔可夫模型参数评估 果。上一世纪9 0 年代，出现一种新的基于规则的词性标注系鲥1 0 l 。这种方法是基于转 换和错误驱动的方法来进行词性标注。其基本处理步骤是：首先为每个句子赋以初始词 性序列，然后通过将这些初始词性序列与正确的词性序列相比较，自动学习得到一些转 换规则，最后将这些规则作用于新的被赋以同样初始词性序列的句子上，就可以得到正 确的词性标注。这种方法的优点是可以用较小的训练集达到较高的词性标注准确度。 由于自然语言的复杂多变性，仅用规则的方法，无论组成规则的条件和动作有多么 复杂，也难以满足实际需要。基于规则的方法的主要缺陷表现在：( 1 ) 规则所能刻画的 知识颗粒度太大，无法用有限的规则来刻画自然语言复杂多变的现象，很难处理自然语 言的不确定性；( 2 ) 不能保证语言学规则之间的相容，也就是说，在自然语言处理系统 中，随着规则数量的增加，规则之间常常发生矛盾和冲突；( 3 ) 获取语言学知识是件非 常困难的事l l “。 基于统计的方法，首先需要准备足够的训练语料，然后通过机器学习方法或统计方 法得到词性与词性同现的概率，产生一个词性的同现概率矩阵，以及词与词性同现的概 率，并产生一个词与词性的同现概率矩阵。在标注时，从文本中取出一个两端没有词性 歧义的词串，然后利用词性与词性同现概率及词与词性同现概率的乘积计算这些词串所 有可能的词性组成的词性串的权值，选择概率最大的词性序列作为输出结果。 基于统计的方法是从大量的训练数据中提取参数，因此，它可以避免基于规则的方 法的许多缺陷。例如，它利用的知识主要是统计数据，可以从语料库中利用有指导或无 指导的学习方法得到，从而避免了人工获取规则的繁琐过程。同时获取的知识具有客观 性好、一致性强等特点，处理生词和不规范句予的能力较规则的方法有较大的提高。 隐马尔可夫模型( h i d d e nm a r k o vm o d e l ，简称h m m ) ，在自然语言处理的各个领域 中获得了广泛的应用。它的理论基础，是在1 9 7 0 年前后由b a u r a 等人建立起来的【1 2 - 1 5 。 在2 0 世纪8 0 年代中期，由b e 实验室r a b i n e r 等人对隐马尔可夫模型的深入浅出的介 绍【1 6 ，”】，才逐渐使隐马尔可夫模型为世界各国从事语言处理的研究人员所了解和熟悉， 进而成为公认的一个研究热点【1 ”。隐马尔可夫模型有一个双重随机过程，其中之一是 马尔可夫链，这是一个基本随机过程，它描述状态的转移。另一个随机过程描述状态和 观察值之间的统计对应关系。 隐马尔可夫模型，是在词性标注领域中应用较为成功的模型之一。中科院计算所设 计的基于层次隐马尔可夫模型的汉语词法分析系统i c t c l a s l 2 2 1 就是一个证明。该系统 在2 0 0 2 年的9 7 3 专家组评测中获得第一名，在2 0 0 3 年汉语特别兴趣研究组( t h ea c l s p c c i a li n t e r e s tg r o u po i lc h i n e s el a n g u a g ep r o c e s s i n g s i g h a n ) 组织的第一届国际汉语 一2 一 分词大赛中综合得分获得两项第一名及一项第二名，被来自于中国、日本、新加坡、韩 国、美国以及其他国家和地区的3 0 0 0 0 多位研究人员和商业机构下载使用。 1 2 参数评估的研究意义 隐马尔可夫模型参数评估是自然语言处理研究领域十分重要的问题之一。它是隐马 尔可夫模型的重要组成部分，也是影响隐马尔可夫模型词性标注结果的重要因素之一。 研究隐马尔可夫模型参数评估，具有以下意义： ( 1 ) 弥补训练语料的不足 传统的参数评估要求随机变量独立观察的样本容量要远远大于它能够取到的值的 个数。在词性标注方面，若有1 0 7 个可能的词性，则对于三元模型来说，它可能的三元 词性联系个数多达1 2 0 万，而北京大学标注的2 0 0 0 年1 月份人民日报语料的三元 联系个数仅为5 万左右，现存的语料规模远远不能满足要求。 为了解决这一问题，在参数评估的过程中，常采用参数平滑算法。如：k a t z 及其同 事提出的k a t zs m o o t h i n g ( g o o dt u r c i n g 方法) 。它采用合理的估计算法对训练数据中从 未出现的状态估以合理的值田】。 ( 2 ) 提高隐马尔可夫模型参数的质量 因为隐马可夫模型的参数是在语料中评估得到的，语料的大小、覆盖不同领域的程 度、不同词及词性的出现频率、较生僻词的出现与否、以及多词性词的出现频率等，都 会影响到最终评估出参数的质量。在参数评估过程中，可采取一些方法对参数进行进一 步的修正。如本文所采用的感知器算法，就是在参数评估后，再利用部分语料对参数进 行进一步修正，从而提高参数的质量。 ( 3 ) 使隐马尔可夫模型获取更多的语言学信息 传统隐马尔可夫模型有三个假设：有限视野，即假定词性的出现概率只依赖于 前词词性；时间不变性，在第一个假设中的这种依赖性并不随着词性在句子中位置 不同而改变；输出独立性，即词的出现概率仅与当前词的词性有关，与前词的前词( 即 前前词) 的词性无关。其中，第一个及第三个假设使传统隐马尔可夫模型忽略了大量的 语言学信息，在一定程度上影响隐马尔可夫模型在词性标注方面的准确率。为了使隐马 尔可夫模型获得更多的语言学信息，可修改第一个及第三个假设。修改第一个假设，假 设词性的出现概率，不仅与前词词性有关，而且与前前词的词性有关，即三元隐马尔可 夫模型；修改第三个假设，即假设一个词的出现概率不仅与当前词的词性有关，而且与 其它的词或词性有关，从而使隐马尔可夫模型在词性标注过程中，获得更多的语言学信 息。 应用于词性标注的隐马尔可夫模型参数评估 1 3 国内外研究现状 近几年，国内外研究人员将统计学及机器学习引入隐马尔可夫模型参数评估过程， 提出了基于语料库的参数评估方法。主要有无指导的参数评估方法及有指导的参数评估 方法。一般来说，有指导的参数评估方法要好于无指导的参数评估方法。 1 3 1 无指导的参数评估 在无指导的参数评估中，训练数据的词性是未知的，首先要对词性的转移概率及词 的出现概率进行初始化。一般来说，词性转移概率初值的选取对训练结果影响不大，可 随机选取或均匀取值，而词的出现概率对训练结果影响比较大，一般倾向于采取较为复 杂的初值选取方法，然后通过迭代，利用极大似然估计方法对参数进行评估。 因为无指导的参数评估所需要的语料并不需要人工事先标注，所以，它主要应用在 以下情况： ( 1 ) 人工对训练语料标注的代价比较高 在自然语言处理过程中，对一些特殊的研究领域，如专有名词、新词的识别等，通过 网络可以找到大量未标注文本，但是，对这些文本进行人工的识别及标注则是一件需要大 量时间及精力的工作。 ( 2 ) 人工对训练语料的标注比较困难 由于自然语言的灵活多变性，对一些训练语料的标注是比较困难的。如对一些有多种 词性的词的标注，或在自然语言处理领域内一些本来就有歧义的词的标注，以及存在较多 旧词新用的情况等。在这种情况下，可采用无指导的参数评估方法。 无指导的参数评估方面的主要文献有： ( 1 ) r a b i 地r l r 对隐马尔可夫模型做了详细的介绍，并提出了无指导的参数评估方法 b 锄w e l c h 算法，并将隐马尔可夫模型运用在语音识别中刚。 ( 2 ) e l w o r t h y d 通过实验说明，在无指导的参数评估中，如果隐马尔可夫模型的初始参 数佩性转移概率矩阵和词的出现概率矩阵) 能够合理初始化，将会取得较好的参数评估结 果。并得出以下结论：如果有人工标注好的语料可以使用，则用有指导的隐马尔可夫模型 参数评估，其结果要好于无指导的隐马尔可夫模型参数评估；如果没有人工标注好的语料 可以使用，如果可获得词的出现概率，则可用b a u m - w e l c h 方法评估；如果没有人工标注 好的语料，而且词的出现概率也无法获得，则用b a u m - w e l c h 方法评估之外，还需要对隐 马尔可夫模型的参数做合理的初始化网。 大连理工大学硕士学位论文 ( 3 ) w a n gqi 和s c h u u r m a n sd 指出，在无指导的隐马尔可夫模型中，可通过两种方式 来提高参数评估的质量。利用词在真实语言环境中的出现概率，平滑词的出现概率； 在隐马尔可夫模型参数评估过程中，要保证词性的转移概率与一个特定的边缘分布相对应， 从而避免在极大似然估计过程中，过度学习某些词性转移概率口q 。 1 3 2 有指导的参数评估 与无指导的参数评估相比，有指导的参数评估要简单，它只需要从语料中统计词性 的转移频率及词的出现频率，计算出词性的转移概率及词的出现概率，从而实现隐马尔 可夫模型参数评估。由于它评估出来的参数质量要高于无指导的参数评估，而得到广泛 应用。 由于有指导的参数评估要求人工标注好训练语料，所以，它主要应用于以下几个方 面： ( 1 ) 有比较大规模的已标注好的语料 因为用有指导的参数评估获得的参数，直接从语料中统计得到，它需要较大规模的 语料，以尽可能涵盖所有可能出现的情况。 ( 2 ) 语料的覆盖面比较广，能够比较准确地反映自然语言真实分布 语料应涵盖政治、经济、金融、生活、文化教育等多种领域，使评估出来的参数能 更好反映自然语言的真实分布。 m a s a y u k ia s a h a r a 给出了用于日语形态素解析的有指导的隐马尔可夫模型参数评估 方法，为了提高参数的质量，做出以下改进f 2 刀： ( 1 ) 使用词一词性混合体作为新的词性 在词性标注过程中，存在一些词，它和其它有相同词性的词不同，在句中有特殊的 作用。与其它词相比，这些词更倾向于看作一个特殊的词性。为了在词性标注过程中减 少歧义和错误，将这些词与词性结合起来作为一个新的词性，在评估这些词的词性转移 概率时，要将词及词性作为整体考虑。 ( 2 ) 有选择地使用三元模型 为了解决采用三元隐马尔可夫模型与模型复杂度增加之间的矛盾，只对那些容易产 生歧义的词，使用三元模型，即在评估参数的过程中，当计算这些词的词性转移概率时， 用三元关系，而在计算其它词的词性转移概率时，仍采用二元关系。 应用于词性标注的隐马尔可夫模型参数评估 1 4 参数评估的研究难点 1 。4 1 无指导的参数评估与有指导的参数评估 无指导的隐马尔可夫模型参数评估，不依赖于人工标注的语料，可以实现跨领域大规 模真实语料的训练和学习。但是，无指导的参数评估具有以下缺点： ( 1 ) 初始化参数的选择 无指导的隐马尔可夫模型参数评估需要初始化参数，不同的初始化模型将评估出不同 的参数。因为参数评估的过程，就是为了使观察值的概率局部最大。因此，需要选出一个 比较好的初始模型，使最后求出的局部极大与全局最大接近。但是，实际上，至今这个问 题还没有一个完美的答案。实际处理时，都是采用一些经验方法，对参数进行初始化。 ( 2 ) 评估过程比较复杂 在初始化参数后，需要用v i t e r b i 算法求出句子所对应的词性序列，并评估出词性转移 概率，然后，根据词性序列，评估出词的出现概率，最后，判断结果是否收敛，如果收敛， 则得到隐马尔可夫模型的参数，如果不收敛，则需要将新评估出的参数作为初始化参数， 继续评估。迭代这过程，直到结果收敛，从而完成评估过程。 ( 3 ) b a u m - w e l c h 评估算法的局限性 经典算法b a u m - w e l c h 算法，实际上采用期望最大化算法( e m 算法) ，尽管e m 算法保 证会收敛于一个局部最大，但在隐马尔可夫模型的计算过程中，往往产生多个局部最大。 另外，训练数据一般都带有一些语言学信息，但是，仅靠e m 算法，即使有大量的训练数 据，也不能发现这些语言学信息。而且，初始化参数的选择对最终评估结果的影响要远远 大于e m 算法本身对最终评估结果的影响。 有指导的隐马尔可夫模型参数评估。具有算法简单，不需要初始化参数等优点，但是， 有指导的参数具有以下缺点： ( 1 ) 它需要较大规模的已标注语料 有指导的参数评估，需要直接从语料中统计出词性的出现频率及词的出现频率，进而 计算出词性转移概率及词的出现概率。因此，它对语料的规模有更大的要求，从而减少参 数的稀疏程度，较准确地反映自然语言的真实分布。 ( 2 ) 数据稀疏现象比较严重 有指导的参数评估过程，词性转移概率及词的出现概率都是从语料中获得，因此不可 避免地产生出现次数为0 的值，而且随着模型考虑语言学信息的增加，这些出现次数为0 6 一 大趣工大学硕士学位论文 的值也呈指数级增加。增加训练语料，只能在一定程度上缓解这一问题，而不能从根本上 解决这一问题。所以，对于有指导的参数评估，参数平滑算法显得更为必要 1 4 2 语言学信息的获取 隐马尔可夫模型参数应满足以下两个条件：( 1 ) 较好地反映语言学规律。( 2 ) 生成的隐 马尔可夫模型具有较小的复杂度。 很明显，这两个条件是一对矛盾体：为了能较好地反映语言学规律，在词性转移概率 及词的出现概率的评估过程中，要考虑更多的上下文信息；但是，考虑更多的上下文信息 后，又必然增加隐马尔可夫模型在词性标注中的计算量，从而增加模型复杂度。 传统隐马尔可夫模型有三个假设，其中，第一个假设( 即有限视野) 及第三个假设( 即输 出独立性假设) ，保证隐马尔可夫模型有较小的复杂度。但同时，它也使隐马尔可夫模型忽 略了大量的语言学信息，从而影响隐马尔可夫模型在词性标注中的精确率及召回率。 在词性标注中，为了提高隐马尔可夫模型的性能，使隐马尔可夫模型能够获取更多语 言学信息，需要修改这两个假设；用三元模型来代w _ - 元模型，即在评估词性的转移概率 时，不仅仅要考虑前词的词性，而且要考虑前前词的词性；在计算词的出现概率时，不仅 考虑当前词的词性，也要考虑其它的词或词性，即词的出现概率不仅与当前词的词性有关， 而且与其它的词或词性有关。 但是，也要注意到，在增加这些上下文信息的同时，也增加了隐马尔可夫模型的复 杂度，导致计算量的剧增，从而影响词性标注的速度。 1 5 本文的工作 本文要解决的闯题是隐马尔可夫模型的参数评估问题。因为在词性标注领域，已标 注的语料相对比较充裕，而且，有指导的隐马尔可夫模型参数评估的结果一般要优于无 指导的参数评估，因此，本文在解决这一问题时，采用有指导的参数评估。为了使隐马 尔可夫模型在词性标注过程中获得更多的语言学信息，本文给出了新的词的出现概率评 优方法。同时，用感知器算法对参数迸一步修正，从而提高参数质量。 本文的目的是实现有指导的隐马尔可夫模型参数评估系统，为了达到这一目标，本文 做了以下工作： ( 1 ) 实现了应用于词性标注的传统隐马尔可夫模型 这一模型保持隐马尔可夫模型的三个假设( 即有限视野；时间不变性；输出 独立性) 不变。在词性标注过程中，采用v i t e r b i 算法，选择最佳的词性序列。 ( 2 ) 实现了传统隐马尔可夫模型的参数评估系统 应用于词性标注的隐马尔可夫模型参数评估 在上一步工作的基础上，实现了与之对应的有指导的隐马尔可夫模型参数评估系统， 用北京大学标注的2 0 0 0 年人民日报的部分语料，评估出参数，并用于词性标注中。 ( 3 ) 实现了新的隐马尔可夫模型参数评估系统 针对词的新的出现概率评估方法，即词的出现概率不仅与当前词词性有关，而且与前 词词性有关，实现了新的参数评估系统，并修改相应的隐马尔可夫模型，使它能够用新评 估的参数迸行词性标注。 ( 4 ) 利用感知器算法对参数进行修正 由于在参数评估过程中，语料规模及语料的选择均会影响最终评估的参数，从而影响 参数的质量，因此，本文引入感知器算法对参数进行进一步修正。感知器算法是一种能根 据输出与所期望的输出间的差别来调整模型参数的算法，本文利用感知器算法的原理，实 现对评估出的参数进行自动调整。 本文的组织如下： 第一章介绍了隐马尔可夫模型参数评估的问题的提出、研究意义和研究难点、前入的 工作以及本文的工作。 第二章主要介绍隐马尔可夫模型的主要理论。介绍隐马尔可夫模型的原理及隐马尔可 夫的三个经典算法：前向一后向算法、v i t e r b i 算法及b a u m - w e l e h 算法。 第三章主要介绍有指导的隐马尔可夫模型参数评估。首先，介绍有指导的隐马尔可夫 模型参数评估方法，指出隐马尔可夫模型的三个参数历4 ，丑的评估方法。其次，对隐马 尔可夫模型的词的出现概率评估方法做了修改，即词的出现概率不仅与当前词词性有关， 而且与前词词性有关，并介绍了采用新的评4 告 - h 法后有指导参数评估。最后，引入感知器 算法，对评估后的隐马尔可夫模型参数进行修正。通过对参数的修正，使训练后的参数更 符合自然语言的分布。 第四章是系统的实现。详细介绍了隐马尔可夫模型参数评估系统的实现，并介绍了有 指导的隐马尔可夫模型参数评估系统的两个子系统：隐尔可夫模型参数评估子系统及隐马 尔可夫模型参数修正子系统。 第五章是对实验结果的分析。分析了利用不同评估模型的实验结果，以及语料规模对 采用不同评估模型及感知器算法的影响，并分析了实验结果、及实验中产生错误的原因及 改进方法。 大连理工大学硕士学位论文 2 隐马尔可夫模型 隐马尔可夫模型，在某种意义上讲，是一个马尔可夫过程的概率函数。马尔可夫是 享誉世界的著名数学家，亦是社会学家他研究的范围很广，对概率论、数理统计、数 论、函数逼近论、微分方程、数的几何等都有建树。马尔可夫最重要的工作是在1 9 0 6 - 1 9 1 2 年间，他提出并研究了一种能用数学分析方法研究自然过程的一般图式，后人把这种图 式以他的姓氏命名为马尔可夫链( m a r k o vc h a i n ) 。同时他开创了对一种无后效性的随机 过程的研究，即在已知当前状态的情况下，过程的未来状态与其过去状态无关，这就是 现在大家熟知的马尔可夫过程。1 9 7 0 年前后，b a u m 等人建立起来有关隐马尔可夫模型 的理论基础。在上一世纪8 0 年代中期，隐马尔可夫模型逐渐为世界各国从事语言处理 的研究人员所了解和熟悉。 2 1 马尔可夫链 在现实世界中，有很多过程都是马尔可夫过程，如液体中微粒所作的布朗运动、传染 病受感染的人数、车站的候车人数等，都可视为马尔可夫过程。所谓马尔可夫链是指时间 连续( 或离散) 、状态可列及时间齐次的马尔可夫过程。这种过程之所以重要，一是由于它的 理论比较完整深入，可以作为一般马尔可夫过程及其他随机过程的借鉴；二是它在自然科 学和许多实际问题( 如教育学、经济学、规则论、排队论等) 中有着越来越多的应用。 这里举一个例子来说明马尔可夫链。假设我们把天气分为三种状态：晴，阴，雨。如 果今天晴，则明天晴的概率为3 4 ，阴的概率为1 8 ，下雨的概率为l ，8 ；如果今天阴，则明天 晴的概率为1 2 ，阴的概率为1 4 ，下雨的概率为1 4 ；如果今天下雨，则明天晴的概率为1 4 ， 阴的概率为l 2 ，下雨的概率为1 4 。我们可以用矩阵来表示这种概率。如图2 1 所示。 晴 明天阴 雨 今天 晴阴雨 3 ，4 1 ，2l ，4 1 81 41 2 1 81 41 4 图2 1 天气状态 f 螗2 1w e a t h e r s t a t e s - 9 一 应用于词性标注的隐马尔可夫模型参数评估 假设今天晴、阴及雨的概率分别为p 卜施，那么我们可以根据上述矩阵，由式( 2 1 ) 可计算出明天晴、阴及雨三种天气的概率：a 、及爿。 烈2 i a + i 易+ i p 3 a 2 i a + i 仍+ j 见 烈。i a + i 扔+ i p 3 ( 2 1 ) 还可以计算出后天，三天后，以至于栉天后的天气状况i 泐，见( 磅，刃) ) e 这个过 程就好像一个链一样，由一个状态决定后一个状态，与此时刻以前的状态无关，称之为 无后效性，这种过程就是马尔可夫链( m a r k o vc h a 岫。 从数学上，可以给出如下定义： 假设* = ( 五，五，耳) 是一个取值于有限集合的随机序列，s 为一状态空间。在任 一时刻挖，x 可以处在状态毛，岛，知，且它在m + k 时刻的状态为# 。的概率，只与它 在m 时刻的状态有关，而与m 时刻以前的状态无关，如式( 2 2 ) 所示a p ( k + = 目名娃i k = g i ，匕一l = 9 0 l ，五= 吼) = 尸( j ，肿l = g 。柑j k = g 。) ( 2 2 ) 其中，q l ，9 2 ，g 。，g m + i 瓴，屯，) 则称x 为m a r k o v 链，其随机转移概率矩阵，如式( 2 3 ) 所示。 嘞( m ，研+ _ j ) = v ( q 。“= 一1 = 岛) ( 2 3 ) 其中，1 i , j s n ，肼，k 为正整数 当( 小，小+ _ j ) 与m 无关时，称这个m a r k o v 链为齐次m a r k o v 链，此时的随机转移 概率矩阵，如式( 2 4 ) 所示。 嘞( 肌，所+ 七) = 嘞( 七) ( 2 4 ) 当j j = 1 ，以( 1 ) 称为一步转移概率，简称为转移概率，记为 p ( q 。“= s m “l = s m ) = p ( + = ，i g 。= f ) = 嘞 它表示在时刻m 取状态g 捌= f 的条件下，在时刻所+ 1 取状态“= _ ，的条件概率。 大连理工大学硕士学位论文 由于l | 步转移概率( | ) 可由转移概率得到，因此，描述m a r k o v 链的最重要参数 就是转移概率矩阵a 但a 矩阵还决定不了初始分布，即由4 求不出窖1 = 岛的概率，这 样，完全描述m a r k o v 链，除4 矩阵之外，还必须引进初始概率矢量口= ( 码，和，) ， 的值，如式( 2 5 ) 所示。 乃= 尸( 吼= 毛) ，1 9 i s n ( 2 5 ) 显然有o 巧l ，乃= l 我们可以用状态图来表示马尔可夫链。这里，状态用包含状态名的圆圈表示，单个 初始状态有一个指向它的箭头。概率转移用连接状态的箭头表示，这些弧上标有处于箭 头尾部时发生状态转移的概率。图中的转移概率为零的弧被省略了需要注意的是每个 状态发出的弧的概率和为1 。如图2 2 所示。 开始 l 图2 2 马尔可夫链的例子 f i g 2 2m a r k o v 曲a i nm o d e l 2 2 隐马尔可夫模型 隐马尔可夫模型是在马尔可夫链模型的基础上发展起来的。由于实际问题比马尔可 夫链模型所描述的更为复杂，观察到的事件并不是与状态一一对应，而是与一组概率分 布相联系，这样的模型就称为隐马尔可夫模型。它是一个双重随机过程，其中之一是马 尔可夫链，这是基本的随机过程，它描述状态的转移。另一个随机过程描述状态和观察 值之间的统计对应关系。这样，站在观察者的角度，只能看到观察值，不像马尔可夫链 模型中的观察值和状态一一对应。因此，在隐马尔可夫模型中，不能直接看到状态，而 是通过一个随机过程去感知状态的存在及其特性，因而称之为“隐”马尔可夫模型【2 8 】。 应用于词性标注的隐马尔可夫模型参数评估 举一个例子来说明隐马尔可夫模型。设有个缸，每个缸里面装有很多彩球，球的 颜色由一组概率分布描述。实验是这样进行的；根据某个初始概率分布，随机的选择 个缸中的一个，再根据这个缸中彩球颜色的概率分布矩阵，随机选择一个球，记下球的 颜色，记为d l ；再把球放回缸中，又根据缸的转移概率矩阵随机的选择下一个缸，再 从缸中随机选择一个球，记下球的颜色，记为仍；这样一直下去就可以得到一个描述 球的颜色的序列：0 1 0 2 。由于这是观察到的序列，所以称之为观察值序列。但是缸与 缸之间的转移以及每次选取的缸被隐藏起来了，并不能直接观察到。而且，从每个缸中 选取球的颜色并不是与缸一一对应，而是由该缸中彩球的概率分布决定，每次选取哪个 缸则由一组转移概率决定。如图2 3 所示。 依次观察到的球o o oo o 图2 3 隐马尔可夫模型的例子 f i g 2 3e x a m p l eo f h m m 藏 个隐马尔可夫模型是一组有限的状态，其中的某一个状态可以以一定概率转移到 另外的状态( 终止状态除外) ，而且在转移时产生输出，能产生的输出是有限的，输出也 将以一定的概率产生。一个隐马尔可夫模型是一个五元组，如式( 2 6 ) 所示。 扣( ，m - , a ，两( 2 6 ) 其中： 大连理工大学硕士学位论文 表示模型中的状态的数目。在实际应用中，虽然状态是隐藏的，但模型的每一 个状态都与一些物理意义相联系，另外这些状态也是相互联系的，可以从一种状态转移 到其它状态。所有独立的状态定义为q = 鼋】，q 2 ，鼬) ，且来用s t 来表示t 时刻的状态， 显然有岛 q l , 9 2 ，g 胁表示每个状态对应的观察值数目。观察值对应于模型的实际输出，可以记这些 观察值为：v ；“，v 2 ，v ， ，记r 时刻观察到的观察值为o t ，其中qe v 。, v 2 ，) 。 这里状态的变化不是直接给出的，而是通过观察结果的变化来表示，这就是“隐”马尔 可夫模型的含义。 a ：a = 嘞 表示状态转移概率矩阵其中，a u = p ( _ + l = q j i 墨= 吼) ，l i ，j n 嘞表示从状态f 转移到状态_ ，的概率，嘞满足：嘞o ，v f ，且a u = l ，v i j 口：占= ) 。表示观察值概率分布矩阵其中表示在状态下，时刻出现v k 的概率，即= p ( 。i = 划s t = 乃) ，1 s _ ，n ，1 七m 吆满足：￥o ，v j ，k ，且 = 1 ，w k ：= 羁) 表示初始状态分布矢量，其中乃= p ( = q d ，1 k 。即在t = 1 时刻 处于状态丑的概率。巧满足：罗巧= 1 。 7 一个隐马尔可夫模型可以分为两个部分，一个是马尔可夫链，由和4 描述，产 生的输出为状态序列，另一个是一个随机过程，由口描述，产生的输出为观察值序列， 如图2 4 所示，r 为观察值时间长度。 l 马尔可夫链 焉，s ，s r 随机过程0 1 , 0 2 ，吁 ( , ) 状态序列 ( 口) 观察值序列 图2 4 隐马尔可夫模型组成示意图 f i g 2 4s t r u c t u r a ls c h e m eo f h m m 下面说明隐马尔可夫模型在词性标注中的应用。词性标注的任务是根据给定的句子 求出每个词对应的词性构成的词性序列。这里词性序列是隐藏的，相当于状态；句子是 外在的，相当于观察值。那么，在转移过程中经过的所有状态按序排列就是句子的词性 序列，记为s 。用只表示第r 次转移的源状态。全部状态的集合就是标注集中的所有词 应用于词性标注的隐马尔可夫模型参数评估 性。一个转移过程中的输出按序排列构成就是句子，记为0 。用d ，表示第t 次转移时的 输出。全部输出的集合就是所有的词。 词性标注的过程，就是在给定的模型工和观察值序列d = q ，o z ，o r 的条件下，选 择出一个与观察值序列相对应的最佳状态序列s ；焉，屯，知。这是由观察值序列生成 状态序列的过程。 2 3 隐马尔可夫模型的三个基本问题 在隐马尔可夫模型中，有三个基本问题： ( i ) 给出一个隐马尔可夫模型丑= ( 皿a ，司，怎么有效地计算某个观测序列发生的概 率，即p ( o f 五) ? ( 2 ) 给出观测序列。和模型a ，怎么选择一个状态序y u ( s , ，s ：，s r ) ，以便能够最好 地解释观测序列? ( 3 ) 给定观测序列o ，怎么通过改变模型a 气皿a ，四的参数，才能找到一个最好解 释这个观测序列的模型? 第一个问题是用来计算观测序列的概率，可由前向一后算法来解决。第二个问题是 用来确定在马尔可夫模型中，观察值序列概率最大的那一条路径，可由v i t e r b i 算法来 解决。第三个问题可用来确定最佳模型，即用于评估隐马尔可夫模型参数，b a u m - w e l c h 算法