Grammatical Error Correction Using Integer Linear Programming

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1456–1465, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Grammatical Error Correction Using Integer Linear Programming Yuanbin Wu Department of Computer Science National University of Singapore 13 Computing Drive Singapore 117417 wuyb@comp.nus.edu.sg Hwee Tou Ng Department of Computer Science National University of Singapore 13 Computing Drive Singapore 117417 nght@comp.nus.edu.sg Abstract We propose a joint inference algorithm for grammatical error correction. Different from most previous work where different error types are corrected independently, our proposed inference process considers all possible errors in a uni�ed framework. We use integer linear programming (ILP) to model the inference process, which can easily incorporate both the power of exist- ing error classi�ers and prior knowledge on grammatical error correction. Exper- imental results on the Helping Our Own shared task show that our method is com- petitive with state-of-the-art systems. 1 Introduction Grammatical error correction is an important task of natural language processing (NLP). It has many potential applications and may help millions of people who learn English as a second language (ESL). As a research �eld, it faces the challenge of processing ungrammatical language, which is dif- ferent from other NLP tasks. The task has received much attention in recent years, and was the focus of two shared tasks on grammatical error correc- tion in 2011 and 2012 (Dale and Kilgarriff, 2011; Dale et al., 2012). To detect and correct grammatical errors, two different approaches are typically used � knowl- edge engineering or machine learning. The �rst relies on handcrafting a set of rules. For exam- ple, the superlative adjective best is preceded by the article the. In contrast, the machine learn- ing approach formulates the task as a classi�cation problem based on learning from training data. For example, an article classi�er takes a noun phrase (NP) as input and predicts its article using class labels a/an, the, or ɛ (no article). Both approaches have their advantages and dis- advantages. One can readily handcraft a set of rules to incorporate various prior knowledge from grammar books and dictionaries, but rules often have exceptions and it is dif�cult to build rules for all grammatical errors. On the other hand, the machine learning approach can learn from texts written by ESL learners where grammatical errors have been annotated. However, training data may be noisy and classi�ers may need prior knowledge to guide their predictions. Another consideration in grammatical error cor- rection is how to deal with multiple errors in an input sentence. Most previous work deals with errors individually: different classi�ers (or rules) are developed for different types of errors (article classi�er, preposition classi�er, etc). Classi�ers are then deployed independently. An example is a pipeline system, where each classi�er takes the output of the previous classi�er as its input and proposes corrections of one error type. One problem of this pipeline approach is that the relations between errors are ignored. For ex- ample, assume that an input sentence contains a cats. An …

Content truncated to 500 words