Paper: Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation

ACL ID P11-1008
Title Exact Decoding of Syntactic Translation Models through Lagrangian Relaxation
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2011
Authors

We describe an exact decoding algorithm for syntax-based statistical translation. The ap- proach uses Lagrangian relaxation to decom- pose the decoding problem into tractable sub- problems, thereby avoiding exhaustive dy- namic programming. The method recovers ex- act solutions, with certificates of optimality, on over 97% of test examples; it has compa- rable speed to state-of-the-art decoders.