Graphical Models over Multiple Strings

Markus Dreyer, Jason EisnerEMNLP 2009 · OpenReview

Abstract

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.

Introduction

In computational linguistics, mapping one string to another is a fundamental task, such as converting a lemma to its past-tense form. While Weighted Finite-State Transducers (WFSTs) excel at these pairwise mappings, many linguistic phenomena involve complex interdependencies among multiple strings. In a morphological paradigm, for instance, the various inflected forms of a verb—such as the 1st-person singular and the infinitive—mutually constrain one another.

Modeling these as independent pairs from a central lemma ignores "horizontal" evidence between forms. However, because strings have an infinite domain, standard graphical model inference is computationally challenging. This paper introduces a framework for Markov Random Fields (MRFs) where variables are strings of unbounded length, enabling joint inference across multiple related strings.

Methods: String-Valued Markov Random Fields

The proposed model is an MRF where each factor (potential function) in the graph is a weighted finite-state machine. Unary factors are Weighted Finite-State Acceptors (WFSAs) scoring single strings, while binary factors are WFSTs scoring the relationship between two strings.

Loopy Belief Propagation

To perform inference, the authors adapt the sum-product algorithm. In this context, the "messages" passed between nodes are themselves WFSAs representing unnormalized distributions over strings.

Message passing in the string-valued MRF, where messages are represented as finite-state automata.
  • Variable-to-Factor messages involve the intersection of WFSAs (pointwise product).
  • Factor-to-Variable messages involve composing a WFST with an incoming WFSA and projecting the result onto a single tape (marginalization).

Because exact inference is undecidable and message size can grow exponentially, the authors approximate messages by pruning them to the top $K$ most plausible strings (e.g., the top 1000 paths). Training is conducted via piecewise pseudolikelihood, where factors are trained locally on available string pairs before global integration.

Experimental Setup

The framework was evaluated using the CELEX morphological database, focusing on 9,393 German verb paradigms. Each paradigm contains 10 variables: the lemma and 9 inflected forms (across person, number, and tense). To simulate real-world challenges, the authors hid forms that are rare in natural text (based on the Mannheim News corpus) and tasked the model with predicting these missing values.

Results and Discussion

The researchers explored several graph topologies to connect the morphological forms, ranging from an unconnected baseline to complex loopy structures.

Different graph topologies for morphological paradigms. (U) is the unconnected baseline, while (L1-L4) represent increasingly complex loopy models.

The loopy model L4 significantly outperformed the unconnected baseline (U), achieving a whole-word accuracy of 82.1% compared to 69.0%. The strength of the joint model was most evident in predicting rare forms. For the "2nd-person singular past," which had minimal training data, the baseline accuracy was a mere 0.8%, whereas the loopy MRF reached 69.7% by leveraging information flow from related forms in the graph.

Despite the theoretical risk of divergence in loopy BP, the models typically converged within two iterations. This demonstrates that while the problem is technically undecidable for arbitrary graphs, approximate belief propagation provides a robust and efficient solution for linguistic string modeling.

Conclusion

This work provides a general framework for joint modeling of multiple strings. By factoring the joint distribution into small, overlapping pairwise transducers, the model achieves high accuracy and memory efficiency. Future work may explore more principled variational approximations to replace the "top-K" pruning heuristic and extend the application to fields like bioinformatics and historical linguistics.

Summary updated

Abstract

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.
BibTeX
@inproceedings{dreyer2009graphical,
  author = {Markus Dreyer and Jason Eisner},
  title = {{Graphical Models over Multiple Strings}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=S1-i7Gfd-r},
}
Figure