Narrative is a fundamental form of representation in human language and culture. Stories connect individuals and deliver experience, emotions and knowledge. Narrative comprehension has attracted long-standing interests in natural language processing (NLP) BIBREF1 , and is widely applicable to areas such as content creation. Enabling machines to understand narrative is also an important first step towards real intelligence. Previous studies on narrative comprehension include character roles identification BIBREF2 , narratives schema construction BIBREF3 , and plot pattern identification BIBREF4 . However, their main focus is on analyzing the stories themselves. In contrast, we concentrate on training machines to predict the end of the stories. Story completion tasks rely not only on the logic of the story itself, but also requires implicit commonsense knowledge outside the story. To understand stories, human can use the information from both the story itself and other implicit sources such as commonsense knowledge and normative social behaviors BIBREF5 . In this paper, we propose to imitate such behaviors to incorporate structured commonsense knowledge to aid the story ending prediction.Recently, BIBREF0 introduced a ROCStories dataset as a benchmark for evaluating models' ability to understand the narrative structures of a story, where the model is asked to select the correct ending from two candidates for a given story. To solve this task, both traditional machine learning approaches BIBREF6 and neural network models BIBREF7 have been used. Some works also exploit information such as sentiment and topic words BIBREF8 and event frames BIBREF9 . Recently, there has been work BIBREF10 that leverages large unlabeled corpus, like the BooksCorpus BIBREF11 dataset, to improve the performance. However, none of them explicitly uses structured commonsense knowledge, which humans would naturally incorporate to improve model performance.Figure 1 (a) shows a typical example in ROCStories dataset: a story about Dan and his parents. The blue words are key-words in the body of the story, and the red word is the key-word in the correct story ending. Figure 1 (b) shows the (implicit) relations among these key-words, which are obtained as a subgraph from ConceptNet BIBREF12 , a commonsense knowledge base. By incorporating such structured external commonsense knowledge, we are able to discover strong associations between these keywords and correctly predict the story ending. Note that these associations are not available from the story itself.To solve the story completion task, we propose a neural network model that integrates three types of information: (i) narrative sequence, (ii) sentiment evolution, and (iii) commonsense knowledge. The clues in narrative chain are captured by a transformer decoder, constructed from a pretrained language model. The sentiment prediction is obtained by using a LSTM model. Additionally, the commonsense knowledge is extracted from an existing structured knowledge base, ConceptNet. In particular, we use a combination gate to integrate all the information and train the model in an end-to-end manner. Experiments demonstrate the improved performance of our model on the task.Our work on story completion is closely related to several research areas such as reading comprehension, sentiment analysis and commonsense knowledge integration, which will be briefly reviewed as below.Reading Comprehension is the ability to process text, understand its meaning, and to integrate it with what the readers already know. It has been an important field in NLP for a long time. The SQuAD dataset BIBREF13 presents a task to locate the correct answer to a question in a context document and recognizes unanswerable questions. The RACE dataset BIBREF14 , which is constructed from Chinese Students English Examination, introduces another task that requires not only retrieval but also reasoning. Usually they are solved by match-based model like QANET BIBREF15 , hierarchical attention model like HAF BIBREF16 , and dynamic fusion based model like DFN BIBREF17 . Also there exists more relevant research on story comprehension such as event understanding of narrative plots BIBREF3 , character personas BIBREF2 and inter-character relationships BIBREF18 .Sentiment Analysis aims to determine the attitude of a speaker (or a writer) with respect to some topic, the overall contextual polarity, or emotional reaction to a document, interaction or event. There have been rich studies on this field, such as learning word vectors for sentiment analysis BIBREF19 and recognizing contextual polarity in a phrase-level BIBREF20 . Recently, researchers studied large-scale sentiment analysis across news and blogs BIBREF21 , and also studied opinion mining on twitter BIBREF22 . Additionally, there have been studies focused on joint learning for better performance, such as detecting sentiment and topic simultaneously from text BIBREF23 .Commonsense Knowledge Integration If machines receive information from a commonsense knowledge base, they become more powerful for many tasks like reasoning BIBREF24 , dialogue generation BIBREF25 and cloze style reading comprehension BIBREF26 . Related works include BIBREF24 , which builds a knowledge graph and uses it to deduce the size of objects BIBREF24 , in addiiton to BIBREF27 , in which a music knowledge graph is built for a single round dialogue system. There are several ways to incorporate external knowledge base (e.g., ConceptNet). For example, BIBREF28 uses a knowledge based word embedding, BIBREF29 employs tri-LSTMs to encode the knowledge triple, and BIBREF30 and BIBREF26 apply graph attention embedding to encode sub-graphs from a knowledge base. However, their work does not involve narrative completion.Story Completion Traditional machine learning methods have been used to solve ROCStory Cloze Task such as BIBREF6 . To improve the performance, features like topic words and sentiment score are also extracted and incorporated BIBREF8 . Neural network models have also been applied to this task (e.g., BIBREF31 and BIBREF7 ), which use LSTM to encode different parts of the story and calculate their similarities. In addition, BIBREF9 introduces event frame to their model and leverages five different embeddings. Finally, BIBREF10 develops a transformer model and achieves state-of-the-art performance on ROCStories, where the transformer was pretrained on BooksCorpus (a large unlabeled corpus) and finetuned on ROCStories.For a given story $S = \lbrace s_1, s_2, ..., s_L\rbrace $ consisting of a sequence of $L$ sentences, our task is to select the correct ending out of two candidates, $e_1$ and $e_2$ , so that the completed story is reasonable and consistent. On the face of it, the problem can be understood as a standard binary classification problem. However, learning binary classifier with standard NLP techniques on the explicit information in the story is not sufficient. This is because correctly predicting the story ending usually requires reasoning with implicit commonsense knowledge. Therefore, we develop a neural network model to predict the story ending by integrating three sources of information: narrative sequence, sentiment evolution and structured commonsense knowledge (see Figure 2 ). Note that the first two types of information are explicit in the story while the third type is implicit and has to be imported from external source such as a knowledge base. In this section, we will explain how we exploit these three information sources and integrate them to make the final prediction.To describe a consistent story, plots should be planned in a logically reasonable sequence; that is there should be a narrative chain between different characters in the story. This is illustrated in the example in Figure 3 , where words in red are events and words in blue are characters. The story chain, “Agatha wanted pet birds $\rightarrow $ Agatha purchased pet finches $\rightarrow $ Agatha couldn't stand noise $\rightarrow $ mess was worse $\rightarrow $ Agatha return pet birds", describes a more coherent and reasonable story than “ Agatha wanted pet birds $\rightarrow $ Agatha purchased pet finches $\rightarrow $ Agatha couldn't stand noise $\rightarrow $ mess was worse $\rightarrow $ Agatha buy two more". When Agatha could not stand the noise, it is more likely for her to give these birds away rather than buy more. Therefore, developing a better semantic representation for narrative chains is important for us to predict the right endings.Inspired by the recent research from OpenAI BIBREF10 on forming semantic representations of narrative sequences, we first pre-train a high-capacity language model on a large unlabeled corpus of text to learn the general information hidden in the context, and then fine-tune the model on this story completion task.Given a large corpus of tokens $C = \lbrace c_1, c_2, ... , c_n\rbrace $ , we can pre-train a language model to maximize the likelihood : $$L_{lm}(C) = \sum _{i} \log P_l(c_i|c_{i-k}, ..., c_{i-1}; \theta )$$   (Eq. 6) where $k$ is the window size, and the conditional probability $P_l$ is modeled using a neural network with parameters $\theta $ .Similar to BIBREF10 , we use a multi-layer transformer decoder with multi-headed self-attention for the language model: $$h_0 &= C W_e+W_p \\
h_l &= transformer(h_{l-1}), l \in [1,M] \\
P(c) &= softmax(h_M W_e^T)$$   (Eq. 7)  where $C = \lbrace c_1, c_2, ... , c_n\rbrace $ are tokens in corpus, $W_e$ is the token embedding matrix, $W_p$ is the position embedding matrix and $M$ is the number of transformer blocks.We use the pre-trained parameters released by OpenAI as the initialization for the transformer decoder. We adapt these parameters to our classification task. For each candidate story $(s_1, s_2, s_3, s_4, e_i)$ (i.e., the story body followed by one candidate ending), we serialize it into a sequence of tokens $X = \lbrace x_1, ... , x_k\rbrace $ , where $k$ is the number of tokens. Then the fine-tuned transformer takes $X$ as its input and outputs the probability of $e_i$ being the correct ending: $$P_N(y|s_1, ..., s_4, e_i) = softmax(W_M h_M^k + b_M)$$   (Eq. 9) where $y \in \lbrace 0,1\rbrace $ is the label indicating whether $e_i$ is the correct ending, $h_M^k$ denotes the hidden representation at the $M$ -th layer of the transformer associated with the $k$ -th token, and $W_M$ and $b_M$ are parameters in the linear output layer.Besides narrative sequence, getting a good sentiment prediction model is also important for choosing the correct endings. Note that stories are different from other objective texts (e.g., news), as they have emotions within the context. Usually there is a sentiment evolution when a storyline is being revealed BIBREF32 .First, we pre-train a sentiment prediction model using the training set of the ROCStories, which does not have alternative endings (i.e., no negative samples). Given a five-sentence story $S = \lbrace s_1, s_2, s_3, s_4, s_5\rbrace $ , we take the first four sentences as the body $B$ and the last sentence as the ending $e$ . We extract the sentiment polarity of each sentence by utilizing a lexicon and rule-based sentiment analysis tool (VADER) BIBREF33 : $$E_i = \text{VADER}(s_i), i \in [1,5]$$   (Eq. 12) where $E_i$ is a vector of three elements including probabilities of the $i$ -th sentence being positive, negative and neutral.Then, we use a Long Short-Term Memory (LSTM) neural network to encode the sentence sentiments $E_i$ with its context into the hidden state $h_i$ , which summarizes the contextual sentiment information around the sentence $s_i$ . And we use the last hidden state $h_4$ to predict the sentiment vector $E_p$ in the ending $e$ : $$h_i &= \text{LSTM}(E_i,h_{i-1}) , i\in [1,4] \\
E_p &= softmax(W_e h_4 + b_e)$$   (Eq. 13) We train the sentiment model by maximizing the cosine similarity between the predicted sentiment vector $E_p$ and the sentiment vector $E_5$ of the correct ending: $$sim(S) = \dfrac{E_p \cdot E_5}{\Vert E_p \Vert _2 \cdot \Vert E_5 \Vert _2}$$   (Eq. 14) Afterwards, we adapt the parameters to the story ending selection task and calculate the following conditional probability $P_S$ : $$P_S(y|s_1, ..., s_4, e_i) = softmax(E_pW_sE_e)$$   (Eq. 15) where $S = \lbrace s_1, s_2, s_3, s_4\rbrace $ is the body, $e_i$ is the candidate ending, $E_p$ is the predicted sentiment vector, $E_e$ is the sentiment vector extracted from ending $e_i$ , and $W_s$ is the similarity matrix to be learned.Narrative sequence and sentiment evolution, though useful, are not sufficient to make correct predictions. In a typical story, newly introduced key-words may not be explained in the story because story-writers are not given enough narrative space and time to develop and describe them BIBREF34 . In fact, there are many hidden relationships among key-words in natural stories. In Figure 1 (a), although the key-word “diet" in the ending is not mentioned in the body, there are hidden relationships among “diet", “overweight" and “unhealthy" as shown in Figure 1 (b). When this kind of implicit information is uncovered in the model, it is easier to predict the correct story ending.We leverage the implicit knowledge by using a numberbatch word embedding BIBREF12 , which is trained on data from ConceptNet, word2vec, GloVe, and OpenSubtitles. The numberbatch achieves good performance on tasks related to commonsense knowledge BIBREF28 . For instance, the cosine similarity between “diet" and “overweight" in numberbatch is 0.453, but it is 0.326 in GloVe. This is because numberbatch makes use of the relationship between them as shown in Figure 1 (b) while GloVe does not.[h] Knowledge distance computation [1] sentence $s_j$ such that $s_j\in S$ $distance_j = 0$ $num = 0$ word $w$ such that $w\in e_i$ $max_d$ = 0 $num += 1$ word $u$ such that $u\in s_j$ $s_j\in S$0 $s_j\in S$1 = cosine similarity(w, u) $s_j\in S$2 $s_j\in S$3  $distance_j += max_d$ $distance_j /= num$ return $(distance_1, ..., distance_4)$ Given the body $S = \lbrace s_1, s_2, s_3, s_4\rbrace $ , a candidate ending $e_i$ and the label $y$ , we tokenize each sentence using NLTK and Standford's CoreNLP tools BIBREF35 . After deleting the stop words, we calculate the knowledge distance vector $D$ between the candidate ending and the body by Algorithm 1. We compute the similarity between two key-words using the cosine similarity of their vector space representations in numberbatch. For each sentence $s_i$ in the body, we then quantify the distance with the ending using averaged alignment score of every key-word in the ending. Then we use a linear layer to model the conditional probability $P_C$ : $$P_C(y|s_1, ..., s_4, e_i) = softmax(W_dD + b_d)$$   (Eq. 17) where $W_d$ and $b_d$ are parameters in the linear output layer, and $D$ is the four-dimensional distance vector.Finally, we predict the story ending by combining the above three sources of information. We utilize the feature vectors $h_M^k$ in the narrative sequence, $E_e$ in the sentiment evolution, and $D$ in the commonsense knowledge and calculate their cosine similarities. Then we concatenate them into a vector $g$ . We use a linear layer to model the combination gate and use that gate to combine three conditional probabilities. $$G &= softmax(W_gg + b_g) \\
\tilde{P}(y|s_1, ..., s_4, e_i) &= softmax(sum(G \odot [P_N; P_S; P_C]))$$   (Eq. 19)  where $W_g$ and $b_g$ are parameters in the linear layer, $(P_N, P_S, P_C)$ are the three probabilities modeled in ( 9 ), ( 15 ) and ( 17 ), $G$ is the hidden variable that weighs three different conditional probabilities and $\odot $ is element-wise multiplication.Finally, since each of the three components ( $P_N$ , $P_S$ and $P_C$ ) are either pre-trained on a separate corpus or individually tuned on the task, we fine-tune the entire model in an end-to-end manner by minimizing the following cost: $$\tilde{L} = L_{cm}(S) - \lambda * L_{lm}(C)$$   (Eq. 20) where $L_{cm}(s) = \sum -ylog(\tilde{P})$ is the cross-entropy between the final predicted probability and the true label, $L_{lm}$ is a regularization term of language model cost, and $\lambda $ is the regularization parameter.We evaluated our model on ROCStories BIBREF0 , a publicly available collection of commonsense short stories. This corpus consists of 100,000 five-sentence stories. Each story logically follows everyday topics created by Amazon Mechanical Turk (MTurk) workers. These stories contain a variety of commonsense causal and temporal relations between everyday events. Writers also develop an additional 3,742 stories which contain a four-sentence-long body and two candidate endings. The endings were collected by asking MTurk workers to write both a right ending and a wrong ending after eliminating original endings of given short stories. Both endings were required to include at least one character from the main story line and to make logical sense. and were tested on AMT to ensure the quality. The published ROCStories dataset is constructed with ROCStories as a training set that includes 98,162 stories that exclude candidate wrong endings, an evaluation set, and a test set, which have the same structure (1 body + 2 candidate endings) and a size of 1,871.We find that the dataset contains 43,095 unique words, and 28,012 key-words in ConceptNet. The average number of words and key-words in ConceptNet for each sentence are shown in Table 1 . $s_1$ , $s_2$ , $s_3$ and $s_4$ are four sentences in the body of stories. $e_1$ and $e_2$ are the two candidate endings. A large portion (65%) of words mentioned in stories are key-words in ConceptNet. Thus we believe ConceptNet can provide additional information to the model.In our experiments, we use a training set which does not have candidate endings to pre-train the sentiment prediction model. For learning to select the right ending, we randomly split 80% of stories with two candidates endings in ROCStories evaluation set as our training set (1,479 cases), 20% of stories in ROCStories evaluation set as our validation set (374 cases). And we utilize the ROCStories test set as our testing set (1,871 cases).We use the following models as our baselines:Msap BIBREF6 : Msap uses a linear classifier based on language modeling probabilities of the entire story, and utilizes linguistic features of the ending sentences. These ending “style” features include sentence length, word and character n-gram in each candidate ending (independent of story).HCM BIBREF8 : HCM uses FC-SemLM BIBREF36 in order to represent events in the story, learns sentiment trajectories in a form of N-gram language model, and uses topic-words' GloVe to extract topical consistency feature. It uses Expectation-Maximization for training.DSSM BIBREF31 : DSSM first uses two deep neural networks to project the context and the candidate endings into the same vector space, and ending choices based on the cosine similarity of the context.Cai BIBREF7 : Cai uses BiLSTM RNN with attention mechanisms to encode the body and ending of the story separately and uses a cosine similarity between their representations to calculate the score for each ending during selection process.SeqMANN BIBREF9 : SeqMANN uses a multi-attention neural network and introduces semantic sequence information extracted from FC-SemLM as external knowledge. The embedding layer concatenates five representations including word embedding, character feature, part-of-speech (POS) tagging, sentiment polarity and negation. The model uses DenseNet to match body with an ending.FTLM BIBREF10 : FTLM solves the stories cloze test by pre-training a language model using a multi-layer transformer on a diverse corpus of unlabeled text, followed by discriminative fine-tuning.We tune the hyper parameters of models on the validation set. Specifically, we set the dimension of LSTM for sentiment prediction to 64. We use a mini-batch size of 8, and Adam to train all parameters. The learning rate is set to 0.001 initially with a decay rate of 0.5 per epoch.We evaluated baselines and our model using accuracy as the metric on the ROCStories dataset, and summarized these results in Table 2 . The linear classifier with language model, Msap, achieved an accuracy of 75.2%. When adding additional features, such as sentiment trajectories and topic words to traditional machine learning methods, HCM achieved an accuracy of 77.6%. Recently, more neural network-based models are used. DSSM simply used a deep structured semantic model to learn representations for both bodies and endings only achieved an accuracy of 58.5%. Utilizing Cai improved neural model performance to 74.7% by applying attention mechanisms on a BiLSTM RNN structure. SeqMANN further improved the performance to 84.7%, when combining more information from embedding layers, like character features, part-of-speech (POS) tagging features, sentiment polarity, negation information and some external knowledge of semantic sequence. Researchers also improved model performance by pre-training word embeddings on external large corpus. FTLM pre-trained a language model on a large unlabeled corpus and fine-tuned on the ROCStories dataset, and achieved an accuracy of 86.5%.We tried two different ways to construct narrative sequence features: Plot&End and FullStory. Plot&End encodes the body and ending of a story separately and then computes their cosine similarity. We use a hierarchy structure to encode the four body sentences. However using such encoding method, our model only achieved an accuracy of 78.4%. One possible reason is that the relation between sentences learned through pre-trained language models are not fully explored if we encode each sentence separately. FullStory encodes all five sentences together. Our model achieved the best performance when using FullStory mode to encode narrative sequence information. We achieved an accuracy of 87.6%, outperforming all baseline models. Such improvement may come from the full use of the pre-trained transformer block, as well as the incorporation of the structured commonsense knowledge and sentiment information in the model.We conducted another two groups of experiments to investigate the contribution of the three different types of information: narrative sequence, sentiment evolution and commonsense knowledge. First, we measure the accuracy of only using one type of information at a time and describe the result in Table 3 . When we use just one type of information, the performances are worse than when using all of the information, suggesting a single type of information is insufficient for story ending selection. We also measure the performance of our model by stripping one type of information at a time and display the results in Table 4 . We observe that by removing the narrative sequence information, the model performance decreases most significantly. We suspect this is because the narrative chain is the key element that differentiates a story from other types of writing. Therefore, removing narrative sequence information makes it difficult to predict the story ending. If we only use the narrative sequence information, the performance is 85.3%. When commonsense knowledge is added to the model on top of the narrative sequence information, the performance improves to 87.2% which is statistically significant. When sentiment evolution information is added, the model only improves to 87.6%. We speculate this is because the pre-trained language model from narrative sequence information may already capture some sentiment information, as it is trained on an ensemble of several large corpus. This suggests that commonsense knowledge has a large impact on narrative prediction task.We present several examples to describe the decision made at the combination gate. All the examples are shown in Table 5 .The first story shows how narrative sequence can be the key in detecting the coherent story ending. This one tells a story of Agatha and birds. As we have analyzed in the narrative sequence, the narrative chain is apparently the most effective clue in deciding the right ending. In the combination gate, the narrative part's weight is 0.5135, which is larger than the sentiment component's weight, 0.2214 as well as the commonsense component's weight of 0.2633. The conditional probability of the correct ending given the narrative information is 0.8634, which is much larger than the wrong ending. As both sentences' sentiments are neutral, the sentiment information is not useful . And as the word “buy” has closer relation to “want" and “purchase" mentioned in the sentence body than the word,“return", the commonsense knowledge actually makes the wrong decision which gives slightly higher probabilities to the wrong ending(0.5642).The second story shows why and how sentiment evolution is influencing the final performance. It is a story about Jackson's beard: Jackson wanted to grow a beard regardless of what his friends said, and he was satisfied with his bushy, thick beard. Clearly the emotions between the two candidate endings are different. Based on the rule of consistent sentiment evolution, an appropriate ending should have a positive emotion rather than a negative emotion. The output of our model shows that in the combination gate, the sentiment evolution component received the largest weight, 0.4880, while the narrative sequence and the commonsense knowledge component have a weight of 0.2287 and 0.2833. Finally, the probability of the correct ending is 0.5360, larger than that of the wrong ending which is 0.4640 in sentiment part. Whereas in the narrative sequence component, the probability of the correct option is 0.4640, smaller than the wrong ending which is 0.5360. Other models like FTLM BIBREF10 that only rely on narrative sequence will make the wrong decision in this case. The probabilities of the commonsense knowledge component is 0.5257 versus 0.4725. Through combination gate, our model mainly relies on the sentiment to make a selection. As a result, it will identify the right ending despite other components influence toward a wrong decision.The third example presents the roles commonsense knowledge plays in our model. It tells a story about a person finding a dog. The sentiments of the two candidates are both neutral again. But based on the knowledge graph in ConceptNet, shown in Figure 4 , there exists many relations between the correct ending and the story body. The key-words in the ending are in red, and the key-words in the story body are in blue. The key-words such as “stray" and “collar" are highly associated with “dog" and “find" in the correct ending. The result shows that the gate gives the commonsense knowledge component a weight of 0.5156, which is the largest among the three components. The conditional probability of the correct ending considering commonsense information (0.5540) is larger than the wrong ending as we expected. In this case, the narrative sequence component makes the wrong decision, which gives higher probabilities to the wrong ending (0.5283). Thus models like FTLM BIBREF10 which only consider narrative chain will identify the wrong ending. However, as the combination gate learns to trust the commonsense knowledge component in this example more, our model still predicts the correct ending.We can see that our model is able to learn to rely on different information types based on the content of different stories. We obtain such model effectiveness by using a combination gate to fuse all three types of information, and in doing so, understand how all three are imperative in covering all possible variations in the dataset.However, it is still challenging for our model to handle the stories that have negations. Figure 5 shows an example. It tells a story between Johnny and Anita. But the only difference between two candidate endings is the negation word. Even when fusing three types of information, our model still cannot get the answer right. Because both event chains are about “asking Anita out", they are both neutral in sentiment, and the key-words in these two endings are the same as well. In the future, we plan to incorporate natural language inference information to the model to handle such cases.Narrative completion is a complex task that requires both explicit and implicit knowledge. We proposed a neural network model that utilized a combination gate to fuse three types of information including: narrative sequence, sentiment evolution and structured commonsense knowledge to predict story endings. The model outperformed state-of-the-art methods. We found that introducing external knowledge such as structured commonsense knowledge helps narrative completion.

Q: Which metrics are they evaluating with?