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

摘要
参考文献
相关文章 (4)

全文: PDF (3238 KB) HTML (1 KB)
输出: BibTeX | EndNote (RIS)

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

	服务

	把本文推荐给朋友
	加入我的书架
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	沈世奇
	刘洋
	孙茂松

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

Abstract：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

Key words： word alignment discriminative model search algorithm dual decomposition

收稿日期: 2012-12-20

中图分类号:

TP391

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

作者简介: 沈世奇(1990—),男,博士研究生,主要研究方向为统计机器翻译;刘洋(1979—),男,副研究员,主要研究方向为机器翻译、自然语言处理;孙茂松(1962—),男,教授,主要研究方向为自然语言处理。

链接本文:

http://jcip.cipsc.org.cn/CN/Y2013/V27/I4/9

[1] Peter F Brown, Vincent J Della Pietra, Stephen A Della Pietra, et al. The mathematics of statistical machine translation: parameter estimation[J]. Computational Linguistics, 1993, 19(2): 263-311.
[2] Philipp Koehn, Franz J Och, Daniel Marcu. Statistical phrase-based translation[C]//Proceedings of HLT-NAACL, Edmonton, Canada, May. 2003: 127-133.
[3] David Chiang. Hierarchical phrase-based translation[J]. Computational Linguistics, 2007,33(2):201-228.
[4] Michel Galley, Jonathan Graehl, Kevin Knight. Scalable inference and training of contextrich syntactic translation models[C]//Proceedings of COLING-ACL, Sydney, Australia, July. 2006: 961-968.
[5] Stephan Vogel, Hermann Ney, Christoph Tillmann. Hmm-based word alignment in statistical translation[C]//Proceedings of the 16th conference on Computational linguistics—Volume 2, COLING 96, Stroudsburg, PA, USA. Association for Computational Linguistics. 1996: 836-841.
[6] Percy Liang, Ben Taskar, Dan Klein. Alignment by agreement[C]//Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, HLT-NAACL06, Stroudsburg, PA, USA. Association for Computational Linguistics. 2006: 104-111.
[7] Yang Liu, Qun Liu, Shouxun Lin. Loglinear models for word alignment[C]//Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, ACL05, Stroudsburg, PA, USA. Association for Computational Linguistics.2005: 459-466.
[8] Robert C Moore. A discriminative framework for bilingual word alignment[C]//Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing, HLT 05, Stroudsburg, PA, USA. Association for Computational Linguistics. 2005: 81-88.
[9] Phil Blunsom, Trevor Cohn. Discriminative word alignment with conditional random fields[C]//Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics, ACL-44, Stroudsburg, PA, USA. Association for Computational Linguistics. 2006: 65-72.
[10] Yang Liu, Qun Liu, Shouxun Lin. Discriminative word alignment by linear modeling[J]. Computational Linguistics, 2010: 36(3):303-339.
[11] Franz Josef Och. Minimum error rate training in statistical machine translation[C]//Proceedings of the 41st Annual Meeting on Association for Computational Linguistics—Volume 1, ACL 03, Stroudsburg, PA, USA. Association for Computational Linguistics. 2003: 160-167.
[12] Chris Dyer, Jonathan H Clark, Alon Lavie, et al. Unsupervised word alignment with arbitrary features[C]//Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Portland, Oregon, USA, June. Association for Computational Linguistics. 2011: 409-419.
[13] Franz Josef Och, Hermann Ney. A systematic comparison of various statistical alignment models[J]. Comput. Linguist., 2003, 29(1):19-51, March.
[14] Jason Riesa, Daniel Marcu. Hierarchical search for word alignment[C]//Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, ACL 10, Stroudsburg, PA, USA. Association for Computational Linguistics. 2010: 157-166.
[15] Terry Koo, Alexander M Rush, Michael Collins, et al. Dual decomposition for parsing with non-projective head automata[C]//Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, EMNLP 10, Stroudsburg, PA, USA. Association for Computational Linguistics. 2010: 1288-1298.
[16] Yin-Wen Chang, Michael Collins. Exact decoding of phrase-based translation models through lagrangian relaxation[C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing, EMNLP 11, Stroudsburg, PA, USA. Association for Computational Linguistics.2011:26-37.
[17] Alexander M Rush, Michael Collins. Exact decoding of syntactic translation models through lagrangian relaxation[C]//Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies—Volume 1, HLT 11, Stroudsburg, PA, USA. Association for Computational Linguistics. 2011: 72-82.
[18] Alexander Rush, Michael Collins. A tutorial on lagrangian relaxation and dual decomposition for nlp[J]. Journal of Artificial Intellegience Research. 2012.
[19] Philipp Koehn. Statistical significance tests for machine translation evaluation[C]//Dekang Lin and Dekai Wu, editors, Proceedings of EMNLP, Barcelona, Spain, July. Association for Computational Linguistics. 2004: 388-395.
[20] John DeNero, Klaus Macherey. Model-based aligner combination using dual decomposition[C]//Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, Portland, Oregon, USA, June. Association for Computational Linguistics. 2011: 420-429.
[21] Andre Martins, Noah Smith, Mario Figueiredo, et al. Dual decomposition with many overlapping components[C]//Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, Edinburgh, Scotland, UK, July. Association for Computational Linguistics. 2011: 238-249.
[22] Sujith Ravi, Kevin Knight. Does giza++make search errors?[J]. Computational Linguistics, 2010, 36(3).