（计算机科学与技术专业论文）基于crfs的中文分词算法研究与实现.pdf

? j i l 立。 煅 声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期：坐兰：型 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。 本学位论文不属于保密范围，适用本授权书。 本人签名：垒匿望日期：盘壹：至：! l 导师签名：日期： 乙订o j i1 r，、l-一l r r ，i ，o 究与实现 摘要 中文分词是汉语自然语言处理的基础性任务，分词的准确度直接 影响到后续处理任务，分词的速度影响一些系统的实际应用。 条件随机场( c i 江s ) 是用于序列标记和数据分割以及组块分析 的条件概率模型，是给定输入序列条件下计算输出序列的无向图模 型。它属于“判别 模型，没有“生成 模型的代表隐马尔可夫模型 ( h m m s ) 严格的输出独立性假设，且克服了最大熵马尔可夫模型 ( m e m m s ) 等其它“判别 模型的标记偏置问题。该模型可以非常容易 的将输入序列中的任意特征纳入到模型中。 条件随机场理论与它之前的基于统计方法的模型有着联系。条件 随机场理论有着隐马尔可夫模型面临的三个基本问题，在解决相同问 题时又用到了相似的解决方法。其条件概率模型与最大熵模型的概率 模型的推导原理及参数估计函数的形式相同，且其条件概率模型借鉴 了最大熵马尔可夫模型的概率分布的形式。 本文系统地描述了条件随机场理论。为了更清楚的描述条件随机 场理论，我们先是给出了隐马尔可夫模型、最大熵模型和最大熵马尔 可夫模型的相关描述。而后给出了条件随机场的定义、模型结构、势 函数的定义、参数估计、训练方法和计算方法等。接着本文描述了将 条件随机场用于汉语分词，采用汉字标注的分词方法及基于c r f s 的 北京邮电大学硕士学位论文基于c r f s 的中文分词算法研究与实现 中文自动分词系统的实现。基于c r f s 的中文分词的准确度很高，但 分词速度有待提高。分词速度是分词系统的一个重要指标，分词速度 有赖于词典结构查询速度的提高，本文提出了基于双字节的双数组查 询方法，速度上比基于单字节查询提高了1 0 左右，并针对双数组结 构空间稀疏和存储空间占用量大的问题，给出了解决方法，使双字节 查询方法的双数组结构在时间和空间上获得了一定的平衡。 关键字：自然语言处理；中文分词；条件随机场；双数组 h p r o c e s s i n gt a s k s ，s u b - w o r da c c u r a c yo fad i r e c ti m p a c to np o s t - p r o c e s s i n g t a s k s ，a n ds u b - w o r do ft h es p e e do fi m p a c to ns o m eo ft h ep r a c t i c a l a p p l i c a t i o no f t h es y s t e m s c o n d i t i o n a lr a n d o mf i e l d s ( c r f s ) i sac o n d i t i o n a lp r o b a b i l i t y m o d e la n da nu n d i r e c t e dg r a p hm o d e la l s o ，u s e df o rl a b e l i n ga n d c u t t i n g o f s e q u e n c ed a t a ，b l o c k sa n a l y s i s ，a r e d i s c r i m i n a t i o n ”m o d e l i td o e sn o t ”g e n e r a t e ”m o d e l s ，s u c ha sh i d d e nm a r k o vm o d e l s ( h m m s ) t h es t r i c t a s s u m p t i o n o fi n d e p e n d e n c e ，a n do v e r c o m et h em a x i m u me n t r o p y m a r k o vm o d e l ( m e m m s ) a n do t h e r d i s c r i m i n a t i o n m o d e ll a b e lb i a s ， q u e s t i o n t h em o d e lc a nb ev e r ye a s yp u ta n yo ft h ei n p u ts e q u e n c e c h a r a c t e r i s t i c si n t ot h em o d e l t h i s p a p e rs y s t e m a t i c a l l yd e s c r i b e st h et h e o r yo fc o n d i t i o n s r a n d o mf i e l d s a st h eh i d d e nm a r k o vm o d e l so ff a c e st h r e eb a s i c p r o b l e m sa n di nr e s o l v i n gt h es a m ep r o b l e mu s e das i m i l a rs o l u t i o n ；t h e c o n d i t i o n a lp r o b a b i l i t ym o d e ld e r i v ef r o mp r i n c i p l e so f p r o b a b i l i t ym o d e l i i i 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 o ft h em a x i m u m e n t r o p ym o d e la n dp a r a m e t e re s t i m a t i o nf u n c t i o ni nt h e f o r mo ft h es a m e ；a n di t sc o n d i t i o n a lp r o b a b i l i t ym o d e ll e a r n i n gf r o mt h e m a x i m u me n t r o p ym a r k o vm o d e l si nt h ef o r mo fp r o b a b i l i t ym o d e l t h e r e f o r e ，i no r d e rt om o r ec l e a r l yd e s c r i b et h ec o n d i t i o n a lr a n d o mf i e l d s t h e o r y , w ef i r s td e s c r i p t i o no ft h er e l e v a n to ft h eh i d d e nm a r k o vm o d e l ， m a x i m u me n t r o p ym o d e la n dm a x i m u me n t r o p ym a r k o vm o d e l t h e n g i v et h ed e f i n i t i o no fc r f s ，m o d e ls t r u c t u r e ，t h ed e f i n i t i o no fp o t e n t i a l f u n c t i o n ，p a r a m e t e re s t i m a t i o n ，t r a i n i n gm e t h o d sa n d c a l c u l a t i o nm e t h o d s w i t ht h ec r f so fc h i n e s ew o r ds e g m e n t a t i o n ，u s i n gc h i n e s ew o r d t a g g i n g m e t h o df o ra u t o m a t i cc h i n e s ew o r ds e g m e n t a t i o ns y s t e m s u b w o r dw o r ds p e e di sa ni m p o r t a n ti n d i c a t o ro ft h es y s t e m ，w h i c h d e p e n d so ns u b - w o r dd i c t i o n a r ys t r u c t u r e dq u e r ys p e e d ，t h i sp a p e r p r e s e n t sab a s e do nd o u b l e - b y t eq u e r ym e t h o d s o fd o u b l e - a r r a y , i m p r o v e d b ya b o u t 10 i ns p e e dt h a ns i n g l e b y t e b a s e dq u e r i e s a n df o rt h e d o u b l e - a r r a ys t r u c t u r es p a c es p a r s e ，a n dl a r g ea m o u n to fs t o r a g es p a c e o c c u p i e db y t h e q u e s t i o n ，g i v e n a s o l u t i o n ，s o t h a t d o u b l e b y t e d o u b l e a r r a y s t r u c t u r eq u e r ym e t h o d si nt i m ea n ds p a c et oo b t a i na c e r t a i nb a l a n c e k e y w o r d s ：n l p ；c h i n aw o r d ；c r f s ；d o u b l e - a r r a y i v i 3 i r 北京邮电大学硕士学位论文基于c r f s 的中文分词算法研究与实现 目录 第1 章引言l 1 1 研究背景和意义1 1 2 分词研究现状l 1 3 论文的主要工作3 1 4 论文组织3 第2 章条件随机场理论5 2 1 隐马尔可夫模型5 2 1 1 离散马尔可夫过程5 2 1 2 隐马尔可夫要素：6 2 1 3 隐马尔可夫模型的三个基本问题7 2 1 4 隐马尔可夫模型的局限性1 5 2 2 最大熵模型1 6 2 2 1 最大熵模型约束条件1 8 2 2 2 最大熵模型的原则1 8 2 3 最大熵马尔可夫模型2 1 2 3 1 最大熵马尔可夫模型的概率形式2 l 2 3 2 标记偏置问题2 2 2 4 条件随机场理论2 3 2 4 1 条件随机场定义2 4 2 4 2 势函数2 4 2 4 3 条件随机场分布模型2 6 2 4 4 条件随机场模型参数估计2 8 2 4 5 条件概率的矩阵计算3 0 2 5 本章小结3 2 第3 章基本c r f s 的算法优化与改进3 3 3 1c r f + + 3 3 3 2 观察序列对象及其优化3 4 3 2 1c r f + + 的观察序列对象3 5 3 2 2 优化的观察序列对象3 6 3 2 3 实验结果与分析3 8 3 3g i t e r b i 算法的改进3 8 3 3 1v i t e r b i 算法3 8 3 3 2v i t e r b i 算法引入规则策略3 9 3 3 3v i t e r b i 算法引入基于阀值的路径剪枝策略4 0 3 3 4 实验结果与分析4 1 3 4 双数组算法的改进4 2 3 4 1 双数组的构造与查询。4 3 3 4 2 双数组的优化4 4 3 4 3 用优化的算法构造字典4 8 3 4 4 实验结果与分析5 2 3 5 本章小结5 3 第4 章基于c r f s 的中文分词系统的实现5 5 v 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 4 1 全文检索项目5 5 4 2 中文分词系统组成5 6 4 3 模块间的关系图5 7 4 4 训练和测试过程5 8 4 5 模块功能与算法描述6 0 4 6 实验设计、结果及分析6 4 4 6 1 实验语料与评价指标6 4 4 6 2 特征模板选择6 5 4 6 3 实验设计6 6 4 6 4 与基于规则、h m m s 方法的比较6 6 4 6 5 实验结果与分析6 7 4 7 本章小结6 8 第5 章总结与展望6 9 5 1 本文总结6 9 5 2 未来工作7 0 参考文献：7 1 致谢7 3 攻读学位期间发表的学术论文目录7 4 v i 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 第1 章引言 中文自动分词是计算机科学研究的重要课题之一。它是中文自然语言理解、 机器翻译、电子词典等信息处理中的基础性工作。在汉语中，词是最小的能够独 立活动的有意义的语言成份，但是汉语是以字为基本书写单位，从形式上看，没 有词这个单位，词语之间没有明显的区分标记。因此，进行中文自然语言处理时 通常先是将汉语语料中的字符串切分成词语序列，这一过程叫做中文分词。 1 1 研究背景和意义 作为中文信息处理基础性任务的分词技术，被广泛用于基于中文的舆情分 析、信息检索、智能问答、信息抽取、文本挖掘，文本倾向性分析等。 网络媒体已被公认为是继报纸、广播、电视之后的“第四媒体”。网络成 为反映社会舆情的主要载体之一。网络环境下的舆情信息的主要来源有： 新闻评论、b b s 、博客、聚合新闻( r s s ) 等。网络舆情表达快捷、信息多元， 方式互动，具有传统媒体无法比拟的优势。为了把握舆论动向和正确引导 舆论，需要实施舆情分析与监控。舆情监控整合了互联网信息采集技术和 信息智能处理技术，通过对互联网海量信息的自动抓取、自动分类聚类、 主题检测、专题聚焦，实现用户的网络舆情监测和新闻专题追踪等信息需 求，形成简报、报告、图表等分析结果，为客户全面掌握群众思想动态， 提供分析依据和做出正确舆论引导。舆情分析与监控的首要任务是进行中 文分词，中文分词的准确度直接影响到后续任务的质量，而中文分词的速 度会影响到客户的实时性需求。 1 2 分词研究现状 中文自动分词是中文信息处理领域的一项基础性课题，也是智能化中文信息 处理的关键。由于中文自动分词在中文信息自动化处理中具有重要的地位，7 0 年代未以来，中文分词方面的研究备受人们关注，并出现了一批有实用前景的分 词方法。 分词技术的主要方法有两个：基于规则的和基于统计的方法。 由于c h o m s k y 的理论被广泛接受，从上个世纪6 0 年代到8 0 年代基于规则的 方法主宰了自然语言处理领域，该方法从语言学和认知学的观念出发，目的在于 建立一组语言学规则，使计算机按照这些规则来理解自然语言。 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 从形式上看，词是稳定的字的组合，因此在上下文中，相邻的汉字同时出现 的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较 好的反映成词的可信度n3 。基于概率统计的方法从概率统计和计算科学出发，通 过对大规模语料库的统计分析，使计算机能够处理自然语言。基于概率统计的方 法，其模型有着丰富的数学基础，使得可以被普遍应用。主要有隐马尔可夫模型 ( h i d d e nm a r k o vm o d e l s ，h m m s ) ，最大熵模型( m a x i m u me n t r o p ym o d e l s ，m e m s ) ， 最大熵马尔可夫模型( m a x i m u me n t r o p ym a r k o vm o d e l s ，m e m m s ) ，条件随机场 ( c o n d i t i o nr a n d o mf i e l d s ，c r f s ) 。 不论是基于规则还是概率统计的方法都能够处理自然语言中的一些任务，但 都存在一定的局限性。基于规则的方法只能在有限的语言现象中发挥作用，很难 覆盖复杂的现实语言的所有特性。另外，随着规则数量的增加，推理的难度和计 算量也随之增加，而且规则的手工获取需要工作量，规则的质量不能得到保证， 规则间可能出现相互矛盾。概率统计模型的分词方法也面临着一些问题。一是， 概率统计方法的独立性假设在现实语言中很难成立，语言符号之间原则上有一定 的关联性，用“阶数固定 的m a r k o v 模型的统计模型，这前提受到很大的质 疑。二是，语料规模的有限可能导致概率统计的非遍历性，出现数据稀疏问题。 三是，概率统计方法本身的“统计平均”，仅能保证统计平均意义上的正确，不 能保证具体事件结果的实际正确性：小概率事件也有可能发生，大概率事件也有 可能不发生。 基于规则的方法本质上是演绎，属于逻辑思维方式，基于统计的方法本质上 是归纳，属于经验思维方式。这两种方法存在非对立性和互补性，在自然语言处 理的研究中可以结合。从分词系统的发展可以看出，分词技术正从基于规则的方 法向基于概率统计或规则与概率统计相结合的方向发展。 基于统计模型的分词算法要想获得更好的切分精度，通常需要大规模的训练 语料，而大规模的训练语料的处理将耗费大量的时间。一般切分精度比较高的算 法，其切分速度一般较慢；而一些切分速度快的算法，因为考虑的因素较少，从 而带来切分精度不高。从主要分词算法来看，切分精度虽然有差别，但差异不是 特别大，好的分词算法其切分精度达到9 5 以上，一般的分词算法能达到8 0 以 上，而切分时间相对差别较大。切分算法的实时性要求对一些应用来说是至关重 要的，如搜索引擎，全文检索服务等。 目前主要的中文分词系统如下： ( 1 ) 微软研究院自然语言组从2 0 世纪9 0 年代初开始研制了一个通用型的 多国语言处理平台n l p w i n 。为了使n l p w i n 成为能够进行7 国语言处理的系统， 约从1 9 9 7 年，开始增加了中文分词，中文处理的研究。 2 北京邮电大学硕士学位论文基于c r f s 的中文分词算法研究与实现 ( 2 ) 中国科学院的张华平、刘群研制的i c t c l a s 分词词性标注一体化系统， 该系统使用基于多层隐马尔可夫模型，取得了很好的分词效果，并在9 7 3 相关主 题专家组组织的中文分词标注评测和国际s i g h a n 2 0 0 3 研讨会组织的中文分词评 测中分别获得多项第一。 ( 3 ) c r f + + 由日本人t a k uk u d o 博士创立的，采用条件随机场( c r f s ) 方法对 序列进行标注的系统。是一个简单、开源、可定制的c r f s 实现，目标是为了序 列数据的标记或分割。c r f + + 被设计成一个通用的目的，能处理自然语言处理的 多种任务，如命名实体识别、信息抽取和文本组块。 用c r f + + 进行中文分词，其准确度很高，但其训练速度和分词速度不高，对 工程开发和一些有实时性需求的应用带来一定的影响。 1 3 论文的主要工作 c r f s 是一种被广泛应用的机器学习方法，它能把与语言有关或无关的特征信 息纳入模型中，根据训练数据的不同自动赋予它们不同的权值，并对新情况做出 准确的预测。 本文主要研究基于c r f s 的中文分词算法，重点是条件随机场理论的研究，系 统模块的优化，将v i t e r b i 算法引入基于规则和基于阀值剪枝的策略，快速查询 结构的改进与实现。 本文主要完成以下几个方面的工作： 1 ) 优化系统结构：提高了分词系统的训练速度。 2 ) 优化v i t e r b i 算法：以快速的进行序列标注。 3 ) 优化查询结构：关键字查询的优化是中文分词速度性能提高的重要部分， 本文采用双数组查询结构，同时提出了双字节查询方法的双数组结构，并有效的 解决了双数组结构空间稀疏问题和总存储空间过大问题。 4 ) 参数训练：以北京大学标注的1 9 9 8 年1 月份人民日报语料作为训练数据， 使用高效的l b f g s 算法对模型参数进行训练。 1 4 论文组织 围绕以上研究内容，本文组织如下： 第一章介绍了中文分词的必要性，背景及研究意义，而后介绍了快速中文分 词的重要性和实用意义，应用领域基本概念，论文的主要工作，最后概述了本论 文的结构组织。 第二章介绍了条件随机场的理论，条件随机场的模型和它之前的其它基于统 3 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 计方法的模型有着紧密的联系，为了更好的叙述和理解条件随机场理论，我们先 是介绍了隐马尔可夫模型，最大熵模型，最大熵马尔可夫模型，而后重点介绍了 条件随机场理论。 第三章介绍了基于条件随机场的中文分词算法的改进，使之能满足有实时性 需求的应用。主要介绍了训练时架构的优化，该优化可节省大量的训练时间，在 实际项目开发中提高了工作效率，特别是进行大规模语料的训练。测试方面对用 于序列标注的v i t e r b i 算法进行了改进，效率较原v i t e r b i 算法提高了4 0 以上。 最后是对查询结构双数组算法的改进与实现。 第四章介绍了基于条件随机场的中文分词系统的实现，包括项目背景，系统 结构，模块间的关系，算法描述，实验设计，实验结果，结果分析及与基于规则、 h 删s 的模型的比较。 第五章对本文进行了总结，并指出了下一步研究的方向及内容。 4 隐马尔可夫模型( h i d d e nm a r k o vm o d e l s ，h m m s ) 研究始于1 9 6 6 ，基于统计 方法的隐马尔可夫模型在若干年后变得很受欢迎，原因有二个，一是该模型有丰 富的数学理论结构，能被广泛的应用；二是在若干重要应用上经恰当的运用表现 的很出色。在讲述隐马尔可夫模型之前，我们先简单介绍以下几个模型用到的马 尔可夫随机过程。 2 1 1 离散马尔可夫过程 设有n 个不同状态p 。，s ：，s 。) 的随机过程，令t = l ，2 ，表示不同的时间 点，q t 表示t 时刻随机过程所处的状态，口玎表示状态墨ns ，的转移概率。当随 机过程满足：当前所处的状态仅与它之前的一个状态有关，即 p q ，= s fi q f - l = s j , q ，- 2 = 墨，】= p q ，= 墨l q f - l = s j 】 ( 2 一1 ) 时，该随机过程为马尔可夫随机过程。而且我们考虑( 2 - 1 ) 式右边的随机过程 是独立于时间的，从而得到状态间的转移概率口盯， a 妒= p q ，= s fiq f - 1 = s j 】， 1 f ，j n ( 2 2 ) 转移概率口有以下属性： a 抒0 ( 2 3 a ) 5 北京邮电大学硕士学位论文基于c r f s 的中文分词算法研究与实现 = l ( 2 3 b ) j = l 因此口服从概率约束。 以上介绍了离散马尔可夫随机过程，下面我们先介绍隐马尔可夫模型的要 素，而后介绍隐马尔可夫模型面临的三个基本问题及解决方法。 2 1 2 隐马尔可夫要素 隐马尔可夫模型有五个要烈2 1 组成： 1 ) n ，表示模型中的状态数。一般地，模型中的各个状态是相互连结的， 任何状态能从其它状态到达。我们用s 表示各个状态的集合，s = p 。，j ：，如 ， q ，表示t 时刻的状态。 2 ) m ，表示模型中每个状态不同的观察符号，即输出字符的个数。我们用 w 表示各个字符的集合，v = p 。，v ：，v 肼) 。 3 ) a ，状态转移概率分布。a = 协口j ，其中， 以矿= 何g ，= s fq ，一l = s j 1 f ，j n ( 2 4 ) 当从状态s i 经一步到达s ，时，口 0 ，否则口i f = 0 。 4 ) b ，观察字符在状态j 时的概率分布，b = 札( 后) j ，其中 6 ( 尼) = 研y iq ，= s j 】1 j n ，1 k m ( 2 5 ) 5 ) 万，表示初始状态分布，万= 切 ，其中， 万j = 研g l = s j 1 j n ( 2 6 ) 给定，m ，彳，b ，7 ，h m m s 能输出一个观察字符的序列 o = o 1 0 2 o r ( 2 7 ) 其中o ，v ，t 是观察序列的字符个数。h m m s 程序如下： t = 1 ： 根据初始状态万，并让g 。= s ，； 6 北京邮电大学硕士学位论文基于c r f s 的中文分词算法研究与实现 f o r ( ts 丁) b e g i n 在状态s ，时，根据字符概率分布包( 后) ，输出字符0 ，= 唯； 根据转移概率分布口扩转移到下一个状态s ，； t = t + 1 ： e n d 从以上的讨论可知，一个完整的隐马尔可夫模型要求两个具体的模型参数 和m ，和三个概率矩阵么，b ，万，也即隐马尔可夫模型可形式化定义为一个五 元组( ，m ，彳，b ，7 ) 。 以上介绍了隐马尔可夫模型的五个要素，下面我们介绍隐马尔可夫模型的三 个基本问题及相应的解决方法。 2 1 3 隐马尔可夫模型的三个基本问题 1 ) 给定一个模型允= ( ，m ，a ，b ，7 ) ，如何高效的计算某一输出字符序列 0 = 0 1 0 2 0 r 的概率p ( oi 力) 。 2 ) 给定一个模型a = ( ，m ，a ，b ，万) 和一个输出字符序列0 = 0 ，0 ：0 r ，如 何找到产生这一序列概率最大的状态序列a = b i s ，s r 。 3 ) 给定一个模型五= ( ，m ，a ，b ，万) 和一个输出字符序列0 = 0 1 0 2 0 r ，如 何调整模型的参数使得产生这一序列的概率最大。 为了方便分析问题和给出解决方案，这里先介绍一下隐马尔可夫模型的条件 独立性假设。隐马可尔可夫模型是一个生成模型，给定一个观察序列，h m m s 模 型隐含一个与观察序列对应的状态序列。隐马可夫模型图示如下，图中清楚的表 示出了隐马尔可夫模型内部的条件独立关系，有三个独立性假设：一是t 时刻的 状态吼= 毛只依赖于t - 1 时刻的状态q f - l = s ， ，即 p ( q ，i g f l q l , a ) = p ( q ，iq t - i , 允) 。二是f 时刻所生成的值包( o ，) 只依赖于f 时刻的 r 状态吼= 毛，即p ( o o ：0 riq 。q ：q r , a ) = 兀p ( o ，lg ，) 。三是状态与具体时间 7 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 无关，即对任意的i 和j 都有尸q ，i q h ，) - p ( q ，i q ，五) 。 g l9 29 3 图2 1h m m 8 问题1 是一个评价问题，即给定一个模型名和一个观察序列0 = 0 。0 ：0 r ， 如何计算由模型产生这一观察序列的概率p ( oj 五) 。最直接的方法是枚举所有长 度为t ，输出观察序列为0 的可能的状态序列。假定其中一个状态序列为 q = q l q 2 q r ( 2 8 ) 其中q 。为初始状态，在( 2 8 ) 条件下观察序列o 的概率为 rr p ( oiq ，兄) = i - ip ( o ，iq ，名) = 兀b 吼( o ，) ( 2 9 ) 状态序列q 的概率为状态问转移概率的乘积 p ( q1 名) = 万们a g m a 9 2 毋a g 。打 ( 2 - 1 0 ) o 和q 的联合概率，即o 和q 同时发生的概率是上式( 2 9 ) ，( 2 1 0 ) 的乘积 p ( o ，q1 名) = p ( oq ，五) j p ( qi 兄) ( 2 - 1 1 ) 则给定模型五，观察序列o 的概率为观察序列与所有可能的状态序列q 的联合概 率的和，即为下式： p ( oi 五) = p ( o ，qi 力) = p ( olq ，2 ) p ( qi 兄) a r t 0a l t o _ = 万吼b q 。( o 。) 口哪：b q ：( 0 2 ) 口机晰b q ，( o r ) ( 2 1 2 ) 吼，q 2 ，q r 根据上式( 2 1 2 ) i , t 算p ( oi 兄) ，计算量为2 丁7 ，其中n 为模型中的状态数， 丁为观察序列的长度，对于观察序列中的每个符号都有个可能的状态，则长度 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 为z 的观察序列总共有r 个长度为丁的可能的输出状态序列。由上式( 2 - 1 2 ) 每个输出的状态序列需要2 丁次计算，确切的是( 2 丁一1 如r 次乘法运算，n r 一1 次 加法运算。即使很小的和r ，这种计算方法也是不可行的，例如当 n = 5 ，t = 1 0 0 时，计算量为2 1 0 0 5 1 0 0 1 0 7 2 ，既使在每秒1 0 0 0 万亿次的超级计 算机上运行，也需要1 0 年半。该计算方法的主要问题是大量的重复计算，目前 可采用f o r w a r d - b a c k w a r d 算法解决这个问题。 f o r w a r d b a c k w a r d 过程口。4 1 ：定义f o r w a r d 变量口f ( f ) 为 口，( f ) = p ( 0 1 0 2 0 ，q ，= j fl 见) ( 2 1 3 ) 即对于模型兄，在t 时刻，状态为墨时的部分观察序列0 。0 ：0 ，的概率记 为口，( f ) ，口，( f ) 为部分观察序列0 。0 ：0 ，和t 时刻的状态s ；的联合分布概率， 则口，( f ) 可递归得到。由各个观察字符的输出状态相互独立，下面给出口，( f + 1 ) 的 递推过程： 口j ( t + 1 ) = p ( 0 1 0 2 0 f + l ，q f + l = s l 兄) = p ( 0 1 0 2 0 f + lq f + l = j ，2 ) p ( q f + l = s ，i 兄) = e ( o 1 0 2 o flq f + l = s j , 2 ) p ( o f + 1ig = 8 1 , 2 ) p ( q f + l = s ja ) = p ( 0 1 0 2 0 ，g ，= 矗q + 1 = j ，i2 ) p ( o iq 州= 勺，力) = p ( 0 1 0 2 0 ，= s jl a ，= s f ，2 ) p ( q ，= 墨i a ) p ( o mi q 川= s i ，五) = p ( 0 1 0 2 0 。ig ，= s i2 ) p ( q ，+ l = j ，iq ，= q ，2 ) p ( q ，= 既l2 ) p ( o 件iig 什l = j ，名) = p ( 0 1 0 2 0 q = 墨l2 ) p ( q f + l = s lq ，= s l , 2 ) p ( o 州lq f + l = s ，五) =阻咖dbj(oli=1 州， = i q ( f ) i 州) j 1 ) 初始化 9 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 口1 ( f ) = z i b i ( 0 1 ) ， i i ( 2 1 4 ) 2 ) 递归，假设f 时刻处于状态墨，t + l 时刻处于状态彭，则有 r 1 a t + i ( _ ，) = i ( f ) 口i b ( o ) ， 1 n 1 f r 一1 ( 2 1 5 ) li = lj 则由上式( 2 1 4 ) ( 2 1 5 ) 可得观察序列所有可能的状态序列的概率为， p ( ol 五) = 口r ( f ) i = l ( 2 - 1 6 ) f o r w a r d 算法的核心部分是递归计算，下图说明了在t 时刻从个状态墨， 1 i n 到达f + 1 时刻的状态邑， t ( f ) t + l 口r + l ( j ) 图2 - 2 f o r w a r d 计算 下面以格子( l a t t i c eo rt r e l l i s ) 结构说明f o r w a r d 的实现过程， sn s 2 s l 才 斗 o l 0 2u 3 u 7 图2 - 3f o r w a r d 计算的格子结构 由以上可知( f ) 是观察序列0 。0 ：0 ，和t 时刻所处的状态s ，的联合概率， 口，( f ) 口 是观察序列o 。o ：o ，的在f 时刻的输出状态序列和在f + l 时刻经s i 到达 s ，的联合概率，从f 时刻所有个可能的状态s ；，1 f 到达f + 1 的已状态的 概率和，而后乘以f + l 时刻观察字符o 在状态j ，的概率屯( o ) 为t + l 时刻在 占，状态的概率，即得到口f + l ( j f ) ，1 j n ，t = 1 ，2 ，t l 。最终的f o r w a r d 变量 l n 即t 时刻，部分观察序列从0 川到0 r ，给定模型兄和状态s ，条件下的概率，由h m m s 的特性，我们可以递推f l t ( i ) ： 肛( i ) = p ( o f + 1 0 f + 2 o7 iq ，= 墨，五) = p ( o 川0 f + 2 07 t ，q 川= s ji q ，= s f ，五) j = l = p ( o f + 1 0 f + 2 o riq f + l = s 1 , 2 ) p ( q = j iq ，= 黾，五) j = l q = j ，旯) p ( o iq = s y , 2 ) p ( q ，+ 。= j ，iq ，= j ，名) = 口j f b j ( 0 川) 屈+ 。( _ ，) 1 ) 初始化屏o ) = 1 ，1 i n 。 2 ) 已知孱+ 。( f ) ，可递归得到f l t ( j ) ， f i t ( j ) = 口 b ，( o f + 1 ) 屈+ l ( n t = t - 1 ，t - 2 ，1 ，1 i 冬 ( 2 1 9 ) = i b a c k w a r d 计算图示如下： r o 2件 o ，l p 同 = 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 s l s 2 t t + l 屈( n f l , + 。( ) 图2 - 4b a c k w a r d 计算 给定观察序列o 和模型五条件下，t 时刻状态为g f = j ，时的状态序列的概率 定义为p ( q ，= s ，10 ，五) 。由口) ，屈( f ) 可知观察序列和f 时刻状态为q ，= s ，时的 联合概率尸q ，= s ，0i 允) 为： p ( q ，= s ，0i 兄) = g , ( i ) f l t ( i ) ( 2 2 0 ) 而 nn p ( oi 兄) = p ( q ，= s ，o1 名) = ( i ) f l t ( i ) ( 2 2 1 ) i = li = l 由上面两式可知： 岍胭卅= 铲2 丽a t ( i ) f l t ( i ) ( 2 _ 2 2 ) 图示如下： t 1 一。( ) t t + l q ( f ) ，f l , ( f )f l , + 。( j f ) 图2 - 5 节点概率计算 问题2 是一个解码问题，即从r 个可能的状态序列中找到一个“最优”的 状态序列，其中是h m m s 模型中状态的个数，丁是观察序列的长度。不像问题 1 2 北京邮电大学硕士学位论文基于c r f s 的中文分词算法研究与实现 1 能给出一个确定的解决方案，对于问题2 根据“最优 的标准不同，可以有若 干个解决方案，所以给定观察序列，找出“最优 状态序列的困难是最优状态序 列的定义，即最优标准的选择。例如一个最优标准是去选择在f 时刻，状态为q 。 的单个概率为最大，这个最优标准是使状态序列中正确的单个状态的数学期望值 最大，为实现问题2 的这一解决方案，我们定义一个变量以( f ) 表示给定观察序 列0 和模型五条件下，在t 时刻，状态为吼= j ，时的概率： 形( f ) = p ( q ，= j ；l0 ，力) ( 2 2 3 ) 上式可以用f o r w a r d b a c k w a r d 变量( f ) ，屈( f ) 表示，由式( 2 2 2 ) 可知： 协丽a t ( i ) f l t ( i ) 2 k a t ( i 丽) f l t ( i ) ( 2 - 2 4 ) 其中口，( f ) 为t 时刻，前面部分观察序列o 。o ：o ，在状态吼= s ，时的概率。屈( f ) 为 t 时刻，后面部分观察序列0 m 0 m 0 r 在状态g f = s ，时的概率。 p ( o i 兄) = q ( i ) f l t ( i ) 是一个归一化因子，使以( f ) 满足经典概率的条件，即： i = l 以( f ) = 1 扛l ( 2 - 2 5 ) 利用7 ，( f ) 我们可以找出t 时刻单个概率最大的状态吼，如下式： 吼= a r g m a x 防( f ) l 1 t t( 2 2 6 ) l s l s 虽然这种最优标准使最终状态序列中的正确状态的数学期望最大，但是给结果状 态序列带来了一些问题。当h m m s 模型中有状态转移的概率为零时，例如从状态j 到状态s ，的转移概率a ，= 0 ，那么依据这个最优标准得到的状态序列将不是一个 有效的状态序列，这是因为这个最优标准选择每个时刻状态最大的概率组成状态 序列，没有考虑到生成状态序列的总体概率。关于这个最优标准，一些可能的修 正方法是考虑多个正确的状态对( g ，g m ) 或g ，q 州，q m ) ，虽然这些方法对某些应 用是合理的，但最广泛应用的标准是考虑使整个状态序列最优，也即是最优路径 北京邮电大学硕士学位论文 基于c r f s 的中文分词算法研究与实现 问题，这种方法试图找到最大的p ( q0 ，名) ，由于e ( o1 名) 的概率对找到最大的 尸 10 ，五) 没有影响，实际上等于找到最大的尸( q ，oi 兄) 。一个有效的查找最优路 径的算法是v i t e r b i 算法，它基于动态规划方法。 v i t e r b i