Minimum Error Rate Training and the Convex Hull Semiring
This work provides incremental improvements for researchers in machine translation by clarifying the computational geometry behind MERT algorithms.
The paper tackles the complexity analysis and implementation of minimum error rate training (MERT) algorithms by framing the line search as an 'inside score' under a convex hull semiring, leading to a straightforward analysis and practical approaches.
We describe the line search used in the minimum error rate training algorithm MERT as the "inside score" of a weighted proof forest under a semiring defined in terms of well-understood operations from computational geometry. This conception leads to a straightforward complexity analysis of the dynamic programming MERT algorithms of Macherey et al. (2008) and Kumar et al. (2009) and practical approaches to implementation.