NUTS: NETWORK FOR UNSUPERVISED TELEGRAPHIC SUMMARIZATION
Year: 2018

Abstract:
Extractive summarization methods operate by ranking and selecting the sentences which best encapsulate the theme of a given document. They do not fare well in domains like fictional narratives where there is no central theme and core information is not encapsulated by a small set of sentences. For the purpose of reducing the size of the document while conveying the idea expressed by each sentence, we need more sentence specific methods. Telegraphic summarization, which selects short segments across several sentences, is better suited for such domains. Telegraphic summarization captures the plot better by retaining shorter versions of each sentence while not really concerning itself with grammatically linking these segments. In this paper, we propose an unsupervised deep learning network (NUTS) to generate telegraphic summaries. We use multiple encoderdecoder networks and learn to drop portions of the text that are inferable from the chosen segments. The model is agnostic to both sentence length and style. We demonstrate that the summaries produced by our model show significant quantitative and qualitative improvement over those produced by existing methods and baselines.

heading: 1 INTRODUCTION
text: Humans tend to relay information to others in a concise manner. Typically, we do not pass on information that we received in exactly the same format. More often than not, we tend to abridge and simplify it for the receiver. This captures the essence of summarization. Formally speaking, summarization refers to capturing all the information in a source, without compromising on understanding. There is a pressing need for summarization techniques to deal with the vast amount of textual data available nowadays.
In certain genres, like fictional narratives, each sentence might have an important role to play. This makes the domain of fictional narratives unsuitable for standard extractive summarization methods. Typically, extractive summarization works well if the source text revolves around a central theme with the same information reiterated across multiple sentences. For such text, picking a small number of relevant sentences is enough to summarize the text. Therefore, this method of extractive summarization is widely used for newswire articles (Lee et al., 2005), encyclopedic and scientific texts (Teufel & Moens, 2002) etc.
However, fictional stories and plays, for instance, do not always focus on a single theme. They describe a sequence of events and often contain dialogue. Information is not repeated and each sentence may contribute to developing the plot further. This problem is tackled in an alternate variation of extractive summarization known as telegraphic summarization. In this summarization technique, each sentence is considered an independent text source with each word acting as a segment. The telegraphic summaries for an input, read like a telegram, hence the name. For example, for an input sentence:“An earthquake in Tokyo left 12 people dead” the telegraphic summarization would be: “earthquake Tokyo 12 dead”. Recently, the advantages of telegraphic summarization over typical extractive techniques have been explored in Malireddy et al. (2018). The independent telegraphic summaries computed for each sentence in a document can be combined to form the summary of the whole document.
Current algorithms for telegraphic summarization rely on handcrafted rules (Grefenstette, 1998) or statistics based on syntax to infer important words in a sentence (Jing, 2000; Riezler et al., 2003;
Knight & Marcu, 2000). These methods, however, do not generalize for all cases. Additionally, the work by Lin (2003) suggests that pure syntax based methods cannot be used for general purpose summarization.
We overcome these limitations by exploring learning based approaches for telegraphic summarization. We propose an unsupervised deep network which implicitly learns to retain significant words in a sentence. We try to reconstruct the source text (which is the input to our network), from an abridged version of it generated at an intermediate stage. This abridged version can be used as the telegraphic summary of the source. Since the proposed architecture follows an unsupervised approach, we do not need any labeled text-summary pairs for our method. Another advantage of our algorithm is that it is agnostic to variations in genre, sentence length, vocabulary, language etc.

heading: 2 RELATED WORK
text: Early work on text summarization started around the mid 20th century. In one of the earliest work by Luhn (1958), summarization was used to generate abstracts automatically from the excerpts of technical papers and magazine articles. Since then, various algorithms for text summarization have been proposed for multiple domains like newspaper articles (Wu & Hu, 2018), scientific articles (Teufel & Moens, 2002) and blogs (Hu et al., 2007).
A comparative study in Ceylan et al. (2010) revealed that a single text summarization algorithm does not perform equally well for all domains. This is because of differences in the nature and style of the sources. Therefore it was concluded that separate algorithms need to be designed for different domains of text sources.
Traditionally, most text summarization algorithms have focused on summarizing newspaper and scientific articles (Luhn, 1958; Teufel & Moens, 2002; Lee et al., 2005). Although, there have been recent attempts to summarize fictional stories (Kazantseva & Szpakowicz, 2010; Lloret & Palomar, 2009; Mihalcea & Ceylan, 2007), the objective of these algorithms is to let the reader decide if the text is interesting enough to read. Therefore, these algorithms do not intend to encapsulate the entire information of the source text.
An early general purpose text summarization algorithm for telegraphic purposes was proposed in Grefenstette (1998). This was a rule-based algorithm, with each rule allowing some specific components of the source sentence in the summary. The first (and the most drastic) generated a stream of all the proper nouns in the text. The second generated all nouns present in the subject or object position. The third, in addition, included the head verbs. The least drastic reduction generated all subjects, head verbs, objects, subclauses, prepositions and dependent noun heads. Since this algorithm is based on definitive guidelines, it does not generalize well for shorter sentences. Additionally, it is not clear which rule should be applied to a sentence to generate its appropriate summary.
There have also been numerous approaches using statistics based on syntax to generate telegraphic summaries (Jing, 2000; Riezler et al., 2003; Knight & Marcu, 2000). Typically, these approaches drop words from the source which are not related to the neighboring words, whilst trying to maintain the grammaticality of the summary. The grammatical correctness of the summary is checked using statistical models. These approaches do not tend to give accurate results for shorter inputs as the constraints for the removal of words are difficult to satisfy.
Recently, deep learning based methods have been enormously successful in the domain of feature learning with little or no manual intervention. These approaches have been applied to core Linguistics problems such as machine translation (Bahdanau et al., 2014), language modeling (Mikolov et al., 2010) and image captioning (Johnson et al., 2016). Although these approaches achieve better results than handcrafted algorithms, they are supervised approaches which require a huge amount of data. Attempts have been made to counter this by exploring unsupervised learning-based algorithms, eliminating the need for labeled ground truth data.
In this work, we have proposed a new architecture for telegraphic summarization, known as NUTS. The proposed architecture implicitly learns to retain the significant segments of the source through several encoder-decoder networks (Sutskever et al., 2014) to generate its telegraphic summary.

heading: 3 NUTS MODEL DETAILS
text: In this section, we explain the details of the proposed model. We first describe the building blocks of the architecture. Thereafter, we introduce the various components of the loss function and explain each loss term and its usage.

heading: 3.1 ARCHITECTURE DETAILS
text: Given an input sentence s = w1, w2 ..., wk containing k words, the network tries to reconstruct the same sentence s, with fewer number of words. The network architecture is such that it drops the words it deems inferable for the final reconstruction. The network generates an indicator vector I = I1, I2 ..., Ii, ..., Ik at an intermediate stage. The value of this indicator vector corresponds to the presence of word wi in the summary subset T of the sentence set S. The words present in T are used as the telegraphic summary of the sentence in order of their occurrence in s. Formally, the network tries to find an I∗ such that the probability p(s|s I) is maximized and∑k t=1 It is minimized, jointly. The probability p(s|s I) can be decomposed further as shown in Equation 1
I∗ = argmax I k∏ t=1 p(wt|(w1 × I1), (w2 × I2), ..., (wk−1 × Ik−1)) (1)
The entire architecture is built using RNN with LSTM cells proposed in Hochreiter & Schmidhuber (1997). The equations for LSTM gates are mentioned in Equation A.1 in the Appendix section.
The proposed architecture has the following major components (illustrated in Fig. 1):
1. Sentence encoder (Es) encodes the input sentence s. Every word wi in the sentence is converted into a d-dimensional vector ei. The sequence of these embedded vectors is fed as input to the encoder at each time step. The final hidden state of Es(he1) acts as a sentence embedding for s.
2. Indicator decoder (DI ) is initialized by the final hidden state of Es. The output of this decoder at each time step is passed through a network of two fully connected layers to generate a single output value. We intend this output value to be close to either zero or one, denoting the value of indicator vector I.
3. Summary encoder (E s ′) encodes the masked sentence s′ = s I, where represents
element-wise multiplication. Therefore, the words corresponding to Ii≈ 0 are effectively skipped. The final hidden state of E
s ′ acts as a sentence embedding for s′.
4. Summary decoder (D s ′) is initialized by the final hidden state of E s ′(he2). This decoder
aims to regenerate the input sentence s from s′. This motivates DI to generate I in such a way that s can be easily reconstructed from s′.
The output at each time step from the LSTM cell in D s ′ are fed to a dense layer, Ws. This dense layer computes the distribution over the vocabulary words from the decoders’ hidden states.

heading: 3.2 LOSS FUNCTION
text: In order to understand the function of each of the modules of the architecture, we outline the need for each module’s loss term and their effects on the output of the network.
1. Summary length loss (L1): ensures that the ratio between the lengths of s′ and s is close to a specific value r. This loss is calculated from the output of DI . We have observed that extreme values of r fail to generate the desired output. In our experiments, low values of r hindered the ability of the summary decoder D
s ′ to reconstruct s from s′. On the other
hand, if r is very large, no words are dropped and s′ and s become equal. Therefore, the value of r is set such that the summary is neither too short nor too long. Mathematically, L1 can be represented as shown in Equation 2. We calculate the value of Len(s′) in this equation as the sum of elements of I. The optimum value of r for our experiments was found to be 0.65.
L1 = (Len(s′) Len(s) − r )2
(2)
2. Summary Decoder Reconstruction loss (L2) ensures that the words retained in s′ are sufficient for reconstructing s. The L2 loss is calculated from the output of Ds′. It aims to maximize the probability of occurrence of wi(the ith word in s), given the final hidden state of E
s ′ (he2) and all previous words in the masked sequence(w′<i), encapsulated by
the hidden state vector from the previous time step. The mathematical representation of L2 is shown in Equation 3.
L2 = − Len(s)∑ i=1 logP (wi|w′<i, he2) (3)
3. Binarization loss (L3) is calculated from the output of DI . Ideally, we want all values in I to be either zero or one. However, if the target indicator is set to these hard values, non-differentiability is introduced into the network. Therefore, we relax the requirement of hard values and fix the range of DI output as [0, 1] using the sigmoid activation function. Additionally, we model L3 such that the outputs tend to be distant from the mid-value of 0.5. This pushes the outputs close to zero or one, effectively fulfilling the objective of I. Mathematically, this is achieved using Equation 4. A larger value of b results in a higher penalty for mid-ranged values of Ii. The value of a is such that L3 is always non-negative. In our experiments, the best value of b was found to be 5.
L3 =
∑Len(s) i=1 (a− b(Ii − 0.5)2)
Len(s) (4)
4. Linkage loss (L4) In our experiments we noticed that without an additional loss to govern how the words are masked, the network tends to learn repetitive masking patterns. Such skewed patterns are undesirable - while certain positions of s are well represented in s′, other positions are entirely missing. A few examples of such summaries are shown in Fig. A.1 of Appendix 1. This motivates the need to couple ease of decoding with words dropped from the summary. We introduce a novel ‘linkage’ loss function to achieve this. The linkage loss facilitates the network to drop words which are deemed inferable. It is applied to the outputs of DI and Ds′ simultaneously. Therefore, it correlates the indicator vector and its effect on reconstruction. It penalizes the network if a) it decides to mask a word but is unable to reconstruct it later or b) it decides to include a word which it could decode easily. The mathematical equation describing the linkage loss is shown in Equation 5. The variable χi denotes the relative ease of decoding word wi, given w′<i and he2. The value of χi lies between 0 and 1 (both included). A larger value χi indicates that wi is difficult to decode. The value of χi is calculated using Equation 6. The addition of linkage loss also results in significantly better results significantly as seen in Section 5.
L4 = Len(s)∑ i=1 ( Iie(1−χi) + (1− Ii)eχi − 1 ) (5)
χi = |logP (wi|w′<i, he2)|
max1≤i≤Len(s)|logP (wi|w<i, he2)| (6)
It can be seen from Equation 5 that L5 is minimized when either a) χi = 0 and Ii = 0 simultaneously (signifying that wi is easy to decode and should be dropped) or b) χi = 1 and Ii = 1 simultaneously (indicating that hard-to-decode words should be retained).
The cumulative loss function (L) is a linear combination of the losses described above. Mathematically, the equation for L is represented in Equation 7.
L = λ1L1 + λ2L2 + λ3L3 + λ4L4 (7)
The weights λ1, λ2, λ3, and λ4 have been set to 3, 2, 50 and 3 respectively for our experiments. Since this is an unsupervised approach currently the weights are experimentally determined and can be fine-tuned on supervision.

heading: 3.3 WEIGHTED LINKAGE
text: We observed that some words are an integral part of the sentence and should never be dropped. Their absence from the summary can entirely change the meaning of the summary/make the summary meaningless (e.g. the word not in source sentence ‘He is not my friend’). However, the Summary Decoder D
s ′ could infer some of these words despite their absence from the masked sentence. We
found that mostly subject and negation words fall into this category.
Therefore, to make the summary more aligned with the meaning of the source text, we provide an additional ‘retention’ weight (ωi) for each word along with sentence s in the input. We use these weights to highlight the importance of retaining these words. This is achieved by modifying the variable χi in the linkage loss described in Equation 5. The modified variable (χ′i) can be obtained using the relation shown in Equation 8. The need for weighted linkage loss is demonstrated with an example in Fig. A.2 of Appendix 1. Although the quantitative scores are not affected significantly, we achieve better qualitative results in terms of retention of meaning due to addition of weighted linkage.
χ′i = ωi × |logP (wi|w′<i, he2)|
max1≤i≤len(s)(ωi × |logP (wi|w<i, he2)|) (8)
It should be noted that the weight input is only required at training time and no additional input other than the sentence is required once the model has been trained.
A detailed flow of the network with an example input is provided in Fig. 2.

heading: 4 EXPERIMENTS
text: We have used the BookCorpus dataset introduced in Zhu et al. (2015) for training the model. This dataset contains 11038 books in 16 different genres (e.g. romance, comedy, science fiction, teen
etc.). The total number of sentences and distinct words in the dataset are 74,004,228 and 1,316,420 respectively. The dataset is widely varied in terms of narratives, emotions and text style.
We created a dataset of 500 sentences for test purposes. These sentences were collected from fictions of several genres. This dataset is similar to the BookCorpus dataset used for training. The sentence length is varied between 5 and 30, with an equal number of examples for each length. The sentences are annotated using the guidelines stated below:
1. A word is the smallest unit in the sentence. It should not be broken further. (“waiting” 6→ “wait”).
2. The order of occurrence of words should be preserved in the summary. 3. The summary should be minimal without changing the meaning of the source. 4. The first occurrence of subject words should be included. Thereafter, subject words and
corresponding pronouns should only be included if necessary.
Five different users (all fluent in English) summarized 100 different sentences each. We verified the consistency of the reference summaries using the inter-annotator agreement Kappa score. All users were asked to cross-annotate additional 20 sentences for this purpose. The users had an agreement Kappa score of 0.82, thus ensuring the gold standard of the summaries. The average relative length of the summaries, created using these guidelines, with respect to the source sentence was 0.702. Some examples of the summaries generated using these guidelines are shown in Table A.1 in Appendix 1.

heading: 4.1 DETAILS OF TRAINING
text: We train the model on the entire BookCorpus dataset. All sentences were divided into buckets based on the number of words. We considered only those buckets where the length was between 5 and 30 words in our experiments. All other sentences were discarded. This was done to ensure that the input was neither too short nor too long. We consider an equal number of sentences from each of the 26 buckets, to make the network agnostic to sentence length. The number of sentences in the smallest bucket was 375,000. Thus, a total of 9,750,000 sentences were considered from the original dataset. 10% of these sentences were used as the validation set and the rest for training. The sentences are input to the network in mini-batches of size 128.
We restricted our vocabulary to 20000 most frequent words from the dataset (Kiros et al., 2015). Each word was embedded as a 300-dimensional vector. All the encoders and decoders are modeled using RNNs with LSTM cells of size 600. The weights of all the RNNs were initialized normally N (µ = 0, σ = 0.1).
The output from DI is passed through two fully-connected layers to form I. The hidden layer has 150 units with ReLU activation and the output layer has a sigmoid activation. The output of D
s ′
at each time-step is multiplied by a matrix Ws, thereby projecting its output from 600-dimensional space to 20000-dimensional vocabulary-space. Softmax activation is then applied over the output of the dense layer to compute probability distribution over the vocabulary. We used Adam (Kingma & Ba, 2014) as the optimization algorithm, with the initial learning rate set to 0.001, β1=0.9 and β2=0.999. Gradients were clipped when they became larger than 1.0.

heading: 5 RESULTS
text: We compare the NUTS model with the two baseline methods (explained below), and a rule-based algorithm proposed by Grefenstette (1998), due to the absence of any recent algorithm to generate telegraphic summaries. The Grefenstette algorithm provides eight levels of summaries. Each level allows for varying amount of information to be retained at the cost of summary length. In our experiments, we consider the summary generated at the last level (most informative) as the output.

heading: 5.1 BASELINE
text: We use the stop words’ list as a baseline indicator of the words which do not contribute to the summary of a sentence. Therefore, for any given input sentence, the telegraphic summary is formed
by removing all the stop words present in the input. The experiments are conducted using the top 1% (200) of the total number of words in the vocabulary. The summary generated after removing the stop words from this list is referred to as B1. We also use an alternate baseline motivated from the TextRank algorithm (Mihalcea & Tarau, 2004). A graph is constructed with the input words as nodes. The weight of the edge between two words, w1 and w2, is equal to the cosine similarity between the corresponding word vectors, e1 and e2. Pre-trained Glove vectors (Pennington et al., 2014) are used to compute e1 and e2. We then run the PageRank algorithm (Page et al., 1998) till convergence and select the top nodes as the summary. Hereafter, this baseline is referred to as B2.

heading: 5.2 QUANTITATIVE EVALUATION
text: Traditionally, the evaluation of summarization algorithms for a document is done using ROUGE as proposed in Lin (2004). ROUGE-N evaluation is based on n-gram co-occurrence between the system and reference summaries. The equation used to calculate ROUGE-N scores can be seen in Equation 9, where N stands for the length of the n-gram, gramn and Countmatch(gramn) is the maximum number of n-grams co-occurring in a candidate summary and a set of reference summaries. In our experiments, each sentence is considered to be an independent document. The reference summaries are generated using the guidelines stated in Section 4.1. All system generated summaries are evaluated against the reference summaries for four values of N(1,2,3,4).
ROUGEN =
∑ s∈Reference summaries ∑ gramn∈S countmatch(gramn)∑
s∈Reference summaries ∑ gramn∈S count(gramn)
(9)
Additionally, we also thought that it would be interesting to compare various algorithms based on their summary lengths. We measured the length of the system generated summaries against the input sentence and the reference summaries for this purpose. These metrics are referred to as summary factor(sf ) and length factor(lf ) respectively. The scores are calculated using the formulae shown in Equation 10 and Equation 11.
sf = Len(summarysystem)
Len(s) (10)
lf = Len(summarysystem)
Len(summaryreference) (11)
The ROUGE-N, sf and lf scores are calculated on the entire test dataset of 500 sentences. The mean scores for each algorithm are presented in Table 1. It can be clearly seen that the proposed architecture outperforms the existing algorithm and the baseline methods by a significant margin. The NUTS architecture increases the average ROUGE-N score by 0.164 from the next best-performing algorithm. Additionally, the average summary length is also close to that of the reference summaries as can be seen by the lf scores. Although the sf scores suggest that the summaries generated using B1 are most concise, the scores are less because the summaries hardly retain any words. This can be verified by observing the other metrics used for comparison. The scores demonstrate that NUTS implicitly balances summary length and content retention, i.e. it learns to retain most words in shorter sentences while shortening the longer sentences simultaneously. There is no other recent algorithm attempting to solve the telegraphic summarization, especially involving learning, to the best of our knowledge. A primary reason for this could be lack of annotated data, which is also the motivation behind the unsupervised approach proposed in this work.

heading: 5.3 QUALITATIVE EVALUATION
text: The ROUGE-N and length factor scores demonstrate the content adequacy and relative sentence length similarity between the system and reference summaries. However, these scores can not comment on the readability of the system generated summaries. The ROUGE-N scores only measure the overlap between the reference and system summary and do not account for the coherence of the summary with the original sentence. Some examples demonstrating these shortcomings of the ROUGE-N scores can be seen in Appendix 1 (Fig. A.3).
We conducted a study to validate the performance of various systems in terms of coherence and meaning between the sentence and its summary. We selected 10 English speaking participants to undertake the study. Each participant was provided with 20 input sentences and four summaries for each sentence. They were asked to choose the summary which best captured the gist of the sentence. Among the 20 sentences, five sentence-summary pairs were present for a sanity check. One of the summaries in each of these five sentences was manually annotated, which the participants were expected to choose. All the choices of the participants who chose a different summary more than once out of these five sentences were discarded from evaluation. As a result, the choices of two participants were not considered. Thus, the remaining 8 participants and their choices for the other 15 questions were examined. Therefore, a total of 120 responses were finally considered for evaluation.
The choices for the remaining sentences corresponded to the four system generated summaries. Out of the 120 responses considered, the participants selected summary generated by the NUTS model 104 times(86.67%). Fig. A.4 in Appendix 1 shows examples of some sentence-summary pairs along with their references. As can be seen, the NUTS model mostly generates summaries close/equal to the reference summaries(sentence 2). We also preserve the meaning of the input sentence (the retention of ‘not’ in the third sentence and ‘own’ in the fourth sentence). It is noteworthy that the nuances are captured despite significant shortening of the input.
The figure also shows some failure cases of the model. The words ‘origami’ and ’thrashers’ may have been masked in sentence 5 and 6 respectively due to the limited vocabulary of the encoder. This may be tackled by expanding the model’s vocabulary as suggested in Kiros et al. (2015).

heading: 6 FUTURE WORK
text: We plan to extend the work proposed in this paper to further reduce the summary length corresponding to a source text. We propose to stack the telegraphic outputs of multiple sentences as a new input to our algorithm and iteratively reduce the summary length across multiple sentences. Alternatively, the addition of context might help to generate concise telegraphic summaries for the entire text.
Another active area of our work is to use sentences selected by existing extractive summarization techniques (Wu & Hu, 2018) as our input. This can enable these algorithms to extract additional sentences in their output. We also plan to develop an algorithm to convert telegraphic inputs into fully grammatical sentences.

heading: 7 CONCLUSION
text: We present a learning-based technique for the task of telegraphic summarization. This is the first attempt to use a deep learning for telegraphic summarization. Furthermore, the proposed network is completely unsupervised and removes the need for labeled summary texts. The network implicitly learns the trade-off between readability and understanding, with respect to the source text. We demonstrate through experiments that our network substantially improves results over the baselines. Additionally, we also conducted qualitative experiments and demonstrate that the proposed network generalizes over length and genre of the source text.

heading: A APPENDIX 1 : ADDITIONAL DETAILS AND EXAMPLES
text: LSTM Details LSTM refers to Long Short-Term Memory, enabling the network to retain memory across timesteps. Additionally, LSTM is designed such that the error gets backpropagated across time-steps efficiently. The equations for various gates and the outputs of a LSTM are presented below.
it = σ(Widt + Uiht−1 + bi)
ft = σ(Wfdt + Ufht−1 + bf )
ot = σ(Wodt + Uoht−1 + bo)
ĉt = tanh(Wcdt + Ucht−1 + bc)
ct = it ĉt + ft ct−1 ht = ot tanh(ct)
(A.1)
where, dt is the value of an input to the cell at time t; ht is the value of the hidden state at time t; Wi, Wf , Wo, Wc are the weight matrices corresponding to dt; Ui, Uf , Uo, Uc are the weight matrices
corresponding to ht−1; bi, bf , bo, bc are the bias values for each gate.The output of each gate at time t is represented as it, ft, ot, and ĉt. The output of the LSTM cell at time t is represented by ct. The operator refers to element-wise multiplication between corresponding operands. Additional Examples In this sub-section, we illustrate the effects of linkage loss and weighted linkage through examples. Additionally, we also show some examples of the sentence-summary pairs from the test dataset we have generated. Finally, we demonstrate the effectiveness of NUTS architecture to retain the meaning of the input sentence and reduce the summary length simultaneously.

Review summaries:
The authors consider the problem of telegraphic sentence compression: they train a system in an unsupervised fashion to predict which words can be dropped from a sentence without drastic loss of information. To that end, they propose a new auto-encoding type architecture which uses the extracted words as latent code, and, most importantly, a linkage loss which relates a word's perplexity given the summary of its left context to its likelihood of being retained. The model itself is sober and well motivated, and the linkage loss is, to the best of my knowledge, original. The authors show that their method outperforms some simple baselines in terms of ROUGE and compression on a small human-annotated test set.