Large Margin Synchronous Generation and its Application to Sentence Compression

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 73–82, Prague, June 2007. c⃝2007 Association for Computational Linguistics Large Margin Synchronous Generation and its Application to Sentence Compression Trevor Cohn and Mirella Lapata School of Informatics University of Edinburgh Edinburgh, United Kingdom {tcohn,mlap}@inf.ed.ac.uk Abstract This paper presents a tree-to-tree transduc- tion method for text rewriting. Our model is based on synchronous tree substitution grammar, a formalism that allows local dis- tortion of the tree topology and can thus naturally capture structural mismatches. We describe an algorithm for decoding in this framework and show how the model can be trained discriminatively within a large margin framework. Experimental results on sentence compression bring significant im- provements over a state-of-the-art model. 1 Introduction Recent years have witnessed increasing interest in text-to-text generation methods for many natural language processing applications ranging from text summarisation to question answering and machine translation. At the heart of these methods lies the ability to perform rewriting operations according to a set of prespecified constraints. For example, text simplification identifies which phrases or sentences in a document will pose reading difficulty for a given user and substitutes them with simpler alternatives (Carroll et al., 1999). Sentence compression pro- duces a summary of a single sentence that retains the most important information while remaining gram- matical (Jing, 2000). Ideally, we would like a text-to-text rewriting sys- tem that is not application specific. Given a parallel corpus of training examples, we should be able to learn rewrite rules and how to combine them in order to generate new text. A great deal of previous work has focused on the rule induction problem (Barzilay and McKeown, 2001; Pang et al., 2003; Lin and Pan- tel, 2001; Shinyama et al., 2002), whereas relatively little emphasis has been placed on the actual gen- eration task (Quirk et al., 2004). A notable excep- tion is sentence compression for which end-to-end rewriting systems are commonly developed (Knight and Marcu, 2002; Turner and Charniak, 2005; Gal- ley and McKeown, 2007; Riezler et al., 2003; Mc- Donald, 2006). The appeal of this task lies in its simplified formulation as a single rewrite operation, namely word deletion (Knight and Marcu, 2002). Solutions to the compression task have been cast mostly in a supervised learning setting (but see Clarke and Lapata (2006a), Hori and Furui (2004), and Turner and Charniak (2005) for unsupervised methods). Rewrite rules are learnt from a parsed parallel corpus and subsequently used to find the best compression from the set of all possible com- pressions for a given sentence. A common assump- tion is that the tree structures representing long sen- tences and their compressions are isomorphic. Con- sequently, the models are not generally applicable to other text rewriting problems since they cannot readily handle structural mismatches and more com- plex rewriting operations such as substitutions or insertions. A related issue is that the tree structure of the compressed sentences is often poor; most al- gorithms …

Content truncated to 500 words