Lexical Event Ordering with an Edge-Factored Model

Omri Abend, Shay B. Cohen, Mark Steedman

Understanding the typical sequence of events is a cornerstone of human intelligence. For instance, knowing that one must "obtain oil" before "frying an onion" is a piece of lexical temporal knowledge that humans use instinctively. This paper, presented at NAACL 2015, addresses the challenge of imbuing machines with this "common sense" of time.

The Knowledge Bottleneck in Temporal Ordering

A primary obstacle in AI tasks like automated planning and document summarization is the "knowledge bottleneck." Traditional methods for learning temporal relations rely on manual annotation, which is labor-intensive and expensive. Consequently, existing datasets are often too small to capture the vast diversity of verbs and objects in natural language. Moreover, previous research frequently focused on simple verb-verb pairs rather than ordering complex sets of events with multiple participants.

Methodology: An Edge-Factored Graph Approach

The authors frame event ordering as a graph problem. Given a set of unordered events—defined as predicate-argument structures—the goal is to determine the most likely sequence.

Figure 1: (a) Extracted events, (b) original recipe text, and (c) the resulting graph representation where nodes are events and edges represent temporal transitions.

The core of their approach is an Edge-Factored Model. In this model, the score of an entire sequence is calculated as the sum of the scores of its individual transitions (edges). To find the optimal sequence, the authors employ Global Inference via Integer Linear Programming (ILP). This allows them to find the highest-scoring Hamiltonian path—a path visiting every node exactly once—which represents the global optimum for the sequence.

The model is trained using a structured perceptron and incorporates three main feature types:

  • Lexical Features: The specific words used (e.g., "fry", "onion").
  • Brown Clusters: Groupings of semantically similar words (e.g., "saute" and "fry") to improve generalization.
  • Frequency Statistics: Data on how often event pairs appear together in large corpora, often associated with discourse markers like "before" or "then."

Leveraging Recipes as a "Silver Standard"

To overcome the lack of labeled data, the researchers utilized cooking recipes. In this domain, the textual order of instructions serves as a reliable proxy for the actual temporal order of actions. By scraping approximately 73,000 recipes, they generated a dataset of over 1 million events. A manual audit confirmed a high correlation (92.4% Kendall’s Tau) between the text sequence and the cooking timeline, validating recipes as a powerful "silver standard" for training.

Experimental Results

The model was evaluated on its ability to reconstruct the original order of shuffled recipe events. The results highlighted the superiority of global optimization over local, "greedy" decision-making.

Figure 4: Performance comparison of different algorithms across various accuracy metrics. GLOBAL-PRC consistently outperforms greedy baselines.

The best-performing model, GLOBAL-PRC, achieved a macro-averaged pairwise accuracy ($acc_2$) of 77.7%, significantly outperforming the greedy baseline of 68.0%. In a binary classification task—distinguishing a correct sequence from a random permutation—the model reached 93% accuracy, a substantial improvement over previous state-of-the-art methods.

Conclusion and Future Directions

The study demonstrates that domain-specific corpora where structure mirrors semantics can effectively bypass the need for manual annotation. While the edge-factored model is highly effective, it currently lacks the ability to capture higher-order dependencies (e.g., needing multiple ingredients prepared before a final cooking step). Future work may explore higher-order models and semi-supervised techniques to adapt these findings to less structured domains like news or literature.

Summary updated

Abstract

Extensive lexical knowledge is necessary for temporal analysis and planning tasks. We address in this paper a lexical setting that allows for the straightforward incorporation of rich features and structural constraints. We explore a lexical event ordering task, namely determining the likely temporal order of events based solely on the identity of their predicates and arguments. We propose an “edgefactored” model for the task that decomposes over the edges of the event graph. We learn it using the structured perceptron. As lexical tasks require large amounts of text, we do not attempt manual annotation and instead use the textual order of events in a domain where this order is aligned with their temporal order, namely cooking recipes.
BibTeX
@inproceedings{abend2015lexical,
  author = {Omri Abend and Shay B. Cohen and Mark Steedman},
  title = {{Lexical Event Ordering with an Edge-Factored Model}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2015},
  doi = {10.3115/v1/n15-1122},
}
Figure