Concept-based Summarization using Integer Linear Programming: From Concept Pruning to Multiple Optimal Solutions

Florian Boudin (1) , Hugo Mougard (1) , Benoit Favre (2, 3)

1 LS2N - équipe TALN - Traitement Automatique du Langage Naturel
2 LIF - Laboratoire d'informatique Fondamentale de Marseille
3 TALEP - Traitement Automatique du Langage Ecrit et Parlé

In concept-based summarization, sentence selection is modelled as a budgeted maximum coverage problem. As this problem is NP-hard, pruning low-weight concepts is required for the solver to find optimal solutions efficiently. This work shows that reducing the number of concepts in the model leads to lower Rouge scores, and more importantly to the presence of multiple optimal solutions. We address these issues by extending the model to provide a single optimal solution, and eliminate the need for concept pruning using an approximation algorithm that achieves comparable performance to exact inference.

Domains: Document and Text Processing

Florian Boudin, Hugo Mougard, Benoit Favre. Concept-based Summarization using Integer Linear Programming: From Concept Pruning to Multiple Optimal Solutions. Conference on Empirical Methods in Natural Language Processing (EMNLP) 2015, Sep 2015, Lisbonne, Portugal. ⟨hal-01203750⟩