Learning to Simplify Sentences with Quasi-Synchronous Grammar and Integer Programming

What it is about

The paper casts simplification as rewriting with a quasi-synchronous grammar (QG), a formalism that relates two trees that need not be isomorphic. The QG rules are induced in two ways: from the revisions of Wikipedia articles whose comments mention simplification, and from aligned Wikipedia and Simple Wikipedia sentences. The rules cover syntactic simplification and sentence division. Because many rewrites are possible, an integer linear program selects the set that maximises a score under constraints on grammaticality, length and the number of sentences, so the choice is global rather than greedy. Evaluation uses the Flesch-Kincaid grade level and human ratings of simplicity, grammaticality and meaning. The ILP models simplify significantly while keeping the meaning, and the Zhu et al. (2010) baseline differs significantly from the ILP models on all rated dimensions. Revision-derived rules and aligned-corpus rules are compared.

Ideas

• I1. Global selection with exact search. The translator picks the most frequent chunk per meta token, which is greedy. Where several chunk choices have similar counts, select the combination that maximises total count under constraints (no concept used twice, one chunk per slot), by a small deterministic search in BTreeMap order. Compare it with the greedy choice on dev, twice.
• I2. Author rules from edit pairs. Count author-specific rewrites from the edit histories of a text, keep the rules seen at least three times, and use them as deltas. This follows the paper's use of revisions as rule source.
• I3. Explicit constraints as gates. Keep grammaticality, length and sentence-count limits as counted gates on output, not as a readability score. The paper's readability formula is a weak signal and should not stand alone.

For Mova

The global choice in I1 is a concrete change to tools/translate/profile.rs, where the standard encoder chooses chunks. The QG formalism itself is not needed; the selection under constraints and the rule-count threshold are. Relevant to open problems 2 (lexicon noise) and 3 (encoder writes trees).

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{woodsend2011learning,
  title = {{Learning to Simplify Sentences with Quasi-Synchronous Grammar and Integer Programming}},
  author = {Woodsend, Kristian and Lapata, Mirella},
  booktitle = {Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing},
  year = {2011},
  url = {https://aclanthology.org/D11-1038/}
}

References

35 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Achterberg, Tobias. 2007. Constraint Integer Programming. Ph.D. thesis, Technische Universität Berlin. find
2. Barzilay, Regina. 2003. Information Fusion for Multi-Document Summarization: Paraphrasing and Generation. Ph.D. thesis, Columbia University. find
3. Barzilay, Regina and Noemie Elhadad. 2003. Sentence alignment for monolingual comparable corpora. In Proceedings of the Conference on Empirical Methods in Natural Language Processing. Sapporo, Japan, pages 25–32. find
4. Beigman Klebanov, Beata, Kevin Knight, and Daniel Marcu. 2004. Text simplification for information-seeking applications. In Proceedings of Ontologies, Dabases, and Applications of Semantics (ODBASE) International Conference. Springer, Agia Napa, Cyprus, volume 3290 of Lecture Notes in Computer Science, pages 735– 747. find
5. Carroll, John, Guido Minnen, Darren Pearce, Yvonne Canning, Siobhan Devlin, and John Tait. 1999. Simplifying text for language-impaired readers. In Proceedings of the 9th Conference of the European Chapter of the ACL. Bergen, Norway, pages 269–270. find
6. Chandrasekar, Raman, Christine Doran, and Bangalore Srinivas. 1996. Motivations and methods for text simplification. In Proceedings of the 16th International Conference on Computational Linguistics. Copenhagen, Denmark, pages 1041– 1044. find
7. Cohn, Trevor and Mirella Lapata. 2008. Sentence compression beyond word deletion. In Proceedings of the 22nd International Conference on Computational Linguistics. Manchester, UK, pages 137–144. find
8. Das, Dipanjan and Noah A. Smith. 2009. Paraphrase identification as probabilistic quasi-synchronous recognition. In Proceedings of the ACL-IJCNLP. Suntec, Singapore, pages 468–476. find
9. Devlin, Siobhan. 1999. Simplifying Natural Language for Aphasic Readers. Ph.D. thesis, University of Sunderland. find
10. Inui, Kentaro, Atsushi Fujita, Tetsuro Takahashi, Ryu Iida, and Tomoya Iwakura. 2003. Text simplification for reading assistance: A project note. In Proceedings of the Second International Workshop on Paraphrasing. Association for Computational Linguistics, Sapporo, Japan, pages 9–16. find
11. Kaji, Nobuhiro, Daisuke Kawahara, Sadao Kurohashi, and Satoshi Sato. 2002. Verb paraphrase based on case frame alignment. In Proceedings of 40th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, Philadelphia, Pennsylvania, USA, pages 215–222. find
12. Klein, Dan and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proceedings of the 41st Annual Meeting of the Association of Computational Linguistics. Sapporo, Japan, pages 423–430. find our card
13. Knight, Kevin and Daniel Marcu. 2002. Summarization beyond sentence extraction: a probabilistic approach to sentence compression. Artificial Intelligence 139(1):91–107. find
14. Koch, Thorsten. 2004. Rapid Mathematical Prototyping. Ph.D. thesis, Technische Universität Berlin. find
15. Mitchell, James V. 1985. The Ninth Mental Measurements Year-book. University of Nebraska Press, Lincoln, Nebraska. find
16. Nastase, Vivi and Michael Strube. 2008. Decoding Wikipedia categories for knowledge acquisition. In Proceedings of the 23rd Conference on Artificial Intelligence. pages 1219–1224. find
17. Nelken, Rani and Stuart Schieber. 2006. Towards robust context-sensitive sentence alignment for monolingual corpora. In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics. Trento, Italy, pages 161–168. find
18. Papineni, Kishore, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proceedings of the 40th ACL. Philadelphia, PA, pages 311–318. find our card
19. Ponzetto, Simone Paolo and Michael Strube. 2007. Knowledge derived from Wikipedia for computing semantic relatedness. Journal of Artificial Intelligence Research 30:181–212. find
20. Sauper, Christina and Regina Barzilay. 2009. Automatically generating Wikipedia articles: A structure-aware approach. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP. Association for Computational Linguistics, Suntec, Singapore, pages 208–216. find
21. Siddharthan, Advaith. 2003. Syntactic Simplification and Text Cohesion. Ph.D. thesis, University of Cambridge, University of Cambridge. find
22. Siddharthan, Advaith. 2004. Syntactic simplification and text cohesion. in research on language and computation. Research on Language and Computation 4(1):77–109. find
23. Smith, David and Jason Eisner. 2006. Quasi-synchronous grammars: Alignment by soft projection of syntactic dependencies. In Proceedings on the Workshop on Statistical Machine Translation. Association for Computational Linguistics, New York City, pages 23–30. find our card
24. Smith, David A. and Jason Eisner. 2009. Parser adaptation and projection with quasi-synchronous grammar features. In Proceedings of the EMNLP. Suntec, Singapore, pages 822–831. find
25. Snover, Matthew, Nitin Madnani, Bonnie Dorr, and Richard Schwartz. 2009. Fluency, adequacy, or HTER? Exploring different human judgments with a tunable MT metric. In Proceedings of the Fourth Workshop on Statistical Machine Translation. Athens, Greece, pages 259–268. find
26. Vickrey, David and Daphne Koller. 2008. Sentence simplification for semantic role labeling. In Proceedings of ACL-08: HLT. Association for Computational Linguistics, Columbus, Ohio, pages 344–352. find
27. Wang, Mengqiu, Noah A. Smith, and Teruko Mitamura. 2007. What is the Jeopardy model? a quasi-synchronous grammar for QA. In Proceedings of the EMNLP-CoNLL. Prague, Czech Republic, pages 22–32. find
28. Watanabe, Willian Massami, Arnaldo Candido Junior, Vinı́cius Rodriguez de Uzẽda, Renata Pontin de Mattos Fortes, Thiago Alexandre Salgueiro Pardo, and Sandra Maria Alu´sio. 2009. Facilita: reading assistance for low-literacy readers. In Proceedings of the 27th ACM International Conference on Design of Communication. Bloomington, IN. find
29. Woodsend, Kristian, Yansong Feng, and Mirella Lapata. 2010. Title generation with quasi-synchronous grammar. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Cambridge, MA, pages 513–523. find
30. Wu, Fei and Daniel S. Weld. 2010. Open information extraction using Wikipedia. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics. Association for Computational Linguistics, Uppsala, Sweden, pages 118–127. find
31. Yamada, Kenji and Kevin Knight. 2001. A syntax-based statistical translation model. In Proceedings of 39th Annual Meeting of the Association for Computational Linguistics. Toulouse, France, pages 523–530. find our card
32. Yamangil, Elif and Rani Nelken. 2008. Mining Wikipedia revision histories for improving sentence compression. In Proceedings of ACL-08: HLT, Short Papers. Association for Computational Linguistics, Columbus, Ohio, pages 137– 140. find
33. Yatskar, Mark, Bo Pang, Cristian Danescu-Niculescu-Mizil, and Lillian Lee. 2010. For the sake of simplicity: Unsupervised extraction of lexical simplifications from Wikipedia. In Proceedings of the Annual Meeting of the North American Chapter of the Association for Computational Linguistics. pages 365–368. find
34. Zhao, Shiqi, Xiang Lan, Ting Liu, and Sheng Li. 2009. Application-driven statistical paraphrase generation. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP. Singapore, pages 834–842. find
35. Zhu, Zhemin, Delphine Bernhard, and Iryna Gurevych. 2010. A monolingual tree-based translation model for sentence simplification. In Proceedings of the 23rd International Conference on Computational Linguistics. Beijing, China, pages 1353–1361. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/woodsend-2011-learning-simplify-sentences-quasi-synchronous/