Paper: An Efficient Shift-Reduce Decoding Algorithm for Phrased-Based Machine Translation

ACL ID C10-2033
Title An Efficient Shift-Reduce Decoding Algorithm for Phrased-Based Machine Translation
Venue International Conference on Computational Linguistics
Session Poster Session
Year 2010
Authors

In statistical machine translation, decod- ing without any reordering constraint is an NP-hard problem. Inversion Transduc- tion Grammars (ITGs) exploit linguistic structure and can well balance the needed flexibility against complexity constraints. Currently, translation models with ITG constraints usually employs the cube-time CYK algorithm. In this paper, we present a shift-reduce decoding algorithm that can generate ITG-legal translation from left to right in linear time. This algorithm runs in a reduce-eager style and is suited to phrase-based models. Using the state-of- the-art decoder Moses as the baseline, ex- periment results show that the shift-reduce algorithm can significantly improve both the accuracy and the speed on different test sets.