We introduce neural finite state transducers (NFSTs), a family of string transduction models defining joint and conditional probability distributions 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 features (Rastogi et al., 2016). We present training and inference algorithms for locally and globally normalized variants of NFSTs. In experiments on dierent transduction tasks, they compete favorably against seq2seq models while oer-ing interpretable paths that correspond to hard monotonic alignments. 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 ecient, interpretable models with well-studied theory. A WFST describes a function that maps each string pair ( x , y ) to a weightoften 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 dierent analyses (labeled alignments) of that pair. However, WFSTs can only model certain functions, 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 . In this paper, we propose neural finite state transducers (NFSTs), in which the weight of each path is instead given by some sort of neural network, such as an RNN. Thus, the weight of an arc can depend on the context in which the arc is used. By abandoning the Markov property, we lose exact dynamic programming algorithms, but we gain expressivity: the neural network can capture dependencies among the operations along a path. For example, the RNN might give higher weight to a path if it is internally consistent: it might thus prefer to transcribe a speaker's utterance with a path that maps similar sounds in similar contexts to similar phonemes, thereby adapting to the speaker's accent. Consider a finite-state transducer T as in Figure 1 (see Appendix A for background). Using the composition operator  , we can obtain a new FST, x  T , whose accepting paths correspond to the accepting paths of T that have input string x . Similarly, the accepting paths of T  y correspond to the accepting paths of T that have output string y . Finally, x  T  y extracts the paths that have both properties. We define a joint probability distribution over ( x , y ) pairs by marginalizing over those paths: p ( x , y ) = (cid:88) a  x T  y p ( a ) = 1 Z ( T ) (cid:88) a  x T  y  p ( a ) (1) where  p ( a ) is the weight of path a and Z ( T ) = (cid:80) a T  p ( a ) is a normalization constant. We define  p ( a ) (cid:44) exp G  ( a ) with G  ( a ) being some parametric scoring function. In our experiments, we will adopt a fairly simple left-to-right RNN architecture (2.2), but one could easily substitute fancier architectures. We will also consider defining G  by a locally normalized RNN that ensures Z ( T ) = 1 . In short, we use the finite-state transducer T to compactly define a set of possible paths a . The number of paths may be exponential in the size of T , or infinite if T is cyclic. However, in contrast to WFSTs, we abandon this combinatorial structure in favor of neural nets when defining the probability distribution over a . In the resulting marginal distribution p ( x , y ) given in equation (1), the path a that aligns x and y is a latent variable. This is also true of the resulting conditional distribution p ( y | x ) . We explore training and inference algorithms for various classes of NFST models (3). Classical WFSTs (Mohri et al., 2008) and BiRNN-WFSTs (Rastogi et al., 2016) use restricted scoring functions and so admit exact dynamic programming algorithms. For general NFSTs, however, we must resort to approximate computation of the model's training gradient, marginal probabilities, and predictions. In this paper, we will use sequential importance sampling methods (Lin and Eisner, 2018), leaving variational approximation methods to future work. Defining models using FSTs has several benefits: Output-sensitive encoding Currently popular models of p ( y | x ) used in machine translation and morphology include seq2seq (Sutskever et al., 2014), seq2seq with attention (Bahdanau et al., 2015; Luong et al., 2015), the Transformer (Vaswani et al., 2017). These models first encode x as a vector or sequence of vectors, and then condition the generation of y on this encoding. The vector is determined from x only. This is also the case in the BiRNN-WFST (Rastogi et al., 2016), a previous finite-state model to which we compare. By contrast, in our NFST, the state of the RNN as it reads and transduces the second half of x is influenced by the first halves of both x and y and their alignment. Inductive bias Typically, a FST is constructed with domain knowledge (possibly by compiling a regular expression), so that its states reflect interpretable properties such as syllable boundaries or linguistic features. Indeed, we will show below how to make these properties explicit by marking the FST arcs. The NFST's path scoring function then sees these marks and can learn to take them into account. The NFST also inherits any hard constraints from the FST: if the FST omits all ( x , y ) paths for some illegal x , y , then p ( x , y ) = 0 for any parameter vector  (a structural zero). Interpretability Like a WFST, an NFST can explain why it mapped x to y in terms of a latent path a , which specifies a hard monotonic labeled alignment. The posterior distribution p ( a | x , y ) specifies which paths a are the best explanations (e.g., Table 5). We conduct experiments on three tasks: grapheme-to-phoneme, phoneme-to-grapheme, and action-to-command (Bastings et al., 2018). Our results on these datasets show that our best models can improve over neural seq2seq and previously proposed hard alignment models. An NFST is a pair ( T , G  ) , where T is an unweighted FST with accepting paths A and G  A  R is a function that scores these paths. As explained earlier, we then refer to  p ( a ) = exp G  ( a ) as the weight of path a  A . A weighted relation between input and output strings is given by  p ( x , y ) , which is defined to be the total weight of all paths with input string x    and output string y    , where where  and  are the input and output alphabets of T . The real parameter vector  can be adjusted to obtain dierent weighted relations. We Model Training Algorithms Long-Term Output-Output Dependency Left-to-Right Factorization WFSTs Dynamic Programming (cid:55) (cid:51) BiRNN-WFSTs Dynamic Programming (cid:55) (cid:51) Local NFSTs Importance Sampling (cid:51) (cid:51) Global NFSTs Importance Sampling (cid:51) (cid:55) Table 1: Comparison between WFSTs, BiRNN-WFSTs (Rastogi et al., 2016), and NFSTs. can normalize  p to get a probability distribution as shown in equation (1). To obtain contextual mark scores as desired, one simple architecture is a recurrent neural network: G  (  ) (cid:44) |  | (cid:88) t =1 g  ( s t  1 ,  t ) (2) s t = f  ( s t  1 ,  t ) , with s 0 = 0 (3) where s t  1  R d is the hidden state vector of the network after reading  1     t  1 . Weighted FST. A WFST over the (+ ,  ) semiring can be regarded as the special case in which G  ( a ) (cid:44) (cid:80) | a | t =1 g  ( a t ) . This is a sum of scores assigned to the arcs in a = a 1 a 2    . Marked FST. Our innovation is to allow the arcs' scores to depend on their context in the path. Now  no longer associates a fixed score with each arc. Rather, we assume that each arc a in the FST comes labeled with a sequence of marks from a mark alphabet  , as illustrated in Figure 1. The marks reflect the FST constructor's domain knowledge about what arc a does (see 4.2 be-low). We now define G  ( a ) = G  (  ( a )) , where  ( a ) =  ( a 1 )  ( a 2 )       is the concatenated sequence of marks from the arcs along path a . It is sometimes helpful to divide marks into different classes. An arc can be regarded as a possible edit that aligns an input substring with an output substring in the context of transitioning from one FST state to another. The arc's input marks describe its input substring, its output marks describe its output substring, and the remaining marks may describe other properties of the arc's aligned input-output pair or the states that it connects. Recall that an FST encodes domain knowledge. Its paths represent alignments between input and output strings, where each alignment specifies a segmentation of x and y into substrings labeled with FST states. Decorating the arcs with marks furnishes the path scoring model with domain-specific information about the alignments. RNN scoring. If  merely associated a fixed score with each mark, then the marked FST would be no more powerful than the WFST. The g  function defines the score of reading  t in this left context, and f  defines how doing so updates the state. In our experiments, we chose f  to be the GRU state update function (Cho et al., 2014). We defined g  ( s ,  t ) (cid:44) ( Ws + b ) (cid:62) emb(  t ) . The parameter vector  specifies the GRU parameters, W , b , and the mark embeddings emb(  ) . One could easily substitute much fancier architectures, such as a stacked BiLSTM with attention (Tilk and Alume, 2016), or a Transformer (Vaswani et al., 2017). In hopes of improving the inductive bias of the learner, we partitioned the hidden state vector into three sub-vectors: s t = [ s a t ; s x t ; s y t ] . The mark scoring function f  ( s t  1 ,  t ) was as before, but we restricted the form of g  , the state update function. s a t encodes all past marks and depends on the full hidden state so far: s a t = g a  ( s t  1 ,  t ) . However, we make s x t encode only the sequence of past input marks, ignoring all others. Thus, s x t = g x  ( s x t  1 ,  t ) if  t is an input mark, and s x t = s x t  1 otherwise. Symmetrically, s y t encodes only the sequence of past output marks. This architecture is somewhat like Dyer et al. (2016), which also uses dierent sub-vectors to keep track of dierent aspects of the history. A diculty with the general model form in equation (1) is that the normalizing constant Z ( T ) = (cid:80) a T  p ( a ) must sum over a large set of pathsin fact, an infinite set if T is cyclic. This sum may diverge for some values of the parameter vector  , which complicates training of the model (Dreyer, 2011). Even if the sum is known to converge, it is in general intractable to compute it exactly. Thus, estimating the gradient of Z ( T ) during training involves approximate sampling from the typically high-entropy distribution p ( a ) . The resulting estimates are error-prone because the sample size tends to be too small and the approximate sampler is biased. A standard solution in the WFST setting (e.g. Cotterell et al., 2014) is to use a locally normalized model, in which Z ( T ) is guaranteed to be 1. 1 The big summation over all paths a is replaced by small summationswhich can be computed explicitly over just the outgoing edges from a given state. Formally, we define the unnormalized score of arc a i in the context of path a in the obvious way, by summing over the contextual scores of its marks:  g  ( a i ) (cid:44) k (cid:88) t = j +1 g  ( s t  1 ,  t ) (4) where j = |  ( a 1 )     ( a i  1 ) | and k = |  ( a 1 )     ( a i ) | . Its normalized score is then g  , T ( a i ) (cid:44) log (cid:16) exp  g  ( a i ) / (cid:88) a (cid:48) exp  g  ( a (cid:48) ) (cid:17) where a (cid:48) ranges over all arcs in T (including a i itself) that emerge from the same state as a i does. We can now score the paths in T using G  , T ( a ) = | a | (cid:88) i =1 g  , T ( a i ) (5) This gives rise to a proper probability distribution p ( a ) (cid:44)  p ( a ) = exp G  , T ( a ) over the paths of T . No global normalization constant is necessary. However, note that the scoring function now requires T as an extra subscript, because it is necessary when scoring a to identify the competitors in T of each arc a i . Thus,when p ( x , y ) is found as usual by summing up the probabilities of all paths in x  T  y , each path is still scored using its arcs' competitors from T . This means that each state in x  T  y must record the state in T from which it was derived. Many algorithms for working with probability distributionsincluding our training and decoding 1 Provided that every state in T is co-accessible, i.e., has a path to a final state. algorithms belowrely on conditional sampling. In general, we would like to sample a path of T given the knowledge that its input and output strings fall into sets X and Y respectively. 2 If X and Y are regular languages, this is equivalent to defining T (cid:48) = X  T  Y and sampling from p ( a | T (cid:48) ) (cid:44)  p ( a ) (cid:80) a (cid:48) T (cid:48)  p ( a (cid:48) ) , (6) Due to the nonlinearity of G  , the denominator of equation (6) is generally intractable. If T (cid:48) is cyclic, it cannot even be computed by brute-force enumeration. Thus, we fall back on normalized importance sampling, directly adopting the ideas of Lin and Eisner (2018) in our more general FST setting. We employ a proposal distribution q : p ( a | T (cid:48) ) = E a  q [ p ( a | T (cid:48) ) q ( a ) ] , (7)  M (cid:88) m =1  p ( a ( m ) ) q ( a ( m ) )   Z  I ( a = a ( m ) ) =  p ( a | T (cid:48) ) , where  Z = (cid:80) Mm (cid:48) =1  p ( a ( m (cid:48) ) ) q ( a ( m (cid:48) ) ) , and q is a locally normalized distribution over paths a  T (cid:48) . In this paper we further parametrize q as q  ( a ; T (cid:48) ) = T (cid:89) t =1 q t ( a t | a 1 ...t  1 ;  , T (cid:48) ) , (8) q t ( a | a : t  1 ;  , T (cid:48) )  exp( g ( s t  1 , a t ;  , T ) + C  ) , where C  (cid:44) C ( s (cid:48) t , X, Y,  )  R , s (cid:48) t (cid:44) f ( s t  1 ,  ( a )) is a compatibility function that is typically modeled using a neural network. In this paper, one the following three cases are encountered:  X = x , is a string, and Y =   : in this case T (cid:48) = x  T . We let C  = C x ( s (cid:48) t , RNN x ( x , i,  );  ) , where i is the length of the input prefix in a 1 ...t .a , RNN x ( x , i,  ) is the hidden state of the i -th position after reading x (not a nor  ) backwards, and C x (  ,  ) is a feed-forward network that takes the concatenated vector of all arguments, and outputs a real scalar. We describe the parametrization of C x in Appendix C.1. 2 When X or Y is larger than a single string, it is commonly all of   or   respectively, in which case conditioning on it gives no information. X =   , and Y = y is a string: in this case T (cid:48) = T  y . We let C  = C y ( s (cid:48) t , RNN y ( y , j,  );  ) , where j is the length of the output prefix in a 1 ...t .a , and RNN y , C y are similarly defined as in RNN x and C x . X and Y are both strings  X = x , Y = y : in this case we let C  = C xy ( s (cid:48) t , RNN x ( x , i,  ) , RNN y ( y , j,  );  ) . Given a path prefix a : t  1 , q t ( a | a : t  1 ;  , T (cid:48) ) is defined over arcs a such that a : t  1 .a is a valid path prefix in T (cid:48) . To optimize  with regard to q  , we follow (Lin and Eisner, 2018) and seek to find   = argmin  KL [ p || q  ] , where  p is the approximate distribution defined in equation (7), which is equivalent to maximizing the log-likelihood of q  ( a ) when a is distributed according to the approximation  p . In this paper, we consider joint training. The loss function of our model is defined as the negative log joint probability of string pair ( x , y ) : L ( x , y ) =  log p ( x , y ) =  log (cid:88) a  x T  y p ( a ) . (9) Since p is an exponential family distribution, the gradients of L can be written as (Bishop, 2006) L ( x , y ) =  E a  p ( | x T  y ) [  log p ( a )] , (10) where p (  | x  T  y ) is a conditioned distribution over paths. Computing equation (10) requires sampling from p (  | x  T  y ) , which, as we discuss in 3.1, is often impractical. We therefore approximate it with   L ( x , y ) =  E a  p ( | x T  y ) [   log p ( a )]   E a   p ( | x T  y ) [   log p ( a )] (11) =  M (cid:88) m =1 w ( m )   G  ( a ( m ) ) , (12) where q is a proposal distribution parametrized as in equation (8) (discussed in 3.1,) a (1) . . . a ( M )  q are i.i.d. samples of paths in x  T  y , and w ( m ) is the importance weight of the m -th sample satisfying w ( m )  exp G  ( a ( m ) ) q ( a ( m ) ) , (cid:80) Mm =1 w ( m ) = 1 . Pseudocode for calculating equation (12) is listed in Algorithm 1. Algorithm 1 Compute approximate gradient for updating G  Require: G  : A  R is an NFST scoring function, q is a distribution over paths, M  N is the sample size 1: function Get-Gradient( G  , M , q ) 2: for m in 1 . . . M do 3: a ( m )  q 4:  w ( m )  exp G  ( a ( m ) ) q ( a ) 5: end for 6:  Z  (cid:80) Mm =1  w ( m ) 7: for m in 1 . . . M do 8: w ( m )   w ( m )  Z 9: end for 10: return  (cid:80) Mm =1 w ( m )   G  ( a ( m ) ) 11: end function 3.3 Decoding most probable strings Besides finding good paths in a conditioned distribution as we discuss in 3.1, we are also often interested in finding good output strings , which is conventionally referred to as the decoding problem, which we define to be finding the best output string y  (cid:44) argmax y  L ( Y ) p Y ( y | T (cid:48) ) , where p Y ( y | T (cid:48) ) (cid:44) (cid:80) a T (cid:48)  y  p ( a ) (cid:80) a (cid:48) T (cid:48)  p ( a (cid:48) ) . y  (cid:44) argmax y  PY ( y | T (cid:48) ) is a consistent estimator of y  , which can directly be used to find the best string. However, making this estimate accurate might be expensive: it requires sampling many paths in the machine T (cid:48) , which is usually cyclic, and therefore has infinitely many more paths, than T (cid:48)  y k , which has finitely many paths when A is acyclic. On the other hand, for the task of finding the best string among a pool candidates, we do not need to compute (or approximate) the denominator in equation (13), since y  = argmax y  L ( Y ) (cid:88) a T (cid:48)  y  p ( a ) . As in the case for paths, the language L ( Y ) is usually infinitely large. However given an output candidate y k  L (cid:48)  L ( Y ) , we can approximate the summation in equation (14) using importance sampling: (cid:88) a T (cid:48)  y k  p ( a ) = E a  q ( |T (cid:48)  y k ) [  p ( a ) q ( a | T (cid:48)  y k )] , (15) Algorithm 2 Training procedure for G  . where q (  | T (cid:48)  y k ) is a proposal distribution over paths in T (cid:48)  y k . In this paper we parametrize q (  | T (cid:48)  y k ) following the definition in equation (8). When L (cid:48) is finitely large, we reduce the decoding task into a reranking task. To populate L (cid:48) , one possibility is to marginalize over paths in the approximate distribution  p ( a | T (cid:48) ) discussed in 3.1 to obtain an estimate  p Y ( y | T (cid:48) ) , and use its support as L (cid:48) . Note that it's possible to populate the candidate pool in other ways, each with its advantages and drawbacks: for example, one can use a topk path set from a weighted (Markovian) FST. This approach guarantees exact computation, and the pool quality would no longer depend on the qualities of the smoothing distribution q  . However it is also a considerably much weaker model and may yield uninspiring candidates. In the common case where the conditioned machine T (cid:48) = X  T  Y has X = x    as the input string, and Y is the universal acceptor that accepts   , one can obtain a candidate pool from seq2seq models: seq2seq models can capture long distance dependencies between input and output strings, and are typically fast to train and decode from. However they are not applicable in the case where L ( Y ) (cid:54) =   . Experimental details of decoding are further discussed in 4.3. Our experiments mainly aim to: (1) show the eectiveness of NFSTs on transduction tasks; (2) illustrate that how priorknowledge can be introduced into NFSTs and improve the performance; (3) demonstrate the interpretability of our model. Throughout, we experiment on three tasks: (i) grapheme-to-phoneme, (ii) phoneme-to-grapheme, and (iii) actions-to-commands. We compare with competitive string transduction baseline models in these tasks. Grapheme-to-phoneme and phoneme-to-grapheme (G2P/P2G) refer to the transduction between words' spelling and phonemic transcription. English has a highly irregular orthography (Venezky, 2011), which necessitates the use of rich models for this task. We use a portion of the standard CMUDict dataset: the Sphinx-compatible version of CMUDict (Weide, 2005). As for metrics, we choose widely used exact match accuracy and edit distance. Action-to-command (A2C) refers to the transduction between an action sequence and imperative commands. We use NACS (Bastings et al., 2018) in our experiment. As for metrics, we use exact match accuracy (EM). Note that the in A2C setting, a given input can yield dierent outputs, e.g. I_JUMP I_WALK I_WALK corresponds to both jump and walk twice and walk twice after jump. NACS is a finite set of action-command pairs; we consider a predicted command to be correct if it is in the finite set and its corresponding actions is exactly the input. We evaluate on the length setting proposed by Bastings et al. (2018), where we train on shorter sequences and evaluate on longer sequences. NFSTs require an unweighted FST T which defines a scaold for the relation it recognizes. In this paper we experiment with two versions of T : the first is a simple general' design T 0 , which contains only three states s { 0 , 1 , 2 } , where the only arc between q 0 and q 1 consumes the mark <BOS> ; and the only arc between q 1 and q 2 consumes the mark <EOS> . T 0 has exactly one accepting state, which is q 2 . To ensure that T 0 defines relation for all possible string pairs ( x , y )       , we add all arcs of the form a = ( s 1 , s 1 ,  , ,  ) ,  ( ,  )     to T . To recognize transduction rules defined in the Wikipedia English IPA Help page, we define TIPA , which has all states and arcs of T 0 , and additional states and arcs to handle multi-grapheme and multi-phoneme transductions defined in the IPA Help: 3 for example, the transduction th  T is encoded as two arcs ( s 1 , s 3 ,  , t , T ) and ( s 3 , s 1 ,  , h ,  ) . Because of the lack of good prior knowledge that can be added to A2C experiments, we only use general FSTs in those experiments for such experiments. Nor do we encode special marks that we are going to introduce below. 4 4.2.1 Design of mark sequences As with regular WFSTs, the arcs can often be hand-engineered to incorporate prior knowledge. Recall thatas we describe in 2.2,eacharc is associatedwith a mark sequence. In this paper, we will always derive the mark sequence on an arc a = ( s (cid:48) , s,  (cid:48) , ,  ) of the transducer T as  = [ ,  (cid:48) , , s ] , where  (cid:48)    can be engineered to reflect FSTand application-specific properties of a path, such as the IPA Help list we mentioned earlier. One way to encode such knowledge into mark sequences is to have special mark symbols in mark sequences for particular transductions. In this paper we experiment with two schemes of marks:  IPA Help (IPA). We define the IPA mark  IPA = { C | V } , where the symbol C indicates that this arc is part of a transduction rule listed in the consonant section of the Wikipedia English IPA Help page. Similarly, the mark V indicates that the transduction rule is listed in the vowel section. 4 The NACS dataset was actually generated from a regular transducer, which we could in principle use, but doing so would make the transduction fully deterministic and probably not interesting/hard enough. Phoneme Classes (Phone). We define Phone marks  Phone = (  ) , where  is a lookup function that returns the phoneme class of  defined by the CMUDict dataset. 5 In this paper we experiment with the following three FST and mark configurations for G2P/P2G experiments:  -IPA-Phone in which case  (cid:48) =  for all arcs. T = T 0 . +IPA-Phone in which case  (cid:48) = [  IPA ] when the transduction rule is found in the IPA Help list, otherwise  (cid:48) =  . T = TIPA . +IPA+Phone in which case  (cid:48) = [  IPA  Phone ] when the transduction rule is found in the IPA Help list, otherwise  (cid:48) = [  Phone ] . T = TIPA . As we said earlier, we only use T = T 0 with no special marks for A2C experiments. Experimental results on these dierent configurations are in 5.3. We experimentwiththe following methods to decode the most probable strings: Approximate Posterior (AP). We approximate the posterior distribution over output strings  p Y ( y | T (cid:48) ) , and pick  y  = argmax y  p Y ( y | T (cid:48) ) as the output. Reranking AP. As we discuss in 3.3, improving  y  by taking more path samples in T (cid:48) may be expensive. The reranking method uses the support of  p Y as a candidate pool L (cid:48) , and for each y k  L (cid:48) we estimate equation (15) using path samples in T (cid:48)  y k . Reranking External. This decoding method uses k -best lists from external models. In this paper, we make use of sequence-to-sequence baseline models as the candidate pool L (cid:48) . Reranking AP + External. This decoding method uses the union of the support of  p Y and k -best lists from the sequence-to-sequence baseline models as the candidate pool L (cid:48) . In this paper,we take 128 path samples per candidate for all Reranking methods. 5 https://github.com/cmusphinx/cmudict/blob/ master/cmudict.phones 5 Results 5.1 Baselines We compare NFSTs against the following baselines: BiRNN-WFSTs proposed by Rastogi et al. (2016), were weighted finite-state transducers whose weights encode input string features by the use of recurrent neural networks. As we note in Table 1, they can be seen as a special case of NFSTs, where the Markov property is kept, but where exact inference is still possible. Seq2seq models are the standard toolkit for transduction tasks. We make use of the attention mechanism proposed by Luong et al. (2015), which accomplishes soft alignments' that do not enforce a monotonic alignment constraint. Neuralized IBM Model 1 is a character transduction model recently proposed by Wu et al. (2018), which marginalizes over non-monotonic hard alignments between input and output strings. Like (Luong et al., 2015), they did not enforce monotonic alignment constraints; but unlike them, they did not make use of the input feeding mechanism, 6 where past alignment information is fed back into the RNN decoder. This particular omission allows (Wu et al., 2018) to do exact inference with a dynamic programming algorithm. All baseline systems are tuned on the validation sets. The seq2seq models employ GRUs, with word and RNN embedding size = 500 and a dropout rate of 0 . 3 . They are trained with the Adam optimizer (Kingma and Ba, 2014) over 50 epochs. The Neuralized IBM Model 1 models are tuned as described in (Wu et al., 2018). Table 2 indicates that BiRNN-WFST models (Ras-togi et al., 2016) perform worse than other models. Their Markovian assumption helps enable dynamic programming, but restricts their expressive power, which greatly hampers the BiRNN-WFST's performance on the P2G/G2P task. The NACS task also relies highly on output-output interactions, and BiRNN-WFST performs very poorly there. Table 3 shows results from dierent decoding methods on the G2P/P2G tasks, configuration +IPA+Phone . AP performs significantly worse than Reranking AP , suggesting that the estimate  y  suers from the variance problem. Interestingly, of decoding methods that employ external models, Reranking External performs better than Reranking AP + External , despite having a smaller candidate pool. We think there is some product-of-experts eect in Reranking External since the external model may not be biased in the same way as our model is. But such benefits vanish when candidates from AP are also in the pool  our learned approximation learns the bias in the model  and hence the worse performance in Reranking AP + External . This suggests an interesting regularization trick in practice: populating the candidate pool using external models to hide our model bias. However when we compare our method against non-NFST baseline methods we do not make use of such tricks, to ensure a more fair comparison. In Table 4 we see that combining both +IPA and +Phone improves model generalizability over the general FST (-IPA -Phone). We also note that using only the IPA marks leads to degraded performance EM Accuracy Edit Distance Dev Test Dev Test -IPA -Phone 31.8 29.3 1.38 1.373 +IPA -Phone 31.3 29.2 1.367 1.431 +IPA +Phone 32.7 31.8 1.319 1.332 Table 4: Average exact match accuracy (%, higher the better) and edit distance (lower the better) on G2P and P2G. compared to the general FST baseline. This is a surprising result  one explanation is the IPA marks are not defined on all paths that transduce the intended input-output pairs: NFSTs are capable of recognizing phoneme-grapheme alignments in dierent paths, 7 but only one such path is marked by +IPA. But we leave a more thorough analysis to future work. Recently, there has been work relating finite-state methods and neural architectures. For example, Schwartz et al. (2018) and Peng et al. (2018) have shown the equivalence between some neural models and WFSAs. The most important dierences of our work is that in addition to classifying strings, NFSTs can also transduce strings. Moreover, NFSTs also allow free topology of FST design, and breaks the Markovian assumption. In addition to models we compare against in 4, we note that (Aharoni and Goldberg, 2017; Deng et al., 2018) are also similar to our work; in that they also marginalize over latent alignments, although they do not enforce the monotonicity constraint. Work that discusses globally normalized sequence models are relevant to our work. In this paper, we discuss a training strategy that bounds the partition function; other ways to train a globally normalized model (not necessarily probabilistic) include (Wiseman and Rush, 2016; Andor et al., 2016). On the other hand, our locally normalized FSTs bear resemblance to (Dyer et al., 2016), which was also locally normalized, and also employed importance sampling for training. Neural finite state transducers (NFSTs) are able to model string pairs, considering their monotonic alignment but also enjoying RNNs' power to handle non-finite-state phenomena. They compete favor-7 This is discussed further in Appendix B.2. ably with state-of-the-art neural models on transduction tasks. At the same time, it is easy to inject domain knowledge into NFSTs for inductive bias, and they oer interpretable paths. In this paper, we have used rather simple architectures for our RNNs; one could experiment with multiple layers and attention. One could also experiment with associating marks dierently with arcsthe marks are able to convey useful domain information to the RNNs. For example, in a P2G or G2P task, all arcs that cross a syllable boundary might update the RNN state using a syllable mark. We envision using regular expressions to build the NFSTs, and embedding marks in the regular expressions as a way of sending useful features to the RNNs to help them evaluate paths. In this paper,we have studied NFSTs as standalone systems. But as probabilistic models, they can be readily embedded in a bigger picture: it should be directly feasible to incorporate a globally/locally normalized NFST in a larger probabilistic model (Finkel and Manning, 2009; Chiang et al., 2010). The path weights of NFSTs could be interpreted simply as scores, rather than log-probabilities. One would then decode by seeking the 1-best path with input x , e.g., via beam search or Monte Carlo Tree Search. In this setting, one might attempt to train the NFST using methods similar to the max-violation structured perceptron or the structured SVM. This work has been generously supported by a Google Faculty Research Award and by Grant No. 1718846 from the National Science Foundation, both to the last author. Hao Zhu is supported by Tsinghua University Initiative Scientific Research Program. We thank Shijie Wu for providing us IBM Neuralized Model 1 experiment results.
method abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain objective abstain abstain abstain abstain objective abstain abstain method method method method method abstain objective abstain abstain objective abstain abstain method abstain abstain abstain method objective abstain result abstain abstain abstain abstain method objective abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain method abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain abstain abstain abstain method abstain method other abstain method method method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method abstain method method abstain other abstain abstain abstain abstain method abstain method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method abstain result method abstain abstain method abstain abstain method other result abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method method method method abstain method abstain abstain abstain other other abstain other method abstain method method abstain abstain abstain abstain method abstain abstain method method abstain abstain abstain abstain other other other