Revisiting Optimal Decoding for Machine Translation IBMModel 4

This paper revisits optimal decoding for statis-tical machine translation using IBM Model 4. We show that exact/optimal inference using Integer Linear Programming is more practical than previously suggested when used in con-junction with the Cutting-Plane Algorithm. In our experiments we see that exact inference can provide a gain of up to one BLEU point for sentences of length up to 30 tokens.