Discovering Diverse and Salient Threads in Document Collections

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 710–720, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Discovering Diverse and Salient Threads in Document Collections Jennifer Gillenwater Alex Kulesza Department of Computer and Information Science University of Pennsylvania Philadelphia, PA 19104 {jengi,kulesza,taskar}@cis.upenn.edu Ben Taskar Abstract We propose a novel probabilistic technique for modeling and extracting salient struc- ture from large document collections. As in clustering and topic modeling, our goal is to provide an organizing perspective into otherwise overwhelming amounts of infor- mation. We are particularly interested in revealing and exploiting relationships be- tween documents. To this end, we focus on extracting diverse sets of threads—singly- linked, coherent chains of important doc- uments. To illustrate, we extract research threads from citation graphs and construct timelines from news articles. Our method is highly scalable, running on a corpus of over 30 million words in about four minutes, more than 75 times faster than a dynamic topic model. Finally, the results from our model more closely resemble human news summaries according to several metrics and are also preferred by human judges. 1 Introduction The increasing availability of large document collections has the potential to revolutionize our ability to understand the world. However, the scale and complexity of such collections fre- quently make it difficult to quickly grasp the important details and the relationships between them. As a result, automatic interfaces for data navigation, exploration, aggregation, and analy- sis are becoming increasingly valuable. In this work we propose a novel approach: threading structured document collections. Con- sider a large graph, with documents as nodes and edges indicating relationships, as in Figure 1. Our goal is to find a diverse set of paths (or threads) through the collection that are indi- vidually coherent and together cover the most salient parts. For example, given a collection of academic papers, we might want to identify the most significant lines of research, threading the citation graph to produce chains of impor- tant papers. Or, given news articles connected chronologically, we might want to extract threads of articles to form timelines describing the ma- jor events from the most significant news stories. Top-tier news organizations like The New York Times and The Guardian regularly publish such timelines, but have so far been limited to creat- ing them by hand. Other possibile applications might include discovering trends on social media sites, or perhaps mining blog entries for impor- tant conversations through trackback links. We show how these kinds of threading tasks can be done efficiently, providing a simple, practical tool for representing graph-based data that offers new possibilities compared with existing models. The Topic Detection and Tracking (TDT) pro- gram (Wayne, 2000) has recently led to some research in this direction. Several of TDT’s core tasks, like link detection, topic detection, and topic tracking, can be seen as subroutines for the threading problem. Our work, however, ad- dresses these tasks jointly, using a global prob- …

Content truncated to 500 words