Improving Grammaticality in Statistical Sentence Generation: Introducing a Dependency Spanning Tree Algorithm with an Argument Satisfaction Model

Proceedings of the 12th Conference of the European Chapter of the ACL, pages 852–860, Athens, Greece, 30 March – 3 April 2009. c⃝2009 Association for Computational Linguistics Improving Grammaticality in Statistical Sentence Generation: Introducing a Dependency Spanning Tree Algorithm with an Argument Satisfaction Model Stephen Wan†‡ Mark Dras† Robert Dale† †Centre for Language Technology Department of Computing Macquarie University Sydney, NSW 2113 swan,madras,rdale@ics.mq.edu.au C´ecile Paris‡ ‡ICT Centre CSIRO Sydney, Australia Cecile.Paris@csiro.au Abstract Abstract-like text summarisation requires a means of producing novel summary sen- tences. In order to improve the grammati- cality of the generated sentence, we model a global (sentence) level syntactic struc- ture. We couch statistical sentence genera- tion as a spanning tree problem in order to search for the best dependency tree span- ning a set of chosen words. We also intro- duce a new search algorithm for this task that models argument satisfaction to im- prove the linguistic validity of the gener- ated tree. We treat the allocation of modi- fiers to heads as a weighted bipartite graph matching (or assignment) problem, a well studied problem in graph theory. Using BLEU to measure performance on a string regeneration task, we found an improve- ment, illustrating the benefit of the span- ning tree approach armed with an argu- ment satisfaction model. 1 Introduction Research in statistical novel sentence generation has the potential to extend the current capabili- ties of automatic text summarisation technology, moving from sentence extraction to abstract-like summarisation. In this paper, we describe a new algorithm that improves upon the grammaticality of statistically generated sentences, evaluated on a string regeneration task, which was first proposed as a surrogate for a grammaticality test by Ban- galore et al. (2000). In this task, a system must regenerate the original sentence which has had its word order scrambled. As an evaluation task, string regeneration re- flects the issues that challenge the sentence gen- eration components of machine translation, para- phrase generation, and summarisation systems (Soricut and Marcu, 2005). Our research in sum- marisation utilises the statistical generation algo- rithms described in this paper to generate novel summary sentences. The goal of the string regeneration task is to re- cover a sentence once its words have been ran- domly ordered. Similarly, for a text-to-text gen- eration scenario, the goal is to generate a sen- tence given an unordered list of words, typically using an n-gram language model to select the best word ordering. N-gram language models appear to do well at a local level when examining word sequences smaller than n. However, beyond this window size, the sequence is often ungrammati- cal. This is not surprising as these methods are un- able to model grammaticality at the sentence level, unless the size of n is sufficiently large. In prac- tice, the lack of sufficient training data means that n is often smaller than the average sentence length. Even if data exists, increasing the size of n corre- sponds to a higher degree polynomial complexity search for the best word sequence. …

Content truncated to 500 words