Latent-Variable Modeling of String Transductions with Finite-State Methods

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 1080–1089, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Latent-Variable Modeling of String Transductions with Finite-State Methods∗ Markus Dreyer and Jason R. Smith and Jason Eisner Department of Computer Science Johns Hopkins University Baltimore, MD 21218, USA {markus,jsmith,jason}@cs.jhu.edu Abstract String-to-string transduction is a central prob- lem in computational linguistics and natural language processing. It occurs in tasks as di- verse as name transliteration, spelling correc- tion, pronunciation modeling and inflectional morphology. We present a conditional log- linear model for string-to-string transduction, which employs overlapping features over la- tent alignment sequences, and which learns la- tent classes and latent string pair regions from incomplete training data. We evaluate our ap- proach on morphological tasks and demon- strate that latent variables can dramatically improve results, even when trained on small data sets. On the task of generating mor- phological forms, we outperform a baseline method reducing the error rate by up to 48%. On a lemmatization task, we reduce the error rates in Wicentowski (2002) by 38–92%. 1 Introduction A recurring problem in computational linguistics and language processing is transduction of charac- ter strings, e.g., words. That is, one wishes to model some systematic mapping from an input string x to an output string y. Applications include: • phonology: underlying representation ↔ surface representation • orthography: pronunciation ↔ spelling • morphology: inflected form ↔ lemma, or differ- ently inflected form • fuzzy name matching (duplicate detection) and spelling correction: spelling ↔ variant spelling ∗This work was supported by the Human Language Tech- nology Center of Excellence and by National Science Founda- tion grant No. 0347822 to the final author. We would also like to thank Richard Wicentowski for providing us with datasets for lemmatization, and the anonymous reviewers for their valuable feedback. • lexical translation (cognates, loanwords, translit- erated names): English word ↔ foreign word We present a configurable and robust framework for solving such word transduction problems. Our results in morphology generation show that the pre- sented approach improves upon the state of the art. 2 Model Structure A weighted edit distance model (Ristad and Yian- ilos, 1998) would consider each character in isola- tion. To consider more context, we pursue a very natural generalization. Given an input x, we evalu- ate a candidate output y by moving a sliding window over the aligned (x, y) pair. More precisely, since many alignments are possible, we sum over all these possibilities, evaluating each alignment separately.1 At each window position, we accumulate log- probability based on the material that appears within the current window. The window is a few charac- ters wide, and successive window positions over- lap. This stands in contrast to a competing approach (Sherif and Kondrak, 2007; Zhao et al., 2007) that is inspired by phrase-based machine translation (Koehn et al., 2007), which segments the input string into substrings that are transduced independently, ig- noring context.2 1At the other extreme, Freitag and Khadivi (2007) use no alignment; …

Content truncated to 500 words