Name Phylogeny: A Generative Model of String Variation

Name Phylogeny: A Generative Model of String Variation Nicholas Andrews and Jason Eisner and Mark Dredze Department of Computer Science and Human Language Technology Center of Excellence Johns Hopkins University 3400 N. Charles St., Baltimore, MD 21218 USA {noa,eisner,mdredze}@jhu.edu Abstract Many linguistic and textual processes involve transduction of strings. We show how to learn a stochastic transducer from an unorganized collection of strings (rather than string pairs). The role of the transducer is to organize the collection. Our generative model explains similarities among the strings by supposing that some strings in the collection were not generated ab initio, but were instead derived by transduction from other, “similar” strings in the collection. Our variational EM learn- ing algorithm alternately reestimates this phy- logeny and the transducer parameters. The fi- nal learned transducer can quickly link any test name into the final phylogeny, thereby locat- ing variants of the test name. We find that our method can effectively find name variants in a corpus of web strings used to refer to per- sons in Wikipedia, improving over standard untrained distances such as Jaro-Winkler and Levenshtein distance. 1 Introduction Systematic relationships between pairs of strings are at the core of problems such as transliteration (Knight and Graehl, 1998), morphology (Dreyer and Eisner, 2011), cross-document coreference resolu- tion (Bagga and Baldwin, 1998), canonicalization (Culotta et al., 2007), and paraphrasing (Barzilay and Lee, 2003). Stochastic transducers such as proba- bilistic finite-state transducers are often used to cap- ture such relationships. They model a conditional distribution p(y | x), and are ordinarily trained on input-output pairs of strings (Dreyer et al., 2008). In this paper, we are interested in learning from an unorganized collection of strings, some of which might have been derived from others by transforma- tive linguistic processes such as abbreviation, mor- phological derivation, historical sound or spelling change, loanword formation, translation, transliter- ation, editing, or transcription error. We assume that each string was derived from at most one parent, but may give rise to any number of children. The difficulty is that most or all of these parent- child relationships are unobserved. We must recon- struct this evolutionary phylogeny. At the same time, we must fit the parameters of a model of the relevant linguistic process p(y | x), which says what sort of children y might plausibly be derived from parent x. Learning this model of p(y | x) helps us organize the training collection by reconstructing its phylogeny, and also permits us to generalize to new forms. We will focus on the problem of name varia- tion. We observe a collection of person names—full names, nicknames, abbreviated or misspelled names, etc. Some of these names can refer to the same per- son; we hope to detect this. It would be an unlikely coincidence if two mentions of John Jacob Jingle- heimer Schmidt referred to different people, since this is a long and unusual name. Similarly, John Ja- cob Jingelhimer Smith and Dr. J. J. Jingleheimer may also be related names for …

Content truncated to 500 words