Paper: Graphical Models over Multiple Strings

ACL ID D09-1011
Title Graphical Models over Multiple Strings
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2009
Authors

We study graphical modeling in the case of string- valued random variables. Whereas a weighted finite-state transducer can model the probabilis- tic relationship between two strings, we are inter- ested in building up joint models of three or more strings. This is needed for inflectional paradigms in morphology, cognate modeling or language re- construction, and multiple-string alignment. We propose a Markov Random Field in which each factor(potentialfunction)isaweightedfinite-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 fac- tors. Though decoding is actually undecidable in general, we can still do efficient joint inference using approximate belief propagation; the nec- essary c...