A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based Decoding with a Fixed Distortion Limit

Yin-Wen Chang, Michael Collins


Abstract
Decoding of phrase-based translation models in the general case is known to be NP-complete, by a reduction from the traveling salesman problem (Knight, 1999). In practice, phrase-based systems often impose a hard distortion limit that limits the movement of phrases during translation. However, the impact on complexity after imposing such a constraint is not well studied. In this paper, we describe a dynamic programming algorithm for phrase-based decoding with a fixed distortion limit. The runtime of the algorithm is O(nd!lhd+1) where n is the sentence length, d is the distortion limit, l is a bound on the number of phrases starting at any position in the sentence, and h is related to the maximum number of target language translations for any source word. The algorithm makes use of a novel representation that gives a new perspective on decoding of phrase-based models.
Anthology ID:
Q17-1005
Volume:
Transactions of the Association for Computational Linguistics, Volume 5
Month:
Year:
2017
Address:
Cambridge, MA
Editors:
Lillian Lee, Mark Johnson, Kristina Toutanova
Venue:
TACL
SIG:
Publisher:
MIT Press
Note:
Pages:
59–71
Language:
URL:
https://aclanthology.org/Q17-1005
DOI:
10.1162/tacl_a_00046
Bibkey:
Cite (ACL):
Yin-Wen Chang and Michael Collins. 2017. A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based Decoding with a Fixed Distortion Limit. Transactions of the Association for Computational Linguistics, 5:59–71.
Cite (Informal):
A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based Decoding with a Fixed Distortion Limit (Chang & Collins, TACL 2017)
Copy Citation:
PDF:
https://aclanthology.org/Q17-1005.pdf
Presentation:
 Q17-1005.Presentation.pdf
Video:
 https://aclanthology.org/Q17-1005.mp4