Neural Finite-State Transducers: Beyond Rational Relations

Proceedings of NAACL-HLT 2019, pages 272–283 Minneapolis, Minnesota, June 2 - June 7, 2019. c⃝2019 Association for Computational Linguistics 272 Neural Finite State Transducers: Beyond Rational Relations Chu-Cheng Lin Computer Science Department Johns Hopkins University Baltimore, MD 21218, USA kitsing@cs.jhu.edu Hao Zhu Dept. of Computer Science and Technology Tsinghua University Beijing, China zhuhao15@mails.tsinghua.edu.cn Matthew R. Gormley Machine Learning Department Carnegie Mellon University Pittsburgh, PA 15213, USA mgormley@cs.cmu.edu Jason Eisner Computer Science Department Johns Hopkins University Baltimore, MD 21218, USA jason@cs.jhu.edu Abstract We introduce neural finite state transducers (NFSTs), a family of string transduction models defining joint and conditional probability distri- butions over pairs of strings. The probability of a string pair is obtained by marginalizing over all its accepting paths in a finite state transducer. In contrast to ordinary weighted FSTs, however, each path is scored using an arbitrary function such as a recurrent neural network, which breaks the usual conditional independence assumption (Markov property). NFSTs are more powerful than previous finite-state models with neural fea- tures (Rastogi et al., 2016). We present training and inference algorithms for locally and globally normalized variants of NFSTs. In experiments on different transduction tasks, they compete favorably against seq2seq models while offer- ing interpretable paths that correspond to hard monotonic alignments. 1 Introduction Weighted finite state transducers (WFSTs) have been used for decades to analyze, align, and transduce strings in language and speech processing (Roche and Schabes, 1997; Mohri et al., 2008). They form a family of efficient, interpretable models with well- studied theory. A WFST describes a function that maps each string pair (x, y) to a weight—often a real number representing p(x, y) or p(y | x). The WFST is a labeled graph, in which each path a represents a sequence of operations that describes how some x and some y could be jointly generated, or how x could be edited into y. Multiple paths for the same (x, y) pair correspond to different analyses (labeled alignments) of that pair. However, WFSTs can only model certain func- tions, known as the rational relations (Berstel and Reutenauer, 1988).The weight of a path is simply the product of the weights on its arcs. This means s1 ε:ε s0 s2 <BOS> ε:ε <EOS> a:æ <i-a><V><o-æ> b:b <i-b><C><o-b> a:훆 <i-a> ε:æ <o-æ> th:θ <i-t><i-h><C><o-θ> Figure 1: A marked finite-state transducer T . Each arc in T is associated with input and output substrings, listed above the arcs in the figure. The arcs are not labeled with weights as in WFSTs. Rather, each arc is labeled with a sequence of marks (shown in brown) that featurize its qualities. The neural scoring model scores a path by scoring each mark in the context of all marks on the entire path. The example shown here is from the G2P application of §4.1; for space, only a few arcs are shown. ε represents the empty string. that in a random path of the form a ⇝ b ⇝ c, the two subpaths ⇝ are conditionally independent given their common …

Content truncated to 500 words