（模式识别与智能系统专业论文）汉语词与句子切分技术及机器翻译评估方法研究.pdf

摘要 本论文以统计模型为基础，在参考了大量前人工作的基础上，对汉语词法分 析、口语句子切分和机器翻译评估进行了较为深入的探讨和研究。汉语词法分 析是大部分中文处理的第一步，其重要性不言而喻；句子切分是语音翻译中连 接语音识别和文本翻译的桥梁，无论语音识别和文本翻译单独的效果有多么好， 这座桥没搭好，综合的性能依然无法提高；机器翻译的自动评估是构建机器翻 译系统中很重要的辅助工作，其可以加速翻译系统的开发速度，缩短其开发周 期。简言之，这三方面同属于自然语言处理的基础的研究领域，其效果直接影 响到高层应用的水平。 在词法分析上，我们茅4 用隐马尔可夫模型( m 心) 提出了一种融和了分词、 词性标注和命名实体识别的一体化诃法分析方法。最初我们用基于类别的 h m m ，其优点是对词的覆盖面广，系统开销小；缺点是不能精确地预测词的出 现概率。为了提升模型的准确率，我们引入基于词汇的 i m m ，并将两者有机地 结合，并用一个“词到字”的概率平滑方法对基于词的h m m 进行平滑。实验 结果显示，我们的混合模型由于综合考虑到了字、词、词性以及命名实体的知 识，在切分的准确率和召回率上都明显优于单纯基于类别或者基于词的h m m 。 此外在分词系统的实现上，我们借助对通用分词系统a p c w s 的整体框架和各功 能模块的介绍，讨论了如何有效地存储和加载数据等一些技术细节问题。 在口语句子切分上，我们提出了基于双向n 元模型和最大熵模型的句子切分 算法，这种算法由于通过最大熵有机地将正、逆向n 元切分结合起来，综合考 虑到了切分点左、右的上下文，从而得到了很好的切分效果。我们在中、英文 语料上训练我们的模型并作铡试，结果显示其在性能上明显优于基本的正向n 元切分。在此基础上，我们分析并对比了各模型的切分结果，从而验证了我们 当初对于模型的预计：其一方面保存了正向n 元算法的正确切分，一方面用逆 向n 元算法有效地避免了正向算法的错误切分。 在机器翻译的自动评估上，我们首先介绍了两种常用的基于参考译文的评估 算法b l e u 和n i s t ，然后给出了一种基于n 元模型的句子流畅度评估方法e 3 。 这种方法不需要借助任何参考译文，它通过区别地对待句子中不同的词的转移 概率，达到了很好的评估效果。 综上所述，本文针对汉语词法分析、口语句子切分和机器翻译评估提出了以 统计模型为基础的创新方法，它们不仅仅在科学方法上有重要的参考价值，对 于实际应用中也有重要意义。 a b s t r a c t t h i st h e s i sp r o p o s e do u rn o v e ls t a t i s t i c a l a p p r o a c h e so nc h i n e s ew o r d a n a l y s i s ，u t t e r a n c es e g m e n t a t i o na n da u t o m a t i ce v a l u a t i o no fm a c h i n e t r a n s l a t i o n ( m t ) w o r da n a l y s i si st h ef i r s ts t e pf o rm o s ta p p l i c a t i o n b a s e do nc h i n e s el a n g u a g et e c h n o l o g i e s ：u t t e r a n c es e g m e n t a t i o ni st h e b r i d g ew h i c h c o n n e c t ss p e e c hr e c o g n i t i o na n dt e x tt r a n s l a t i o ni nas p e e c h t r a n s l a t i o ns y s t e m ：a u t o m a t i ce v a l u a t i o no fm a c h i n et r a n s l a t i o n ( m t ) s y s t e mc a ns p e e dt h er e s e a r c ha n dd e v e l o p m e n to fam ts y s t e m ，r e d u c ei t s d e v e l o p i n gc o s t i ns h o r t ，t h e t h r e e a s p e c t sa l lb e l o n g t ot h eb a s i c r e s e a r c ha r e ao fn a t u r a ll a n g u a g ep r o c e s s i n g ( n l p ) a n dh a v es i g n i f i c a n t m e a n i n gt om a n yi m p o r t a n ta p p li c a t i o n ss u c ha st e x tt r a n s l a t i o n ，s p e e c h t r a n s 】a t jo na n ds oo n i nc h i n e s ew o r da n a l y s i s ，w ep r o p o s e dan o v e lu n i f i e da p p r o a c hb a s e do n h m m ，w h i c he f f i c i e n t l yc o m b i n ew o r ds e g m e n t a t i o n ，p a r to fs p e e c h ( p o s ) t a g g i n g a n dn a m e d e n t i t y ( n e ) r e c o g n i t i o n o u r f i r s t m o d e li sa c l a s s b a s e dh m m s oa st oi n c r e a s ei t sa c c u r a c y ，w ei n t r o d u c ei n t ot h e w o r d b a s e d m ma n dc o m b i n ei tw i t ht h ec l a s s b a s e dh m m a tl a s tw eu s e d a “w o r d t o c h a r a c t e r ”s m o o t h i n gm e t h o df o rp r e d i c t i n gt h ep r o b a b i l i t y o ft h o s ew o r d sw h i c hd o n to c c u ri nt h et r a i n i n gs e t t h ee x p e r i m e n t a l r e s u l t ss h o wt h a to u rc o m b i n e dm o d e l ，b yc o m p r e h e n s i v e l yc o n s i d e r i n gt h e i n f o r m a ti o no fc h i n e s ec h a r a c t e r s ，w o r d s ，p o sa n dn e ，a c h i e v e dm u c h b e t t e r p e r f o r m a n c e i nt h e p r e c i s i o na n dr e c a l l o ft h ec h i n e s ew o r d s e g m e n t a ti o n b a s e do nt h ek n o w l e d g eo fo u rc o m b i n e dm o d e l ，w ed e s c r i b e d t h ed e t a i l si ni m p l e m e n t i n gt h eg e n e r a lw o r ds e g m e n t a t i o ns y s t e ma p c w s w ed i s c u s s e ds o m et e c h n i c a lp r o b l e m si nt h ed a t as a v i n ga n dl o a d i n g ，a n d d e s c r i b e do u rm o d u l e so f k n o w l e d g em a n a g e m e n t a n dw o r dl a t t i c e c o n s t r u c t i o n i nu t t e r a n c es e g m e n t a t i o n ，t h i sp a p e rp r o p o s e dan o v e la p p r o a c hw h i c h w a sb a s e do nab i - d i r e c t i o n a ln - g r a mm o d e la n dm a x i m i z e de n t r o p ym o d e l t h i sn o v e lm e t h o d ，w h i c he f f e c t i v e l yc o m b i n e st h en o r m a l a n dr e v e r s e i l n - g r a ma l g o r i t h m ，i sa b l et om a k eu s eo fb o t ht h el e f ta n dr i g h tc o n t e x t o ft h ec a n d i d a t es i r ea n da c h i e v e dv e r yg o o dp e r f o r m a n c ei nu t t e r a n c e s e g m e n t a t i o n w ec o n d u c t e de x p e r i m e n t sb o t hi nc h i n e s ea n di ne n g l i s h t h er e s u l t ss h o w e dt h ee f f e c to fo u rn o v e lm e t h o dw a sm u c hb e t t e rt h a n t h en o r m a ln - g r a ma l g o r i t h m t h e nb ya n a l y z i n gt h ee x p e r i m e n t a lr e s u l t s ， w ef o u n dt h er e a s o nw h yo u rn o v e lm e t h o da c h i e y e db e t t e rr e s u l t s ：i to n o n eh a n dr e t a i n e dt h ec o r r e c ts e g m e n t a t i o no ft h en o r m a ln - g r a ma l g o r i t h m ， o nt h eo t h e rh a n da v o i d e dt h ei n c o r r e c ts e g m e n t a t i o nb ym a k i n gu s eo f r e v e r s en g r a ma l g o r i t h m i na u t o m a t i ce v a l u a t i o no fm ts y s t e m s w ef i r s ti n t r o d u c e dt w oc l a s s i c m e t h o d so na u t o m a t i ce v a l u a t i o nw h i c hr e l l e do nr e f e r e n c et r a n s l a t i o n s t h e nw ep r o p o s e do u rn o v e ls e n t e n c ef l u e n c ye v a l u a t i o nm e t h o db a s e do n n - g r a mm o d e l t h i sm e t h o d ，c a l l e d a se 3 ，d o e s n tn e e da n yr e f e r e n c e t r a n s l a ti o n sa n da c h i e v e d v e r y w e l le v a l u a t i o np e r f o r m a n c eb y d is c r i m i n a t e l yu s et h ed i f f e r e n tt r a n s m i s s i o np r o b a b i l i t i e so fw o r d si n t h ee v a l u a t i n gs e n t e n c e i ns u m m a r i z a t i o n ，t h i st h e s i sp r o p o s e dn o v e la p p r o a c h e sf o rt h et h r e e b a s i cr e s e a r c h e si nn l p ：c h i n e s ew o r da n a l y s i s ，u t t e r a n c es e g m e n t a t i o n a n da u t o m a t i ce v a l u a t i o no fm ts y s t e m s w eb e l i e v et h eo r i g i n a l i d e a s int h e mn o to n l yh a v ei m p o r t a n tr e f e r e n c ev a l u ef o ro t h e rr e s e a r c h e s ， h u ta l s oc a nb eu s e dt oi m p r o v et h ep e r f o r m a n c eo fn l pa p p l i c a t i o n s i l l 独创性声明 本人声明所成交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与 我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确地说明并表示了谢意。 虢一到工跏虢熟垂 日期： 关于论文使用授权的说明 塑坐- 望 本人完全了解中国科学院自动化研究所有关保留、使用学位论文的规定，即：中国科学院自 动化研究所有权保留送交论文的复印件允许论文被查阅和借阅；可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 签名 ( 保密的论文在解密后应遵守此规定) 第一章绪言 第一章绪言 近十几年来，随着计算机硬件设备的飞速发展，其单位存储和计算成本大 幅度降低，使一些基于大规模搜索和迭代的复杂算法能够在p c 上广泛地实现和 应用；而随着行业信息化的普及和网络资源的迅猛膨胀，可用语料资源也大为 丰富，这一切给基于大规模语料库的统计自然语言处理提供了所需的硬件和软 件环境。 统计自然语言处理以数学模型和大规模语料库为基础，其核心思想是建立 数学模型以表述某一种语言现象，然后在大规模语料库中对那种模型进行训练， 使其满足已经获知的经验知识，然后用训练好的模型对于未知的现象进行预测。 几乎所有基于统计的方法都可以归结到上述的框架中去。相比传统的基于规则 的自然语言处理，统计方法有如下好处。 第一，它不依赖于人主观的先验知识，这也是本文认为统计方法最重要 的优点。大规模语料库实际上和规则一样，都是一种知识的表征 形式。不同的是语料库相比规则而言，有更强的独立性和客观性。 大家知道，规则往往是针对某一特定的应用，由某方面的专家按 照一定的形式所书写的指导原则，它是专家在自己的经验基础上 对语言现象的一种总结，具有很强的主观性。往往不同的专家所 书写的规则会有不同，甚至同一位专家在不同时候所写规则也会 有出入，而随着规则的不断增加，新旧规则之间会产生矛盾，当 规则的数目达到一定程度以后往往就不可能再增加新的规则了。 而语料库很简单，任何一篇电子文档都可以成为一个小的语料 库，郎使对于那些经过人工处理后的熟语料，由于大家是在一定 规范地约束下进行的，那些规范相对而言都是比较简单和机械的 规范，所以人的主观影响会小得多，即使在某些个别的词或旬上 出现矛盾，也不会对整体造成很大影响。 第二，统计方法相比基于规则的方法有更强的鲁棒性。规则的方法是离 散的，一条规则只能总结有限数目的语言现象；而统计模型是连 续的，它可以对全部的现象进行描述。规则是人对于经验知识的 一种抽象，这种抽象是零散的，它并不保证所有的规则的总和可 以描述全部的语言现象，所以每遇到一个不能处理的实例，我们 必须增加新的规则以满足需求。而统计模型所依赖的语料库虽然 也是离散的，语料库中包含的现象也只是全部现象的一个真子 汉语词与句子切分技术及机器评估方法研究 集，但由于我们是用严密的数学模型来对现象进行的抽象和归 纳，它就可以保证训练出的模型适用于所有的实例，从而保证了 强的鲁棒性。当然，不同的统计模型对现象描述的准确程度是不 一样的。 第三， 统计方法将知识和算法分离。前文已提过，规则往往是由某方面 的专家针对某一特定的应用所书写的指导原则，而同个语料库 可以为多种算法、多种应用服务，它是很独立的知识库。这样语 料库的建立和完善可以和算法的设计并行，不仅节省了人力物 力，也给一些标准化测试提供了基础。另外这项优点给基于统计 方法的系统的维护和更新带来了很大的方便。随着应用的扩展， 我们往往要考虑到新的语言现象，这时基于统计方法的系统只需 要用更大的语料库重新弘i i 练一下模型就可以了，而基于规则的方 法则需要增加大量的规则，而如上文以前提过的，这并非一件容 易的事情。 正是由于这些优点，统计方法在近十年来得到了飞速发展，它逐步取代传 统基于规则的方法，成为自然语言处理领域的主流技术。 在中文处理方面，统计方法已经有很多成功的应用，如词性标注、音字转化 及拼音输入等，但由于汉语本身的复杂性和灵活性，有很多问题依然尚待解决。 本文试图以统计模型为基础，研究汉语自动分词、分句及机器翻译自动评估的 解决方法。分词是大部分中文处理系统的第一步，其重要性不言而喻；句子切 分是语音翻译中连接语音识别和文本翻译的桥梁；而机器翻译的自动评估可以 提高一个机器翻译系统的开发速度和节约其成本。简言之，这三类问题同属于 中文信息处理领域的基础研究课题，它们的效果直接关系到其他高层应用，所 以我们的研究不仅仅在科学方法上有重要的参考价值，对于实际应用也有重要 意义。 后面的章节是这样安排的：第二章介绍三种常用的统计模型，这是本文所提 出的方法的理论基础；第三章介绍基于隐马尔可夫模型的一体化汉语分词方法； 第四章介绍基于n 元模型和最大熵模型的句子切分方法；第五章介绍基于n 元 模型的句子流畅度评估方法：第六章对全文进行总结。 第二窜统计语言模型 第二章统计语言模型 本论文的所有工作均是基于统计方法，因此在本章里，我们将介绍一些常用 的统计模型。其构成了我们的方法的理论支撑。 统计模型是一种抽象的数学模型，用来对事物进行一种近似的描述，它首先 假设某类现象满足一种模型，然后用已知的现象实例对模型进行训l 练，以得到 模型的相关参数，然后用这个训练过的模型来预测未知的现象。对于自然语言 处理而言，最常用的有n 元模型、隐马尔可夫模型、最大熵模型等。 2 1 n 元模型 21 1 n 元模型定义 n 元模型是自然语言处理中最常用的一种数学模型。它的定义如下。 如果我们假设语言也满足马尔可夫性，那么某一个词在某个句子中的出现概 率就可以用公式1 进行计算，进而一个句子的概率可以计算为： p ( s ) = p ( w l w 2 w 。) ( 2 ) = p o 嵋) xp ( w zlw 】) p ( w 1w 卜肿1 w h ) p ( w 。 w 。一肿 w ，一i ) 。 一般n 越大，模型越精确，但所用参数和所需要的训练集也越大( 如果训练 集不够大将导致严重的数据稀疏问题) 。假设词汇量为l o o k ( 实用中文系统的词 汇量) ，下表给出了不同的n 元模型的参数形式以及所用的参数数目。 汉语词与句子切分技术及机器评估方法研究 表l ：n 元模型实例及参数个数 模型参数参数个数 o - g r a mp ( w ) = 1 l v l 1 卜g r a m ( u n i g r a m )p ( w ) l e 5 2 - g r a m ( b i g r a m )p ( w 。1 w 。一，) l e l 0 3 - g r a m ( t r i g r a m )p ( w 。l w 。 w ) 1 e 1 5 4 - g r a m ( t e t r a g r a m )p ( w 1 w l 一3w 。2w 一1 ) 1 e 2 0 在实际运用中，考虑到训练所需的语料规模，n 一般取3 ，也就是所谓的 2 1 2 参数估计 2 1 2 1 最大似然估计 虽然我们已经介绍了n 元模型的基本概念，但要真正使用它，还需要进行参 数估计这一步，也就是将表1 中的那些参数计算出来。以t r i g r a m 为例，用最 大似然估计计算参数的公式为： 酬w i _ 2 w i - 1 ，= 篇糟 ( 3 ) 其中c o u n t 似，叫表示虬在l l 练语料中同现的次数e 最大似然估计可以计算出训练语料中出现过的n 元组对应的t r i g r a m 参数， 但如果我们碰到没有出现过的n 元组怎么办呢? 最简单的办法是认为那些参数 为0 ，但这样做会导致系统的适应能力很低，一旦碰到未出现过的n 元组，系统 就基本上处理不了。 为了解决这一问题，l a p l a c e 提出了一种简单机制，就是给每个n 元组，无 论其有无在训练语料中出现，都加上1 。如下图所示。 第二章统计语言模型 图2 ：l a p l a c e 法则 l a p l a c e 法则可以粗略解决“0 次数”问题，但它将所有未出现的n 元组都 赋予出现次数1 是不符合语言模型的实际情况的，因为很多词的组合( n 元组) 其实根本就不存在。 l i d s t o n e 在l a p l a c e 的基础上又做了一点改进，他给所有n 元组加上的不 是整数l ，而是一个待确定的小数p 。如下图所示。 图3 ：l i d s t o n e 法则 u 是一个小于l 的小数，可以在通过如下方式训练得到：将训练语料分为2 部 分a 和b ，首先用a 对n 元模型进行训练，然后对b 进行预测，调节u 直到“。， 使得对b 的预测达到最佳；然后用b 作训练，a 作测试，调节u 直到i x ：；u 最 终的值为u 。和u 。的算术平均值。 2 1 2 2 参数平滑 l a p l a c e 和l i d s t o n e 法则仅仅是对“o 次数”问题的一个粗糙的解决方式， 它们都无法针对不同的n 元组做出不同的预测，我们需要更为细致的参数平滑 算法来帮助我们进行参数估计。 从机理上划分，目前的参数平滑算法可以分为折扣法( d i s c o u n t i n g ) 、回退 法( b a c k o f f ) 和插值法( i n t e r p o l a t i o n ) 。在这里我们只介绍其中的回退法。 回退法是最常用的一种平滑算法，它的基本思想是当高阶参数不存在时，回 汉语词与句子切分技术及机器评估方法研究 退到低阶参数，当然，为了保证每一阶参数的总和要为l ，对于那些存在的参数 要进行一些减弱。我们以m o d i f i e dk n e s e r 舱，s m o o t h i n g 为例来介绍回退法， 这种平滑方法被认为是对于n 元模型最有效的平滑算法之一，也是本文所实现 的系统中所实用的方法。m o d i f i e dk n e s e r 呐砂s m o o t h i n g 算法见图4 。 从图4 中我们可以看出，对于已经存在的n 元组，m o d i f i e dk n e s e r - n e y s m o o t h i n g 根据他们出现的次数给出不同的消减，对于不存在的n 元组，它根据 一定的比例回退到低阶参数，而低阶参数的计算和高阶类似，可以回退到更低 阶。值得注意的是m o d i f i e dk n e s e ，舱，s m o o t h i n g 对于一元参数的计算方法， 它没有使用语料中的绝对统计数目，而是用和它相邻的不同的一元组的数目， 这样可以避免如下的错误回退发生：假设词组a b 在语料中出现的频度很高，但 是对于b 而言，它只出现在a 的后面，也就是p ( b l a ) = 1 ，这样如果统计b 的出 现频度，是很高的，而当我们计算某个p ( b l c ) 时，显然语料中找不到c b 这个词 组，因而回退到p ( b ) ，而p ( b ) 的值是很大的，这样就形成了一种误导。而如果 我们用b 左边出现的不同词的个数作为元概率的统计基础，那么b 左边只有a 这一个词，个数为1 ，当我们再回退到b 时，就不会出现很高的概率，从而避免 了这种误导。 第二章统计语言模型 汉语词与句子切分技术及机器评估方法研究 2 2 隐马尔可夫模型 2 2 ，1 定义 隐马尔可夫模型( h i d d e nm a r k o vm o d e l ) 是自然语言处理和语音识别中又 一非常常用的数学模型，它于2 0 世纪6 0 年代末被b a u m 提出，在7 0 年代处被 c m u 的b a k e r 第一次用于语音识别，其后慢慢流行开来并被用于自然语言处理的 一些领域中。它假设在观测现象的背后有一系列隐藏的状态，观测序列是由这 些隐藏状态序列所生成，其定义如下图所示。 图5 ：隐马尔可夫模型 和隐马尔可夫模型相伴随的一般有三项假设：马尔可夫假设、不动性假设和 输出独立性假设。马尔可夫假设是假设状态序列满足一阶马尔可夫性，即某一 状态序列出现的概率只和它前面一个状态相关，这点和二元模型是一致的；不 动性是状态的转移和时间无关；独立性是某一观测现象只和当前状态相关。如 果我们用0 。，0 ：，o r 表示观测序列，x ，x ：，x ，表示状态序列，这三项假设可 以用下图表示。 图6 ：隐马尔可夫假设 第二章统计语言模型 2 2 2 和h m m 相关联的三个问题 和n 元模型一样，在给出了定义之后，我们自然想到如何去训练和使用它。 一般而言，和隐马尔可夫模型相关的有三个经典问题：评估问题，解码问题和 学习问题。以下我们将分别介绍。 2 2 2 1 评估问题( 前向算法) 评估问题是给定模型 ，求某一观测序列o h ，0 。的概率。为了简化这个问 题，我们首先假设观测序列是由状态o = q q ，生成的，在这个假设下，观测序 列的概率为： r p ( o i q ， ) = 丌p ( q 五) ，( d 。) b 。：( o ：) x - b ，( o ，) ( 4 ) ，2 t 而给定x ，状态序列q = q 一q ，的概率为： p ( qi 旯) = p ( q l q 2 q ri 咒) = 刀吼a 吼g ：a 9 2 如a g ，一秆 ( 5 ) 由于我们并不知道观测序列是由哪一种状态序列所生成，我们必须考虑所有的 情况，也就是： p ( ot a ) = p ( q ，oi 五) = p ( o iq ，a ) p ( q 五) a i iq ! t q = z 。b ( o 。) 口 ! b q ：( d ：) 口。b ，( o ，) h 乱q t ( 6 ) 公式6 给出了计算观测序列的方法，但从公式中我们可以看出，其时间复杂度 很高，假设状态空间长度为n ，q l ，一q ，有n 1 种可能组合，而总的时间复杂度将 为： t i m e = n 7 2 t 指数级复杂度的算法在实际应用中一般是无法实现的。为此我们引入动态规划 来缩减计算量，由于h 删中的状态的转移概率只和其前一状态相关，这给我们 的计算带来了很大好处。我们定义前向变量ai 。为：给定模型 ，在t 时刻状 态为s ，的部分观测序0 、0 。的概率。用公式表述如下： 一一 坚堕型苎望! 塑坌垫查墨塑墅堡竺塑堕里壅 a ? = p ( 0l 0 ，q ，= s 。1 名) 基于n 。，n 。可以计算为： 口0 ，= 口? ao b ，( o 。) f 这是一个迭代公式，其初始值为： g i = 乃，b f ( 0 【) 而我们最终所要得到的结果为 ( 7 ) ( 8 ) ( 9 ) p ( o 1 彳) = p ( o ，o ：0 tq ，= s i ) = 口； ( 1 0 ) i 而对于公式l o 的迭代计算，在每一个观测值我们要考虑所有n 个状态，对于每 个状态我们需要考虑其前面n 个状态，那么总的时间复杂度为n * n * t = n 2 木t ，大 大小于先前的n t * 2 t ，这个复杂度是可以实现的。 2 2 2 2 解码问题( 韦特比算法) 解码问题就是给定，模型和观测序列，找到最可能的状态序列。这个问题也 是h m m 在大多数实际应用中的运作方式。比如对于词性标注，我们把词看作观 测序列，词性看作状态序列，标注的过程就是找到最可能的状态序列的过程。 对于解码问题的精确数学描述如下： q = a r g m a x p ( 0 1 0 2 0 r ，q l q 2 q ri2 ) 目1 口2q r 事实上解码问题和评估问题很相似，评估是计算所有可能的状态序列产生的 观测序列的概率的总和，而解码则是从这些状态序列中挑出最有可能的，也就 是概率最大的。 和评估问题类似，如果我们遍历所有可能的状态序列，计算的时间复杂度会 很高，我们同样采用动态规划来解决解码问题。我们定义6i 。为t 时刻到达状态 第二章统计语言模型 i 的最优路径( 状态序列) = m a xp ( q l q 2 吼= f ，0 1 0 2 0 ，l 五) q q q 2 “一i 这样在t + l 时刻到达状态k 的最优路径为 醴= m a x ( 8 。b j ( 0 , + - ) ) ( 1 2 ) ( 1 3 ) 对于每个状态，我们通过公式1 3 选择其最优的前一状态并记录下来，一直到最 末的状态t ，然后遍历t 的各个状态，选择最优的一个，最后通过各状态的前驱 得到完整的最优路径，也就是状态序列。这个过程可以用下图表示。 图7 ：韦特比搜索 2 2 2 3 学习问题( 前向后向算法) 学习问题也就是训练问题，即给定观测序列，找到最优的 ，使观测序列 的概率也就是p ( 0 i ) 最大。这个问题是三个问题中最难的一个，一般我们用前 向后向算法( e m 算法在删参数估计上的应用) 来预测x 。 包含三方面，初始概率分布、状态间转移概率、和状态到观测值的生成 概率。我们首先来考虑如何计算这三种参数的期望值。 首先我们引入后向变量b 。：给定t 时刻的状态s 和模型x ，部分观测序列 汉语词与句子切分技术及机器评估方法研究 0 。0 。0 ，的概率。 2 p ( d ，+ i d f + 2 0 rl q ，= s j , 五) ( 1 5 ) 我们定义l 。( i ，j ) 为：给定观测序列和模型，在时间t 为状态s 。，在时间t + l 为状态s 的概率： 苗( f ，) = p ( q ，= s ，g ，+ ，= s 1 0 ，五) 带入前向和后向变量，e 。( i ，j ) 可表示为 ( 1 4 ) 驰= 觜= 裹凝 ， 那么在时刻t 状态为s ，的概率r 1 。为 r 从而状态s t 的期望次数为： r f f r = l r 从状态s l 转移到s t 的期望次数为：毒( f ，) t = l ( 1 6 ) ( 1 7 ) ( 1 8 ) 从公式1 7 、1 8 ，我们可以给出h m m 各参数的期望值，然后修正后的模型参数又 可以用来计算状态的期望次数以及状态转移的期望次数，如此循环，直到收敛， 也就是我们所要求的最优参数。算法如图8 所示。 、j，l 芦j 、 州 i | l 第二章统计语言模型 图8 ：前向后向算法 从图8 我们可以看出，前向后向算法实际上是叫算法在 n m 隐参数估计上的运 用。 需要说明的一点是以上介绍的训练方法是在我们只有观测序列的条件下的 方法，如果我们的训练集包含状态序列，那么和n 元模型类似，只需要用最大 似然估计和平滑算法就可以计算出各参数的值。 2 3 最大熵模型 2 3 1 介绍 最大熵模型是自然语言处理中广泛使用和功能强大的一种统计模型，它可以 利用多种上下文信息特征对一些归类问题进行决策。下面我们先看一个例子来 大致了解最大熵的思想。 考虑这样一个天气预测问题：假设一个地区天气的种类有晴朗、多云、小雨、 汉语词与句子切分技术及机器评估方法研究 暴雨、小雪、暴雪六种，我们来预测下每种天气出现的概率。首先我们有如 下的概率归一限制： p ( 晴朗) + p ( 多云) + p ( 小雨) + p ( 暴雨) + p ( 小雪) + p ( 暴雪) = 1 但是满足上面限制的概率分布有无穷种，比如我们可以选择p ( 晴朗) = 1 ，这个分 布假设那个地区的天气永远是晴朗，或者我们选择p ( 晴朗) = p ( 多云) = 1 2 ，这个 分布假设那个地区的天气不是晴朗就是多云，而且两者的概率相同。这些假设 都满足上式的限制，但我们应该选择哪一种呢? 事实上，以上两种分布都是缺 乏根据的，因为我们没有更多的信息告诉我们那六种天气之间的频度关系，在 这种条件下，最客观( 均衡) 地估计应该是： p ( 晴朗) = p ( 多云) = p ( ，j 、雨) = p ( 暴雨) = p ( d 、雪) = p ( 暴雷) = 1 6 也就是六种天气具有相同的概率。不过很多时候我们并非对以往的经验一无所 知，比如我们如果知道一般会有一半的时间天气是晴朗和多云，那么又该如何 安排这六者的概率呢? 这时的限制条件有如下两个。 p ( 晴朗) + p ( 多云) + p ( d 、雨) + p ( 暴雨) + p ( 小雪) + p ( 暴雪) = 1 p ( 晴朗) + p ( 多云) = 1 1 2 在此条件下，我们可以选择的分布依然有无穷多个，而在未知其他信息的情况 下，比较明智的做法仍然是选择最均衡的估计： p ( 晴朗) = p ( 多云) = 1 1 4 p ( 小雨) = p ( 暴雨) = p ( d 、雪) = p ( 暴雪) = 1 8 也许我们从以往的经验里又得到了一条信息：多云和小雨出现的次数占1 3 ，那 么限制条件变为： p ( i t i g 朗) + p ( 多云，+ p ( d 、雨) + p ( 暴雨) + p ( 小雪) + p ( 暴雷) = 1 p ( 晴朗) + j 口( 多云) = 1 2 p ( 多云) + p ( 小雨) = 1 3 第二章统计语言模型 这时要选择个最均衡的分布就不那么容易了，我们面临两个问题：i ，什么样 才算是均衡的概率分布；2 ，给定均衡的标准后，如何在给定限制条件下得到这 个分布。这两个问题都可以用最大熵模型加以解决，而最大熵模型的本质思想 也就是在满足所有已知事件的基础上对未知事件作最客观均一地估计。 2 3 2 定义 自然语言处理的很多问题可以概括为如下形式：给定训练样本( x 。，y 。) ， ( x t ，y ：) ，( x 。，y 。) ，其中x 为上下文环境，y 为输出，预测在新的上下 文环境中最有可能的某种输出。在最大熵模型中，我们引入特征函数这个概念， 以获取和上下文相关的多种特征信息。 特征函数的一般形式为： 厂( 五力： 1 如果x 满足某一种上下文特征并且y 是某一? 输守 ( 1 9 ) u o t t t e m i s e 由此训练样本实际上可以看成一系列特征的集合，比如：( x 。，y 。) = ( f ，f ：f 。厶) ， ( x 。，yz ) = ( f t f 。f ， ) 由此我们可以直观地看出，只要我们知道每个 特征相对于其他特征的比重( 影响度) ，就可以对未出现的事件进行预测。比如 对于给定上下文x ，输出y 的概率为： e x p ( e ，( y ) ) p ( w ) 2 t 其中 ，为f f 所对应的权值，z ( x ) 为归一化参数 z ( x ) = e x p ( 2 , f , ( x ，y ” y ( 2 0 ) ( 2 1 ) 现在我们要考虑的问题就是如何根据训练集求得每一个特征函数所对应的 值，使其“在满足所有已知事件的基础上对未知事件作最客观均一地估计”。下 面我们首先介绍这个限制条件。 汉语词与句子切分技术及机器评估方法研究 2 3 2 1 限制条件 限制条件也就是上文所述的“满足所有已知事件”。在以特征函数为基础的 框架中，限制条件也就是特征函数的经验值应该和期望值相等，如下所示： p ( f ) = p ( ，) 特征函数的经验值可以表示如下 p ( 厂) = p ( x ，y ) f ( x ，y ) ( 2 2 ) ( 2 3 ) 在实际计算中，我们可以统计某一特征出现的总次数，然后除以全部特征出现 的总次数，就得到了这个特征的经验值。而特征的期望值表示如下： p ( 厂) = p ( x ，y ) f ( x ，y ) ，y 我们用下式来近似p ( x y ) p ( x ，y ) = p ( x ) p ( yix ) 那么特征的期望值可表不为： p ( ，) = p ( x ) p ( y ix ) f ( x ，j ，) j t y 综合2 2 、2 3 、2 6 式，我们得到最终需要满足的限制条件： p ( x ，y ) f ( x ，y ) = p ( x ) p ( y 1x ) f ( x ，y ) 2 3 2 2 最大熵法则 ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) 最大熵法则也就是我们要满足的均一化法则，即让我们的模型对于训练集中 的样本做到最客观的估计。熵表示的实际上是混乱程度，而熵最大也就是表明 混乱的程度最大，这时均一性也最强。假设x 为一离散随机变量，下面给出熵 第= 章统计语言模型 的定义： ( x ) = 一p ( x ) l o g p ( x ) ( 2 8 ) 其中p ( x ) 表示x 的概率分布。由于我们要求的是给定上下文环境，某种输出的 概率分布，这实际上是一个条件概率分布，在最大熵的基础上，我们给出条件 熵的定义： h ( y i 工) = p ( x = x ) h ( y l 一) = 一p ( x ) p ( y i x ) l o g p ( y i x ) ( 2 9 ) ro 在给定训练集的条件下，我们用x 的经验分布代替p ( x ) ，上式可改写为： h ( y i x ) 一p ( x ) p ( y i x ) l o g p ( y i 工) ( 3 0 ) j 而最大熵法则实际上就是使上式的值达到最大。这样我们所求的条件概率分布 就是在满足式2 7 的前提下使式3 0 的值达到最大的概率分布。 2 3 3 参数训练 在前面两小节的基础上，我们已经明确所求概率分布px ( yix ) 要满足的条件 即： 条件1 ：p ( x ，y ) f ( x ，y ) = p ( x ) p ( y ix ) f ( x ，y ) ，yx , y 条件2 ： 儿( y l x ) = a 佗m a x ( 一p ( 力p ( 川x ) l o g p ( y l 功) p ( y l x )o 这是一个条件极值问题，我们引入拉格朗日乘子 ，并定义拉格朗日函数为： a ( p ，旯) = ( p ) + 五，( p ( ；) 一p ( ，) ) i 那么条件1 和条件2 可以归并为下面的最优化问题 p 。( y = a r g m a x ( h ( p ) + 五( p ( z ) 一p ( ，) ) ) p o ，1 j ) f ( 3 1 ) ( 3 2 ) 汉语词与句子切分技术及机器评估方法研究 将公式2 3 、2 6 、3 0 带入公式3 l ，我们得到： a ( p ，五) = 一p ( x ) l o g ( z 。( x ) ) + 丑。p ( ，) fi ( 3 3 ) 下面我们考察一下式3 3 所示的优化值和x ，y 联合概率的经验值相对于p ( y ix ) 的对数期望之间的关系。首先给出p ( x ，y ) 相对于p ( y ix ) 的对数期望： l ( x ，y ) = p ( x ，y ) l o g ( p ( y ( 3 3 ) 我们可以发现l ( x ，y ) 和人( p ， ) 是相等的，推导如下： l ( x ，y ) = p ( x ，y ) l o g ( p ( y = p ( x ，y ) 【e a i z ( x ，y ) 一l o g ( z 。( z ) ) 2 善烈t 力莩五：扛卜莓烈五力l o g ( z a o ”( 3 4 ) = 3 - ip ( z ) -