Spanning tree approaches for statistical sentence generation

Stephen Wan*, Mark Dras, Robert Dale, Cécile Paris

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

4 Citations (Scopus)


In abstractive summarisation, summaries can include novel sentences that are generated automatically. In order to improve the grammaticality of the generated sentences, we model a global (sentence) level syntactic structure. We couch statistical sentence generation as a spanning tree problem in order to search for the best dependency tree spanning a set of chosen words. We also introduce a new search algorithm for this task that models argument satisfaction to improve the linguistic validity of the generated tree. We treat the allocation of modifiers to heads as a weighted bipartite graph matching problem (also known as the assignment problem), a well studied problem in graph theory. Using BLEU to measure performance on a string regeneration task, we demonstrate an improvement over standard language model baselines, illustrating the benefit of the spanning tree approach incorporating an argument satisfaction model.

Original languageEnglish
Title of host publicationEmpirical Methods in Natural Language Generation - Data-Oriented Methods and Empirical Evaluation
Place of PublicationBerlin; Heidelberg
PublisherSpringer, Springer Nature
Number of pages32
Volume5790 LNAI
ISBN (Print)3642155723, 9783642155727
Publication statusPublished - 2010
Event12th European Workshop on Natural Language Generation, ENLG 2009 - Athens, Greece
Duration: 30 Mar 20093 Apr 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5790 LNAI
ISSN (Print)03029743
ISSN (Electronic)16113349


Other12th European Workshop on Natural Language Generation, ENLG 2009

Fingerprint Dive into the research topics of 'Spanning tree approaches for statistical sentence generation'. Together they form a unique fingerprint.

Cite this