Minimum error rate training

Minimum error rate training (or MERT) is a method. This is a work in progress by Francis Keith

Citation

MERT was originally proposed in the paper “Minimum Error Rate Training in Statistical Machine Translation”, Franz Josef Och, ACL, 2003, pp. 160-167. (found here [1])

Background

When training a model, often times it is beneficial to take into account the actual evaluation method for that model. In many cases, training methods do not. MERT attempts to train models for statistical machine translation. It attempts to optimize the parameters of the model while considering a more complex evaluation method than simply counting incorrect translations. It essentially attempts to train the model based on the method that will be used to evaluate the model.

Optimization Problem

The goal of MERT, as the name would suggest, is to find a minimum error rate count, given:

• $f_{1}^{s}$, the representative corpus
• ${\hat {e}}_{1}^{s}$, the reference translations
• $K$, a set of candidate translations
  • $C_{s}=\{e_{s,1},...,e_{s,K}\}$ for each $f_{s}$
• $M$ feature functions $h_{m}(e,f)$
• $M$ model parameters $\lambda _{m}$

We then attempt to optimize:

${\hat {e}}(f_{s};\lambda _{1}^{M})={\underset {e\in C}{\operatorname {argmax} }}\{\sum _{m=1}^{M}\lambda _{m}h_{m}(e|f_{s})\}$

The error count is provided by:

${\hat {\lambda }}_{1}^{M}={\underset {\lambda _{1}^{M}}{\operatorname {argmin} }}\{\sum _{s=1}^{S}E(r_{s},{\hat {e}}(f_{s};\lambda _{1}^{m}))\}$ $={\underset {\lambda _{1}^{M}}{\operatorname {argmin} }}\{\sum _{s=1}^{S}\sum _{k=1}^{K}E(r_{s},e_{s,k})\delta ({\hat {e}}(f_{s};\lambda _{1}^{M}),e_{s,k})\}$

Training Algorithm

The key to the optimization is doing an optimization along the line:

$\lambda _{1}^{M}+\gamma *d_{1}^{M}$

$\gamma$ comes from:

${\hat {e}}({\hat {f}};\gamma )={\underset {e\in C}{\operatorname {argmin} }}\{t(e,f)+\gamma *m(e,f)\}$

As $t$ and $m$ are functions of $\gamma$, we can define a piecewise linear function $f'$ such that:

$f'(\gamma ;f)={\underset {e\in C}{\operatorname {min} }}\{t(e,f)+\gamma *m(e,f)\}$

The algorithm is as follows:

• Compute $f'(\gamma ;f)$ for every sentence $f$ with the incremental change in error count
  • This yields a sequence $\gamma _{1}^{f}<\gamma _{2}^{f}<...<\gamma _{N_{f}}^{f}$
  • Each of these shows a change in error count $\Delta E_{n}^{f}$
• Compute the optimal $\gamma$ by traversing these intervals while updating the error count

Benefits

MERT has numerous benefits, most of which are specific to MT problems

• Finds global optima
  • This is important because the error count is not smoothed, which means there could be significantly more local optima
• Guarantees convergence
  • This is also important because the unsmoothed error count is not a convex function

Drawbacks

MERT, while very powerful (and the current popular approach to training MT models), has some drawbacks

• Tends to overfit
• Doesn't work well with large feature sets
• High variance across runs due to many local optima

Related Work

MERT is more or less the standard for training MT models currently. As a result, it is used in many MT papers

• An End-to-End Discriminative Approach to Machine Translation, Liang et al., 2006. - Provides an improvement to allow for more features
• Hierarchical Phrase-Based Translation, Chiang, 2007. - Uses MERT for phrase-based translation