Evaluating Machine Translations Using mNCD

Marcus Dobrinkat, Tero Tapiovaara, Jaakko Väyrynen, Kimmo KettunenACL 2010

Introduction

Evaluating machine translation (MT) systems presents a significant challenge: while human evaluation is the gold standard for accuracy, it is prohibitively slow and expensive for iterative development. Conversely, automatic metrics like BLEU are efficient but often too rigid, relying on exact word matches and failing to account for linguistic variations such as stems (e.g., "running" vs. "run") or synonyms (e.g., "happy" vs. "glad").

This paper introduces mNCD, a hybrid evaluation metric that bridges the gap between information theory and linguistics. By enhancing the theoretically grounded Normalized Compression Distance (NCD) with flexible linguistic matching, the authors provide a measure that correlates more closely with human judgment.

Methodology: From NCD to mNCD

Normalized Compression Distance (NCD) is a language-independent similarity measure based on Kolmogorov complexity. It operates on the principle that if two strings are similar, they will share patterns that allow them to be compressed more efficiently together than separately. However, standard NCD is "blind" to linguistic nuances.

The core innovation of this work is the "m" factor, which incorporates "relaxed matching" modules from the METEOR metric. This process involves several steps:

  1. Linguistic Identification: The algorithm identifies words in the machine-translated hypothesis and the human reference that share a stem or are synonyms.
  2. Similarized References: A "similarized reference" (S) is created by replacing words in the human reference with the specific words used in the hypothesis whenever a stem or synonym match is found.
  3. Compression-Based Scoring: The final score is calculated by determining the NCD between the hypothesis and this newly created similarized reference.
Examples of candidate (C), reference (R), and similarized reference (S) strings with corresponding 1-NCD and METEOR scores.

The researchers evaluated two compression algorithms: PPMZ, which offers higher performance at a slower speed, and bz2, which is faster but slightly less precise.

Experimental Setup

The metric was tested using data from the 2008 ACL Workshop on Statistical Machine Translation (WMT08), featuring translations from 30 different MT systems across English and five European languages. Human benchmarks included three categories: RANK (relative quality), CONST (short phrase rankings), and YES/NO (phrase acceptability).

Key Results and Insights

The integration of linguistic "slack" proved essential. By allowing the reference to adapt to the hypothesis through synonyms and stems, the metric became significantly more representative of human perception.

Performance Gains

In English tasks, mNCD (using the PPMZ compressor) improved the correlation with human "RANK" judgments by 15% compared to standard NCD. As shown in the table below, mNCD consistently outperformed standard NCD across all human judgment categories and parameter settings.

Comparison of mNCD and NCD performance across various human judgment categories (RANK, CONST, YES/NO) and parameter settings.

Robustness and Semantic Flexibility

Experiments with "block size" revealed that NCD is remarkably robust across different text granularities, with correlations remaining stable whether calculated on individual sentences or entire documents. Furthermore, the most pronounced improvements occurred in English, the only language for which a synonym database was available during testing, highlighting semantic flexibility as a primary driver of accuracy.

Limitations and Future Work

While effective, mNCD introduces a dependency on high-quality linguistic resources like WordNet, which reduces the language-independent advantage of pure NCD. Results in French, Spanish, and German were less consistent due to the lack of synonym modules for those languages.

Future research will focus on using statistical methods to automatically generate synonym lexicons for other languages and implementing context-aware word sense disambiguation to refine the synonym matching process.

Summary updated

BibTeX
@inproceedings{dobrinkat2010evaluating,
  author = {Marcus Dobrinkat and Tero Tapiovaara and Jaakko Väyrynen and Kimmo Kettunen},
  title = {{Evaluating Machine Translations Using mNCD}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
}
Figure