{'fraction_non_alphanumeric': 0.02719723569079864, 'fraction_numerical': 0.012093852755949396, 'mean_word_length': 4.9299405155320555, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Joint Decoding of Tree Transduction Models for Sentence Compression

In this paper, we provide a new method for decoding tree transduction based sentence compression models augmented with language model scores, by jointly decoding two components. In our proposed solution, rich local discriminative features can be easily integrated without increasing computational complexity. Utilizing an unobvious fact that the resulted two components can be independently decoded, we conduct efficient joint decoding based on dual decomposition. Experimental results show that our method outperforms traditional beam search decoding and achieves the state-of-the-art performance.


Introduction
Sentence compression is the task of generating a grammatical and shorter summary for a long sentence while preserving its most important information. One specific instantiation is deletion-based compression, namely generating a compression by dropping words. Various approaches have been proposed to challenge the task of deletion-based compression. Earlier pioneering works (Knight and Marcu, 2000) considered several insightful approaches, including noisy-channel based generative models and discriminative decision tree models. Structured discriminative compression models (McDonald, 2006) are capable of integrating rich features and have been proved effective for this task. Another powerful paradigm for sentence compression should be mentioned here is constraints-based compression,including integer linear programming solutions (Clarke and Lapata, 2008) and first-order Markov logic networks (Huang et al., 2012;Yoshikawa et al., 2012).
A notable class of methods that explicitly deal with syntactic structures are tree transduction models (Cohn and Lapata, 2007;Cohn and Lapata, 2009). In such models a synchronous grammar is extracted from a corpus of parallel syntax trees with leaves aligned. Compressions are generated from the grammar with learned weights. Previous works have noticed that local coherence is usually needed by introducing ngram language model scores, which will make accurate decoding intractable. Traditional approaches conduct beam search to find approximate solutions (Cohn and Lapata, 2009).
In this paper we propose a joint decoding strategy to challenge this decoding task. We address the problem as jointly decoding a simple tree transduction model that only considers rule weights and an ngram compression model. Although either part can be independently solved by dynamic programming, the naive way to integrate two groups of partial scores into a huge dynamic programming chart table is computationally impractical. We provide an effective dual decomposition solution that utilizes the efficient decoding of both parts. By integrating rich structured features that cannot be efficiently involved in normal formulation, results get significantly improved.

Motivation
Under the tree transduction models, the sentence compression task is formulated as learning a mapping from an input source syntax tree to a target tree with reduced number of leaves. This mapping is known as a synchronous grammar. The synchronous grammar discussed through out this paper will be synchronous tree substitution grammar (STSG), as in previous studies.
In such formulations, sentence compression is finding the best derivation from a syntax tree that produces a simpler target tree, under the current definition of grammar and learned parameters. Each derivation is attached with a score. For the sake of efficient decoding, the score often decom-poses with rules involved in the derivation. A typical score definition for a derivation y of source tree x is in such form (Cohn and Lapata, 2008;Cohn and Lapata, 2009): The first term is a weighted sum of features φ r (x) defined on each rule r. It is plausible to introduce local scores from ngram models. The second term in the above score definition is added with such purpose. Cohn and Lapata (2009) explained that exact decoding of Equation 1 is intractable. They proposed a beam search decoding strategy coupled with cube-pruning heuristic (Chiang, 2007), which can further improve decoding efficiency at the cost of largely losing exactness in log probability calculations. For efficiency reasons, rich local ngram features have not been introduced as well.

Components of Joint Decoding
The score in Equation 1 consists of two parts: sum of weighted rule features and local ngram scores retrieved from a language model. There is an implicit fact that either part can be used alone with slight modifications to generate a coarse candidate compression. Therefore, we can build a joint decoding system that consists of these two independently decodable components.
In this section we will refer to these two independent models as the pure tree transduction model and the pure ngram compression model, described in Section 3.1 and Section 3.2 respectively. There is a direct generalization of the ngram model by introducing rich local features, which results in the structured discriminative models (Section 3.3).

Pure Tree Transduction model
By merely considering scores from tree transduction rules, i.e. the first part of Equation 1, we can have our scores factorized with rules. Then finding the best derivation from a STSG grammar can be easily solved by a dynamic programming process described by Cohn and Lapata (2007).
This simplified pure tree transduction model can still produce decent compressions if the rule weights are properly learned during training.

Pure Ngram based Compression
The pure ngram based model will try to find the most locally smooth compression, reflected by having the maximum log probability score of ngrams.
To avoid the trivial solution of deleting all words, we find the target compression with specified length by dynamic programming.
Furthermore, we can integrate features other than log probabilities. This is equivalent to using a structured discriminative model with rich features on ngrams of candidate compressions.

Structured Discriminative Model
The structured discriminative model proposed by McDonald (2006) defines rich features on bigrams of possible compressions. The score is defined as weighted linear combination of those features: where the function L(z k ) maps a token z k in compression z back to the index of the original sentence x. Decoding can still be efficiently done by dynamic programming.
With rich local structural information, the structured discriminative model can play a complementary role to the tree transduction model that focus more on global syntactic structures.

Joint Decoding
From now on the remaining issue is jointly decoding the components. Either part factorizes over local structures: rules for the tree transduction model and ngrams for the language model or structured discriminative model. We may build a large dynamic programming table to utilize this kind of locality. Unfortunately this is computationally impractical. It is mathematically equivalent to perform exact dynamic programming decoding of Equation 1, which would consume asymptotically O(SRL 2(n−1)V ) 1 time for building the chart (Cohn and Lapata, 2009). Cohn and Lapata (2009) proposed a beam search approximation along with cube-pruning heuristics to reduce the time complexity down to O(SRBV ) 2 .
In this work we utilize the efficiency of independent decoding from the two components respectively and then combine their solutions according to certain standards. This naturally results in a dual decomposition  solution.
Dual decomposition has been applied in several natural language processing tasks, including dependency parsing (Koo et al., 2010), machine translation (Chang and Collins, 2011;Rush and Collins, 2011) and information extraction (Reichart and Barzilay, 2012). However, the strength of this inference strategy has seldom been noticed in researches on language generation tasks.
We briefly describe the formulation here.

Description
We denote the pure tree transduction part and the pure ngram part as g(y) and f (z) respectively. Then joint decoding is equivalent to solving: max where y denotes a derivation which yields a final compression {y 1 , ..., y m }. This derivation comes from a pure tree transduction model. z denotes the compression composed of {z 1 , ..., z m } from an ngram compression model. Without loss of generality, we consider y k and z k as indicators that take value 1 if the k's token of original sentence has been preserved in the compression and 0 if it has been deleted. In the constraints of problem 3, y kt or z kt denote indicator variables that take value 1 if y k or z k = t and 0 otherwise. Let L(u, y, z) be the Lagrangian of (3). Then the dual objective naturally factorizes into two parts that can be evaluated independently: With this factorization, Algorithm 1 tries to solve the dual problem min u L(u) by alternatively decoding each component.
This framework is feasible and plausible in that the two subproblems (line 3 and line 4 in Algorithm 1) can be easily solved with slight modifica-Algorithm 1 Dual Decomposition Joint Decoding 1: Initialization: u (0) k = 0, ∀k ∈ {1, ..., n} 2: for i = 1 to M AX IT ER do 3: kt ∀k ∀t then 6: return (y (i) , z (i) ) 7: end if 10: end for tions on the values of the original dynamic programming chart. Joint decoding of a pure tree transduction model and a structured discriminative model is almost the same.
The asymptotic time complexity of Algorithm 1 is O(k(SRV + L 2(n−1) )), where k denotes the number of iterations. This is a significant reduction of O(SRL 2(n−1)V ) by directly solving the original problem and is also comparable to O(SRBV ) of conducting beam search decoding.
We apply a similar heuristic with Rush and Collins (2012) to set the step size δ i = 1 t+1 , where t < i is the number of past iterations that increase the dual value. This setting decreases the step size only when the dual value moves towards the wrong direction. We limit the maximum iteration number to 50 and return the best primal solution y (i) among all previous iterations for cases that do not converge in reasonable time.

Baselines
The pure tree transduction model and the discriminative model naturally become part of our baselines for comparison 3 . Besides comparing our methods against the tree-transduction model with ngram scores by beam search decoding, we also compare them against the available previous work from Galanis and Androutsopoulos (2010). This state-of-the-art work adopts a two-stage method to rerank results generated by a discriminative maximum entropy model.

Data Preparation
We evaluated our methods on two standard corpora 4 , refer to as Written and Spoken respectively. 3 The pure ngram language model should not be considered here as it requires additional length constraints and in general does not produce competitive results at all merely by itself. 4 Available at http://jamesclarke.net/research/resources We split the datasets according to Table 1. All tree transduction models require parallel parse trees with aligned leaves. We parsed all sentences with the Stanford Parser 5 and aligned sentence pairs with minimum edit distance heuristic 6 . Syntactic features of the discriminative model were also taken from these parse trees.
For systems involving ngram scores, we trained a trigram language model on the Reuters Corpus (Volume 1) 7 with modified Kneser-Ney smoothing, using the widely used tool SRILM 8 .

Model Training
The training process of a tree transduction model followed similarly to Cohn and Lapata (2007) using structured SVMs (Tsochantaridis et al., 2005). The structured discriminative models were trained according to McDonald (2006).

Evaluation Metrics
We assessed the compression results by the F1score of grammatical relations (provided by a dependency parser) of generated compressions against the gold-standard compression (Clarke and Lapata, 2006). All systems were controlled to produce similar compression ratios (CR) for fair comparison. We also reported manual evaluation on a sampled subset of 30 sentences from each dataset. Three unpaid volunteers with self-reported fluency in English were asked to rate every candidate. Ratings are in the form of 1-5 scores for each compression.

Results
We report test set performance of the structured discriminative model, the pure tree transduction (T3), Galanis and Androutsopoulos (2010)'s method (G&A2010), tree transduction with language model scores by beam search and the proposed joint decoding solutions. 5 http://nlp.stanford.edu/software/lex-parser.shtml 6 Ties were broken by always aligning a token in compression to its last appearance in the original sentence. This may better preserve the alignments of full constituents. 7 http://trec.nist.gov/data/reuters/reuters.html 8 http://www-speech.sri.com/projects/srilm/ Table 2 shows the compression ratios and Fmeasure of grammatical relations in average for each dataset. Table 3 presents averaged human rating results for each dataset. We carried out pairwise t-test to examine the statistical significance of the differences 9 . In both datasets joint decoding with dual decomposition solution outperforms other systems, especially when structured models involved. We can also find certain improvements of joint modeling with dual decomposition on the original beam search decoding of Equation 1, under very close compression ratios.
Joint decoding of pure tree transduction and discriminative model gives better performance than the joint model of tree transduction and language model. From Table 3 we can see that integrating discriminative model will mostly improve the preservation of important information rather than grammaticality. This is reasonable under the fact that the language model is trained on large scale data and will often preserve local grammatical coherence, while the discriminative model is trained on small but more compression specific corpora.  Table 4 shows some examples of compressed sentences produced by all the systems in comparison. The two groups of outputs are compressions of one sentence from the Written corpora and the Spoken corpora respectively. Ungrammatical compressions can be found very often by several baselines for different reasons, such as the outputs from pure tree transduction and the discriminative model in the first group. The reason behind the under generation of pure tree transduction is that it mainly deals with global syntactic integrity merely in terms of the application of synchronous rules. Introducing language model scores will smooth the candidate compressions and avoid many aggressive decisions of tree transduction. Discriminative models are good at local decisions with poor consideration of grammaticality. We can see that the joint models have collected their predictive power together. Unfortunately we can still observe some redundancy from our outputs in the examples. The size of training corpus is not large enough to provide enough lexicalized information.
On the other hand, the time consumption of the joint model with dual decomposition decoding in our experiments matched the aforementioned asymptotic analysis. The training process based on new decoding method consumes similar time as beam search with cube-pruning heuristic.

Conclusion and Future Work
In this paper we propose a joint decoding scheme for tree transduction based sentence compression. Experimental results suggest that the proposed framework works well. The overall performance gets further improved under our framework by introducing the structured discriminative model.
As several recent efforts have focused on extracting large-scale parallel corpus for sentence compression (Filippova and Altun, 2013), we would like to study how larger corpora can affect tree transduction and our joint decoding so- Original: It was very high for people who took their full-time education beyond the age of 18 , and higher among women than men for all art forms except jazz and art galleries . Discr.: It was high for people took education higher among women . (Galanis and Androutsopoulos, 2010): It was high for people who took their education beyond the age of 18 , and higher among women . Pure T3: It was very high for people who took . T3+LM-BeamSearch: It was very high for people who took their education beyond the age of 18 , and higher among women than men . T3+LM-DualDecomp: It was very high for people who took their education beyond the age of 18 , and higher among women than men . T3+Discr.: It was high for people who took education beyond the age of 18 , and higher among women than men . Gold-Standard: It was very high for people who took full-time education beyond 18 , and higher among women for all except jazz and galleries .
Original: But they are still continuing to search the area to try and see if there were , in fact , any further shooting incidents . Discr.: they are continuing to search the area to try and see if there were , further shooting incidents . (Galanis and Androutsopoulos, 2010): But they are still continuing to search the area to try and see if there were , in fact , any further shooting incidents . Pure T3: they are continuing to search the area to try and see if there were any further shooting incidents . T3+LM-BeamSearch: But they are continuing to search the area to try and see if there were , in fact , any further shooting incidents . T3+LM-DualDecomp: But they are continuing to search the area to try and see if there were any further shooting incidents . T3+Discr.: they are continuing to search the area to try and see if there were further shooting incidents . Gold-Standard: they are continuing to search the area to see if there were any further incidents .
lution. Meanwhile, We would like to explore on how other text-rewriting problems can be formulated as a joint model and be applicable to similar strategies described in this work.