Multiple Many-to-Many Sequence Alignment for Combining String-Valued Variables: A G2P Experiment

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 909–919, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Multiple Many-to-Many Sequence Alignment for Combining String-Valued Variables: A G2P Experiment Steffen Eger Text Technology Lab Goethe University Frankfurt am Main Frankfurt am Main, Germany steeger@em.uni-frankfurt.de Abstract We investigate multiple many-to-many alignments as a primary step in integrat- ing supplemental information strings in string transduction. Besides outlining DP based solutions to the multiple alignment problem, we detail an approximation of the problem in terms of multiple sequence segmentations satisfying a coupling con- straint. We apply our approach to boosting baseline G2P systems using homogeneous as well as heterogeneous sources of sup- plemental information. 1 Introduction String-to-string translation (string transduction) is the problem of converting one string x over an alphabet Σ into another string y over a possi- bly different alphabet Γ. The most prominent applications of string-to-string translation in nat- ural language processing (NLP) are grapheme- to-phoneme conversion, in which x is a letter- string and y is a string of phonemes, translit- eration (Sherif and Kondrak, 2007), lemmatiza- tion (Dreyer et al., 2008), and spelling error cor- rection (Brill and Moore, 2000). The classi- cal learning paradigm in each of these settings is to train a model on pairs of strings {(x, y)} and then to evaluate model performance on test data. Thereby, all state-of-the-art modelings we are aware of (e.g., (Jiampojamarn et al., 2007; Bisani and Ney, 2008; Jiampojamarn et al., 2008; Jiampojamarn et al., 2010; Novak et al., 2012)) proceed by first aligning the string pairs (x, y) in the training data. Also, these modelings ac- knowledge that alignments may typically be of a rather complex nature in which several x sequence ph oe n i x f i n I ks Table 1: Sample monotone many-to-many align- ment between x = phoenix and y = finIks. characters may be matched up with several y se- quence characters; Table 1 illustrates. Once the training data is aligned, since x and y sequences are then segmented into equal number of seg- ments, string-to-string translation may be seen as a sequence labeling (tagging) problem in which x (sub-)sequence characters are observed variables and y (sub-)sequence characters are hidden states (Jiampojamarn et al., 2007; Jiampojamarn et al., 2010). In this work, we extend the problem of classi- cal string-to-string translation by assuming that, at training time, we have available (M + 2)-tuples of strings {(x, ˆy(1), . . . , ˆy(M), y)}, where x is the input string, ˆy(m), for 1 ≤ m ≤ M, are sup- plemental information strings, and y is the de- sired output string; at test time, we wish to pre- dict y from (x, ˆy(1), . . . , ˆy(M)). Generally, we may think of ˆy(1), . . . , ˆy(M) as arbitrary strings over arbitrary alphabets Σ(m), for 1 ≤ m ≤ M. For example, x might be a …

Content truncated to 500 words