Paper: Polynomial Time Joint Structural Inference for Sentence Compression

ACL ID P14-2054
Title Polynomial Time Joint Structural Inference for Sentence Compression
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2014
Authors

We propose two polynomial time infer- ence algorithms to compress sentences un- der bigram and dependency-factored ob- jectives. The first algorithm is exact and requires O(n 6 ) running time. It extend- s Eisner?s cubic time parsing algorithm by using virtual dependency arcs to link deleted words. Two signatures are added to each span, indicating the number of deleted words and the rightmost kept word within the span. The second algorithm is a fast approximation of the first one. It re- laxes the compression ratio constraint us- ing Lagrangian relaxation, and thereby re- quires O(n 4 ) running time. Experimental results on the popular sentence compres- sion corpus demonstrate the effectiveness and efficiency of our proposed approach.