SCIENCE@home

Approximation Strategies for Multi-Structure Sentence Compression

K. Thadani

Published 2014 in Annual Meeting of the Association for Computational Linguistics

ABSTRACT

Sentence compression has been shown to benefit from joint inference involving both n-gram and dependency-factored objectives but this typically requires expensive integer programming. We explore instead the use of Lagrangian relaxation to decouple the two subproblems and solve them separately. While dynamic programming is viable for bigram-based sentence compression, finding optimal compressed trees within graphs is NP-hard. We recover approximate solutions to this problem using LP relaxation and maximum spanning tree algorithms, yielding techniques that can be combined with the efficient bigrambased 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 significant improvement in runtime.

PUBLICATION RECORD

  • Publication year

    2014

  • Venue

    Annual Meeting of the Association for Computational Linguistics

  • Publication date

    2014-06-01

  • Fields of study

    Computer Science

  • Identifiers
    DOI 10.3115/v1/P14-1117
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-48 of 48 references · Page 1 of 1

CITED BY

Showing 1-12 of 12 citing papers · Page 1 of 1