Parameter Estimation for Probabilistic Finite-State Transducers

By Jason Eisner. 2002

213 citations recorded by the source corpus.

Weighted finite-state transducers suffer from the lack of a training algorithm. Training is even harder for transducers that have been assembled via finite-state operations such as composition, minimization, union, concatenation, and closure, as this yields tricky parameter tying. We formulate a "parameterized FST" paradigm and give training algorithms for it, including a general bookkeeping trick ("expectation semirings") that cleanly and efficiently computes expectations and gradients.

Subfields: Artificial Intelligence

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

Citations in the corpus

DeepProbLog: Neural Probabilistic Logic Programming (2018, methodology): “More speciﬁcally, to compute the gradient with respect to the probabilistic logic program part, we rely on Algebraic ProbLog (aProbLog, [Kimmig et al., 2011]), a generalization of the ProbLog language and inference to arbitrary commutative semirings, including the gradient semiring [Eisner, 2002].”
Inside-Outside and Forward-Backward Algorithms Are Just Backprop (tutorial paper) (2016, methodology): “Eisner (2002) generalized the forward-backward algorithm to this setting and drew a connection to gradients.”
Bridging CNNs, RNNs, and Weighted Finite-State Machines (2018, methodology): “The Forward algorithm can be generalized to any semiring (Eisner, 2002), a fact that we make use of in our experiments and analysis.”
Morphological Inflection Generation with Hard Monotonic Attention (2016, background): “finite state transducers (Mohri et al., 1997; Eisner, 2002) which combine expert knowledge with datadriven parameter tuning.”
First- and Second-Order Expectation Semirings with Applications to Minimum-Risk Training on Translation Forests (2009, methodology): “The expectation semiring (Eisner, 2002), originally proposed for ﬁnite-state machines, is one such “training” semiring, and can be used to compute feature expectations for the E-step of the EM algorithm, or gradients of the likelihood function for gradient descent.”
A Maximum Entropy Model of Phonotactics and Phonotactic Learning (2008, methodology): “We then obtain the E[Ci] values by summing over all paths through the machine, using a method devised by Eisner (2001, 2002).”
Differentiable Weighted Finite-State Transducers (2020, background): “The ideas of learning with WFSTs (Eisner, 2002) and automatic differentiation through operations on graphs (Bottou et al.”
Probabilistic finite-state machines - part I (2005, methodology): “To estimate the probabilistic component in the two-step approaches, maximum likelihood or other criteria can be used [7], [45], [93].”
An Algebraic Prolog for Reasoning about Possible Worlds (2011, methodology): “As a final example, the gradient of the success probability, as used for parameter learning in ProbLog (Gutmann et al. 2008), can directly be calculated in aProbLog as well, using the gradient semiring (Eisner 2002).”
Graphical Models over Multiple Strings (2009, background): “Or if Q is large but parameterized by some compact parameter vector φ, so we are only allowed to control its edge weights via φ, then Li and Eisner (2009, section 6) explain how to minimize KL(P ‖Q) by gradient descent. In both cases Q must be deterministic. We remark that if a factor F were specifi”
Contrastive Estimation: Training Log-Linear Models on Unlabeled Data (2005, methodology): “To compute this, intersect the WFSA and the lattice, obtaining a new acyclic WFSA, and sum the u -scores of all its paths (Eisner, 2002) using a simple dynamic programming algorithm akin to the forward algorithm.”
Hope and Fear for Discriminative Training of Statistical Translation Models (2012, methodology): “4 Calculating the risk and its gradient To calculate the expected loss, we can use the expectation semiring of Eisner (2002); we give a slightly modified definition that renormalizes intermediate values in such a way that they can be stored directly instead of as signed logarithms:”
Neural Data-to-Text Generation via Jointly Learning the Segmentation and Correspondence (2020, methodology): “To control the granularity as we want, we utilize posterior regularization (Ganchev et al., 2010) to constrain the expected number of segments for each text 5 , which can be calculated by going through a similar forward pass as in Equation 4 (Eisner, 2002; Backes et al., 2018).”