{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,24]],"date-time":"2026-09-24T12:17:02Z","timestamp":1790252222121,"version":"4.1.0"},"reference-count":56,"publisher":"MIT Press","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computational Linguistics"],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p>Word ordering is a fundamental problem in text generation. In this article, we study word ordering using a syntax-based approach and a discriminative model. Two grammar formalisms are considered: Combinatory Categorial Grammar (CCG) and dependency grammar. Given the search for a likely string and syntactic analysis, the search space is massive, making discriminative training challenging. We develop a learning-guided search framework, based on best-first search, and investigate several alternative training algorithms.<\/jats:p><jats:p>The framework we present is flexible in that it allows constraints to be imposed on output word orders. To demonstrate this flexibility, a variety of input conditions are considered. First, we investigate a \u201cpure\u201d word-ordering task in which the input is a multi-set of words, and the task is to order them into a grammatical and fluent sentence. This task has been tackled previously, and we report improved performance over existing systems on a standard Wall Street Journal test set. Second, we tackle the same reordering problem, but with a variety of input conditions, from the bare case with no dependencies or POS tags specified, to the extreme case where all POS tags and unordered, unlabeled dependencies are provided as input (and various conditions in between). When applied to the NLG 2011 shared task, our system gives competitive results compared with the best-performing systems, which provide a further demonstration of the practical utility of our system.<\/jats:p>","DOI":"10.1162\/coli_a_00229","type":"journal-article","created":{"date-parts":[[2015,7,20]],"date-time":"2015-07-20T18:19:23Z","timestamp":1437416363000},"page":"503-538","source":"Crossref","is-referenced-by-count":11,"title":["Discriminative Syntax-Based Word Ordering for Text Generation"],"prefix":"10.1162","volume":"41","author":[{"given":"Yue","family":"Zhang","sequence":"first","affiliation":[{"name":"Singapore University of Technology and Design"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen","family":"Clark","sequence":"additional","affiliation":[{"name":"University of Cambridge"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"281","reference":[{"key":"R1","unstructured":"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\u2013343, Edinburgh."},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1162\/089120105774321091"},{"key":"R3","unstructured":"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\u2013226, Stroudsburg, PA."},{"key":"R4","unstructured":"Blackwood, Graeme, Adri\u00e0 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\u201379, Beijing."},{"key":"R5","unstructured":"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\u2013106, Beijing."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.3115\/1220355.1220535"},{"key":"R7","unstructured":"Caraballo, Sharon A. and Eugene Charniak. 1998. New figures of merit for best-first probabilistic chart parsing. Computational Linguistics, 24:275\u2013298."},{"key":"R8","unstructured":"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\u201395, Toulouse."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"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\u2013176, Berlin.","DOI":"10.1007\/11562214_15"},{"key":"R10","unstructured":"Chang, Pi-Chuan and Kristina Toutanova. 2007. A discriminative syntactic word order model for machine translation. In Proceedings of ACL, pages 9\u201316, Prague."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.2.201"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"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\u201316, Prague.","DOI":"10.3115\/1608912.1608915"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.4.493"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Collins, Michael and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL, pages 111\u2013118, Barcelona.","DOI":"10.3115\/1218955.1218970"},{"key":"R15","unstructured":"Crammer, Koby, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. 2006. Online passive-aggressive algorithms. Journal of Machine Learning Research, 7:551\u2013585."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5106-x"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102373"},{"key":"R18","unstructured":"Espinosa, Dominic, Michael White, and Dennis Mehay. 2008. Hypertagging: Supertagging for surface realization with CCG. In Proceedings of ACL-08: HLT, pages 183\u2013191, Columbus, OH."},{"key":"R19","unstructured":"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\u2013327, Prague."},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.3115\/1620853.1620915"},{"key":"R21","unstructured":"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\u2013344, Uppsala."},{"key":"R22","unstructured":"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\u2013750, Los Angeles, CA."},{"key":"R23","unstructured":"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\u2013229, Nancy."},{"key":"R24","doi-asserted-by":"crossref","unstructured":"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\u2013816, Suntec.","DOI":"10.3115\/1690219.1690260"},{"key":"R25","unstructured":"Hockenmaier, Julia. 2003. Data and Models for Statistical Parsing with Combinatory Categorial Grammar. Ph.D. thesis, School of Informatics, University of Edinburgh."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1162\/coli.2007.33.3.355"},{"key":"R27","unstructured":"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\u2013151, Montr\u00e9al."},{"key":"R28","unstructured":"Huang, Liang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of ACL, pages 1077\u20131086, Uppsala."},{"key":"R29","unstructured":"Johansson, Richard and Pierre Nugues. 2007. Extended constituent-to-dependency conversion for English. In 16th Nordic Conference of Computational Linguistics, pages 105\u2013112, Tartu."},{"key":"R30","doi-asserted-by":"crossref","unstructured":"Kay, Martin. 1996. Chart generation. In Proceedings of ACL, pages 200\u2013204, Santa Cruz, CA.","DOI":"10.3115\/981863.981890"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"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 Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics Companion Volume Proceedings of the Demo and Poster Sessions, pages 177\u2013180, Prague.","DOI":"10.3115\/1557769.1557821"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.3115\/1073445.1073462"},{"key":"R34","unstructured":"Koo, Terry and Michael Collins. 2010. Efficient third-order dependency parsers. In Proceedings of ACL, pages 1\u201311, Uppsala."},{"key":"R35","doi-asserted-by":"crossref","unstructured":"Lee, J. and S. Seneff. 2006. Automatic grammar correction for second-language learners. In Proceedings of Interspeech, pages 1978\u20131981, Pittsburgh, PA.","DOI":"10.21437\/Interspeech.2006-542"},{"key":"R36","unstructured":"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\u201310, Sofia."},{"key":"R37","unstructured":"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\u2013330."},{"key":"R38","doi-asserted-by":"crossref","unstructured":"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\u2013318, Philadelphia, PA.","DOI":"10.3115\/1073083.1073135"},{"key":"R39","unstructured":"Ratnaparkhi, Adwait. 1996. A maximum entropy model for part-of-speech tagging. In Proceedings of EMNLP, pages 133\u2013142, Somerset, NJ."},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1017\/S1351324997001502"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"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\u2013504, Honolulu. HI.","DOI":"10.3115\/1613715.1613777"},{"key":"R42","unstructured":"Shen, Libin, Giorgio Satta, and Aravind Joshi. 2007. Guided learning for bidirectional sequence classification. In Proceedings of ACL, pages 760\u2013767, Prague."},{"key":"R43","doi-asserted-by":"crossref","unstructured":"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.","DOI":"10.1609\/aaai.v28i1.8927"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.3115\/1596324.1596352"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"Wan, Stephen, Mark Dras, Robert Dale, and C\u00e9cile 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), pages 852\u2013860, Athens.","DOI":"10.3115\/1609067.1609162"},{"key":"R47","unstructured":"Weir, David. 1988. Characterizing Mildly Context-Sensitive Grammar Formalisms. Ph.D. thesis, University of Pennsylviania."},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.1007\/s11168-006-9010-2"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.3115\/1699510.1699564"},{"key":"R51","unstructured":"Wu, Dekai. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377\u2013403."},{"key":"R52","doi-asserted-by":"crossref","unstructured":"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\u2013198, Philadelphia, PA.","DOI":"10.3115\/1073083.1073116"},{"key":"R53","unstructured":"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\u2013666, Edinburgh."},{"key":"R54","unstructured":"Zhang, Yue. 2013. Partial-tree linearization: Generalized word ordering for text synthesis. In Proceedings of IJCAI, pages 2232\u20132238, Beijing."},{"key":"R55","unstructured":"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\u2013746, Avignon."},{"key":"R56","unstructured":"Zhang, Yue and Stephen Clark. 2008. Joint word segmentation and POS tagging using a single perceptron. In Proceedings of ACL\/HLT, pages 888\u2013896, Columbus, OH."},{"key":"R57","unstructured":"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\u2013852, Cambridge, MA."},{"key":"R58","doi-asserted-by":"publisher","DOI":"10.1162\/coli_a_00037"},{"key":"R59","unstructured":"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\u2013193, Portland, OR."}],"container-title":["Computational Linguistics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/COLI_a_00229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T13:16:57Z","timestamp":1748524617000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/coli\/article\/41\/3\/503-538\/1520"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":56,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.1162\/COLI_a_00229"],"URL":"https:\/\/doi.org\/10.1162\/coli_a_00229","relation":{},"ISSN":["0891-2017","1530-9312"],"issn-type":[{"value":"0891-2017","type":"print"},{"value":"1530-9312","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}