Lexicalized Markov Grammars for Sentence Compression

Proceedings of NAACL HLT 2007, pages 180–187, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Lexicalized Markov Grammars for Sentence Compression∗ Michel Galley and Kathleen R. McKeown Columbia University Department of Computer Science New York, NY 10027, USA {galley,kathy}@cs.columbia.edu Abstract We present a sentence compression system based on synchronous context-free grammars (SCFG), following the successful noisy-channel approach of (Knight and Marcu, 2000). We define a head- driven Markovization formulation of SCFG dele- tion rules, which allows us to lexicalize probabili- ties of constituent deletions. We also use a robust approach for tree-to-tree alignment between arbi- trary document-abstract parallel corpora, which lets us train lexicalized models with much more data than previous approaches relying exclusively on scarcely available document-compression corpora. Finally, we evaluate different Markovized models, and find that our selected best model is one that ex- ploits head-modifier bilexicalization to accurately distinguish adjuncts from complements, and that produces sentences that were judged more gram- matical than those generated by previous work. 1 Introduction Sentence compression addresses the problem of re- moving words or phrases that are not necessary in the generated output of, for instance, summa- rization and question answering systems. Given the need to ensure grammatical sentences, a num- ber of researchers have used syntax-directed ap- proaches that perform transformations on the out- put of syntactic parsers (Jing, 2000; Dorr et al., 2003). Some of them (Knight and Marcu, 2000; Turner and Charniak, 2005) take an empirical ap- proach, relying on formalisms equivalent to proba- bilistic synchronous context-free grammars (SCFG) ∗This material is based on research supported in part by the U.S. National Science Foundation (NSF) under Grant No. IIS-05-34871 and the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR0011-06-C-0023. Any opinions, findings and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF or DARPA. (Lewis and Stearns, 1968; Aho and Ullman, 1969) to extract compression rules from aligned Penn Tree- bank (PTB) trees. While their approach proved suc- cessful, their reliance on standard maximum like- lihood estimators for SCFG productions results in considerable sparseness issues, especially given the relative flat structure of PTB trees; in practice, many SCFG productions are seen only once. This problem is exacerbated for the compression task, which has only scarce training material available. In this paper, we present a head-driven Markovization of SCFG compression rules, an approach that was successfully used in syntactic parsing (Collins, 1999; Klein and Manning, 2003) to alleviate issues intrinsic to relative frequency estimation of treebank productions. Markovization for sentence compression provides several benefits, including the ability to condition deletions on a flexible amount of syntactic context, to treat head-modifier dependencies independently, and to lexicalize SCFG productions. Another part of our effort focuses on better align- ment models for extracting SCFG compression rules from parallel data, and to improve upon (Knight and Marcu, 2000), who could only exploit 1.75% of the Ziff-Davis corpus because of stringent assump- tions about human abstractive behavior. To …

Content truncated to 500 words