Weighting Finite-State Transductions With Neural Context

Proceedings of NAACL-HLT 2016, pages 623–633, San Diego, California, June 12-17, 2016. c⃝2016 Association for Computational Linguistics Weighting Finite-State Transductions With Neural Context Pushpendre Rastogi and Ryan Cotterell and Jason Eisner Department of Computer Science, Johns Hopkins University {pushpendre,ryan.cotterell,eisner}@jhu.edu Abstract How should one apply deep learning to tasks such as morphological reinflection, which stochastically edit one string to get another? A recent approach to such sequence-to-sequence tasks is to compress the input string into a vector that is then used to generate the out- put string, using recurrent neural networks. In contrast, we propose to keep the traditional architecture, which uses a finite-state trans- ducer to score all possible output strings, but to augment the scoring function with the help of recurrent networks. A stack of bidirec- tional LSTMs reads the input string from left- to-right and right-to-left, in order to summa- rize the input context in which a transducer arc is applied. We combine these learned fea- tures with the transducer to define a probabil- ity distribution over aligned output strings, in the form of a weighted finite-state automaton. This reduces hand-engineering of features, al- lows learned features to examine unbounded context in the input string, and still permits ex- act inference through dynamic programming. We illustrate our method on the tasks of mor- phological reinflection and lemmatization. 1 Introduction Mapping one character sequence to another is a structured prediction problem that arises frequently in NLP and computational linguistics. Common applications include grapheme-to-phoneme (G2P), transliteration, vowelization, normalization, mor- phology, and phonology. The two sequences may have different lengths. Traditionally, such settings have been modeled with weighted finite-state transducers (WFSTs) with parametric edge weights (Mohri, 1997; Eisner, 2002). This requires manual design of the transducer states and the features extracted from those states. Alternatively, deep learning has recently been tried for sequence-to-sequence transduction (Sutskever et al., 2014). While training these systems could dis- cover contextual features that a hand-crafted para- metric WFST might miss, they dispense with impor- tant structure in the problem, namely the monotonic input-output alignment. This paper describes a nat- ural hybrid approach that marries simple FSTs with features extracted by recurrent neural networks. Our novel architecture allows efficient modeling of globally normalized probability distributions over string-valued output spaces, simultaneously with au- tomatic feature extraction. We evaluate on morpho- logical reinflection and lemmatization tasks, show- ing that our approach strongly outperforms a stan- dard WFST baseline as well as neural sequence-to- sequence models with attention. Our approach also compares reasonably with a state-of-the-art WFST approach that uses task-specific latent variables. 2 Notation and Background Let Σx be a discrete input alphabet and Σy be a dis- crete output alphabet. Our goal is to define a con- ditional distribution p(y | x) where x ∈ Σ∗ x and y ∈ Σ∗ y and x and y may be of different lengths. We use italics for characters and boldface for strings. xi denotes the ith character of x, and xi:j de- notes the substring xi+1xi+2 · · · xj …

Content truncated to 500 words