START Conference Manager    

Subtree Extractive Summarization via Submodular Maximization

Hajime Morita, Ryohei Sasano, Hiroya Takamura and Manabu Okumura

The 51st Annual Meeting of the Association for Computational Linguistics (ACL 2013)
Sofia, Bulgaria, August 4-9, 2013


This study proposes a text summarization model that simultaneously performs sentence extraction and compression. We translate the text summarization task into a problem of extracting a set of dependency subtrees in the document cluster. We also encode obligatory case constraints as must-link dependency constraints in order to guarantee the readability of the generated summary. In order to handle the subtree extraction problem, we investigate a new class of submodular maximization problem, and a new algorithm that has the approximation ratio 1/2 (1 - 1/e). Our experiments with the NTCIR ACLIA test collections show that our approach outperforms a state-of-the-art algorithm.

START Conference Manager (V2.61.0 - Rev. 2792M)