Grammatical Error Correction Using Integer Linear Programming
Wu, Yuanbin and Ng, Hwee Tou

Article Structure

Abstract

We propose a joint inference algorithm for grammatical error correction.

Introduction

Grammatical error correction is an important task of natural language processing (NLP).

Related Work

The knowledge engineering approach has been used in early grammatical error correction systems (Murata and Nagao, 1993; Bond et al., 1995; Bond and Ikehara, 1996; Heine, 1998).

Inference with First Order Variables

The inference problem for grammatical error correction can be stated as follows: “Given an input sentence, choose a set of corrections which results in the best output sentence.” In this paper, this problem will be expressed and solved by integer linear programming (ILP).

Constraints for Prior Knowledge

4.1 Modification Count Constraints

Inference with Second Order Variables

5.1 Motivation and Definition

Experiments

Our experiments mainly focus on two aspects: how our ILP approach performs compared to other grammatical error correction systems; and how the different constraints and the second order variables affect the ILP performance.

Conclusion

In this paper, we model grammatical error correction as a joint inference problem.

Topics

ILP

Appears in 33 sentences as: ILP (35)
In Grammatical Error Correction Using Integer Linear Programming
  1. We use integer linear programming ( ILP ) to model the inference process, which can easily incorporate both the power of existing error classifiers and prior knowledge on grammatical error correction.
    Page 1, “Abstract”
  2. ear programming ( ILP ).
    Page 2, “Introduction”
  3. Variables of ILP are indicators of possible grammatical error corrections, the objective function aims to select the best set of corrections, and the constraints help to enforce a valid and grammatical output.
    Page 2, “Introduction”
  4. Furthermore, ILP not only provides a method to solve the inference problem, but also allows for a natural integration of grammatical constraints into a machine learning approach.
    Page 2, “Introduction”
  5. We will show that ILP fully utilizes individual error classifiers, while prior knowledge on grammatical error correction can be easily expressed using linear constraints.
    Page 2, “Introduction”
  6. We evaluate our proposed ILP approach on the test data from the Helping Our Own (H00) 2011 shared task (Dale and Kilgarriff, 2011).
    Page 2, “Introduction”
  7. Experimental results show that the ILP formulation is competitive with state—of—the—art grammatical error correction systems.
    Page 2, “Introduction”
  8. Section 3 introduces a basic ILP formulation.
    Page 2, “Introduction”
  9. Sections 4 and 5 improve the basic ILP formulation with more constraints and second order variables, respectively.
    Page 2, “Introduction”
  10. The difference between their work and our ILP approach is that the beam-search decoder returns an approximate solution to the original inference problem, while ILP returns an exact solution to an approximate inference problem.
    Page 2, “Related Work”
  11. The inference problem for grammatical error correction can be stated as follows: “Given an input sentence, choose a set of corrections which results in the best output sentence.” In this paper, this problem will be expressed and solved by integer linear programming ( ILP ).
    Page 2, “Inference with First Order Variables”

See all papers in Proc. ACL 2013 that mention ILP.

See all papers in Proc. ACL that mention ILP.

Back to top.

shared task

Appears in 11 sentences as: shared task (10) shared tasks (1)
In Grammatical Error Correction Using Integer Linear Programming
  1. Experimental results on the Helping Our Own shared task show that our method is competitive with state-of-the-art systems.
    Page 1, “Abstract”
  2. The task has received much attention in recent years, and was the focus of two shared tasks on grammatical error correction in 2011 and 2012 (Dale and Kilgarriff, 2011; Dale et al., 2012).
    Page 1, “Introduction”
  3. We evaluate our proposed ILP approach on the test data from the Helping Our Own (H00) 2011 shared task (Dale and Kilgarriff, 2011).
    Page 2, “Introduction”
  4. Corrections are called edits in the H00 2011 shared task .
    Page 7, “Inference with Second Order Variables”
  5. We follow the evaluation setup in the H00 2011 shared task on grammatical error correction (Dale and Kilgarriff, 2011).
    Page 7, “Experiments”
  6. The development set and test set in the shared task consist of conference and workshop papers taken from the Association for Computational Linguistics (ACL).
    Page 7, “Experiments”
  7. In the H00 2011 shared task , participants can submit system edits directly or the corrected plain—text system output.
    Page 7, “Experiments”
  8. We compare our ILP approach with two other systems: the beam search decoder of (Dahlmeier and Ng, 2012a) which achieves the best published performance to date on the H00 2011 data set, and UI Runl (Rozovskaya et al., 2011) which achieves the best performance among all participating systems at the H00 2011 shared task .
    Page 8, “Experiments”
  9. The H00 2011 shared task provides two sets of gold-standard edits: the original gold-standard edits produced by the annotator, and the official gold—
    Page 8, “Experiments”
  10. standard edits which incorporated corrections proposed by the H00 2011 shared task participants.
    Page 8, “Experiments”
  11. Experiments on the H00 2011 shared task show that ILP inference achieves state-of—the-art performance on grammatical error correction.
    Page 9, “Conclusion”

See all papers in Proc. ACL 2013 that mention shared task.

See all papers in Proc. ACL that mention shared task.

Back to top.

objective function

Appears in 9 sentences as: Objective Function (1) objective function (8)
In Grammatical Error Correction Using Integer Linear Programming
  1. Variables of ILP are indicators of possible grammatical error corrections, the objective function aims to select the best set of corrections, and the constraints help to enforce a valid and grammatical output.
    Page 2, “Introduction”
  2. Express the inference objective as a linear objective function ; and
    Page 2, “Inference with First Order Variables”
  3. For the grammatical error correction task, the variables in ILP are indicators of the corrections that a word needs, the objective function measures how grammatical the whole sentence is if some corrections are accepted, and the constraints guarantee that the corrections do not conflict with each other.
    Page 2, “Inference with First Order Variables”
  4. 3.2 The Objective Function
    Page 3, “Inference with First Order Variables”
  5. Define the objective function as
    Page 3, “Inference with First Order Variables”
  6. This linear objective function aims to select a set of Zl’fp, such that the sum of their weights is the largest among all possible candidate corrections, which in turn gives the most grammatical sentence under the decomposable assumption.
    Page 3, “Inference with First Order Variables”
  7. An observation on the objective function is that it is possible, for example, to set Zimp = 1 and
    Page 3, “Inference with First Order Variables”
  8. Putting the variables, objective function , and constraints together, the ILP problem with respect to first order variables is as follows:
    Page 4, “Inference with First Order Variables”
  9. (17) A new objective function combines the weights from both first and second order variables:
    Page 6, “Inference with Second Order Variables”

See all papers in Proc. ACL 2013 that mention objective function.

See all papers in Proc. ACL that mention objective function.

Back to top.

confidence score

Appears in 8 sentences as: confidence score (6) confidence scores (5)
In Grammatical Error Correction Using Integer Linear Programming
  1. The confidence scores f (s’ , t) of classifiers, where t E E and E is the set of classifiers.
    Page 3, “Inference with First Order Variables”
  2. For each article instance in s’, the classifier computes the difference between the maximum confidence score among all possible choices of articles, and the confidence score of the observed article.
    Page 3, “Inference with First Order Variables”
  3. Next, to compute whpyg, we collect language model score and confidence scores from the article (ART), preposition (PREP), and noun number (NOUN) classifier, i.e., E = {ART, PREP, NOUN}.
    Page 4, “Inference with First Order Variables”
  4. The confidence score f (3’ ,t) of classifier t is the average of the confidence scores of t on the
    Page 4, “Inference with First Order Variables”
  5. Here, the symbol ft (8’ [p] , p, ART) refers to the confidence score of the article classifier at position
    Page 4, “Inference with First Order Variables”
  6. When measuring the gain due to 21131213312 2 1 (change cat to cats), the weight wNoungmluml is likely to be small since A cats will get a low language model score, a low article classifier confidence score, and a low noun number classifier confidence score .
    Page 6, “Inference with Second Order Variables”
  7. As described in Section 3.2, the weight of each variable is a linear combination of the language model score, three classifier confidence scores , and three classifier disagreement scores.
    Page 8, “Experiments”
  8. Finally, the language model score, classifier confidence scores , and classifier disagreement scores are normalized to take values in [0, 1], based on the H00 2011 development data.
    Page 8, “Experiments”

See all papers in Proc. ACL 2013 that mention confidence score.

See all papers in Proc. ACL that mention confidence score.

Back to top.

language model

Appears in 8 sentences as: language model (8)
In Grammatical Error Correction Using Integer Linear Programming
  1. Features used in classification include surrounding words, part-of—speech tags, language model scores (Gamon, 2010), and parse tree structures (Tetreault et al., 2010).
    Page 2, “Related Work”
  2. The language model score h(s’, LM) of 8’ based on a large web corpus;
    Page 3, “Inference with First Order Variables”
  3. Next, to compute whpyg, we collect language model score and confidence scores from the article (ART), preposition (PREP), and noun number (NOUN) classifier, i.e., E = {ART, PREP, NOUN}.
    Page 4, “Inference with First Order Variables”
  4. When measuring the gain due to 21131213312 2 1 (change cat to cats), the weight wNoungmluml is likely to be small since A cats will get a low language model score, a low article classifier confidence score, and a low noun number classifier confidence score.
    Page 6, “Inference with Second Order Variables”
  5. As described in Section 3.2, the weight of each variable is a linear combination of the language model score, three classifier confidence scores, and three classifier disagreement scores.
    Page 8, “Experiments”
  6. We use the Web 1T 5—gram corpus (Brants and Franz, 2006) to compute the language model score for a sentence.
    Page 8, “Experiments”
  7. Finally, the language model score, classifier confidence scores, and classifier disagreement scores are normalized to take values in [0, 1], based on the H00 2011 development data.
    Page 8, “Experiments”
  8. We use the following values for the coefficients: VLM = 1 ( language model ); At = 1 (classifier confidence); and ,ut = —1 (classifier disagreement).
    Page 8, “Experiments”

See all papers in Proc. ACL 2013 that mention language model.

See all papers in Proc. ACL that mention language model.

Back to top.

model score

Appears in 7 sentences as: model score (6) model scores (1)
In Grammatical Error Correction Using Integer Linear Programming
  1. Features used in classification include surrounding words, part-of—speech tags, language model scores (Gamon, 2010), and parse tree structures (Tetreault et al., 2010).
    Page 2, “Related Work”
  2. The language model score h(s’, LM) of 8’ based on a large web corpus;
    Page 3, “Inference with First Order Variables”
  3. Next, to compute whpyg, we collect language model score and confidence scores from the article (ART), preposition (PREP), and noun number (NOUN) classifier, i.e., E = {ART, PREP, NOUN}.
    Page 4, “Inference with First Order Variables”
  4. When measuring the gain due to 21131213312 2 1 (change cat to cats), the weight wNoungmluml is likely to be small since A cats will get a low language model score , a low article classifier confidence score, and a low noun number classifier confidence score.
    Page 6, “Inference with Second Order Variables”
  5. As described in Section 3.2, the weight of each variable is a linear combination of the language model score , three classifier confidence scores, and three classifier disagreement scores.
    Page 8, “Experiments”
  6. We use the Web 1T 5—gram corpus (Brants and Franz, 2006) to compute the language model score for a sentence.
    Page 8, “Experiments”
  7. Finally, the language model score , classifier confidence scores, and classifier disagreement scores are normalized to take values in [0, 1], based on the H00 2011 development data.
    Page 8, “Experiments”

See all papers in Proc. ACL 2013 that mention model score.

See all papers in Proc. ACL that mention model score.

Back to top.

beam search

Appears in 6 sentences as: Beam search (1) beam search (5)
In Grammatical Error Correction Using Integer Linear Programming
  1. We compare our ILP approach with two other systems: the beam search decoder of (Dahlmeier and Ng, 2012a) which achieves the best published performance to date on the H00 2011 data set, and UI Runl (Rozovskaya et al., 2011) which achieves the best performance among all participating systems at the H00 2011 shared task.
    Page 8, “Experiments”
  2. P R F P R F UI Runl 40.86 11.21 17.59 54.61 14.57 23.00 Beam search 30.28 19.17 23.48 33.59 20.53 25.48 ILP 20.54 27.93 23.67 21.99 29.04 25.03
    Page 8, “Experiments”
  3. The results of the beam search decoder and UI Run1 are taken from Table 2 of (Dahlmeier and Ng, 2012a).
    Page 8, “Experiments”
  4. The performance of ILP inference is also competitive with the beam search decoder.
    Page 8, “Experiments”
  5. Table 5 provides the comparison of the beam search decoder and ILP inference in detail.
    Page 8, “Experiments”
  6. The main difference between the two is that, except for spelling errors, ILP inference gives higher recall than the beam search decoder, while its precision is lower.
    Page 8, “Experiments”

See all papers in Proc. ACL 2013 that mention beam search.

See all papers in Proc. ACL that mention beam search.

Back to top.

machine learning

Appears in 6 sentences as: machine learning (6)
In Grammatical Error Correction Using Integer Linear Programming
  1. To detect and correct grammatical errors, two different approaches are typically used — knowledge engineering or machine learning .
    Page 1, “Introduction”
  2. In contrast, the machine learning approach formulates the task as a classification problem based on learning from training data.
    Page 1, “Introduction”
  3. On the other hand, the machine learning approach can learn from texts written by ESL learners where grammatical errors have been annotated.
    Page 1, “Introduction”
  4. Furthermore, ILP not only provides a method to solve the inference problem, but also allows for a natural integration of grammatical constraints into a machine learning approach.
    Page 2, “Introduction”
  5. As such, the machine learning approach has become the dominant approach in grammatical error correction.
    Page 2, “Related Work”
  6. Previous work in the machine learning approach typically formulates the task as a classification problem.
    Page 2, “Related Work”

See all papers in Proc. ACL 2013 that mention machine learning.

See all papers in Proc. ACL that mention machine learning.

Back to top.

linear programming

Appears in 5 sentences as: linear programming (5)
In Grammatical Error Correction Using Integer Linear Programming
  1. We use integer linear programming (ILP) to model the inference process, which can easily incorporate both the power of existing error classifiers and prior knowledge on grammatical error correction.
    Page 1, “Abstract”
  2. Integer linear programming has been successfully applied to many NLP tasks, such as dependency parsing (Riedel and Clarke, 2006; Martins et al., 2009), semantic role labeling (Punyakanok et al., 2005), and event extraction (Riedel and Mc—Callum, 2011).
    Page 2, “Related Work”
  3. The inference problem for grammatical error correction can be stated as follows: “Given an input sentence, choose a set of corrections which results in the best output sentence.” In this paper, this problem will be expressed and solved by integer linear programming (ILP).
    Page 2, “Inference with First Order Variables”
  4. The ILP problem is solved using lp_solve1, an integer linear programming solver based on the revised simplex method and the branch—and—bound method for integers.
    Page 4, “Inference with First Order Variables”
  5. The inference problem is solved using integer linear programming .
    Page 9, “Conclusion”

See all papers in Proc. ACL 2013 that mention linear programming.

See all papers in Proc. ACL that mention linear programming.

Back to top.

LM

Appears in 5 sentences as: LM (5)
In Grammatical Error Correction Using Integer Linear Programming
  1. The language model score h(s’, LM ) of 8’ based on a large web corpus;
    Page 3, “Inference with First Order Variables”
  2. wlmflc : VLMh(8/7 LM ) + Z )‘tf(8/7
    Page 3, “Inference with First Order Variables”
  3. wNoun,2,singular : VLMh/(Sl, LM )+ AARTfls’, ART) + APREpfls’, PREP) + ANOUNfls’, NOUN)+ IU’ARTg(S/7 ART) + ,U/PREPg(3/a PREP) ‘i— MNOUNg(8/, NOUN).
    Page 4, “Inference with First Order Variables”
  4. wNoun,2,singular = VLMh(3/, LM ) + A2“ (f(a, 1, ART) + f(the, 5, ART)) + )‘PREPf(On, 4, PREP) ANOUN T (
    Page 4, “Inference with First Order Variables”
  5. wufl) : VLMh(8/7 LM ) + Z )‘tf(8/7
    Page 6, “Inference with Second Order Variables”

See all papers in Proc. ACL 2013 that mention LM.

See all papers in Proc. ACL that mention LM.

Back to top.

Dependency Relation

Appears in 3 sentences as: Dependency Relation (1) dependency relation (1) dependency relations (1)
In Grammatical Error Correction Using Integer Linear Programming
  1. 4.3 Dependency Relation Constraints
    Page 5, “Constraints for Prior Knowledge”
  2. Another set of constraints involves dependency relations , including subject—verb relation and determiner—noun relation.
    Page 5, “Constraints for Prior Knowledge”
  3. In Section 4, three sets of constraints are introduced: modification count (MC), article-noun agreement (ANA), and dependency relation (DR) constraints.
    Page 8, “Experiments”

See all papers in Proc. ACL 2013 that mention Dependency Relation.

See all papers in Proc. ACL that mention Dependency Relation.

Back to top.

gold-standard

Appears in 3 sentences as: gold-standard (4)
In Grammatical Error Correction Using Integer Linear Programming
  1. The gold-standard edits are with —> to and e —> the.
    Page 7, “Experiments”
  2. Given a set of gold-standard edits, the original (ungrammatical) input text, and the corrected system output text, the M 2 scorer searches for the system edits that have the largest overlap with the gold—standard edits.
    Page 7, “Experiments”
  3. The H00 2011 shared task provides two sets of gold-standard edits: the original gold-standard edits produced by the annotator, and the official gold—
    Page 8, “Experiments”

See all papers in Proc. ACL 2013 that mention gold-standard.

See all papers in Proc. ACL that mention gold-standard.

Back to top.