Multimodal Storytelling via Generative Adversarial Imitation Learning

1 Introduction

As the Internet becomes more pervasive, information overload becomes increasingly more severe. Even with the help of search engines such as Google and Yahoo, people cannot easily understand a series of coherent news events. For example, a person who desires to learn about the 2016 Presidential Election needs iteratively search through several keywords many times and review numerous news documents so that he or she can generate a cohesive picture, e.g., knowledge graph. Storytelling is an efficient way to solve this issue of information overload. By inferring the entity nodes connections, the original documents can be represented through a knowledge graph which consists of a set of storylines. Current works [Kumar et al., 2008; Hossain et al., 2012; Shahaf et al., 2012a; 2012b; Lin et al., 2012] mainly focus on this task but employ strict assumptions that may not capture meaningful stories. For instance, [Shahaf and Guestrin, 2010] argues that maximizing the weakest link makes good storylines, which can be reduced to density-based clustering. However, to model users' preferred stories, it requires to understand the evolution patterns, not merely to keep strong coherence.

Specifically, existing research in this area suffers from several shortcomings: (1) Strong assumptions can lead to poor storylines. Most related works manually design coherence metrics which are directly assumed to be associated with good storylines. However, a high consistency does not guarantee story quality, since good story might have other properties such interest, novelty, or user-preferred style. Therefore, the coherence based metric is not sufficient for modeling storylines. (2) Lack of multimodal learning. Existing works only focus on unimodal data such as Text Storytelling or Visual Storytelling, overlooking the cross-modality information. Multimodal learning can find entity linkages that a unimodal may miss. (3) Absence of benchmark dataset: Few prior works are reported to provide a publicly available dataset for imitation storytelling.

This paper focuses on directly imitating user-provided storylines rather than designing any indirect measures. The basic idea is to learn the connectivity features and structure in storylines so that the agent can reveal similar stories in other domains. This approach is illustrated in Figure 1. The September 11 attack event contains a storyline which shows the key entities related to the cause, perpetrators, victims, and the aftermath. Similarly, the event Charlie Hebdo Attack also has a story of a similar type. We argue that the two similar storylines share the same structure in a certain embedding space. Therefore, we can reveal similar stories in another event domain(Mexico Iguala mass kidnapping at the bottom). The inherent benefit of utilizing multimodal data is that humans often make inferences between the images and texts so as to resolve ambiguities.

Deep reinforcement learning can learn multi-step decisions. However, a critical difficulty in reinforcement learning is designing a reward function for optimizing the agent. Unlike game application in which there exists a responsive environment, it is dramatically difficult to design a reward function for storytelling due to the unavailability of such responses. Instead of proposing reward function, we introduce a typical Inverse Reinforcement Learning(IRL), imitation learning, to learn the latent policy. Imitating from demonstrations is a strategy in which an agent learns a hidden policy for a dynamic environment by observing demonstrations delivered by an expert agent. While IRL is often with two issues: instability and implicit policy. To solve these problems, Generative Adversarial Networks(GAN)[Goodfellow et al., 2014] mechanism is employed to solve the instability issue. GAN yields an internal generator model which can output policy explicitly after training, which addresses the second issue. Therefore, it is promising to integrate IRL with GAN to learn policy from users' demonstrations.

Different from previous work, our study treats storytelling as an imitation learning. Specifically, a policy is acquired from one event domain, and then transfer the policy to learn a storyline from another event. Furthermore, our work takes full advantage of multimodal data to improve the imitation performance. In this paper, we define a Multimodal Imitation Storytelling Task(MIST), and then propose a multimodal generative adversarial method that derives latent policy behind users' demonstrations without explicitly designing a reward function. The main contributions as follows:

• Proposing an imitation learning method for storytelling: To avoid the difficulty in designing reward function for storytelling, we enforce generative adversarial model on imitation learning. Using this learning strategy, the model can robustly model latent connectivity patterns.
• Designing a multimodal model integrated with GAN based imitation learning: Inspired by human's ability to link multiple entities through visual similarity, we propose a multimodal method across textual and visual modality with imitation learning. Our model learns reward functions from these two modalities and their correlation.
• Creating a benchmark dataset for multimodal imitation storytelling: A new multimodal storytelling dataset is collected from multiple attacks and civil unrest events. Under several selected topics, storylines are manually extracted and validated. Both texts and images are included in our dataset.

The rest of this paper is organized as follows. Section 2

reviews the related works. A detailed description of the proposed method is given in Section 3. Experiments on multiple public datasets and case study are presented in Section 4. We conclude the paper in Section 5.

2 RelatedWorks

Storytelling: The storyline generation problem was first studied by Kumar et al. [Kumar et al., 2008] as a generic redescription mining technique, by which a series of redescription between the given disjoint and dissimilar object sets and corresponding subsets are discovered. Storytelling is an efficient way to solve the issue of information overload. By extracting critical and connected entities, the original document is structurally summarized. Current works contain two categories: Textual Storytelling[Kumar et al., 2008; Hossain et al., 2012; Fang et al., 2011; Voskarides et al., 2015; Lee et al., 2012; Shahaf et al., 2012a; 2012b; Lin et al., 2012] and Visual Storytelling[Kim et al., 2014; Park and Kim, 2015; Wang et al., 2012]. Few works are reported to extract storylines based on both text and image. Current methods often suggest assumptions between good storyline and explicit metrics, such as average similarity or weakest similarity of all the neighbor nodes. However, these assumptions limit the generating meaningful stories since a user may have unique notions of good storylines. A few researchers employ Latent Dirichlet Allocation(LDA)[Zhou et al., 2015; Huang and Huang, 2013] to extract stories in unsupervised fashion. However, it is difficult for LDA to accurately model sequential data.

Reinforcement Learning: Starting from AlphaGo [Silver et al., 2016] and Atari[Mnih et al., 2015], numerous game applications [Lample and Chaplot, 2016; He et al., 2016; Oh et al., 2015; Narasimhan et al., 2016] enjoy the property of deep reinforcement learning in imitating sequential patterns. However, it is often difficult to design rewards function, especially for this real world problem. Other possible solutions include behavior cloning[Pomerleau, 1991], and Inverse Reinforcement Learning(IRL)[Russell, 1998; Ng et al., 2000] which can derive the underlying cost function under which the expert data is uniquely optimal. Unfortunately, behavior cloning learns a policy as a supervised learning problem over state-action pairs from expert trajectories and required large amounts of data because of compounding error caused by covariate shift. While IRL has stability issue and does not explicitly tell us how to act. Several works[Yu et al., 2017; Ho and Ermon, 2016] employ Generative Adversarial Networks(GAN) solve IRL issue. Hence we leverage GAN and IRL to effectively imitate user-provided storylines.

Multimodal Learning is to derive the patterns in associated cross-modality information. An example is that readers often estimate the relationship among news articles using the top images inside because if the images contain the same entity, they are probably involved in the same event. However, current works[Kiros et al., 2015][Srivastava and Salakhutdinov, 2012][Ngiam et al., 2011] focus on joint representation learning, paying little attention to sequence problem.

Different from the previous study, our work treats storytelling as a combination problem of imitation learning and multimodal learning. By employing GAN based imitation learning, our proposed model can learn and show the hidden policy. Moreover, this work takes full advantage of joint constraint on cross-modality data to improve the imitation performance.

3 Multimodal Imitation Storytelling

This section formally defines the task of imitation storytelling and then describes our proposed MIL-GAN model. In particular, a multimodal and GAN based imitation learning is elaborated in 3.2, the multimodal method we applied is introduced in 3.3.

3.1 Problem Setup

Based on a set of event document-storyline pairs {D, S}, our goal is to reveal the user generated policy πGuser . Each D is a documents collection and each S consist of several entity nodes {e}

Let M = {txt, img,mm} be the types of modalities appearing in D and S, which denote textual data, image and multimodal relationship between respectively. In the proposed method, a generator πGθ controlled by multimodal parameters θ = {θtxt , θimg , θmm} is used to approximate the users' policy generator πGuser .

Following REINFORCE algorithm[Williams, 1992], the collected rewards RT along the sequence starting from the initial state e0 = {etxt , eimg , emm} are maximized so as to optimize the generator. Utilizing GAN model, a discriminator Dφ yields rewards as the state score of the proposed generator. Since the Q value function is influenced by both the generator and discriminator, let QGθ Dφ denote the Q function. The learning process iteratively updates the objective function via gradient w.r.t. the parameters θ until convergence.

3.2 Imitation Learning via GAN

The intermediate rewards are set to zero for storytelling task because it's difficult to evaluate the generated storyline until it's complete. Following [Sutton et al., ],the objective of policy π (st| S1:t-1) is to generate a sequence starting from s0 to maximize the expected reward:

Because multimodal constraints involves several separate relationship embedded in text, image and their bi-directional coherence, the objective function is formulated as:

where QGθ Dφ (state, action) is the action-value function that estimates the expected accumulative reward from initial state e0. The Q value is from the rating on sequence generated by πGθ . When the discriminator consider the generated sequences real, the Q value will increase. The basic idea of estimating Q value is to treat it as the probability of the sequence being real considered by the discriminator, i.e., QGθ Dφ = Dφ. Due to the model limitation, only the sequence of fixed length can be evaluated by discriminator. However, incomplete sequence does provide partial information for rating. To estimate this incomplete portion of the sequence, the action-value function value is assigned with the expected rewards obtained from LSTM sampling controlled by πGθ . Therefore, the QGθ Dφ (S1:t-1, st) value is estimated as:

By using such Q values, the generator can update the objective function w.r.t. its parameters. Once generator finishes update, the sampling sequences mixed with the real data are fed into discriminator. Following the typical rules of GAN and an improvement[Arjovsky et al., 2017] that the original log operation of discriminator is removed, the discriminator will then improve the function:

As illustrated in Figure 2, the GAN iteratively updates the multimodal generators using Formula 3, and improves the multimodal discriminators by Formula 4. Following policy gradient theorem(episodic case) [Sutton et al., ], the gradient of the objective function J(θ) w.r.t. the parameters θ can be expressed as:

Theorem 3.1 (Multimodal Policy Gradient Theorem). The gradient of the objective function ∇θJ (θ) w.r.t. the parameter θ via policy gradient is:

Proof of Theorem 3.1. Let v denote the state value function. To keep the notation simple, we leave it implicit in all cases that v, π and Q are controlled by the generator Gθi . For each single modality, due to that intermediate rewards are set to zero, and state transferring probability γ is one-hot deterministic, we have:

Sum over modalities M on Eq. (6) is exactly Eq. (2), i.e., ∇θJ = ∑i∈M λi · ∇θiv (s0). Substitute v in Eq. (6) and Q in (5) iteratively:

We can re-write accumulative policy output as probability:

After repeating unrolling and apply Eq. (7), it is then immediate that:

In storytelling, each node can only be assigned with one entity, the policy function in the last term given a specific st reach lim T→∞ π (st S1:t-1) = inf π (st S1:t-1) = 0. Accordingly, the above equation becomes:

Using weighted likelihood [Sutton et al., ], the expectation inside Formula 3.1 can be decomposed using unbiased estimation. To keep the notation simple, we leave it implicit in all cases that π is a function of st given S1:t-1, and QGθ Dφ is a function of st and S1:t-1. Thus, the gradient can be estimated as:

The gradient can then be applied on the previous parameters as: θi ← θi + α∇θiJ (θi ), where α is learning rate. Algorithm 1 presents full details of the proposed method. First, we pre-train Gi on input set S. Then, the generator and discriminator are trained alternatively and periodically. When training the discriminator, positive examples are from the given dataset, while negative examples are sampled from the generator.

Algorithm 1: Multimodal Imitation Storytelling

Input: initialize generator policy πGθ and discriminator Dφ with random weights; multimodal storyline dataset Data = {E(ntity)1:T , I(mg)1:T }; event documents as knowledge base D

Output: Generator πGθ and discriminator Dφ; Newly-generated storyline sequences by πGθ on unseen test dataset.

• 1 // Pre-processing
• 2 Derive embeddings Ve on D and map entity E in Ve;
• 3 Compute representations Vi of based on D using multimodal learning, and map each of I1:T to Vi;
• 4 Generate the sequence S including Ve, Vi and Vi - Ve;
• 5 // Pre-training
• 6 Train πGθ using LSTM on S;
• 7 Generate negative samples using πGθ for training Dφ;
• 8 Feed Dφ with negative samples and real data;
• 9 Train Dφ via minimizing the cross entropy;
• 10 // GAN training

• 25 Apply πGθ on unseen dataset Data′ starting from randomly selected entity E′ ∈ Data′

3.3 Multimodal Learning

The task contains three types of modalities which are text, image, and their coherence. Entity words are encoded using word embeddings algorithm such as Word2Vec. Whereas our model expresses images in a semantic sentential space instead of word space since images contain massive information.

A SVD-based semantic embedding model is employed to derive vectors for images conditioning on contextual words. Denote the image vector I ∈ Mk(R) from a multimodal vector space and is associated with sentential description SEN = {w1, ...,wN} where wi indicates words. To represent the vectors I is to condition on the embedding vector of the description SEN. We aim to model the conditional distribution Pr(wn|w1:n-1,, I) of the following word wn given context from the contextual words and the vector I. Vocabulary embedding matrix with associated image vectors are represented using a tensor Ψ = Ik ⊗SENv×k ∈ Mv×k×k(R) where ⊗ mean tensor product in which any word in description is associated with related images. Given I, the model predicts word representation of the following words as a function of I and contextual words using tensor decomposition:

where the dimensionality of j is tunable. Σ denote a function which retain all the arguments on the diagonal after multiplication. This idea share resemblance with SVD in which the middle matrix is a diagonal matrix. The context is then represented as an intermediate variable which subject to the expectation of weights distribution among word pairs : C = Ev×v [U T jk Vfv(wi)]. Combining with I, we get another intermediate factor which encode context and image using Hadamard product ψ = (UC) · (V I). Using with softmax, the conditional probability Pr can be calculated. The true following words are used as true label for backpropagation method such as SGD, this neural networks iteratively update w.r.t. the parameters. The training parameters include Ujv, σjk, Vjk, and weights distribution Evv. The this model encodes image in a vector space Vi. Finally, the third modality is the sequential difference between word embeddings and image vectors.

4 Benchmark and Experiment Setting

The proposed method is evaluated on newly-proposed storytelling dataset 1 . To guide the model to discover desirable stories, manually labeled storylines are compiled for GAN training. Generator obtained in one event dataset was tested on another event corpus. This experiment shows if the generator is capable of deriving transferable storyline. Please note that different event datasets share no entities.

4.1 Benchmark Description andMetrics

Training set contain events from two major categories: Homicide and Protest. Homicide contains 1310 storylines, while Protest chooses 934 storylines. Two short examples are shown in Figure 1. They are from the most famous historical events, such as 9/11 Attack , Orlando Nightclub Attack, Occupy Wall Street, and Protest led by Martin Luther King. Each event contains several hundred documents. All the articles are taken from Google news and Wikipedia. Generators will be trained in the two categories separately. The Test set includes two event 2014 Iguala mass kidnapping 2 and Malaysia Airlines Flight 370 3 , since the two test events involve both homicide and protest sub-events. For data augmentation purpose, slicing window is employed to divide raw data into minimal sequence.

1 https://gist.github.com/aquastar/03dadfd751f5862ea0b44bb66996b490

Metrics: First the proposed method with several baselines are tested under convergence performance. Secondly, our evaluation conducts user studies via Amazon Mechanical Turk(AMT) cloud sourcing service, since the ultimate goal is to validate imitation behaviors.

4.2 Training Setting

Words are expressed using Word2Vec in each independent event corpus, while images are initially represented in VGG19 and then transferred to sentential space using multimodal learning. To normalize their shape, word vectors along each storyline are reduced by the vector of the first word in its storyline. Likewise, image vectors are reduced by the first image in each storyline. The same operation is also conducted on the multimodal sequence. For GAN model, the generator is implemented using LSTM model which accept continuous values. TextCNN[Zhang and LeCun, 2015] is used for discriminator since such CNN is effective for both text and image. Baselines include Random(Ran.), Scheduled sampling(SS)[Bengio et al., 2015], policy gradient(PG), and LSTM.

4.3 Initial Analysis

We evaluate our result with several established alternatives: random, scheduled sampling[Bengio et al., 2015] and policy gradient with similarity. Unfortunately, the baselines do not share the same metric or objective function. Instead, they were compared regarding accumulative normalized similarity on the training set:

where, sample A denotes sequence matrix from the userprovided data, and B is the output sequence matrix from models. The result is shown in Table (1).

2 https://en.wikipedia.org/wiki/2014 Iguala mass kidnapping

3 https://en.wikipedia.org/wiki/Malaysia Airlines Flight 370

Using the multimodal GAN, we improve the text-only model. One interesting point is that the image-only modality does not performance very well, but with other modalities, the performance increases. This makes sense because an image may contain too much information which is likely to lead to confusion. For instance, an image of original World Trade Center being attached could be either a victim object(the building) or an attacker (the attacking flight). With textual label such as victim, the image would be confined in a smaller and accurate semantic space.

The balance parameters λi=1,2,3 are all initialized to 1. After fine tuning, good performance often appear if more weights were assigned on text part. One good set example is [0.6, 0.3, 0.1] for [Ve, Vi , Vi -Ve] separately.

However, result of the training set can only show that the potential ability to achieve success, but it is not the ultimate evaluation. In next section, we conducted user study via Amazon Mechanical Turk(AMT) Service to directly assess users' satisfaction.

4.4 Evaluation via user study

Evaluating storytelling is a difficult task, due to the fact that there is no established golden standard, and even ground truth is hard to elicit. The ultimate goal of imitation storytelling is to help users discover customized storylines given users' examples. Therefore, a third-party user study via AMT is conducted, since it allows us to obtain accurate statistical information with a large sample size of users. It aims to test whether the generated storyline matches users' interests. We evaluate our result with the baselines mentioned in the last subsection.

In the study, workers were asked which storyline fit the given storyline best. Due to our dynamic reward per assignment in AMT, every minimal unit of cost is treated as one evaluation, so 1000 rating were collected. For each test event, several starting entities were randomly chosen. Storylines were generated from these starting entities using both our proposed method and baselines. For each unit task in AMT, workers were asked to choose the best one among those generated candidates gave event background knowledge such as Wikipedia or key news articles:

• 1st Step: AMT will be given E0, which denotes an event background and user-provided storyline S0 which is a user-define storyline. S0 contain a topic which is based on E0.
• 2nd Step: After AMT workers study the relationship between the storyline and event, they will be given another event E1 and a few machine generated storyline S1/S2/S3/S4. They are also related.
• 3rd Step: Based on their understanding of the relationship S0-E0, choose the best one that would have similar relationship: E1-S[?] among (S1,S2,S3,S4)

The final result as shown in Table 2 demonstrates that our proposed MIL-GAN was significantly preferred by users. T. slightly improve the preference beyond Schedule Sampling. Policy Gradient fails to capture the users' behavior.

4.5 case analysis

In this subsection, several typical examples are presented, and detailed analysis will be elaborated.

case 1: Mexico Murderer

• SS: Abarca→Flipe→Flipe→Guerrero
• PG: Abarca→Pineda→student→student
• T.: Abarca→gang→student→Guerrero
• MIL-GAN: Abarca→Flipe→Ayotzinapa→Guerrero

case 1: Mexico Drug Cartel

• SS: Cartel→Flipe→Flipe→Guerrero
• PG: Cartel→gang→gang→Sinaloa
• T.: Cartel→Drug→Pineda→gang
• MIL-GAN: Cartel→Pineda→Abarca→Flipe

case 2: MH370

• SS: Zaharie→wife→wife→cockpit
• PG: Zaharie→Flight→Fariq→training
• T.: Zaharie→Flight→Aisa→Search
• MIL-GAN: Zaharie→MH370→India→debris

We found that (1)The generated sequences from the baselines SS and PG often contains more vague words such as student and gang. These two baselines tend to overfit and often yield repeat nodes as in case 1 and 2. This suggests that the models without GAN are likely to overfit. (2) With GAN, the proposed models seems succeeded to avoid the overfit issue. Compared with SS and PG, T. and MIL-GAN tend to generate specific word rather than ambiguous ones. For example, in case 1, 2 and 3, T. and MIL-GAN generated specific words such as Aisa and debris. Compared with T., MIL-GAN generates even more specific entity name such as Ayotzinapa, Flipe and India. This implies that multimodal constraints does improve the unimodal performance.

5 Conclusion

In this paper, we proposed a multimodal imitation learning approach for generating storyline on unseen events. To avoid the reward function designing, GAN based imitation learning is introduced to learn the latent policy given users' demonstrations. To bridge the information gap between text and image, our model effectively integrates generative adversarial nets and multimodal learning via deterministic policy gradient. The different modalities learn from each other and potentially resolve confusion from each single modality. In our experiments, we utilized user-provided demonstration to explicitly illustrate the advantage of the proposed method beyond baselines. Associating with multimodal perspective, our model succeeds to capture the latent patterns across different modalities, and therefore reveal more satisfying storylines towards users' interests.