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.
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.
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