Approximation Strategies for Multi-Structure Sentence Compression

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.