We introduce the task of story fragment stitching, which is the process of automatically aligning and merging event sequences of partial tellings of a story (i.e., story fragments). We assume that each fragment contains at least one event from the story of interest, and that every fragment shares at least one event with another fragment. We propose a graph-based unsupervised approach to solving this problem in which events mentions are represented as nodes in the graph, and the graph is compressed using a variant of model merging to combine nodes. The goal is for each node in the final graph to contain only coreferent event mentions. To find coreferent events, we use BERT contextualized embedding in conjunction with a tf-idf vector representation. Constraints on the merge compression preserve the overall timeline of the story, and the final graph represents the full story timeline. We evaluate our approach using a new annotated corpus of the partial tellings of the story of Moses found in the Quran, which we release for public use. Our approach achieves a performance of 0.63 F1 score.
Understanding stories is a long-held goal of both artificial intelligence and natural language processing [Charniak, 1972; Schank and Abelson, 1977; Wilensky, 1978; Dyer, 1983; Riloff, 1999; Frank et al., 2003; Mueller, 2007; Winston, 2014]. Stories are found throughout our daily lives, e.g., in news, entertainment, education, religion, and many other domains. Automatically understanding stories implicates many interesting natural language processing tasks, and much information can be extracted from stories, including concrete facts about specific events, people, and things, commonsense knowledge about the world, and cultural knowledge about Copyright c 2020 by the paper’s authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). the societies in which we live. One interesting and challenging task which has not yet been solved is what we call here story fragment stitching. In this task we seek to merge partial tellings of a story—where each partial telling contains part of the sequence of events of a story, perhaps from different points of view, and may be found across different sources or media—into one coherent narrative which may then be used as the basis for further processing. Conceptually, this task is similar to both cross-document event coreference (CDEC) and event ordering in NLP. However, story fragment stitching, as we define it, presents a more challenging problem for at least two reasons. First, and unlike event coreference, the overall timeline of the story’s events need to be preserved across all fragments. Second, and unlike event ordering which targets only events related to a single entity, this work considers all events across all fragments.
For the purposes of this work, we define a story as a sequence of events effected by characters and presented in a discourse. This is in accord with fairly standard definitions: for example, [Forster, 1927] said that “A story is a narrative of events arranged in their time sequence.” As a simplifying assumption, we additionally assume that the events in the story are presented in the chronological order in which the events of a story take place (i.e., the fabula time order) [Bordwell, 2007]. We leave the problem of extracting the chronological ordering of events within a text for other work.
We present an approach to story fragment stitching problem inspired by [Finlayson, 2016] which in turn based on model merging, a regular grammar learning algorithm [Stolcke and Omohundro, 1993], using similarity measures based on BERT contextualized embedding and tf-idf weights of events and their arguments. We apply this approach to a concrete example of this problem, namely, the story of the prophet Moses as found in the Quran, the Islamic holy book. The story of Moses is not found in one single telling in the Quran; rather, it is found in eight fragments spread across six different chapters (the chapters of the Quran are called suras), with the story comprising 7,931 total words across 283 verses of anywhere from 2 to 94 words in length. In this work we demonstrated our approach using the seven fragments with coherent timelines.
The story of Moses is especially useful for this work because it has been subject to detailed event analysis, in particular, [Ghanbari and Ghanbari, 2008] identified a canonical timeline of events for the story. Further, the Quran verse structure provides a natural unit of analysis, where nearly every verse is related to only a single event in the story timeline. We manually extracted 573 event mentions from 273 verses (omitting 11, as described later) and annotated all events corresponding to the Ghanbari’s event categories. We used this data to test our approach, resulting in a proof of concept of story fragment stitching. We release both our code and data to enable reimplementations1.
We begin by discussing prior work on cross-document event coreference, event ordering, as well as the description and analysis of story structure (§2). Then we introduce our method, including the task definition (§3.1) and specific aspects of our approach (§3.2–§3.3). We then describe our evaluation, including construction of the gold standard for the Moses story in the Quran (§4.1), the experiment setup (§4.2), the result of our model (§4.5), as well as an error analysis (§5). We conclude with a list of contributions (§6). 2
The most closely related problems to story stitching are the problem of cross-document event coreference (CDEC) and cross-document event ordering. In CDEC systems, the goal is to group expressions that refer to the same event across multiple documents. [Bagga and Baldwin, 1999; Lee et al., 2012; Goyal et al., 2013; Saquete and Navarro-Colorado, 2017; Kenyon-Dean et al., 2018; Barhom et al., 2019]. In event ordering task, which was introduced in SemEval-2015 [Minard et al., 2015], the goal is to order events cross-document in which a specific target entity is involved. That is, a system should produce a timeline for a specific target entity and that timeline consists of the ordered list of the events in which that entity participates. Similarly, within document event sequence detection task, which was introduced in TAC KBP 2017 event track [Mitamura et al., 2017], aims to identify event sequence (i.e., after links) that occurs in a script [Schank and Abelson, 1977].
Despite this very interesting and useful prior work, these systems are not directly applicable to the task of story fragment stitching as we define it. In particular, CDEC systems ignore the timeline of the story’s events (i.e., the overall timeline of the story’s events is not guaranteed to be preserved across all fragments), while event ordering systems only order certain events related to a specific target.
Researchers have explored several ways of assessing similarity between stories [Schank and Abelson, 1975; Roth and Frank, 2012; Finlayson, 2012; Iyyer et al., 2016; Nikolentzos et al., 2017; Chaturvedi et al., 2018]. These works provided valuable ways to capture similarity between stories. However, the story similarity task is not directly applicable to the task of stitching fragmented stories, where the goal is to order events across multiple stories (fragments), except in the simple baseline sequence alignment approach [Needleman and Wunsch, 1970; Reiter, 2014].
1The code and data are available at https://doi.org/10.34703/ gzx1-9v95/28GC2M
We now discuss the precise definition of the story fragment stitching task (§3.1) and the details of the two main components of our approach: model formulation (§3.2), and the graph merge to align fragments events into a full, ordered, end-to-end list of story events (§3.3). 3.1
We define the goal of story fragment stitching as: align a set of story fragments into a full, ordered, end-to-end list of story events. We assume that the story fragments are ordered lists of events, where the order is that of the fabula, namely the order of events as they happen in the story world. In many stories, the fabula order is different from the discourse order, but we do not consider this case here; we leave the problem of extracting the chronological order of events to other work. We also assume that each fragment shares at least one event with another fragment. The output of the system is an ordered list of nodes, where each node is a collection of event mentions (corefering events) that all describe one particular single event, and these nodes are in the same order as the overall fabula. 3.2
The first step of the approach is model initialization which is shown Algorithm 1 lines 1–3. Using the function constructLinearBranch, we convert each fragment’s list of events into a linear directed graph (linear branch) where each node contains only a single event. Each event is represented by a vector which is a concatenation of the event contextualized embedding from the BERT model and tf-idf weights of the event lemma and its semantic arguments. BERT [Devlin et al., 2018] is a multi-layer bidirectional transformer trained on plain text for masked word prediction and next sentence prediction tasks, while tf-idf is the standard term weighting approach to reflect how important a word is in a document in comparison to the rest of documents [Salton and McGill, 1986]. Using the function linkGraphs we link all linear branches to a start and an end node, resulting in one directed graph of all the set of fragments, as shown in Figure 1.
This initial model will be used to generate possible solutions by merging different nodes on the basis of a similarity measure, discussed below. When two nodes A and B are merged, the new node C should contain an average vector of both A and B. In the next section, we introduce the merge approach. 3.3
The second step of the approach is model merging, shown in Algorithm 1 lines 4–15. We first compute a threshold ↵ using computeTFIDFAvgSim function, which takes the average of the highest and lowest cosine similarity values between all fragments using tf-idf weights. ↵ sets the minimum similarity required to merge two nodes; for our data ↵ was 0.39. Next, using a cosine similarity measure, the computeNodesSim function computes the full set of similarity scores between all pairs of nodes. Then the algorithm starts by searching for e2:2 en:2 . . . the most similar nodes using findMostSim function, lines 6 and 13, and merges the most similar nodes using merge function. Because the fragments are assumed to be already in fabula time order, the pairsIntroduceCycle boolean function disallows merges that would introduce cycles, ignoring (and removing) self-loops (the no-cycles constraint), and thereby preserves the overall order of the events. Note that disallowing cycles also prevents merges of non-neighboring nodes within the same fragment. The new merged node then contains a weighted average vector of the old nodes vectors and nodes similarity are updated using updateNodesSim function. The algorithm continues to merge nodes until the similarity measure drops below ↵ . Because the final resulting graph is not guaranteed to contain only one path from start to end, by using bestPath function, the path with the maximum merged nodes (based on the number of events) is considered to be the final output of the model.
F : set of text fragments f
E : map of f to sets ef of gold event annotations 1 /* Create initial model */ G ; foreach f 2 F do g constructLinearBranch(f, E.get(f ))
G.add(g) 2 end 3 model
linkGraphs(G) /* Merging process */ 4 ↵ computeTFIDFAvgSim(F) 5 nodesSim computeNodesSim(model) 6 (maxPairSim,pairs) findMostSim(nodesSim) repeat 7 if ¬ pairsIntroduceCycle(model, pairs) then 8 model merge(pairs) 9 nodesSim updateNodesSim(model,nodesSim) else 10 11 nodesSim 12 end 13 (maxPairSim,pairs) 14 until maxPairSim < ↵ ; 15 bestPath findBestPath(model) setSimToZero(pairs,nodesSim) findMostSim(nodesSim)
We evaluate our approach against a gold-standard annotation of Moses’ from the Quran. We first describe how we collected and annotated the data (§4.1). After that we demonstrate the experiment setup (§4.2) and the evaluation (§4.3). Then we report the performance of our approach (§4.5). Finally, we do an error analysis of the performance of our system (§5). 4.1
Moses was an important figure whose story is central to the major Abrahamic religions, including Judaism, Christianity, and Islam. Moses’ story is found in fragmentary form throughout the holy books of these religions, with some parts repeated, but in different contexts and sometimes from different perspectives. In the Quran, the holy book of Islam, the story of Moses appears in eight different fragments across six different chapters (suras) comprising 283 verses. Thus the story of Moses serves as an excellent example for the evaluation of our approach to story fragment stitching. The relevant suras and verses are listed in Table 1, along with the number of events present in the fragments of each chapter.
We annotated verses based on a comparative analysis of Moses’ story in the Old Testament and the Quran by [Ghanbari and Ghanbari, 2008]. The Ghanbari study breaks Moses’ story 43 event categories, shown in Table 3 in chronological order. For the annotation, three annotators labeled each verse with its single relevant event. We measured a Fleiss’ kappa of 0.76, which represents excellent agreement. The annotation was originally done on the Arabic version of the Quran, but we transferred the annotations to an English translation [Ali, 1973] for the remainder of the study.
We excluded one fragment (Sura 2 [Al-Baqarah], verses 50–60) from the analysis because its timeline is quite different from the fabula order. We manually extracted 708 total event mentions from the remaining seven fragments. Our annotation procedure followed the standards outlined for events in the TimeML standard [Saurı et al., 2006]. We omitted 135 Reporting mentions (e.g., say, reply, etc.) because these usually are just indicators of direct speech, and do not correspond to plot events. This resulted in 573 event mentions relevant to the plot, which we labeled as to which specific event it referred in the Moses timeline (Table 3). 301 of the event mentions were labeled with an event described in the timeline, while 272 were not relevant. 4.2
We used the netwrokx library [Hagberg et al., 2008] for graph operations. We extracted event contextualized embedding using the flair implementation [Akbik et al., 2018] of the BERT model with the default parameters2. The tf-idf weights for the lemmas of all tokens excluding stop words are computed using spaCy [Honnibal and Montani, 2017] and scikit-learn libraries [Pedregosa et al., 2011]. The event arguments are extracted and resolved using the AllenNLP semantic role labeling (SRL) and coref2bert base uncased, layers=-1, pooling operation=first For the evaluation, we used the temporal awareness measure [UzZaman et al., 2013] used in both event ordering task SemEval-2015 [Minard et al., 2015] and event sequence task TAC-KBP-2017 [Mitamura et al., 2017]. The temporal awareness metric calculates precision and recall values based on the closure and reduction graphs. For a directed graph, a reduced graph is derived from the original graph by having the fewest possible edges that have the same reachability relation as the original graph. In this work, the final directed path of nodes in the final model represents the reduced graph. For example, consider the final directed path of nodes in the final model to be:
start ! n1 ! n2 ! n3 ! end where, for example, events e1, e2 2 n1, e3 2 n2, and e4, e5 2 n3. The reduced graph (G ) is represented as the following edges: h(e1, e3), (e2, e3), (e3, e4), (e3, e5)i and the transitive closure graph (G+) is represented as the following edges: h(e1, e3), (e2, e3), (e1, e4), (e1, e5), (e2, e4), (e2, e5), (e3, e4), (e3, e5)i ,where the relation between (ei, ej ) is defined as before relation. The temporal awareness metric calculates the precision and recall as follow: precision = |System \ Ref erence+|
|System | recall = |Ref erence \ System+| |Ref erence | (1) (2) ,where System and Reference are the proposed approach and the gold standard, respectively. The final F1 score is the harmonic mean of the precision and recall values. 4.4
We used the Needleman-Wunsch algorithm [Needleman and Wunsch, 1970] as a baseline. Needleman-Wunsch is a wellknown global alignment algorithm used in bioinformatics and the social sciences. Using dynamic programming, this algorithm searches for optimal alignment of an arbitrary number
tf-idf BERT
of items (the events lemma in our case) by using a scoring function that penalizes the dissimilarities and the insertion of gaps. We used the default implementation3developed by [Dekker and Middell, 2011] which follows the group of progressive alignment algorithms where two sequences are aligned and then the result is aligned to the next sequence. It repeats the procedure until all sequences are aligned. peculiarities of Quranic language cause errors. For example, the word We is usually present as an event’s argument when God is speaking of himself. This causes problems for the coreference resolution system, in that it does not pair we with such mentions Lord and God, thus introduces additional errors into the system. Also, some events have the same event mention and arguments but happen at different points in the timeline. Example 1 shows text from different parts of the story: the first is when God shows Moses one of the signs whereas the second is when Moses shows the Pharaoh the sign. Notably, the two events have the same event triggers (showed in bold) and the same arguments (underlined). (20:19–20) “Throw it down, O Moses,” said (the Voice). So he threw it down, and lo, it became a running serpent. (7:106–107) He said: “If you have brought a sign then display it, if what you say is true.” At this Moses threw down his staff, and lo, it became a live serpent.
Example 1: An example to show when two events happen at different points in the timeline.
Further, the approach is sensitive to the order of merges. If an incorrect merge is performed early, this can eliminate correct merges later on account of the no-cycles constraint. Therefore performing only the highest confidence merges first is critical, and errors in that process degrade other distance parts of the model. 6
We introduced the story fragment stitching problem, the task of merging partial tellings of a story into a unified whole. We have introduced an approach that models the story’s fragments in a graph and applies an adapted model merging approach to merge similar nodes and produce an ordered, endto-end list of story events. Our approach achieves a performance of 0.63 F1 using the temporal awareness metric. 7
Mr. Aldawsari was funded in part by a doctoral fellowship from Prince Sattam Bin Abdulaziz University, as well as NSF Grant IIS-1749917 to Dr. Finlayson. We thank Seyedeh Mohadeseh Taheri Mousavi and Zahra Ejei for their assistance in annotating the verses from the Quran in the original Arabic. The idea of combining distributional semantics with automatic story model merging was proposed and developed by Mr. Asgari in his Master’s thesis at CSAIL MIT supervised by Dr. Finlayson in 2013–2014 academic year. The creation of the corpus was also among the contributions of that thesis. Moses’s Birth
1. Moses’ Birth and left in the Nile.
Moses is Rescued from the Nile 2. Moses is rescued from the Nile. 3. Moses’ sister kept an eye on him. 4. Moses brought back to his mother.
5. Moses after infancy and through maturity.
Moses kills the Egyptian
6. Moses beats and kills the Egyptian.
Moses flees to the Madyan
7. Moses ran away to the Madyan.
Moses’ Marriage 8. Moses protected Shu’ayb’s daughters.
9. Moses traveled with his family.
Moses is Chosen to be a Prophet 10. Moses saw the fire from the distance.
11. Moses talked to God through the burning bush.
God Shows Moses the Miracles 12. God changed the wand to the snake.
13. God illuminated Moses’ hand.
God Send Moses to the Pharaoh
14. God commanded Moses to meet the Pharaoh.
Moses Speaks with the Pharaoh 15. Moses and Aaron went to the Pharaoh with miracles. 16. Moses showed Pharaoh the signs. 17. Pharaoh refused their message. 18. Pharaoh accused Moses. 19. Pharaoh requested a competition with Moses. 20. Competition between Moses and the magicians. 21. Magicians believed in Moses’s message. 22. Magicians are threatened by the Pharaoh.
23. Pharaoh cruelty to the believers.
God Sends Calamities in Egypt 24. Calamities are sent to the Egyptians and the Pharaoh. 25. God withdraw the punishment. 26. God commanded Moses to travel with his people.
27. Pharaoh and his army followed Moses and his people. Parting of the Red Sea 28. Separation of the Sea and drowning of the Pharaoh. 29. God saved Moses and his people.
Going to Mt. Sinai to Receive the Commandments 30. Moses went to Sinai for 40 nights. 31. God sent down food and brings forth water. 32. Moses met God and appeared on mountain.
33. Moses delivered the commands and the stone tablets. The People Betray God 34. Worshipping the Calf in the Absence of Moses. 35. Moses returned to his people. 36. Samiri explained to Moses what he saw. 37. Moses blamed his brother. 38. Moses returned to God.
39. Moses stroked the stone.
Wandering in the Desert 40. Israelites are commanded to take over the holy region. 41. The disobedient Israelites won’t enter the holy region. 42. God punished them. 43. Sacrifice of a heifer. 2 2 2 2 1 2 1 1 2 2 2 2 2 2 4 3 3 4 3 4 3 3 1 1 1 3 3 5 3 3 1 2 3 2 1 2 1 1 1 1 2 2 1 6 4 4 2 2 10 1 20 3 12 4 11 5 9 8 10 4 5 8 34 8 6 6 6 1 6 6 14 5 6 4 15 3 14 3 3 10 3 9 5 4 1 1 0.33 0.45 0.55 0.34 0.68 0.85 0.74