Joint Decoding of Tree Transduction Models for Sentence Compression

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1828–1833, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Joint Decoding of Tree Transduction Models for Sentence Compression Jin-ge Yao Xiaojun Wan Jianguo Xiao Institute of Computer Science and Technology, Peking University, Beijing 100871, China Key Laboratory of Computational Linguistic (Peking University), MOE, China {yaojinge, wanxiaojun, xiaojianguo}@pku.edu.cn Abstract In this paper, we provide a new method for decoding tree transduction based sentence compression models augmented with lan- guage model scores, by jointly decoding two components. In our proposed so- lution, rich local discriminative features can be easily integrated without increasing computational complexity. Utilizing an unobvious fact that the resulted two com- ponents can be independently decoded, we conduct efficient joint decoding based on dual decomposition. Experimental results show that our method outperforms tradi- tional beam search decoding and achieves the state-of-the-art performance. 1 Introduction Sentence compression is the task of generating a grammatical and shorter summary for a long sen- tence while preserving its most important informa- tion. 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 gen- erative models and discriminative decision tree models. Structured discriminative compression models (McDonald, 2006) are capable of inte- grating rich features and have been proved effec- tive for this task. Another powerful paradigm for sentence compression should be mentioned here is constraints-based compression,including inte- ger linear programming solutions (Clarke and La- pata, 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 Lap- ata, 2009). In such models a synchronous gram- mar is extracted from a corpus of parallel syn- tax 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 strat- egy to challenge this decoding task. We ad- dress the problem as jointly decoding a simple tree transduction model that only considers rule weights and an ngram compression model. Al- though 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 im- practical. We provide an effective dual decompo- sition solution that utilizes the efficient decoding of both parts. By integrating rich structured fea- tures that cannot be efficiently involved in normal formulation, results get significantly improved. 2 Motivation Under the tree transduction models, the sentence compression task is formulated as learning a map- ping from an input source syntax tree to a target tree with …

Content truncated to 500 words