（计算机应用技术专业论文）汉语组块计算的若干研究.pdf

堡堕垒竺生墨塑董士竺塑二_ j 塑墨一 摘要 组块的概念最初是在认知心理学中提出的，并在信息处理理论和通用智能系统中得 到应用。它又被推广到计算语言学领域中，用“分而治之”的策略来解决问题，对自然 语言进行组块计算。本文中对组块的计算，不仅包括组块分析，还涉及到对组块相似度 计算的研究。 完全的句法分析是当前自然语占处理中的一个难点和重点。一方面我们既要达到语 法分析的目的，另一方面还要降低分析过程中的难度。因此针对这种局面，进行部分的 句法分析，即组块分析。本文的目标就是在这种背景下，从理论、算法和应用三个方面 来讨论汉语组抉及其分析方法和技术。 本文范琵指出当前语法分析的困难，而组块分析是一条解决问题的途径。f 并介绍了 组块分析的研究现状，以及组块分析的两条技术路线。提出了汉语组块分析任务的重要 性和可行性。 随后总结了界定组块的各种方法，在前人工作的基础上对汉语组块进行了定义。同 时组块库的获取和收集也是一项迫切的任务，由于不易直接获取具有组块标注的语料， 当前大多组块语料库是通过转化现有树库获得。本文实验所用的组块库是从宾州大学中 文树库中抽取而来的。根据组块定义，结合现有语料的实际，本文定义了1 2 种汉语组 块类型，和分析过程中所用到的组块标注符号。 我们实现组块分析的系统是采用统计与规则相结合的路线。统计方法首次采用了成 熟的数学模型最大熵模型进行汉语组块的识别和划分。最大熵模型具有简洁、通用 性和可移植性等特点，能灵活地选取特征，同时可以把计算模型和语言模型作为独立的 模块处理，而不必关心语言内部的细节。规则方法采用了有限自动机来完成组块分析的 任务，有限自动机实现简单、效率高，也具有较高的组块标注正确率。在两种方法并用 的基础上，加入了错误驱动的基于转换的机器学习方法，根据系统标注语料和正确标注 语料相比较的结果，不断学习和反馈，生成转换规则集合，用于基于混合模型的标注系 统中。 特征集合的选取是最大熵模型的关键问题所在，它选取合适与否决定了组块标注结 果的好坏。因此在本文中针对汉语组块的划分和识别，提出了词、词性标注、语法标注 和词音节数是构成组块划分的主要影响因素，并根据这几种因素来确定最大熵模型的特 征空间，从中自动获取组块分析的有效特征集合。 我们所采用的基于混合模型的组块分析方法，不仅利用了现有的技术，而且有效地 结合了两种方法的优势，达到较为满意的组块划分和识别效果。文中给出了各种模型的 汉语组块计算的若干研究 于已有的汉语语义资源同义词词林和知网，引入了义原问相似度和相关度的计算公 式。i 同时根据义原构成词语、词语组成组块的关系，逐步计算出词语问的相似度和相关 度，最后得到组块问的相似度。对于英汉双语组块，本文提出了同时利用w j r d n e t ，得 到双语组块的相似度，该相似度计算的实现将有利于改进双语组块对齐的效果，乃至改 进机器翻译系统的性能。 本文的研究成果可以应用到信息检索、信息抽取、文本分类聚类、机器翻译等自然 语言处理系统中去。、一一、 卅飞 关键词：自然语言处理，语法分析，组块分析，最大熵定理，有限自动机 n 堡堕垄堡生簦塑董堕茎! 坐坚竺一 a s t u d y o nt h ec o m p u t a t i o no fc h i n e s ec h u n k s l is u j i a n ( a p p l i e dc o m p u t e rt e c l i l o l o g y ) d i r e c t e db yb a is h u o t h ec o n c e p to f c h u n k w a sp r o p o s e di nt h es c i e n c eo fc o g n i t i v ep s y c h o l o g y ，w h i c h w a s l a 【e ra p p l i e di nt h ef i e l do fi n f o 门n a t i o np r o c e s s i n gt h e o r ya n ds y s t e m so fg e n e r a li n t e l l i g e n c e n o wi tw a ss p r e a dt ot h ef i e l do fc o m p u a t i o n a ll i n g u i s t i c s ，u s i n gt h e “d i v i d e a n d c o n q u e r ” s t m t e g yt oc o n d u c tc h u l l k i n g i nt h i sp 印e r ，t 1 1 ec o m p u t a t i o no fc h u n k sn o to n l yi n c l u d e s c h u n k p a r s i n g ，b u t a l s or e f e r st ot 1 1 ec o m p u t a t i o no fs i m i l a r 埘b c t 、e e nc h u n k s a sak e yp r o b l e mo fn a t u r a ll a n g u a g ep r o c e s s i n g ，t h ep r o b l e m so fc o m p i e t es y n t a c t i c p a r s i n ga r e n ts o l v e dy e t d u et ot h i ss i t u a t i o n ，c h u m d n gi su s e dt or e d u c et h ed i m c u l t yo f c o m p l e t es ”t a c t i cp a r s i n g c h u n k i n gr c f e r st ot h et e c h n i q u e so fr e c o g n i s i n gr e l a t i v e l ys i m p l e s y n 协c t i cs t m c t u r e s t h et h e s i sa i m s t od i s c u s st h em e t h o d sa 1 1 dt e c h n i q u e so f c h u m 【p a r s i n g a tf i r s t ，w ep o i mo u tt h ed i 伍c u l t i e so fs ”诅c t i cp a r s i n ga i l dt l l i n kt h a tc h u i l kp a r s i n gi s o n ew a yt os o l v em i sp r o b l e m a tt 1 1 es 锄et i m e ，t h ec u r r e ms t a t eo fc h u r l i ( p a r s i n gi s i n t m d u c e d ，a n dt 1 1 er u l e - b a s e da 1 1 ds t a t i s t i c a lt e c h n i q u e sa r ea l s oi l l u s t r a t e d i ti so b v i o u s 协a tt h et a s ko f c h _ i l i 墩p a r s i n gi si m p o n a m a i l df e a s i b l e t h e nw es u i l l m a r i z et h ec u r r e n td e f i n i t i o n so fc h u l l | ( s b a s e do nt h ew o r ko fo t h e r s ，w e m a l ( ead e f i n i t i o nf o rc h i n e s ec h u n k s i ti si a b o r i o u st oc o l l e c tt h ec o r p u sw i t hc h u l l kt a g s ， a 1 1 dt h u si t s a c q u i s i t i o n i s m o s t l yc a r r i e d o u t t 1 1 r o u g h t h et r a n s f o m a t i o no ft h e e x i s t i n g t r e e b a n k t h et r a i na n dt e s td a t ai no u tp a p e ri se x t r a c t e df t o mu p e 皿c h i n e s et r e e b a l l k a c c o r d i n gt ot h ed e f i n i t i o no fc h u n ka n dt h ep r a c t i c eo fc o r p u sa v a i l a b l e ，1 2c h i n s ec h u n k c a t e g o r i e sa r ei n t r o d u c e d ，w i t h t h e c h u l l l ( t a g su s e di nt l l ep r o c e s so f c h u n kt a g g i n g t h es y s t e mo ft e x t c h u r l k i n g i nm i st h e s i s a d o p t s ah y b r i dm o d e l ，w h i c hc o m b i n e s m l e 七a s e dm e t h o da i l ds t a t i s t i c a lm e m o d t h ef i r s tt i m ew eu t i l i z em em a t u r es t a t i s t i c a l m o d e l i n gt e c h n i q u e m a ) ( i m 咖e n t r o p y ( m e ) m o d e l t oc o n d u c tt l l ed i v i s i o na n dr e c o g n i t i o n o fc h i n e s ec h u l l l ( s i n p r a c t i c e ，u s i n g m em o d e i 、v ec a nr e a c h h i g ha c c u r a c y w i t h k n o w l e d g e p o o rf e a t u r e s a n o t h e ra d v a n t a g eo f m em o d e li si t sr e u s a b i l i t ya n dt h et h e o r yo f m ef r a m e w o r ki si n d e p _ e n d e n to fa n yp a n i c u l a rn a t u r a l l a n g u g a g et a s k a sf o rm l e _ b a s e d m o d e l i n gt e c h n i q u e s ，f i n i t e s t a t ea u t o m a t o n ( f s a ) i su s e d 州t l lh i 曲e m c i e n c yd u et oi t s d e f i n i t e n e s s a tt h es a m et i m e ，t m n s f o m a t i o n - b a s e de f r o rd r i v e nm a c h i n el e a m i n gm e t h o d i sa l s oa d d e dt oi m p r o v eo u rs y s t e m t h i sm a c h i n e i e a m i n gm e m o dc o m p a r e sm et a g g i n g r e s u l t so ft h o s et w om e t h o d sa b o v e、v i t h t h ec o r r e c t r c s u l t ， a l l dp m d u c e sas e to f t r a n s f o 珊a t i o nr u l e st l r d u 曲i e 姗i n ga n df e e d b a c k t h es e l e c t i o no ff e a t u r e si sa k e yp r o b i e mo fm em o d e lw h i c hd e t e m l i n e st h e p e r f o m a n c eo f t e x tc 蜮n g a i m i n g a tt l l et a s ko ft e x tc h u l l l 【i n g ，w ep r o p o s e dt h a tw o r d ， p a r to fs p e e c k 科l l 切i c t i ct a g g m g 锄dr b y t h ma r et h em a i n 墨c t o r sw l l i c hc o 璐t n l c taf b a t u r e i n 汉语组块计算的若f 研究 s p a c eo f m em o d e l a n d a i la l g o r i n u ni sp r e s e n t e dt oa u t o m a t i c a l l ya c q u i r eaf e a t u r es e t t h eh y b r i dm o d e i nm ym e s i sn o to n l ym a k e su s eo ft h et e c h n i q u e sa v a i l a b l e ，b u ta l s o c o m b i n e st h ea d v a n t a g e so fe v e r ym e t h o d a n dt h ee x p e r i m e n t a lp r o c e d u r ea 1 1 dr e s u l t sa r e g i v e na n da n a l y s e d w e c a t lc o n c l u d et l l a ti tn e e d sal o to f e 肋nt og e tl i t t l ep r o g r e s s a tl a s tw ei n t r o d u c et h em e t h o dt o c o m p u t et h es i m i l a r i t y o fc h i n e s ec h u n k s ，a 1 1 d p r o p o s eas u p p o s i t i o nt oc o m p u t e t h es i m i l a r i t yo f b i l i n g u a lc h u n k s b a s e do nt h es e m a n t i c r e s o u r c e t b n g y i c ic i l i na n dh o w n e t ，s t e pb ys t e pw ec o m p u t e t h es i m i l 撕t ya n da s s o c i a t i o n o fs e m e m e s ，t h es i m i l a r i t ya 1 1 d r e l e v a n c y o fw o r d s ，a 1 1 ds i m i l 撕t yo fc h u n k s a sf o r e n 鲥s h c h i n e s eb i l i n g u a lc h u n k s ，w o r d l l e t i sa l s oc h o s e nt o g e t t h e s i m 订a r i t y t h i s s u p p o s i t i o n 、“l lb eh e l p f h lt oi n l p r o v et h ea l i g r l m e n to f b i l i n g u a lc h u n k s t h e s er e s u l t sc a nb ea p p l i e di nm a n yn l p a p p l i c a t i o n s ，s u c ha si n f o m l a t i o nr e t r i e v a l ， i n f b n n a t i o ne x t r a c t i o n ，t e x tc l a s s 谲c a t i o r i c l u s t e r i n g ，m a c h i n et m s l a t i o na 1 1 ds oo n k e y w o r d s ：n a t u r a ll a n g u a g ep r o c e s s i n 岛s y n t a c t i c p a r s i n & c h u n kp a r s i n g ，m a x i m u m e n t m p yp r i n c i p l e ，f i n i t es t a t ea u t o m a t o n i v 独创性声明 本人声明我所呈交的论文是我个人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本 文所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名：巷舂支菱 日期：2 c 以岁形 关于论文使用授权的说明 中国科学院计算技术研究所有权保留送交论文的复印件，允许论文被 查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、缩印或 其它复制手段保存该论文。 作者签名：蕉丧建导师签名： o 时，则称规则r 为合式的基本组块规则。 定义5 3 ：基本组块规则集g 所有合式的基本组块规则构成基本组块规则集g 。 汉语中一些常用的字经常嵌入到组块中形成固定结构，因此在基本组块规则中会出 现一些诸如“所”“的”之类的字。例如，“数学家n n 所m s p 认为v v 的d e c ”，这罩 规则中的词性标注m s p 和d e c 必须加以限定，也就是我们要把规则改为：n n 所v v 的。 否则就会极大地影响组块识别的准确率。通过把一些词性标注换为具体的词，基本组块 规则集得到扩展。我们采用的是宾州树库的汉语词性体系，构成组块的几个词性标注序 列构成一条合式的基本组块规则，加入到基本组块规则集中去。这里的规则集合与a b n e y 提出的有限自动叠不同，它不分层次，只需要构造一个有限自动机来进行组块分析。 根据上面的几个定义，很容易从实际语料中获得基本组块规则集合，它可以被看作 是一种从实际中归纳得到的有规律的知识。同时还可以获得到规则发生的频数，在知道 规则及其发生概率的情况下，该规则集合就相当于一个加权的接受机。基于统计的方法 在分析语言结构方面先天不足，不能系统化地表示语言，但由统计总结出来的规则却在 一定程度上表示了语言知识和结构。该规则集合是正则语法，我们可以构造加权的有限 状态自动机，对输入语句进行组块的划分和识别。 5 3 3 组块的划分和识别 利用有限自动机进行分析实质上是一个模式匹配过程，在这个过程中，如遇到冲突， 则按最大匹配原则选择合适的模式。例如，下面为基本组块规则集的一个子集，图5 2 为该规则子集对应的有限自动机。 c d ( i ) n c j j 的n n f 2 ) n c j j 。的 ( 3 ) n c j n n 的n n ( 4 ) n c 寸c d + m n n ( 5 ) q c _ c d + m ( 6 ) v c c 专a 舻1 v v ( 7 ) v c c o a d 地v v a d 图5 3 有限自动机的部分构成 苎至垦茎主塑型查鲨堕望苎盈塑堡坐l 一 规则子集中， 表示一个或多个；口表示可以省略；n c ( n o u n c h u n k ) 表示名词组块； v c c ( v e r bc h u n k ) 表示动词组块；词性标注参见附录。图5 3 中圆圈表示自动机的状 念，双圆圈表示一个组块的终止状态。输入已经正确分词和标注的汉语语句，输出经过 组块标注的汉语语句。 例2 ：“c d 个m 好j j 的d e c 开端n n 是v v 成功n n 的d e c 一半n n a p u ，。 表5 1 描述了有限自动机对例句2 进行组块分析的过程。i 代表输入，s 代表一个特 殊的状态栈，在每次开始进行一个新的组块分析前，它存放所有自动机的初始状态，其 内部可以自动调整，分析丌始时把需要的自动机状态放在栈顶。状态s i 代表自动机移 进到状态i ，r j 代表根据基本组块规则j 得到了一个名词组块( n c ) 或动词组块( v c c ) 。 每一次都是从某个自动机的初始状态出发寻找匹配，当达到该自动机的终止状态时则产 生一个组块。若遇到不能形成组块的词不影响组块划分的进行，跳过从下一个词继续进 行处理。最后输出经过组块标注的语句形成为：“ 一c d 个mq c 好j j 的d e c 丌 端n nn c 是v vv c c 成功n n 的d e c 一半n nn c 。p u ”。首先是数词c d 和量 词m 由规则5 形成量词组块q c ，然后形容词j j 、“的”、名词n n 根据规则1 形成一个名 词组块n c ，最后由规则3 又可以得到名词n n 、“的”、名词n n 三部分构成的名词组块。 表5 1 规则划分组块过程 义 好的开端是成功 的 坐 c d 个m 。p u 旭1 d e cn n烈n nd e cn n q c ， 5 os 1s 3 r 5 n c 5 os 2s 3s 4 r 1 v c c o 5s 6 r 6 n c 5 o s 2s 3s 4 r 3 组块标注过程中遵循的原则是最长匹配原则( t h el o n g e s tm a t c h ) 。同时在生成组块 过程中发生冲突时，则利用规则发生的频度规定规则的优先级，优先考虑使用发生频度 大的规则来确定组块的类型，从而使划分和识别更为准确。 例如，对于一个句子中，如果出现词性标注序列为“c dmn n ”，这时我们按照最长 匹配原则，则根据规则4 生成一个名词组块n c ，而不是根据规则5 先生成一个量词组块 q c 。 通过统计语料库中的所有组块长度，假设每个组块的平均长度为a v g ( c k f ) ，则每 个组块分析的时间复杂度为o ( a v g ic k i ) ，对于一个长度为t 的语句，平均有t a v g ( f c k l ) 竖堕望丛生兰! 堕丝塑一 个组块，因此该语句分析的时问复杂度为o ( t ) 。有限自动机进行分析时是具有确定性的， 因此在速度上具有明显的优势。这样通过前面规则集的自动获取后，构造一个有限自动 机，就可以得到一个初始的标注器。 5 4 学习器的建立 如图5 1 所示，基于错误转换的机器学习方法还包括一个学习器。学习器的输入有 三部分资源：( 1 ) 经初始状态标注器标注的文本。( 2 ) 带标注的训练语料库，也就是j 下 确标注的文本。( 3 ) 转换规则模板集合，转换规则模板集合用来确定可能的转换规则空 问。学习器比较初始标注器生成的文本和正确标注文本，从错误中学习到新的转换规则， 组成转换规则集合，并应用到当前标注结果中。 5 4 1 转换规则模板的定义 在转换学习中，侯选转换规则空问是由一个转换规则模板集合来定义的。每个模板 也分为两部分，一是转换动作，一是转换条件。在模板条件部分指定了一个特征集合， 例如当前词左右两边的词、词性、组块标注符等，这些作为检查动作部分发生的相关因 素。转换动作部分为从种组块标注符号到另一种的转换。在对语料库的扫描过程中， 当某个词的组块标注符号发生错误时，这时在当前位置应用各个转换规则模板，纠正错 误组块标注符号，并匹配模板中各种相关因素，产生相应的转换规则。转换规则的重写 规则部分和触发环境部分分别由模板的动作和条件部分衍生。 令w 代表一个被错误标注的词，c l 和c 2 分别代表该词被错误标注的组块标注符号 和正确的组块标注符号，且c l ，c 2 属于组块标注符号集合( 见第二章) 。则转换动作 的形式如下：将词w 的组块标注符从c 1 转换为c 2 。 转换条件中包含的属性信息包括：当前词周围一定范围内的词性信息，用符号t 来 表示，用下标表示与当前词的位置关系，例如t t 表示当前词前一个词的词性标注；词 信息，用符号w 表示；组块标注信息，用符号c 表示。转换条件的形式为： 【t 1w + 。f c + ，】+ 。表示这三种因素可以互相组合作为模板动作的转换条件。 由此可以看出，所有模板的转换动作格式都是相同的，关键是选择模板的转换条件。 表5 2 列出了我们在组块分析中试用的部分模板，这里只表示转换条件部分各种因素的 组合。 第五章娃十规则方法的组块分析研究 表5 2 部分转换模板 模板转换条件含义 t 2 ，t l ，t o当前词及其前两个词的词性标注 t 2 ，t i ，t i当前词前两个词的词性标注和其后一词的词性标注 t 1 ，t o当前词及其前一个词的词性标注 t 1 ，t l当前词前后两个词的词性标注 t 2 ，c l当前词前一词的组块标注及前隔一词的词性标注 t i ，t o ，t i当前词及其前后两词的词性标注 c 2 ，c 1 ，w o当前词及当前词前面两词的组块标注 c ，l ，t o 当前词的词性标注及其前一个词的组块标注 t o ，t l ，c i当前词与其后一个词的词性标注以及前一个词的组块标注 c 一2 ，c 1 ，t o 当前词的词性标注及其前两个词的组块标注 c “t 1 ，t 0 当前词的词性标注及其前一个词的组块标注和词性标注 采用以上1 1 个模板应用到具有6 5 ，0 0 0 个汉词的训练语料库中，可以得到可能的转 换规则空间中包括的可能规则数目为6 ，6 0 0 条。 5 4 2 转换规则集合的获取 转换空间内的规则只是转换规则集合的候选规则，并非都要加入到转换规则集合中 来，只有对组块标注性能，也就是对标注正确率有所提高的规则才归入转换规则集合中。 首先把候选规则集中的每条规则分别运用于初始标注的结果，给其中每条规则打分， 选择得分最高的规则，并把这条规则作用于当前语料库。给规则打分的标准是： s c o r e ( r ) = c ( r ) 一w ( r ) r 表示一条候选转换规则，s c o r e ( r ) 表示一条转换规则r 的得分，c ( r ) 表示应用转换规 则r 后正确标注的词的数目，w ( r ) 表示应用规则r 后错误标注的词的数目。当萨确标注 的词的数目越多，则该规则的得分越高；错误标注的词的数目越多，规则得分越低；得 分由两方面来共同决定，即使应用一条规则后把错误标注纠正为正确标注的数目多，但 它同时可能也会把正确的标注转换为错误的标注，因此不代表该条规则的得分一定高。 每次把得分最高的规则运用于初始标注的结果作为下一轮循环的基础，并把这条规 则作为规则序列中的第一条规则输出，不断重复以上过程。算法结束的条件是所有侯选 堡堕型型型盐塑一 转换规则都加入到转换规则集合中或没有转换规则得分大于阈值。一般选择阈值为o ， 选择所有可能降低标注错误的规则，获得转换规则集合。以下列出了常用的5 条转换规 则。 ( 1 )动作：p c = n c ；条件：c i ( x ) - p ca 1 1 d t o ( x ) = n n 例：( 第一列表示组块标注，第二列表示词性标注，第三列为句中的词，第四列表示转 换动作，其他例句格式相同) p cp p cn n p cn n n o cc c n cn n n cn n v c cv v ( 2 ) 动作 例： a d v ca d p cp n cn n p cn n n cn n v pv v ( 3 ) 动作 例如： n cj j n cn n n cn n n cn n n cn n 以 机械 = n c 设备 和 工业 原材料 为主 p c = n c ：条件：t 一2 ( x ) = p 锄dc 1 ( x ) = n c 凡 属于 国际 金融= n c 组织 贷款 n c = n c $ ；条件：c 1 ( x ) = n c a 1 1 dt o ( x ) = n n 最佳 经济 效益 乡镇= n c $ 企业 ( 4 ) 动作：n c = n c $ ；条件：c 1 ( x ) = n ca n dt _ l ( x ) = n na n dt 0 ( x ) ：n r 例如： n cn n新华社 n cn r 深劫l= n c $ n c $n t二月 n cn t二十八日 ( 5 ) 动作：v c c - v c $ ；条件：c i ( x ) = v c c a n d t o ( x ) = v v 笙皇翌竺塑型塑堕竺望堡坌盟塑塾一 例如： v c cv c是 v c cv v借鉴= v c $ n c j j 发达 n cn n国家 根据上面的转换规则及其实例来看，基于转换的学习方法获取的转换规则是确定性 的。而且规则的使用是有序的，应用前面的规则执行转换动作，这样满足后面规则的触 发环境，j 可以执行后续的转换规则( 如规则示例2 ) 。因此前面的规则更具有归纳性， 而后续规则则更有特殊性【赵军1 9 9 9 】。 5 5 本章小结 本文中采用基于转换的规则方法完成组块标注的任务，分为三个部分：( 1 ) 初始组 块标注器中规则集的获取和标注的实现过程：( 2 ) 利用错误驱动的学习方法从训练集中 获取上下文相关的转换规则构造学习器；( 3 ) 将初始状态标注器与学习器结合起来进行 组块的划分和识别。 与b r i 儿基于转换的学习方法不同的是，学习得到的转换规则集合要与初始有限自动 机共同构成个组块分析器，而依照b r i l l 的思想，由于最初标注是非常任意的，所以 最终基于转换规则集合的学习器可以单独承担标注的任务。我们把任务进行分解，由于 最初耗费一定的气力去构造一个有效的初始组块标注器，最终降低了转换规则集合构建 的代价，但是需要初始有限自动机和转换规则集合共同集成在组块标注器中。 基于规则的方法在实际应用中仍然具有不可忽视的地位，同时结合了基于转换的错 误驱动的机器学习方法改进系统的性能。本章具体介绍了基于转换的机器学习方法和有 限自动机的原理，以及这两种方法如何结合在组块分析中得到应用。通过自动获取规则 集合构造有限自动机，实现初始状态的组块标注器。接着利用基于转换的机器学习方法， 把标注结果与f 确结果相比较，利用转换模板不断得到可以改进系统性能的转换规则， 构造出学习器。最后说明了系统是利用有限自动机的分析器和学习器共同完成组块分析 的任务。 笙查垦墨竺壅塑墨壅竺坌堑一 第六章系统实现及实验分析 第三章和第扛章分别介绍了基于统计和基于规则的组块分析方法。规则处理的优势 在于充分利用语言学知识，由有限自动机对组块进行快速的划分和识别。而统计处理的 优势在于二全部知识是通过对大规模语料库的参数训练得到的，有很好的一致性和较高的 覆盖率 周强1 9 9 5 。所以最好的方法是考虑把它们结合起来，充分发挥两者的优势。统 计方法我们选用了最大熵模型框架，规则采用了有限自动机和错误驱动的基于转换的规 则学习方法。它们相结合体现在两个方面，是在形成和完善规则和统计模型的过程中， 两者相辅相成：二是对新的语料进行分析时规则和统计方法并举，新语料由预处理器分 别送到规则和统计组块划分器中进行处理，并把新语料反馈到系统中，作为进一步改进 系统的资源。 前面已经介绍了最大熵模型和规则方法在组块分析中的一些关键算法。本章将从全 局角度详细介绍系统如何基于两种技术路线进行组块分析的实现过程。并给出了实验 结果和实验分析。本章首先描述了整个系统的实现流程，然后对具体算法和过程进行介 绍，最后在对实验数据整理和统计的基础上对各种方法的实验结果进行比较，并进行 全面、系统的分析和评价。 6 2 系统的实现流程 图6 1 为我们进行组块分析的系统流程。椭圆代表数据，矩形代表过程。根据特征 对模型提供信息增益的大小，得到一个最优的特征集，同时经由迭代缩放算法对特征集 中的所有特征进行参数估计，得到最大熵模型。当未经组块标注的测试语料经过最大熵 模型，根据模型提供的最优概率分布，得到相应的标注结果。训练语料是标准的已经组 块标注的文本，从这些文本的组块中提取组块规则，可以得到一个有限自动机( f s a ) 。 该有限自动机也可以对测试语料进行标注，产生一个标注结果。由于最大熵的统计方法 和有限自动机的规则方法可以互相弥补其不足，因此我们把两种方法产生的结果，与标 准的也就是正确的语料进行比较，发现在哪些情况下更适用哪种方法，这样就可以得到 两种方法中的正确结果，降低组块标注的错误率。反过来，从测试语料的标注结果中也 可以提取组块规则，以及进一步收集和加工新的语料。这样的反馈又改进了有限自动机 和最大熵模型。这里错误驱动的基于转换的机器学习方法体现在，学习选择标注方法的 使用环境。 6 i 图6 1 ：系统总流程 由此我们的系统分为三个部分： ( 1 、基于最大熵模型的组块分析器：其原理在第三章已经详细介绍过。 ( 2 ) 基于有限自动机的组块分析器；其方法在第五章作过介绍，这里由于效率的原因， 只采用了简单的有限自动机方法。把机器学习的原理用到第三部分中去，单独形成 一个模块。 f 3 ) 基于转换的学习器，根据最大熵模型和规则模型分别产生的标注结果与标准标注语 料进行比较，得到转换规则。这里的转换规则仍然分为：动作部分和触发环境。转 换动作为：选择哪种模型的标注结果；转换规则的触发环境：设置转换模板，学习 得到转换动作发生的具体条件。下面我们在第三节中对转换方法再作具体介绍。 6 3 系统的具体实现 6 3 1 组块库的获取 般来说，为了从语料库中统计所需要的知识，首先要对语料进行加工，然后对加 工的语料进行统计，并利用这些统计结果训练得到模型的参数。在第二章提到组块库可 以从宾州中文树库转化而来的，并且对宾州树库和组块都分别作了介绍，这里简要描述 了一下从树库获取组块语料库的原理。中文组块库是对汉语经过切分、词性标注和组块 标注的语料。收集语料很大时，完全靠人工来整理是不现实的。本文针对这种情况，提 出了获取语料库的三种途径。 ( 1 ) 对宾州树库进行转化，由于宾州树库是经过切分、词性标注和语法分析的语料，对 于提取组块提供了相对可靠的依据。c o n l l 2 0 0 0 中提供了用p e r l 编写的树库转换 为英文组块库转换的程序c h u n k l i n k p l s a b i n e2 0 0 们。我们借鉴该程序的转换原 笙查皇墨竺壅翌墨壅壁坌堑一 理，根据汉语组块的特点，从树库中抽取最小单位的短语作为组块，并作适当的调 整。从树库中抽取出组块。例如在树库中存在量词短语( c l p ) ，由于c l p 一般都 是由单独的量词构成的，并且和基数词或序数词共同组成数量短语( q p ) ，因此在 转换中就没有单独为c l p 设定对应的组块类型，而是抽取它稍高一层的数量短语 q p ，并把它转换为数量组块( q c ) 。即，对于其他的一些短语类型，如果构成该类型 的词语数目少，且它一定被包含在另一组块类型中，则也不为它单独设定一种类型 作转换，树库中的这种短语类型有v c d 、v r d 等。另外在树库中，有些形容词单 独可以形成一个形容词短语，但又被包含在名词短浯中，这种长度很小的形容词短 语我们不单独提取为形容词组块，而直接向上归并到一个名词组块中：对于一些修 饰动词的副词、本身构成副词短语的情况，我们也同样忽略副词短语，而提取动词 短语作为动词组块。 ( 2 ) 收集没有经过加工的文本，根据我们的切分和词性标注程序对语料进行加工，同时 依据宾州树库词性切分和标注的规范进行转化。最后通过我们的组块分析器进行组 块标注，这样逐步扩大我们组块库的规模。在收集没有经过任何加工的生语料时， 分词和词性标注是必须的第一步。为了保持和宾州大学的规范一致，我们首先采用 北京大学的切分和标注工具进行第一遍处理，然后设置与宾州大学标注体系相应的 对应关系，采用宾州中文词性标注的标准。同时我们已经具备基于规则和最大熵模 型的组块标注器，把经过词性标注的语料作为输入，产生相应的组块标注语料。 ( 3 ) 人工校对，不管是第一阶段的自动转化程序，和第二阶段的收集过程，在一定程度 上都会存在着一些错误，这就需要人工介入以纠正错误。例如：在自动转换成组块 库过程中，树库是针对新闻领域的语料，也存在一些片段构不成成功的句法分析树， 在树库中则用f r a g 标志处理。虽然这个片段不能构成树状结构，但它一般都可以 分解为若干个组块。这样我们通过手工处理这个片段，使树库中的f r a g 片段被分 解为多个组块。 前面两步的工作已经减轻了人工校对相当的工作量，同时通过人工校对，反馈正确 信息以进一步改善前面的自动工作，从而使人工劳动量逐渐降低。 6 3 2 最大熵的算法描述 最大熵模型系统和规则系统中的各算法本文在前面各章已经详细介绍过了，下面仅 给出这些算法的c 十+ 语言描述。 我们把最大熵模型框架在c + + 中设计为一个类m a x e n t r o p y ，对于其中一些具体算 法：g i s 和f i 算法则设计为该类中的成员函数，分别为s c a l e ( ) 函数和f i ( ) 函数，其中f i ( ) 调用s c a l e ( ) 函数。 墨堡型堡旦羔堕董竺茎一 算法6 一l ：g i s 算法的具体实现 输入：训练语料库文件 输出：特征参数文件 v o i dm a x e n t r o p y ：s c a l e ( ) d o u b l e f l o a t k l ：表示上次迭代后k l 距离值 d i f f ：表示k l 距离的变化 初始化模型中的各参数 i n i t p a r a m e t e r s ( ) ： p r e p a r e m o d e l ( ) ： k = o ： 设定模型收敛的条件，即k l 距离的阈值 k 1 = l e 9 9 ： 迭代过程开始 d o 保存参数值 f o r ( i = o ：i n rf e a t u r e s ：i + + ) o l dd a r a m e t e r s i = p a r a m e t e r s i ： o l dc o r r e c t i o nd a r a m e t e r = c o r r e c t l 0 np a r a m e t e r g a m m a ( ) ：计算初始参数值 p a r a m e t e r s c h a n g e d 2 l ： p r 印a r e _ m o d e l ( ) ：调整模型 d i f f = k l k l ： k l = k l ： k ”：记录迭代的次数 打印每次迭代后k l 距离，熵值、相对熵值 p ri n t f ( ”d t f t f t f t n ”，k ，k l ，h p ， l ) ： i f ( d i f f o ) 模型已经收敛 恢复原来的参数 f o r ( i = o ：i n r f e a t u r e s ：i + + ) p a r a m e t e r s i = o l dp a r a m e t e r s i ： c o r r e c t i o np a r a m e t e r = o l dc o r r e c ti o nd a r a m e t e r ： p a r a m e t e r s c h a n g e d = l ： p r e p a r e f n o d e l ( ) ： w h i l e ( ! ( d i f f k l m a x i t ) if( d i f f c a n d i d a t e s n r c a n d i d a t e s ) 从侯选特征集中抽取n 个特征 f o r ( j = o ：i a a 。a 。 ，有限自动机的构成为d f a 5 ( q ，q o ， t e ) ： ( 1 ) q 为规则r 右部各前缀的集合：q ： e ，a 。a ，a z ，a - m a n ) ： ( 2 ) q o = ： ( 3 ) t = a ma 。 ； ( 4 ) 对于q ( q q ) 和字符表中的一个输入符