Text Summarization through Entailment-based Minimum Vertex Cover

Proceedings of the Third Joint Conference on Lexical and Computational Semantics (*SEM 2014), pages 75–80, Dublin, Ireland, August 23-24 2014. Text Summarization through Entailment-based Minimum Vertex Cover Anand Gupta1, Manpreet Kaur2, Adarsh Singh2, Aseem Goel2, Shachar Mirkin3 1Dept. of Information Technology, NSIT, New Delhi, India 2Dept. of Computer Engineering, NSIT, New Delhi, India 3Xerox Research Centre Europe, Meylan, France Abstract Sentence Connectivity is a textual charac- teristic that may be incorporated intelli- gently for the selection of sentences of a well meaning summary. However, the ex- isting summarization methods do not uti- lize its potential fully. The present pa- per introduces a novel method for single- document text summarization. It poses the text summarization task as an opti- mization problem, and attempts to solve it using Weighted Minimum Vertex Cover (WMVC), a graph-based algorithm. Tex- tual entailment, an established indicator of semantic relationships between text units, is used to measure sentence connectivity and construct the graph on which WMVC operates. Experiments on a standard sum- marization dataset show that the suggested algorithm outperforms related methods. 1 Introduction In the present age of digital revolution with pro- liferating numbers of internet-connected devices, we are facing an exponential rise in the volume of available information. Users are constantly fac- ing the problem of deciding what to read and what to skip. Text summarization provides a practical solution to this problem, causing a resurgence in research in this field. Given a topic of interest, a standard search of- ten yields a large number of documents. Many of them are not of the user’s interest. Rather than go- ing through the entire result-set, the reader may read a gist of a document, produced via summa- rization tools, and then decide whether to fully read the document or not, thus saving a substan- tial amount of time. According to Jones (2007), a summary can be defined as “a reductive trans- formation of source text to summary text through content reduction by selection and/or generaliza- tion on what is important in the source”. Summa- rization based on content reduction by selection is referred to as extraction (identifying and includ- ing the important sentences in the final summary), whereas a summary involving content reduction by generalization is called abstraction (reproduc- ing the most informative content in a new way). The present paper focuses on extraction-based single-document summarization. We formulate the task as a graph-based optimization problem, where vertices represent the sentences and edges the connections between sentences. Textual en- tailment (Giampiccolo et al., 2007) is employed to estimate the degree of connectivity between sen- tences, and subsequently to assign a weight to each vertex of the graph. Then, the Weighted Mini- mum Vertex Cover, a classical graph algorithm, is used to find the minimal set of vertices (that is – sentences) that forms a cover. The idea is that such cover of well-connected vertices would cor- respond to a cover of the salient content of the doc- ument. The rest of the paper is organized as follows: …

Content truncated to 500 words