《快速解码和最佳译码机器翻译》由会员分享，可在线阅读，更多相关《快速解码和最佳译码机器翻译（7页珍藏版）》请在金锄头文库上搜索。
1、快速解码和最佳译码机器翻译乌尔里希Germann迈克尔Jahr,凯文Knight信息科学学院计算机科学系南加州大学斯坦福大学4676年海军,1001套房斯坦福,CA 1001玛丽安德尔湾 CA 90292 jahrcs.sta nford.edu germa nn,骑士 ,marcu kyamada isi.edu文摘良好的解码算法的成功是至关重要的任何统计机器翻译系统。译码器的工作是找到最有可能 的翻译根据组以前学参数相结合(公式)。因为可能翻译的空间非常大，典型的解码算法只能够 检查的一部分，因此冒险错过良好的解决方案。在本文中,我们比较传统的基于堆栈的速度和 输出质量与两个新的解码器解码
2、算法:一种快速贪婪的解码器和缓慢但最佳译码器对解码为 一个整数规划优化问题1介绍统计太系统,翻译法语句子成英语(说)，分为三个部分:(1)语言模型(LM)分配一个概率P(e)任 何英语字符串,(2)翻译模型(TM)分配一个概率P(fe)任何一对英语和法语字符串，和(3)译码 器。解码器是一个前所未有的句子，并试图找到能最大化的P(ef),或者说最大化P(e)P(fe)。 布朗et al。(1993)介绍了一系列的TMs基于逐字替换和重新排序，但不包括解码算法。如果 源语言和目标语言局限于具有相同的词序(通过或通过选择合适的预处理)，那么可以应用线 性维特比算法(Tillmann。，1997)。
3、如果重新排序是有限的二叉树中的节点周围旋转,那么可 以由最优译码high-polynomial算法(吴,1996)。对于任意word-reordering,解码问题是np完 全(骑 士,1999)。一个明智的策略(布朗et al .,1995王Waibel,1997)是检查一个大的子集可能解码和选择。当 然，可以错过这样一个好翻译。如果译码器返回ebut存在一些e P(ef)P(ef),这被称为一个搜 索错误。小王和Waibel(1997)的话,很难知道一个搜索错误大白(只显示解码是次优的方法是 实际生产higherscoring。因此，虽然解码是一个明确的优化任务，每个问题实例有一个正确的
4、答案，很难迅速想出好的答案。本文报告的测量速度，搜索错误，翻译质量的一个传统的堆栈解 码器(内克,1969;布朗et al .,1995)和两个解码器。第一个是一个快速贪婪的解码器，第二个是 一个缓慢的最优译码器基于通用数学编程技术。2 IBM模型4在本文中，我们使用IBM模型4,它围绕着一个词对齐的概念在一对句子（参见图1）。一个字 对齐分配一个家（英语）字符串的位置，每一个法语单词。如果两个法语单词排列相同的英语单 词，然后，英语单词是说两个肥力。同样地，如果一个英语单词仍然unalignedto，那么生育零。 图1中的词对齐的简称是一个假设的随机过程的一个英语字符串被转换成法语字符串。有
5、 几集的决策。首先，每个英语单词都分配一个生育。这些作业都是随机的根据字符串表删除任何单词与生育能力为零，我们与生育两个重复的任何单词，等等。如果一 个词有生育能力大于零，我们称之为肥沃。如果其生育率是大于一，我们称之为非常肥沃。新的字符串中的每个英语单词后，我们可能会增加生育一个看不见的英语NULL元素概率 p（通常约为0.02）。NULL元素最终会产生“捏造”的法语单词。接下来，我们执行一个逐字替换的英语单词（包括零）法语单词，根据表中最后，我们交换法语单词。在交换模型4区分法语单词，头（最左边的法语单词产生特定的英语 单词）,nonheads（non-leftmost,生成只有非常肥沃的
6、英语单词），和NULL-generated。头。被分配一个法国的一个英语单词字符串位置基于位置分配给前面的英语单词。如果一个 英语单词翻译成法语位置j,然后法国头的话随机放置在法国k与失真probabilitywhere类” 是指自动确定为法语和英语单词类词汇项。这相对偏移k-j鼓励相邻的英语单词转化为相邻 法语单词。如果是不孕，那么来自，等。如果非常肥沃,j的平均位置的法语翻译Non-heads。如果英语单词的头e j放在法国地位，然后第一个non-head被放在法国k位置 根据另一个表（ j）接下来non-head放置在位置问概率NULL-generated。头和non-heads放置后,
7、NULL-generated的话有无数随机到剩下的空槽。 如果有NULL-generated单词，然后用概率选择任何安置计划这些随机决定，从e,导致不同的选择f和f的对齐e e。我们映射到一个特定的 a、f 对 与概率：x符号表示生育因素,翻译，头排列，non-head排列，null-fertility,和null-translation probabilities.1 吗3定义的问题如果我们观察一个新的句子f,那么一个最优译码器将搜索一个最大化的eP（e | f）P（e）P（f | e）。在这里,P（f | | e）是 P的总和（a、f | e）在所有可能的排列。因为这涉及大 量计算，总和我
8、们通常避免它，而不是寻找一个 e,双maximizesWe把语言模型P（e）是一 个平滑的英语语法模型。4基于堆栈的解码为每一个可能的下一个词，扩展h增加w,推动产生的假说压入堆栈。回到第二步（流行）。解码过程的一个关键区别语音识别（SR）和机器翻译(MT)是演讲总是产生同样的订单作为其转录。因此，在SR解码之间总是有一个简单的 从左到右对应输入和输出序列。相比之下，在太留给一一正确的关系很少持有甚至语言对法 语和英语一样相似。我们解决这个问题通过构建解决方案从左到右，但允许解码器使用其输 入任何命令。这种变化使得解码明显更复杂太;而不是提前知道输入的顺序，我们必须考虑所 有n !个印度输入句
9、子的排列。SR和解码之间的另一个重要区别是缺乏可靠的启发式方法在太使用启发式A *搜索估计的成本完成部分假设。好的启发式可以准确地比较不同部分的价值的假设，从而集中搜索最有前途的方向。从左到 右限制在SR可以使用一个简单而可靠的启发式的估计成本基于类的数量输入解码。部分原 因是缺乏从左到右的信件,太启发式更难以开发(王Waibel,1997)。没有启发式,一个典型的堆 栈解码器是无效的，因为短的假设将几乎总是比看起来更有吸引力，因为我们将单词添加到 一个假设,我们最终找到的概率增加越来越多的条款。正因为如此，再假设将被赶走的堆栈的 短的，即使它们在现实中更好的解码。幸运的是，通过使用多个栈，我
10、们可以消除这种影响。multistack解码器，我们使用不止一个堆栈迫使假设公平竞争。更具体地说，我们有一个堆栈 的每个子集输入单词。这样，假设只能如果有其他调整，更好，假设表示相同的输入的一部分。 不止一个堆栈，然而，如何multistack译码器在每次迭代选择假说扩展?我们解决这个问题通 过采取从每个栈一个假设，但是一个更好的解决方案是比较假设从不同的堆栈和扩展只有最 好的。我们描述的multistack解码器是密切的模型3解码器中描述专利(布朗et al .,1995)。假设我 们构建解决方案逐步通过应用操作。有四个操作：添加添加了一个新的英语单词，将一个法语单词。AddZfert添加了
11、两个新的英语单词。第一个生育零,而第二个是对齐到一个法语单词。将一个额外的法语单词扩展到最近的英语单词，增加其生育能力。AddNull对齐一个法语单词的英语NULL元素。AddZfert是迄今为止最昂贵的操作，我们必须考虑插入一个zero-fertility英语单词之前每个 每个对齐法语单词的翻译。英语词汇量大小为40000，比AddNull AddZfert贵400000倍！ 我们可以以两种方式降低AddZfert的成本。首先，我们可以只考虑某些英语单词作为zero-fertility候选人，即单词经常发生和高频率分配的可能性为零。第二，我们只能插入一个zero-fertility词如果它将
12、增加一个假设的 可能性。根据解码的定义问题,zero-fertility英语单词只能做一个解码更有可能通过增加P(e) 超过它减少仅考虑帮助zero-fertility插入,我们拯救自己AddZfert显著的开销在许多情况下操作,消除所有的可能性和减少其成本比AddNullo5贪婪的解码在过去的十年里，许多情况下NPcomplete问题已经被证明可以在合理使用贪婪的方法/多项 式时间(塞尔曼et al .,1992;Monasson et al .,1999)。而不是深入探测搜索空间，这些贪婪的方法通常开始随机,近似解，然后逐步改善,直到达到一个令人满意的解决方案。在许多情况下, 贪婪的方法迅
13、速产生令人惊讶的是良好的解决方案。我们推测这种贪婪的方法可能是有用的在太解码的上下文中。贪婪的解码器,我们描述开始 翻译过程从一个英语光泽的法语句子作为输入。光泽是由调整每一个法语单词的最可能的英 文翻译为例，在句子翻译法国好说定,il parle de美女victoire。”,贪婪的译码器最初假设的一 个很好的翻译“听到，那说话的一个美丽的胜种，因为最好的翻译“好”是“好”,“最好的翻译说定” 是“听到”，等等。相应的对齐这翻译是显示在图2中6的整数规划解码骑士(1999)把太解码货郎担问题寻找最佳的旅行(Garey和Johnson,1979)选择好词序解码 器输出类似于选择一个好的TSP旅
14、行。因为任何TSP问题可以转换为解码的问题实例，实 例模型4解码证明地长度的非完全多项式f。有趣的是考虑相反的方向是可以改变一个解码 问题实例到TSP实例？如果是这样的话，我们可以充分利用先前的研究有效的TSP算法。我 们也可以利用现有的软件包，获得复杂译码器几乎没有编程工作。很难连续解码转化为TSP,但广泛的组合优化问题(TSP)可以表达更多的线性整数规划的总 体框架。7实验和讨论在我们的实验中，我们使用一个测试集合的505句英语，均匀分布在整个长度6、& 10、15、20。我们评估所有解码器对(1)速度，搜索最优(2),(3)翻译的准确性。最 后两个因素可能并不总是一致，模型4是一个不完美
15、的翻译process-i.e模型。，没有保证数值 最优译码实际上是一个很好的翻译。我们发现有几个非常有用的解码器。只有通过IP解码器输出，例如，我们可以知道堆栈解码器 是返回最佳解决方案很多句子(见表1)。IP和堆栈解码器使我们快速定位错误的贪婪的解码 器,并实现扩展基本贪婪的搜索，可以找到更好的解决方案。(我们想出了第五节中讨论的贪婪 操作通过仔细分析错误日志的类型如表1所示)。表1中的结果也使我们能够优先考虑我们 的研究议程上的项目。由于大多数的翻译错误可以归因于我们使用的语言和翻译模型(见表 1中列光磁电式),很明显，显著改善翻译质量将来自更好的模型。结果在表2中，用解码器，使用三元模型
16、语言模型,表明我们的贪婪的解码算法是一个可行的 替代传统的堆栈解码算法。即使在贪婪的译码器使用一组optimized-forspeed的操作最多的 一个词是翻译，最多一次移动,或插入,3-word-long段swapped-which标记贪婪”的几个小孩 在表2翻译准确性的影响略。相比之下，翻译速度增加至少有一个秩序级的。根据感兴趣的应用程序，可以选择使用一个缓慢的解码器提供最优结果或一个快速、贪婪的译码器，它提供了好不,但是可以接受的结果。也可以运行 贪婪的译码器使用一个时间阈值,在算法的实例。当阈值设置为1秒/句子(表1)的标签，只是 略有影响性能。应答。这项工作是由DARPA-ITO格兰特n66001 - 00 - 1 - 9814。引用p 布朗,s .德拉饰面的饰面的诉德
