---
title: "Sentence Compression Beyond Word Deletion — Cohn 2008"
description: "Their model builds on the tree-to-tree transducer of Cohn and Lapata (2007), a discriminatively… 25 references, cited by 81 papers here."
authors: ["Trevor Cohn", "Mirella Lapata"]
year: 2008
venue: "Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)"
source: "https://aclanthology.org/C08-1018/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/cohn-2008-sentence-compression-beyond-word-deletion/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/cohn-2008-sentence-compression-beyond-word-deletion/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2008](https://md.research.elamur.ai/free/en/papers/2008/) / Sentence Compression Beyond Word Deletion

# Sentence Compression Beyond Word Deletion

**Authors:** [Trevor Cohn](https://md.research.elamur.ai/free/en/authors/trevor-cohn/) and [Mirella Lapata](https://md.research.elamur.ai/free/en/authors/mirella-lapata/) · **Year:** 2008 · **Venue:** [Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)](https://md.research.elamur.ai/free/en/venues/coling/) ([COLING 2008](https://md.research.elamur.ai/free/en/venues/coling/2008/)) · **Publisher:** [International Committee on Computational Linguistics (ICCL)](https://md.research.elamur.ai/free/en/publishers/international-committee-on-computational-linguistics-iccl/) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/C08-1018/) · [PDF](https://aclanthology.org/C08-1018.pdf) · [OpenAlex](https://openalex.org/W2083451366)

**Citations:** 169 citations (OpenAlex, 2026-10-14) · [81](https://md.research.elamur.ai/free/en/papers/cohn-2008-sentence-compression-beyond-word-deletion/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
Cohn and Lapata extend sentence compression beyond word deletion. In their abstractive setting, a sentence may also be shortened by substituting, reordering, or inserting words. Existing compression corpora contain only deletions, and paraphrase corpora are not designed around information loss. So the authors built a new corpus: 575 sentences from 30 news articles, compressed by annotators who could rewrite freely. Their model builds on the tree-to-tree transducer of Cohn and Lapata (2007), a discriminatively trained system grounded in the STSG (synchronous tree substitution grammar) formalism. The extensions are:
- a new grammar extraction method that learns paraphrase rules by pivoting through bilingual corpora,
- an n-gram language model feature for fluency,
- loss functions tailored to compression.

In a human evaluation against an extractive baseline, the abstractive system scored significantly higher on preserving important information. It was numerically, but not significantly, better on grammaticality. Both systems fell short of human compressions. The work shows that abstractive compression is a well-defined task and that syntax-based transduction can handle it. This is relevant to summarisation, simplification and other generation tasks.

## Key points
- **Corpus:** 30 newspaper articles (575 sentences) from the BNC and the American News Text corpus. Five documents were compressed by two annotators to check feasibility; the remaining 25 were done by a single annotator for consistency. The corpus is publicly released.
- **Annotator agreement:**
  - Compression rates were similar, at 56% and 54% of words kept.
  - Inter-annotator BLEU was 23.79%, compared with 13.22% between each compression and its source sentence.
- **Model:** a discriminative STSG transducer that maps a source parse tree to a compressed target tree. Each rule's score is a feature–weight inner product, and decoding uses dynamic programming over derivations.
- **Human evaluation:**
  - 22 native-speaker volunteers rated 90 items (30 sentences × system, baseline, gold) for grammaticality and importance.
  - ANOVA followed by Tukey tests showed the abstractive model beat the extractive baseline on importance (α \< 0.01).
- **Rewrite operations:**

  | Operation | System | Humans |
  |---|---|---|
  | Deletions | 67% | 69% |
  | Substitutions | 27% | 24% |
  | Insertions | 6% | 7% |

  Only 63% of system compressions kept the original meaning, against 96.5% for humans.

## Interesting ideas
- **Two-part agreement check for open-ended annotation.** When many outputs are valid, the authors assess annotators on separate axes: how much they compress, and how similar their wordings are via BLEU. The BLEU score is set against a reference point (source vs. compression). This is a cheap way to validate any new generation dataset where exact-match agreement makes no sense.
- **Paraphrase rules from bilingual pivoting.** Rewrite rules are learned by pivoting through parallel corpora, so no monolingual paraphrase data is required. This could suit lower-resource languages such as Ukrainian, where parallel text is easier to find than paraphrase corpora.
- **Error analysis exposes pivoting artefacts.** The system rewrote "her" as "him" because both share the French translation "lui". The authors suggest pivoting through several foreign languages to cancel out such ambiguities. This is a useful lesson for anyone building lexical resources via translation.
- **Counting edit operations and meaning preservation.** Comparing the system's mix of deletions, substitutions and insertions with the human mix, and checking how often meaning survives, shows whether a model rewrites in a human-like way. It also measures the risk that comes with more expressive operations, and it applies to evaluating any rewriting or simplification system.
- **Task-specific losses in discriminative training.** Because the learning framework accepts different loss functions, the training objective can be aligned with what the task actually rewards, such as compression rate or information kept. This is a reusable design choice for structured prediction models.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

## Institutions

- [University of Edinburgh](https://md.research.elamur.ai/free/en/universities/university-of-edinburgh/) — University, Edinburgh, United Kingdom · 255 works · 68,771 citations

📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works

## Cite

Cite as: Trevor Cohn and Mirella Lapata. 2008. Sentence Compression Beyond Word Deletion. Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008).

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{cohn2008sentence,
  title = {{Sentence Compression Beyond Word Deletion}},
  author = {Trevor Cohn and Mirella Lapata},
  booktitle = {Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008)},
  year = {2008},
  doi = {10.3115/1599081.1599099},
  url = {https://doi.org/10.3115/1599081.1599099}
}
```

- [← previous Forest-Based Translation](https://md.research.elamur.ai/free/en/papers/mi-2008-forest-based-translation/)
- [next → Generalizing Word Lattice Translation](https://md.research.elamur.ai/free/en/papers/dyer-2008-generalizing-word-lattice-translation/)
- [↑ back to papers of 2008](https://md.research.elamur.ai/free/en/papers/2008/)

## References

25 references, 9 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. C. Bannard, C. Callison-Burch. 2005. [Paraphrasing with bilingual parallel corpora](https://md.research.elamur.ai/free/en/papers/bannard-2005-paraphrasing-bilingual-parallel-corpora/). In Proceedings of the 43rd ACL, 255–262, Ann Arbor, MI.
2. R. Barzilay. 2003. Information Fusion for Multi-Document Summarization: Praphrasing and Generation. Ph.D. thesis, Columbia University. [find](https://scholar.google.com/scholar?q=R%2E+Barzilay%2E+2003%2E+Information+Fusion+for+Multi%2DDocument+Summarization%3A+Praphrasing+and+Generation%2E+Ph%2ED%2E+thesis%2C+Columbia+University%2E)
3. D. Bikel. 2002. Design of a multi-lingual, parallel-processing statistical parsing engine. In Proceedings of the HLT, 24–27, San Diego, CA. [find](https://scholar.google.com/scholar?q=D%2E+Bikel%2E+2002%2E+Design+of+a+multi%2Dlingual%2C+parallel%2Dprocessing+statistical+parsing+engine%2E+In+Proceedings+of+the+HLT%2C+24%E2%80%9327%2C+San+Diego%2C+CA%2E)
4. J. Carroll, G. Minnen, D. Pearce, Y. Canning, S. Devlin, J. Tait. 1999. [Simplifying text for language impaired readers](https://md.research.elamur.ai/free/en/papers/carroll-1999-simplifying-text-language-impaired-readers/). In Proceedings of the 9th EACL, 269–270, Bergen, Norway.
5. D. Chiang. 2007. [Hierarchical phrase-based translation](https://md.research.elamur.ai/free/en/papers/chiang-2007-hierarchical-phrase-based-translation/). Computational Linguistics, 33(2):201–228.
6. J. Clarke. 2008. Global Inference for Sentence Compression: An Integer Linear Programming Approach. Ph.D. thesis, University of Edinburgh. [find](https://scholar.google.com/scholar?q=J%2E+Clarke%2E+2008%2E+Global+Inference+for+Sentence+Compression%3A+An+Integer+Linear+Programming+Approach%2E+Ph%2ED%2E+thesis%2C+University+of+Edinburgh%2E)
7. T. Cohn, M. Lapata. 2007. Large margin synchronous generation and its application to sentence compression. In Proceedings of the EMNLP/CoNLL, 73–82, Prague, Czech Republic. [find](https://scholar.google.com/scholar?q=T%2E+Cohn%2C+M%2E+Lapata%2E+2007%2E+Large+margin+synchronous+generation+and+its+application+to+sentence+compression%2E+In+Proceedings+of+the+EMNLP%2FCoNLL%2C+73%E2%80%9382%2C+Prague%2C+Czech+Republic%2E)
8. S. Corston-Oliver. 2001. Text Compaction for Display on Very Small Screens. In Proceedings of the NAACL Workshop on Automatic Summarization, 89– 98, Pittsburgh, PA. [find](https://scholar.google.com/scholar?q=S%2E+Corston%2DOliver%2E+2001%2E+Text+Compaction+for+Display+on+Very+Small+Screens%2E+In+Proceedings+of+the+NAACL+Workshop+on+Automatic+Summarization%2C+89%E2%80%93+98%2C+Pittsburgh%2C+PA%2E)
9. H. Daumé III, D. Marcu. 2002. A noisy-channel model for document compression. In Proceedings of the 40th ACL, 449–456, Philadelphia, PA. [find](https://scholar.google.com/scholar?q=H%2E+Daume%CC%81+III%2C+D%2E+Marcu%2E+2002%2E+A+noisy%2Dchannel+model+for+document+compression%2E+In+Proceedings+of+the+40th+ACL%2C+449%E2%80%93456%2C+Philadelphia%2C+PA%2E)
10. J. Eisner. 2003. [Learning non-isomorphic tree mappings for machine translation](https://md.research.elamur.ai/free/en/papers/eisner-2003-learning-non-isomorphic-tree-mappings/). In Proceedings of the ACL Interactive Poster/Demonstration Sessions, 205–208, Sapporo, Japan.
11. M. Galley, K. McKeown. 2007. Lexicalized Markov grammars for sentence compression. In Proceedings of the NAACL/HLT, 180–187, Rochester, NY. [find](https://scholar.google.com/scholar?q=M%2E+Galley%2C+K%2E+McKeown%2E+2007%2E+Lexicalized+Markov+grammars+for+sentence+compression%2E+In+Proceedings+of+the+NAACL%2FHLT%2C+180%E2%80%93187%2C+Rochester%2C+NY%2E)
12. M. Galley, M. Hopkins, K. Knight, D. Marcu. 2004. [What’s in a translation rule?](https://md.research.elamur.ai/free/en/papers/galley-2004-what-s-translation-rule/) In Proceedings of the HLT/NAACL, 273–280, Boston, MA.
13. H. Jing. 2000. [Sentence reduction for automatic text summarization](https://md.research.elamur.ai/free/en/papers/jing-2000-sentence-reduction-automatic-text-summarization/). In Proceedings of the ANLP, 310– 315, Seattle, WA.
14. T. Joachims. 2005. A support vector method for multivariate performance measures. In Proceedings of the 22nd ICML, 377–384, Bonn, Germany. [find](https://scholar.google.com/scholar?q=T%2E+Joachims%2E+2005%2E+A+support+vector+method+for+multivariate+performance+measures%2E+In+Proceedings+of+the+22nd+ICML%2C+377%E2%80%93384%2C+Bonn%2C+Germany%2E)
15. K. Knight, D. Marcu. 2002. Summarization beyond sentence extraction: a probabilistic approach to sentence compression. Artificial Intelligence, 139(1):91–107. [find](https://scholar.google.com/scholar?q=K%2E+Knight%2C+D%2E+Marcu%2E+2002%2E+Summarization+beyond+sentence+extraction%3A+a+probabilistic+approach+to+sentence+compression%2E+Artificial+Intelligence%2C+139%281%29%3A91%E2%80%93107%2E)
16. P. Liang, B. Taskar, D. Klein. 2006. [Alignment by agreement](https://md.research.elamur.ai/free/en/papers/liang-2006-alignment-agreement/). In Proceedings of the HLT/NAACL, 104– 111, New York, NY.
17. C.-Y. Lin. 2003. Improving summarization performance by sentence compression — a pilot study. In Proceedings of the 6th International Workshop on Information Retrieval with Asian Languages, 1–8, Sapporo, Japan. [find](https://scholar.google.com/scholar?q=C%2E%2DY%2E+Lin%2E+2003%2E+Improving+summarization+performance+by+sentence+compression+%E2%80%94+a+pilot+study%2E+In+Proceedings+of+the+6th+International+Workshop+on+Information+Retrieval+with+Asian+Languages%2C+1%E2%80%938%2C+Sappo)
18. R. McDonald. 2006. Discriminative sentence compression with soft syntactic constraints. In Proceedings of the 11th EACL, 297–304, Trento, Italy. [find](https://scholar.google.com/scholar?q=R%2E+McDonald%2E+2006%2E+Discriminative+sentence+compression+with+soft+syntactic+constraints%2E+In+Proceedings+of+the+11th+EACL%2C+297%E2%80%93304%2C+Trento%2C+Italy%2E)
19. K. Papineni, S. Roukos, T. Ward, W.-J. Zhu. 2002. [BLEU: a method for automatic evaluation of machine translation](https://md.research.elamur.ai/free/en/papers/papineni-2002-bleu-method-automatic-evaluation-machine/). In Proceedings of the 40th ACL, 311–318, Philadelphia, PA.
20. C. Quirk, C. Brockett, W. Dolan. 2004. [Monolingual machine translation for paraphrase generation](https://md.research.elamur.ai/free/en/papers/quirk-2004-monolingual-machine-translation-paraphrase-generation/). In Proceedings of the EMNLP, 142–149, Barcelona, Spain.
21. A. Stolcke. 2002. SRILM – an extensible language modeling toolkit. In Proceedings of the ICSLP, Denver, CO. [find](https://scholar.google.com/scholar?q=A%2E+Stolcke%2E+2002%2E+SRILM+%E2%80%93+an+extensible+language+modeling+toolkit%2E+In+Proceedings+of+the+ICSLP%2C+Denver%2C+CO%2E)
22. B. Taskar, C. Guestrin, D. Koller. 2003. Max margin Markov networks. In Proceedings of NIPS 16. [find](https://scholar.google.com/scholar?q=B%2E+Taskar%2C+C%2E+Guestrin%2C+D%2E+Koller%2E+2003%2E+Max+margin+Markov+networks%2E+In+Proceedings+of+NIPS+16%2E)
23. I. Tsochantaridis, T. Joachims, T. Hofmann, Y. Altun. 2005. Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research, 6:1453–1484. [find](https://scholar.google.com/scholar?q=I%2E+Tsochantaridis%2C+T%2E+Joachims%2C+T%2E+Hofmann%2C+Y%2E+Altun%2E+2005%2E+Large+margin+methods+for+structured+and+interdependent+output+variables%2E+Journal+of+Machine+Learning+Research%2C+6%3A1453%E2%80%931484%2E)
24. J. Turner, E. Charniak. 2005. Supervised and unsupervised learning for sentence compression. In Proceedings of 43rd ACL, 290–297, Ann Arbor, MI. [find](https://scholar.google.com/scholar?q=J%2E+Turner%2C+E%2E+Charniak%2E+2005%2E+Supervised+and+unsupervised+learning+for+sentence+compression%2E+In+Proceedings+of+43rd+ACL%2C+290%E2%80%93297%2C+Ann+Arbor%2C+MI%2E)
25. V. Vandeghinste, Y. Pan. 2004. Sentence compression for automated subtitling: A hybrid approach. In Proceedings of the ACL Workshop on Text Summarization, 89–95, Barcelona, Spain. [find](https://scholar.google.com/scholar?q=V%2E+Vandeghinste%2C+Y%2E+Pan%2E+2004%2E+Sentence+compression+for+automated+subtitling%3A+A+hybrid+approach%2E+In+Proceedings+of+the+ACL+Workshop+on+Text+Summarization%2C+89%E2%80%9395%2C+Barcelona%2C+Spain%2E)

*Updated 24 October 2026*