（计算机软件与理论专业论文）日语依存关系解析的研究.pdf

人近理l ：人学硕十学位论文 摘要 句法分析是自然语言处理的基本技术，包括短语结构解析和依存关系解析两种句法 分析方法。依存关系可以明确地表明词之间的句法依存关系，并方便地转化为语意依存 描述，近年来得到广泛重视，在机器翻译、信息检索、自动文摘等领域有着直接的应用。 日语依存关系解析是基于日语依存文法来确定句子中文节与文节之间的依存关系。 基于支持向量机( s u p p o r tv e c t o rm a c h i n e ，s v m ) 的组块逐步应用算法是一种比较成功的 日语依存关系解析算法，依存关系精确率达到8 8 6 6 。这种方法存在两个问题，一个 是使用s v m 模型进行分类时，分类超平面附近的向量分类正确率较低；另一个问题是， 日语长句的依存关系解析精度较低。 针对这两个问题，本文提出了四种方法进行改进。 ( 1 ) 基于支持向量机与k 邻近算法( kn e a r e s tn e i g h b o r , k n n ) 相结合的日语依存关 系解析，首先使用s v m 模型对向量进行分类，对位于分类超平面附近的向量，使用k n n 算法进行修正。 ( 2 ) 基于支持向量机与条件随机场( c o n d i t i o n a lr a n d o mf i e l d ，c r f ) 相结合的日语依 存关系解析，当判断两个文节间是否存在依存关系时，综合考虑s v m 和c r f 两个模型 的判断结果，利用中间参数比较两种结果的可信度，将其中可信度较高的模型的判断结 果作为最终结果。 ( 3 ) 针对长旬中依存关系复杂，解析精确率低的问题，本文提出了基于并列关系树 的解析算法，依据并列关系将日语句子划分为层次结构，由里向外依次解析各层的依存 关系，每次的解析过程都相当于是对短句的依存关系解析。 ( 4 ) 距离模糊支持向量机( d i s t a n c ef u z z ys u p p o r tv e c t o rm a c h i n e ，d f s v m ) 是对模糊 支持向量机( f u z z ys u p p o r tv e c t o rm a c h i n e f s v m ) 的改进。d f s v m 重新定义了隶属度， 将训练样本距离其正确分类超平面的距离转化为隶属度，能较好的反应训练样本对于分 类的贡献程度，从而改进了分类精度。 s v m 与k n n 结合方法、s v m 与c r f 结合方法解决了s v m 分类超平面附近向量 分类精度较低的问题。基于并列关系树的日语依存解析算法，解决了日语长句依存关系 解析精确率较低的问题。d f s v m 模型对f s v m 进行了改进，给出了新的隶属度定义。 实验采用同本京都大学语料库，几种方法均比传统s v m 算法更具优越性，达到了 较高的精确率。基于d f s v m 模型解析算法的解析效果最好，精确率为8 9 8 7 。 关键词：日语依存关系解析；s v m k n n 相结合；s v m c r f 相结合；并列关系树；d f s v m 人迮理l ：人学硕十学位论文 r e s e a c hi nj a p a n e s ed e p e n d e n c ya n a l y s i s a b s t r a c t s y n t a xp a r s i n gi s ab a s i ct e c h n i q u eo fn a t u r a ll a n g u a g ep r o c e s s i n g ，i n c l u d i n gt w o m e t h o d s ，o n eo fw h i c hi sp h r a s eb a s e da n dt h eo t h e ri sd e p e n d e n c yb a s e d d e p e n d e n c y r e l a t i o n sp r e s e n tr e l a t i o n sb e t w e e nw r o r d s a n da r ee a s yt ob ec o n v e r t e di n t os e m a n t i c d e p e n d e n c y d e p e n d e n c ya n a l y s i si sw i d e l yu s e di nm a c h i n et r a n s l a t i o n ，i n f o r m a t i o nr e t r i e v a l a n da u t o m a t i ca b s t r a c t j a p a n e s ed e p e n d e n c ya n a l y s i si st od e t e r m i n ea no p t i m a lc o m b i n a t i o no fd e p e n d e n c i e s b a s e do nd e p e n d e n c yc o n s t r a i n t s t h ec a s c a d e dc h u n k i n gm o d e l ，w h i c hi sb a s e do ns v m m o d e l ，c a nr e a c hh i g ha c c u r a c yi nj a p a n e s ed e p e n d e n c ya n a l y s i s n ed e p e n d e n c ya c c u r a c y r e a c h e s8 8 6 6 b u tt h e r ea r et w ol i m i t a t i o n st ot h i sm e t h o d f i r s t ，t h ev e c t o rn e a rt h e h y p e r p l a n ei sh a r dt ob ec l a s s i f i e dw h e nt h es v m m o d e li sa p p l i e d s e c o n d l y ，l o n gs e n t e n c e a n a l y s i sc a l ln o tb ef u l f i l l e dw i t hh i g ha c c u r a c y t os o l v e t h e s ep r o b l e m s ，f o u rm e t h o d sa r eg e n e r a t e di nt h i sp a p e ra sf o l l o w ： i nt h es v m 1 洲m e t h o d w ec l a s s i f yt h ev e c t o rw i t ht h es v mm o d e lf i r s t t h e nw eu s e t h ek n nm e t h o dt od e c i d et h ec l a s so ft h ev e c t o rn e a rt h eh y p e r p l a n e t h ec r fm o d e li si n t r o d u c e dt oa n a l y s ej a p a n e s ed e p e n d e n c ya sc o m b i n e dw i t ht h e t h e s v mm o d e l t od e c i d ew h e t h e rt w oc h u n k sh a v ed e p e n d e n c yr e l a t i o n s ，w ec o n s i d e rb o t ht h e s v ma n dc r fr e s u l t s w ec o m p a r et h eo u t p u to ft h et w om o d e l s ，a n da d o p tt h eh i g h e r b e l i e v a b l et a g t os o l v et h ep r o b l e mi nl o n gs e n t e n c ea n a l y s i s ，w ep r e s e n taj a p a n e s ep a r a l l e la n a l y s i s m e t h o db a s e do np a r a l l e ls t r u c t u r e s t h ep a r a l l e lr e l a t i o n sc a nd i v i d eal o n gs e n t e n c ei n t o s e v e r a ls u b s e n t e n c e st or e d u c et h ea n a l y s i sc o m p l e x i t y w ea n a l y s et h ed e p e n d e n c yr e l a t i o n s i nt h es u b s e n t e n c e sw i t h i np a r a l l e lr e l a t i o n sf i r s t , t h e no u to ft h e m 硼1 l l s ，w es e p a r a t et h e l o n gs e n t e n c ea n a l y s i si n t os h o r ts u b s e n t e n c e sa n a l y s i st oa c h i e v eh i g h e ra c c u r a c y w ei m p r o v et h ef u z z ys u p p o r tv e c t o rm a c h i n e ( f s v m ) t ot h ed f s v mw i t han e w m e t h o dt oc a l c u l a t ef u z z ym e m b e r s h i p w et r a n s f e rt h ed i s t a n c ef r o mt h et r a i n i n gv e c t o rt o t h eh y p e r p l a n ei n t o f u z z ym e m b e r s h i p i t i s e a s y t os h o wt h ec o n t r i b u t i o no ft h e c o r r e s p o n d i n gt r a i n i n gv e c t o rt ot h ec l a s s i f i c a t i o np r o b l e m t h em o d i f i e ds v m k n nm e t h o da n dt h es v m c r fm o d e lh a v ed e c r e a s e dt h eh a r d s h i p i nc l a s s i f y i n gt h ev e c t o rn e a rt h eh y p e r p l a n e t h ep a r a l l e ls t r u c t u r et r e e - b a s e dm e t h o dd i v i d e s t h el o n gs e n t e n c ei n t os e v e r a ls h o r ts u b s e n t e n c e s ，a n da n a l y s e st h ed e p e n d e n c yr e l a t i o n s 日语依存关系解析的研究 l a y e rb yl a y e r t h ed f s v mm o d e li m p r o v e st h ef s v mm o d e lw i t hn e wd e f i n i t i o no ft h e f u z z ym e m b e r s h i p e x p e r i m e n t su s i n gt h ek y o t ou n i v e r s i t yc o r p u ss h o wt h a tt h ep r o p o s e dm e t h o d sc a n i m p r o v et h ea c c u r a c yo fd e p e n d e n c ya n a l y s i sa n dt h ed f s v mm o d e lr e a c h e st h eh i g h e s t a c c u r a c y t h ed e p e n d e n c ya c c u r a c yr e a c h e s8 9 8 7 k e yw o r d s ：j a p a n e s ed e p e n d e n c ya n a l y s i s ：m o d i f i e ds v m - k n n m e t h o d ；p a r a l l e ls t r u c t u r e t r e e ：d f s v m i v 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地3 - ； b ， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 学位论文题目：望童丝銎堑驾警孟堑鲻 作者签名： j 曩塾日期：j 塑丘年f 月j 2 日 人迮理l ：人学硕十研究生学何论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目r ，! 盈透鱼亟幽堑鲫 作者签名： j 塑日期：j 吐年_ l 月二_ 日 导师签名：乏盏忍幺幺邕 日期：二吐年_ l 月日 j ( 连理上人学硕士学位论文 1绪论 1 1研究背景及意义 1 1 1 日语句法分析 句法分析的主要任务是：给定一个句r 了，以语言的语法特征为主要知识源，生成一 棵短语句法树，通过树的形式指明句了各部分之间的关系。其实质是消除歧义的过程。 句法分析在自然语言处理领域的五个研究层次f lj 语音论、词法论、构文论、语义论、 语用论中属于语义解析模型，在词法分析( 分词) 部分的上一层。所以，句法分析是日语 自然语言理解研究的基础工程之一，是对给定句子和文章进行语义分析的前提。句法分 析方法大体上分基于规则的方法和基于统计的方法【2 - 3 1 。 构文论主要研究乔姆斯基提出的生成文法，包括如何合并单词或文节、如何形成插 入因了、如何确定插入因了间的修饰关系等理论。句法分析是与“生成”相反，对已知句 了( 己进行了分词，明确了单词切分和词件) 进行到底是采用了哪些规则生成的判断过 程。研究清楚这个问题就可以知道句了的“构造模式”。这部分的主要任务就是消除歧义。 由日语语言的特点1 4 母j 来看，日语这样的语言不能使用严格的句予构造规则。而丰 富的附属词以及由附属词提供的句法和语义信息来看，在日语句法分析巾，采用依存关 系分析方法是比较适合的1 1 0 】。 日语句法分析中的必要要素有：依存条件、修饰关系类型、优先条件、基本优先度 等。 ( 1 ) 依存条件：由一对存在依存关系的义节构成。 ( 2 ) 修饰关系类型：构成依存关系的类型。 ( 3 ) 优先条件：近接优先或远接优先。 ( 4 ) 基本优先度：对于可匹配的各对文节，分配优先度。 日文的句法分析就是着重分析这利一文节和文节之间的依存关系和优先度。 日语语言分析中，分词方面的研究成果已经达到了9 8 以上的精度。而作为自然语 言处理的两个核心问题之一的句法分析研究相对还没有成熟。 日语采用主、宾、谓结构，和汉语的主、谓、宾结构不同。而且，日语的语序比较 自由，长句子比较多，这就给口语句法分析的研究带来了难度。尤其是长句子的句法分 析，歧义数量比较多，句型比较复杂，是句法分析的难点之一。 1 1 2 日语依存关系解析的意义 对口语的机器翻译要要经过图1 1 几个步骤： 日语依存关系解析的研究 分词 上 l 句法分析 上 i 译文生成 图1 ，1 日语机器翻详的过程 f i g 1 1 p r o c e s so fm a c h i n et r a n s l a t i o nf o rj a p a n e s e 依存关系解析是句法分析的重要组成部分。日语依存关系的解析是日语自然语言处 理的一个子领域，它是句法分析层面上的研究，是句法层面上的浅层分析。 目前，日语机器翻译的三个主要步骤中，分词已经取得了9 8 以上的精度，而句法 分析研究相对还没有成熟。由此句法分析已经成为提高机器翻译精度的关键，是日语机 器翻译r f l 的瓶颈。所谓的句法分析是在分词的基础上，分析句_ 了的语法结构，生成语法 树。 日语依存关系解析以分词和分文节为基础，分析文节之间的依存关系，为进一步的 语法树的生成做准备。如果依存关系的解析能够取得一个很好的精度，那么对于语法树 的生成，对于译文的选择，以及以后句子层面的分析都有很大的帮助。 1 1 3 日语依存关系的特点 依存关系解析是句法分析的重要方法。依存关系可以明确地表明中心词之间的句法 依存关系，并能方便地转化为语义依存描述。1 9 7 0 年美国计算语言学家r o b i n s o nj 在一 篇题为依存结构和转换规则的论文巾，提出了依存关系的四条公理，这为依存语法 的形式化描述及在计算语言学中的应用奠定了基础，这四条公理是： ( 1 ) 一个句子只有一个成分是独立的。 ( 2 ) 其他成分直接依存于某一成分。 ( 3 ) 任何一个成分都不能依存于两个或两个以上的成分。 ( 4 ) 如果a 成分直接依存于b 成分，而c 成分在句了巾位于彳和8 之间，那么c 或者直接依存于彳，或者直接依存予b ，或者直接依存于a 和b 之间的某一成分。 日语依存关系具自和汉语以及其他自然语言不同的特点。 首先，日语的依存关系必须满足下面三条依存公理： 人造理l ：人学硕+ 学侮论文 ( 1 ) 每一个文节( 除了文术的那个文节) 都一定存在而且只存在一个依存对象。 ( 2 ) 依存方向永远向后，即一个文节的依存对象只能出现在它的后方。 ( 3 ) 依存关系不能交叉，即不存在图1 2 所示的情况： 图1 2 交叉的依存关系 f i g 1 2 c r o s s e dd e p e n d e n c ya n a l y s i s 这三条依存公理是每组依存关系都必须遵守的原则。 其次，日语的依存关系还具有其他一般性的特点： ( 1 ) 日语是一种很紧凑的语言，因此，有很多的依存关系发生在相邻的文节之间，大部 分的依存关系跨越的范围都不是很大。 ( 2 ) 由于日语是靠助词和助动词来确定单词在句中的地位和语法机能的，因而，助词和 助动词在依存关系的判定方面具有很重要的作用。 由于日语具有特殊的活用形式，这种活用形式( 如连体形、连用形) 对依存关系的解 析帮助也很大。 1 1 4 日语依存关系的难点 目前在日语依存关系解析中，依然存在着很多的难点： ( 1 ) 在一个日语句子中，一个文节大多存在多个候补的依存对象。如图1 3 所示： f 一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一_ i ： ： i毒 i 工 it ：o ：本意持。i 。、弓 女性窑探l ( 。、否。 图1 3 多个依存候补 f i g 1 3m u l t i p l ed e p e n d e n c yc a n d i d a t e s “二本奁”这个文节有两个依存候补“持o 【，、否”和“探l g ( j ，) ，则x 优 先于z ，。依据s v m s ，得出最大化的问题，如公式( 2 1 4 ) 所示。墨代表一对向量仇1 ，x t 2 ) 。 m ) 8 善。口，一言，；，叩y 刚砷吖，) s 霪印彳1 ，；i 。叩办y ， q 1 4 ( 妒( x ，。) 一妒( j ，2 ) ) ( 妒( ji i ) 一妒( zi 2 ) ) 人迕理i ：人学硕十学伊论文 2 1 6 改进的s v m 模型i m p r o v e ds v m 尽管s v m 已被证实是一种很有效的学习机，研究人员也下了很大功夫提高优化问 题的寻优速度，但对于大规模样本集，特别是在支持向量很多的情形，寻优速度和分类 速度还是不太尽如人意，很显然对于小规模的训练集，训练的速度当然会快得多，大家 都在寻找一种方法能降低大规模训练集的训练规模，同时又不降低分类的j 下确率 文献【2 1 】中，将l s v m 模型【2 2 l 和n n 模型【2 3 l 结合到一起，从简化训练集规模、删除 不好的样本出发，达到提高只语依存关系解析精度，提高解析速度的目的，依存精确率 达到8 9 2 8 。本文称之为改进的i m p r o v e ds v m 模型。 i m p r o v e ds v m 模型具体如下： ( 1 ) 使用基于组块的文节逐步应用算法，在预处理的语料基础上，得到一个训练集 合s 。 ( 2 ) 在s 中随机抽取- d , 部分( 本文实验中抽耿八分之一的样本) 样本，形成一个小 的训练集s j 。 ( 3 ) 使用s v m 对s j 进行训练，得到一个分类器c j 。 h ) 把初始训练集s 中的每一个样本都带入到分类器c j 中，求得每一个样本到c j 超平面的距离d 。设有一阈值亭为0 亭 1 ，如果1 一亭 d 1 + 亭，则保留这个样本，否 则删除这个样本。经过删除后训练集s 缩减为s 。使用s v m 模型对5 训练，得到分类 器c 。用分类器c 做一个丌放性测试，得到解析精度。 ( 5 ) 调整e 的大小，重复( 4 ) 的过程，得到解析精度最高的s 。 ( 6 ) 使用n n 的方法在s 。中再删除一些不好的样本，得到减约集。 ( 7 ) 使用s v m 的训练样本集s ”，得到最后的分类器c “。 ( 8 ) 使用分类器c “进行依存关系解析。 实验证明，使用i m p r o v e ds v m 的方法对训练集进行修剪之后，不仅缩减了训练集 的规模，同时还删除了对分类影响很小、没有影响、甚至是有不好影响的样本，基本上 保留了对分类起决定作用的好的样本。进而，缩短了训练的时间和训练时所需要的内存 数量，提高了解析的精度和解析的速度，使得本文提出的r 语依存关系解析模型具有实 际应用的可能。 2 2 条件随机场 条件随机场( c o n d i t i o n a lr a n d o mf i e l d s c r f ) 1 2 5 l 是最近提 5 的种条件模型，它不 需要h m m 所要求的严格的独立假设，并且也克服了m e m m 和其它r 1 f 乍成_ f 】向图模型。 和m e m m 一样，c r f 是条件概率模型不是有向图模型，而是无向图馍型：c r f 是在 日语依存戈系解忻的研究 给定观测序列的条件下定义的关于整个类别标记的一个单一的联合概率分钿，而不是在 给定当i ，j 状念的条件下，定义下一个状态的状态分布。类别的分布条件属性使得c r f 能够对真实世界的数据建模，这罩标记序列的条件概率取决于观测序列的非独立、相互 作用的特征。 2 2 1 条件随机场的图结构 c r f 是无向图模型的一种形式，在给定将要标记的观测序列的情况下，无向图模型 可以被用来在标记序列上定义一个联合概率分布。假设x ，l ，分别表示需要标记的观察 序列和它对应的标记序列的联合分布随机变量，条件随机场，n 就是一个以观测序列x 为全局条件的无向图模型。 通常，我们定义g = ，e ) 是一个无向图，y = kiv y 。即y 中的每个结点对应 着一个随机变量所表示的标记序列的成分k 。因而，整个图和与图相关的分布类别以x 为条件，所以与g 相关的联合分布的类别的形式是p ( y 。y 。ix ) ，这旱夕和x 分别是类 别序列和观测序列。如果每个随机变量k 满足关于g 的马尔可夫属性，给定x 和k 以 外的所有随机变量k 。i i ，嵋礼，缈) ，则随机变量k 的概率为： 尸( kix ，虼，u 乒l ，) 一p ( kl 石，匕，u 口 ，) ( 2 1 5 ) 其中u 口 ，表示“与y 在图g 中相邻，那么( xn 就是一个条件随机场。 理论上，如果图g 表示了将要建模的标记序列之间的条件依存关系，则它的结构可 以是任意的。但是当用于序列标记任务建模时，所遇到的最简单和最通用的图结构是这 样的：与】，的元素相对应的结点形成了一个简单的一阶链( f i r s t o r d e rc h a i n ) 。我们将这 种条件随机场称为线性链条件随机场( l i n e a r c h a i nc r f ) ，如图2 2 所示： y i iy i y i + i x i ix i x 卜i 幽2 2c r f 的模掣结构 f i g 2 2 t h em o d e ls t r u c t u r eo fal i n e a r c h a i nc r f 人迮理i ：人学硕+ 学位论文 表示l ，的随机变量只是图g 的一部分，这是因为我们希望定义一个概率分御 p ( yix ) 。另外，x 的元素间并不存在任何图结构，这是因为我们只是将观察序列作为 条件，所以并不对x 做任何的独立假设。 2 2 2 条件随机场的势函数表示 c r f 的图结构可以被用来将k 联合分布分解为一个归一化( n o r m a l i z e d ) l 拘势函数的 乘积，势函数来自条件独立的概念，是严格非负的、实数值函数，这里k 是y 的元素。 每一个势函数涉及的g 中的顶点表示随机变量的一个子集。根据无向图模型的条件独立 定义，如果g 中两个顶点之间没有边，则意味着两个顶点表示的随机变量独立于g 中 其它给定的顶点。因而势函数必须保证可以将联合概率分解，以至于条件独立的随机变 量不会出现在相同的势函数中。最容易满足这个要求的方法是保证每一个势函数作用于 随机变量的一个集合上，而这些变量对应的顶点形成了一个最大的全通环( c l i q u e ) 。这 确保了势函数所涉及的任何随机变量对，其顶点是直接联系的，如果两个顶点在一个全 通环( c l i q u e ) 中一起出现，则这种关系就明确表示出来了。在链结构的c r f 下，每一个 势函数作用于相邻的标记变量z 和y ，对。 尽管无向图模型中随机变量的联合分布可写成势函数的乘积，需要指出的是一个孤 立的势函数并没有直接的概率意义，而是表示了定义这个势函数所涉及的随机变量的结 构上的约束而已。这反过来也影响了全局结构的概率一一个概率大的全局结构较概率小 的全局结构更能满足这些约束条件。 在给定观测序列x 的情况下，l a f f e r t y 等定义了标记序列y 的概率是势函数( p o t e n t i a l f u n c t i o n ) 乘积的一个归一化形式，其中每个因子形式如下： e x p ( x a i t j 陬1 ，誓，x ，f ) + 心 ，x ，f ) ) ( 2 1 6 ) 这里f ，( 鼍。，k ，x ，d 是关于整个观测序列和位置f 以及f 标记的特征函数，& 傅，x ，f ) 是 关于位置i 的标记和观测序列的状态特征函数，这里参数a ，和心是特征权重，可从训练 语料中估计得到。 当定义特征函数时，可以构造了观测序列的实数值特征b ( x ，f ) 集合来描述训练数据 的经验分布特征，这些特征与模型具有相同的分布。下面是一个例子： b ( x , i ) ：l 三征位肴! 确翟磐是汉字“书 日语依存关系解析的研究 每个特征函数表示一个实数值的观测特征b ( x ，i ) ，如果当前状态( 状态函数) 或前一 个状态和当前状态( 转移函数) 具有特定的值，则所有的特征函数都是实数值的。例如下 面的转移函数： 假岫f ) z xd 讧2 装p 绷 在后面的描述中，我们用下面的公式来表示状态函数。 & ，x ，i ) - s k 缳，￥，x ，i ) ( 2 1 7 ) 且 e 何，x ) - d ，￥，x ，f ) ( 2 1 8 ) 其中一 中，x ，f ) 是一个状态特征函数，x ，f ) 或者转移特征函数f j 小，x ，f ) 。因 此给定观测序列x - x , ，五，五，置，其对应标记序列l ，- r , ，k ，y ，k 的概率 为： 尸( 1 ，x ，a ) 。三两1e x p ( 军a j ( 1 ，x ) ) 2 1 9 ) z ( x ) 是归一化因子( n o r m a l i z a t i o nf a c t o r ) 。 z ( x ) 。乏e x p ( c ( y ，x ) ) ( 2 2 0 ) 2 2 3 序列标注任务 现在我们用c r f 建立了尸ix ) 的统计模型，求解序列标记任务就是求得l ，满足 p ( r l x ) 最大，z ( x ) 与y 无关，所以 y 霉s r g m 伊xp ( r lx ) 蓦鹕甲乙南钹p ( jt ( y ，x ) ) ( 2 2 1 ) - 鹕垮x 勺够，x ) 使用v i t e r b i 等动态优化方法，即可求出最优解y 。 人近理i ：人学硕十学位论文 建立c r f 模型的主要任务就是从样本数据中估计得到特征权重a 。c r f 参数估计 可以使用最大似然估计( m a x i m u ml i k e l i h o o de s t i m a t i o n ，m l e ) 和贝叶斯估计( b a y e s e s t i m a t i o n ) 。下面主要介绍用最在似然估计估计c r f 的模型参数。 在训练集r = ) 中，最大似然参数估计就是假设p ( 1 ，ix ，a ) 为a 的函数， i 吏p ( ylx ，a ) 的对数值最大的a 为估计值。 厶- 1 0 9 p ( y 七m 钔 。；1 0 9 高唧( 莩九( 矿) ) ( 2 2 2 ) 。；( 莩- c ( y k , x k ) 一l 。g ( z ( x 七) ) 人一a r g m x a x ；l 。g p ( y 七l x 七，a )( 2 2 3 ) 由于l 为凸函数，导数为零点为最值点。故对a 求导，则 鬻。；悸w 七) 啦t ，吣删) 亿2 4 ， 可简写为 导；q e ，；o ( 2 2 5 ) 孤； o一 q 为九在训练集t 中出现的频率，弓。乏( 堆t ) e ( 1 ，x ) 】是在模型分布中的特 征期望。e j 如果直接计算需要很大的计算量，可以使用动态规划的方法求解，如向前一 向后算法( f o 研a r d b a c k w a r d ) 。 如果直接使用最大似然估计，可能会发生过度学习问题，可以通过引入罚函数的方 碍 法解决这一问题。例如使用惩罚项弓7 ，则原问题变为： 巧 l ，= l 一寺+ c 洲f ( 2 2 6 ) 日语依存关系解析的研究 va ； 鲁。鲁一等 亿2 7 ， a 入；8 入：0 2 、 于是a 的参数估计问题可以用最优化方法解决。可以使用g i s 、i i s 等迭代方法，本 文的实现使用l b f g s ( l i m i t e d - m e m o r yb r o y d e n - h e t c h e r - g o l d f a r b - s h a n n o ) 算法。 2 2 5 动态规划方法 对于一个链式结构的c r f ，可以为每个句子添加开始状态标记和结束状态标记来标 记序列，y o 和k + 。分别表示开始标记和结束标记，给定一个观测序列x ，标记序列y 的 概率p ( yix ，a ) 可以使用矩阵进行有效的计算。 设王，是标记的字母表，y 和y ”是来自这个字母表的标记，我们定义了n + 1 个矩阵 的集合 m