Hierarchical Neural Story Generation

Abstract: We explore story generation: creative systems that can build coherent and fluent passages of text about a topic. We collect a large dataset of 300K human-written stories paired with writing prompts from an online forum. Our dataset enables hierarchical story generation, where the model first generates a premise, and then transforms it into a passage of text. We gain further improvements with a novel form of model fusion that improves the relevance of the story to the prompt, and adding a new gated multi-scale self-attention mechanism to model long-range context. Experiments show large improvements over strong baselines on both automated and human evaluations. Human judges prefer stories generated by our approach to those from a strong non-hierarchical model by a factor of two to one.

Story-telling is on the frontier of current text generation technology: stories must remain thematically consistent across the complete document, requiring modeling very long range dependencies; stories require creativity; and stories need a high level plot, necessitating planning ahead rather than word-by-word generation BIBREF0 .
We tackle the challenges of story-telling with a hierarchical model, which first generates a sentence called the prompt describing the topic for the story, and then conditions on this prompt when generating the story. Conditioning on the prompt or premise makes it easier to generate consistent stories because they provide grounding for the overall plot. It also reduces the tendency of standard sequence models to drift off topic.
We find that standard sequence-to-sequence (seq2seq) models BIBREF1 applied to hierarchical story generation are prone to degenerating into language models that pay little attention to the writing prompt (a problem that has been noted in other domains, such as dialogue response generation BIBREF2 ). This failure is due to the complex and underspecified dependencies between the prompt and the story, which are much harder to model than the closer dependencies required for language modeling (for example, consider the subtle relationship between the first sentence and prompt in Figure FIGREF1 ).
To improve the relevance of the generated story to its prompt, we introduce a fusion mechanism BIBREF3 where our model is trained on top of an pre-trained seq2seq model. To improve over the pre-trained model, the second model must focus on the link between the prompt and the story. For the first time, we show that fusion mechanisms can help seq2seq models build dependencies between their input and output.
Another major challenge in story generation is the inefficiency of modeling long documents with standard recurrent architectures—stories contain 734 words on average in our dataset. We improve efficiency using a convolutional architecture, allowing whole stories to be encoded in parallel. Existing convolutional architectures only encode a bounded amount of context BIBREF4 , so we introduce a novel gated self-attention mechanism that allows the model to condition on its previous outputs at different time-scales.
To train our models, we gathered a large dataset of 303,358 human generated stories paired with writing prompts from an online forum. Evaluating free form text is challenging, so we also introduce new evaluation metrics which isolate different aspects of story generation.
Experiments show that our fusion and self-attention mechanisms improve over existing techniques on both automated and human evaluation measures. Our new dataset and neural architectures allow for models which can creatively generate longer, more consistent and more fluent passages of text. Human judges prefer our hierarchical model's stories twice as often as those of a non-hierarchical baseline.
We collect a hierarchical story generation dataset from Reddit's WritingPrompts forum. WritingPrompts is a community where online users inspire each other to write by submitting story premises, or prompts, and other users freely respond. Each prompt can have multiple story responses. The prompts have a large diversity of topic, length, and detail. The stories must be at least 30 words, avoid general profanity and inappropriate content, and should be inspired by the prompt (but do not necessarily have to fulfill every requirement). Figure FIGREF1 shows an example.
We scraped three years of prompts and their associated stories using the official Reddit API. We clean the dataset by removing automated bot posts, deleted posts, special announcements, comments from moderators, and stories shorter than 30 words. We use NLTK for tokenization. The dataset models full text to generate immediately human-readable stories. We reserve 5% of the prompts for a validation set and 5% for a test set, and present additional statistics about the dataset in Table TABREF4 .
For our experiments, we limit the length of the stories to 1000 words maximum and limit the vocabulary size for the prompts and the stories to words appearing more than 10 times each. We model an unknown word token and an end of document token. This leads to a vocabulary size of 19,025 for the prompts and 104,960 for the stories. As the dataset is scraped from an online forum, the number of rare words and misspellings is quite large, so modeling the full vocabulary is challenging and computationally intensive.
The challenges of WritingPrompts are primarily in modeling long-range dependencies and conditioning on an abstract, high-level prompt. Recurrent and convolutional networks have successfully modeled sentences BIBREF5 , BIBREF4 , but accurately modeling several paragraphs is an open problem. While seq2seq networks have strong performance on a variety of problems, we find that they are unable to build stories that accurately reflect the prompts. We will evaluate strategies to address these challenges in the following sections.
High-level structure is integral to good stories, but language models generate on a strictly-word-by-word basis and so cannot explicitly make high-level plans. We introduce the ability to plan by decomposing the generation process into two levels. First, we generate the premise or prompt of the story using the convolutional language model from BIBREF4 . The prompt gives a sketch of the structure of the story. Second, we use a seq2seq model to generate a story that follows the premise. Conditioning on the prompt makes it easier for the story to remain consistent and also have structure at a level beyond single phrases.
The length of stories in our dataset is a challenge for RNNs, which process tokens sequentially. To transform prompts into stories, we instead build on the convolutional seq2seq model of BIBREF6 , which uses deep convolutional networks as the encoder and decoder. Convolutional models are ideally suited to modeling long sequences, because they allow parallelism of computation within the sequence. In the Conv seq2seq model, the encoder and decoder are connected with attention modules BIBREF7 that perform a weighted sum of encoder outputs, using attention at each layer of the decoder.
CNNs can only model a bounded context window, preventing the modeling of long-range dependencies within the output story. To enable modeling of unbounded context, we supplement the decoder with a self-attention mechanism BIBREF8 , BIBREF9 , which allows the model to refer to any previously generated words. The self-attention mechanism improves the model's ability to extract long-range context with limited computational impact due to parallelism.
Gated Attention: Similar to BIBREF9 , we use multi-head attention to allow each head to attend to information at different positions. However, the queries, keys and values are not given by linear projections but by more expressive gated deep neural nets with Gated Linear Unit BIBREF4 activations. We show that gating lends the self-attention mechanism crucial capacity to make fine-grained selections.
Multi-Scale Attention: Further, we propose to have each head operating at a different time scale, depicted in Figure FIGREF7 . Thus the input to each head is downsampled a different amount—the first head sees the full input, the second every other input timestep, the third every third input timestep, etc. The different scales encourage the heads to attend to different information. The downsampling operation limits the number of tokens in the attention maps, making them sharper.
The output of a single attention head is given by DISPLAYFORM0 
 where INLINEFORM0 contains the hidden states up to time INLINEFORM1 at layer INLINEFORM2 , and INLINEFORM3 are gated downsampling networks as shown in Figure FIGREF7 . Unlike BIBREF9 , we allow the model to optionally attend to a 0 vector at each timestep, if it chooses to ignore the information of past timesteps (see Figure FIGREF8 ). This mechanism allows the model to recover the non-self-attention architecture and avoid attending to the past if it provides only noise. Additionally, we do not allow the self-attention mechanism to attend to the current timestep, only the past.
Unlike tasks such as translation, where the semantics of the target are fully specified by the source, the generation of stories from prompts is far more open-ended. We find that seq2seq models ignore the prompt and focus solely on modeling the stories, because the local dependencies required for language modeling are easier to model than the subtle dependencies between prompt and story.
We propose a fusion-based approach to encourage conditioning on the prompt. We train a seq2seq model that has access to the hidden states of a pretrained seq2seq model. Doing so can be seen as a type of boosting or residual learning that allows the second model to focus on what the first model failed to learn—such as conditioning on the prompt. To our knowledge, this paper is the first to show that fusion reduces the problem of seq2seq models degenerating into language models that capture primarily syntactic and grammatical information.
The cold fusion mechanism of BIBREF3 pretrains a language model and subsequently trains a seq2seq model with a gating mechanism that learns to leverage the final hidden layer of the language model during seq2seq training. We modify this approach by combining two seq2seq models as follows (see Figure FIGREF13 ): DISPLAYFORM0 
 where the hidden state of the pretrained seq2seq model and training seq2seq model (represented by INLINEFORM0 ) are concatenated to learn gates INLINEFORM1 . The gates are computed using a linear projection with the weight matrix INLINEFORM2 . The gated hidden layers are combined by concatenation and followed by more fully connected layers with GLU activations (see Appendix). We use layer normalization BIBREF10 after each fully connected layer.
Sequence-to-sequence neural networks BIBREF1 have achieved state of the art performance on a variety of text generation tasks, such as machine translation BIBREF1 and summarization BIBREF11 . Recent work has applied these models to more open-ended generation tasks, including writing Wikipedia articles BIBREF12 and poetry BIBREF13 .
Previous work on story generation has explored seq2seq RNN architectures BIBREF14 , but has focused largely on using various content to inspire the stories. For instance, BIBREF15 uses photos to inspire short paragraphs trained on romance novels, and BIBREF16 chain a series of independent descriptions together into a short story. BIBREF17 decompose story generation into two steps, first converting text into event representations, then modeling stories as sequences of events before translating back to natural language. Similarly, BIBREF18 generate summaries of movies as sequences of events using an RNN, then sample event representations using MCMC. They find this technique can generate text of the desired genre, but the movie plots are not interpretable (as the model outputs events, not raw text). However, we are not aware of previous work that has used hierarchical generation from a textual premise to improve the coherence and structure of stories.
Previous work has proposed decomposing the challenge of generating long sequences of text into a hierarchical generation task. For instance, BIBREF19 use an LSTM to hierarchically learn word, then sentence, then paragraph embeddings, then transform the paragraph embeddings into text. BIBREF20 generate a discrete latent variable based on the context, then generates text conditioned upon it.
Previous work has investigated the integration of language models with seq2seq models. The two models can be leveraged together without architectural modifications: BIBREF21 use language models to initialize the encoder and decoder side of the seq2seq model independently, and BIBREF22 combine the predictions of the language model and seq2seq model solely at inference time. Recent work has also proposed deeper integration. BIBREF23 combined a trained language model with a trained seq2seq model to learn a gating function that joins them. BIBREF3 propose training the seq2seq model given the fixed language model then learning a gate to filter the information from the language model.
We evaluate a number of baselines:
(1) Language Models: Non-hierarchical models for story generation, which do not condition on the prompt. We use both the gated convolutional language (GCNN) model of BIBREF4 and our additional self-attention mechanism.
(2) seq2seq: using LSTMs and convolutional seq2seq architectures, and Conv seq2seq with decoder self-attention.
(3) Ensemble: an ensemble of two Conv seq2seq with self-attention models.
(4) KNN: we also compare with a KNN model to find the closest prompt in the training set for each prompt in the test set. A TF-IDF vector for each prompt was created using fasttext BIBREF24 and faiss BIBREF25 was used for KNN search. The retrieved story from the training set is limited to 150 words to match the length of generated stories.
To train the fusion model, we first pretrain a Conv seq2seq with self-attention model on the WritingPrompts dataset. This pretrained model is fixed and provided to the second Conv seq2seq with self-attention model during training time. The two models are integrated with the fusion mechanism described in Section SECREF11 .
We implement models with the fairseq-py library in PyTorch. Similar to BIBREF6 , we train using the Nesterov accelerated gradient method BIBREF26 using gradient clipping BIBREF27 . We perform hyperparameter optimization on each of our models by cross-validating with random search on a validation set. We provide model architectures in the appendix.
We generate stories from our models using a top-k random sampling scheme. At each timestep, the model generates the probability of each word in the vocabulary being the likely next word. We randomly sample from the INLINEFORM0 most likely candidates from this distribution. Then, subsequent timesteps generate words based on the previously selected words. We find this sampling strategy substantially more effective than beam search, which tends to produce common phrases and repetitive text from the training set BIBREF28 , BIBREF29 . Sentences produced by beam search tend to be short and generic. Completely random sampling can introduce very unlikely words, which can damage generation as the model has not seen such mistakes at training time. The restriction of sampling from the 10 most likely candidates reduces the risk of these low-probability samples.
For each model, we tune a temperature parameter for the softmax at generation time. To ease human evaluation, we generate stories of 150 words and do not generate unknown word tokens.
For prompt generation, we use a self-attentive GCNN language model trained with the same prompt-side vocabulary as the sequence-to-sequence story generation models. The language model to generate prompts has a validation perplexity of 63.06. Prompt generation is conducted using the top-k random sampling from the 10 most likely candidates, and the prompt is completed when the language model generates the end of prompt token.
We propose a number of evaluation metrics to quantify the performance of our models. Many commonly used metrics, such as BLEU for machine translation or ROUGE for summarization, compute an n-gram overlap between the generated text and the human text—however, in our open-ended generation setting, these are not useful. We do not aim to generate a specific story; we want to generate viable and novel stories. We focus on measuring both the fluency of our models and their ability to adhere to the prompt.
For automatic evaluation, we measure model perplexity on the test set and prompt ranking accuracy. Perplexity is commonly used to evaluate the quality of language models, and it reflects how fluently the model can produce the correct next word given the preceding words. We use prompt ranking to assess how strongly a model's output depends on its input. Stories are decoded under 10 different prompts—9 randomly sampled prompts and 1 true corresponding prompt—and the likelihood of the story given the various prompts is recorded. We measure the percentage of cases where the true prompt is the most likely to generate the story. In our evaluation, we examined 1000 stories from the test set for each model.
For human evaluation, we use Amazon Mechanical Turk to conduct a triple pairing task. We use each model to generate stories based on held-out prompts from the test set. Then, groups of three stories are presented to the human judges. The stories and their corresponding prompts are shuffled, and human evaluators are asked to select the correct pairing for all three prompts. 105 stories per model are grouped into questions, and each question is evaluated by 15 judges.
Lastly, we conduct human evaluation to evaluate the importance of hierarchical generation for story writing. We use Amazon Mechanical Turk to compare the stories from hierarchical generation from a prompt with generation without a prompt. 400 pairs of stories were evaluated by 5 judges each in a blind test.
We analyze the effect of our modeling improvements on the WritingPrompts dataset.
Our proposed fusion model is capable of generating unique text without copying directly from the training set. When analyzing 500 150-word generated stories from test-set prompts, the average longest common subsequence is 8.9. In contrast, the baseline Conv seq2seq model copies 10.2 words on average and the KNN baseline copies all 150 words from a story in the training set.
Figure FIGREF27 shows the values of the fusion gates for an example story, averaged at each timestep. The pretrained seq2seq model acts similarly to a language model producing common words and punctuation. The second seq2seq model learns to focus on rare words, such as horned and robe.
However, the fusion model has limitations. Using random sampling to generate can produce errors. For example, can't is tokenized to ca n't, and the model occasionally produces the first token but misses the second. A similar error is after one line of dialogue, the model may move to another line of dialogue without generating a newline token. A further obstacle is repetition. The model focuses frequently on what it has recently produced, which leads to the generation of similar text multiple times.
In the generation of prompts using the GCNN language model, we find that prompts are fairly generic compared to human prompts. Language models often struggle to model rare words accurately, as the probability distribution over the next word is dominated by more common words. This tends to produce similar prompts, particularly at the start — we see many prompts that start with the man. In contrast, many of the human prompts are very unique (e.g. prompting stories in fantasy worlds such as Harry Potter and Game of Thrones) and the language model rarely produces the specific vocabulary required by these settings.
We analyze the encoder-decoder attention in the fusion model and find that unlike attention maps in machine translation, where each decoder timestep tends to attend to a different word on the encoder-side, the attention map for each decoder timestep looks similar and focuses mainly on salient words in the prompt. We further look at the usage of the self-attention layers within the decoder. While they could be leveraged to look at words generated very far in the past, at many timesteps the self-attention focuses on the recent past.
We have collected the first dataset for creative text generation based on short writing prompts. This new dataset pushes the boundaries of text generation by requiring longer range dependencies and conditioning on an abstract premise. Building on this dataset, we show through automatic and human evaluation that novel hierarchical models, self-attention mechanisms and model fusion significantly improves the fluency, topicality, and overall quality of the generated stories.
9 layers with hidden unit sizes INLINEFORM0 and convolutional kernel widths INLINEFORM1 . Learning rate 1, momentum 0.99, dropout 0.1, embedding size 300, l2 normalization INLINEFORM2 , 4 decoder self-attention heads.
3 layers in encoder with hidden unit sizes INLINEFORM0 and convolutional kernel widths INLINEFORM1 . 8 layers in the decoder with hidden unit sizes INLINEFORM2 with convolutional kernel widths INLINEFORM3 . Learning rate 0.25, momentum 0.99, dropout 0.3, embedding size 256, output embedding size 256, l2 nomalization INLINEFORM4 , 4 decoder self-attention heads.
Two different Conv seq2seq models were trained and ensembled together by averaging with equal weights.
The pretrained seq2seq model is the model in Section SECREF37 . The additional fused model has the following architecture:
5 layers in the encoder with hidden unit sizes INLINEFORM0 and convolutional kernel widths INLINEFORM1 . 5 layers in the decoder with hidden unit sizes INLINEFORM2 and convolutional kernel widths INLINEFORM3 . Learning rate 0.25, momentum 0.99, dropout 0.3, embedding size 256, output embedding size 256, l2 normalization INLINEFORM4 , 4 decoder self-attention heads.

Figure and table captions:
Figure 1: Example prompt and beginning of a story from our dataset. We train a hierarchical model that first generates a prompt, and then conditions on the prompt when generating a story.
Table 1: Statistics of WRITINGPROMPTS dataset
Figure 2: Self-Attention Mechanism of a single head, with GLU gating and downsampling. Multiple heads are concatenated, with each head using a separate downsampling function.
Figure 3: Multihead self-attention mechanism. The decoder layer depicted attends with itself to gate the input of the subsequent decoder layer.
Figure 4: Diagram of our fusion model, which learns a second seq2seq model to improve a pretrained model. The separate hidden states are combined after gating through concatenation.
Table 2: Effect of new attention mechanism. Gated multi-scale attention significantly improves the perplexity on the WRITINGPROMPTS dataset.
Table 3: Perplexity on WRITINGPROMPTS. We dramatically improve over standard seq2seq models.
Figure 5: Human accuracy at pairing stories with the prompts used to generate them. People find that our fusion model significantly improves the link between the prompt and generated stories.
Figure 6: Accuracy of prompt ranking. The fusion model most accurately pairs prompt and stories.
Figure 7: Accuracy on the prompt/story pairing task vs. number of generated stories. Our generative fusion model can produce many stories without degraded performance, while the KNN can only produce a limited number relevant stories.
Table 4: Effect of Hierarchical Generation. Human judges prefer stories that were generated hierarchically by first creating a premise and creating a full story based on it with a seq2seq model.
Figure 8: Average weighting of each model in our Fusion model for the beginning of the generated story for the prompt Gates of Hell. The fused model (orange) is primarily used for words which are closely related to the prompt, whereas generic words are generated by the pre-trained model (green).
Table 5: Example stories generated by the proposed hierarchical fusion approach compared to stories generated by a language model. Stories generated by the fusion model relate to the desired prompt and show increased coherence between sentences and ability to stay on one topic compared to the language modeling baseline.

Questions about this paper:
What human evaluation metrics do they look at?

Answers:
Accuracy at pairing stories with the prompts used to generate them; accuracy of prompt ranking