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

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...