Optimal Search for Minimum Error Rate Training

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 38–49, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Optimal Search for Minimum Error Rate Training Michel Galley Microsoft Research Redmond, WA 98052, USA mgalley@microsoft.com Chris Quirk Microsoft Research Redmond, WA 98052, USA chrisq@microsoft.com Abstract 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., one thousand sentences), by either searching only promising regions of the param- eter space, or by using a variant of LP-MERT that relies on a beam-search approximation. Experimental results show improvements over the standard Och algorithm. 1 Introduction Minimum error rate training (MERT)—also known as direct loss minimization in machine learning—is a crucial component in many complex natural language applications such as speech recognition (Chou et al., 1993; Stolcke et al., 1997; Juang et al., 1997), statisti- cal machine translation (Och, 2003; Smith and Eisner, 2006; Duh and Kirchhoff, 2008; Chiang et al., 2008), dependency parsing (McDonald et al., 2005), summa- rization (McDonald, 2006), and phonetic alignment (McAllester et al., 2010). MERT directly optimizes the evaluation metric under which systems are being evaluated, yielding superior performance (Och, 2003) when compared to a likelihood-based discriminative method (Och and Ney, 2002). In complex text gener- ation tasks like SMT, the ability to optimize BLEU (Papineni et al., 2001), TER (Snover et al., 2006), and other evaluation metrics is critical, since these met- rics measure qualities (such as fluency and adequacy) that often do not correlate well with task-agnostic loss functions such as log-loss. While competitive in practice, MERT faces several challenges, the most significant of which is search. The unsmoothed error count is a highly non-convex objective function and therefore difficult to optimize directly; prior work offers no algorithm with a good approximation guarantee. While much of the ear- lier work in MERT (Chou et al., 1993; Juang et al., 1997) relies on standard convex optimization tech- niques applied to non-convex problems, the Och al- gorithm (Och, 2003) represents a significant advance for MERT since it applies a series of special line min- imizations that happen to be exhaustive and efficient. Since this algorithm remains inexact in the multidi- mensional case, much of the recent work on MERT has focused on extending Och’s algorithm to find better …

Content truncated to 500 words