Back

Statistical Significance Tests for Machine Translation Evaluation

Philipp Koehn

article2004EMNLP1,938 citations

Proposes bootstrap resampling techniques to accurately test the statistical significance of machine translation evaluations using metrics like BLEU, enabling reliable system comparisons even on test sets as small as 300 sentences.

Listen

The rapid development of statistical machine translation relies heavily on automated metrics like BLEU to assess quality improvements across system iterations. However, standard testing on small sample sets often leaves engineering teams and decision-makers uncertain whether observed performance gains reflect genuine quality advancements or mere random variation. Standard statistical formulas cannot easily compute confidence bounds for complex metrics like BLEU because they are computed at the aggregate corpus level rather than as simple sentence-level averages.

The article set out to evaluate bootstrap resampling methods for estimating statistical significance in machine translation evaluation. It aimed to demonstrate that these computational techniques can reliably determine whether performance differences between translation systems are real, even when evaluating small test sets.

The author evaluated this approach by training phrase-based translation systems on the multi-language Europarl dataset and measuring performance against a massive baseline benchmark of 30,000 sentence pairs. To simulate cost-effective development cycles, the large dataset was subdivided into smaller test sets ranging from 100 to 3,000 sentences. The article evaluated paired bootstrap resampling—a technique where virtual test sets are repeatedly created by drawing sentences with replacement from an existing small sample—and compared its estimated confidence levels against the true results established on the full 30,000-sentence corpus.

The key findings indicate that paired bootstrap resampling provides highly accurate and slightly conservative significance estimates across multiple test sizes. First, when comparing systems with a moderate performance gap of 2% to 3% BLEU, test sets as small as 300 sentences (roughly 9,000 words) are sufficient to reliably identify the superior system with 95% statistical significance. Second, significance testing proved well-calibrated; conclusions estimated at the 90% to 95% confidence level were accurate 95% of the time, demonstrating that the method errs slightly on the side of caution. Third, the sampling method substantially alters test stability: selecting consecutive sentences caused score swings between 21% and 37%, whereas broadly sampling sentences from different sections of the corpus narrowed the variance to between 27% and 31%.

These findings mean development teams can safely reduce evaluation costs, computational overhead, and development cycle times without sacrificing rigorous decision-making. Instead of running computationally expensive tests on tens of thousands of sentences or risking false conclusions from raw score differences, organizations can use small, targeted test sets to guide model deployment and tuning decisions.

The source supports recommending that translation development workflows incorporate paired bootstrap resampling and broad corpus sampling as standard evaluation protocol. For very close system comparisons where true performance differences are under 1%, teams should expand sample sizes beyond 300 sentences to ensure reliable detection. While confidence in the methodology is strong, practitioners should exercise caution with extremely small sets of 100 sentences, which exhibited elevated false-conclusion rates, and remember that significance thresholds depend on system variance and domain consistency.

Massachusetts Institute of Technologystatistical significancesystem qualitytest resultsstatistical significance testsmachine translation evaluationBLEU score difference
Koehn (2004).pdf
Cover for Statistical Significance Tests for Machine Translation Evaluation

Abstract

If two translation systems differ differ in performance on a test set, can we trust that this indicates a difference in true system quality? To answer this question, we describe bootstrap resampling methods to compute statistical significance of test results, and validate them on the concrete example of the BLEU score. Even for small test sizes of only 300 sentences, our methods may give us assurances that test result differences are real.

Topics

statistical significancesystem qualitytest resultstest samplestranslation systemstranslation modelstranslation process

Keywords

statistical significance testsmachine translation evaluationBLEU score differencestatistical machine translation systemreference translationsparallel corpora

Table of Contents

  • 1 Introduction
  • 2 Background
  • 2.1 Statistical Machine Translation
  • 2.2 Automatic Evaluation
  • 2.3 BLEU: A Closer Look
  • 3 Experimental Design
  • 3.1 System and Corpus
  • 3.2 Selecting a Test Set
  • 3.3 Broad Sampling
  • 3.4 Comparison of Translation Performance
  • 4 Statistical Significance
  • 5 Bootstrap Resampling
  • 6 Paired Bootstrap Resampling
  • 7 Validation Experiments
  • 7.1 95% Statistical Significance
  • 7.2 Other Significance Levels
  • 8 Summary and Outlook
  • References

Knowls

  1. Knowl 1 — Paired Bootstrap Resampling for Machine Translation System Comparison

    algorithm

    To evaluate whether translation system AA is significantly better than translation system BB on a test set of nn sentences according to an evaluation metric (such as BLEU), paired bootstrap resampling repeatedly resamples test sentences to estimate the probability that one system outperforms the other on the underlying distribution:

    Input: Translations TAT_A from System A, translations TBT_B from System B, references TrefT_{ref} (each of length nn), evaluation metric Score(⋅,⋅)\text{Score}(\cdot, \cdot), number of resamples RR (e.g., R=1000R = 1000), significance threshold α\alpha (e.g., α=0.05\alpha = 0.05)
    Output: Significance verdict and estimated probability of superiority
    wins_A = 0
    wins_B = 0
    for r = 1 to R do
        I=I = array of nn indices sampled uniformly with replacement from {1,…,n}\{1, \dots, n\}
        TA(r)={TA[i]:i∈I}T_A^{(r)} = \{T_A[i] : i \in I\}
        TB(r)={TB[i]:i∈I}T_B^{(r)} = \{T_B[i] : i \in I\}
        Tref(r)={Tref[i]:i∈I}T_{ref}^{(r)} = \{T_{ref}[i] : i \in I\}
        SA=Score(TA(r),Tref(r))S_A = \text{Score}(T_A^{(r)}, T_{ref}^{(r)})
        SB=Score(TB(r),Tref(r))S_B = \text{Score}(T_B^{(r)}, T_{ref}^{(r)})
        if SA>SBS_A > S_B then
            wins_A = wins_A + 1
        else if SB>SAS_B > S_A then
            wins_B = wins_B + 1
        end if
    end for
    significance_A = wins_A / R
    significance_B = wins_B / R
    if significance_A >= 1 - \alpha then
        return System A is superior to System B at the 100(1−α)%100(1 - \alpha)\% significance level
    else if significance_B >= 1 - \alpha then
        return System B is superior to System A at the 100(1−α)%100(1 - \alpha)\% significance level
    else
        return Difference is not statistically significant at the 100(1−α)%100(1 - \alpha)\% level
    end if

    By evaluating both systems on identical resampled sentence sets II, the test pairs the observations, directly modeling the variance of their score differences.

  2. Knowl 2 — Bootstrap Resampling for Metric Confidence Interval Estimation

    algorithm

    Because non-linear corpus-level evaluation metrics such as BLEU do not decompose into sample averages of independent sentence scores, Student's tt-distribution cannot be used analytically to construct confidence intervals. Non-parametric bootstrap resampling computes empirical confidence intervals from a single evaluation set of nn sentences:

    Input: System translations TT, reference translations TrefT_{ref} (both of size nn), evaluation metric Score(⋅,⋅)\text{Score}(\cdot, \cdot), number of resamples RR (e.g., R=1000R = 1000), confidence level qq (e.g., q=0.95q = 0.95)
    Output: Confidence interval [a,b][a, b]
    scores = empty list
    for r = 1 to R do
        I=I = array of nn indices sampled uniformly with replacement from {1,…,n}\{1, \dots, n\}
        T(r)={T[i]:i∈I}T^{(r)} = \{T[i] : i \in I\}
        Tref(r)={Tref[i]:i∈I}T_{ref}^{(r)} = \{T_{ref}[i] : i \in I\}
        s(r)=Score(T(r),Tref(r))s^{(r)} = \text{Score}(T^{(r)}, T_{ref}^{(r)})
        Append s(r)s^{(r)} to scores
    end for
    Sort scores in ascending order: s(1)≤s(2)≤⋯≤s(R)s_{(1)} \le s_{(2)} \le \dots \le s_{(R)}
    low_idx = round(R⋅(1−q)/2R \cdot (1 - q) / 2) + 1
    high_idx = round(R⋅(1−(1−q)/2)R \cdot (1 - (1 - q) / 2))
    a = scores[low_idx]
    b = scores[high_idx]
    return interval [a,b][a, b]

    For R=1000R = 1000 and q=0.95q = 0.95, dropping the lowest 2525 (2.5%2.5\%) and highest 2525 (2.5%2.5\%) scores yields the 95%95\% confidence interval [s(26),s(975)][s_{(26)}, s_{(975)}].

  3. Knowl 3 — Bootstrap Resampling Equivalence Assumption for MT Evaluation

    assumption

    The application of bootstrap resampling to machine translation evaluation assumes that estimating the confidence interval from a large number of test sets of nn sentences drawn with replacement from a fixed set of nn test sentences is equivalent to estimating the confidence interval from a large number of test sets of size nn drawn from an infinite population of domain sentences. This assumption enables researchers to compute statistical significance from a single translation run of nn sentences without requiring repeated translations of new sentences.

  4. Knowl 4 — Empirical Calibration and Accuracy of Bootstrap Significance Levels

    data/table

    To validate whether the nominal significance levels estimated by paired bootstrap resampling reflect true error rates, paired comparisons on small test subsets drawn from Europarl were checked against the ground-truth outcomes computed on a large test set of 30,000 sentences across various significance bins.

    Significance Level Conclusions Correct
    100% 1042 100%
    99%–99.9% 738 100%
    98%–98.9% 245 99%
    95%–97.9% 394 98%
    90%–94.9% 363 95%
    80%–89.9% 520 88%
    70%–79.9% 324 77%
    60%–69.9% 253 72%
    50%–59.9% 261 52%

    The empirical accuracy of the conclusions consistently matches or exceeds the nominal significance interval (e.g., 95%95\% accuracy for conclusions in the 90%–94.9%90\%\text{--}94.9\% significance bin), demonstrating that paired bootstrap resampling produces well-calibrated, slightly conservative significance estimates.

  5. Knowl 5 — Statistical Power of Paired Bootstrap Resampling by Sample Size and Effect Size

    data/table

    The empirical probability of reaching a conclusion at the 95%95\% statistical significance level depends on the true BLEU score difference (evaluated on 30,000 sentences) and the sample size (n=100,300,600,3000n = 100, 300, 600, 3000). The table reports the percentage of correct and incorrect conclusions drawn across distinct test set samples:

    System BLEU Sample Size (Sentences)
    Comparison Difference 100 300 600 3000
    Spanish better than Portuguese 1.5% 33% / 1% 60% 84% 100%
    Spanish better than Danish 2.0% 31% 65% 96% 100%
    Portuguese better than Danish 0.5% 7% / 2% 12% / 1% 10% 30%
    Portuguese better than Greek 2.1% 38% 68% 92% 100%
    Danish better than Greek 1.6% 24% 48% 74% 100%
    Danish better than German 4.3% 85% 100% 100% 100%
    Greek better than German 2.7% 65% 97% 100% 100%
    Greek better than Finnish 5.1% 97% 100% 100% 100%
    German better than Finnish 2.4% 53% 91% 100% 100%

    Entries of the form X% / Y% indicate X%X\% correct and Y%Y\% wrong conclusions (single percentages represent 0%0\% errors). When the true BLEU difference is at least 2.0%–3.0%2.0\%\text{--}3.0\%, a sample size of 300 sentences reliably detects system superiority in 65%–100%65\%\text{--}100\% of cases with nearly zero errors.

  6. Knowl 6 — Broad Sampling Strategy for Representative Test Set Construction

    model/method

    When evaluating translation quality on small test sets (e.g., n=300n = 300 sentences), consecutive sentence blocks exhibit large variance in BLEU scores (ranging from 21%21\% to 37%37\% on Europarl) because factors affecting translation difficulty (such as topic, vocabulary, syntactic complexity, and original source language) cluster across adjacent sentences.

    To build representative test sets and minimize score variance, a broad sampling strategy selects sentences distributed across the entire corpus at uniform stride. For a corpus of N=30,000N = 30,000 sentences, the kk-th sample set of 300 sentences (where k∈{1,…,100}k \in \{1, \dots, 100\}) is formed by taking sentences: {k,k+100,k+200,…,k+29900}\{k, k + 100, k + 200, \dots, k + 29900\} Broad sampling narrows the BLEU variance across 100 test sets of 300 sentences to a range of 27%–31%27\%\text{--}31\%, compared to 21%–37%21\%\text{--}37\% for consecutive blocks.

  7. Knowl 7 — Empirical Coverage of Bootstrapped BLEU Confidence Intervals

    empirical result

    When computing 95%95\% confidence intervals via bootstrap resampling (R=1000R = 1000 resamples) on 100 broad samples of 300 sentences for a Spanish-to-English translation system, the true system score (28.9%28.9\% BLEU, measured on 30,000 sentences) fell inside the estimated confidence interval for 97 of the 100 samples. The interval failed to contain the true value in only 3 test samples (samples no. 10, 81, and 88), yielding an empirical coverage of 97%97\%, which validates the theoretical 95%95\% confidence expectation.

  8. Knowl 8 — Sample Size and Performance Gap Limitations in Paired Bootstrap Resampling

    limitation

    The efficacy of paired bootstrap resampling for machine translation evaluation is limited by two main factors:

    1. Sample size below 300 sentences: At n=100n = 100 sentences, the rate of false conclusions at the 95%95\% significance level increases noticeably (e.g., 1%1\% false positives for Spanish vs. Portuguese and 2%2\% for Portuguese vs. Danish), indicating that test sets of 100 sentences are too small for reliable MT evaluation.
    2. Small true score differences (<1.0%< 1.0\% BLEU): When the true performance gap is narrow (such as 0.5%0.5\% BLEU between Portuguese and Danish), a test set of 300 sentences reaches 95%95\% significance in only 12%12\% of samples (with 1%1\% incorrect conclusions), and even a large test set of 3000 sentences only reaches significance in 30%30\% of samples.

Coverage note — None was omitted; all key algorithms, the core assumption, experimental designs, calibration tables, power analyses, and stated limitations of bootstrap significance testing for MT evaluation have been covered.

References

  1. 1.Brown, P., Cocke, J., Pietra, S. A. D., Pietra, V. J. D., Jelinek, F., Lafferty, J. D., Mercer, R. L., and Rossin, P. (1990). A statistical approach to machine translation. Computational Linguistics, 16(2):76–85.
  2. 2.Brown, P. F., Pietra, S. A. D., Pietra, V. J. D., and Mercer, R. L. (1993). The mathematics of statistical machine translation. Computational Linguistics, 19(2):263–313.
  3. 3.Efron, B. and Tibshirani, R. J. (1994). An Introduction to the Bootstrap. CRC Press.
  4. 4.Germann, U. (2003). Greedy decoding for statistical machine translation in almost linear time. In Proceedings of HLT-NAACL.
  5. 5.Koehn, P. (2002). Europarl: A multilingual corpus for evaluation of machine translation. Unpublished, http://www.isi.edu/~koehn/europarl/.
  6. 6.Koehn, P. (2004). Pharaoh: a beam search decoder for phrase-based statistical machine translation models. In Proceedings of AMTA.
  7. 7.Koehn, P., Och, F. J., and Marcu, D. (2003). Statistical phrase based translation. In Proceedings of HLT-NAACL.
  8. 8.Kumar, S. and Byrne, W. (2004). Minimum bayes-risk decoding for statistical machine translation. In Proceedings of HLT-NAACL.
  9. 9.Melamed, I. D., Green, R., and Turian, J. P. (2003). Precision and recall of machine translation. In Proceedings of HLT-NAACL.
  10. 10.Och, F. J. (2002). Statistical Machine Translation: From Single-Word Models to Alignment Templates. PhD thesis, RWTH Aachen, Germany.
  11. 11.Och, F. J. (2003). Minimum error rate training for statistical machine translation. In Proceedings of ACL.
  12. 12.Papineni, K., Roukos, S., Ward, T., and Zhu, W.-J. (2002). BLEU: a method for automatic evaluation of machine translation. In Proceedings of ACL.
  13. 13.Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. (2002). Numerical Recipes in C++. Cambridge University Press.
  14. 14.Tillmann, C. (2003). A projection extension algorithm for statistical machine translation. In Collins, M. and Steedman, M., editors, Proceedings of EMNLP, pages 1–8.
  15. 15.Vogel, S., Zhang, Y., Huang, F., Tribble, A., Venugopal, A., Zhao, B., and Waibel, A. (2003). The CMU statistical machine translation system. In Proceedings of MT Summit IX.
  16. 16.Zens, R., Och, F. J., and Ney, H. (2002). Phrase-based statistical machine translation. In Proceedings of the German Conference on Artificial Intelligence (KI 2002).

Citation

MLA
Koehn, P. “Statistical Significance Tests for Machine Translation Evaluation”. Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, 2004, pp. 388–95, https://aclanthology.org/W04-3250/.
APA
Koehn, P. (2004). Statistical Significance Tests for Machine Translation Evaluation. Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, 388–395. https://aclanthology.org/W04-3250/
Chicago
Koehn, P. 2004. “Statistical Significance Tests for Machine Translation Evaluation”. Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, 388–95. https://aclanthology.org/W04-3250/.
Harvard
Koehn, P. (2004) “Statistical Significance Tests for Machine Translation Evaluation”, Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, pp. 388–395. Available at: https://aclanthology.org/W04-3250/.
Vancouver
1. Koehn P (2004) Statistical Significance Tests for Machine Translation Evaluation. In: Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, pp 388–395

BibTeX

@inproceedings{koehn-2004-statistical,
    title = "Statistical Significance Tests for Machine Translation Evaluation",
    author = "Koehn, Philipp",
    editor = "Lin, Dekang  and
      Wu, Dekai",
    booktitle = "Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing",
    month = jul,
    year = "2004",
    address = "Barcelona, Spain",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/W04-3250/",
    pages = "388--395"
}
Metadata:ACL Anthology

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by-nc-sa/4.0/