TL;DR
This paper proposes a novel way to frame Script Induction (SI) – the task of understanding event sequences in text – as a problem within Association Rule Mining (ARM). By leveraging ARM techniques, the authors develop a more robust and explainable method for predicting missing events in narrative chains, outperforming existing count-based approaches.
What Problem Does This Paper Address?
Script Induction aims to capture the common-sense knowledge about sequences of events that typically occur in specific situations (e.g., "going to a restaurant" involves ordering, eating, paying). Traditionally, SI has relied on statistical methods, often assuming events are independent. This assumption can be limiting. The paper addresses the challenge of building more accurate and interpretable SI models by exploring how to leverage the power of Association Rule Mining (ARM), a well-established technique in data mining for discovering relationships in large datasets. Specifically, they aim to improve the prediction of missing events in narrative sequences, a task known as the "narrative cloze test."
Methods
The core contribution is unifying existing count-based SI models within a general framework of narrative chain likelihood maximization. Instead of relying on simplified (e.g., naive Bayes) assumptions of independence, the authors propose using ARM to mine "higher-order count statistics."
Here's a breakdown:
- Unification: They show how previous SI models (like the Unordered PMI and Bigram Probability models) can be seen as special cases of maximizing chain likelihood.
- ARM for Rule Mining: The paper adapts ARM's core components:
- Frequent Itemsets: Identifying commonly co-occurring events.
- Association Rules: Discovering relationships of the form "if events A, B occur, then event C is likely."
- Interestingness Function: A new metric
int(S → E)is proposed to measure the reliability of a rule, going beyond simple support.
- Interestingness Function: A new metric
- Weighted Set Cover for Inference: For predicting a missing event in a narrative chain, they frame the problem as a weighted set cover problem. This allows them to efficiently combine the mined rules to make a prediction, using a greedy algorithm for an approximate solution.
- Higher-Order Statistics: A key advantage is the ability to capture dependencies between multiple events, moving beyond pairwise relationships.
Datasets
- Training: 1994–2006 portion of the New York Times part of the Annotated Gigaword dataset (1.3M chains with 8.7M narrative events).
- Development: Subset of 2007–2008 (10K chains with 62K narrative events).
- Test: Subset of 2009–2010 (5K chains with 31K narrative events).
The dataset consists of automatically generated in-document coreference chains, filtered for length and common reporting verbs.
Key Insights and Ideas
- ARM as a Natural Fit for SI: The paper convincingly argues that ARM's ability to find frequent itemsets and interesting rules directly maps to the goals of SI – identifying co-occurring events and their sequential relationships.
- Moving Beyond Independence Assumptions: By using ARM, the proposed method can capture more complex, higher-order dependencies between events, which is crucial for understanding nuanced narratives.
- Weighted Set Cover for Explainable Prediction: Framing the prediction task as a set cover problem provides a more interpretable way to combine evidence from multiple rules, making the model's reasoning more transparent.
- Inductive Biases of ARM are Beneficial: The authors conclude that the "inductive biases" introduced by ARM (i.e., the way it structures the search for patterns) are beneficial for performance on the narrative cloze test.
Key Results
- Improved Performance: The proposed ARM-based approach shows improved performance over other count-based SI models. Specifically, they report a 5% relative improvement in Mean Reciprocal Rank (MRR) and a 10% improvement in Recall@50 on the test set.
- Ablation Studies: Experiments (Table 2) demonstrate that pruning rules based on support and interestingness thresholds (key ARM concepts) is crucial for performance. They also show that using binary rules (size two) is equivalent to prior UOP models, but higher-order rules offer further gains. The posterior ARM model (using Eq. 7) achieved the best performance.
- Scalability: The algorithms for rule mining and inference are noted to be computationally efficient, suggesting potential for further improvement with larger datasets.
Limitations and Future Work
- Data Sparsity: Relying solely on count-based statistics can lead to sparsity issues with longer itemsets.
- Future Work: The authors suggest exploring methods that combine count-based statistics with dense embeddings from modern contextual encoders (like BERT) to mitigate sparsity and improve performance. Mining rules based on both counts and embedding properties is highlighted as a promising direction.
Summary updated