【毕业学位论文】（Word原稿）汉语词与句子切分技术及机器评估方法研究-模式识别与智能系统

分类号 密级 编号 中国科学院研究生院 硕士学位论文 汉语词与句子切分技术及机器翻译评估方法研究 指导教师 宗成庆 研究员 博士 中国科学院自动 化研究所 申请学位级别 工学硕士 学科专业名称 模式识别与智能系统 论文提交日期 20 年 6 月 论文答辩日期 20 年 6 月 培养单位 中国科学院自动化研究所 学位授予单位 中国科学院研究生院 答辩委员会主席 in of 独 创性声明 本人声明所成交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确地说明并表示了谢意。 签名： _导师签名： _ 日 期： _ 关于论文使用授权的说明 本人完全了解中国科学院自动化研究所有关保留、使用学位论文的规定，即：中国科学院自动化研究所有权保留送交论文的复印件，允许论文被查阅和借阅；可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。 （保密的论文在解密后应遵守此规定） 签名： _导师签名： _ 日 期： _ I 摘要 本论文以统计模型为基础， 在参考了大量前人工作的基础上， 对 汉语词 法 分析、 口语 句子切分和机器翻译评估 进行了较为深入的探讨和研究 。 汉语词法分析是大部分中文处理的第一步，其重要性不言 而喻；句子切分是语音翻译中连接语音识别和文本翻译的桥梁，无论语音识别和文本翻译单独的效果有多么好，这座桥没搭好，综合的性能依然无法提高；机器翻译的自动评估是构建机器翻译系统中很重要的辅助工作，其可以加速翻译系统的开发速度，缩短其开发周期。 简 言之，这三方面同属于自然语言处理 的 基础的 研究 领域， 其效果直接 影响 到高层应用 的水平 。 在 词法分析 上 ，我们利用隐马尔可夫模型 （ 提出了一种融和了分词、词性标注和命名实体识别的一体化词法分析 方法。 最初我们用 基于类别的其优点是对词的覆盖面广，系统开销小；缺点是不能精 确地预测词的出现概率。为了 提升模型的准确率，我们引入基于词汇的 将两者有机地结合， 并 用一个“词到字”的概率平滑方法对基于词的 行平滑。 实验结果显示，我们的混合模型由于综合考虑到了 字、 词、词性以及命名实体的知识，在切分的准确率和召回率上都明显优于单纯基于类别或者基于词的 外在分词系统的实现上，我们借助对通 用 分词系统 整体框架和各功能模块的介绍 ，讨论了如何有效地存储和加载数据等 一些 技术 细节 问题。 在口语句子切分上， 我们提出 了 基于双向 种算法由于 通过最大熵有机地将正、逆向 N 元切分结合起来，综合考虑到了切分点左、右的上下文，从而得到了很好的切分效果。我们 在 中、英文语料 上 训练我们的模型并作测试，结果显示 其 在性能上明显优于基本的正向 此基础上，我们分析 并对比 了 各模型的 切分结果，从而验证了我们当初 对于模型的预计： 其 一方面 保存 了 正向 N 元算法 的 正确切分， 一方面 用逆向 法 的错误切分。 在 机器翻译 的 自动评估 上，我们 首先 介绍了两种常用的基于参考译文的评估算法 然后 给出 了一种基于 N 元模型的句子流畅度评估方法 种 方法不需要 借助 任何参考译文，它通过区别地对待句子中不同的词的转移概率，达到了很好的评估效果。 综上所述 ， 本文针对汉语词法分析、口语句子切分和机器翻译评估提出了以统计模型为基础的创新方法，它们 不仅仅在科学方法上有重要的参考价值， 对于 实际 应用 中 也有重要 意义 。 of is is in a of of a MT In to to as so we a is a So as to we MM it At we a “ of t in by E, in of on of we in We in of In a on a V is to of of in We of by we it on of on by of In T we on on we 3, t by of in In T We in be to LP 录第一章 绪言 . 1 第二章 统计语言模型 . 3 元模型 . 3 元模型定义 . 3 . 4 马尔可夫模型 . 8 义 . 8 关联的三个问题 . 9 大熵模型 . 13 绍 . 13 义 . 15 数训练 . 17 结 . 20 第三章 基于隐马尔可夫模型的一体化中文分词方法 . 21 关工作 . 21 于类别的隐马尔可夫分词框架 . 23 的定义 . 24 于类别的隐马尔可夫模型 . 24 . 26 于类别的隐马尔可夫 模型的小结 . 29 于基于类别的隐马尔可夫模型的改进 . 29 于类别和基于词的隐马尔可夫模型的合并 . 30 词到字”的平滑方法 . 31 验 . 32 练和测试语料 . 32 模型的测试结果 . 32 误分析 . 34 用分词系统 . 35 统框架 . 35 数据装载以及知识管理 . 36 切分模块 . 40 结 . 45 第四章 基于双向 N 元模型和最大熵模型的句子切分 . 46 关工作 . 47 大熵平衡的双向 . 50 向 . 50 向 . 51 向 . 52 于最大熵模型的切分算法 . 53 大熵平衡的双向 . 54 V 验 . 56 练和测试语料 . 56 验结果 . 56 果分析 . 58 结 . 59 第五章 机器翻译自动评估方法研究 . 60 关工作 . 60 于参考译文的评估方法 . 62 法 . 62 法 . 63 进的 . 64 于统计的句子流畅度评估方法 . 65 于 . 65 验 . 68 结 . 72 第六章 结论 . 73 参考文献 . 75 附录 1： 本论文的研究工作得到如下项目资助 . 81 附录 2：攻读硕士学位期间发表的论文 . 81 致谢 . 82 一章 绪言 - 1 - 第一章 绪 言 近十几年来，随着 计算机 硬件设备的飞速发展，其单位 存储和计算 成本大幅度降低， 使一些基于 大规模 搜索 和迭代 的 复杂 算法 能够在 而随着行业信息化的普及 和网络资源的迅猛膨胀 ，可 用语料资源也大为丰富， 这一切给基于大规模语料库的统计自然语言处理提供了所需的硬件 和软件 环境 。 统计自然语言处理以数学模型和大规模语料库为基础，其核心思想是建立数学模型以表述某一种语言现象，然后在大规模语料库中对那种模型进行训练，使其满足 已经获知的经验知识，然后用训练好的模型对于未知的现象进行预测。几 乎所有基于统计的方法都可以归结到上述的框架中去。相比传统的基于规则的自然语言处理，统计方法有如下好处。 第一， 它 不依赖于人主观的先验知识 ，这 也是本文认为统计方法最重要的优点 。大规模语料库实际上和规则一样，都是一种知识的 表征形式。不同的是语料库相比规则而言，有更强的独立性和客观性。大家知道，规则往往是针对某一特定的应用，由某方面的专家按照一定的形式所书写的指导原则，它是专家在自己的经验基础上对语言现象的一种总结，具有很强的主观性 。 往往不同的专家所书写的规则会有不同，甚至同一位专家在不同时候所写规则也会有出入 ，而随着规则的不断增加，新 旧规则 之间会产生矛盾，当规则的数目达到一定 程度 以后往往就不可能再增加新的规则了 。而语料库很简单，任何一篇电子文档都可以成为一个小的语料库，即使对于那些经过人工处理后的熟语料，由于大家是在一定规范 地约束下进行的， 那些规范相对而言都是比较简单和机械的规范，所以人的主观影响会小得多 ，即使在某些个别的词或句上出现矛盾，也不会对整体造成很大影响。 第二， 统计方法相比基于规则的方法有更强的鲁棒性。规则的方法是离散的，一条规则只能总结有限数目的语言现象；而统计模型是连续的，它可以对全部的现象进行描述。 规则是人对于经验知识的一种抽象，这种抽象是零散的，它并不保证所有的规则的总和可以描述全部的语言现象，所以每遇到一个不能处理的实例，我们必须增加新的规则以满足需求。而统计模型所依赖的语料库虽然也是离散的，语料库中包含的现象 也只是全部现象的一个真子汉语词与句子切分技术及机器评估方法研究 - 2 - 集，但由于我们是用严密的数学模型来对现象进行的抽象和归纳，它就可以保证训练出的模型适用于所有的实例，从而保证了强的鲁棒性。当然， 不同的统计模型对现象描述的准确程度是不一样 的 。 第三， 统计方法 将知识和算法分离 。 前文已提过，规则往往是由某方面的专家针对某一特定的应用所书写的指导原则，而 同一个语料库可以为多种算法、多种应用服务 ，它是很独立的知识库。这样语料库的建立和完善可以和算法的设计并行， 不仅节省了人力物力，也给一些标准化测试提供了基础。 另外这项优点给基于统计方法的系统的维护和更新带来了很大的 方便。随着应用的扩展，我们往往要考虑到新的语言现象，这时基于统计方法的系统只需要用更大的语料库重新训练一下模型就可以了，而基于规则的方法则需要增加大量的规则，而如上文以前提过的，这并非一件容易的事情。 正是由于 这些 优点，统计方法在近十年来得到了 飞速发展， 它 逐步取代传统基于规则的方法，成为自然语言处理领域的主流技术。 在中文处理方面，统计方法已经有很多成功的应用，如词性标注、音字转化及拼音输入等，但由于汉语本身的复杂性和灵活性，有很多问题依然尚待解决。本文试图以统计模型为基础，研究汉语自动分词、分句及机器翻译 自动评估的解决方法。分词是大部分中文处理系统的第一步，其重要性不言而喻；句子切分是语音翻译中连接语音识别和文本翻译的桥梁；而机器翻译的自动评估可以提高一个 机器 翻译系统的开发速度和节约其成本。 简言之， 这三类问题同属于中文信息处理领域的基础 研究 课题， 它 们的效果直接关系到其他 高 层应用， 所以 我们的研究 不仅仅在科学方法上有重要的参考价值， 对于 实际 应用 也有重要意义 。 后面的章节是这样安排的：第二章介绍三种常用的统计模型，这是本文 所提出的 方法的理论基础；第三章介绍基于隐马尔可夫模型的一体化汉语分词方法；第四章介绍 基于 N 元模型和最大熵模型的句子切分方法；第五章介绍基于 N 元模型的句子流畅度评估方法；第六章对全文进行总结。 第 二 章 统计语言模型 - 3 - 第二章 统计语言模型 本论文 的所有工作均是基于统计方法，因此在本章里，我们将介绍一些常用的统计模型。 其构成了我们的方法的理论支撑。 统计模型是一种抽象的数学模型，用来对事物进行一种近似的描述，它首先假设某类现象满足一种模型，然后用已知的现象实例对模型进行训练，以得到模型的相关参数，然后用这个训练过的模型来预测未知的现象。对于自然语言处理而言，最常用的有 马尔可夫模型、最大熵模型等。 元模型 元模型定义 的定义如下。 图 1： 如果我们假设 语言也满足马尔可夫性，那么某一个词在某个句子中的出现概率就可以用公式 1 进行计算 ，进而一个句子的概率可以计算为： ).|(.).|(.)|()().()(111112121 (2) 一般 型越精确，但 所用参数和 所需要的训练集也越大 （如果训练集不够大将导致严重的数据稀疏问题） 。假设词汇量为 100K（实用中文 系统的词汇量），下表给出了不同的 数形式 以及所用的参数数目。 假设序列 阶马尔可夫链，那么某一元素 现的概率只和其前面 元素相关，即： ).|().|( 1111 （ 1） 汉语词与句子切分技术及机器评估方法研究 - 4 - 表 1： 模型 参数 参数个数 0p(w)=1/|V| 1 1p(w) 1p(wi|1p(wi|1p(1实际运用中，考虑到训练所需的语料 规模 ， N 一般取 3， 也就是所谓的 数 估计 大似然估计 虽然我们已经介绍了 要真正使用它，还需要进行参数 估计 这一步 ，也就是将表 1 中的那些参数计算出来。 以 例，用最大似然估计计算参数的公式为： ),(),()|(121212 u n t u n ) 其中 wi,示 wi, 最大似然估计可以计算出训练语料中出现过的 数，但如果我们碰到没有出现过的 N 元组怎么办 呢？最简单的办法是认为那些参数为 0，但这样做会导致系统的适应能力很低，一旦碰到未出现过的 N 元组，系统就基本上处理不了。 为了解决 这一问题， 是 给 每个 论其有无在训练语料中出现，都加上 1。 如下图所示。 第 二 章 统计语言模型 - 5 - 图 2： 则 则可以粗略解决“ 0 次数”问题，但它将所有未出现的 N 元组都赋予出现次数 1是不符合语言模型的实际情况的，因为很多词的组合（ 实 根 本就不存在。 基础上又做了一点改进， 他给所有 N 元组加上的不是整数 1，而是一个待确定的小数 。如下图所示。 图 3： 则 是一个小于 1 的小数，可以 在 通过如下方式训练得到：将训练语料分为 2 部分 ，首先用 A 对 后对 节 直到 1，使得对 后用 节 直到 2； 最终的值为 1和 2的算术平均值。 数平滑 则仅仅是对“ 0 次数”问题的一个粗糙的解决方式，它 们都无法针对不同的 N 元组 做出 不同的预 测，我们需要更为细致的参数平滑算法来帮助我们进行参数估计。 从机理上划分，目前的参数平滑算法可以分为折扣法（ 回退法（ 插值法（ 在这里我们只介绍其中的回退法。 回退法 是最常用的一种平滑算法，它的基本思想是当高阶参数不存在时，回w n)=,w n)+1/(C+B) C: 训练集中 N 元组出现的总 次数 B: N 元参数的总个数 w n)=,w n)+(C+ C: 训练集中 N 元组出现的总次数 B: N 元参数的总个数 :待确定的小数 汉语词与句子切分技术及机器评估方法研究 - 6 - 退到低阶参数，当然， 为了保证 每一阶参数的总和要为 1，对于那些存在的参数要进行一些减弱 。 我们以 这种平滑方法被认为是对于 N 元模型最有效的平 滑算法之一，也是本文所实现的系统中所实用的方法 。 4。 从图 4 中我们可以看出， 对于已经存在的 N 元组， 出不同的消减 ，对于不存在的 根据一定的比例回退到低阶参数，而低阶参数的计算和高阶类似，可以回退到更低阶。值得注意的是 于一元参数的计算方法，它没有使用语料中的绝对统计数目，而是用和它相邻的不同的一元组的数 目，这样可以避免如下的错误回退发生： 假设词组 是对于 B 而言，它只出现在 A 的后面，也就是 p(B|A)=1，这样如果统计 B 的出现频度，是很高的，而当我们计算某个 p(B|C)时，显然语料中找不到 而回退到 p(B)，而 p(B)的值是很大的，这样就形成了一种误导。而如果我们用 么 这一个词，个数为 1，当我们再回退到 不会出现很高的概率，从而避免了这种误导。 第 二 章 统计语言模型 - 7 - 图 4： |()()( )()()|( 1 21 111111 o u n o u n o u n )()(11 N c o u n )()()()(111331122111111其中： 32100)(321 2113432321212433221x 的 n 元组的个数 |)(:|)( 11 1 u n i |)(:|)( 11 1 u n i |)(:|)( 11 1 u n i 1|)(:|)( 1o u n - 8 - 马尔可夫模型 义 隐马尔可夫模型（ 自然语言处理和语音识别中又一非常常用的数学模型， 它于 20 世纪 60 年代末被 出，在 70 年代处被后 慢慢 流行开来并 被用于 自然语言处理 的一些领域 中。 它假设在观测现象的背后有一系列隐藏的状态，观测序列是 由 这些隐藏状态序列所生成 ，其定义如下图所示。 图 5：隐马尔可夫模型 和隐马尔可夫模型相伴随的一般有三项假设：马尔可夫假设、不动性假设和输出独立性假设 。 马尔可夫假设是 假设状态序列满足一阶马尔可夫性，即某一状态序列出现的概率只和它前面一个状态相关 ，这点和二元模型是一致的 ； 不动性是状态的转移和时间 无关；独立性是某一观测现象只和当前状态相关。 如果我们 用 示观测序列， 示状态序列， 这三项假设可以用下图表示。 图 6： 隐 马尔可夫假设 隐马尔可夫模型 可表示为 一个五元组： ( x , o, A, B, ) 其中： x = ., 隐 状态的有限集合 o = .,观 测现象 的有限集合 A = p( = 转移概率 B = p( 输出概率 = i， i = p( 初始状态分布 马尔可夫假设 ： p( 1) = p(不动性假设 ： p(|= p(|对任意 i,j 成立 输出独立性假设 ： p(., .,= p( 第 二 章 统计语言模型 - 9 - 关联的三个问题 和 给出 了定义之后，我们自然想到如何去训练和使用它。一般而言，和隐马尔可夫模型相关的有三个经典问题：评估问题，解码问题和学习问题。 以下我们将分别介绍。 估 问题 （前 向 算法） 评估问题 是给定模型 ，求 某一观 测 序列 ., 为了简化这个问题，我们首先假设观测 序列 是由状态 Q= 这个假设下，观测序列的概率为： )(.)()(),|(),|( 21 1 21 （ 4） 而给定 ，状态序列 Q= 率为： TT 32211 .)|.()|( 21 （ 5） 由于我们并不知道观测序列是由哪一种状态序列所生成，我们必须考虑所有的情况，也就是： )(.)()()|(),|()|,()|(1122111, . l l l （ 6） 公式 6 给出了计算观测序列的方法，但从公式中我们可以看出，其时间复杂度很高，假设状态空间长度为 N， 总的时间复杂度将为： 2 指数级复杂度的算法在实际应用中一般是无法实现的。 为此我们引入动态规划来缩减计算量，由于 的状态的转移概率只和其前一状态相关，这给我们的计算带来了很大 好处。 我们定义前向变量 给定模型 ，在 t 时刻状态为 测序 用公式表述如下： 汉语词与句子切分技术及机器评估方法研究 - 10 - )|,.( 1 （ 7） 基于 可以计算为： )(1 （ 8） 这是一个迭代公式，其初始值为： )( 11 Ob （ 9） 而我们最终所要得到的结果为： i ),.()|( 21 （ 10） 而 对于公式 10的迭代计算，在每一个观测值我们要考虑所有 于每个状态我们需要考虑其前面 N 个状态，那么总的时间复杂度为 N*N*T=，大大小于先前的 T，这个复杂度是可以实现的。 码 问题（ 韦特比 算法） 解码问题就是给定，模型和观测序列，找到最可能的状态序列。这个问题 也是 大多数 实际 应 用 中 的 运作 方式。比如对于词性标注，我们把词看作观测序列，词性看作状态序列，标注的过程就是找到最可能的状态序列的过程。对于解码问题的精确数学描述如下： )|.,.(m 121. . （ 11） 事实上解码问题和评估问题很相似，评估是计算所有可能 的 状态序列 产生 的观测序列的 概率的总和，而解码则是从这些状态序列中挑 出 最有可能的，也就是 概率最大的。 和评估问题 类似，如果我们遍历所有可能的状态序列，计算的时间复杂度会很高，我们同样采用动态规划来解决解码问题。 我们定义 章 统计语言模型 - 11 - 状态序列） ： )|.,.(m 121. . 12 （ 12） 这样在 t+1时刻到达状态 )(m a x 11 （ 13） 对于每个状态 ，我们通过公式 13选择其最优的前一状态并记录下来 ，一直到最末的状态 T，然后遍历 择最优的一个，最后通过各状态的前驱得到完整的最优路径，也就是状态序列。这个过程可以用下图表示。 图 7： 韦特比 搜索 习问题（前向后向算法） 学习问题也就是训练问题，即给定观测序列，找到最优的 ，使 观测序列的概率也就是 P(O| )最大。 这个问题是三个问题中最难的一个，一般我们用前向后向算法（ 计上的应用 ）来预测 。 包含三方面，初始概率分布、状态间转移概率、和状态到观测值的生成概率。我们首先来考虑如何计算这三种参数的期望值。 首先我们引入后向变量 给定 ，部分观测序列初始化： )( 11 Ob 1=1 0)带入 35式，我们得到： 第 二 章 统计语言模型 - 19 - )|(),(ex p ()|()(1),(),()()()(1),(),()()(, x （ 36） 由上式可以看出，只要我们能找到 使 A( | )0，那么新的模型相对于旧的就是一个改进，为了让模型尽快收敛，我们寻找使 A( | )最大的 。 注意到如果将目前的 A( | )以 i 为变量微分并令之为 0，我们得到的等式中包含 1 2, , n，这样我们仍无法简单地计算出 i。如果我们能把 的其他 换出来，就可以比较方便的对 A( | )进行微分。为此我们将 36 式改写为： yx x i ii # ),( ),(),(ex p ()|()(1),(),()|( （ 37） 其中 f#(x,y)为： i i ,(),(# （ 38） 也就是 (x,y)所满足的特征函数的个数，由于： 1),( ),(# ii (),(# 作一个随机变量 的分布 ， 而 么应用E(x)=(x)，我们得到： )|(),(),()|()(1),(),()|(,),(# # x y （ 39） 现在我们将 B( | )微分，