Script Induction as Association Rule Mining (2020)

Abstract: We show that the count-based Script Induction models of Chambers and Jurafsky (2008) and Jans et al. (2012) can be unified in a general framework of narrative chain likelihood maximization. We provide efficient algorithms based on Association Rule Mining (ARM) and weighted set cover that can discover interesting patterns in the training data and combine them in a reliable and explainable way to predict the missing event. The proposed method, unlike the prior work, does not assume full conditional independence and makes use of higher-order count statistics. We perform the ablation study and conclude that the inductive biases introduced by ARM are conducive to better performance on the narrative cloze test.

## introduction the goal of this paper is to demonstrate how the efforts in script induction (si), up until recently dominated by statistical approaches @xcite @xcite , can be productively framed and extended as a special case of association rule mining (arm), a wellestablished problem in data mining @xcite @xcite . we start by introducing si and arm and then demonstrate a unification under a general chain likelihood maximization framework. we discuss how the existing count-based si models tackle this maximization problem using naïve bayes assumptions. we provide an alternative: mining higherorder count statistics using arm and picking the most reliable rules using the weighted set cover algorithm. we validate the proposed approach and demonstrate improved performance over other count-based approaches. we conclude with a discussion on the implications and potential extensions of the proposed framework. our intent in this work is not to establish new state of the art results in the area of si. rather, our primary contribution is retrospective, drawing a connection between a sub-topic in computational linguistics (cl) with a major pre-existing area of computer science, i.e., data mining. in the case one approached si through counting co-occurrence statistics, then the existing tools of arm lead naturally to solutions that had not been previously considered within cl. ## si as arm the models defined by eqs. 5, 6, and 7 are hard to compute directly: without simplifying assumptions, they would require huge number of parameters and large training sets @xcite . a common approach in the existing count-based si work is to assume full conditional independence. a viable and less restrictive alternative, as we show in this section, is estimating higher-order count statistics via mining association rules (section 4.1) and combining the most confident rules to predict the missing event with a simple weighted set cover algorithm (section 4.2). more formally, during the training phase, we would like to populate the set of interesting rules @xmath0, whose antecedents are sub-sets of the event space s ⊂ e, and consequents are single events e, @xmath1. we denote as s e all the rules with the same consequent event e. during the test phase, where we have an incomplete narrative chain {e 1 , e 2 , . . . , e l } and want to predict a missing event, we will use rules from s e to efficiently decompose p (e 1 , e 2 , . . . , e l |e) into p (s 1 |e) • p (s 2 |e) • . . . • p (s t |e) for each candidate event e. naturally, this means selecting a set of rules whose antecedents {s 1 , s 2 , . . . , s t } (we call this set a candidate cover) are pairwise disjoint (s i ∩s @xmath2, @xmath3, and cover the event chain fully (s 1 ∪ s 2 ∪ . . . ∪ s @xmath4, e 2 , . . . , e l }). to quantify the goodness of the decomposition, we define a score function for a candidate cover {s 1 , . . . , s t } and a candidate event e as follows: score(s 1 , s 2 , . . . , s t ; e) = in section 4.1, we explain how the set of rules s is populated from the si training corpus. in section 4.2, we provide a randomized algorithm that solves problem 9 with a provably bounded error. ## experimental results we perform two experiments, comparing existing count-based si models with three variants of the proposed arm model. the performance is measured using recall@50 and mean reciprocal rank. in the first experiment, we establish that the count-based pruning, introduced by arm support and interestingness thresholds (t sup and t int , respectively) for reducing the search space during rule mining, does contribute to better performance on the narrative cloze test. we also validate empirically that the arm model with binary (of size two) rules is equivalent to the uop model by @xcite . finally, we compare variants of the arm model, which vary in a way of incorporating a prior probability of the missing event. we conclude that the posterior arm model, given by eq. 7, achieves the best performance. the results of this experiment are outlined in in the second experiment, we compare the bestscoring arm model and other baseline models on 5,000 test chains. we achieve 5% relative improvement for mean reciprocal rank (mrr) and 10% for recall@50, which can be attributed to using higher-order count statistics and the selection of the prior for the missing event. the scalability of both rule mining and inference algorithms suggests that the performance may be further improved as the training corpus size grows and more reliable higher-order statistics become available. the results of this experiment are shown in ## conclusion our decision to approach count-based si as arm was motivated by a previously under-explored similarity of these well-established areas, which we outlined in this paper. drawing similarities from the existing work on classification using association rules (car) @xcite , we proposed a scoring function that uses arm-based count statistics to reliably predict the missing event in the narrative cloze test. one downside of relying solely on count-based statistics is the low support of longer itemsets due to data sparsity. on the other hand, modern contextual encoders @xcite mitigate this via parameter sharing. reliably mining rules whose support and interestingness are based on both counts and properties of dense embeddings can be a promising direction of future work.