A Hierarchical Neural Autoencoder for Paragraphs and Documents

Introduction

Generating coherent text is a central task in natural language processing. A wide variety of theories exist for representing relationships between text units, such as Rhetorical Structure Theory [Mann and Thompson (1988] or Discourse Representation Theory [Lascarides and Asher (1991], for extracting these relations from text units [Marcu (2000, LeThanh et al. (2004, Hernault et al. (2010, Feng and Hirst (2012, inter alia], and for extracting other coherence properties characterizing the role each text unit plays with others in a discourse [Barzilay and Lapata (2008, Barzilay and Lee (2004, Elsner and Charniak (2008, Li and Hovy (2014, inter alia]. However, applying these to text generation remains difficult. To understand how discourse units are connected, one has to understand the communicative function of each unit, and the role it plays within the context that encapsulates it, recursively all the way up for the entire text. Identifying increasingly sophisticated human-developed features may be insufficient for capturing these patterns. But developing neural-based alternatives has also been difficult. Although neural representations for sentences can capture aspects of coherent sentence structure [Ji and Eisenstein (2014, Li et al. (2014, Li and Hovy (2014], it’s not clear how they could help in generating more broadly coherent text.

Recent LSTM models [Hochreiter and Schmidhuber (1997] have shown powerful results on generating meaningful and grammatical sentences in sequence generation tasks like machine translation [Sutskever et al. (2014, 1, Luong et al. (2015] or parsing [Vinyals et al. (2014]. This performance is at least partially attributable to the ability of these systems to capture local compositionally: the way neighboring words are combined semantically and syntactically to form meanings that they wish to express.

Could these models be extended to deal with generation of larger structures like paragraphs or even entire documents? In standard sequence-to-sequence generation tasks, an input sequence is mapped to a vector embedding that represents the sequence, and then to an output string of words. Multi-text generation tasks like summarization could work in a similar way: the system reads a collection of input sentences, and is then asked to generate meaningful texts with certain properties (such as—for summarization—being succinct and conclusive). Just as the local semantic and syntactic compositionally of words can be captured by LSTM models, can the compositionally of discourse releations of higher-level text units (e.g., clauses, sentences, paragraphs, and documents) be captured in a similar way, with clues about how text units connect with each another stored in the neural compositional matrices?

In this paper we explore a first step toward this task of neural natural language generation. We focus on the component task of training a paragraph (document)-to-paragraph (document) autoencoder to reconstruct the input text sequence from a compressed vector representation from a deep learning model. We develop hierarchical LSTM models that arranges tokens, sentences and paragraphs in a hierarchical structure, with different levels of LSTMs capturing compositionality at the token-token and sentence-to-sentence levels.

We offer in the following section to a brief description of sequence-to-sequence LSTM models. The proposed hierarchical LSTM models are then described in Section 3, followed by experimental results in Section 4, and then a brief conclusion.

Long-Short Term Memory (LSTM)

In this section we give a quick overview of LSTM models. LSTM models [Hochreiter and Schmidhuber (1997] are defined as follows: given a sequence of inputs $X=\{x_{1},x_{2},...,x_{n_{X}}\}$, an LSTM associates each timestep with an input, memory and output gate, respectively denoted as $i_{t}$, $f_{t}$ and $o_{t}$. For notations, we disambiguate $e$ and $h$ where $e_{t}$ denote the vector for individual text unite (e.g., word or sentence) at time step t while $h_{t}$ denotes the vector computed by LSTM model at time t by combining $e_{t}$ and $h_{t-1}$. $\sigma$ denotes the sigmoid function. The vector representation $h_{t}$ for each time-step $t$ is given by:

$f(h_{t-1},e_{y_{t}})$ denotes the activation function between $e_{h-1}$ and $e_{y_{t}}$, where $h_{t-1}$ is the representation outputted from the LSTM at time $t-1$. Note that each sentence ends up with a special end-of-sentence symbol $<$end$>$. Commonly, the input and output use two different LSTMs with different sets of convolutional parameters for capturing different compositional patterns.

In the decoding procedure, the algorithm terminates when an $<$end$>$ token is predicted. At each timestep, either a greedy approach or beam search can be adopted for word prediction. Greedy search selects the token with the largest conditional probability, the embedding of which is then combined with preceding output for next step token prediction. For beam search, [Sutskever et al. (2014] discovered that a beam size of 2 suffices to provide most of benefits of beam search.

Paragraph Autoencoder

In this section, we introduce our proposed hierarchical LSTM model for the autoencoder.

Let $D$ denote a paragraph or a document, which is comprised of a sequence of $N_{D}$ sentences, $D=\{s^{1},s^{2},...,s^{N_{D}},{end}_{D}\}$. An additional ”$end_{D}$” token is appended to each document. Each sentence $s$ is comprised of a sequence of tokens $s=\{w^{1},w^{2},...,w^{N_{s}}\}$ where $N_{s}$ denotes the length of the sentence, each sentence ending with an “$end_{s}$” token. The word $w$ is associated with a $K$-dimensional embedding $e_{w}$, $e_{w}=\{e_{w}^{1},e_{w}^{2},...,e_{w}^{K}\}$. Let $V$ denote vocabulary size. Each sentence $s$ is associated with a K-dimensional representation $e_{s}$.

An autoencoder is a neural model where output units are directly connected with or identical to input units. Typically, inputs are compressed into a representation using neural models (encoding), which is then used to reconstruct it back (decoding). For a paragraph autoencoder, both the input $X$ and output $Y$ are the same document $D$. The autoencoder first compresses $D$ into a vector representation $e_{D}$ and then reconstructs $D$ based on $e_{D}$.

For simplicity, we define $LSTM(h_{t-1},e_{t})$ to be the LSTM operation on vectors $h_{t-1}$ and $e_{t}$ to achieve $h_{t}$ as in Equ.1 and 2. For clarification, we first describe the following notations used in encoder and decoder:

$e_{t}^{w}$ and $e_{t}^{s}$ denotes word-level and sentence-level embedding for word and sentence at position $t$ in terms of its residing sentence or document.

2 Model 1: Standard LSTM

The whole input and output are treated as one sequence of tokens. Following ?) and ?), we trained an autoencoder that first maps input documents into vector representations from a $LSTM_{\text{encode}}$ and then reconstructs inputs by predicting tokens within the document sequentially from a $LSTM_{\text{decode}}$. Two separate LSTMs are implemented for encoding and decoding with no sentence structures considered. Illustration is shown in Figure 1.

3 Model 2: Hierarchical LSTM

The hierarchical model draws on the intuition that just as the juxtaposition of words creates a joint meaning of a sentence, the juxtaposition of sentences also creates a joint meaning of a paragraph or a document.

We first obtain representation vectors at the sentence level by putting one layer of LSTM (denoted as $LSTM_{\text{encode}}^{\text{word}}$) on top of its containing words:

The vector output at the ending time-step is used to represent the entire sentence as

To build representation $e_{D}$ for the current document/paragraph $D$, another layer of LSTM (denoted as $LSTM_{\text{encode}}^{\text{sentence}}$) is placed on top of all sentences, computing representations sequentially for each timestep:

Representation $e_{{end_{D}}}^{s}$ computed at the final time step is used to represent the entire document: $e_{D}=h_{{end_{D}}}^{s}$.

Thus one LSTM operates at the token level, leading to the acquisition of sentence-level representations that are then used as inputs into the second LSTM that acquires document-level representations, in a hierarchical structure.

Decoder

As with encoding, the decoding algorithm operates on a hierarchical structure with two layers of LSTMs. LSTM outputs at sentence level for time step $t$ are obtained by:

The initial time step $h_{0}^{s}(d)=e_{D}$, the end-to-end output from the encoding procedure. $h_{t}^{s}(d)$ is used as the original input into $LSTM_{\text{decode}}^{word}$ for subsequently predicting tokens within sentence $t+1$. $LSTM_{\text{decode}}^{word}$ predicts tokens at each position sequentially, the embedding of which is then combined with earlier hidden vectors for the next time-step prediction until the $end_{s}$ token is predicted. The procedure can be summarized as follows:

During decoding, $LSTM_{\text{decode}}^{word}$ generates each word token $w$ sequentially and combines it with earlier LSTM-outputted hidden vectors. The LSTM hidden vector computed at the final time step is used to represent the current sentence.

This is passed to $LSTM_{\text{decode}}^{sentence}$, combined with $h_{t}^{s}$ for the acquisition of $h_{t+1}$, and outputted to the next time step in sentence decoding.

For each timestep $t$, $LSTM_{\text{decode}}^{sentence}$ has to first decide whether decoding should proceed or come to a full stop: we add an additional token $\text{end}_{D}$ to the vocabulary. Decoding terminates when token $\text{end}_{D}$ is predicted. Details are shown in Figure 2.

4 Model 3: Hierarchical LSTM with Attention

Attention models adopt a look-back strategy by linking the current decoding stage with input sentences in an attempt to consider which part of the input is most responsible for the current decoding state. This attention version of hierarchical model is inspired by similar work in image caption generation and machine translation [Xu et al. (2015, 1].

Let $H=\{h_{1}^{s}(e),h_{2}^{s}(e),...,h^{s}_{N}(e)\}$ be the collection of sentence-level hidden vectors for each sentence from the inputs, outputted from $LSTM_{\text{encode}}^{\text{Sentence}}$. Each element in H contains information about input sequences with a strong focus on the parts surrounding each specific sentence (time-step). During decoding, suppose that $e_{t}^{s}$ denotes the sentence-level embedding at current step and that $h_{t-1}^{s}(\text{dec})$ denotes the hidden vector outputted from $LSTM_{decode}^{sentence}$ at previous time step $t-1$. Attention models would first link the current-step decoding information, i.e., $h_{t-1}^{s}(\text{dec})$ which is outputted from $LSTM_{dec}^{sentence}$ with each of the input sentences $i\in[1,N]$, characterized by a strength indicator $v_{i}$:

The attention vector is then created by averaging weights over all input sentences:

LSTM hidden vectors for current step is then achieved by combining $c_{t}$, $e_{t}^{s}$ and $h_{t-1}^{s}(\text{dec})$:

5 Training and Testing

Parameters are estimated by maximizing likelihood of outputs given inputs, similar to standard sequence-to-sequence models. A softmax function is adopted for predicting each token within output documents, the error of which is first back-propagated through $LSTM_{\text{decode}}^{word}$ to sentences, then through $LSTM_{\text{decode}}^{sentence}$ to document representation $e_{D}$, and last through $LSTM_{\text{encode}}^{sentence}$ and $LSTM_{\text{encode}}^{word}$ to inputs. Stochastic gradient descent with minibatches is adopted.

For testing, we adopt a greedy strategy with no beam search. For a given document $D$, $e_{D}$ is first obtained given already learned LSTM${}_{\text{encode}}$ parameters and word embeddings. Then in decoding, $LSTM_{\text{decode}}^{\text{sentence}}$ computes embeddings at each sentence-level time-step, which is first fed into the binary classifier to decide whether sentence decoding terminates and then into $LSTM_{\text{decode}}^{\text{word}}$ for word decoding.

Experiments

We implement the proposed autoencoder on two datasets, a highly domain specific dataset consisting of hotel reviews and a general dataset extracted from Wkipedia.

We use a subset of hotel reviews crawled from TripAdvisor. We consider only reviews consisting sentences ranging from 50 to 250 words; the model has problems dealing with extremely long sentences, as we will discuss later. We keep a vocabulary set consisting of the 25,000 most frequent words. A special “$<$unk$>$” token is used to denote all the remaining less frequent tokens. Reviews that consist of more than 2 percent of unknown words are discarded. Our training dataset is comprised of roughly 340,000 reviews; the testing set is comprised of 40,000 reviews. Dataset details are shown in Table 1.

Wikipedia

We extracted paragraphs from Wikipedia corpus that meet the aforementioned length requirements. We keep a top frequent vocabulary list of 120,000 words. Paragraphs with larger than 4 percent of unknown words are discarded. The training dataset is comprised of roughly 500,000 paragraphs and testing contains roughly 50,000.

2 Training Details and Implementation

Previous research has shown that deep LSTMs work better than shallow ones for sequence-to-sequence tasks [Vinyals et al. (2014, Sutskever et al. (2014]. We adopt a LSTM structure with four layer for encoding and four layer for decoding, each of which is comprised of a different set of parameters. Each LSTM layer consists of 1,000 hidden neurons and the dimensionality of word embeddings is set to 1,000. Other training details are given below, some of which follow ?).

LSTM parameters and word embeddings are initialized from a uniform distribution between [-0.08, 0.08].

Stochastic gradient decent is implemented without momentum using a fixed learning rate of 0.1. We stated halving the learning rate every half epoch after 5 epochs. We trained our models for a total of 7 epochs.

Decoding algorithm allows generating at most 1.5 times the number of words in inputs.

Gradient clipping is adopted by scaling gradients when the norm exceeded a threshold of 5.

Our implementation on a single GPU Tesla K40m, 1 Kepler GK110B, 2880 Cuda cores. processes a speed of approximately 600-1,200 tokens per second. We trained our models for a total of 7 iterations.

3 Evaluations

We need to measure the closeness of the output (candidate) to the input (reference). We first adopt two standard evaluation metrics, ROUGE [Lin (2004, Lin and Hovy (2003] and BLEU [Papineni et al. (2002].

is a recall-oriented measure widely used in the summarization literature. It measures the n-gram recall between the candidate text and the reference text(s). In this work, we only have one reference document (the input document) and ROUGE score is therefore given by:

where $\text{count}_{\text{match}}$ denotes the number of n-grams co-occurring in the input and output. We report ROUGE-1, 2 and W (based on weighted longest common subsequence).

BLEU

Purely measuring recall will inappropriately reward long outputs. BLEU is designed to address such an issue by emphasizing precision. n-gram precision scores for our situation are given by:

BLEU then combines the average logarithm of precision scores with exceeded length penalization. For details, see ?).

Coherence Evaluation

Neither BLEU nor ROUGE attempts to evaluate true coherence. There is no generally accepted and readily available coherence evaluation metric. ?) and ?) proposed metrics based on discourse relations, but these are hard to apply widely since identifying discourse relations is a difficult problem. Indeed sophisticated coherence evaluation metrics are seldom adopted in real-world applications, and summarization researchers tend to use simple approximations like number of overlapped tokens or topic distribution similarity (e.g., [Yan et al. (2011b, Yan et al. (2011a, Celikyilmaz and Hakkani-Tür (2011]). Because of the difficulty of developing a universal coherence evaluation metric, we proposed here only a tailored metric specific to our case. Based on the assumption that human-generated texts (i.e., input documents in our tasks) are coherent [Barzilay and Lapata (2008], we compare generated outputs with input documents in terms of how much original text order is preserved.

We develop a grid evaluation metric similar to the entity transition algorithms in [Barzilay and Lee (2004, Lapata and Barzilay (2005]. The key idea of Barzilay and Lapata’s models is to first identify grammatical roles (i.e., object and subject) that entities play and then model the transition probability over entities and roles across sentences. We represent each sentence as a feature-vector consisting of verbs and nouns in the sentence. Next we align sentences from output documents to input sentences based on sentence-to-sentence F1 scores (precision and recall are computed similarly to ROUGE and BLEU but at sentence level) using feature vectors. Note that multiple output sentences can be matched to one input sentence. Assume that sentence $s_{\text{output}}^{i}$ is aligned with sentence $s_{\text{input}}^{i^{\prime}}$, where $i$ and $i^{\prime}$ denote position index for a output sentence and its aligned input. The penalization score $L$ is then given by:

Equ. 18 can be interpreted as follows: $(j-i)$ denotes the distance in terms of position index between two outputted sentences indexed by $j$ and $i$, and $(j^{\prime}-i^{\prime})$ denotes the distance between their mirrors in inputs. As we wish to penalize the degree of permutation in terms of text order, we penalize the absolute difference between the two computed distances. This metric is also relevant to the overall performance of prediction and recall: an irrelevant output will be aligned to a random input, thus being heavily penalized. The deficiency of the proposed metric is that it concerns itself only with a semantic perspective on coherence, barely considering syntactical issues.

4 Results

A summary of our experimental results is given in Table 3. We observe better performances for the hotel-review dataset than the open domain Wikipedia dataset, for the intuitive reason that documents and sentences are written in a more fixed format and easy to predict for hotel reviews.

The hierarchical model that considers sentence-level structure outperforms standard sequence-to-sequence models. Attention models at the sentence level introduce performance boost over vanilla hierarchical models.

With respect to the coherence evaluation, the original sentence order is mostly preserved: the hierarchical model with attention achieves $L=1.57$ on the hotel-review dataset, equivalent to the fact that the relative position of two input sentences are permuted by an average degree of 1.57. Even for the Wikipedia dataset where more poor-quality sentences are observed, the original text order can still be adequately maintained with $L=2.04$.

Discussion and Future Work

In this paper, we extended recent sequence-to-sequence LSTM models to the task of multi-sentence generation. We trained an autoencoder to see how well LSTM models can reconstruct input documents of many sentences. We find that the proposed hierarchical LSTM models can partially preserve the semantic and syntactic integrity of multi-text units and generate meaningful and grammatical sentences in coherent order. Our model performs better than standard sequence-to-sequence models which do not consider the intrinsic hierarchical discourse structure of texts.

While our work on auto-encoding for larger texts is only a preliminary effort toward allowing neural models to deal with discourse, it nonetheless suggests that neural models are capable of encoding complex clues about how coherent texts are connected .

The performance on this autoencoder task could certainly also benefit from more sophisticated neural models. For example one extension might align the sentence currently being generated with the original input sentence (similar to sequence-to-sequence translation in ), and later transform the original task to sentence-to-sentence generation. However our long-term goal here is not on perfecting this basic multi-text generation scenario of reconstructing input documents, but rather on extending it to more important applications.

That is, the autoencoder described in this work, where input sequence $X$ is identical to output $Y$, is only the most basic instance of the family of document (paragraph)-to-document (paragraph) generation tasks. We hope the ideas proposed in this paper can play some role in enabling such more sophisticated generation tasks like summarization, where the inputs are original documents and outputs are summaries or question answering, where inputs are questions and outputs are the actual wording of answers. Sophisticated generation tasks like summarization or dialogue systems could extend this paradigm, and could themselves benefit from task-specific adaptations. In summarization, sentences to generate at each timestep might be pre-pointed to or pre-aligned to specific aspects, topics, or pieces of texts to be summarized. Dialogue systems could incorporate information about the user or the time course of the dialogue. In any case, we look forward to more sophi4d applications of neural models to the important task of natural language generation.

Acknowledgement

The authors want to thank Gabor Angeli, Sam Bowman, Percy Liang and other members of the Stanford NLP group for insightful comments and suggestion. We also thank the three anonymous ACL reviewers for helpful comments. This work is supported by Enlight Foundation Graduate Fellowship, and a gift from Bloomberg L.P, which we gratefully acknowledge.

References