Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function

Shinsaku Sakaue, Tsutomu Hirao, Masaaki Nishino, Masaaki Nagata

Abstract
Submodular maximization with the greedy algorithm has been studied as an effective approach to extractive summarization. This approach is known to have three advantages: its applicability to many useful submodular objective functions, the efficiency of the greedy algorithm, and the provable performance guarantee. However, when it comes to compressive summarization, we are currently missing a counterpart of the extractive method based on submodularity. In this paper, we propose a fast greedy method for compressive summarization. Our method is applicable to any monotone submodular objective function, including many functions well-suited for document summarization. We provide an approximation guarantee of our greedy algorithm. Experiments show that our method is about 100 to 400 times faster than an existing method based on integer-linear-programming (ILP) formulations and that our method empirically achieves more than 95%-approximation.
Anthology ID:
N18-1157
Volume:
Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)
Month:
June
Year:
2018
Address:
New Orleans, Louisiana
Editors:
Marilyn Walker, Heng Ji, Amanda Stent
Venue:
NAACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
1737–1746
Language:
URL:
https://aclanthology.org/N18-1157
DOI:
10.18653/v1/N18-1157
Bibkey:
Cite (ACL):
Shinsaku Sakaue, Tsutomu Hirao, Masaaki Nishino, and Masaaki Nagata. 2018. Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 1737–1746, New Orleans, Louisiana. Association for Computational Linguistics.
Cite (Informal):
Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function (Sakaue et al., NAACL 2018)
Copy Citation:
PDF:
https://preview.aclanthology.org/nschneid-patch-1/N18-1157.pdf
Note:
 N18-1157.Notes.pdf
PDF Search Note