基于对偶分解的词语对齐搜索算法

词语对齐旨在计算平行文本中词语之间的对应关系,对机器翻译、双语词典构造等多项自然语言处理任务都具有重要的影响。虽然近年来词语对齐在建模和训练算法方面取得了显著的进展,但搜索算法往往都采用简单的贪心策略,面临着搜索错误较大的问题。该文提出了一种基于对偶分解的词语对齐搜索算法,将复杂问题分解为两个相对简单的子问题,迭代求解直至收敛于最优解。由于对偶分解能够保证求解的收敛性和最优性,该文提出的搜索算法在2005年度863计划词语对齐评测数据集上显著超过GIZA++和判别式词语对齐系统,对齐错误率分别降低4.2%和1.1%。

Search for Discriminative Word Alignment via Dual Decomposition

Word alignment aims to determine the corresponding relationship between the words in parallel texts. It has an important influence on machine translation, bilingual dictionary construction and many other natural language processing tasks. Although in recent years the word alignment has made significant progress in modeling and training algorithm, its search algorithm often uses greedy strategies and faces the problem of large search errors. This paper proposed a word alignment search algorithm based on dual decomposition, making a complex problem into two relatively simple sub-problems and iteratively solving it until convergence to the optimal solution. Since the dual decomposition can ensure the convergence and optimality of solutions, this algorithm significantly exceeds GIZA++ and discriminant word alignment system on alignment error rates when testing on the 863 Projects word alignment evaluation data set of 2005. Alignment error rate is decreased by 4.2% and 1.1% respectively.
Key wordsword alignment; discriminative model; search algorithm; dual decomposition