Theory of Alignment Generators and Applications to Statistical Machine Translation
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1142-1146.
Abstract
Viterbi Alignment and Decoding are two fundamental search problems in Statistical Machine Translation. Both the problems are known to be NPhard and therefore, it is unlikely that there exists an optimal polynomial time algorithm for either of these search problems. In this paper we characterize exponentially large subspaces in the solution space of Viterbi Alignment and Decoding. Each of these subspaces admits polynomial time optimal search algorithms. We propose a local search heuristic using a neighbourhood relation on these subspaces. Experimental results show that our algorithms produce better solutions taking substantially less time than the previously known algorithms for these problems.
@inproceedings{ijcai2005p156,
title = {Theory of Alignment Generators and Applications to Statistical Machine Translation},
author = {Udupa, Raghavendra and Maji, Hemanta Kumar},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {1142--1146},
year = {2005},
url = {https://ijcai.org/proceedings/2005/156},
}
TY - CPAPER TI - Theory of Alignment Generators and Applications to Statistical Machine Translation AU - Udupa, Raghavendra AU - Maji, Hemanta Kumar T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 1142 EP - 1146 UR - https://ijcai.org/proceedings/2005/156 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
