A Polynomial-Time Dynamic Programming Algorithm for Phrase-Based Decoding with a Fixed Distortion Limit
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(n d! l h^{d+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.
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(n d! l h^{d+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.
Research Areas
