Chambers and Jurafsky, Jointly combining implicit constraints improves temporal ordering, EMNLP 2008

Citation

Jointly combining implicit constraints improves temporal ordering, by N. Chambers, D. Jurafsky. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2008.

Online version

This paper is available online [1].

Summary

Unlike earlier works on temporal ordering of events that focus more on improving local, pairwise ordering of events while ignoring possible temporal contradictions in the global space of events, this paper is one of the earliest work that presents the idea of using global constraints to better inform local decisions on temporal ordering of events in text. Two types of global constraints are used: transitivity (A before B and B before C implies A before C) and time expression normalization (e.g. last Tuesday is before today).

The constraints are first used to create more densely connected temporal network of events. Then they are enforced over this temporal network of events using Integer Linear Programming to ensure global consistency of local ordering.

Brief description of the method

The model has two components: (1) pairwise classifier between events, (2) global constraint satisfaction layer that maximizes the confidence scores from the classifier.

In the first component, Support Vector Machine (SVM) classifier is used. Using features varying from POS tags and lexical features surrounding the event to tense, grammatical aspect features of the events, probabilities of temporal relations between pairwise events are computed. These scores are then used as confidence scores to choose an optimal global ordering.

In the second component, the ILP uses the following objective function:

$max\sum _{i}\sum _{j}p_{ij}x_{ij}\,\!$

with the constraints:

$\forall _{i}\forall _{j}{x_{ij}}\in {0,1}$

$\forall _{i}{x_{i1}}+{x_{i2}}+...+{x_{im}}=1\,\!$

${x_{ia}}+{x_{jb}}-{x_{kc}}<=1\,\!$

where ${x_{ij}}\,\!$ represents the ith pair of events classified into the jth relation of m relations.

The first constraint simply says that each variable must be 0 or 1. The second constraint says that a pair of events cannot have two relations at the same time. The third constraint is added for connected pairs of events $i,j,k\,\!$, for each transitivity condition that infers relation $c\,\!$ given $a\,\!$ and $b\,\!$.

Prior to running the two components, the set of training relations is expanded to create a more well-connected network of events. One way to expand it is to perform temporal reasoning over the document's time expression (e.g. yesterday is before today) to add new relations between times. Once new time-time relations are added, transitive closure is conducted through transitive rules that creates new connections in the network, such as:

A simultaneous B $\land$ A before C $\to$ B before C

Experimental Result

The experiment is done on the task of classifying temporal relations between events into before, after, or vague (unknown) relations on the TimeBank Corpus. These are the core relations in the TempEval-07 temporal ordering challenge.

Training and testing are done using 10-fold cross validation and micro-averaged accuracies. The method shows 3.6% absolute increase in the accuracy of before/after classification over the local, pairwise classification model. This improvement is statistically significant (p < 0.000001, Mc-Nemar's test, 2-tailed).

Using time expression normalization to create new relations between time expressions, transitive closure over the original set of temporal relations in the corpus, and additional event-event temporal information from Berthard et al. (2007), the method shows an 81% increase in the number of relations in the corpus to train on.

Discussion

Both the increased connectivity of the corpus and the global inference contributed to the improved performance. Global inference alone on the original set of temporal relations in the corpus shows no improvement over pairwise classification model. This is due to the sparseness of the corpus (since tagging is done manually, the vast majority of possible relations are untagged). Global constraints cannot assist local decisions if the graph is not connected. This highlights the importance of time expression normalization and transitive closure to make the corpus more well connected prior to conducting global inference.

Unfortunately, this paper does not differentiate between improvement in performance contributed by the increased connectivity and the improvement contributed by the global inference. Could the increased performance be contributed solely by the increased connectivity of the graph? There is a need for a separate evaluation on the accuracy of relations inferred using only pairwise classification and transitive closure (without global inference).

Related papers

An interesting follow-up paper is Yoshikawa 2009 jointly identifying temporal relations with markov logic which uses Markov Logic instead of Integer Linear Programming to do a softer (non-deterministic) joint inference.

Another related paper is Denis and Muller, Predicting Globally-Coherent Temporal Structures from Texts via Endpoint Inference and Graph Decomposition, IJCAI 2011 which attempts to classify all types of temporal relations (not just before/after) in TimeBank Corpus by first translating these 13 temporal interval relations to their end points, making the set of constraints much smaller for the Integer Linear Programming to deal with, while preserving the same temporal information.