A Survey on Temporal Reasoning for Temporal Information Extraction from Text (Extended Abstract)

1 Introduction

Human language is filled with cues about the timing of the events that we communicate about. Temporal Information Extraction (TIE) is the process of automatically extracting temporal cues from text, with the goal to construct a (possibly underspecified) timeline of events from them.

TIE not only plays a major role in the general problem of natural language understanding (NLU), but is also used in many applications: information retrieval [Campos et al., 2015], question answering [Meng et al., 2017], and multidocument summarization [Ng et al., 2014], and has great potential in the clinical domain, for applications like patient timeline visualization [Jung et al., 2011], forecasting treatment effects [Zhou and Hripcsak, 2007], and patient selection for clinical trials [Raghavan et al., 2014]. Because of the strong structure of time, and the great variation in the types of temporal cues we can express in language, a central challenge in TIE is how to combine all these separate cues into a single coherent temporal ordering of the described events. To achieve this, temporal reasoning is of vital importance. We define Temporal Reasoning (TR) in the context of TIE as the process of combining different (annotated or extracted) temporal cues to derive additional temporal information about the text. TR is crucial for TIE and has already been exploited widely in the research community in all stages of TIE model construction: annotation, pre-processing, model training, inference, and evaluation.

∗This paper is an extended abstract of an article in the Journal of Artificial Intelligence Research [Leeuwenberg and Moens, 2019].

To cover the evolution of TR approaches for TIE in parallel with the popularization of using machine learning (ML) methods for natural language processing (NLP), the focus of this survey lies on the research on TR for TIE systems from the past three decades. We abstract from what linguistic features are successful for TIE systems, as this is discussed in depth by [Derczynski, 2017], and can be considered complementary to the focus of the survey. This extended abstract aims to capture the most important elements and conclusions from the original article [Leeuwenberg and Moens, 2019].

In the context of the interesting and important new developments in the past years this article provides the following contributions:

• An introduction to the various types of temporal information in language, and a brief explanation introducing the background on TR for TIE required for the latest state-of-the-art TIE models.
• An overview of the various ways in which TR has been exploited in TIE models over the past decades.
• A distillation of the most important conclusions to successfully incorporate TR in a TIE system and some promising directions for future work.

2 Temporal Cues in Language

It is important to study the types of temporal information that can be expressed in language because the different cues need to be combined by a TR system in order to build a complete temporal overview of the text. The most common interpretation of events on the timeline is as an interval (some expressions may refer to sets of events/intervals, or very short almost instantly occurring events). The span of the interval corresponds to the time that the event takes place. In this section, we give a short exemplified overview of different temporal cues in language to show what types of temporal information the cues can provide, i.e., in what way the cues may constrain the position of event intervals on the timeline.

Temporal cues can refer to various components of the event intervals: the entire interval, but also just its start, end, or duration. For instance, in Ex. 1, the duration of the antibiotics administration is given (10 days), and so is its start time (sometime on the 2nd of June). However, for the improvement in respiratory status only the end time is mentioned explicitly (last 2 days of the antibiotics administration).

Ex. 1 Antibiotics were started on 6/2 and continued for 10 days. Respiratory status improved up til the last 2 days.

The type of information given for each component can also differ: it can be absolute (e.g., in Ex. 1, the duration of the antibiotics of 10 days), or relative to other intervals (e.g., in Ex. 2 the start time of the third set is after the first two). Additionally, the information can be definite, with clear interpretable timings (e.g., in Ex. 2, the duration of 28 minutes), or indefinite, using vague quantification (in Ex. 2, the duration of the first two sets, each nearly an hour).

Ex. 2 After the grueling duels of the first two sets, which each had taken nearly an hour, Nadal won the third set in 28 minutes.

Even with all these explicit cues, world knowledge about the typical order of events, their durations, and even typical time between events may be needed to properly interpret the temporal meaning that is to be conveyed (e.g., although not explicitly mentioned, one would assume that the third set took place on the same day as the first two). Finally, temporal information provided through language is generally underspecified (e.g., based on the example texts, we don't know in what year any of the events took place). A good TR system should be able to flexibly incorporate all these different types of information, and possibly their uncertainty, to come to the timeline that is to be conveyed by the writer.

3 Reasoning with Intervals and Points

The most popular TR framework used in TIE is Allen's interval algebra (AIA) [Allen, 1983]. AIA is based on a set of thirteen mutually exclusive basic interval relations (shown in Fig. 1) that can be assigned to any pair of definite intervals

(where relative positions of start and end-points are known). If for two intervals x and y information about the relative positions of their start and end-points is incomplete (i.e., their relation is indefinite, as in Fig. 2) a general Allen relation can be assigned, expressed as the disjunction of all possible basic relations, given the information provided. The full AIA covers the powerset of all thirteen basic relations, comprising 2 13 = 8192 relations.

To infer new relations from a graph of general Allen relations between different events, a composition table is used, containing transitivity rules for all basic relations, i.e., it shows for any pair of connected relations r1(x, y) and r2(y, z), what relation r3(x, z) could be inferred. For the full AIA, computing all inferrable relations (taking the transitive closure) is, like checking consistency, NP-complete [Vilain et al., 1990], making full AIA impractical for TIE systems. Many TIE systems that use TR are limited to using basic relations (i.e., definite relations). Although hardly used in TIE systems, many tractable sub-fragments of AIA exist [Krokhin et al., 2003]. Some of which focus on integrating quantitative reasoning [Meiri, 1996] or uncertainty [Schockaert and De Cock, 2008]. A major insight on which many efficient TR algorithms are built is the fact that the basic Allen relations can be expressed as sets of point-algebraic relations (<, =, >), as shown in Fig. 1. Point algebra (PA) can express each basic Allen relation as a conjunctive set of point-wise relations between the starts and endings of the intervals. For example, x {equals} y can be expressed by the conjunctive set {x- = y-, x+ = y+}, i.e., if intervals x and y are equal, then their start and endings are also equal (and vice-versa). They also allow expression of many indefinite relations (e.g., the one from Fig. 2, as {x- < y-, x+ > y-}). Reasoning in PA requires a much smaller transitivity table, which contributes to its efficiency, important for practical TR systems.

4 Annotation Schemes

The scheme for temporal annotation in text steers the types of temporal cues that can be extracted by TIE systems, and consequently how TR can be exploited.

The most popular scheme is TimeML [Pustejovsky et al., 2003], used as the basis for many corpora, and for TempEval, a series of shared tasks on TIE evaluation that resulted in many of the existing TIE systems [Verhagen et al., 2007]. The core TimeML concepts are event expressions and time expressions (timex). Event expressions refer to events in the real world, and timex refer to calendar dates, times, and definite durations, among others. In TimeML, events and timex expressions are temporally connected through interval relations, called temporal links (TLinks), approximately following Allen's basic interval relations, consequently focusing on definite information. To go beyond the focus on explicit and definite information in TimeML, many interesting proposals have been made: to include a vague relation to annotate indefinite relations [Cassidy et al., 2014], to annotate point-wise relations between start and end points of events instead of basic interval relations [Ning et al., 2018], annotation of durations for all events (not only for events with an explicit definite duration timex as in TimeML) [Pan et al., 2006], and to annotate temporal position of events on the absolute calendar instead of by interval relations [Reimers et al., 2016], as pair-wise temporal relation annotation is a difficult task for annotators [Derczynski, 2016]. These proposals provide new opportunities for further exploitation of TR.

5 Survey of Current Approaches

This section desribes how TR has been incorporated in existing TIE systems throughout the steps of model development: annotation, data pre-processing, training and prediction, and evaluation. This abstract focuses purely on the task of temporal relation extraction among events and timex, as TR plays a large role in this task, and performance metrics are generally lower compared to event and timex extraction.

5.1 Annotation &Data Preprocessing

A widely recognized problem in temporal annotation, is that annotators regularly miss temporal cues in the text, especially when annotating TLinks between pairs of events, as there are so many possible relations to annotate. [Verhagen, 2005] argue that not all event-pairs are equally useful to annotate, as some can be inferred with TR from earlier annotations. Another motivation to exploit TR during annotation is that annotators sometimes annotate temporally inconsistent graphs, which impedes training of TIE systems.

A frequently made TR-based preprocessing step is to calculate the transitive closure over the annotated relations, to obtain a more dense graph. The effect of temporal closure on performance for models that use no TR during prediction is ambivalent. It may improve performance [Mani et al., 2006], or decrease performance [Tatu and Srikanth, 2008]. However, when using a model that exploits TR also during prediction, data expansion through a temporal closure can be beneficial [Chambers and Jurafsky, 2008].

5.2 Training and Prediction

To enhance temporal relation extraction models, TR can be integrated during training, and prediction. There are various ways how integration of TR in training and prediction can improve TIE models: (1) ensure temporal consistency among predicted relations, and (2) to constrain the output space and improve prediction accuracy.

Greedy Inference. Two greedy approaches have been proposed to construct a graph of temporal relations: relations are added one-by-one, in a certain order, checking temporal consistency after each addition. The order can be natural reading order, or follow the score from a local classifier (best first). Both approaches improved results over absence of TR, the last surpassing the first [Bramsen et al., 2006].

Post-Hoc Conflict Resolution. Another approach is to first predict the full graph with a local model, and detect and resolve inconsistencies afterwards, by removing conflicting edges based on confidence [Verhagen and Pustejovsky, 2008; Tatu and Srikanth, 2008] among others. Most works report a positive impact of this method, but differ in how they remove edges. It could be interesting to compare these to each other in more detail.

Sieve-Level and Stacked Inference. The sieve-based method [Chambers et al., 2014] is flexible in incorporation of both rule-based and machine learning components. This approach extract TLinks in consecutive phases by separate model components (or sieves). Each sieve extracts TLinks, using the original input text, and the outputs from earlier sieves. TR is incorporated by taking a transitive closure after applying each sieve. This prevents later sieves from assigning TLinks that are inconsistent with those extracted by earlier sieves. Similar approaches have been adopted by [McDowell et al., 2017], and [Mirza and Tonelli, 2016], who report an increase in recall (and F1) due to sieve-level TR.

Much alike are methods that stack learners on top of each other to correct mistakes from earlier stages [Laokulrat et al., 2015], which can even be trained jointly across stacks [Meng and Rumshisky, 2018].

Markov Logic Networks. Another important method for TR-based prediction are Markov Logic Networks (MLN), first explored for TIE by [Yoshikawa et al., 2009]. A major difference between MLN and the methods mentioned earlier, is that instead of combining locally trained models in a global inference setting, MLN also incorporate the temporal constraints in training. The weights for TR constraints allow the model to learn soft correlations between TLinks. Model different transitivity rules with MLN, [Yoshikawa et al., 2009] show that incorporating TR during training and prediction outperforms local models.

Integer Linear Programming. Where MLN use soft constraints, integer linear programming (ILP), a method for constrained optimization, uses hard constraints to cut off large areas from the search space, which can result in faster inference [Mojica and Ng, 2016]. ILP for TR-based prediction was first proposed by [Bramsen et al., 2006], to maximize the sum of pair-wise classifier scores under TR-based constraints. ILP

has been adopted widely and successfully for TIE. In contrast to many, [Denis and Muller, 2011] formulated their ILP objective in PA for more efficient TR. Recent approaches not only use ILP during prediction, but also during training, combining ILP with a structured perceptron [Leeuwenberg and Moens, 2017; Ning et al., 2017].

Direct TimelineModels. Recently, a new approach to temporal event ordering was proposed [Leeuwenberg and Moens, 2018]. Instead of predicting TLinks among events and temporal expressions, their model predicts start and end points of events such that their order satisfies the annotated TLinks. Prediction time of this approach is linear in the number of events, in contrast to predicting a graph of TLinks, which is quadratic or requires pruning. To train their model they exploit TR to convert TLinks to sets of PA constraints.

5.3 Evaluation

A problem in evaluation of TIE, is that the same timeline can be represented by different sets of relations: if a system predicts BEFORE(x, y) it should not be penalized if the ground truth is AFTER(y, x). For this, taking a temporal closure over the predicted and ground truth graphs has been proposed, in combination with different ways to weigh original vs. inferred relations [Setzer et al., 2003; Tannier and Muller, 2011; UzZaman and Allen, 2011], of which the temporal awareness metric [UzZaman and Allen, 2011] is the most widely used evaluation metric.

6 Conclusions and FutureWork

In this abstract, we provide a short demonstration of various types of temporal information in language, briefly introduced the most frequently used framework in TR for TIE, and reviewed different methods to exploit TR for constructing TIE models, distilling the most widely confirmed conclusions.

In closing, it is clear that TR is crucial for TIE, and widely used in all aspects of model construction: annotation, data preprocessing, training, prediction, and evaluation. However, most current research on TIE still addresses sub-fragments of the complete TIE problem, focusing on extraction of specific types of temporal cues, instead of extracting all cues jointly which would allow them to complement each other. Consequently, it remains an open research question how to perform efficient and expressive TR involving all types of temporal cues. We believe to answer this question, a flexible, expressive and efficient reasoning framework is required. For this, we believe important directions of research are pointbased reasoning approaches, striking a good balance between efficiency and expressiveness, and (deep) machine learning methods, to facilitate flexibility in model construction, multitask learning, and sharing of representations.

Acknowledgements

This work was supported by the ERC Advanced Grant CALCULUS (788506), and by the IWT-SBO project ACCUMULATE (150056).