Inducing Temporal Graphs

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 189–198, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Inducing Temporal Graphs Philip Bramsen Pawan Deshpande Yoong Keok Lee Regina Barzilay MIT CSAIL MIT CSAIL DSO National Laboratories MIT CSAIL bramsen@mit.edu pawan@mit.edu lyoongke@dso.org.sg regina@csail.mit.edu Abstract We consider the problem of constructing a directed acyclic graph that encodes tem- poral relations found in a text. The unit of our analysis is a temporal segment, a frag- ment of text that maintains temporal co- herence. The strength of our approach lies in its ability to simultaneously optimize pairwise ordering preferences and global constraints on the graph topology. Our learning method achieves 83% F-measure in temporal segmentation and 84% accu- racy in inferring temporal relations be- tween two segments. 1 Introduction Understanding the temporal flow of discourse is a significant aspect of text comprehension. Con- sequently, temporal analysis has been a focus of linguistic research for quite some time. Tem- poral interpretation encompasses levels ranging from the syntactic to the lexico-semantic (Re- ichenbach, 1947; Moens and Steedman, 1987) and includes the characterization of temporal dis- course in terms of rhetorical structure and prag- matic relations (Dowty, 1986; Webber, 1987; Pas- sonneau, 1988; Lascarides and Asher, 1993). Besides its linguistic significance, temporal analysis has important practical implications. In multidocument summarization, knowledge about the temporal order of events can enhance both the content selection and the summary generation pro- cesses (Barzilay et al., 2002). In question an- swering, temporal analysis is needed to determine when a particular event occurs and how events re- late to each other. Some of these needs can be addressed by emerging technologies for temporal analysis (Wilson et al., 2001; Mani et al., 2003; Lapata and Lascarides, 2004; Boguraev and Ando, 2005). This paper characterizes the temporal flow of discourse in terms of temporal segments and their ordering. We define a temporal segment to be a fragment of text that does not exhibit abrupt changes in temporal focus (Webber, 1988). A seg- ment may contain more than one event or state, but the key requirement is that its elements maintain temporal coherence. For instance, a medical case summary may contain segments describing a pa- tient’s admission, his previous hospital visit, and the onset of his original symptoms. Each of these segments corresponds to a different time frame, and is clearly delineated as such in a text. Our ultimate goal is to automatically construct a graph that encodes ordering between temporal segments. The key premise is that in a coherent document, temporal progression is reflected in a wide range of linguistic features and contextual dependencies. In some cases, clues to segment or- dering are embedded in the segments themselves. For instance, given a pair of adjacent segments, the temporal adverb next day in the second seg- ment is a strong predictor of a precedence relation. In other cases, we can predict the right order be- tween a pair of segments by analyzing their rela- tion to other …

Content truncated to 500 words