基于剪枝策略的短语机器翻译算法研究.pdf

基于剪枝策略的短语机器翻译算法研究 刘水 李生 赵铁军 张春越 王博 哈尔滨工业大学 语言语音教育部 微软重点实验室 哈尔滨 150001 E mail liushui cqzong 摘摘 要要 本文参照基于短语的机器翻译系统 moses 改进并实现了该系统的算法 剪枝策略将机器翻译系 统的代价控制在可接受的范围内 同时 剪枝策略也是影响翻译质量的重要因素之一 与 Moses 实现的 lazy 算法不同 本文将几种剪枝策略相融合实现了一种综合的剪枝策略 以 NIST02 作为开发集 NIST05 作为测试集 在相同参数和翻译模型下 Moses 系统的 bleu 为 23 89 本文系统为 24 09 以该系 统为基线 本文提出并实现了一种不划分边界路径的 cube pruning 算法 以较小的翻译质量的损失为代 价 使解码速度提高了 20 倍 该系统的 bleu 得分为 23 63 关键字关键字 机器翻译 立方体剪枝 束剪枝 柱状图剪枝 Research on Pruning Strategy in SMT Shui Liu Sheng Li Tiejun Zhao Chunyue Zhang Bo Wang School of Computer Science and Technology Harbin Institute of Technology Harbin 150001 China E mail xli cqzong Abstract Our system used phrase based translation model that is similar to moses with a variant on pruning strategy The pruning strategy in decoding algorithm discard hypothesis during the translating procedure to make the algorithm applicable which is an important factor that effect the quality of translations Comparing with moses we combine various pruning strategies to a comprehensive strategy We use nist02 as our tuning set and nist05 as development set within the same translation model and parameters tuned by moses our system achieve 24 01 in bleu and moses achieve 23 89 Based on this system to speed up the decoder we impliment the widely used pruning algorithm cube pruning with a no boundary method that makes the decoder 20 times faster than normal decoding mode which achieve 23 62 in bleu score Keywords SMT Cube Pruning Beam Search Histogram Pruning 1 引言引言 基于短语的机器翻译模型 1 4 可以将源语言端的局部上下文信息天然的加入到目标语 言的翻译过程中 同时 基于短语的翻译模型对于目标语言的调序很大程度上依赖于语言模 型 而语言模型随着语料规模的增大具有较好的一致性 5 因此 基于短语的机器翻译系 统在大规模语料上具有较好的翻译效果 相比于基于句法的机器翻译模型 6 9 短语信息的 抽取方法相对简单 在训练时间和运行效率方面具有较大的优势 本文参照目前比较成功的机器翻译系统 moses 10 12 实现了一个基于短语的机器翻 译系统 该系统将信道模型应用到机器翻译模型中 应用Viterbi 算法进行解码 13 在Viterbi 解码过程中 剪枝策略是影响系统性能和运行效率的主要原因之一 相比于 moses 本文 实现了一种综合的剪枝策略以确保该算法的解码质量 cube pruning 14 15 是广泛应用在 完全句法分析和机器翻译中的一种高效解码方法 为了提高系统的速度 本文实现了该算法 使系统速度得到大幅度的提升 2 基于短语的翻译模型基于短语的翻译模型 本文实现的系统基于信道噪声翻译模型 12 在该模型中对于某个源语言 F 将该源语 言翻译成某种目标语言 E 可以表示为式 1 1 在上式中 fI为源语言 F 的某种切分产生的短语序列 eI为该序列产生的目标语言序 列 P e 为语言模型得分 P f e 为翻译模型得分 wlength e 为词惩罚得分 rm e f 为 词汇调序模型得分 d e f 为扭曲度模型得分 2 1 基于短语的翻译模型中的短语模型基于短语的翻译模型中的短语模型 对于给定的短语对 f 和 e 翻译模型得分 P f e 被拆解成 5 项 如公式 2 2 上式中 f e 和 e f 为 2 个方向的翻译得分 lex f e 和 lex e f 为 2 个方向的词 汇化翻译得分 phrase penalty e f 为短语惩罚得分 2 2 基于短语的翻译模型中的调序模型基于短语的翻译模型中的调序模型 在本文的基于短语的机器翻译系统中 目标语言端的显示调序模型 主要依赖于词汇化 调序模型 rm e f 和扭曲度模型 distortion e f 扭曲度模型将源语言和目标语言之间的语 序差异用扭曲度表示 如式 3 3 上式中 si 为当前短语在源语言端的起始位置 ei 1 为当前短语前一个短语在源 语言端的结束位置 词汇调序模型 rm e f 反映了目标语言与源语言间的一种词汇调序关 系 该模型定义了 3 种语言与目标语言之间的相对关系 一致顺序 monotone 交换顺序 swap 和非连续顺序 discontinuous 当前短语与前一个短语满足 ei 1 si 1 时 则当前短语的方向 orientation 为一致顺序 monotone 当前短语与前一个短语满足 si 1 ei 1 时 则当前短语的方向为交换顺序 swap 当 前短语不 满足上 述 2 种位置关 系时 则当 前短语的 方向为 非连续顺序 discontinuous 词汇化短语及其方向在某些情况下会对临近短语方向产生的影响 因此 该模型定义了 2 个方向的调序模型 令 oi 表示当前短语的方向 ei fi 表示当前的翻译短语对 ei 1 fi 1 为前一个翻译短语对 则当前短语的词汇化调序权值满足式 4 4 其中 P oi ei 1 fi 1 和 b oi为前一个翻译短语对与当前短语方向产生的条件统计概 率及其权值 P oi ei fi 和 p oi为当前翻译短语对与当前方向产生的条件统计概率及其权 值 3 基于短语的翻译模型中的剪枝算法基于短语的翻译模型中的剪枝算法 本文算法的可以看做一个 Viterbi 的解码过程 解码器从覆盖最少词数的翻译开始 逐 渐增加翻译的长度 直至翻译覆盖所有源语言词 与多数基于 Viterbi 的序列标注问题不同 在机器翻译算法的寻优过程中 无法产生常数或者多项式的候选最优路径数 对于一个基于 3 元语言模型的解码器来说 在解码过程中产生的候选路径 最优翻译 数的上限 2nf Ve 2nf 其中 nf 为源语中的词汇数目 Ve 为目标语言的词汇数 剪枝算法的引入使解码器在保 证一定翻译质量的同时 在多项式时间内完成解码 3 1 基于扭曲度的剪枝算法基于扭曲度的剪枝算法 扭曲度是反映目标语言和源语言的相对调序关系的模型 本文的短语模型可以通过该模 型根据源语言进行隐式的调序 同时 在解码过程中 也会根据扭曲度进行强制的约束 以使其二者的调序在某个范围内 在 moses 中 应用以下扭曲度条件 对目标语言和源语言的相对调序关系进行限制 当目标语言和源语言不满足以下条件之一时 新的搜索路径才将被扩展 ei 1 si 1 1 ui 1 si ei 1 si 1 1 ei 1 si 1 1 ui 1 si ei 1 si 1 1 ei ei 1 si 1 MaxDistortion 1 si ei 1 si 1 1 ei ui 1 MaxDistortion 1 其中 ui 1 为前一个短语中在源语言端第一个未被覆盖的词 MaxDistortion 为最大的 扭曲度限制 3 2 普通解码中的剪枝算法普通解码中的剪枝算法 在普通解码的 Viterbi 过程中 若算法仅关注最优路径 获得最高得分的翻译 的相对位 置 在此解码过程中可以采用重合并 recombine 的方法 丢弃一些不影响最优路径相对 位置的中间路径 并可以证明这样的剪枝不会影响最终最优路径的相对位置 若 2 个翻译 hypotheses 路径 满足下述条件时 将进行重合并 recombine 剪枝 丢 弃翻译得分较低的翻译路径 覆盖相同的源语言词 具有相同最后 n 1 个翻译词 最后一个短语在源语言端具有相同开始位置和结束位置 其中 n 为翻译模型中语言模型的 ngram 元数 单纯基于重合并的剪枝算法可以在一定程度上减少解码算法在寻优过程中的代价 但是 并不能将解码的时间复杂度降低至多项式时间 为了将解码代价降低至多项式时间 在普通 解码模式下通常采用束搜索 beam search 剪枝技术和柱状图剪枝技术 histogram pruning 以 达到这个目的 与重合并剪枝技术不同 这 2 种剪枝技术都存在将潜在的最优路径丢弃的危 险 柱状图剪枝技术 只保存当前最优的 N 条路径 N 为柱状图剪枝的阀值 丢弃在这个范 围以外的搜索路径 由此 可以证明该剪枝策略将解码算法的代价控制在多项式间内 束搜索剪枝是一种在许多寻优技术中广泛应用的剪枝技术 该剪枝技术将目前路径的最 高的得分除以某个大于 1 的阀值 所有在此阀值以下的路径都将被丢弃 由于当前最高的得 分未必是最终的最优得分 束搜索剪枝是一种与搜索路径顺序相关的剪枝技术 考虑到以上剪枝策略在解码过程中可能同时丢弃同一条翻译路径 为了避免这种重复剪 枝的情况 同时实现以上算法的逻辑 将以上 3 种策略融合成一种混合策略 如图 1 图 1 综合剪枝策略 其中 以上算法中 s为存储当前翻译路径h的数据结构 HW为柱状图剪枝的阀值 BW为束剪枝的阀值 函数 empty s 当 s 中没有记录任何翻译路径时返回 true 否则返回 false 函数 insert h s 将翻译路径 h 存储到 s 中 函数 f h 返回路径 h 的翻译得分 函数 max s 返回在 s 中得分最高的翻译路径 h 函数 min s 返回在 s 中翻译路径的最低得分 函数 eraseMin s 将删除 s 中得分最低的翻译路径 函数 eraseEqual h s 函数 size s 返回 s 存储的翻译路径数 函数 eq h s 当 s 中存在符合与 h 进行重合并条件的翻译路径时返回 true 否则返 回 false 函数 be h s 当 s 中存在符合与 h 做重合并条件的翻译路径并且该路径的得分低于 h 时 返回 true 否则返回 false 3 3 cube pruning 剪枝解码算法剪枝解码算法 立方体剪枝解码 cube pruning 是在完全句法分析和机器翻译中得到广泛应用的一 种解码方法 该算法基于最优子结构的单调性 monotonicity 假设 而由于语言模型和 2 个 调序模型 的存在使产生新翻译路径的过程无法 满足这个假设 因此 立方体剪枝的解码代价的提高是建立在损失一定翻译质量的基础 上的 在本文涉及立方体剪枝解码过程中 一个新翻译路径的产生过程可以认为是一个推导过 程 如式 5 5 其中 M 为机器翻译模型 hi为覆盖 i 个源语言词的翻译路径 pj 为覆盖 j 个连续源 语言词的短语 且 hi和 pj 满足前文中扭曲度剪枝条件 当解码过程中 在某个翻译模型 M 下 所有根据式 6 的推导过程产生的翻译路径都满 足以下关系 如下式 6 时 则称基于该翻译模型 M 的算法是基于最优子结构的单调翻 译算法 6 其中 f M R 为基于翻译模型 M 的翻译路径得分函数 由于下文对于算法的 描述 都是基于前文的翻译模型 以下将其简写为 f 在立方体剪枝中 解码器总是扩展当前最好翻译路径的下一个最好推导 解码器将当前 产生的最好路径加入到一个根据分数排序的堆 s 中 其余翻译路径如果在 s 的大小达到束 剪枝的阀值时 仍未被加入到 s 中 将被解码器丢弃 本文将这些被丢弃的翻译路径称为 翻译边界路径 该剪枝策略实际上与束剪枝面临相同的问题 当前的局部最优翻译路径未必是全局中最 好的 HW 柱状图剪枝的阀值 个之一 在被丢弃的边界翻译路径中 可能存在一些比较好 的翻译路径 基于这个考虑 本文提出无边界的立方体剪枝算法 该解码算法在解码过程 中 并不对边界翻译路径进行单独划分 所有产生的翻译路径都保存在同一个基于分数排序 的堆 s 中 基于以上单调假设关系 令 Hi为覆盖相同 i 个源语言词的翻译路径集合 Pj为覆盖 相 同j个 相 同 连 续 源 语 言 词 的 短 语 集 合 且 存 在 集 合 jj n ii m ji nm Mj n i m ji nm ji PpHhhphhH 定 义1 翻 译 路 径 jiji nm Hh 的 后 续 翻 译 路 径 集 合 为 S S ji nm ji nm j n j n i m i m ji nm ji nm hhpfpfhfhfhh 定 义2 翻 译 路 径 jiji nm Hh 的 交 叉 翻 译 路 径 集 合 为 0 j n j n i m i m ji nm ji nm pfpfhfhfhhC 定 义3 翻 译 路 径 jiji nm Hh 的 后 续 相 邻 路 径 集 合 为 ji nm ji nm ji yx ji nm ji yx ji nm ji yx ji nm ji nm hShChhhhShfhhN 图 2 为本文提出的无边界路径划分的立方体解码算法 函数 GetNextBest h 返回翻译 路径 h 的临近翻译路径集合 在此算法过程中 当前翻译搜索路径的扩展主要依赖于与当 前路径的后续相邻翻译路径集合 如定义 3 和一致性假设 由于一致性假设实质上只是定义 了一种偏序关系 且如前讨论 由于模型的限制新的翻译路径的产生过程实际上不满足一致 性假设 因此 在偏序关系关系实质上并不产生翻译 路径的相对顺序 而是作为扩展翻译 路径的前瞻性的决策 在产生新的翻译路径后 仅依据新产生的翻译路径得分对其进行排序 图 2 无边界剪枝方法 4 实验及实验结果讨论实验及实验结果讨论 本文使用开源软件 mose 在 FBIS 上进行词对齐及短语的抽取 选取 NIST 02 作为开 发集 使用 moses 在该开发集上进行 MERT 训练 选取 NIST 05 作为测试集 应用以上 训练过程获得的短语模型和模型参数 在 moses 和本文系统上分别进行解码 实验结果如表 1 其中 system 为与 moses 相同解码设置下的普通解码 system2 为 与 moses 相同解码设置下的立方体解码解码 从中可出 由于剪枝策略不同和在系统实现 上的差异 本文的基线解码虽然在翻译质量 翻译得分评价 上略优于 moses 系统 在普通 解码状态下速度远低于 moses 加入立方体剪枝后的解码器以较小的翻译质量的损失 换取 了系统速度的大幅度提升 表一 表一 实验结果实验结果 system bleu nist time cost moses 23 89 7 7171 1623s system1 24 09 7 7534 11452s system2 23 62 7 7080 480s 参考文献参考文献 P Koehn F J Och et al Statical Phrase based Translation In Proceeding of HLT NAACL 2003 Marcu D Wang A Phrase Based joint Probability Model for Statistical Machine Translation In Proceedings of 2002 EMNLP F J Och H Ney The Alignment Template Approach to Statistical Machine Translation Computational Linguistics 2004 30 4 417 449 D Xiong Q liu et al Maximum EntropyBased Phrase Reordering Model for Statistical Machine Translation In Proceeding of the ACL 2006 Sydney Australia S F Chen J Goodman An Empirical Study of Smoothing Techniques for Language Modeling In Proceedings of the 34th annual meeting on Association for Computational Linguistics 1996 310 318 K Yamada K Knight A Syntex based Statistical Translation Model In Proceeding of the ACL 2001 L Huang D Chiang Forest Rescoring Faster Decoding with Integrated Language Models In Proceeding of the ACL 2007 Prague Czech Republic D Xiong Q Liu Forest Rescoring Faster Decoding with Integrated Language Models In Proceeding of the ACL 2007 Prague Czech Republic D Marcu Wei Wang A Echihabi K Knight Forest Rescoring Faster Decoding with Integrated Language Models In Proceeding of the ACL 2007 Prague Czech Republic P Koehn Hieu Hoang Alexandra Birch et Moses Ope