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

Search for Discriminative Word Alignment via Dual Decomposition

作　　者：沈世奇[1] 刘洋[1] 孙茂松[1] 

机构地区：[1]清华大学计算机科学与技术系智能技术与系统国家重点实验室,北京100084

出　　处：《中文信息学报》2013年第4期9-15,共7页Journal of Chinese Information Processing

基　　金：国家863计划资助项目(2012AA011102;2011AA01A207);媒体与网络技术教育部-微软重点实验室项目(20123000007)

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

关 键 词：词语对齐 判别式模型 搜索算法 对偶分解 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]