Theory of Alignment Generators and Applications to Statistical Machine Translation
Abstract
Viterbi Alignment and Decoding are two fundamental search problems in Statistical Machine Translation. Both the problems are known to be NP-hard 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.
Cite
Text
Udupa and Maji. "Theory of Alignment Generators and Applications to Statistical Machine Translation." International Joint Conference on Artificial Intelligence, 2005.Markdown
[Udupa and Maji. "Theory of Alignment Generators and Applications to Statistical Machine Translation." International Joint Conference on Artificial Intelligence, 2005.](https://mlanthology.org/ijcai/2005/udupa2005ijcai-theory/)BibTeX
@inproceedings{udupa2005ijcai-theory,
title = {{Theory of Alignment Generators and Applications to Statistical Machine Translation}},
author = {Udupa, Raghavendra and Maji, Hemanta Kumar},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2005},
pages = {1142-1147},
url = {https://mlanthology.org/ijcai/2005/udupa2005ijcai-theory/}
}