First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests

By Zhifei Li, Jason Eisner. 2009

161 citations recorded by the source corpus.

Many statistical translation models can be regarded as weighted logical deduction. Under this paradigm, we use weights from the expectation semiring (Eisner, 2002), to compute first-order statistics (e.g., the expected hypothesis length or feature counts) over packed forests of translations (lattices or hypergraphs). We then introduce a novel second-order expectation semiring, which computes second-order statistics (e.g., the variance of the hypothesis length or the gradient of entropy). This second-order semiring is essential for many interesting training paradigms such as minimum risk, deterministic annealing, active learning, and semi-supervised learning, where gradient descent optimization requires computing the gradient of entropy or risk. We use these semirings in an open-source machine translation toolkit, Joshua, enabling minimum-risk training for a benefit of up to 1.0 bleu point.

Subfields: Artificial Intelligence, Molecular Biology, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

In Optimization & Training

Citations in the corpus

Structured Attention Networks (2017, methodology): “Table 1, based on Li & Eisner (2009), demonstrates how to handle this issue, and Figure 2 (right) describes backpropagation through the forward-backward algorithm.”
Determinantal Point Processes for Machine Learning (2012, neutral): “This focus on diversity places DPPs alongside a number of recently developed techniques for working with diverse sets, particularly in the information retrieval community [Carbonell and Goldstein, 1998, Zhai et al., 2003, Chen and Karger, 2006, Yue and Joachims, 2008, Radlinski et al., 2008, Swamina”
Empirical Risk Minimization of Graphical Model Parameters Given Approximate Inference, Decoding, and Model Structure (2011, background): “Our own contributions to this area included general algorithms for computing the gradient of annealed risk when dynamic programming is involved (Li and Eisner, 2009).”
Hope and Fear for Discriminative Training of Statistical Translation Models (2012, methodology): “Keywords: machine translation, structured prediction, large-margin methods, online learning, distributed computing”
Batch Tuning Strategies for Statistical Machine Translation (2012, background): “(5)MR approaches that use lattices (Li and Eisner, 2009; Pauls et al., 2009; Rosti et al., 2011) or the complete search space (Arun et al.”
Posterior Regularization for Structured Latent Variable Models (2010, background): “• An extensive evaluation of different types of constraints in several domains: multi-view learn- ing, cross-lingual dependency grammar induction, unsupervised part-of-speech induction, and bitext word alignment.”
Minimum-Risk Training of Approximate CRF-Based NLP Systems (2012, methodology): “All the methods below are regularized in practice, but we omit mention of regularizers for simplicity.”
cdec: A Decoder, Alignment, and Learning Framework for Finite- State and Context-Free Translation Models (2010, methodology): “Values that can be computed using the semirings include the number of derivations, the expected translation length, the entropy of the translation posterior distribution, and the expected values of feature functions (Li and Eisner, 2009).”
A Shared Task on Bandit Learning for Machine Translation (2017, methodology): “Sampling and computation of expectations on the hypergraph used the Inside-Outside algorithm (Li and Eisner, 2009).”
Learning Structured Predictors from Bandit Feedback for Interactive NLP (2016, methodology): “Sampling and computation of expectations on the hypergraph uses the Inside-Outside algorithm over the expectation semiring (Li and Eisner, 2009).”
Structured Determinantal Point Processes (2010, methodology): “However, we can use a much more efﬁcient O ( D 2 T ) algorithm based on second-order semiring message passing [9].”
Semi-supervised maximum mutual information training of deep neural network acoustic models (2015, methodology): “Our approach for computing the lattice entropy and its derivatives is based on the ideas in [26], but we present it in a form that does not require the concept of a semiring.”
Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper) (2016, background): “, 2015; Gormley, 2015); • how to efficiently obtain the partial derivatives of the expected counts by differentiating the algorithm a second time (Li and Eisner, 2009); • how to navigate through the space of possible inside algorithms (Eisner and Blatz, 2007); • how to convert an inside algorithm in”
SparseMAP: Differentiable Sparse Structured Inference (2018, methodology): “Even when marginal inference is available, case-by-case derivation of the backward pass is needed, sometimes producing fairly complicated algorithms, e.g. , second-order expectation semirings (Li & Eisner, 2009).”
Softmax-Margin CRFs: Training Log-Linear Models with Cost Functions (2010, methodology): “Li and Eisner (2009) introduced a novel semiring for minimizing risk using dynamic programming; Xiong et al. (2009) minimized risk in a CRF.”
Stochastic Structured Prediction under Bandit Feedback (2016, methodology): “Sampling and computation of expectations on the hyp rgraph uses the Inside-Outside algorithm over the expectation semiring [14].”