Grammatical error correction (GEC) is one of the areas in natural language processing in which purely neural models have not yet superseded more traditional symbolic models. Hybrid systems combining phrase-based statistical machine translation (SMT) and neural sequence models are currently among the most effective approaches to GEC. However, both SMT and neural sequence-to-sequence models require large amounts of annotated data. Language model based GEC (LM-GEC) is a promising alternative which does not rely on annotated training data. We show how to improve LM-GEC by applying modelling techniques based on finite state transducers. We report further gains by rescoring with neural language models. We show that our methods developed for LM-GEC can also be used with SMT systems if annotated training data is available. Our best system outperforms the best published result on the CoNLL-2014 test set, and achieves far better relative improvements over the SMT baselines than previous hybrid systems. Grammatical error correction (GEC) is the task of automatically correcting all types of errors in text; e.g. [ In a such situaction  In such a situation ]. Using neural models for GEC is becoming increasingly popular (Xie et al., 2016; Yuan and Briscoe, 2016; Ji et al., 2017; Sakaguchi et al., 2017; Schmaltz et al., 2017; Chollampatt and Ng, 2018; Ge et al., 2018a,b), possibly combined with phrase-based SMT (Chollampatt et al., 2016; Chollampatt and Ng, 2017; Grundkiewicz and Junczys-Dowmunt, 2018). A potential challenge for purely neural GEC models is their vast output space since they assign non-zero probability mass to any sequence. GEC is  compared to machine translation  a highly constrained problem as corrections tend to be very local, and lexical choices are usually limited. Finite state transducers (FSTs) are an efficient way to represent large structured search spaces. In this paper, we propose to construct a hypothesis space using standard FST operations like composition, and then constrain the output of a neural GEC system to that space. We study two different scenarios: In the first scenario, we do not have access to annotated training data, and only use a small development set for tuning. In this scenario, we construct the hypothesis space using word-level context-independent confusion sets (Bryant and Briscoe, 2018) based on spell checkers and morphology databases, and rescore it with count-based and neural language models (NLMs). In the second scenario, we assume to have enough training data available to train SMT and neural machine translation (NMT) systems. In this case, we make additional use of the SMT lattice and rescore with an NLM-NMT ensemble. Our contributions are:  We present an FST-based adaptation of the work of Bryant and Briscoe (2018) which allows exact inference, and does not require annotated training data. We report large gains from rescoring with a neural language model. Our technique beats the best published result with comparable amounts of training data on the CoNLL-2014 (Ng et al., 2014) test set when applied to SMT lattices. Our combination strategy yields larger gains over the SMT baselines than simpler rescoring or pipelining used in prior work on hybrid systems (Grund-kiewicz and Junczys-Dowmunt, 2018). Constructing the set of hypotheses The core idea of our approach is to first construct a (weighted) hypothesis space H which is large enough to be likely to contain good corrections, but constrained enough to embrace the highly structured nature of GEC. Then, we use H to constrain a neural beam decoder. We make extensive use of the FST operations available in Open-FST (Allauzen et al., 2007) like composition (de-noted with the  -operator) and projection (denoted with  input (  ) and  output (  ) ) to build H . The process starts with an input lattice I . In our experiments without annotated training data, I is an FST which simply maps the input sentence to itself as shown in Fig. 1(a). If we do have access to enough annotated data, we train an SMT system on it and derive I from the SMT n -best list. 1 For each hypothesis y we compute the Levenshtein distance lev ( x , y ) to the source sentence x . We construct a string z by prepending lev ( x , y ) many < mcorr > tokens to y , and construct I such that: z = ( < mcorr > ) lev ( x , y )  y (1) [[ I ]]( z ) =   SMTSMT ( y | x ) . We adapt the notation of Mohri (2003) and denote the cost I assigns to mapping a string z to itself as [[ I ]]( z ) , and set [[ I ]]( z ) =  if I does not accept z . SMT ( y | x ) is the SMT score. In other words, I represents the weighted SMT n -best list after adding lev ( x , y ) many < mcorr > tokens to each hypothesis as illustrated in Fig. 1(c). We scale SMT scores by a factor  SMT for tuning. Bryant and Briscoe (2018) addressed substitution errors such as non-words, morphology-, article-, and preposition-errors by creating confusion sets C ( x i ) that contain possible (context-independent) 1:1 corrections for each input word x i . Specifically, they relied on CyHunspell for spell checking (Rodriguez and Seal, 2014), the AGID morphology database for morphology errors (Atkinson, 2011), and manually defined confusion sets for determiner and preposition errors, hence avoiding the need for annotated training data. We use the same confusion sets as Bryant and Briscoe (2018) to augment our hypothesis space via the edit flower transducer E shown in Fig. 2. E can map any sequence to itself via its  -self-loop. Additionally, it allows the mapping x i  < corr >  y for each y  C ( x i ) . For example, for the misspelled word x i = situaction' and the confusion set C ( situaction' ) = { situation' , acquisition' } , E allows mapping situaction' to  < corr > situa-tion' and  < corr > acquisition', and to itself via the  -self-loop. The additional < corr > token will help us to keep track of the edits. We obtain our base lattice B which defines the set of possible hypotheses by composition and projection: B :=  output ( I  E ) . Scoring the hypothesis space We apply multiple scoring strategies to the hypotheses in B . First, we penalize < mcorr > and < corr > tokens with two further parameters,  mcorr and  corr , by composing B with the penalization transducer P shown in Fig. 3. 2 The  mcorr and  corr parameters control the trade-off between the number and quality of the proposed corrections since high values bias towards fewer corrections. To incorporate word-level language model scores we train a 5-gram count-based LM with 2 Rather than using < mcorr > and < corr > tokens and the transducer P we could directly incorporate the costs in the transducers I and E , respectively. We chose to use explicit correction tokens for clarity. KenLM (Heafield, 2011) on the One Billion Word Benchmark dataset (Chelba et al., 2014), and convert it to an FST L using the OpenGrm NGram Library (Roark et al., 2012). For tuning purposes we scale weights in L with  KenLM : [[ L ]]( y ) =   KenLM log P KenLM ( y ) . Our combined word-level scores can be expressed with the following transducer: Since we operate in the tropical semiring, path scores in H word are linear combinations of correction penalties, LM scores, and, if applicable, SMT scores, weighted with the  -parameters. Note that exact inference in H word is possible using FST shortest path search. This is an improvement over the work of Bryant and Briscoe (2018) who selected correction options greedily. Our ultimate goal, however, is to rescore H word with neural models such as an NLM and  if annotated training data is available  an NMT model. Since our neural models use subword units (Sennrich et al., 2016, BPEs), we compose H word with a transducer T which maps word sequences to BPE sequences. Our final transducer HBPE which we use to constrain the neural beam decoder can be written as: HBPE =  output ( H word  T ) =  output ( I  E  P  L  T ) . To help downstream beam decoding we apply (cid:15) -removal, determinization, minimization, and weight pushing (Mohri, 1997; Mohri and Riley, 2001) to HBPE . We search for the best hypothesis y  BPE with beam search using a combined score of word-level symbolic models (represented by HBPE ) and subword unit based neural models: y  BPE = arg max y BPE (cid:16)  [[ HBPE ]]( y BPE ) +  NLM log PNLM ( y BPE ) +  NMT log PNMT ( y BPE | x BPE ) (cid:17) (7) The final decoding pass can be seen as an ensemble of a neural LM and an NMT model which is constrained and scored at each time step by the set of possible tokens in HBPE . We have introduced three  -parameters  corr ,  KenLM , and  NLM , and three additional parameters  SMT ,  mcorr , and  NMT if we make use of annotated training data. We also use a word insertion penalty  wc for our SMT-based experiments. We tune all these parameters on the development sets using Powell search (Powell, 1964). 3 3 Experiments Experimental setup In our experiments with annotated training data we use the SMT system of Junczys-Dowmunt and Grundkiewicz (2016) 4 to create 1000-best lists from which we derive the input lattices I . All our LMs are trained on the One Billion Word Benchmark dataset (Chelba et al., 2014). Our neural LM is a Transformer decoder architecture in the transformer base con-figuration trained with Tensor2Tensor (Vaswani et al., 2018). Our NMT model is a Transformer model ( transformer base ) trained on the concatenation of the NUCLE corpus (Dahlmeier et al., 2013) and the Lang-8 Corpus of Learner English v1.0 (Mizumoto et al., 2012). We only keep sentences with at least one correction (659K sentences in total). Both NMT and NLM models use byte pair encoding (Sennrich et al., 2016, BPE) with 32K merge operations. We delay SGD updates by 2 on four physical GPUs as suggested by 3 Similarly to Bryant and Briscoe (2018), even in our experiments without annotated training data, we do need a very small amount of annotated sentences for tuning. Saunders et al. (2018). We decode with beam size 12 using the SGNMT decoder (Stahlberg et al., 2017). We evaluate on CoNLL-2014 (Ng et al., 2014) and JFLEG-Test (Napoles et al., 2017), using CoNLL-2013 (Ng et al., 2013) and JFLEG-Dev as development sets. Our evaluation metrics are GLEU (Napoles et al., 2015) and M2 (Dahlmeier and Ng, 2012). We generated M2 files using ERRANT (Bryant et al., 2017) for JFLEG and Tab. 1 to be comparable to Bryant and Briscoe (2018), but used the official M2 files in Tab. 2 to be comparable to Grundkiewicz and Junczys-Dowmunt (2018). Results Our LM-based GEC results without using annotated training data are summarized in Tab. 1. Even when we use the same resources (same LM and same confusion sets) as Bryant and Briscoe (2018), we see gains on JFLEG (rows 1 vs. 2), probably because we avoid search errors in our FST-based scheme. Adding an NLM yields significant gains across the board. Tab. 2 shows that adding confusion sets to SMT lattices is effective even without neural models (rows 3 vs. 4). Rescoring with neural models also benefits from the confusion sets (rows 5 vs. 6). With our ensemble systems (rows 7 and 8) we are able to outperform prior work 5 (row 1) on CoNLL-2014 and 5 We compare our systems to the work of Grundkiewicz and Junczys-Dowmunt (2018) as they used similar training data. We note, however, that Ge et al. (2018b) reported even better results with much more (non-public) training data. Comparing (Ge et al., 2018a) and (Ge et al., 2018b) suggests that most of their gains come from the larger training set. come within 3 GLEU on JFLEG. Since the baseline SMT systems of Grundkiewicz and Junczys-Dowmunt (2018) were better than the ones we used, we achieve even higher relative gains over the respective SMT baselines (Tab. 3). Error type analysis We also carried out a more detailed error type analysis of the best CoNLL-2014 M2 system with/without training data using ERRANT (Tab. 4). Specifically, this table shows that while the trained system was consistently better than the untrained system, the degree of the improvement differs significantly depending on the error type. In particular, since the untrained system was only designed to handle Replacement word errors, much of the improvement in the trained system comes from the ability to correct Missing and Unnecessary word errors. The trained system nevertheless still improves upon the untrained system in terms of replacement errors by 10 F 0 . 5 (45.53 vs. 55.63). In terms of more specific error types, the trained system was also able to capture a wider variety of error types, including content word errors (adjec-tives, adverbs, nouns and verbs) and other categories such as pronouns and punctuation. Since the untrained system only targets spelling, orthographic and morphological errors however, it is interesting to note that the difference in scores between these categories tends to be smaller than others; e.g. noun number (53.43 vs 64.96), orthography (62.77 vs 74.07), spelling (67.91 vs 75.21) and subject-verb agreement (66.67 vs 68.39). This suggests that an untrained system is already able to capture the majority of these error types. Oracle experiments Our FST-based composition cascade is designed to enrich the search space to allow the neural models to find better hypotheses. Tab. 5 reports the oracle sentence error rate for different configurations, i.e. the fraction of reference sentences in the test set which are not in the FSTs. Expanding the SMT lattice significantly reduces the oracle error rate from 55.63% to 48.17%. We demonstrated that our FST-based approach to GEC outperforms prior work on LM-based GEC significantly, especially when combined with a neural LM. We also applied our approach to SMT lattices and reported much better relative gains over the SMT baselines than previous work on hybrid systems. Our results suggest that FSTs provide a powerful and effective framework for constraining neural GEC systems. This paper reports on research supported by the U.K. Engineering and Physical Sciences Research Council (EPSRC grant EP/L027623/1) and Cambridge Assessment, University of Cambridge.
abstain abstain abstain abstain result abstain objective result abstain other abstain abstain abstain objective objective method method abstain abstain abstain result method abstain abstain method method abstain abstain abstain method method method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain method method abstain abstain method abstain abstain abstain abstain method method method other abstain method method method method method method abstain abstain abstain abstain method method abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain objective method result other