（计算机软件与理论专业论文）svm和最大熵相结合的中文机构名自动识别.pdf

大连理工大学硕士学位论文 摘要 未登录词的识别是汉语自动分词的难点之一，而中文机构名是未登录词的一个重要 部分，涉及广泛，种类繁多，形态各异，且绝大多数未收入到词典中。中文机构名的自 动识别对提高汉语自动分词和句法分析的精确率都有重要的意义。 本文提出一种支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 和最大熵相结合的中文机 构名自动识别方法。中文机构名识别范围限定在以机构名特征词为结尾的完整机构名。 根据机构名的特点，将机构名识别分为两个部分，后界判断和前部标注。对文本中出现 在特征词典的词，基于s v m 判断是否是机构名特征词( 后界判断) ，从识别出的机构名 特征词前词开始向前基于最大熵标注，直到标注到非机构名成分停止标注( 前部标注) ， 然后继续在文中重复上述过程。 为了提高后界判断效率，提出驱动式识别方法，对文本中出现的收录在特征词典的 词进行后界判断，识别出该词是否是机构名特征词，对识别出的机构名特征词开始前部 标注。由此可知，后界判断问题是二值分类问题，而s v m 是一种优秀的二值分类器， 因此基于s v m 的后界判断模型可以有效地解决机构名特征词识别问题。根据机构名特 征词的统计分析和语法特征，建立基于s v m 的后界判断模型。 机构名前部词组成比较复杂，由于最大熵可以灵活地将许多分散、零碎的知识组合 起来，对复杂问题的解决有较好的效果，同时最大熵以较好的效率解决多类分类问题， 因此最大熵的前部标注模型有效地解决了比较复杂的中文机构名前部词识别问题。根据 机构名前部词的特征和统计分析结果，制定最大熵特征模板，构建特征集并进行参数估 计获得基于最大熵的前部标注模型。 实验表明，s v m 和最大熵相结合的中文机构名自动识别方法是有效的：系统开式 召回率和精确率分别达9 1 0 5 ，9 3 5 9 ，f 值为9 2 8 4 。和当前同类文献相比，本识 别系统取得了比较好的识别结果。并且本文所提出的方法具有较强的推广能力，利用本 方法还可以对其它未登录词如人名、地名等进行识别。 关键词：中文机构名；驱动式；最大熵；支持向量机 大连理工大学硕士学位论文 a u t o m a t i ci d e n t i f i c a t i o no fc h i n e s eo r g a n i z a t i o nn a m e s b a s e do i ls v ma n dm a x i m u me n t r o p y a b s t r a c t c h i n e s eo r g a n i z a t i o nn a m er e c o g n i t i o nb e l o n g st ot h ed o m a i no ft h er e c o g n i t i o no f n a m ee n t i t y ，w h i c hi sab a s i cr e s e a r c hw o r ki nc h i n e s el e x i c a la n a l y s i s i ft h e r ea r es o m e b i l b l o w nc h i n e s eo r g a n i z a t i o nn a m e si nt h et e x t , t h e yw i l la f f e c tt h ec o r r e c t n e s so f s e g m e n t a t i o na n dl e x i c a la n a l y s i s ，t h i sr e q u i r e st h es e g m e n t a t i o ns y s t e mo fh a v i n gt h ea b i l i t y t ol f e c o g n i z ct h ec h i n e s eo r g a n i z a t i o nn a m e ，s oi tc a ni m p r o v et h ec o r r e c t n e s so f s e g m e n t a t i o na n dl e x i c a la n a l y s i s n ea u t o m a t i cr e c o g n i t i o nm e t h o do fc h i n e s eo r g a n i z a t i o nn a n l ew i t ht h ec o m b i n a t i o n o fs v ma n dm a x i m u me n t r o p yi sp r o p o s e d a sf o rt h ew o r d sa p p e a r e di nt h ec h a r a c t e r i s t i c d i c t i o n a r y ，w eu s es v m t od e c i d ew h e t h e ri ti st h ec h a r a c t e r i s t i cw o r do ft h eo r g a n i z a t i o n n a n l e ( h a t t e rb o t m a a r yd e c i s i o n ) w eu t h em e t h o db a s e do ns v m t ot a gf r o mt h ew o r d b e f o r et h ec h a r a c t e r i s t i cw o r d , u n t i le n c o u n t e rn o n - o r g a n i z a t i o nn a m ec o m p o s i t i o n ( t a g g i n g f o r e s i d e ) ，t h e nc o n t i n u et h ep r o c e s sm e n t i o n e db e f o r ei nt h i sp a p e r i no r d e rt oi m p r o v et h ee f f i c i e n c yo ft h el a t t e rb o u n d a r yd e c i s i o n , ad r i v er e c o g n i t i o n m e t h o di sp r o p o s e d , w h i c hd e c i d e st h el a t t e rb o u n d a r yo f t h ew o r d sa p p e a ri nt h et e x t , w h i c h a r ec o l l e c t e di nt h ec h a r a c t e r i s t i cd i c t i o n a r y , t h e nt a gt h ef o r m e rp a r t so ft h eo r g a n i z a t i o n b a r n e t h el a t t e rb o u n d a r yd e c i s i o ni sap r o b l e mo ft w ov a l u ec a t e g o r i z a t i o n , a n ds v mc a i l e f f e c t i v e l ys o l v et h ep r o b l e mo f t h er e c o g n i t i o no f t h ec h a r a c t e r i s t i cw o r do f t h eo r g a n i z a t i o n n a m e d u et ot h ec o m p l e xc o m p o s i t i o no f t h ef o r m e rw o r do f t h eo r g a n i z a t i o nn a r f l e ，m a x i m u m e n t r o p yc o m b i n ed i f f e r e n tk i n d so f t e x ti n f o r m a t i o n , a n ds o l v et h ep r o b l e mo f t h er e c o g n i t i o n o ft h em o r ec o m p l e xf o r m e rw o r d so ft h ec h i n e s eo r g a n i z a t i o nn a m e a c c o r d i n gt ot h e f e a t u r eo f t h ef o r m e rw o r d sa n dt h ea n a l y s i so ft h es t a t i s t i c a lr e s u l t s ，w em a k et h el 慨d n l t m l e n t r o p yf e a t u r em o d u l e ，e s t a b l i s ht h ef e a t u r es e ta n da c c e s st h ep a r a m e t e r s ，e v e n t u a l l yg e tt h e f o r m e rp a r t st a gm o d u l eb a s e do nm a x i m u m e n t r o p y t h er e s u l t ss h o wt h a ts v ma n dm a x i m u me n t r o p yc o m b i n e dc h i n e s eo r g a n i z a t i o n n a l n er e c o g n i t i o ni se f f e c t i v e ：i no p e nt e s t , t h er e c a l la n dp r e c i s i o nr a t ea n df - m e a s u r ea r e 9 1 0 5 ，9 3 5 9 ，a n d9 2 8 4 r e s p e c t i v e l y c o m p a r e dt op r e s e n td o c u m e n to f t h i sk i n d ，t h e r e c o g n i t i o ns y s t e mg e t sb e t t e rr e s u l t s ，f u r t h e r m o r e ，i tc a l la l s or e c o 霉r i z eo t h e rn a m ee n t i t i e s , s u c ha sp e r s o nn s i n e ，p l a c en a m ea n ds oo n 璺竺塑墨奎塑塑丝全箜! 茎垫塑垒皂垫! 型一一 k e yw o r d s ：c h i n e s eo r g a n i z a t i o nn a m e ；d r i v em o d e ；m a x i m u me n t r o p y ；s u p p o r t v e c t o rm a c h i n e ( s v m ) 一i v 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 储躲和碍晚鲨血夕 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名： 塑缓鼋 导师繇童t 磷。， 噍绛4 汐辑日 大连理工大学硕士学位论文 1 绪论 1 1 问题描述 1 1 1 中文机构名自动识别的提出 自然语言是人类进行推理和交流的桥梁【l 】。由于语言在智能活动中具有举足轻重的 作用，当计算机在不同领域逐步代替人完成各项工作时，人们也期待着计算机在自然语 言的处理上能够接近甚至达到人的智能水平。作为人工智能的一个重要分支，自然语言 处理就是用计算机理解和处理自然语言和各种符号，包括机器翻译、信息检索、信息抽 取等等。 汉语作为世界上最主要的语言之一，其独特之处在于其基本构造单位是字而不是 词。尽管在汉语口语中，存在音节上的一定变化，形成了某种程度的词的界限，但却并 没有形成真正的明显的分词( 即将词与词分开) 标志；在书面汉语中，词与词之间则完全 缺乏形态上的切分标志。因此，要将汉语纳入以词法、语法、语义等为基础的按层次分 析的体系中去，就必须首先建立汉语中词的切分规范并将汉语的基本语言单位转化为 词，这就是分词问题；而使用计算机自动进行词的切分，即汉语中的自动分词问题。 由于汉语自动分词在中文信息处理中的重要性，近些年来众多专家学者做了许多研 究工作 2 - 1 1 。这些研究工作都取得了一些成果，但同实际需求相比较，还有很大差距。 汉语自动分词的困难主要有：歧义切分字段处理，未登录词识别。 ( 1 ) 歧义切分字段处理 歧义字段切分在中文文本中是普遍存在的，是影响分词系统切分精度的重要因素。 歧义切分字段从构成形式上分为两类：一是交集型歧义切分字段，也称交集字段；二是 多义组合型歧义切分字段，也称多义组合字段 ( 2 ) 未登录词识别 未登录词包括中外人名、中国地名、机构组织名、事件名、货币名、缩略名、派生 词、各种专业术语以及不断发展和约定俗成的一些新词语，其中中外人名、中国地名、 机构组织名属于专有名词。自动分词是进行自然语言处理的基础，未登录词的识别又是 困扰汉语自动分词的一个难点，而专名是未登录词中很重要的一部分。专名虽然只占汉 语文章的1 2 ，但是，由于在中文里专名没有明显记号，如果不加以特定处理，由 专名引起的切分错误常常占绝大部分，有时甚至可以达到总出错比率的5 0 以上。而且 由于专名被切开，在后续的句法和语法分析中作为分离的单词处理，将对机器翻译和机 器理解自然语言造成很多困难。识别未登录词，现有的解决方案可以分为两种：一揽子 s 和最大熵相结合的中文机构名自动识别 解决方案和个别解决方案。一揽子解决方案就是将人名、地名、机构组织名等各种专 名做一揽子处理，这类方法一般需要对大规模语料进行人工标注，然后从熟语料中进行 学习以获得不同颗粒度的知识。 如上述，在中文文本的自动分词处理中，未登录词是影响自动分词精度提高的主要 原因之一。若在分词阶段未能把人名和地名、机构名等未登录词识别出来，则会对以后 的词法、语法、语义等的分析造成不可逾越的障碍。对于机器翻译而言，分词阶段的错 误率在翻译的过程中将会被“放大”，放大的倍数约等于句子的平均长度，这严重影响 翻译的质量。 识别未登录词，基本专门针对某类特定的专名未登录词进行处理，一般通过构造相 关字表和词表来分别识别类似词和词组的命名实体。发表的关于人名识别的论文有文献 【8 1 2 】、关于地名识别的论文有文献【1 3 - t 6 1 , 关于机构名识别的研究有文献 1 7 2 6 】。此 外，一揽子解决方案中涉及机构名识别的研究有文献【2 7 3 1 】。 中文机构名是未登录词中的一个重要部分，未被正确识别的机构名是造成分词错误 的重要原因。解决中文机构名识别的一个最直观最简单的方法就是穷举法，将所有中文 机构名加入分词词典中，但这种方法存在很多闯题：首先，中文机构名是不断交化的， 随着时间的推移，有很多中文机构名会逐渐消失，新的中文机构名会不断涌现；其次， 这样做会使分词词典的规模急剧增加，增加系统开销，降低运行效率：另外，这种方法 也会使得各种歧义现象出现的概率增加，降低切分正确率。为此，研究中文机构名的自 动识别是很有必要的。 但是，由于中文机构名在汉语文本中出现的特点，实现中文机构名的自动识别有很 大的困难。比如中文机构名数量大，并且没有明确规范的中文机构名定义；中文机构名 是动态变化的；与印欧语言中地名采用大写字母开头不同的是，中文机构名缺乏可以辨 识的启发标记；中文机构名的构成相当随意，用词比较自由、分散，有些词既可以作为 中文机构名的组成部分又可以作为中文机构名的指示词出现在中文机构名的前部或后 部；中文机构名长度没有严格限制，短的如“新华社”，长的如“世界休闲与娱乐协会 研究委员会”。 1 1 2 中文机构名自动识别的意义 中文机构名作为未登录词的一个子集，涉及广泛、种类繁多、形态各异，绝大多 数未收录词典，中文机构名的自动正确识别对后续的句法分析有很重要的意义，这将 为机器翻译和机器理解，以及信息抽取和信息检索奠定良好的基础。 大连理工大学硕士学位论文 中文文本中的机构名没有物理标记( 除缩略语以外) 且数目特别庞大；与人名地名相 比，机构名具有不稳定性，它会随着社会发展，新机构不断涌现，旧机构不断被淘汰、 改组或更名，因而机构名具有一定的时代性。机构名的不规范性，机构的命名有很强的 随意性，越小的机构其名称可能越“奇怪”。机构名用字和用词的随意性和机构名长度 的不确定性，导致机构名的边界很难确定。因此，相对于人名地名来讲，机构名的识别 更加复杂。 自动分词是进行自然语言处理的基础，未登录词的识别又是困扰汉语自动分词的一 个难点，两专名是未登录词中很重要的一部分。由于许多分词系统都是在假设词表完备 的前提下进行分词的，但汉语是一个开放的集合，新词不断涌现，旧词也无法尽收词表。 未登录的专有名词虽然只占汉语文章的1 2 ，但由于专有名词在中文信息处理中没 有明显记号，分词系统在遇到专有名词时，会将其切成“碎片”，甚至导致严重歧义错 误。因而专有名词的识别已成为汉语自动分词的焦点。 就句法分析而言，自动分词是现代汉语句法分析器的一项基础性工作。汉语语言理 解有着极其广泛的应用价值，在人机接口、问答系统、汉外机器翻译等众多的应用领域 中，对输入文本进行句法分析是一项必不可少的处理任务。因为计算机从事句法分析所 凭借的语法知识不外乎来自机器词典和句法规则库。机器词典收录了每个词条的词法、 句法和语义知识，而句法规则一般来讲是在词类等知识基础上构造的。因此，对汉语句 子必须先进行词语切分处理后，才有可能进行句法分析。如果对输入的源文件中每个句 子未经分词处理，仍然是一些字串序列，就无法根据句子中出现的每个具体词到机器词 典中去查找相应的语言知识；而且，如果不知道每个具体词的词性等词汇知识也就不可 能直接调用相应的句法规则来判断句子的句法结构。由于中文中“词”的定义含糊，歧 义切分字段和未登录词辨识困难，造成自动切分困难重重，我们在自然语言处理中首先 要解决自动切词的瓶颈闯题，企图越过这一步是行不通的。 综上所述，中文机构名的自动识别对提高汉语自动分词和句法分析的精确率都有很 重要的意义。 1 2 中文机构名自动识别研究现状 国内学者在9 0 年代开始对中文机构名的识别进行研究。同自然语言处理的其它分 支类似，中文机构名自动识别处理技术分为三种；基于规则的方法、基于统计的方法及 规则与统计相结合的方法。 ( 1 ) 基于规则的方法，最有代表性、也是关于中文机构名的自动识别方面最早的文 章是张小衡等的中文机构名称的识别与分析【m ，从语言学和计算机技术两个角度， s 和最大熵相结合的中文机构名自动识别 对机构名称的语法性质、语义特性以及机构名称的组织规律进行了研究和分析，总结了 很多有益于机构名称识别的规则。根据这些规则，建立了一个对高校名称进行识别的模 型。 ( 2 ) 基于统计的方法，郑家恒等的中国组织机构名自动识别系统的设计与实现 ”s 】利用隐马尔可夫模型并结合概率估值公式来评价在真实文本中构成组织机构名的能 力，实现了中国组织机构名的自动识别系统。俞鸿魁等的基于角色标注的中文机构名 识别【1 9 l 根据在机构名识别中的作用，采取v i t e r b i 算法对切分结果进行角色标注，在 角色序列的基础上，进行字符串识别，最终实现中文机构名的识别。冯冲等的采用主 动学习策略的组织机构名识别闭认为组织机构名等命名实体的识别是信息抽取、机器 翻译等任务的重要基础。为了克服识别器训练过程中对标注数据的依赖，本文提出了一 种基于主动学习的训练策略，改进了基本的最大熵模型的解码算法和训练过程。实验表 明采用主动学习策略的最大熵模型训练算法能够有效减少标注数据的使用。周俊生等的 基于层叠条件随机场模型的中文机构名自动识别【2 1 】提出了一种新的基于层叠条件随 机场模型的中文机构名自动识别算法。该算法在低层条件随机场模型中解决对人名，地 名等简单命名实体的识别，将识别结果传递到高层模型，为高层的机构名条件随机场模 型实现对复杂机构名的识别提供决策支持。 ( 3 ) 规则与统计相结合的方法，c h e r tkj 等的k n o w l e d g ee x t r a c t i o nf o ri d e n t i f i c a t i o n o f c h i n e s e o r g a n i z a t i o n n a m e s ) ) 吲该文利用了机构名称结构属性和统计属性以及机构名 称的局部语言知识化进行识别并进行信息抽取。吴雪军等的 c ot r a i n i n g 的机器学习 方法在中文机构名识别中的应用t 2 3 1 采用c o 的机器学习的方法构造机构名识_training 别知识库。宇缨等的一种基于s v m r s 的中文机构名称自动识别方法肼】提出一种 支持向量机和粗糙集( r o u g hs e t , r s ) 相结合的中文机构名称短语识别方法。该方法借助 词的基本语义搭配关系表示短语的构成规则，并通过粗糙集属性约简的方法自动学习到 机构名称构成规则的无冗余集。识别时，首先寻找到与这些规则匹配的词串作为候选机 构名，然后结合候选机构名以及其上下文词的语义特征，利用s v m 分类器判断该候选 是否是真正的机构名称。还有本实验室张艳丽等的统计和规则相结合的中文机构名称 识别瞄】根据机构名的特点，利用统计方法建立了机构名识别所需的特征词词典与前部 词词典等系统词典，并通过对汉语语法知识以及实际语料的分析，对机构名前部词进行 了分类和研究，总结了有效的规则，对机构名进行识别，取得了较好的效果。 另外，还有学者将多种未登录词采用一体化的识别方法。g o hcl 等的( c h i n e s e u n k n o w nw o r di d e n t i f i c a t i o nu s i n gc h a r a c t e r b a s e dt a g g i n ga n dc h u n k i n g ) ) 2 7 利用形态素 解析获得初始分词结果和位置标记，然后将低频词作为可能的未登录词，将分词结果再 一4 一 大连理工大学硕士学位论文 分解成单字分别赋予属性值，利用基于s v m 的c h u n k e r 抽取未登录词。其中对于机构 名的抽取主要依靠的是中心词。c h i e uhl 等的( n a m e de n t i t yr e c o g n i t i o nw i t ha m a x i m u m e n t r o p y a p p r o a g h 【2 司是利用最大熵来识别命名实体的，不仅利用命名实体在 一个句子中的局部上下文信息，而且利用在同一篇文档中每个出现的单词。这些全局的 特征提高了识别效果。但本试验只给出了针对英文和德文的机构名识别结果。陈小荷的 自动分词中未登录词问题的一揽子解决方案1 2 9 j 分析了现有的解决未登录词问题的各 种方案，提出两趟分词、在“分词碎片”中计算单字成词概率和未登录词概率的一揽子 解决方案，并报告一个初步的、令人鼓舞的开放测试结果。吕雅娟等的基于分解与动 态规划策略的汉语未登录词识别 3 0 1 采用分解处理策略将未登录词的识别分为预处理， 二、三字未登录词识别，多字未登录词识别等层次，降低了整体的处理难度。同时将自 身可信度与上下文认可度集成到评价函数中，实现了统计数据与规则的综合比较。对于 多字未登录词的识别，使用动态规划方法实现了最佳路径的搜索，较好地解决了未登录 词之间的冲突问题。后面两种方法并没有对机构名进行专门的处理，但其中的思想值得 借鉴。 前人的研究已经取得了较好的效果，但目前还存在一些问题： ( 1 ) 基于规则的识别模型，很大程度上依赖于规则库的完备性和准确性，由于目前 很难使规则库达到完备，而且当规则总数达到一定的极限时，规则间不可避免地会产生 碰撞问题，即是所谓的获取知识的“瓶颈”问题，所以识别效果并不理想。基于传统规 则存在许多潜在危机，单纯的规则模型已经不常用。 ( 2 ) 有些文献使用一些先进统计模型取得很好的识别效果，但是采取全标注策略， 计算效率偏低。还有些文献使用的统计模型，尽管效率很高，但是统计模型借助信息能 力有限，难以解决复杂问题。对于复杂问题应该在计算效率和识别效果之间获得平衡， 对于实际应用来说，单纯地强调计算效率或者识别效果，意义都不是很大，应该综合考 虑这两个方面的要求。 1 3 本文的工作 1 3 1 相关概念 为了理解上的需要，先对本文要用到的相关概念进行定义： 定义1 1 ：机构名是指机关团体或其他企事业单位。就其范围来说，包括学校、公 司、研究院所和政府机关等。 定义1 2 ：机构名特征词指的是机构名末尾具有一定表征意义的词，一般来说是普 通名词。最常见的机构名特征词如：“厂、大学、法院、公司、银行、医院”等。 s v m 和最大熵相结合的中文机构名自动识别 定义1 3 ：机构名前部词是指机构名中机构名特征词之外的词。前部词可以指明一 所大学是大连理工大学，大连海事大学，还是大连医科大学，其中的“大连、理工、 海事、医科”均是前部词。 定义1 4 ：特征词是指可以作为机构名特征词的候选词。如“北京小学”中的“小 学”只是个特征词还不是机构名特征词。 定义1 5 ：机构名后界词就是指机构名中的尾部词，实际就是机构名特征词。 定义1 6 ：机构名前界词就是整个机构名前面那个词，就是机构名前部词之前的词。 定义1 7 ：后界判断是指识别出机构名特征词的过程，实际就是确定机构名后界词。 定义1 8 ：前部标注是指在机构名特征词识别出来后，从机构名特征词向前对机构 名前部词标注，直到标注到非机构名为止的过程，实际就是确定机构名前界词。 1 3 2 具体工作 由于机构名特征词是中文机构名唯一有固定信息可以利用的部分，而机构名前部词 组成又比较复杂，因此将机构名后界词识别和机构名前界词识别分为两部分单独处理。 机构名后界词识别是二值分类问题，由于s v m 是一种优秀的二值分类器，引入s v m 来解决。机构名前部词组成比较复杂，由于最大熵可以融进较多信息和扩充信息的层次 和距离。对复杂问题的解决有较好的效果，同时最大熵以较好的效率解决多类分类问题， 对于机构名前界词识别引入最大熵来解决。因此，本文将s v m 和最大熵相结合来尝试 解决中文机构名识别问题。 本文处理范围限定在以机构名特征词为机构名尾部的完整机构名，对于其他机构名 不在本文处理范围。文中所提机构名均指中文机构名。 本文识别过程是对文本中出现在特征词典的词进行后界判断，识别出该词是否是机 构名特征词，对识别出的机构名特征词开始前部标注，直到标注到非机构名成分停止标 注，然后继续在文本中查找被收录在特征词典的词，进行后界判断，前部标注。后界判 断使用s v m ，前部标注使用最大熵模型。 本文具体来说做了如下几点工作： ( 1 ) 建立中文机构名识别所需要的词典和标注训练语料。通过已经标注好的语料， 建立特征词词典。对经过分词、词性标注后的训练文本，手工标注本文定义机构名成分 标记。 ( 2 ) 由于机构名在文本出现频率不是很大，同时机构名特征词在一定范围内，为了 提高效率，提出驱动式识别方法。所谓驱动式识别方法就是在后界判断时，对文本中出 现的收录在特征词典的词进行后界判断，识别出该词是否是机构名特征词，从识别出的 大连理工大学硕士学位论文 机构名特征词开始向前前部标注。 ( 3 ) 后界判断问题是二值分类问题，而s v m 是一种优秀的二值分类器，因此基于 s v m 的后界判断模型可以有效的解决机构名特征词识别问题。根据机构名特征词的统 计分析和语法特征，构建s v m 向量，通过学习，获取后界判断模型。 ( 4 ) 机构名前部词组成比较复杂，由于最大熵可以融进较多信息和扩充信息的层次 和距离，对复杂问题的解决有较好的效果，同时最大熵以较好的效率解决多类分类问题， 因此基于最大熵的前部标注模型可以有效解决比较复杂的中文机构名前部词识别问题。 根据机构名前部词的特征和统计分析结果，构建最大熵特征模板，构建特征集并进行参 数训练可以获得前部标注模型。 s w 和最大熵相结合的中文机构名自动识别 2 $ v m 近年来，支持向量机( s u p p o r tv e c t o rm a c h i n e s ，s v m ) 的研究在广泛开展。支持向 量机是v v i p n i k 等根据统计学习理论( s t a t i s t i c a l l e a r n i n g t h e o r y ，s l t ) 提出的一种新的 机器学习方法，在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势， 已经在模式识别、函数逼近和概率密度估计等方面取得了良好的效果。支持向量机从本 质上讲是一种前向神经网络，根据结构风险最小化准则，在使训练样本分类误差极小化 的前提下，尽量提高分类器的泛化推广能力从实施的角度，训练支持向量机的核心思 想等价于求解一个线性约束的二次规划问题，从而构造一个超平面作为决策平面，使得 特征空间中两类模式之间的距离最大，而且它能保证得到的解为全局最优解。 支持向量机实质上是一种基于统计学习理论和线性分类思想的学习方法，其中支持 向量是对分类有较好区分能力的样本点，这些支持向量可以构造出空隙最大的最优分类 超平面。 通过核函数变换的方法，支持向量机可将在低维空间无法线性分类的样本映射到高 维空间进行分类，很好得解决了有限数量样本的高维模型构造问题。支持向量机优于已 有机器学习方法一个重要方面是高维处理能力，即s v m 的学习误差不依赖于特性空间 的维数，不会出现其它机器学习方法的“过学习”现象。 应用s v m 解决自然语言处理中的文本分类、词性标注、短语识别 3 2 - 3 5 1 等问题，取 得令人满意的结果。 2 1s v m 原理 2 1 1 线性s 首先我们将探讨一下线性超平面，它是一个基于超平面的分类器。假如我们有个 训练数据点 ( 置，y ，) ，( x ：，y 2 ) ，( x 。，y 。) ) ，其中x 。e r 4 并且y ， 1 。利用这些数据， 通过学习机器，我们将训练出个超平面分类器： ，( x ) = s g n ( w x 6 ) 而且我们将保证所得到的超平面到正负两类之间的空间间隔距离最大。通过学习机的训 练，我们还将得到平行于超平面h 。：y = - x b = 0 的两个超平面，而且这两个超平面 到h 。的距离相等。这两个超平面的表达式分别为：h ：y = x b = 1 ， h ，：y = w x b 1 ，如图2 1 所示。 一8 一 大连理工大学硕士学位论文 图2 1 最优分类超平面 f i g 2 1 伽叩i i n l i 捌h y p e r p l a n o 0 特别是在保证这两个超平面之间不存在任何数据的情况下，h ，和h ：之间的距离必 须达到最大化。对于任意分割平面h 以及和它相对应的h ，和h ：我们都能找到一个向量 系数，使得h 和h ，分别为： y = w x - b = “ y = ”x - b = 一l 由于我们要最大化这两个平面之间的距离，在h 。超平面上面存在一些正例数据，而在 h ，超平面上面存放着一些负例数据，这些数据我们就称它们为支持向量，只有这些数 据才对我们最后的模型真正产生作用，其余不是存放在这两个超平面上的训练数据都可 以从我们的训练模型中剔除。 回顾在二维平面中，点到直线出+ 缈+ c = 0 之间的距离计算公式为： l 向+ 觋嘲 鬲 同理，h 上某点到超平面h 的距离为： 1 2 俪 并且从超平砷倒h ：的距离为南因此为了使这两个平面间的距离最大，必须保证 在h 。和h ：之间没有数据存在的情况下使得m f = w 1 w i d 、。在此可以把式子： ，x 一6 2 + 1 ( y j = + 1 ) ，x - b 一1 ( 只= - 1 ) 合并成一个式子为： 一9 一 眢 s 和最大熵相结合的中文机构名自动识别 y i ( ，工一6 ) 1( 2 1 ) 容易验证，最优超平面就是满足条件式( 2 1 ) 并且使得 o ( w ) = 2 2 1 2 构造s 构造s v m 就是要构造最优超平面，我们必须用系数的模最小的超平面把属于两个 不同类y - 1 ，1 ) 的样本集( 而，y ) ，( 工，y ，) 中的向量而分开。 要找到这个超平面，我们需要求解下面的二次规划问题：最小化泛函 m ( ”) = 圭( ” 约束条件为不等式： y i 【 。p ) 一6 】l ，i = 1 , 2 ，3 ，z( 2 2 ) 这个优化问题的解是由下面的拉格朗日泛函( 拉格朗日函数) 的鞍点给出的： 工( w ，6 ，口) = 去( ，) 一口。 【( 而w ) - b y , 一l 其中口，为拉格朗日乘子。我们需要把对拉格朗日函数关于，b 求其最小值和关于 0 求其最大值。 在鞍点上，求，6 0 和必须满足以下条件； a l ( w o , b o , a 。) ：o a 6 o l ( w o , b o , a 。) ：0 a ， 以显式重写这些方程，我们得到最优超平面的下列特性： ( 1 ) 对最优超平面，系数口? 必须满足约束 口? 乃= o ，口? o ，i - - 1 ，z ( 2 ) 最优超平面( 向量，。) 是训练集中的向量的线性组合： w 。= y 。口? 茸，口? o ，f = l ，z 1 - 1 ( 3 ) 进一步，只有所谓的支持向量可以在的展开中具有非零的系数口? 。支持向 量就是使得不等式( 2 2 ) 中的不等式成立的向量。因此我们得到 大连理工大学硕士学位论文 w o = y ，c r ? 工，口? 0 ( 2 _ 3 ) 支持向量 这一点是从传统的k u h n - t u c k e r 条件得到的。根据k t t h n - t u e k e r 条件可知，最优超平面 的充分必要条件是分类超平面满足条件： 口? ( 【( x l o ) - b o y l - 1 = o ，f = 1 ，f 把的表达式代入拉格朗日函数中，并考虑到k u l m - t u e k e r 条件，我们得到下面的泛函： ，1， 。 矿( a ) = 钙一寺q 吩乃乃( 而，x j ) ( 2 4 ) 1 - 1 ou - 1 问题变为在非负象限吼o ，待l ，f 中最大化这一泛函，并服从约束条件： ， y i = o ( 2 5 ) 1 = 1 根据式( 2 3 ) ，拉格朗日乘子和支持向量决定了最优超平面，因此要构造最优超平面，我 们需要解决的是一个简单的二次规划问题：在约束条件口，2 0 ，( f = 1 ，z ) 和式( 2 5 ) 下最 大化式( 2 4 ) 的二次型。， 设口。= ( q o 口2 0 ，仃? ) 为这个二次规划问题的解，那么与最优超平面对应的向量w 。 的模等于； 0 w o l l 2 = 2 w ( a 。) = 口纠o ( 而x j ) y , y j 支持向量 基于最优超平面的分类规则就是下面的指示函数： f ( x ) = s g n ( m a ? ( 为x ) - b o ) 支持向量 其中一是支持向量，群是对应的拉格朗日乘子，6 0 是常数， b o = 去【( p o x ( 1 ) ) + ( ，o 膏( 一1 ) ) 】 上 其中，我们用x ( 1 ) 表示属于第一类的某个( 任意一个) 支持向量，用x ( 一1 ) 表述属于第二 类的一个支持向量( v a p i n k a n d c h e r v o n c n k i s ，1 9 7 4 及v a p n i k ，1 9 7 9 ) 。 2 1 3 非线性$ v m 对于非线性划分问题，可以通过一个非线性变换予：r n h 将它转化为某个高维空 间h 中的线性划分问题。一般来说，这种非线性变换的形式可能非常复杂，难于实现。 但是注意到在上面的问题中，不论是优化的目标函数式( 2 4 ) 还是分类函数式( 2 5 ) 都只涉 及到向量的点积运算，即：毋( t ) 咖o ，) 的形势如果存在一个核函数k ，满足： s 和最大熵相结合的中文机构名自动识别 k ( x j ，x f ) = 驴( 毛) 圣( x ，) ( 2 6 ) 那么就能用原空间中的函数来实现变换空间中的点积，从而绕开映射垂的具体形式。 根据泛函分析中的有关理论，只要核函数k ( x ，力满足m e r c e r 条件，它就对应于某 变换空间中的点积，也就是说，存在映射烈工) 使得式( 2 6 ) 成立。此时的分类函数为； 卫 f ( x ) = s 弘( c t l y i k ( x f ，曲+ a 1 = 1 2 1 4 支持向量机 如果用内积足( x ，x ) 代替最优分类面中的点积，就相当于把原特征空间交换到了 某一新的特征空间，此时优化函数变为： w ( a ) = q 一去嘶q 乃乃( 而x j ) t = l t , l 相应的判别函数也应变为： 卫 厂( x ) = s g n ( 甜。y i k ( x s ，曲+ 6 ) l - i 算法的其他条件均不变，这就是支持向量机。 ， 支持向量机的基本思想可以概括为：首先通过非线性变换将输入空闯变换到一个高 维空间，然后在这个新空间中求取最优线性分类面，而这种非线性变换是通过定义适当 的内积函数实现的。 常用的核函数有以下几种： ( 1 ) 线性内积函数k c x ，力可j ，； c 2 ) 多项式内积函数k ( x ，j ，产【 们+ j 】函 ( 3 ) 径向基内积函数k ( x ，y ) = e x p 一i x - y 1 2 a 2 ； ( 4 ) 二层神经网络内积函数r ( x ，力= t a n h ( 麒x 力+ c ) a 2 2s v m 学习算法 s v m 方法的训练运算速度是限制它的应用的主要方面，近年来人们针对方法本身 的特点提出了许多算法来解决对偶寻优问题。大多数算法的一个共同的思想就是循环迭 代：将原问题分解成为若干子问题，按照某种迭代策略，通过反复求解子问题，最终使 结果收敛到原问题的最优解。根据子问题的划分和迭代策略的不同，又可以大致分为两 类。 大连理工大学硕士学位论文 第一类是所谓的。块算法”。“块算法”基于的是这样一个事实，即去掉l a g r a n g e 乘子等于零的训练样本不会影响原问题的解。对于给定的训练样本集，如果其中的支持 向量是己知的，寻优算法就可以排除非支持向量，只需对支持向量计算权值( 即l a g r a n g e 乘子) 即可。实际上支持向量是未知的，因此“块算法”的目标就是通过某种迭代方式 逐步排除非支持向量。具体的做法是，选择一部分样本构成工作样本集进行训练，剔除 其中的非支持向量，并用训练结果对剩余样本进行检验，将不符合训练结果( 一般是指 违反k k t 条件) 的样本( 或其中的一部分) 与本次结果的支持向量合并成为一个新的工作 样本集，然后重新训练。如此重复下去直到获得最优结果。当支持向量的数目远远小于 训练样本数目时，“块算法”显然能够大大提高运算速度。然而，如果支持向量的数日 本身就比较多，随着算法迭代次数的增多，工作样本集也会越来越大，算法依旧会变得 十分复杂。 因此第二类方法把问题分解成为固定样本数的子问题：工作样本集的大小固定在算 法速度可以容忍的限度内，迭代过程中只是将剩余样本中部分“情况最糟的样本”与工 作样本集中的样本进行等量交换，即使支持向量的个数超过工作样本集的大小，也不改 变工作样本集的规模，而只对支持向量中的一部分进行优化。固定工作样本集的方法和 块算法的主要区别在于：块算法的目标函数中仅包含当前工作样本集中的样本，而固定 工作样本集方法虽然优化变量仅包含工作样本，其目标函数却包含整个训练样本集，即 工作样本集之外的样本的l a g r a n g e 乘子固定为前