Fast k-best Sentence Compression
This addresses the computational inefficiency in sentence compression for NLP applications, offering a faster and effective alternative to ILP-based methods.
The paper tackles the slow speed of ILP-based sentence compression by introducing a novel algorithm that generates k-best compressions using local deletion decisions, achieving a two-orders-of-magnitude speed improvement over a recent ILP method while producing better compressions, with minimal quality degradation when moving from single best to top-five results.
A popular approach to sentence compression is to formulate the task as a constrained optimization problem and solve it with integer linear programming (ILP) tools. Unfortunately, dependence on ILP may make the compressor prohibitively slow, and thus approximation techniques have been proposed which are often complex and offer a moderate gain in speed. As an alternative solution, we introduce a novel compression algorithm which generates k-best compressions relying on local deletion decisions. Our algorithm is two orders of magnitude faster than a recent ILP-based method while producing better compressions. Moreover, an extensive evaluation demonstrates that the quality of compressions does not degrade much as we move from single best to top-five results.