Predicting globally-coherent temporal structures via endpoint inference and graph decomposition
Pascal Denis and Philippe Muller
An elegant approach to learning temporal orderings from texts consists in formulating this problem as a constraint optimization problem, which can be then given an exact solution using Integer Linear Programming. This strategy works well for cases where the number of possible relations between temporal entities is restricted to the mere precedence relation (Bramsen et al., 2006; Chambers & Jurafsky, 2008). But it becomes impractical when considering all possible interval relations due to an important combinatorial blow-up. This paper investigates two innovations, inspired from work on temporal reasoning, that directly control this combinatorial blow-up, therefore rendering an exact ILP inference viable in the general case. First, we translate our network of constraints from temporal intervals to endpoints, resulting in a drastically smaller set of constraints, while preserving the same information. Second, we show that additional efficiency is gained by enforcing coherence on particular subsets of the entire temporal graphs. We evaluate these innovations through various experiments on the TimeBank 1.2 corpus, and compare our different ILP formulations with various baselines and oracle systems.