  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.
