GENERATING MULTI-SENTENCE ABSTRACTIVE SUM-
Year: 2019

Abstract:
In multi-participant postings, as in online chat conversations, several conversations or topic threads may take place concurrently. This leads to difficulties for readers reviewing the postings in not only following discussions but also in quickly identifying their essence. A two-step process, disentanglement of interleaved posts followed by summarization of each thread, addresses the issue, but disentanglement errors are propagated to the summarization step, degrading the overall performance. To address this, we propose an end-to-end trainable encoderdecoder network for summarizing interleaved posts. The interleaved posts are encoded hierarchically, i.e., word-to-word (words in a post) followed by post-to-post (posts in a channel). The decoder also generates summaries hierarchically, threadto-thread (generate thread representations) followed by word-to-word (i.e., generate summary words). Additionally, we propose a hierarchical attention mechanism for interleaved text. Overall, our end-to-end trainable hierarchical framework enhances performance over a sequence to sequence framework by 8-10% on multiple synthetic interleaved texts datasets.

heading: INTRODUCTION
text: Interleaved texts are becoming more common with new ways of working and new forms of communication, e.g., multi-author entries for activity reports, meeting minutes and social media conversations, such as Slack. Quickly getting a sense of or following the content of different threads in interleaved texts, where posts belonging to different threads occur in one sequence, is often difficult. An example of two threads with multiple posts interleaved to form a sequence is:
Post1-Thread1 → Post1-Thread2 → Post2-Thread1 → Post3-Thread1 → Post2Thread2→ Post3-Thread2
This intermingling leads to difficulties in not only following discussions but also in retrieving their essence. In conversation disentanglement, interleaved posts are grouped by the thread; e.g., the previous example could be rearranged as:
Post1-Thread1→ Post2-Thread1→ Post3-Thread1 Post1-Thread2→ Post2-Thread2→ Post3-Thread2
In analyzing interleaved texts, Shang et al. (2018) went a step further and proposed summarization of the interleaved texts. They designed an unsupervised two-step system and evaluated the system on meeting texts. In the first step, a conversation disentanglement component disentangles the texts thread-wise. Then, in the second step, a multi-sentence compression component compresses the thread-wise posts to single sentence summaries. However, this system has a major disadvantage, in that the disentanglement obtained through either supervised Jiang et al. (2018) or unsupervised Wang & Oard (2009) methods propagate its errors to the downstream summarization task, and thus, degrades the overall performance.
We aim to tackle this issue of error propagation through an end-to-end trainable encoder-decoder system that takes a variable length input, e.g., interleaved texts, processes it and generates a variable length output, e.g., a multi-sentence summary; see Figure 1 for an illustration. An end-to-end system eliminates the disentanglement component, and thus, the error propagation.
The encoder first performs word-to-word encoding to embed each post, followed by post-to-post encoding to embed the overall content of the posts and represent the discourse structure of the interleaved texts. The decoder has a thread-to-thread decoder to generate a representation for each thread, and the thread representation is given to a word-to-word decoder to generate a summary sentence. We also propose to use hierarchical attention similar to Nallapati et al. (2016), but instead of computing post-level attention at every word, attentions are only computed when decoding new sentences. Further, the attention networks are trained end-to-end.
Despite the availability of a multitude of real-world interleaved texts, a major challenge to train encoder-decoder models is the lack of labels (summaries). As labeling is difficult and expensive Barker et al. (2016); Aker et al. (2016); Verberne et al. (2018), we synthesize two separate corpora. Each is derived by mixing texts and associated summaries from a corpus of documents, where the mixed text has a structure reflective of a multi-party conversation with inter-leaved threads and the summary highlights the information in the threads. We find abstracts and titles of randomized controlled trial (RCT) articles, a PubMed corpus, and also for Stack Exchange posts and titles.
To summarize, our contributions are threefold:
• We propose to combine a hierarchical encoder and decoder to obtain multi-sentence summaries of interleaved texts.
• We propose a novel hierarchical attention mechanism that is integrated with the hierarchical encoder-decoder architecture and which equips the decoder to disentangle the interleaving further.
• We use two synthetic datasets to verify the ideas and show our end-to-end trainable architecture addresses not only the issue of error-propagation observed in competitive methods but also improves the performance.

heading: RELATED WORK
text: Quite often multi-party conversations, e.g. news comments, social media conversation and activity report, have tens of posts discussing several different matters pertaining to a subject. Ma et al. (2012); Aker et al. (2016); Shang et al. (2018) designed methodologies to summarize posts in order to provide an overview on the discussed matters. They broadly follow the same approach: cluster the posts and then extract a summary from each cluster.
There are two kinds of summarization: abstractive and extractive. In abstractive summarization, the model utilizes a corpus level vocabulary and generates novel sentences as the summary, while extractive models extract or rearrange the source words as the summary. Abstractive models based on neural sequence-to-sequence (seq2seq) (Rush et al. (2015)) proved to generate summaries with higher ROUGE scores than the feature-based abstractive models. Integration of attention into seq2seq
(Bahdanau et al. (2014)) led to further advancement of abstractive summarization (Nallapati et al. (2016); Chopra et al. (2016)).
There are many possible patterns of organization of the information in texts, e.g., chronological pattern. News articles have an inverted pyramid pattern, i.e., core information in the lead sentences and the extra information in later sentences. A seq2seq model is appropriate for summarization of a news article as it encodes and decodes sequentially. However, in interleaved texts, related information maybe separated; thus a seq2seq model may be competent but not sufficient.
Li et al. (2015) proposed an encoder-decoder (auto-encoder) model that utilizes a hierarchy of networks: word-to-word followed by sentence-to-sentence. Their model is better at capturing the underlying structure than a vanilla sequential encoder-decoder model (seq2seq). Krause et al. (2017); Jing et al. (2018) showed multi-sentence captioning of an image through hierarchical Recurrent Neural Network (RNN), topic-to-topic followed by word-to-word, is better than seq2seq.
These works suggest a hierarchical encoder, with word-to-word encoding followed by post-to-post, will better recognize the dispersed information in interleaved texts. Similarly, a hierarchical decoder, thread-to-thread followed by word-to-word, will intrinsically disentangle the posts, and therefore, generate more appropriate summaries.
Nallapati et al. (2016) devised a hierarchical attention mechanism for a seq2seq model, where two levels of attention distributions over the source, i.e., sentence and word, are computed at every step of the word decoding. Based on the sentence attentions, the word attentions are rescaled. Hsu et al. (2018) slightly simplified this mechanism and computed the sentence attention only at the first step. Our hierarchical attention is more intuitive and computes new sentence attentions for every new summary sentence, and unlike Hsu et al. (2018), is trained end-to-end .
MODEL

heading: PROBLEM STATEMENT
text: We aim to design a system that when given a sequence of posts, C = 〈P1, . . . ,P|C |〉, produces a sequence of summaries, T = 〈S1, . . . ,S|T |〉. For simplicity and clarity, unless otherwise noted, we will use lowercase italics for variables, uppercase italics for sequences, lowercase bold for vectors and uppercase bold for matrices.
Figure 2 illustrates the proposed hierarchical encoder-decoder framework. In the framework, first, a low-level, word-to-word encoder converts a sequence of words in a post, Pj , to a sequence of representations, Hj = 〈hw2wj0 , . . . ,hw2wj|Pj |〉. Subsequently, a top-level, post-to-post encoder converts those representations, 〈H0, . . . ,H|C |〉, to a sequence of top-level post representations 〈hp2p1 , . . . ,h p2p |C |〉. These encoded representations are then passed to the decoder, which utilizes a top-level, threadto-thread, decoder to disentangle them into a sequence of thread representations 〈ht2t1 , . . . ,ht2t|T |〉. Finally, a low-level, word-to-word, decoder takes a feed-forward mapped thread representation ht2ti and generates a sequence of summary words 〈wi1, . . . ,wi|Si|〉. The maximum number of posts in a sequence of interleaved texts is denoted by n and threads by m. We limit the number of words in posts and summaries to fixed lengths by either truncating or
padding, and denote them by p and q respectively. The hidden states of the encoder and decoder have dimensionality l.

heading: ENCODER
text: The hierarchical encoder used in Figure 2 is based on Nallapati et al. (2017), where word-toword and post-to-post encoders are bi-directional LSTMs. The word-to-word Bi-LSTM encoder (Ew2w) runs over word embeddings of any post, Pj , and generates a set of hidden representations (〈hEw2wj0 , . . . ,h Ew2w jp 〉); see left middle section in Figure 2. The average pooled value of the word-
to-word representations of post Pj ( 1p ∑p k=0 h Ew2w jk ) are input to the post-to-post Bi-LSTM encoder (Et2t), which then generates a set of representations (〈h Ep2p 0 , . . . ,h Ep2p n 〉) corresponding to those posts. Overall, output word-to-word representations, W, has dimension n× p× 2l and post-to-post representations, P, has dimension n× 2l for a given channel, C .

heading: DECODER
text: Our hierarchical decoder (see Figure 2) is based on Li et al. (2015), where both thread-to-thread and word-to-word decoders are uni-directional LSTMs.
The initial state hDt2t0 of the thread-to-thread LSTM decoder (f Dt2t ) is set with a feedforwardmapped representation of an average pooled post representations (c′ = 1n ∑n k=0 h p2p k ). At each step i of the decoder, a sequence of attention weights, 〈β̂i,0, . . . , β̂i,n×p〉, corresponding to the set of encoded word representations, 〈hw2w0 , . . . ,hw2wn×p〉 are computed utilizing the previous state, h Dt2t i−1 . We will elaborate the attention computation in the next section.
A weighted representation of the words (crossed blue circle) is then computed: ∑n j=1 β̂ijWij , and used as one input to LSTM fDt2t . Additionally, we use the last hidden state hDw2wi−1· of the wordto-word decoder LSTM (Dw2w) of the previously generated summary sentence as the second input to compute the next state of thread-to-thread decoder, i.e., hDt2ti . The motivation is to provide information about the previous sentence.
The current state hDt2ti is passed through a single layer feedforward network and a distribution over STOP=1 and CONTINUE=0 is computed:
pSTOPi = σ(g ( hDt2ti ) ) (1)
where g is a feedforward network. In Figure 3, the process is depicted by a red circle. The threadto-thread decoder keeps decoding until pSTOPi is greater than 0.5.
Additionally, the current state hDt2ti is passed through another single layer feedforward network k followed by tanh activation to compute the thread representation si = tanh(k ( hDt2ti ) ).
Given a thread representation si, the word-to-word decoder generates a summary for the thread. Our word-to-word decoder is based on Bahdanau et al. (2014). It is a unidirectional attentional LSTM (fDw2w ); see the right-hand side of Figure 2. We refer to Bahdanau et al. (2014) for further details.

heading: HIERARCHICAL ATTENTION
text: Our novel dynamic hierarchical attention is based on two popular concepts: attention scores should integrate in top-down manner (Nallapati et al. (2016)) and two distributions over same words must be modeled together (See et al. (2017)), not just in isolation.
Our hierarchical attention works at 3 levels, the post level (corresponding to posts), i.e., γ, and higher level (corresponding to source tokens), i.e., β, are computed while obtaining a thread representation, s. The lower level attention (also corresponding to source tokens), i.e., α, is computed while generating a word, y, of a summary, S .; see yellow rectangles in Figure 4.
At step i of thread decoding, we also compute elements of post-level attention, i.e., γi· as below.
γij = σ(attnβ(hDt2ti−1 ,Pj) j ∈ {1, . . . , n} (2)
At the same step, we also compute elements of high-level attention, i.e, βi· as below.
βik = σ(attnβ(hDt2ti−1 ,ak)) k ∈ {1, . . . , n× p} (3) ak = add(Wjl,Pj) where k := j ∗ l and j ∈ {1, . . . , n}, l ∈ {1, . . . , p} (4)
where ak is computed as in Eq. 4. W in Eq. 4 is a word-to-word encoder representations of dimension n × p × 2l, add aligns a post representation to its constituting word representations and does element-wise addition, and attnβ is a feedforward network that aligns the current thread decoder state hDt2ti−1 with all n ∗ p number of ak vectors. Then, we use γ to rescale high-level attention, β as below.
β̂ik = βik ∗ γij where k := j ∗ l and l ∈ {1, . . . , p} j ∈ {1, . . . , n} (5) At step t of word-to-word decoding of summary thread i, we compute elements of low level attention, i.e., αit· as below.
αitk = exp(eitk)∑n·p k=1 exp(eitk) where eitk = attnα(hDw2wt−1 ,ak) (6)
, and ak is same as in Eq. 4 and attnα is a feedforward network that aligns the current word decoder state hDw2wt−1 with all n ∗ p number of ak vectors.
Finally, we use rescaled high-level word attentions, β̂, for rescaling low level attention, α as below:
α̂itk = β̂k × exp(eitk)∑n·p k=1 β̂k × exp(eitk)
(7)
Table 1 compares our hierarchical attention with previous work on hierarchical attention in the text summarization domain.

heading: TRAINING OBJECTIVE
text: We train our hierarchical encoder-decoder network similarly to an attentive seq2seq model Bahdanau et al. (2014), but with an additional weighted sum of sigmoid cross-entropy loss on stopping distribution; see Eq. 1. Given a summary, Yi = 〈wi0, . . . ,wiq〉, our word-to-word decoder generates a target Ŷ = 〈yi0, . . . , yiq〉, with words from a same vocabulary U . We train our model end-to-end by minimizing the objective given in Eq. 8.
m∑ i=1 q∑ j=1 log pθ (yij |wi·<j ,W) + λ m∑ i=1 ySTOPi log(p STOP i ) (8)

heading: DATASET
text: Obtaining labeled training data for conversation summarization is challenging. The available ones are either extractive (Verberne et al. (2018)) or too small (Barker et al. (2016); Anguera et al. (2012)) to train a neural model. To get around this issue and thoroughly verify the proposed architecture, we synthesized a dataset by utilizing a corpus of conventional texts for which summaries are available. We create two corpora of interleaved texts: one from the abstracts and titles of articles from the PubMed corpusand one from the questions and titles of Stack Exchange questions. A random interleaving of sentences from a few PubMed abstracts or Stack Exchange questions roughly resembles interleaved texts, and correspondingly interleaving of titles resembles its multi-sentence summary.
The algorithm that we devised for creating synthetic interleaved texts is defined in detail in the Appendix. The number of abstracts to include in the interleaved texts is given as a range (from a to b) and the number of sentences per abstract to include is given as a second range (from m to n). We vary the parameters as below and create three different corpora for experiments: Easy (a=2, b=2, m=5 and n=5), Medium (a=2, b=3, m=2 and n=5) and Hard (a=2, b=5, m=2 and n=5). Table 2 shows an example of a data instance in the Hard Interleaved RCT corpus.

heading: EXPERIMENTS
text: we report ROUGE-1, ROUGE-2, and ROUGE-L as the quantitative evaluation of the models. The Pubmed Medium and Hard corpora train, test and validation have approximately 290k, 6k and 1.5k instances, respectively. The Stack-Exchange Medium corpus train has 180k and Hard has 210k instances, while the both corpora have test and validation of approximately 5k and 4k instances, respectively. The remaining hyper-parameters are described in detail in the Appendix.

heading: BASELINES
text: We first trained and tested it on the Easy corpus. We also ran Shang et al. (2018)’s unsupervised two-step system on the test set of the Easy Interleaved Pubmed corpus. Additionally, we also utilized Shang et al. (2018)’s clustering component to first cluster the interleaved texts of the corpus, and then the disentangled corpus is used to train the seq2seq model. We refer to the latter as cluster→seq2seq. The performance comparison of Shang et al. (2018) and the two seq2seq models are shown in Table 3. Clearly, seq2seq performs better than Shang et al. (2018), the reason being a seq2seq model trained on a sufficiently large dataset is better at summarization than the unsupervised sentence com-
Table 3: Rouge F1-Scores for seq2seq models on the Pubmed Easy Corpus.
Model Rouge-1 Rouge-2 Rouge-L Shang et al. (2018) 30.37 10.77 20.04 seq2seq 44.38 19.47 35.20 cluster→seq2seq 42.93 18.76 30.68
Table 4: Recalls on a sampled Pubmed HardCorpus. Int=Interleaved, Dis=Disentangled.
Model type Rouge-1 Rouge-2 Rouge-L seq2seq Int 32.40 11.09 22.97 hier2hier Int 33.51 12.50 24.27 seq2seq Dis 37.01 14.44 26.91 hier2hier Dis 37.68 15.11 28.25
pression (extractive) method. The lower performance of cluster→seq2seq in comparison to seq2seq shows that a disentanglement component is unnecessary in easy scenario.Furthermore, we utilize the ground-truth labels and disentangle the interleaved posts of a sampled (150k) Hard Corpus, and re-run the seq2seq model. The results (see Table 4) show seq2seq (row 3) takes advantage of cluster labels but hier2hier (row 4) does more than it.
SEQ2SEQ VS. HIER2HIER MODELS
We then compare the proposed hierarchical approach against the seq-to-seq approach in summarizing the interleaved texts by experimenting on the Medium and Hard corpora.
Table 5 shows the experimental results on several corpora; clearly, an increase in the complexity of interleaving scantly impacts the performances. Though, in case of Pubmed, seq2seq depreciates by 1-2 points while hier2hier remains nearly same with increase of complexity. In Stack Exchange corpora, as Hard corpora has more training data (+30k) seq2seq improves slightly. However, a noticeable improvement is observed on changing the decoder to hierarchical, i.e., 1.5-3 Rouge points in Pubmed and 2-4.5 points in Stack Exchange depending on the interleaving complexity.
To understand the impact of hierarchy on the hier2hier model, we perform an ablation study and use the Hard Pubmed corpus for the experiments, and Table 6 shows the results. Clearly, adding hierarchical decoding already provides a boost in the performance. Hierarchical encoding also adds some improvements to the performance; however, the enhancement attained in training and inference speed by the hierarchical encoding is much more valuable. We will discuss it in depth later.
Further, we also compiled corpora to mimic real world conversation interleaving, wherein the sequence of summaries for interleaved posts may not follow the sequential occurrence of posts, see 17-18 in Algorithm. 1). An example, a post mention an action in the very beginning of conversation, but does only elaborates it at the end. Therefore, summary corresponding to the action should be at the end. So, we again create Medium and Hard real world mimicking corpora of the Stack Exchange dataset as it is more similar to real world conversations, and perform the same set of experiments. As seen in Table 7, the results show that both the seq2seq and hier2hier models performance are slightly lower as it is tougher task; see Table 5. In addition, the hier2hier model is still consistently better than the seq2seq model.
Importantly, hier2hier converges much earlier than the seq2seq and also reaches a lower training loss (Figure 5 in Appendix). hier2hier takes ≈1.5 days for training on a Tesla V100 GPU, while seq2seq takes ≈4.5 days. Therefore, the hier2hier model not only achieves greater accuracy but also reduces training and inference time.

heading: HIERARCHICAL ATTENTION
text: The contribution of the post-level and high-level attentions in a hierarchical decoder is two-fold: computing the thread representation and rescaling the word-level attentions. To understand the impact of hierarchical attention on the hier2hier model, we perform an ablation study of post-level attentions (γ) and high-level attentions (β), using the Hard corpus for the experiments.
Table 8 shows the performance comparison. Clearly, γ attention improves the performance (0.5-1) of hierarchical decoding but not a lot. The high-level attention, i.e., β is very important as without it the model performances is noticeably reduced (Rouge values decrease from 2-3). Additionally, we also include Li, Luong and Jurafsky, 2015 post-level attention technique in the comparison, as it is the closest hierarchical attention to ours (see Table 1). Though, (Li, Luong and Jurafsky) utilize a softmax obtained β to compute thread representation, and in contrast to us, they do not reuse β for re-scaling α, and thereby, closest to hier2hier(+γ − β). Evidently, re-utilization gives hier2hier(+γ−β) an edge over (Li, Luong and Jurafsky, 2015). Lastly, removing both the γ and β) makes the hier2hier similar to seq2seq, except a few more parameters, i.e., two additional LSTM, and the performance is also very similar.

heading: DISCUSSION
text: Table 9 shows an output of our hierarchical abstractive system, in which interleaved texts are in the top, and ground-truth and generated summaries in the bottom. Table 9 also shows the top two post indexes attended to by the post-level attention (γ) while generating those summaries, and they coincide with relevant posts. Similarly, the top 10 indexes (words) of the high-level attention (β)
is directly visualized in the table through the color coding matching the generation. The system not only manages to disentangle the interleaved texts but also to generate appropriate abstractive summaries. Meanwhile, β provides explainability of the output.
As interleaving in the table includes abstracts from the same category, e.g. Physical Activities, the interleaving is complex and approximates the real-world conversations. Despite that, the end-toend hierarchical system tackles the task to a large extent. The next, future stage in this research is transfer learning of the hierarchical system to more types of conversations. We find models trained for 50k iteration on Pubmed Hard corpora (a=6, b=10, m=2 and n=3) and then fine-tuned on the popular meeting AMI corpus (McCowan et al. (2005)) already reaches competitive results (Rouge1=39.81, Rouge-2=11.35) against SOA system on AMI (Shang et al. (2018) Rouge-1=37.86 and Rouge-2=07.84). Additionally, we aim to modify hier2hier to include some of the recent additions of seq2seq models, e.g., See et al. (2017) pointer mechanism.

heading: CONCLUSION
text: We presented an end-to-end trainable hierarchical encoder-decoder architecture which implicitly disentangles interleaved texts and generates a multi-sentence abstractive summary covering the text threads. Furthermore, the architecture addresses the error propagation issue that occurs in the twostep architectures. Our proposed novel hierarchical attention further boosts both disentanglement and summary generation.

heading: APPENDIX

heading: INTERLEAVE ALGORITHM
text: In Algorithm. 1, INTERLEAVE takes a set of concatenated abstracts and titles, C = 〈A1;T1, . . . ,A|C|;T|C|〉, minimum, a, and maximum, b, number of abstracts to interleave, and minimum, m, and maximum, n, number of sentences in a source, and then returns a set of concatenated interleaved texts and summaries. WINDOW takes a sequence of texts, X, and returns a window iterator of size |X |−wt + 1, where w and t are window size and sliding step respectively. window reuses elements of X, and therefore, enlarges the corpus size. Notations U refers to a uniform sampling, [·] to array indexing, and REVERSE to reversing an array.
Algorithm 1 Interleaving Algorithm 1: procedure INTERLEAVE(C, a, b,m, n) 2: Ĉ, Z← WINDOW(C, w = b, t = 1), Array() 3: while Ĉ 6= ∅ do 4: C′,A′, T′, S← Ĉ.NEXT(), Array(), Array(), {} 5: r ∼ U(a, b) 6: for j = 1 to r do . Selection 7: A, T← Ĉ[j] 8: T′.ADD(T) 9: q ∼ U(m, n) 10: A′.ADD(A[1:q]) 11: S← S ∪ {j×q} 12: Â, T̂← Array(), Array() 13: for 1 to |S| do . Interleaving 14: k← U(S) 15: S← S\k 16: I← REVERSE(A′[k]).POP() 17: Â.ADD(I) 18: J← T′[k] 19: if J 6∈ T̂ then:

heading: 20: T̂.ADD(J)
text: 21: Z.ADD(Â;T̂) 22: return Z

heading: PARAMETERS
text: For the word-to-word encoder, the steps are limited to 20, while the steps in the word-to-word decoder are limited to 14. The steps in the post-to-post encoder and thread-to-thread decoder depend on the corpus type, e.g., Medium has 15 steps in post-to-post and 3 steps in thread-to-thread. In seq2seq experiments, the source is flattened, and therefore, the number of steps in the source is limited to 300. We initialized all weights, including word embeddings, with a random normal distribution with mean 0 and standard deviation 0.1. The embedding vectors are of dimension 80. The vocabulary size is limited to 5000 and 15000 for Pubmed and Stack Exchange corpora respectively. All hidden states of the encoder and decoder in the models are set to dimension 100. We pad short sequences with a special token, 〈PAD〉. We use Adam Kingma & Ba (2014) with an initial learning rate of .0001 and batch size of 64 for training. Texts are lowercased and numbers are replaced by the special symbol %.

heading: DATA POINTS AND RESULTS
text: TRAINING: SEQ2SEQ VS HIER2HIER

Review summaries:
This paper proposes a technique for generating summaries of interleaved texts. Unlike previous work that first perform unsupervised clustering to extract ordered threads, the authors instead propose a hierarchical model that directly process interleaved threads. In particular, the authors propose using a hierarchical encoder that encodes words -> post -> threads as well as a hierarchical decoder that decodes threads -> words. On synthetic interleaved datasets composed from PubMed and StackExchange, the proposed method outperform seq2seq with attention as well as a pipeline system that applies unsupervised clustering followed by seq2seq. The authors present results for well-chosen ablations as well as baselines.