{'fraction_non_alphanumeric': 0.030886726142200595, 'fraction_numerical': 0.006116517977831847, 'mean_word_length': 4.8391870560378845, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Text Summarization as Tree Transduction by Top-Down TreeLSTM

Extractive compression is a challenging natural language processing problem. This work contributes by formulating neural extractive compression as a parse tree transduction problem, rather than a sequence transduction task. Motivated by this, we introduce a deep neural model for learning structure-to-substructure tree transductions by extending the standard Long Short-Term Memory, considering the parent-child relationships in the structural recursion. The proposed model can achieve state of the art performance on sentence compression benchmarks, both in terms of accuracy and compression rate.


I. INTRODUCTION
In the latter years there has been increasing interest in textto-text rewriting methods for many natural language processing applications, such as machine translation [1], question answering [2] and text compression [3]. In this work, we focus on text compression problems, that is often formulated as extractive compression [4], in which only word deletions are allowed. Given an ordered set of words representing a source sentence the aim is to produce the associated compressed text by removing any subset of these words, unchanging the order.
The task is typically addressed in the neural network literature by considering it as a sequence-to-sequence transduction problem. Representing natural language sentences as sequences of words has limitations. For instance, it can separate a word from its relevant context (i.e. other relevant words) which, in non-trivial sentences, can be interleaved by a subsequence of words (e.g. a subordinate sentence) irrelevant to the interpretation of the target word. In this paper, we reformulate extractive compression as a structure-tosubstructure transduction problem by considering a parse tree representation of the sentence (both original and compressed). This representation highlights how words are assembled into linguistic substructures according to grammar rules, explicitly capturing the relevant context in which single words should be interpreted. We show how text compression can effectively be solved by learning a structure-to-substructure transduction problem, by extending the standard Long Short-Term Memory (LSTM) to consider the parent-child relationships of the trees in the structural recursion.
The adaptive processing of tree-structured data is a widely studied machine learning task, starting from the seminal work by [5] which established a general framework for it. Several approaches exists in literature for dealing with tree-structured input samples, while there are considerably less tackling the production of a tree-structured output. Generative models, for instance, have been used to learn a probability distribution on trees exploiting conditional independence relationships induced by the tree structure to simplify inference. According with the direction of tree visit, in literature both top-down [6] and bottom-up [7]- [9] models have been proposed.
Recursive Neural Networks (RecNN) [5] extend the concept of recurrent neural model to handle the processing of treestructured data. These models typically perform a bottomup processing of the tree, unfolding the network over the tree structure in such a way that the hidden recursive state of the current tree node depends from that of its children. In practice, this results in an unfolded network resembling a deep multilayer Perceptron with weight sharing. It is easy to understand how such construction is subject to the classical gradient vanishing/explosion problem [10], which has lead to a widespread use of Long Short-Term Memory (LSTM) units [11] also in the tree-structured domain. The TreeLSTM model in [12] has been the first extension of the LSTM cell to handle tree-structures through a bottom-up approach which basically implements a specific instance of the structured data processing framework proposed in the late nineties by [5]. An alternative approach is that put forward in the Tree Echo State Network (TreeESN) [13] where the recursive neurons are randomly initialized according to some dynamic system stability criterion and their weights are not adjusted by the training procedure. Recently, the Hidden Tree Markov Networks (HTNs) [14] have been proposed as an hybrid approach integrating probabilistic bottom-up models within a neural architecture and learning scheme.
Kernel methods have been widely applied to tree-structured data classification and regression, since they allow a straightforward reuse of kernel-based learning machinery for vectorial data by plugging in an appropriately defined tree kernel. There has been a large body of research dealing with the definition of efficient and discriminative tree kernels, including syntactic kernels [15], which compute tree similarity by counting the number of common substructures (e.g. subtrees, paths, etc), as well as generative kernels exploiting an underlying probability distribution over trees, see [16] for a recent survey on the topic.
The majority of the works in literature deals with problems of tree classification and regression while the problem of learning structured transductions is seldom addressed. In [17], tree transduction has been framed as a problem of learning a conditional generative process between structured samples, providing evidence of how to realize this for isomorph transductions (i.e. where input and output structures have the same skeleton). In this paper, we extend such an approach to deal with a restricted form of non-isomorph transformations, i.e. structure-to-substructure transductions, using a recurrent neural model implementing a top-down visit of the input tree and generating the output tree following the same direction. We show how the proposed approach can be used to effectively deal with the sentence compression problem. Traditionally, extractive compression has been addressed using a sequential representation of the sentences, using both generative/grammar based approaches [18], [19] as well as, more recently, through deep recurrent networks [20]. Nonetheless, there has been a number of works addressing the problem from a treestructured perspective, such as in [4], [21]- [25]. These, however, use a fully grammar-based approach, where rules are language-depended and hand-engineered and where the only trained part concerns the order of application of the rules.
We propose a Top-Down TreeLSTM (TD-TreeLSTM) that is able to learn structure-to-substructure compression from pairs of parse trees. We discuss how the top-down parsing and generation direction allows to capture structural and semantic information in the most effective way for the realization of sentence compression tasks. Contextual information is allowed to flow from the higher, more abstract, levels of the tree reducing ambiguity when deciding if a specific substructure or word needs to be removed from the summary. The TD-TreeLSTM model needs no apriori knowledge concerning the language or grammar, being able to extract the necessary information from the parse tree structure. To the extent of our knowledge, this is also the first use of a top-down recurrent neural model for trees.

II. BACKGROUND A. Tree-Structured Data and Transductions
We focus on the problem of learning tree transductions from pairs of input-output trees (x n , y n ), where the superscript identifies the n-th sample pair in the dataset and it will be omitted when the context is clear. We consider labeled rooted trees where a generic tree is defined by the triplet (U n , E n , X n ) consisting of a set of nodes U n = {1, . . . , U n }, a set of edges E n ⊆ U n ×U n and a set of labels X n . The term u ∈ U n is used to denote a generic tree node, whose direct ancestor, called parent, is denoted as pa(u). A node u can have a variable number of direct descendants (children), such that the l-th child of node u is denoted as ch l (u). The pair (u, v) ∈ E n is used to denote an edge between a generic node and its child and we assume trees to have maximum finite out-degree L (i.e. the maximum number of children of a node). Each node u in the tree is associated with a label x u ∈ X n (y u , for the output tree) which can be of different nature depending on the application, e.g. a vector of continuous-valued features representing word embeddings or a symbol from a discrete and finite alphabet.
A tree transduction defines a mapping from elements of an input domain into element of output domain, where elements from both domains are tree-structured samples. Let I # , O # denote the input and output domains, respectively, then a structural transduction is a function F : I # → O # . The transductions considered in this work are based on the concept of tree isomorphism, defined as follows.
Def. (Tree isomorphism): Let x = (U, E, X ) and x = (U , E , X ), they are isomorphic if exists a bijection f : An equivalent definition can be given using the concept of skeleton.
Following such definition, two trees are isomorphic if they have the same skeleton (labels are irrelevant, only structure matters). A general structure-to-structure transduction can be realized by an encoding-decoding process where F = F out • F enc with: The terms F enc and F out are the encoding and output transductions, respectively, and H # is the structured state space (e.g. the space of the hidden neuron activations of a recursive neural model). Figure 1 shows a tree-to-tree isomorphic transduction in both encoding and output mappings.
x enc(x) y Another type of basic transduction is the one shown in Fig.  2, that is a structure-to-element or supersource transduction. This maps an input tree to a vectorial domain, such as with a tree classification or regression task. In this case the encoding function produces a tree isomorphic to the input one, then a state mapping function S is applied to flatten the encoding structure to a vector which is used by F out to produce the final output.
In this work, we focus on a particular form of transduction that we call structure-to-substructure transduction. We consider the case in which the output tree y is obtained from the input tree x by pruning some of its proper subtrees. Conceptually this is a non-isomorphic transduction but, for the purpose of our text compression application, it can be effectively implemented as an isomorphic transduction where the output tree has the labels of the pruned nodes set to a specific NULL value.

B. Learning Text Summarization
Text summarization applications using an extractive compression approach can be coarsely partitioned depending on the sample representation they use.
Sequential models represent the sentence as a sequence of words. In [19], Integer Linear Programming (ILP) is used to infer globally optimal compression. The text compression problem is modeled by constrained optimization problem using a set of integer variables and associated linear local and global constraints. The performances of this model are sensitive to the definition of the particular language and grammar dependent constraints, which are all hand-crafted. In [18], compression is casted as a sequence labeling problem using Conditional Random Fields (CRF) in which, for each pair of input-output sequence, the observations X are the words in the input and the random variables Y are the words in the output. The CRF feature functions consider aspects such as word tokens, POS tags, positional features and features extracted from syntactic and discourse parse trees. Again, these are hand engineered aspects and changing language or domain could lead to their redefinition. A neural based approach is taken by [20], where a LSTM is used to perform an online/on-the-fly compression of the sequence of input works. In this work, it is shown that adding an extra input layer to reduce sparsity helps to obtain more compression while performing a pre-training of the model as autoencoder increases the accuracy.
Tree-based models exploit a hierarchical representation of the sentences (both in input and in output) in the attempt to make good use of information about words' contextual relationships. These approaches are typically based on Synchronous Context-Free Grammar (SCFG). Some of them perform discriminative subtree deletion, such as in [4], where a noisy-channel model is used to identify the compression y which maximizes P (y)P (x|y) such that P (y) measures the grammatical quality of the compressed sentence and P (x|y) captures the probability that the source sentence x is an expansion of the target compression y. This approach has been extended in [21] using a different lexicalized headdriven Markovianization which yields more robust probability estimates. The authors of [22] have instead shown that SCFGs are not expressive enough to model structurally complicated compressions, showing how to enhance them through sets of general rules. A different line of research, followed by [23]- [25], perform compression as subtree substitution using another generalization of the SCFG, that is the Synchronous Tree Substitution Grammar (STSG). The fundamental limitation of these grammar-based models is the need to hand-define the transformation rules, which are strictly dependent on the specific task, language and syntactic categories of the parser, which is a key problem for the scalability of the approach.
Our proposed model relaxes the need for such expert information, allowing to infer implicit substitution rules from non-aligned parse trees through the TD-TreeLSTM, whose formalization is given in the following section.

III. TOP-DOWN TREE TRANSDUCTION FOR TEXT SUMMARIZATION
We propose a model to realize text compression as structureto-substructure transductions. It receives in input a parse tree (i.e. costituency tree) representation of the input text and returns in output a parse tree representing the compressed sentence (Fig. 3). We show how this transduction process can be learned by a TD-TreeLSTM unfolding on all the root-toleaf paths of the parse trees, whose internal nodes represent syntactic categories, while the leaves are labeled by dictionary words.  Fig. 3. An example of a structure-to-substructure transduction between the input parse tree of the sentence "I like playing football with you." and the substructure representing its compressed version "I like playing football.". The parts of the original tree deleted in the compressed version are marked in red (the corresponding output node labels are set to NULL).

A. Top-Down TreeLSTM (TD-TreeLSTM)
Several works have been focused on extending Recurrent Neural Networks (RNN) to deal with tree structured data. Lately, most of these works focused on tree-structured extensions of LSTM cells and networks. The primary source of differentiation between the different approaches concerns the processing direction. Bottom Up (BU): tree processing flows from leaves to the root. These are recursive models [12] mainly used as onepass encoder of the structure, following the assumption that a node hidden state computed recursively from its children states is a "good" vectorial summary of the information in all the subtree rooted in the node. Top Down (TD): tree processing flows from the root to the leaves. LSTM models belonging to this category are mainly used in generative settings, where one wants to generate the children of a node based on the hidden state of the parent [26] [27]. Their use as encoders of the full structure is not common, as this would require some form of mapping function summarizing the whole tree into a single encoding vector (e.g. the mean of the hidden states of all the nodes in the tree).
Here, we put forward the idea that a TD recurrent model provides an effective means to realize structure-to-substructure transductions. The underlying neural machinery of our proposed model is an LSTM cell, hence we call our approach TD-TreeLSTM. To the extent of our knowledge, this is the first application of a top-down LSTM model in the context of structure-to-substructure transductions. The TD-TreeLSTM unit activation for a generic node u is formally defined by the following equations (see Fig. 4 for the corresponding graphical representation) with the term x u denoting unit input (i.e. a vectorial representation of the node label), h pa(u) and c pa(u) are, respectively, the hidden state and the memory cell state of the node's parent, σ is the sigmoid activation function and is elementwise multiplication. It can be seen that the formal model of this unit is that of a standard LSTM unit for sequences; however, this will be TD unfolded over the tree by following in parallel all the root to leaves paths.
The rationale behind the choice of a TD approach is founded on the specificity of the tree-compression application. In a parse tree the dictionary words occur only as leaf labels; a disambiguation of their interpretation can be performed by considering their context which can only come from their parents, given that they have no children by definition. Hence, it follows that a parent-to-children information flow is more relevant than a children-to-parent one to determine if a word, represented necessarily by a leaf node, has to be included or not in a summary. Let us consider a trivial example: the word "you" could be interpreted either as a subject or complement, depending on the context. It is highly likely that, in the former case, the word needs to be kept during compression. On the contrary, it is highly likely that it will be deleted in the latter interpretation. Clearly, a purely BU model cannot distinguish between the two cases. The example above is rendered graphically in Fig. 5: in the BU case, shown in Fig.  5(a), the state (and the corresponding output) of the leaf node "you" is conditioned only on its input label and its encoding cannot change depending on where the "you" labeled node occur in the structure. Conversely, the TD case depicted in Fig.  5(b) shows how the state of the "you" node is conditioned on the encoding of its parent and recursively from the path that has lead to the node. Therefore the occurrence of word "you" in different parts of the tree can be associated to different encodings of the corresponding leaf depending on the context dictated by the path leading to it.

B. Output Representation
The previous subsection has described how to obtain a state encoding for the tree nodes using a TD context propagation. To realize the transduction, we need to define also an output function generating the predicted label for each node (which includes the special NULL label to denote the absence of a node in the output structure). In the following, we define two alternative approaches tailored to the text summarization application. Note that, for this specific application, we can restrict to generating output labels only for the leaves (which are the only nodes where words can appear).
1) Vectorial Output Layer: node output is word encoded using the same dictionary of the input tree labels. These are typically vector encoded using either a one-hot or a word embedding representation. The input dictionary is augmented with a special NULL vector ( Fig. 6(b)). Formally, the output for a generic node u is computed by with h u and c u being the hidden and memory cell states, respectively. To associate a specific word of the dictionary to the output vector generated by the equation above, we use a simple nearest neighbor approach, where we associate out u with the closest vector in the words dictionary. Given this interpretation of the output function, we can associate it with a Mean Squared Error (MSE) loss to drive the training phase optimization, by minimizing the discrepancy between the ground-truth outputs (i.e. the words in the summary text) and the output computed by the model for each node.  Fig.  3. The arrows denote the direction of the tree processing flow. Note how the top-down approach allows to condition the encoding of the leaf labeled with "you" based on the context given by node "PRP" and, recursively, by its ancestors (e.g. "VP").
2) Binary Output Layer: node output is a binary value. Given a node u, its output will be equal to 1 if the node will be present (together with its label) in the output tree and it will be equal to 0 otherwise (Fig. 6(c)). The corresponding output rule is with h u and c u being the hidden and memory cell states, respectively. The term σ denotes the sigmoid activation function used to produce an output value representing the probability of node presence: the value of out u is confronted to a threshold (fixed to 0.5) to ultimately determine if the node is present or not in the output tree. The training loss associated to this output function is Binary Cross Entropy (BCE).

IV. EXPERIMENTS AND RESULTS
In the following we confront the empirical performance of the proposed TD-TreeLSTM model, on sentence compression Original: I like playing football with you.
Compressed: I like playing football. tasks, with that of two state-of-the-art approaches: a LSTMbased model [20] using a sequential representation of the sentence and a generative model [25] based on a tree-structured representation of the text.

A. Experimental Setup
The experiments are based on the CLWritten and CLSpoken corpora [19], which are widely used for evaluating sentence compression techniques. The former was created by sampling from written sources, while the latter was created by manually transcribed speech of broadcast news stories. Since CLSpoken is created from a speech corpus, it often contains incomplete and ungrammatical utterances and speech artifacts such as disfluencies, false starts and hesitations. The corresponding shortened/compressed form of all sentences were created manually. Here, the annotators were asked to produce the smallest possible target compression by deleting extraneous words from the source, without changing the word order and the meaning of the sentences. In particular, three annotators have been used for the CLSpoken benchmark: we have considered each annotator independently providing then the overall CLSpoken performance as the average on the three annotators.
The corpora provide sentences in sequential form (see [19] for more details). The corresponding tree representation has been obtained using the (constituency) Stanford Parser [28] on the original sentences. We will use the term POStag, from now on, to refer to the categories associated to the internal nodes of the parse trees.
Node labels can be of two kinds depending on the node type: vocabulary words are represented through word embeddings, obtained using the word2vec [29] approach by performing 1000 training epochs with negative sampling method; POStag categories, instead, are represented using a one-hot encoding. The statistics of the label representations for the two corpora are reported in Table I.   TABLE I  INPUT LABEL INFO -VECTOR SIZE IS THE DIMENSION OF THE INPUT  VECTORS, SET SIZE IS THE NUMBER OF DIFFERENT INPUT VALUES FOR  EACH TYPE OF LABEL, VECTOR TYPE IS THE ENCODING USED FOR THE   INPUT  For model selection and validation purposes we have split each corpus in training set, validation and test sets, along the lines of the experimental setups defined for the baseline models in [25] [20]. In particular, the partition of the corpora is performed using a hold-out approach with the same proportion of training/validation/test used in [19], i.e. 903/63/882 for CLWritten and 882/78/410 for CLSpoken.
Performance on the two corpora has been assessed using the metrics used in the case of the two baseline models: accuracy or importance factor: this metric measure how much of the important information is retained. Accuracy is evaluated using Simple String Accuracy (SSA) [30], which is based on the string edit distance between the compressed output generated by the model and the reference ground-truth compression; compression rate: this metric measures how much of the original sentence remains after compression. Compression rate is defined as the length of the compressed sentence divided by the original length, so lower values indicate more compression; F1 score: provides an assessment similar to the accuracy defined above.
Model selection and early stopping decisions are taken by considering an hybrid metric, computed on the validation set, which trades off accuracy and compression according to the following definition t = accuracy 2 compression rate .
Training has been performed by BackPropagation Through Structure (BPTS) [31] in combination with an Adam optimizer [32]. L 2 penalization term has been added to the loss function for the sake of model regularization, using a penalization weight fixed to λ = 10 −4 . Model selection has been performed on the number of LSTM units which, after a preliminary coarse grained search, has been selected from the following set of values: 200, 250, 300, 350, 400. Additionally, we have validated the choice of the type of output layer: when considering the vectorial output representation, we have set the NULL element to be the vector with all entries equal to 1 in order to use the cosine distance as vector-word similarity.

B. Results
Validation performances for the best TD-TreeLSTM configurations are summarized in Table II and III for the binary and vectorial outputs, respectively. Overall the binary output seems more effective in optimizing the trade-off metric t, in particular because of a more effective compression.  Given the validation results, in the following we focus on analyzing the performance of the binary output configuration. Test set assessment has been performed for the best configurations on the validation set: 10 independent runs with different random initialization of the weights have been performed and results averaged. Table IV reports the resulting test set performance: variance is not reported because it is in the order of 10 −5 .
A comparison between our model and state-of-the-art approaches for sequence (LSTM) and tree-based (STSG) compression is reported in Table V: our model outperforms both on accuracy/F1 score and compression rate. In particular, our model halves the difference between compression rate and the reference gold compression whilst the accuracy respect to the LSTM-based model is increased by 4%. F1 score improvements respect to the STSG approach are even more evident (+10% on CLWritten and +30% on CLSpoken). A more detailed view of the precision of the proposed method can be gained by looking at the distribution of the sentences according to accuracy levels. Fig. 7 shows the number of test set sentences for 7 accuracy levels: sentences with an accuracy below 50% are very few (i.e. less than 10 for each corpus), while on average most corpora sentences fall into the 75% accuracy class. The CLSpoken2 corpus has a better behavior with most of the sentences falling into the top-accuracy groups.
To appreciate the quality of the generated compressions, Table VI reports an example of the most accurate compressions (i.e. accuracy>90% excluding the perfect ones to avoid trivial examples). One can see how the common mistakes relate to an excessive deletion of minor elements, e.g. a comma, an article or an adjective.   CLSpoken3 Input: And Chicago could take its fourth championship of the decade with one more win. Output: Chicago could take championship with one more win. Gold: Chicago could take its fourth championship of the decade.
produced output is quite different from the gold compression it is still (mostly) reasonable grammatically and semantically.

V. CONCLUDING REMARKS
We have introduced a deep learning approach to extractive natural language compression by casting it as a restricted form of (parse) tree transduction. In particular, we proposed the first use of a TD-TreeLSTM model for learning structure-tosubstructure transductions by building on application-driven considerations concerning context propagation. We have for-mulated the claim that a TD approach can help disambiguating the interpretation of the most impacting parts of the parse tree, i.e. the leaves encoding the vocabulary words. We have empirically shown that TD processing allows to exploit such enriched contextual information brought to vocabulary words by the parse tree representation of sentences. The experimental results shows that our solution outperforms the state-of-the-art.
The proposed model can be made more effective in terms of compression performance by working on optimizing the representation of the vocabulary words and syntactic categories. On the one hand, we would like to explore alternative word representations from the NLP literature. On the other hand, we would like to surpass such static representations, introducing a fine-tuning refinement of the label representation by exploiting end-to-end differentiability of the model. Ultimately, we would like to enrich the TD model along the lines of [33], introducing an additional dependency of the current node from its preceding sibling, defining a form of Parent-Sibling Top-Down TreeLSTM which can be particularly effective in further disambiguating words at the leaves of the parse tree.

ACKNOWLEDGMENT
This work has been supported by the Italian Ministry of Education, University, and Research (MIUR) under project SIR 2014 LIST-IT (grant n. RBSI14STDE). The authors gladly acknowledge Dell-EMC and Nvidia for donating the Dell C4130 server and the Nvidia M40 GPUs used to perform the experimental analysis.