Paper: Optimal Search for Minimum Error Rate Training

ACL ID D11-1004
Title Optimal Search for Minimum Error Rate Training
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2011

Minimum error rate training is a crucial compo- nent to many state-of-the-art NLP applications, such as machine translation and speech recog- nition. However, common evaluation functions such as BLEU or word error rate are generally highly non-convex and thus prone to search errors. In this paper, we present LP-MERT, an exact search algorithm for minimum error rate training that reaches the global optimum using a series of reductions to linear programming. Given a set of N-best lists produced from S input sentences, this algorithm finds a linear model that is globally optimal with respect to this set. We find that this algorithm is poly- nomial in N and in the size of the model, but exponential in S. We present extensions of this work that let us scale to reasonably large tuning sets (e.g....