（计算机应用技术专业论文）基于双向搜索的ilp算法构建汉语语义自动切分系统.pdf

摘要自然语言理解主要有两种途径。一种是利用各种语言规则对自然语句进行分析，得到句中各组成成分间的关系结构。另一种是基于数据分析方法，被称为自然语言理解中的“经验主义”，或称实证方法，它主要是利用大规模的语料库，采用概率的方法得到各语言现象共存的概率，在分析新语料时以共存概率的大小来确定语言成分之间的关系。基于规则的理性方法，本质是一种确定性的演绎推理方法。其优点在于根据上下文对确定事件的定性描述，能够充分利用现有的语言学成果。缺点是对一些不确定的事件则无能为力，同时规则的相容性和适应性也存在着限制。基于统计的方法是一种经验主义的方法，其优势在于它的全部知识都是通过对大规模的语料库加工分析而得到的，可以获得很好的一致性和覆盖性。基于统计的方法是一种非确定性的定量分析方法，这种定量分析是基于概率的，因此必然会掩盖小概率事件的发生。本文考察一种新的实证途径，采用结构化的知识表示，应用i l p 方法解决自然语言语句切分分析器的获取问题。自然语言语义结构的分析是自然语言理解的基础，可分为二个层次，其一是研究能充分表达自然语句内各成份间语义关系的表示方法；其二是研究如何将自然语句转换成某种期望的语义表示形式，即在自然语言语句和其对应的语义表示问建立正确的映射，完成这种映射也称为自然语言语句的语义切分分析，这也是本文研究的重点之一，本文给出了一种基于i l p 算法的自动语义切分器的构建系统i c a s p ，并通过一个切分示例来说明i c a s p 构建的切分器将自然语句映射成论旨角色语义表示的方法途径。论旨角色语义分析的基本思想是：在句中起中心作用的动词，同参与动作的各个成分个体一起构成句子的“语义格”框架，以此描述自然语句中各组成成分间的深层语义关系，表达施事( 谁做的) 、受事( 对谁做的) 、工具( 用什么工具) 等概念所表示的语法语义关系。“切分”一词常用来表达将句子转换成能够明确描述句子语法关系的一种层次结构，依据某一上下文无关文法，自然语句可能可被切分为由句子成分加入适当的标注组成的层次结构，然而局限在语法结构上的切分只是自然语言语句理解基于双向搜索的i l p 算法构建汉语语义自动切分系统问题中的- 4 , 部分，事实上，自然语言理解要考虑的是深层的、面向语义上的问题，至少对句子的切分分析要指出句中成分的一些重要语义关系，诸如谁对谁做了什么等等，对自然语句语义层次上的切分分析称为语义切分。针对自然语句旨角色语义表示，本文设计并实现了一种基于i l p 算法的自然语句语义切分器构建系统i c a s p ，i c a s p 采用一种新颖的i l p 算法i c c r 从语料中归纳学习控制规则，i c a s p 构建的语义切分器就是在这些控制规则的指导下完成对自然语言语句的切分操作，i c c r 融合了自顶向下和自底向上的i l p 算法思想，在保留其基本的方法的同时有效地克服了各自的弱点，自底向上的归纳技术保证i c c r 可以很好的处理具有高结构化特征的样例；自顶向下的逐步特殊化方式，使得i c c r 在具有以增强、相对抽象的方式表达的背景知识时，仍能有效地进行归纳。i c c r 可以使用增强形式表示的背景知识，无需显式的构造谓词便可以处理包括函数的样例，能以简捷的方式学习递归方式描述的子旬，并在一个简单的框架中根据归纳需要发明新谓词。i c c r 是一个双向搜索i l p 算法，在自顶向下的搜索过程中采用了基于绑定的一阶规则评估函数，相比常用的基于规则所覆盖的正、负样例数目的规则评估函数，新的规则评估函数能更好地量化一阶规则启发式性能，并能有效地区分等价规则的优劣，可提高算法的搜索效率和规则的可读性，引导算法沿着正确、高效的路径搜索。在某种意义上，机器学习算法可以描述为在一个很大的由可能的假设组成的空间中进行搜索，以确定其中最符合学习者所观察到的数据和任何先验知识的目标假设，i l p 算法也不例外。无论是自顶向下搜索还是自底向上搜索均是启发式的，为降低爬山搜索收验到局部最优的风险，同时保持爬山搜索的高效剪枝特性，常采用束搜索策略搜索假设空间。对于k - s i z e 束搜索算法，本方从选择这k 条搜索路径的方式上，提出几种束搜索算法优化方化，并且针对二个i l p 基准学习任务进行了比对实验验证了这些优化思想。关键词：自然语言理解，语义切分，切分器构建，论旨角色，控制规则，评估函数，束搜索。i ia b s t r a e tt h e r ea r em a i n l yt w oa p p r o a c h e st on a t u r a ll a n g u a g eu n d e r s t a n d i n g t h ef i r s to n ei su s i n gs o m el a n g u a g er o l e st oa n a l y s e st h er e l a t i o n s h i pi n a l lc o m p o n e n t so fn a t u r a ll a n g u a g et e x t t h i sa p p r o a c hi sc a l l e d “r a t i o n a l i s t i ca p p r o a c ”t h es e c o n do n ei sb a s e do nd a t aa n a l y s i sa n di sc a l l e d “e m p i r i c a la p p r o a c h ”t h i sa p p r o a c hi sb a s e do nah u g ec o r p u s ，u s i n gp r o b a b i l i s t i cm e t h o d st og e tt h ec o n c o m i t a n c ep r o b a b i l i t yo fe v e r yl a n g n a g ed h e n o m e n a t h e s em e t h o d si d e n t i f yt h er e l a t i o n sb yt h ev a l u eo ft h ec o n c o m i t a n c ep r o b a b i l i t yw h e nt h e ya n a l y s e st h ec o r p u s t h em e t h o d sb a s e do nl a n g u a g er u l e sa r ee s s e n t i a l l yd e d u c t i o nr e a s o n i n g i t sa d v a n t a g ei st h eq u a l i t a t i v ed e s c r i p t i o na c c o r d i n gc o n t e x t i tc a nu t i l i z et h ef r u i to fm o d e mi i n g u i s t i c s t h ed i s a d v a n t a g ei st h a tt h e yc a n td e a l 谢t ht h eu n c e r t a i ne v e n t s w h i l et h e r ea r es o m er e s t r i c t i o no nt h er u l e sc o n s i s t e n c ya n da d a p t a b i l i t y t h ea p p r o a c hb a s e do ns t a t i s t i c si sa l le m p i r i c a lo n e t h ea d v a n t a g ei st h a ti tg e t sa l li t sk n o w l e d g eb ya n a l y z i n gt h eh u g ec o r p u s i tc a r la c h i e v eb e t t e rc o n s i s t e n c ya n dw i d ec o v e r i n g t h em e t h o db a s e do ns t a t i s t i c si sa l lu n d e t e r m i n e dq u a n t i t a t i v ea n a l y s i s d h et ob a s i n go np r o b a b i l i t y , t h ee v e n t sw i t hl o w e s tp r o b a b i l i t ya r eh i d d e n t h i sp a p e rc o n s i d e r san e we m p i r i c a la p p r o a c h a d o p t i n gs t r u c t u r a ld a t ad e s c r i p t i o n ，i l pm e t h o d sa r eu s e dt os o l v et h ep r o b l e m so f p a r s e ra c q u i r i n g t h es t r u c t u r ea n a l y z i n gi st h eb a s eo fn a t u r a ll a n g u a g ec o m p r e h e n s i o n i tc o u l db ed i v i d e di n t ot w ol e v e l s ：t h ef i r s to n ei st os t u d yt h es e m a n t i cr e p r e s e n t a t i o n so fa 1 1c o m p o n e n t si nan a t u r a ls e n t e n c e ：t h es e c o n do n ei st oe s t a b l i s ham a pb e t w e e nt h e s er e p r e s e n t a t i o n sa n dn a t u r a ll a n g u a g es e n t e n c e s t h i si so n ee m p h a s e so ft h i sp a p e r i nt h i sp a d e lt h es y s t e mi c a s pt h a tb u i l d sa na u t o m a t i c a l l ys e m a n t i cp a r s e ri sp r e s e n t e d t h ep a r s i n gm e t h o do fap a r s e rc o n s t r u c t e db yt h es y s t e mi c a s pi si l l u s t r a t e db yac a s e r o l ep a r s i n ge x a m p l ei nt h i sp a p e r t h eb a s i ci d e ao fc a s e - r o l es e m a n t i cp a r s i n gi s ：t h ec e n t r a lv e r bc o m b i n e dw i t ho t h e rc o m p o n e n t si nt h es e n t e n c ef o r m st h e“s e m a n t i cc a s e r o l e ”f r a m e t 1 1 i sf r a m ei su s e dt od e s c r i b et h ed e e ps e m a n t i cr e l a t i o n sw i t h i ne v e r yc o m p o n e n to fan a t u r a ll a n g u a g es e n t e n c e ，e x p r e s s i n gt h ea g e n t i v e s ，p a t i e n t sa n di n s t r u m e n t sa n do t h e rs e m a n t i cc a s e si nt h es e n t e n c e t h ew o r d “p a r s e ”i so f t e nu s e dt oe x p r e s st h ea c t i o nt h a tt r a n s l a t i n gan a t u r a ll a n g u a g es e n t e n c ei n t oal a y e rs t r u c t u r eo ft h es e n t e n c es y n t a c t i cr e l a t i o n s a c c o r d i n gt os o m ec o n t e x t f r e eg r a m m a t , an a t u r a ll a n g u a g es e n t e n c em a vb ep a r s e di n t oal a y e rs t r u c t u r ew i t hs o m ea n n o t a t i o n so fc o m p o n e n t si nt h es e n t e n c e b u tt h ep a r s i n go nt h es y n t a c t i c1 e v e rc a nb eo n l yv e r ys m a l lp a r to fc o m p r e h e n s i o no ft h es e n t e n c e i nf a c t n a t u r a ll a n g u a g ec o m p r e h e n s i o ns h o u l dc o n s i d e rt h es e m a n t i co r i e n t e dp r o b l e m s a tl e a s t p a r s i n gas e n t e n c es h o u l dp o i n to u ts o m ei m p o r t a n tr e l a t i o n si nt h es e n t e n c e s u c ha sw h oh a v ed o n es o m e t h i n gt os o m e o n e e t c p a r s i n gi ns e m a n t i cl e v e l i sc a l l e ds e m a n t i cp a r s i n g i nt h i sp a p e r , as e m a n t i cp a r s e rc o n s t r u c t i n gs y s t e mi c a s pi sd e s i g n e da n di m p l e m e n t e d i c a s pi sb a s e do nan e wi l pa l g o r i t h mi c c r t h en e wi i i基于双向搜索的i l p 算法构建汉语语义自动切分系统i l pa l g o r i t h mi su s e dt o1 e a r nc o n t r o lr u l e sf r o mc o m u si ni c a sp t h es e m a n t i cp a r s e ri sg u i d e di np a r s i n gas e n t e n c eb yt h e s ec o n t r o lr u l e s i c c ri n t e g r a t e ds o m ea d v a n t a g ea s p e c t so fc u r r e n ti l pm e t h o d s i np a r t i c u l a r , i tc o m b i n e sab o t t o m - u dm e t h o ds i m i l a rt of o i lw i t hat o p d o w nm e t h o ds i m i l a rt og o l e m i ta l s oi n e l u d e sp r e d i c a t ei n v e n t i o na n dr e c u r s i v ep r o g r a ml e a r n i n g c o n t r a s t i n ge x p e r i m e n t sd e m o n s t r a t et h ea d v a n t a g e so f t h i sm e t h o d i c c rs e a r c h e sf i r s t - o r d e rr u l e ss p a c ei nt w od i r e c t i o n s 、册l c ni ts e a r c h e saf i r s t - o r d e rr u l e ss p a c et o p - d o w n i tu s eah e u r i s t i cf u n c t i o nt oe v a i u a t ea 1 1t h ec a l l d i d a t er u l e s t l i sn e wh e u r i s t i cf u n c t i o ni sb a s e do nb i n d i n g s c o m p a r i n gt ot r a d i t i o n a le v a l u a t i o nh e u r i s t i cf u n c t i o n sb a s e do nt h en u m b e r so fe x a m p l ec o v e r e db yt h ee v a l u a t e dr u l e s i tc a l lm e a s u r et h ef i r s t o r d e rr u l e sw i t hm o r ea c c u r a c y ，a n dc a nd i s t i n g u i s ht h er u l e si na l le q u i v a l e n tc l a s so ff i r s t o r d e rr u l e s i tc a ni m p r o v et h ee m c i e n c yo fs e a r c ha n dr e a d a b i l i t yo ft h el e a r n e dr o l e s 1 e a d i n gt h ea l g o d t h r at os e a r c ha l o n gw i t hc o r r e c ta n de f f i c i e n tp a t h s 0 d eu s e f u lp e r s p e c t i v eo nm a c h i n el e a r n i n gi st h a ti ti n v o l v e ss e a r c h i n gav e r yl a r g es p a c eo fp o s s i b l eh y p o t h e s e st od e t e r m i n eo n et h a tb e s tf i t st h eo b s e r v e dd a t aa n da n yp r i o rk n o w l e d 9 r eh e l db yt h el c a m e lm a c h i n el e a r n i n gc o u l db ed e s c r i b e da ss e a r c h i n gt h r o u g hah u g eh y p o t h e s i ss p a c e ，s oa st og e tat a r g e th y p o t h e s i sc o n s i s t e n tw i t ho b s e r v e dd a t a , s od oi l pa l g o r i t h m s b o t hs e a r c h e sf r o mt o pt ob o t t o mo rs e a r c h e sf r o mb o t t o mt ot o pa r eh e u r i s t i cs e a r c h e s b c a ms e a r c ha l g o r i t h mr e t a i n si t sa d v a n t a g ei ne f f i c i e n c yw h i l er e d u c i n gt h er i s ko fc o n v e 画n gt ol o c a l l yo p t i m a lh y p o t h e s e s b e a ms e a r c ha l g o r i t h mi sw i d e l yu s e di na if i e l d t ok s i z eb e a ms e a r c h d u et oo n l ykp a t h sa r em a i n t a i n e dt h ek e vt oo p t i m i z et h ea c c u r a c yo fb e a ms e a r c hi sh o wt os e l e c tt h ekp a t h s i nm o s to fs e a r c ha l g o r i t h m s ，t h ekc a n d i d a t e s 、v i t l lt h em o s t1 1 i g hp e r f o r m a n c em e a s u r ev a l u ea r es e l e c t e da te a c hs e a r c hs t e p i nt h i sp a p e r ，t h ea u t h o rp r e s e n t e ds o m em e t h o d so fc a n d i d a t es e l e c t i o no fb e a ms e a r c ha p p r o a c h e s ，a n dt h et h o u g h to fa v o i d i n g “砌lo fb l o o db r o t h e rn o d e s ”i sp r e s e n t e d t h ee x p e r i m e n t sa r ed o n eo nt h eu c ir e p o s i t o r yo f m a c h i n e1 e a r n i n gd a t a b a s e s k e y w o r d s ：n a t u r a ll a n g u a g ec o m p r e h e n s i o n ，s e m a n t i cp a r s i n g ，p a r s e rc o n s t r -u c f i n g ，c a s e - r o l e ，c o n t r o lr u l e ，e v a l u a t i o nf u n c t i o n ，b e a ms e a r c h i v独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得安徽大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名吁五签字日期：。l 扩杉年力月。彦目学位论文版权使用授权书本学位论文作者完全了解安徽大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权安徽大学可以将学位论文的全瓿或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书)学位论文作者签名：多 呵上导师签名：，雾笸f 幻签字日期：o 矿，多年易月多乡日签字日期：o 。疗年乎月) 驴日学位论文作者毕业去向工作单位：山东大学威海分校计算机系电话：0 6 3 1 5 6 88 505通讯地址：山东威海市文化西路山大威海分校计算机系邮编：2 6 42 0 9tk，lll1 第一章绪论让计算机准确地理解人类的自然语言、人类与计算机间进行自由对话是人们的理想之一，目前己研究出一系列自然语句的结构化、形式化表示方法，计算机可从这些表示中获得更多的语义信息，研究将自然语言语句转换成能表达其中语义的某种结构化( 或形式化) 表示，对于推动自然语言理解的进展有着重要意义。一阶子句的强表达能力和良好的可理解性，以及逻辑程序设计坚实的理论基础，使得归纳逻辑程序设计成为当前广受关注的的机器学习前沿研究课题，已在诸多领域展示出良好的应用前景，本文研究的自然语句语义自动切分器便是利用i l p 技术解决切分器中控制规则的获取问题。同样是一阶子句强表达能力，导致目标假设空间巨大，即i l p 方法的弱语言偏置特性，为了保证i l p 方法在实际应用中可行，研究i l p 方法的搜索偏置显得尤为重要。1 1 自然语言理解自然语言理解一直是人工智领域中最富挑战性的一个分支，其基本任务之一是对作为输入的自然语言文本进行转换或切分，输出对应的方便于计算机操纵的语义表示语言文本。对于语义切分问题，传统的理性途径( r a t i o n a l i s t a p p r o a c h )是搜寻语言处理所需的基于规则表示的知识，相关研究人员提出了多种框架，用以表示和计算语言学知识( l i n g u i s t i ck n o w l e d g e ) 。到目前为止，通过这些传统的途径还无法构建具有良好精确性、健壮性、和宽覆盖性的自然语言理解系统，即便是局限于一个特定领域的“子语言”理解系统的建造也是很困难、耗时，且运行状况经常是低效、不完备的，且难以移植到一个新的应用领域【” 2 1 。实证方法( e m p i r i c a l a p p r o a c h ) 用基于语料自动获取语言模型，取代传统的推理途径中手工产生的规则。实证方法将自然语言处理系统的建造工作有效地分为二个部分：标注( a n n o t a t i o n ，建立语料) 和获取。第一部分是人类专家的职责( 通常使用一些辅助工具) ，训练语料用以示例系统要进行自然语言分析的类第1 页基于双向搜索的i l p 算法构建汉语语义自动切分系统型，例如，对自然语句进行论旨角色语义切分、或进行语法切分等。若待建的系统是进行宽覆盖的自然语言语法切分，则所需的语料是很多由自然语言语句文本与对应的语法树配对组成的样本集合，这种语料称作t r e e b a n k ( m a r c u s ，s a n t o r i n i ，& m a r c i n k i e w i c z ，1 9 9 3 ) 3 】。第二部分，即知识获取，是一个机器学习问题，给定合适的训练语料，采用机器学习算法自动构建一个切分器( 切分分析程序系统) ，该切分器能将语料及其外的自然语言文本转换为所期望的表示形式。考察语音识别的研究过程，基于语料的自然语言处理首先主要是将统计技术就用到诸于语音标注、上下文无关文法或转移网络的归纳、这些方法回避传统、符号的方法而倾向概率、统计的方法，这些方法均将所获取的知识表示为命题形式，这就意味着，通过考察一个确定的属性集合f 如语法范畴，s y n t a c t i cc a t e g o r y ) 、当前结点周围的确定上下文，对切分树中的一个结点标识，而具体可能要测试哪个属性已由获取系统的设计者事先确定好了。这种途径在机器学习中称作特征向量表示( f e a t u r e v e c t o rr e p r e s e n t a t i o n ) ，决策上下文是由事先选择的特征值定义的有限向量【4 1 。我们可以期待这种简单、非结构化模型能有效地处理语音识别问题，因为语音在本质上是线性的；然而这种方法在语法分析这类领域也获得相当的成功，而这类领域通常需要构造和操纵无限、高结构化表示的知识，这主要得益于这样二个方面：1 ) 系统设计者投入大量的精力，手工精心选择合适的属性集、精心挑选用以学习的有限文本；2 ) 在一致的大语料上进行训练，尽管这种简单的模型没有强有力的表达能力，但知识可能是很完备的。本文考察一种实证的途径，使用结构化的知识表示。在传统的n l p 中，关系表示是个有用工具。实际上，所有这些工作都是使用基于手工的语法，目前还没有一个实用的关系数据自动构造系统。然而，归纳逻辑程序设计( i l p ) 研究的是学习一阶逻辑描述的知识；i l p 是机器学习的一个分支，越来越受关注。由于一阶逻辑的表达能力，i l p 方法可以学到关系和递归的概念，而基于属性描述语言的机器学习算法难以做到。本文研究的主要内容是应用i l p 方法解决切分器的获取问题。1 2 基于i l p 构建语义自动切分系统第2 页第一章绪论i c a s p ( i n d u c t i v e l yc o n s t r u c ta u t o m a t i cs e m a n t i cp a r s e n 是生成自然语句切分器的一个通用途径，所涉及的学习问题可用图1 1 示例。给定合适的语料，i c a s p生成一个切分器，该切分器可将语料中及之外的语句映射成所期望的某种结构化表示。i c a s p 适应多种切分要求，这也是i c a s p 的特点之一。圣孽i 签j 妻烹曼皇；汉语语义切分燕墨塑坌垒妻?i。，：j ”系统；：一= ”图1 - 1 ：自然语句切分器获取i 司题f i g u r e1 - 1 ：t h ep a r s e ro f n a t u r a ll a n g u a g es e n t e n c ea c q u i s i t i o np r o b l e m“切分”一词常用来表达将句子转换成能明确描术句子语法的一种层次结构，例如，句子：“小明看电影”可能被切分为由句子的成分加入适当的标注组成的层次结构： s 【n p 小明】 vp 看 n p 电影珈。然而局限在语法结构上的切分只是句子理解问题中的一小部分，事实上，n l p 要考虑的是深层的、面向语义上的问题，至少对句子的切分分析要指出旬中组成成分间的一些重要关系，诸如谁对谁做了什么等等。因此作为语言理解系统要采用更面向语义的语言( m r l ：m e a n i n g r e p r e s e n t a t i o n l a n g u a g e ) 来表示对句子的切分分析结果，如论旨角色( c a s e - r o l er e p r e s e n t a t i o n ) ，上述句子可以被切分为： 看，a g e n t ： d x 明】，p a t i e n t ： 电影】( 其中a g e n t 表示“施事语义格”，p a t i e n t 表示受事语义格) ，表示由“小明”在“电影”上实施了“看”的动作，另外，对于一些数据库应用，可能期望将表达查询要求的自然语言语句切分成一种逻辑结构，这种结构可以方便地由自动演绎算法来操纵，对应上述句子的一阶谓词表示可以是：小明( m 1 ) 八电影( b 1 ) 八看( m 1 ，b 1 ) 。第3 页基于双向搜索的i l p 算法构建汉语语义自动切分系统在系统i c a s p 中“切分”一词具有相对广泛的意义，它可以将输入的句子根据应用需要，转换成所需的语义表示形式，i c a s p 可以用来获取进行语法切分的切分器、进行论旨角色切分的切分器、以及一阶逻辑切分的切分器，这种弹性是系统i c a s p 的主要特征之一。i c a s p 通过学习控制规则来实现切分器归纳，p r o l o g 程序描述的控制规则用以控制切分器的切分动作。i c a s p 采用一种新颖的i l p 算法从切分语料中归纳学习控制规则。归纳算法本身是个一般性的归纳学习系统，已在一些基准性的i l p问题( b e n c h m a r kt a s k ) 上进行测试。归纳算法能从结构化的本文中自动提取相关部分，构造新的谓词以表达一些进行精确切分所必需的新的词汇和短语。对于不同切分要求，切分器只需替代相应的切分框架，其中的控制规则学习部分无需变化，从而对i c a s p 系统赋于多种切分能力。1 3 归纳逻辑程序设计技术归纳逻辑程序设计( i n d u c t i v el o g i cp r o g r a m m i n gi l e ) 是由机器学( m a c h i n el e a r n i n g ) 与逻辑程序设计( l o g i cp r o g r a m m i n g ) 发展并结合所形成的一个研究领域。i l p 继承了逻辑程序设计的坚实的理论基础，继承了机器学习实验的方法和面向实际应用的方向，使得i l p 的研究不但为机器学习提供深入的理论与方法，也为知识工程等人工智能的应用领域提供新的强有力的技术支持，因而i l p 成为机器学习的前沿研究课题之- - 5 1 。与传统机器学习方法有所不同，i l p 借助逻辑程序设计的理论与方法，利用背景知识学习一阶规则。一阶规则较之基于属性一值表示方式的规贝i j 、决策树及神经网络具有更强的表达能力，使归纳结论内涵更加丰富和精确。因此i l p 有能力克服存在于传统机器学习中的两个主要限制，即知识表示机制的限制与学习中背景知识利用的限制【6 】。i l p 已在广泛的应用领域取得成功，如生物化学、有限元网格设计、软件工程、a g e n t 技术等 7 】。按算法的搜索方向为分类标准，i l p 系统可分为三类：第一类是主要使用一般化操作的系统，如c i g o l 、n i a r v i n 和g o l e i d t s d 3 1 。其中g o l e m 为这类i l p 系统的代表，这些系统由覆盖已知的某个正例的特殊规则开始，使用一般化操作来产生新的假设子旬，新子句覆盖更多的正例，并排斥所有第4 页第一章绪论的负例。这类系统基于极小一般化操作来逐步构建目标子句，要求背景知识表示为基本事实的集合，对于实际问题，这种明细表达会非常庞大，由此构建的子旬数量也会急剧增加，其次这种学习策略对示例的分布情况敏感，若只提供一个随机的示例样本，g o l e m 难以构造出足够抽象的假设，降低了学习系统的性能。第二类是主要使用特殊化操作的系统，如m a r k u s 、m f o i l 、f o c l 、f o i l 和c l a u d i e n 等 1 4 - 2 2 j 。其中f o i l 是这类系统的代表，这些系统由能覆盖所有已知训练例的子句开始，使用特殊化操作以一般到特殊的方式构造假设子句，当假设子句能够排除所有负例时，这一子句作为部分归纳结论而保留下来，子句构造过程周而复始，直至满足i l p 语义要求。f o i l 也使用背景知识，但它是利用背景知识提高性能，自顶向下的算法可以很方便地利用以强化方式相对抽象表达的背景知识，有效评估各种相互竞争的假设，f o i l 一个根本的弱点就是其学到的子句与函数无关，任何函数须由包含显示构造谓词的背景知识处理，构造谓词的增加会显著降低系统的性能。第三类是混合使用一般化和特殊化的操作的系统。这些系统由己知正例集或适度一般的假设开始，视结论的一般化程度交叉使用一般化和特殊化操作来构造假设子句。混合式归纳方式对假设的搜索较为细致，但需要仔细地设计控制策略。本文给出了双向搜索i l p 算法i c c r ( i n d u c t i v e l y c o n s t r u c t c o n t r o l - r u l e s ) ，将自顶向下搜索策略和自底向上搜索策略有机地给合起来，在保留其基本的思想方法同时有效地克服了各自的弱点，自底向上的归纳技术保证i c c r 可以很好的处理具有高结构化特征的样例，而无需充当“构造器”的谓词；自顶向下的逐步特殊化方式，使得i c c r 在具有以强化方式相对抽象表达的背景知识时，仍能有效地进行归纳。i c c r 可以使用增强形式表示的背景知识，无需显式的构造谓词便可以处理包括函数的样例，能以简捷的方式学习递归方式描述的子句，并在一个简单的框架中根据归纳需要发明新谓词。一阶规则学习可看作是对规则空间的搜索，搜索正确刻画了数据特征的规则或规则集合。为系统地、有效地组织规则空间的搜索，一种有效的方式是通过定义规则空间的“更一般关系”来结构化待搜索的规则空间 2 引。一阶规则学习算法通常采用一阶规则间的e 包容序来结构化待搜索的规则空间。i c c r 也同样采用0 一包容序结构化一阶规则空间，以规则评估函数引导搜索目标规则。但一阶规则空第5 页基于双向搜索的 l p 算法构建汉语语义自动切分系统间中的o 包容序是一个q u a s i o r d e r 序( 自反的和传递的) 【2 。采用常用的基于规则覆盖例子数目的评判标准，沿着这个q u a s i o r d e r 序学习一阶规则时，存在一阶规则的等价类问题，即无法区分等价类中规则的相对优劣，这会使搜索过程盲目地倾向于长规则，将严重地降低算法的搜索效率和规则的可读性。产生等价类问题的原因在于，在通常采用的基于规则覆盖正、负例个数的评判标准中，目标谓词或背景知识谓词构成的条件原子的描述作用被存在量词笼统地概括，没有充分利用隐含在例子和背景知识中的信息，从而无法区分等价规则的优劣。我们在绑定概念的基础上，依据信息理论，采用了基于绑定的规则评估函数。新的规则评估函数能量化一阶规则的优劣，且可充分利用隐藏在例子和背景知识中的信息，判别出规则的条件原子对规则描述数据特征的准确影响，从而区分出等价规则的优劣。分析表明，新的规则评估函数能更好地指导算法的搜索方向，可提高算法的搜索效率和规则的可读性。在某种意义上，机器学习算法可以描述为在一个很大的由可能的假设组成的空间中进行搜索，以确定其中最符合学习者所观察到的数据和任何先验知识的目标假设【25 1 ，实践中，穷尽搜索假设空间是不可能的，启发式搜索便是一种自然合理的选择。爬山搜索算法能高效地实现搜索剪枝，求解实际问题时，能在庞大的假设空间中，找到最优或近似最优解，事实上，许多著名的算法都采用爬山贪婪算法搜索对应的假设空间，如f o i l t 2 6 1 等。爬山搜索是基于候选假设的启发式函数值，只沿着“最有期望”的一条路径搜索目标假设，根源于其不回溯特性，爬山算法容易收敛到局部最优解而非全局最优解。束搜索算法保持了爬山搜索算法的高效剪枝特性，同时能有效减小爬山搜索收敛到局部最优解的风险，人工智能领域广泛采用束搜索策略，如遗传算法( g a )l ，子群发现算法c n 2 一s d 2 s ! 等。因此，有必要对束搜索的精度优化方法进行研究。一般地，对于k - s i z e 所选的k 个候选成员性能量度值越邻近，对应的k 条搜索路径收敛到同一局部最优解的可能性越大。换句话说，如果在候选成员集合中按某种方式分散地选择k 个候选作为下一步搜索入口，那么这k 条路径收敛到不同的局部最优解的可能性大，因此每一搜索步从候选成员集合中直接选取具有最高性能量度值的k 个成员作为进一步搜索的入口，不是一种最有效的方法。基于上述认识，本文从侯选成员的选取方法为优化研究入口，提出了几种能有效避第6 页第一章绪论免k 条路径收敛到相同的局部最优解的候选成员选取方法，并通过对比实验直观地说明这几种方法对束搜索精度的影响。1 4 研究内容及论文安排1 4 1 本文的主要研究内容本文将开展汉语自然语句自动切分器获取方法的研究，研究内容主要包括以下二个方面。1 ) 如何将自然语句转换成某种或某几种形式化的表示，这些形式化的表示能表达自然语句中各组成成份间深层的语义关系。着重研究了基于语料的自然语句语义切分器的获取途径、目标语义自动切分器对自然语句的切分方式、切分效果。其中包括确定自动语义切分器的获取框架、针对论旨角色语义表示设计并实现一个基于语料的自然语句语义自动切分器的构建系统i c a s p 、对i c a s p 获取的切分器进行实验测试及分析。2 ) i c a s p 中用以学习控制规则的i l p 算法i c c r 的研究、设计和实现。i c c r本身是一个通用的i l p 算法，其功能是从示例及背景知识中学习一阶规则，相关研究主要有以下内容：i c c r 的双向搜索策略引导搜索的一阶规则评估函数。一阶谓词递归定义的学习机制及发明新谓词的方法。束搜索精度优化方法。1 4 2 本文的结构及内容安排本文共分7 章，其内容组织如下：第一章绪论。本章简要介绍了与本文研究直接相关研究背景，包括当前i l p 系统的搜索方式、假设空间的束搜索策略、引导搜索的启发式评估函数、自然语言理解及语义切分等相关研究内容，据此说明本文的研究工作在其中的位置、作用等。第二章自然语言理解基础理论。本章对自然语言理解进行了简要概述，着重介绍了几种以语义为主的分析方法。第7 页基于双向搜索的i l p 算法构建汉语语义自动切分系统第三章构建语义自动切分系统。所谓语义切分就是将自然语言语句映射为某种结构化( 或形式化) 的表示，这种表示有助于计算机从中“理解”对应的自然语句中的语义。本章提出一种有效的语义切分系统构造方法，其基本思想是通过分析样例生成初始切分程序，采用第五章描述的双向搜索i l p 学习算法学习控制规则，最后用学到的控制规则来精化初始切分程序，从而构造出确定性的语义切分