Approximation Strategies for Multi-Structure Sentence Compression

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 1241–1251, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Approximation Strategies for Multi-Structure Sentence Compression Kapil Thadani Department of Computer Science Columbia University New York, NY 10025, USA kapil@cs.columbia.edu Abstract Sentence compression has been shown to benefit from joint inference involving both n-gram and dependency-factored objec- tives but this typically requires expensive integer programming. We explore instead the use of Lagrangian relaxation to decou- ple the two subproblems and solve them separately. While dynamic programming is viable for bigram-based sentence com- pression, finding optimal compressed trees within graphs is NP-hard. We recover ap- proximate solutions to this problem us- ing LP relaxation and maximum spanning tree algorithms, yielding techniques that can be combined with the efficient bigram- based inference approach using Lagrange multipliers. Experiments show that these approximation strategies produce results comparable to a state-of-the-art integer linear programming formulation for the same joint inference task along with a sig- nificant improvement in runtime. 1 Introduction Sentence compression is a text-to-text genera- tion task in which an input sentence must be transformed into a shorter output sentence which accurately reflects the meaning in the input and also remains grammatically well-formed. The compression task has received increasing attention in recent years, in part due to the availability of datasets such as the Ziff-Davis cor- pus (Knight and Marcu, 2000) and the Edinburgh compression corpora (Clarke and Lapata, 2006), from which the following example is drawn. Original: In 1967 Chapman, who had cultivated a con- ventional image with his ubiquitous tweed jacket and pipe, by his own later admission stunned a party attended by his friends and future Python colleagues by coming out as a homosexual. Compressed: In 1967 Chapman, who had cultivated a conventional image, stunned a party by coming out as a homosexual. Following an assumption often used in compres- sion systems, the compressed output in this corpus is constructed by dropping tokens from the input sentence without any paraphrasing or reordering.1 A number of diverse approaches have been proposed for deletion-based sentence compres- sion, including techniques that assemble the out- put text under an n-gram factorization over the input text (McDonald, 2006; Clarke and Lapata, 2008) or an arc factorization over input depen- dency parses (Filippova and Strube, 2008; Galanis and Androutsopoulos, 2010; Filippova and Altun, 2013). Joint methods have also been proposed that invoke integer linear programming (ILP) formu- lations to simultaneously consider multiple struc- tural inference problems—both over n-grams and input dependencies (Martins and Smith, 2009) or n-grams and all possible dependencies (Thadani and McKeown, 2013). However, it is well- established that the utility of ILP for optimal infer- ence in structured problems is often outweighed by the worst-case performance of ILP solvers on large problems without unique integral solu- tions. Furthermore, approximate solutions can often be adequate for real-world generation sys- tems, particularly in the presence of linguistically- motivated constraints such as those described by Clarke and Lapata (2008), or domain-specific …

Content truncated to 500 words