DeepStory: Video Story QA by Deep Embedded Memory Networks

1 Introduction

The question-answering (QA) problem is an important research theme in artificial intelligence, and many computational models have been proposed during the past few decades. Most traditional methods focused on knowledge representation and reasoning based on natural language processing with many hand-crafted syntactic and semantic features [Abney et al., 2000; Hovy et al., 2001]. Recently, deep learning methods have started to outperform traditional methods on text domain using convolutional neural networks [Yu et al., 2014], long short-term memory [Wang et al., 2015] and attention based deep models [Tan et al., 2016]. These methods are different from previous approaches in that they do not require any feature engineering and exploit a large amount of training data. The performance improvements have continuously extended to image QA tasks [Fukui et al., 2016; Kim et al., 2016].

However, the results in the video domain so far have lagged compared to that in the text or image settings. There are still very few methods and datasets to address the video story QA. [Kim et al., 2015] used a probablistic concept graph. [Tapaswi et al., 2016] built two story learning models separately from scenes and dialogues of videos and fused the final answer predictions of each model, i.e. averaging the answer prediction scores. This late fusion sometimes led to performance degradation because understanding video stories requires both scene and dialogue information together, not separately.

At this point, this paper provides two contributions to the video story QA problem. First, we construct a novel and large-scale video story QA dataset-PororoQA from children's popular cartoon videos series 'Pororo'. PororoQA has two properties that make it suitable as a test bed for video story QA. 1) Due to the characteristics of cartoon videos series, it has simple, clear but a coherent story structure and a small environment compared to other videos like dramas or movies. 2) The dataset provides high-quality scene descriptions to allow high-level video analysis. The new dataset consists of 16,066 video scene-dialogue pairs created from the videos of 20.5 hours in total length, 27,328 fine-grained descriptive sentences for scene descriptions and 8,913 multiple choice questions about the video stories. Each question is coupled with a set of five possible answers; one correct and four incorrect answers provided by human annotators. We plan to release the dataset to the community.

Second, we propose a video story learning model - Deep Embedded Memory Networks (DEMN). DEMN reconstructs stories from a joint stream of video scene-dialogue by combining scenes and dialogues in sentence forms using a latent embedding space. The video stories are stored in the long-term memory component that can be read and written to [Ha et al., 2015; Weston et al., 2015]. For a given QA pair, a word level attention-based LSTM evaluates the best answer by creating question-story-answer triplets using long-term memory and focusing on specific keywords. These processes pass through three modules (video story understanding module, story selection module, answer selection module) and, they are learned in a supervised learning setting.

We test our model on two different datasets - PororoQA and MovieQA and compare the results with various story QA models including human, VQA models, memory networks.

The experimental results show that the DEMN achieves state-of-the-art performances on both datasets by 1) the reconstruction of video stories in a scene-dialogue combined form using the latent embedding and 2) the attention.

2 Video Story QA

2.1 Task Statement

Figure 1 shows the overview of a video story QA task. We regard video X, e.g. an episode of a cartoon video series, as a compositional material consisting of a set of video scenes V={vi}1…|V|, and a set of dialogues L={li}1…|L|, where vi is a sequence of image frames (not single). li is a natural language sentence containing a dialogue. In our work, vi is paired with li, i.e. X={(vi,li)}1…|X|, and |X|=|V|=|L|. Also, we assume that there is a set of externally available sources E which is not included in the video itself but available for the video story QA task. For an external information source, we use a set of ground-truth scene descriptions E in which a description ei is one or multiple sentences describing the scene vi of video X. Considering that most videos in the real environment do not have fine-grained annotations, we let the QA model learn the relationships between the ground-truth descriptions and scenes of videos during training and retrieve the relevant descriptions ê from E at test time for newly observed scene.

We also formulate a video story QA task as a multi-choice QA task. Each video X has story-related questions and an answer sentence set for each question. Let q be a question about a story of a video X and, A be a hypothesis answer sentence set for q. A consists of k multiple choice answer sentences A={ar}1…k (in our work, k=5). Thus, the QA model should choose a correct answer sentence among the set of k possible answer sentences given a question q and a video X. In other words, given a scoring function F(X, q, ar), our goal is to pick the correct answer sentence a* that maximize F:

2.2 Related Datasets for Video Story QA

From the extensive literature review, MovieQA is the most similar public dataset to the video story QA task [Tapaswi et al., 2016]. This dataset contains 14K QA pairs about 408 movie stories and provides various information sources including video clips and descriptive sentences. However, to be more suitable as a testbed for the video story QA, certain points of MovieQA should be considered:

• Scenes of videos are not always provided for the QA tasks (6,462 questions can be answered using the scenes); most questions are answered only using the linguistic information sources such as dialogues, script, and plot.
• All questions are created from the plot synopsis of Wikipedia without watching movies.
• All movies have different characters and backgrounds, and complex and distant story structures that make optimization difficult.
• The descriptive sentences in MovieQA often contain contextual information not available within the provided video clip [Li et al., 2016], i.e. low cohesion between the scenes and descriptive sentences.

For these reasons, we created a new benchmark that 1) allows high-level video analysis with high-quality, large amounts of descriptive sentences, and 2) have simple, clear but a coherent story structure.

2.3 PororoQA Dataset

Because of its simple nature, cartoon images were used for exploring the high-level reasoning required to solve imageQA [Zitnick et al., 2013; Agrawal et al., 2015]. Similar to cartoon images, cartoon videos have a simple story structure and a small environment compared to other videos such as movies and dramas. In particular, cartoon series for kids have the properties that similar events are repeated, and the number of characters and background is small. We use a famous cartoon video series for children called 'Pororo', which consists of 171 episodes. Each episode has a different story of 7.2 minutes average length, and the amount of total running time is 20.5 hours. There are ten main characters in the entire video. The size of vocabulary is about 4,000.

Scene & dialogue pair construction: We extracted scenes by segmenting the videos based on the start/end times of speech of all the character in the videos and made 16,066 scene-dialogue pairs from the whole video. Note that the Please read carefully. Your work will be rejected if you don't follow the guide lines.

1. After selecting an episode and watching a Youtube video, please make story-related QAs in English. Please keep in mind that be sure to watch a video before making any data.

2. Please select a scene-subtitle pair that is most likely to match with your question and write down QAs. All questions should be localized in the video contents.

3. Please provide a correct answer to a question that most people would agree on and four wrong answers for deception.

4. Your answer should be a complete sentence with correct grammar. The minimum number of words in a sentence is four.

- "lunch" (x) -> "Pororo and Crong are having a lunch" (o)

5. Please avoid vague terms.

• "When did Pororo go there?" (x) -> "When did Pororo go Loopy's house?" (o)
• "What is Pororo doing?" (x) -> "What is Pororo doing when Crong is crying in the

house?" (o)

6. Please avoid completely unrelated questions.

- "How old is the earth" (x)

7. Please avoid image-specific (and not story-related) questions.

- "How many trees are in the video?" (x)

8. Please avoid creating duplicate questions in an episode.

9. Please use character names as follows.

Figure 2: The instructions shown to the AMT QA creators.

subtitles of the videos were used to make the dialogues; thus, the dialogues do not contain speaker information. A scene has 34 image frames on average.

Descriptive sentences collection: The descriptive sentences and QAs were collected through our website. We made all the videos and the scene-dialogue pairs visible to human annotators. The annotators could provide data directly on the site after viewing the videos and the scene-dialogue pairs. We converted each scene to an animated GIF to be displayed on the site. Then we asked the human annotators from Amazon Mechanical Turk (AMT) to visit the site and concretely describe each scene in one or multiple sentences following the guidelines. Total 27,328 descriptive sentences were collected from the human annotators. The average number of sentences and words in the scene description is 1.7 and 13.6. Table 1 shows the advantage of our descriptions over that of MovieQA; the descriptions are well associated with the visual stories. For the evaluation, we randomly selected 100 samples from each dataset and recruited ten persons to score on each question between 0 and 1.

QA collection: We recruited AMT workers different from the workers who participated in making the descriptive sentences. They were asked to watch the videos before creating any QA and then asked to make questions about the video stories with a correct answer and four wrong answers for each question. The descriptive sentences were not given to the annotators. Next, they gave the context for each question by localizing the question to a relevant scene-dialogue pair in the video. In other words, each question has a relevant scene-dialogue pair which contains information about the answer. After excluding QA pairs that do not follow the guidelines, e.g., vague or irrelevant ones such as "where are they?" or 'how many trees in the videos?", we obtained 8,913 QA pairs. The average number of QA per episode, i.e. a video, is 52.15. The average numbers of words in the question and answer is 8.6 and 7.3. Figure 2 shows the guildleines given to the AMT workers. Table 2 shows the examples and statistics by types of the questions.

Dataset comparison: We compare our dataset to other existing public video datasets in Table 3. To the best of our knowledge, PororoQA has the highest number of videoQA, as well as is the first video dataset that have a coherent storyline throughout the dataset. We plan to release the PororoQA dataset to the community as our contribution.

3 Deep Embedded Memory Networks

Memory networks, initially proposed for text QA, use an explicit memory component and model the relationships between the story, question, and answer [Weston et al., 2015].

In video story QA, these ideas have to be extended such that the model understands video stories from a joint stream of two modalities, i.e scene and dialogue, and gives attention to specific pieces of evidence to answer correctly. Figure 3 shows the structure of our proposed model DEMN for video story QA. DEMN takes a video X={(vi,li)}1…|X| as input, where vi is a scene (a sequence of image frames), and li is a dialogue (a natural language sentence). A QA task passes through three modules as described below.

3.1 Video Story Understanding Module

The main objective of this module is to reconstruct video stories in the form of sentences from the scene-dialogue streams of the observed videos. At training time (trained independently with other modules), the module learns a scene embedding matrix M1 and a dialogue embedding matrix M2. At test time, the module transforms each scene-dialogue pair to a video story in the following way:

• Deep residual networks [Kaiming et al., 2016] and an encoder-decoder deep model [Kiros et al., 2015b] compute a visual-linguistic features pair (vi, li) for an input scene-dialogue pair (vi, li).
• Combined vector ci is the sum of embedded representation of the scene vi T M1 and representation of the corresponding dialogue li, i.e. ci = vi T M1 + li.
• The module retrieves the nearest description êi to ci by measuring the dot-product similarity of the embedded combined vector ci T M2 and the deep representation êi of the description êi.
• We define a video story si as a concatenation of êi and li. The output S is a set of video stories for the input video X, i.e. S={si}1…|X| ={êi || li}1…|X|. || means concatenation. For example, si can be 'There are three friends on the ground. The friends are talking about the new house.' Each story si is stored in a long-term memory component, e.g. a table.

Training: We use the scene-dialogue-ground truth description pairs in the training dataset to learn M1 and M2. First, we train a scene embedding matrix M1 using a combination of hinge rank loss and dot-product score [Weston et al., 2010; Frome et al., 2013; Kiros et al., 2015a] such that the M1 is trained to achieve a higher dot-product score between the embedded representation of the scene and the representation of the corresponding dialogue than the scores between non-corresponding combinations. Thus, the per training example hinge rank loss is as follows:

where vtr is a scene in the training video dataset and, vtr is a vector of aggregation of image features computed from each frame of vtr. We used the average pooling of 2,048-D sized 200-layer residual networks activations [Kaiming et al., 2016]. ltr is a corresponding dialogue for vtr and, ltr is a feature vector of ltr computed from 4,800-D skip-thought vectors pre-trained using Wikipedia and the dialogue corpus in 'Pororo' cartoon videos [Kiros et al., 2015b]. lj is a feature vector of a contrastive (non-corresponding) dialogue sentence for vtr. We use the same deep models when computing features for scenes and dialogues at the test time. M1 is the embedding matrix of trainable parameters pre-trained with scene-descriptive sentence pairs from MPII-MD dataset [Rohrbach et al., 2015]. We use stochastic gradient descent (SGD) to train M1. γu is a margin and fixed as 1 during training time.

After M1 is trained, we compute a combined vector ctr for each pair (vtr, ltr) by summing the embedded scene vector vtr T M1 and the representation of corresponding dialogue ltr. Then, we train M2 in the same way such that embedding of ctr, i.e. ctr T M2, and the deep representation etr for the ground-truth description etr of vtr achieves a higher dot-product score than the scores between ctr and contrastive description vectors ej. Note that all denoted vectors, i.e. vtr, ltr, lj, ctr, etr, ej are normalized to unit length.

3.2 QA Modules

Story selection module: The key function of the module is to recall the best video story s* that contains the answer information to the question q. The module reads the list of the stories S = {si}1…|X| of the input video X from long-term memory and scores each story si by matching with q. The highest scoring relevant story is retrieved with:

where G is a function that scores the match between the pair of q and si. The output of the module sa is q || s*, which fuses the question and the relevant story. An example of sa is 'What were the friends doing on the ground? There are three friends on the ground. The friends are talking about the new house'.

Answer selection module: This module selects the most appropriate answer a* in the answer set A={ar}1…k. Similar to the story selection module, this module scores the match between the pair of the sa and each answer sentence ar. The highest scoring answer sentence is selected with:

where H is a scoring function that matches between the pair. Scoring function: To handle the long sentences such as si or sa, the word level attention-based model [Tan et al., 2016] is used as the scoring functions G and H. The model builds the embeddings of two sequences of tokens X={xi}1…|X|, Y={yi}1…|Y| and measure their closeness by cosine similarity. X and Y can be a video story, a question or an answer sentence. The model encodes each token of X, Y using a bidirectional LSTM [Hochreiter et al., 1997; Schuster et al., 1997] and calculates the sentence vector X by averaging the output token vectors of the bidirectional LSTM on the X side. Then the each token vector of Y are multiplied by a softmax weight, which is determined by X.

where hy(t) is the t-th token vector on the Y side. h′y(t) is the updated t-th token vector. Wa, Wq, wms are attention parameters. The sentence vector Y is calculated by averaging the updated token vectors on the Y side.

Training: We train the QA modules in a fully supervised setting. Each question q in the training data set is associated with a list of scene-dialogue pairs {(vi, li)}1…|X| of a video X to which the q belongs and their respective judgements {y s i}1…|X|, where y s i = 1 if (vi, li) is correctly relevant for q, and y s i=0 otherwise. Also, each q is associated with a list of answer sentences {ar}1…k with their judgments {y a r}1…k, where y a r = 1 if the ar is the correct answer for q, and y a r = 0 otherwise. In our setting, there is one relevant scene-dialogue pair and correct answer for each q. We considered each data instance as two triplets (q, (vi, li), y s i), (q, ar, y a r) and convert them to (q, si, y s i) and (sa, ar, y a r), where si is êi || li, and sa is q || êc || lc. êi means the description of vi retrieved by the video story understanding module. Subscript c is an index of the correctly relevant scene-dialogue pair for q, i.e. y s c = 1. Training is performed with a hinge rank loss over these two triplets:

where s* is the correct relevant story for q, i.e. s* = êc || lc, and a* is the correct answer sentence for q. γs and γa are margins fixed as 1 during training time.

4 Experimental Results

4.1 Experimental Setup

We split all 171 episodes of the 'Pororo' videos into 60% training (103 episodes) / 20% validation (34 episodes) / 20% test (34 episodes). The number of QA pairs in training / validation / test are 5521 / 1955 / 1437. The evaluation methods are QA accuracy and Mean Reciprocal Rank (MRR). MRR is used to evaluate the story selection module of the models, and its value informs the average of the inverse rank of the correct relevant story among a video story set S.

4.2 Model Experiments on PororoQA

We intend to measure 1) human performance on the PororoQA task, 2) performance of existing story QA models, 3) performance comparison between the proposed model and other story QA models. The performances were evaluated for ablation experiments with all possible input combinations (Q: question, L: dialogue, V: scene, E: ground-truth descriptions). We briefly describe the human experiments, the comparative models, and our model setting.

Human baselines: In each experiment, six human evaluators answered all questions in the test set.

BoW / W2V / LSTM Q+V: These are baseline models used in the VQA challenge [Agrawal et al., 2015]. For video story QA task (Q+L+V), we extended the models by replacing the image input to the video scene input and adding an extra input (or two inputs for L+E) to the models to use linguistic sources in videos, such as dialogues or descriptions. To represent language, they used 2,000-D bag-of-word, the average pooling of 2,000-D word2vec [Mikolov et al., 2013], and 4,800-D skip-thoughts vectors. These linguistic features were fused with visual features calculated from the average pooling of 200-layer residual networks activations.

Memory networks / end-to-end memory networks: Memory networks and end-to-end memory networks [Sukhbaatar et al., 2015] were initially proposed for text story QA. For the video story QA task (Q+L+V), these models were extended by [Tapaswi et al., 2016]. They separately built two story QA models using scenes (Q+V) and dialogues (Q+L). Then fused the QA results from the last components of the models. The visual story models retrieved the descriptions ê as a proxy for the scenes like our model.

DEMN: We evaluated the DEMN with two modes, i.e. with and without attention. We used linear neural networks as alternative scoring functions G and H. Also, the DEMN and the (end-to-end) memory networks did not retrieve the descriptions for all ablation experiments involving V+E but used the ground-truth descriptions instead.

Results: We report human performances on the PororoQA task. The first row in Table 4 shows the human performances on the experiments. Videos were important in the majority of the questions. As more information was provided, human performance was significantly improved. We found that there was more useful information in the descriptions to answer questions than the dialogues. Overall, humans achieved a high accuracy of 96.9%.

The remaining rows in Table 4 show the performances of the QA models. Unlike images, the visualQA models failed to solve the QAs only with the visual features (Q+V). Also, they had difficulty using the sequences of the long dialogues and descriptions. The end-to-end memory networks do not use the supervisions between questions and relevant scene-dialogue labels, so performances were lower than the memory networks. The memory networks had similar performances to the DEMN that do not use attention when there was one story modality (Q+L, Q+V, Q+E or Q+V+E). However, when using linguistic stories and visual stories together (Q+L+V, Q+L+E or Q+L+V+E), DEMN was able to achieve better performances. Our combined video story reconstruction led to improved MRR scores (0.19 and 0.20) and thus QA accuracies. Using attention, DEMN showed the best performance than the other models. However, there is still room for performance improvement when comparing differences in performance with humans, or performance differences depending on whether E is used. Figure 4 shows the qualitative results of the DEMN on the PororoQA tasks.

4.3 Model Experiments on MovieQA Benchmark

The MovieQA benchmark dataset provides 140 movies and 6,462 multiple choices QAs. We report the accuracies of DEMN in Table 5. At the time of submission of the paper, DEMN achieved state-of-the-art results on both the validation set (44.7%) and test set (30.0%) for video QA mode. To understand the scenes, we used a description set from MPII-MD [Rohrbach et al., 2015] as E. We assume that the reason for the relatively low performance on MovieQA is that unlike PororoQA, there are many different story structures that make optimization difficult.

5 Concluding Remarks

We proposed the video story QA model DEMN with the new video story QA dataset-PororoQA. PororoQA has simple, coherent story-structured videos and high-quality scene descriptions. We demonstrated the potential of our model by showing state-of-the-art performances on PororoQA and MovieQA. Our future work is to explore methods such as curriculum learning [Bengio et al., 2009] that may help optimize in more complex story structures using PororoQA.

Acknowlegdements

This work was partly supported by the ICT R&D program of MSIP/IITP. [2017-0-00162, Development of Human-care Robot Technology for Aging Society] and [2015-0-00310 -SWStarLab, Autonomous Cognitive Agent Software That Learns Real-Life with Wearable Sensors].