Paper: Approximation Strategies for Multi-Structure Sentence Compression

ACL ID P14-1117
Title Approximation Strategies for Multi-Structure Sentence Compression
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2014

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 form...