Elamur Research⌕
☰
home / papers / 2015 / Discriminative Syntax-Based Word Ordering for Text Generation

Discriminative Syntax-Based Word Ordering for Text Generation

Paper · 2015 · Yue Zhang and Stephen Clark

Summary

The paper addresses word ordering for text generation: turning an unordered bag of words (or lemmas) into a fluent, grammatical sentence. The authors frame this as structured prediction. The system outputs both a word sequence and a syntactic analysis, using either Combinatory Categorial Grammar (CCG) or dependency grammar. Because the combined space of permutations and analyses is enormous, they use best-first search guided by a discriminative model trained on syntactically annotated data. They compare several training algorithms and find that scaling feature vectors works best. Scaling lets hypotheses of different lengths be compared fairly and allows negative examples to be expanded during training. Task-specific constraints can be added when needed. Experiments cover pure word ordering on the standard Wall Street Journal test set, where the system beats earlier systems. They also vary how much POS and dependency information is given as input, and evaluate on the NLG 2011 shared task, where results are competitive with the best entries. The work matters because the ordering component can work on its own and be reused in machine translation, summarization, or grammar correction.

Key points

  • The system supports two grammar formalisms, CCG and dependency grammar, within one learning-guided best-first search framework. Accepted hypotheses are stored in a chart-like structure.
  • Training updates the parameters as soon as the top agenda item is incorrect, using the lowest-scored gold hypothesis on the agenda. The authors relate this to LaSO, easy-first guided learning (Shen, Satta, and Joshi 2007), SEARN, and early update.
  • On the Wall Street Journal benchmark, measured with BLEU, the system reports the best word-ordering accuracy to date.
  • The input conditions range from a bare word bag to full POS tags plus unordered, unlabeled dependencies; the latter is equivalent to tree linearization.
  • For the NLG 2011 shared task, the system was extended to handle lemmas, word inflection, and labeled dependencies. This article extends three prior works presented at conferences, namely Zhang 2013; Zhang, Blackwood, and Clark 2012; and Zhang and Clark 2011.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of CambridgeCambridge · United Kingdom243 works · 121,396 citations🎓Singapore University of Technology and DesignSingapore · Singapore49 works · 11,074 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 2Research subjects and languages the work is about.Text generation · 202 worksSyntax & grammar formalisms · 214 works

Cite

Cite as Yue Zhang and Stephen Clark. 2015. Discriminative Syntax-Based Word Ordering for Text Generation. Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/coli_a_00229

@article{zhang2015discriminative,
  title = {{Discriminative Syntax-Based Word Ordering for Text Generation}},
  author = {Yue Zhang and Stephen Clark},
  journal = {Computational Linguistics},
  year = {2015},
  doi = {10.1162/coli\_a\_00229},
  url = {https://doi.org/10.1162/coli_a_00229}
}

References

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

  1. Auli, Michael and Adam Lopez. 2011. Training a log-linear parser with loss functions via softmax-margin. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 333–343, Edinburgh. find
  2. Barzilay, Regina and Kathleen McKeown. 2005. Sentence fusion for multidocument news summarization. Computational Linguistics, 31(3):297–328.
  3. Belz, Anja, Michael White, Dominic Espinosa, Eric Kow, Deirdre Hogan, and Amanda Stent. 2011. The first surface realisation shared task: Overview and evaluation results. In Proceedings of the 13th European Workshop on Natural Language Generation, ENLG ’11, pages 217–226, Stroudsburg, PA.
  4. Blackwood, Graeme, Adrià de Gispert, and William Byrne. 2010. Fluency constraints for minimum Bayes-risk decoding of statistical machine translation lattices. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 71–79, Beijing. find
  5. Bohnet, Bernd, Leo Wanner, Simon Mill, and Alicia Burga. 2010. Broad coverage multilingual deep sentence generation with a stochastic multi-level realizer. In Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 98–106, Beijing.
  6. Bos, Johan, Stephen Clark, Mark Steedman, James R. Curran, and Julia Hockenmaier. 2004. Wide-coverage semantic representations from a CCG parser. In Proceedings of COLING-04, pages 1240–1246, Geneva. find
  7. Caraballo, Sharon A. and Eugene Charniak. 1998. New figures of merit for best-first probabilistic chart parsing. Computational Linguistics, 24:275–298.
  8. Carroll, John, Ann Copestake, Dan Flickinger, and Victor Poznanski. 1999. An efficient chart generator for (semi-) lexicalist grammars. In Proceedings of the 7th European Workshop on Natural Language Generation (EWNLG99), pages 86–95, Toulouse. find
  9. Carroll, John and Stephan Oepen. 2005. High efficiency realization for a wide-coverage unification grammar. In Proceedings of the Second International Joint Conference on Natural Language Processing, IJCNLP’05, pages 165–176, Berlin. find
  10. Chang, Pi-Chuan and Kristina Toutanova. 2007. A discriminative syntactic word order model for machine translation. In Proceedings of ACL, pages 9–16, Prague. find
  11. Chiang, David. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228.
  12. Clark, Stephen and James R. Curran. 2007a. Perceptron training for a wide-coverage lexicalized-grammar parser. In Proceedings of the ACL 2007 Workshop on Deep Linguistic Processing, pages 9–16, Prague. find
  13. Clark, Stephen and James R. Curran. 2007b. Wide-coverage efficient statistical parsing with CCG and log-linear models. Computational Linguistics, 33(4):493–552.
  14. Collins, Michael and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL, pages 111–118, Barcelona.
  15. Crammer, Koby, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. 2006. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551–585. find
  16. Daumé, Hal, John Langford, and Daniel Marcu. 2009. Search-based structured prediction. Machine Learning, 75(3):297–325. find
  17. Daumé, Hal and Daniel Marcu. 2005. Learning as search optimization: approximate large margin methods for structured prediction. In ICML, pages 169–176, Bonn. find
  18. Espinosa, Dominic, Michael White, and Dennis Mehay. 2008. Hypertagging: Supertagging for surface realization with CCG. In Proceedings of ACL-08: HLT, pages 183–191, Columbus, OH. find
  19. Filippova, Katja and Michael Strube. 2007. Generating constituent order in German clauses. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 320–327, Prague. find
  20. Filippova, Katja and Michael Strube. 2009. Tree linearization in English: Improving language model based approaches. In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Short Paper…
  21. Fowler, Timothy A. D. and Gerald Penn. 2010. Accurate context-free parsing with combinatory categorial grammar. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 335–344, Uppsala. find
  22. Goldberg, Yoav and Michael Elhadad. 2010. An efficient algorithm for easy-first non-directional dependency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 742–750, Los Angeles, CA. find
  23. Guo, Yuqing, Deirdre Hogan, and Josef van Genabith. 2011. DCU at generation challenges 2011 surface realisation track. In Proceedings of the Generation Challenges Session at the 13th European Workshop on Natural Language Generation, pages 227–229, Nancy. find
  24. He, Wei, Haifeng Wang, Yuqing Guo, and Ting Liu. 2009. Dependency based Chinese sentence realization. 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, pages 809–816, Suntec. find
  25. Hockenmaier, Julia. 2003. Data and Models for Statistical Parsing with Combinatory Categorial Grammar. Ph.D. thesis, School of Informatics, University of Edinburgh. find
  26. Hockenmaier, Julia and Mark Steedman. 2007. CCGbank: A corpus of CCG derivations and dependency structures extracted from the Penn Treebank. Computational Linguistics, 33(3):355–396.
  27. Huang, Liang, Suphan Fayong, and Yang Guo. 2012. Structured perceptron with inexact search. In Proceedings of the 2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 142–151, Montréal.
  28. Huang, Liang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of ACL, pages 1077–1086, Uppsala. find
  29. Johansson, Richard and Pierre Nugues. 2007. Extended constituent-to-dependency conversion for English. In 16th Nordic Conference of Computational Linguistics, pages 105–112, Tartu.
  30. Kay, Martin. 1996. Chart generation. In Proceedings of ACL, pages 200–204, Santa Cruz, CA.
  31. Koehn, Phillip. 2010. Statistical Machine Translation. Cambridge University Press. find
  32. Koehn, Philipp, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondrej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In Pro… find
  33. Koehn, Philipp, Franz Josef Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology - Volume 1, NAACL ’03, pages 48–54, Edmonton, Canada. find
  34. Koo, Terry and Michael Collins. 2010. Efficient third-order dependency parsers. In Proceedings of ACL, pages 1–11, Uppsala. find
  35. Lee, J. and S. Seneff. 2006. Automatic grammar correction for second-language learners. In Proceedings of Interspeech, pages 1978–1981, Pittsburgh, PA. find
  36. Liu, Yang. 2013. A shift-reduce parsing algorithm for phrase-based string-to-dependency translation. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1–10, Sofia. find
  37. Marcus, Mitchell P., Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19(2):313–330.
  38. 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 Annual Meeting of the Association for Computational Linguistics, pages 311–318, Philadelphia, PA.
  39. Ratnaparkhi, Adwait. 1996. A maximum entropy model for part-of-speech tagging. In Proceedings of EMNLP, pages 133–142, Somerset, NJ.
  40. Reiter, Ehud and Robert Dale. 1997. Building applied natural language generation systems. Natural Language Engineering, 3(1):57–87. find
  41. Shen, Libin and Aravind Joshi. 2008. LTAG dependency parsing with bidirectional incremental construction. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 495–504, Honolulu. HI. find
  42. Shen, Libin, Giorgio Satta, and Aravind Joshi. 2007. Guided learning for bidirectional sequence classification. In Proceedings of ACL, pages 760–767, Prague. find
  43. Song, Linfeng, Yue Zhang, Kai Song, and Qun Liu. 2014. Joint morphological generation and syntactic linearization. In Proceedings of the Twenty-Eighth AAAI Conference, Quebec. find
  44. Steedman, Mark. 2000. The Syntactic Process. The MIT Press, Cambridge, MA. find
  45. Surdeanu, Mihai, Richard Johansson, Adam Meyers, Lluı́s Màrquez, and Joakim Nivre. 2008. The CONLL-2008 shared task on joint parsing of syntactic and semantic dependencies. In Proceedings of the Twelfth Conference on Computational Natural Language Learning, pages 159–177, Manchester.
  46. Wan, Stephen, Mark Dras, Robert Dale, and Cécile Paris. 2009. Improving grammaticality in statistical sentence generation: Introducing a dependency spanning tree algorithm with an argument satisfaction model. In Proceedings of the 12th Conference of the European Chapter of the ACL (EACL 2009), page… find
  47. Weir, David. 1988. Characterizing Mildly Context-Sensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylviania. find
  48. White, Michael. 2004. Reining in CCG chart realization. In Proceedings of INLG-04, pages 182–191, Brockenhurst. find
  49. White, Michael. 2006. Efficient Realization of Coordinate Structures in Combinatory Categorial Grammar. Research on Language & Computation, 4(1):39–75. find
  50. White, Michael and Rajakrishnan Rajkumar. 2009. Perceptron reranking for CCG realization. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 410–419, Singapore. find
  51. Wu, Dekai. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–403.
  52. Xu, Peng, Ciprian Chelba, and Frederick Jelinek. 2002. A study on richer syntactic dependencies for structured language modeling. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 191–198, Philadelphia, PA. find
  53. Zettlemoyer, Luke S. and Michael Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence, pages 658–666, Edinburgh.
  54. Zhang, Yue. 2013. Partial-tree linearization: Generalized word ordering for text synthesis. In Proceedings of IJCAI, pages 2232–2238, Beijing. find
  55. Zhang, Yue, Graeme Blackwood, and Stephen Clark. 2012. Syntax-based word ordering incorporating a large-scale language model. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 736–746, Avignon. find
  56. Zhang, Yue and Stephen Clark. 2008. Joint word segmentation and POS tagging using a single perceptron. In Proceedings of ACL/HLT, pages 888–896, Columbus, OH.
  57. Zhang, Yue and Stephen Clark. 2010. A fast decoder for joint word segmentation and POS-tagging using a single discriminative model. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 843–852, Cambridge, MA. find
  58. Zhang, Yue and Stephen Clark. 2011. Syntactic processing using the generalized perceptron and beam search. Computational Linguistics, 37(1):105–151. find
  59. Zhang, Yue and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 188–193, Portland, OR. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/zhang-2015-discriminative-syntax-based-word-ordering/