---
title: "Paraphrasing for Automatic Evaluation — Kauchak 2006"
description: "Metrics like BLEU score machine output by counting n-gram overlap with a human reference."
authors: ["David Kauchak", "Regina Barzilay"]
year: 2006
venue: "Proceedings of the Human Language Technology Conference of the NAACL, Main Conference"
source: "https://aclanthology.org/N06-1058/"
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/kauchak-2006-paraphrasing-automatic-evaluation/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/kauchak-2006-paraphrasing-automatic-evaluation/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2006](https://md.research.elamur.ai/free/en/papers/2006/) / Paraphrasing for Automatic Evaluation

# Paraphrasing for Automatic Evaluation

**Authors:** [David Kauchak](https://md.research.elamur.ai/free/en/authors/david-kauchak/), [Regina Barzilay](https://md.research.elamur.ai/free/en/authors/regina-barzilay/) · **Year:** 2006 · **Venue:** Proceedings of the Human Language Technology Conference of the NAACL, Main Conference · **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/N06-1058/) · [PDF](https://aclanthology.org/N06-1058.pdf) · [OpenAlex](https://openalex.org/W2132019450)

**Citations:** 218 citations (openalex-snapshot · 2026-10-14) · [103](#cited-by) in our library, of the 140884 papers whose bibliographies we read

## Summary
Metrics like BLEU score machine output by counting n-gram overlap with a human reference. They therefore penalize correct translations that use different wording. Kauchak and Barzilay show that such variation is common. In the NIST 2004 MT evaluation data, two independent human translations of the same sentence almost never match exactly.

Their remedy is to rewrite each reference so it borrows vocabulary from the system output while keeping its meaning. The method works in three steps:
1. Find unmatched word pairs that are WordNet synonyms.
2. Check each candidate with a per-word classifier trained on automatically gathered Gigaword sentences, using word sense disambiguation-style context features.
3. Substitute the words that pass, producing a synthetic reference that replaces the original in BLEU.

The context-filtered variant (ContextWN) brought BLEU closest to human judgments. Human-rated paraphrase accuracy across four resources (WordNet, ContextWN, LSA, Brown) ranked them in the same order as their benefit to evaluation. The work matters because it gives cheap semantic flexibility to overlap metrics. It also makes MT evaluation a task-based test of paraphrase quality.

## Key points
- Of 10,728 human reference pairs in NIST 2004 MT evaluation data, only 21 (under 0.2%) were identical, and 60% differed in at least 11 words.
- Candidate substitutions are limited to reference words absent from the output, paired with output words absent from the reference, and kept only if WordNet lists them as synonyms. Words occurring fewer than 10,000 times in Gigaword are never substituted.
- Context features are n-grams and position-tagged local collocations (n = 1…4, window i−2 to i+2). Training data is built automatically: sentences containing the target word are positives, and random sentences at random positions are negatives.
- Two judges rated paraphrase accuracy on 200 samples per method, with Kappa around 0.7:
  - ContextWN: about 75%
  - WordNet: about 63%
  - Brown: 56%
  - LSA: about 30%
  
  LSA made by far the most substitutions yet hurt BLEU's agreement with humans.
- Filtering discarded roughly a quarter of WordNet's proposals. Of 73 incorrect WordNet substitutions, 40 were removed, at the cost of wrongly dropping 27 correct ones. The net effect on evaluation was still positive.

## Interesting ideas
- **Paraphrase toward the output.** Rather than producing arbitrary paraphrases of a reference, rewrite it only toward words the hypothesis actually uses. This targeted normalization could help any overlap-based metric, including evaluation of Ukrainian generation where morphology and synonymy inflate surface mismatch.
- **Self-supervised substitution classifiers.** Each candidate word gets its own classifier, trained on raw-corpus sentences containing it versus random sentences. This needs no labeled data, so it transfers readily to lower-resource languages with large monolingual corpora.
- **Filter dictionary synonyms by context.** Lexical resources overgenerate, as when "place" inside "take place" gets matched to "home". A discriminative filter of this kind could improve thesaurus-based query expansion or data augmentation.
- **Accuracy over coverage.** The most prolific rewriter was the least useful, which is a good caution when choosing lexical resources for augmentation or matching.
- **Downstream use as an extrinsic test.** Ranking paraphrase sources by their effect on a metric's agreement with humans mirrored the manual accuracy ranking. Such a downstream check can serve as a cheaper proxy for intrinsic human annotation.

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

Fields: [Machine translation](https://md.research.elamur.ai/free/en/shelves/machine-translation/) · [Natural language processing](https://md.research.elamur.ai/free/en/shelves/nlp/)

Topics: [Word sense disambiguation](https://md.research.elamur.ai/free/en/topics/word-sense-disambiguation/) · [Machine translation](https://md.research.elamur.ai/free/en/topics/machine-translation/)

## Cited by

Cited by

103 papers of our library cite it (of the 140884 whose bibliographies we read); 14 of them have a page here, 89 not yet.

- [A Survey of Paraphrasing and Textual Entailment Methods](https://md.research.elamur.ai/free/en/papers/androutsopoulos-2009-survey-paraphrasing-textual-entailment-methods/)
- [Findings of the 2013 Workshop on Statistical Machine Translation](https://md.research.elamur.ai/free/en/papers/bojar-2013-findings-2013-workshop-statistical-machine/)
- [Syntactic Constraints on Paraphrases Extracted from Parallel Corpora](https://md.research.elamur.ai/free/en/papers/burch-2008-syntactic-constraints-paraphrases-extracted-parallel/)
- [Mutaphrase: Paraphrasing with FrameNet](https://md.research.elamur.ai/free/en/papers/ellsworth-2007-mutaphrase-paraphrasing-framenet/)
- [BLEU might be Guilty but References are not Innocent](https://md.research.elamur.ai/free/en/papers/freitag-2020-bleu-might-be-guilty-but/)
- [Towards Heterogeneous Automatic MT Error Analysis](https://md.research.elamur.ai/free/en/papers/gimenez-2008-heterogeneous-automatic-mt-error-analysis/)
- [UMBC_EBIQUITY-CORE: Semantic Textual Similarity Systems](https://md.research.elamur.ai/free/en/papers/han-2013-umbc-ebiquity-core-semantic-textual/)
- [ParaAMR: A Large-Scale Syntactically Diverse Paraphrase Dataset by AMR Back-Translation](https://md.research.elamur.ai/free/en/papers/huang-2023-paraamr-large-scale-syntactically-diverse/)
- [One Vector is Not Enough: Entity-Augmented Distributed Semantics for Discourse Relations](https://md.research.elamur.ai/free/en/papers/ji-2015-one-vector-is-not-enough/)
- [Paraphrase Generation with Deep Reinforcement Learning](https://md.research.elamur.ai/free/en/papers/li-2018-paraphrase-generation-deep-reinforcement-learning/)
- [Generating Phrasal and Sentential Paraphrases: A Survey of Data-Driven Methods](https://md.research.elamur.ai/free/en/papers/madnani-2010-generating-phrasal-sentential-paraphrases-survey/)
- [Fluency, Adequacy, or HTER? Exploring Different Human Judgments with a Tunable MT Metric](https://md.research.elamur.ai/free/en/papers/snover-2009-fluency-adequacy-or-hter-exploring/)
- [Paraphrasing as Zero-shot Translation with Feature-guided Diversity Enhancement](https://md.research.elamur.ai/free/en/papers/yan-2026-paraphrasing-as-zero-shot-translation/)
- [Application-driven Statistical Paraphrase Generation](https://md.research.elamur.ai/free/en/papers/zhao-2009-application-driven-statistical-paraphrase-generation/)

## Cite

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

```bibtex
@inproceedings{kauchak2006paraphrasing,
  title = {{Paraphrasing for Automatic Evaluation}},
  author = {Kauchak, David and Barzilay, Regina},
  booktitle = {Proceedings of the Human Language Technology Conference of the NAACL, Main Conference},
  year = {2006},
  doi = {10.3115/1220835.1220893},
  url = {https://doi.org/10.3115/1220835.1220893}
}
```

- [← previous Opentrad Apertium Open-Source Machine Translation System: an Opportunity for Business and Research](https://md.research.elamur.ai/free/en/papers/sanchez-2006-opentrad-apertium-open-source-machine/)
- [next → Parser Combination by Reparsing](https://md.research.elamur.ai/free/en/papers/sagae-2006-parser-combination-reparsing/)
- [↑ back to papers of 2006](https://md.research.elamur.ai/free/en/papers/2006/)

## References

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

1. B. Babych, A. Hartley. 2004. Extending the BLEU evaluation method with frequency weightings. In Proceedings of the ACL, 621–628. [find](https://scholar.google.com/scholar?q=B%2E+Babych%2C+A%2E+Hartley%2E+2004%2E+Extending+the+BLEU+evaluation+method+with+frequency+weightings%2E+In+Proceedings+of+the+ACL%2C+621%E2%80%93628%2E)
2. S. Banerjee, A. Lavie. 2005. METEOR: An automatic metric for MT evaluation with improved correlation with human judgments. In Proceedings of the ACL Workshop on Intrinsic and Extrinsic Evaluation Measures for MT and/or Summarization, 65–72. [find](https://scholar.google.com/scholar?q=S%2E+Banerjee%2C+A%2E+Lavie%2E+2005%2E+METEOR%3A+An+automatic+metric+for+MT+evaluation+with+improved+correlation+with+human+judgments%2E+In+Proceedings+of+the+ACL+Workshop+on+Intrinsic+and+Extrinsic+Evaluation+Meas) [our card](https://md.research.elamur.ai/free/en/papers/banerjee-2005-meteor-automatic-metric-mt-evaluation/)
3. R. Barzilay, L. Lee. 2003. Learning to paraphrase: An unsupervised approach using multiple-sequence alignment. In Proceedings of NAACL-HLT, 16–23. [find](https://scholar.google.com/scholar?q=R%2E+Barzilay%2C+L%2E+Lee%2E+2003%2E+Learning+to+paraphrase%3A+An+unsupervised+approach+using+multiple%2Dsequence+alignment%2E+In+Proceedings+of+NAACL%2DHLT%2C+16%E2%80%9323%2E) [our card](https://md.research.elamur.ai/free/en/papers/barzilay-2003-learning-paraphrase-unsupervised-approach-multiple/)
4. P. F. Brown, P. V. deSouza, R. L. Mercer. 1992. Class-based n-gram models of natural language. Computational Linguistics, 18:467–479. [find](https://scholar.google.com/scholar?q=P%2E+F%2E+Brown%2C+P%2E+V%2E+deSouza%2C+R%2E+L%2E+Mercer%2E+1992%2E+Class%2Dbased+n%2Dgram+models+of+natural+language%2E+Computational+Linguistics%2C+18%3A467%E2%80%93479%2E)
5. I. Dagan, O. Glickman, B. Magnini, eds. 2005. The PAS-CAL recognizing textual entailment challenge, 2005. [find](https://scholar.google.com/scholar?q=I%2E+Dagan%2C+O%2E+Glickman%2C+B%2E+Magnini%2C+eds%2E+2005%2E+The+PAS%2DCAL+recognizing+textual+entailment+challenge%2C+2005%2E)
6. P. Edmonds, G. Hirst. 2002. Near synonymy and lexical choice. Computational Linguistics, 28(2):105–144. [find](https://scholar.google.com/scholar?q=P%2E+Edmonds%2C+G%2E+Hirst%2E+2002%2E+Near+synonymy+and+lexical+choice%2E+Computational+Linguistics%2C+28%282%29%3A105%E2%80%93144%2E)
7. A. Haghighi, A. Ng, C. Manning. 2005. Robust textual inference via graph matching. In Proceedings of NAACL-HLT, 387–394. [find](https://scholar.google.com/scholar?q=A%2E+Haghighi%2C+A%2E+Ng%2C+C%2E+Manning%2E+2005%2E+Robust+textual+inference+via+graph+matching%2E+In+Proceedings+of+NAACL%2DHLT%2C+387%E2%80%93394%2E)
8. S. Harabagiu, D. Moldovan, M. Pasca, R. Mihalcea, M. Surdeanu, R. Bunescu, R. Girju, V. Rus, P. Morarescu. 2001. The role of lexico-semantic feedback in open-domain textual question-answering. In Proceedings of ACL, 274–291. [find](https://scholar.google.com/scholar?q=S%2E+Harabagiu%2C+D%2E+Moldovan%2C+M%2E+Pasca%2C+R%2E+Mihalcea%2C+M%2E+Surdeanu%2C+R%2E+Bunescu%2C+R%2E+Girju%2C+V%2E+Rus%2C+P%2E+Morarescu%2E+2001%2E+The+role+of+lexico%2Dsemantic+feedback+in+open%2Ddomain+textual+question%2Danswering%2E+In+Proc)
9. P. Koehn. 2004. Statistical significance tests for machine translation evaluation. In Proceedings of EMNLP, 388–395. [find](https://scholar.google.com/scholar?q=P%2E+Koehn%2E+2004%2E+Statistical+significance+tests+for+machine+translation+evaluation%2E+In+Proceedings+of+EMNLP%2C+388%E2%80%93395%2E)
10. J. R. Landis, G. G. Koch. 1977. The measurement of observer agreement for categorical data. Biometrics, 33:159–174. [find](https://scholar.google.com/scholar?q=J%2E+R%2E+Landis%2C+G%2E+G%2E+Koch%2E+1977%2E+The+measurement+of+observer+agreement+for+categorical+data%2E+Biometrics%2C+33%3A159%E2%80%93174%2E)
11. C. Lin, F. Och. 2004. ORANGE: a method for evaluating automatic evaluation metrics for machine translation. In Proceedings of COLING, 501–507. [find](https://scholar.google.com/scholar?q=C%2E+Lin%2C+F%2E+Och%2E+2004%2E+ORANGE%3A+a+method+for+evaluating+automatic+evaluation+metrics+for+machine+translation%2E+In+Proceedings+of+COLING%2C+501%E2%80%93507%2E) [our card](https://md.research.elamur.ai/free/en/papers/lin-2004-orange-method-evaluating-automatic-evaluation/)
12. I. D. Melamed, R. Green, J. P. Turian. 2003. Precision and recall of machine translation. In Proceedings of NAACL-HLT, 61–63. [find](https://scholar.google.com/scholar?q=I%2E+D%2E+Melamed%2C+R%2E+Green%2C+J%2E+P%2E+Turian%2E+2003%2E+Precision+and+recall+of+machine+translation%2E+In+Proceedings+of+NAACL%2DHLT%2C+61%E2%80%9363%2E) [our card](https://md.research.elamur.ai/free/en/papers/melamed-2003-precision-recall-machine-translation/)
13. S. Miller, J. Guinness, A. Zamanian. 2004. Name tagging with word clusters and discriminative training. In Proceedings of HLT-NAACL, 337–342. [find](https://scholar.google.com/scholar?q=S%2E+Miller%2C+J%2E+Guinness%2C+A%2E+Zamanian%2E+2004%2E+Name+tagging+with+word+clusters+and+discriminative+training%2E+In+Proceedings+of+HLT%2DNAACL%2C+337%E2%80%93342%2E) [our card](https://md.research.elamur.ai/free/en/papers/miller-2004-name-tagging-word-clusters-discriminative/)
14. NIST. 2002. Automatic evaluation of machine translation quality using n-gram co-occurrence statistics, 2002. [find](https://scholar.google.com/scholar?q=NIST%2E+2002%2E+Automatic+evaluation+of+machine+translation+quality+using+n%2Dgram+co%2Doccurrence+statistics%2C+2002%2E)
15. B. Pang, K. Knight, D. Marcu. 2003. Syntax-based alignment of multiple translations: Extracting paraphrases and generating new sentences. In Proceedings of NAACL-HLT, 102–209. [find](https://scholar.google.com/scholar?q=B%2E+Pang%2C+K%2E+Knight%2C+D%2E+Marcu%2E+2003%2E+Syntax%2Dbased+alignment+of+multiple+translations%3A+Extracting+paraphrases+and+generating+new+sentences%2E+In+Proceedings+of+NAACL%2DHLT%2C+102%E2%80%93209%2E) [our card](https://md.research.elamur.ai/free/en/papers/pang-2003-syntax-based-alignment-multiple-translations/)
16. K. Papineni, S. Roukos, T. Ward, W. Zhu. 2002. BLEU: a method for automatic evaluation of machine translation. In Proceedings of the ACL, 311–318. [find](https://scholar.google.com/scholar?q=K%2E+Papineni%2C+S%2E+Roukos%2C+T%2E+Ward%2C+W%2E+Zhu%2E+2002%2E+BLEU%3A+a+method+for+automatic+evaluation+of+machine+translation%2E+In+Proceedings+of+the+ACL%2C+311%E2%80%93318%2E) [our card](https://md.research.elamur.ai/free/en/papers/papineni-2002-bleu-method-automatic-evaluation-machine/)
17. C. Quirk, C. Brockett, W. Dolan. 2004. Monolingual machine translation for paraphrase generation. In Proceedings of EMNLP, 142–149. [find](https://scholar.google.com/scholar?q=C%2E+Quirk%2C+C%2E+Brockett%2C+W%2E+Dolan%2E+2004%2E+Monolingual+machine+translation+for+paraphrase+generation%2E+In+Proceedings+of+EMNLP%2C+142%E2%80%93149%2E) [our card](https://md.research.elamur.ai/free/en/papers/quirk-2004-monolingual-machine-translation-paraphrase-generation/)
18. R. E. Schapire, Y. Singer. 2000. Boostexter: A boosting-based system for text categorization. Machine Learning, 39(2/3):135–168. [find](https://scholar.google.com/scholar?q=R%2E+E%2E+Schapire%2C+Y%2E+Singer%2E+2000%2E+Boostexter%3A+A+boosting%2Dbased+system+for+text+categorization%2E+Machine+Learning%2C+39%282%2F3%29%3A135%E2%80%93168%2E)
19. R. Serafin, B. D. Eugenio. 2004. FLSA: Extending latent semantic analysis with features for dialogue act classification. In Proceedings of the ACL, 692–699. [find](https://scholar.google.com/scholar?q=R%2E+Serafin%2C+B%2E+D%2E+Eugenio%2E+2004%2E+FLSA%3A+Extending+latent+semantic+analysis+with+features+for+dialogue+act+classification%2E+In+Proceedings+of+the+ACL%2C+692%E2%80%93699%2E) [our card](https://md.research.elamur.ai/free/en/papers/serafin-2004-flsa-extending-latent-semantic-analysis/)
20. A. Stent, M. Marge, M. Singhai. 2005. Evaluating evaluation methods for generation in the presense of variation. In Proceedings of CICLING, 341–351. [find](https://scholar.google.com/scholar?q=A%2E+Stent%2C+M%2E+Marge%2C+M%2E+Singhai%2E+2005%2E+Evaluating+evaluation+methods+for+generation+in+the+presense+of+variation%2E+In+Proceedings+of+CICLING%2C+341%E2%80%93351%2E)