Graphical Models over Multiple Strings

By Markus Dreyer, Jason Eisner. 2009

44 citations recorded by the source corpus.

We study graphical modeling in the case of string-valued random variables. Whereas a weighted finite-state transducer can model the probabilistic relationship between two strings, we are interested in building up joint models of three or more strings. This is needed for inflectional paradigms in morphology, cognate modeling or language reconstruction, and multiple-string alignment. We propose a Markov Random Field in which each factor (potential function) is a weighted finite-state machine, typically a transducer that evaluates the relationship between just two of the strings. The full joint distribution is then a product of these factors. Though decoding is actually undecidable in general, we can still do efficient joint inference using approximate belief propagation; the necessary computations and messages are all finite-state. We demonstrate the methods by jointly predicting morphological forms.

Subfields: Artificial Intelligence, Natural Language Processing

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 Natural Language Processing

Citations in the corpus

Learning with Latent Language (2017, background): “String-valued latent variables are widely used in language processing tasks ranging from morphological analysis (Dreyer and Eisner, 2009) to sentence compression (Miao and Blunsom, 2016).”
Approximation-Aware Dependency Parsing by Belief Propagation (2015, unknown): “, 2012), TAG (Auli and Lopez, 2011), ITG-constraints for phrase extraction (Burkett and Klein, 2012), and graphical models over strings (Dreyer and Eisner, 2009).”
Dual Decomposition Inference for Graphical Models over Strings (2015, methodology): “…sample from the distribution over x deﬁned by such a model (Bouchard-Cˆot´e et al., 2007), or approximately compute the distribution’s marginals using variants of sum-product belief propagation (BP) (Dreyer and Eisner, 2009) and expectation propagation (EP) (Cotterell and Eisner, 2015).”
Minimum-Risk Training of Approximate CRF-Based NLP Systems (2012, background): “ERMA is attractive for NLP because the freedom to use arbitrarily structured graphical models makes it possible to include latent linguistic variables, predict complex structures such as parses (Smith and Eisner, 2008), and do collective prediction in relational domains (Ji and Grishman, 2011; Benso”