Difference between revisions of "Denis and Muller, Predicting Globally-Coherent Temporal Structures from Texts via Endpoint Inference and Graph Decomposition, IJCAI 2011"

From Cohen Courses
Jump to navigationJump to search
 
(14 intermediate revisions by the same user not shown)
Line 14: Line 14:
 
Like [[RelatedPaper::Yoshikawa 2009 jointly identifying temporal relations with markov logic|Yoshikawa et al. (2009)]], this [[Category::paper]] is a follow up paper to [[RelatedPaper::Chambers and Jurafsky, Jointly combining implicit constraints improves temporal ordering, EMNLP 2008|Chambers and Jurafsky (2008)]] that focuses on using global inference to improve local, pairwise [[AddressesProblem::temporal ordering]] of events in text. Similar to [[RelatedPaper::Chambers and Jurafsky, Jointly combining implicit constraints improves temporal ordering, EMNLP 2008|Chambers and Jurafsky (2008)]], this paper formulates the global inference of temporal ordering as a constraint optimization problem, which can be then given an exact solution using [[UsesMethod::Integer Linear Programming]] (ILP). [[RelatedPaper::Chambers and Jurafsky, Jointly combining implicit constraints improves temporal ordering, EMNLP 2008|Chambers and Jurafsky (2008)]] however, restricts themselves to only predicting precedence relations (''before''/''after'') as ILP becomes impractical when considering all possible interval relations due to the combinatorial number of variables and constraints needed to represent them. The main contribution of this paper is in reducing the number of variables and constraints needed to represent all interval relations, by translating these temporal intervals into their end points, thus preserving the same temporal information while reducing the number of variables and constraints to handle. Additional gain in efficiency is achieved by decomposing the temporal graph and enforcing temporal coherence on the subsets of the graph.  
 
Like [[RelatedPaper::Yoshikawa 2009 jointly identifying temporal relations with markov logic|Yoshikawa et al. (2009)]], this [[Category::paper]] is a follow up paper to [[RelatedPaper::Chambers and Jurafsky, Jointly combining implicit constraints improves temporal ordering, EMNLP 2008|Chambers and Jurafsky (2008)]] that focuses on using global inference to improve local, pairwise [[AddressesProblem::temporal ordering]] of events in text. Similar to [[RelatedPaper::Chambers and Jurafsky, Jointly combining implicit constraints improves temporal ordering, EMNLP 2008|Chambers and Jurafsky (2008)]], this paper formulates the global inference of temporal ordering as a constraint optimization problem, which can be then given an exact solution using [[UsesMethod::Integer Linear Programming]] (ILP). [[RelatedPaper::Chambers and Jurafsky, Jointly combining implicit constraints improves temporal ordering, EMNLP 2008|Chambers and Jurafsky (2008)]] however, restricts themselves to only predicting precedence relations (''before''/''after'') as ILP becomes impractical when considering all possible interval relations due to the combinatorial number of variables and constraints needed to represent them. The main contribution of this paper is in reducing the number of variables and constraints needed to represent all interval relations, by translating these temporal intervals into their end points, thus preserving the same temporal information while reducing the number of variables and constraints to handle. Additional gain in efficiency is achieved by decomposing the temporal graph and enforcing temporal coherence on the subsets of the graph.  
  
The proposed method is evaluated through experiment on [[UsesDataset::TimeBank Corpus]] and achieves similar accuracy as [[RelatedPaper::Tatu_and_Srikanth_2008_Experiments_with_reasoning_for_temporal_relations_between_events_COLING|Tatu and Srikanth (2008)]] which infers temporal relations while preserving consistency. Tatu and Srikanth (2008) however, only performs classification on 6 of the 13 possible temporal relations. This paper on the other hand, classifies all 13 temporal relations.
+
The proposed method is evaluated through experiments on the [[UsesDataset::TimeBank Corpus]] and achieves similar accuracy as [[RelatedPaper::Tatu_and_Srikanth_2008_Experiments_with_reasoning_for_temporal_relations_between_events_COLING|Tatu and Srikanth (2008)]] which infers temporal relations while preserving consistency. Tatu and Srikanth (2008) however, only performs classification on 6 of the 13 possible temporal relations. This paper on the other hand, classifies all 13 temporal relations. [[RelatedPaper::Chambers and Jurafsky, Jointly combining implicit constraints improves temporal ordering, EMNLP 2008|Chambers and Jurafsky (2008)]] achieves an accuracy of 70%, however they only perform classifications on 2 temporal relations (accuracy in these three papers is actually a recall measure).
  
 
== Brief description of the method ==
 
== Brief description of the method ==
Line 40: Line 40:
 
and other constraints.  
 
and other constraints.  
  
To achieve more efficiency, the temporal graph is decomposed into subsets so as to limit the coherence enforcement to relevant subgroups of events.
+
To achieve even more efficiency, the temporal graph is decomposed into subsets so as to restrict the constrained prediction to relevant subgroups of events. Two different decompositions are tried:
 +
 
 +
* decomposition based on human annotations - human annotations in the corpus are scattered and events appear in separate, self-connected components in the graph. The constrained prediction is restricted to these connected components
 +
* decomposition based on dates that appear in the same sentence as the events - events are grouped based on dates they are closest to in the sentence
  
 
== Experimental Result ==
 
== Experimental Result ==
  
The experiment is done using the data from [http://www.timeml.org/tempeval/ TempEval] temporal ordering challenge, with the tasks of classifying temporal relations between events and time expressions (Task A), between events and the DCT (Task B), and between events in two consecutive sentences (Task C). Temporal relations are classified into one of 6 classes: ''BEFORE'', ''OVERLAP'', ''AFTER'', ''BEFORE-OR-OVERLAP'', ''OVERLAP-OR-AFTER'', and ''VAGUE''. Training and inference algorithms are provided by [http://code.google.com/p/thebeast/ Markov thebeast], a Markov Logic interpreter tailored for NLP applications. Accuracy for measuring performance is defined as:
+
The experiment is done on [[UsesDataset::TimeBank Corpus]] using 5-fold cross validation. Three sets of experiments are conducted to evaluate:
 +
 
 +
* the effectiveness of relations inferred using only the transitive closure of original relations in the corpus  (as described in [[Chambers_and_Jurafsky,_Jointly_combining_implicit_constraints_improves_temporal_ordering,_EMNLP_2008|Chambers and Jurafsky (2008)]])
 +
* the effectiveness of using ILP point model on the entire temporal graph
 +
* the effectiveness of using ILP point model with graph decompositions
  
<math>\frac{{C_a} + {C_b} + {C_c}} {{G_a} + {G_b} + {G_c}}\,\!</math>
+
When only transitive closure is done, an accuracy of 26% is achieved. When ILP is used, an accuracy of almost 50% is achieved. This is the accuracy achieved by [[RelatedPaper::Tatu_and_Srikanth_2008_Experiments_with_reasoning_for_temporal_relations_between_events_COLING|Tatu and Srikanth (2008)]] on the temporal predictions where they preserve consistency. However, this paper uses the whole set of 13 relations while [[RelatedPaper::Tatu_and_Srikanth_2008_Experiments_with_reasoning_for_temporal_relations_between_events_COLING|Tatu and Srikanth (2008)]] has only six. When predictions is limited on subsets of decomposed graph, ILP accuracy increases to 54%, perhaps benefiting from the more relevant context of the graph.
  
where <math>{C_a}</math>, <math>{C_b}</math>, <math>{C_c}</math> are the number of correctly identified labels in each task, and <math>{G_a}</math>, <math>{G_b}</math> and <math>{G_c}</math> are the number of gold labels of each task.
+
== Related papers ==
  
The paper shows that by incorporating global constraints that hold between temporal relations predicted in Task A, B, and C, the accuracy for all three tasks can be improved significantly. For two out of the three tasks, the approach in this paper achieves the best accuracy by at least 2% more than other approaches. For task B, the approach's accuracy is less than that of rule-based approach; however it is better than all other machine learning approaches.
+
The approach in this paper is similar to that of an earlier work by [[Chambers_and_Jurafsky,_Jointly_combining_implicit_constraints_improves_temporal_ordering,_EMNLP_2008|Chambers and Jurafsky (2008)]] that proposes to use global framework based on [[Integer_Linear_Programming|Integer Linear Programming (ILP)]] to jointly infer temporal relations between events.  
  
== Related papers ==
+
However, while [[Chambers_and_Jurafsky,_Jointly_combining_implicit_constraints_improves_temporal_ordering,_EMNLP_2008|Chambers and Jurafsky (2008)]] only performs classification on 2 relations, this paper performs classification on all 13 temporal relations in [[UsesDataset::TimeBank Corpus]].
  
The approach in this paper is similar to that of an earlier work by [[Chambers_and_Jurafsky,_Jointly_combining_implicit_constraints_improves_temporal_ordering,_EMNLP_2008|Chambers and Jurafsky (2008)]] that proposes to use global framework based on [[Integer_Linear_Programming|Integer Linear Programming (ILP)]] to jointly infer temporal relations between events. [[Chambers_and_Jurafsky,_Jointly_combining_implicit_constraints_improves_temporal_ordering,_EMNLP_2008|Chambers and Jurafsky (2008)]] show that adding global inference improves the accuracy of the inferred temporal relations. However they only focus on event-event temporal relations while this paper also jointly predicts temporal order between events and time expressions, and between events and document creation time.  
+
This paper also fills up the gap on [[Chambers_and_Jurafsky,_Jointly_combining_implicit_constraints_improves_temporal_ordering,_EMNLP_2008|Chambers and Jurafsky (2008)]]'s evaluation by computing accuracy on inferred relations using only transitive closure. This evaluation was not done in [[Chambers_and_Jurafsky,_Jointly_combining_implicit_constraints_improves_temporal_ordering,_EMNLP_2008|Chambers and Jurafsky (2008)]], thus casting a question on whether the improved performance observed in their paper is attributed solely to the transitive closure that makes the graph more well connected or to the global inference. Unfortunately however, since these two papers conduct different classifications: one on just 2 relations while the other on all 13 relations, the evaluation results are not directly comparable. In itself, this paper shows that adding ILP global inference on the transitively closed graph improves accuracy, confirming the merit of doing global inference for better temporal ordering of events in text.  
  
Secondly, [[Chambers_and_Jurafsky,_Jointly_combining_implicit_constraints_improves_temporal_ordering,_EMNLP_2008|Chambers and Jurafsky (2008)]] combines the output of local classifiers using [[Integer_Linear_Programming|ILP]] framework while this paper uses [[Markov_Logic_Networks|Markov Logic Networks]] which represents global constraints through the addition of weighted first order logic formulae. The advantage is that it allows for representation of non-deterministic rules that tend to hold between temporal relations but do not always have to. For example, if A happens before B and B overlaps with C, then there is a good chance that A also happens before C, but this is not always the case. The learned weights of the rules allow for ''soft'' enforcement of the constraints.
+
This paper also shows the improved accuracy obtained through decomposing the temporal graph into more relevant subsets and conducting inference on them. This potentially shows that although a global inference helps in improving accuracy of local decisions, a more focused "semi-global" inference might be better.

Latest revision as of 00:49, 30 September 2011

Reviews of this paper

Citation

Predicting Globally-Coherent Temporal Structures from Texts via Endpoint Inference and Graph Decomposition, by P. Denis, P. Muller. In Proceedings of IJCAI, 2011.

Online version

This Paper is available online [1].

Summary

Like Yoshikawa et al. (2009), this paper is a follow up paper to Chambers and Jurafsky (2008) that focuses on using global inference to improve local, pairwise temporal ordering of events in text. Similar to Chambers and Jurafsky (2008), this paper formulates the global inference of temporal ordering as a constraint optimization problem, which can be then given an exact solution using Integer Linear Programming (ILP). Chambers and Jurafsky (2008) however, restricts themselves to only predicting precedence relations (before/after) as ILP becomes impractical when considering all possible interval relations due to the combinatorial number of variables and constraints needed to represent them. The main contribution of this paper is in reducing the number of variables and constraints needed to represent all interval relations, by translating these temporal intervals into their end points, thus preserving the same temporal information while reducing the number of variables and constraints to handle. Additional gain in efficiency is achieved by decomposing the temporal graph and enforcing temporal coherence on the subsets of the graph.

The proposed method is evaluated through experiments on the TimeBank Corpus and achieves similar accuracy as Tatu and Srikanth (2008) which infers temporal relations while preserving consistency. Tatu and Srikanth (2008) however, only performs classification on 6 of the 13 possible temporal relations. This paper on the other hand, classifies all 13 temporal relations. Chambers and Jurafsky (2008) achieves an accuracy of 70%, however they only perform classifications on 2 temporal relations (accuracy in these three papers is actually a recall measure).

Brief description of the method

The paper proposes two steps method for temporal ordering of events: (1) learn a classifier which outputs a score for each event pair and their temporal relation, (2) combine these local scores with coherence constraints on the temporal graph within a global optimization problem using Integer Linear Programming (ILP).

Being an NP-hard problem, inference in ILP is sensitive to its number of variables and constraints. In this case, these numbers are exponential in the number of temporal relations used. For ILP to be able to handle all 13 temporal relations specified in TimeBank Corpus, the paper proposes to first translate these temporal relations intervals into their end points; thus reducing the number of relations from 13 to 5. This reduced number of temporal relations result in 50 times less number of constraints needed to represent global temporal coherence in while preserving the temporal information. The translation between each pair of events' temporal relations to points are shown in the table below: (inverses and simultaneous relation are not shown)

Allen.png

Where the intervals are, in Allen (1983)'s notation: b as in BEFORE, m as in MEET (IBEFORE or immediately before), o as in OVERLAP, s as in START, d as in DURING, and f as in FINISH. For each event pair , four relations between their endpoints are considered: , , , as shown in the table.

The variables in ILP can then be represented in terms of the endpoints as triplets: where p and q are endpoints and r is a possible temporal relation over them. The weights on the variables, are obtained from classifier scores. The objective function is defined as:

subject to the constraints:

and the constraint that at most one base relation can hold between 2 points:

and other constraints.

To achieve even more efficiency, the temporal graph is decomposed into subsets so as to restrict the constrained prediction to relevant subgroups of events. Two different decompositions are tried:

  • decomposition based on human annotations - human annotations in the corpus are scattered and events appear in separate, self-connected components in the graph. The constrained prediction is restricted to these connected components
  • decomposition based on dates that appear in the same sentence as the events - events are grouped based on dates they are closest to in the sentence

Experimental Result

The experiment is done on TimeBank Corpus using 5-fold cross validation. Three sets of experiments are conducted to evaluate:

  • the effectiveness of relations inferred using only the transitive closure of original relations in the corpus (as described in Chambers and Jurafsky (2008))
  • the effectiveness of using ILP point model on the entire temporal graph
  • the effectiveness of using ILP point model with graph decompositions

When only transitive closure is done, an accuracy of 26% is achieved. When ILP is used, an accuracy of almost 50% is achieved. This is the accuracy achieved by Tatu and Srikanth (2008) on the temporal predictions where they preserve consistency. However, this paper uses the whole set of 13 relations while Tatu and Srikanth (2008) has only six. When predictions is limited on subsets of decomposed graph, ILP accuracy increases to 54%, perhaps benefiting from the more relevant context of the graph.

Related papers

The approach in this paper is similar to that of an earlier work by Chambers and Jurafsky (2008) that proposes to use global framework based on Integer Linear Programming (ILP) to jointly infer temporal relations between events.

However, while Chambers and Jurafsky (2008) only performs classification on 2 relations, this paper performs classification on all 13 temporal relations in TimeBank Corpus.

This paper also fills up the gap on Chambers and Jurafsky (2008)'s evaluation by computing accuracy on inferred relations using only transitive closure. This evaluation was not done in Chambers and Jurafsky (2008), thus casting a question on whether the improved performance observed in their paper is attributed solely to the transitive closure that makes the graph more well connected or to the global inference. Unfortunately however, since these two papers conduct different classifications: one on just 2 relations while the other on all 13 relations, the evaluation results are not directly comparable. In itself, this paper shows that adding ILP global inference on the transitively closed graph improves accuracy, confirming the merit of doing global inference for better temporal ordering of events in text.

This paper also shows the improved accuracy obtained through decomposing the temporal graph into more relevant subsets and conducting inference on them. This potentially shows that although a global inference helps in improving accuracy of local decisions, a more focused "semi-global" inference might be better.