BLEU

Last updated

BLEU (bilingual evaluation understudy) is an algorithm for evaluating the quality of text which has been machine-translated from one natural language to another. Quality is considered to be the correspondence between a machine's output and that of a human: "the closer a machine translation is to a professional human translation, the better it is" this is the central idea behind BLEU. Invented at IBM in 2001, [1] BLEU was one of the first metrics to claim a high correlation with human judgements of quality, and remains one of the most popular automated and inexpensive metrics.

Contents

Scores are calculated for individual translated segments—generally sentences—by comparing them with a set of good quality reference translations. Those scores are then averaged over the whole corpus to reach an estimate of the translation's overall quality. Intelligibility or grammatical correctness are not taken into account.

BLEU's output is always a number between 0 and 1. This value indicates how similar the candidate text is to the reference texts, with values closer to 1 representing more similar texts. Few human translations will attain a score of 1, since this would indicate that the candidate is identical to one of the reference translations. For this reason, it is not necessary to attain a score of 1. Because there are more opportunities to match, adding additional reference translations will increase the BLEU score.

Mathematical definition

Basic setup

A basic, first attempt at defining the BLEU score would take two arguments: a candidate string and a list of reference strings . The idea is that should be close to 1 when is similar to , and close to 0 if not.

As an analogy, the BLEU score is like a language teacher trying to score the quality of a student translation by checking how closely it follows the reference answers .

Since in natural language processing, one should evaluate a large set of candidate strings, one must generalize the BLEU score to the case where one has a list of M candidate strings (called a "corpus") , and for each candidate string , a list of reference candidate strings .

Given any string , and any integer , we define the set of its n-grams to be

Note that it is a set of unique elements, not a multiset allowing redundant elements, so that, for example, .

Given any two strings , define the substring count to be the number of appearances of as a substring of . For example, .

Now, fix a candidate corpus , and reference candidate corpus , where each .

Modified n-gram precision

Define the modified n-gram precision function to be

The modified n-gram, which looks complicated, is merely a straightforward generalization of the prototypical case: one candidate sentence and one reference sentence. In this case, it is

To work up to this expression, we start with the most obvious n-gram count summation:

This quantity measures how many n-grams in the reference sentence are reproduced by the candidate sentence. Note that we count the n-substrings, not n-grams. For example, when , all the 2-substrings in (ab and ba) appear in 3 times each, so the count is 6, not 2.


In the above situation, however, the candidate string is too short. Instead of 3 appearances of it contains only one, so we add a minimum function to correct for that:

This count summation cannot be used to compare between sentences, since it is not normalized. If both the reference and the candidate sentences are long, the count could be big, even if the candidate is of very poor quality. So we normalize it

The normalization is such that it is always a number in , allowing meaningful comparisons between corpuses. It is zero iff none of the n-substrings in candidate is in reference. It is one iff every n-gram in the candidate appears in reference, for at least as many times as in candidate. In particular, if the candidate is a substring of the reference, then it is one.

Brevity penalty

The modified n-gram precision unduly gives a high score for candidate strings that are "telegraphic", that is, containing all the n-grams of the reference strings, but for as few times as possible.

In order to punish candidate strings that are too short, define the brevity penalty to be

where is the positive part of .

is the length of the candidate corpus, that is,

where is the length of . is the effective reference corpus length, that is,

where , that is, the sentence from whose length is as close to as possible.

Final definition of BLEU

There is not a single definition of BLEU, but a whole family of them, parametrized by the weighting vector . It is a probability distribution on , that is, , and .

With a choice of , the BLEU score is

In words, it is a weighted geometric mean of all the modified n-gram precisions, multiplied by the brevity penalty. We use the weighted geometric mean, rather than the weighted arithmetic mean, to strongly favor candidate corpuses that are simultaneously good according to multiple n-gram precisions.

The most typical choice, the one recommended in the original paper, is . [2]

Algorithm

This is illustrated in the following example from Papineni et al. (2002):

Example of poor machine translation output with high precision
Candidatethethethethethethethe
Reference 1thecatisonthemat
Reference 2thereisacatonthemat

Of the seven words in the candidate translation, all of them appear in the reference translations. Thus the candidate text is given a unigram precision of,

where is number of words from the candidate that are found in the reference, and is the total number of words in the candidate. This is a perfect score, despite the fact that the candidate translation above retains little of the content of either of the references.

The modification that BLEU makes is fairly straightforward. For each word in the candidate translation, the algorithm takes its maximum total count, , in any of the reference translations. In the example above, the word "the" appears twice in reference 1, and once in reference 2. Thus .

For the candidate translation, the count of each word is clipped to a maximum of for that word. In this case, "the" has and , thus is clipped to 2. These clipped counts are then summed over all distinct words in the candidate. This sum is then divided by the total number of unigrams in the candidate translation. In the above example, the modified unigram precision score would be:

In practice, however, using individual words as the unit of comparison is not optimal. Instead, BLEU computes the same modified precision metric using n-grams. The length which has the "highest correlation with monolingual human judgements" was found to be four. The unigram scores are found to account for the adequacy of the translation, how much information is retained. The longer n-gram scores account for the fluency of the translation, or to what extent it reads like "good English".

Comparing metrics for candidate "the the cat"
ModelSet of gramsScore
Unigram"the", "the", "cat"
Grouped Unigram"the"*2, "cat"*1
Bigram"the the", "the cat"

An example of a candidate translation for the same references as above might be:

the cat

In this example, the modified unigram precision would be,

as the word 'the' and the word 'cat' appear once each in the candidate, and the total number of words is two. The modified bigram precision would be as the bigram, "the cat" appears once in the candidate. It has been pointed out that precision is usually twinned with recall to overcome this problem , as the unigram recall of this example would be or . The problem being that as there are multiple reference translations, a bad translation could easily have an inflated recall, such as a translation which consisted of all the words in each of the references.

To produce a score for the whole corpus, the modified precision scores for the segments are combined using the geometric mean multiplied by a brevity penalty to prevent very short candidates from receiving too high a score. Let r be the total length of the reference corpus, and c the total length of the translation corpus. If , the brevity penalty applies, defined to be . (In the case of multiple reference sentences, r is taken to be the sum of the lengths of the sentences whose lengths are closest to the lengths of the candidate sentences. However, in the version of the metric used by NIST evaluations prior to 2009, the shortest reference sentence had been used instead.)

iBLEU is an interactive version of BLEU that allows a user to visually examine the BLEU scores obtained by the candidate translations. It also allows comparing two different systems in a visual and interactive manner which is useful for system development.

Performance

BLEU has frequently been reported as correlating well with human judgement, and remains a benchmark for the assessment of any new evaluation metric. There are however a number of criticisms that have been voiced. It has been noted that, although in principle capable of evaluating translations of any language, BLEU cannot, in its present form, deal with languages lacking word boundaries. Designed to be used for several reference translation, in practice it's used with only the single one. [1] BLEU is infamously dependent on the tokenization technique, and scores achieved with different ones are incomparable (which is often overlooked); in order to improve reproducibility and comparability, SacreBLEU variant was designed. [1]

It has been argued that although BLEU has significant advantages, there is no guarantee that an increase in BLEU score is an indicator of improved translation quality.

See also

Notes

  1. ^ Papineni, K., et al. (2002)
  2. ^ Papineni, K., et al. (2002)
  3. ^ Coughlin, D. (2003)
  4. ^ Papineni, K., et al. (2002)
  5. ^ Papineni, K., et al. (2002)
  6. ^ Papineni, K., et al. (2002)
  7. ^ Coughlin, D. (2003)
  8. ^ Doddington, G. (2002)
  9. ^ Denoual, E. and Lepage, Y. (2005)
  10. ^ Callison-Burch, C., Osborne, M. and Koehn, P. (2006)
  11. ^ Lee, A. and Przybocki, M. (2005)
  12. ^ Callison-Burch, C., Osborne, M. and Koehn, P. (2006)
  13. ^ Lin, C. and Och, F. (2004)
  14. ^ Callison-Burch, C., Osborne, M. and Koehn, P. (2006)
  15. ^ Madnani, N. (2011)

Related Research Articles

<span class="mw-page-title-main">Gradient</span> Multivariate derivative (mathematics)

In vector calculus, the gradient of a scalar-valued differentiable function of several variables is the vector field whose value at a point gives the direction and the rate of fastest increase. The gradient transforms like a vector under change of basis of the space of variables of . If the gradient of a function is non-zero at a point , the direction of the gradient is the direction in which the function increases most quickly from , and the magnitude of the gradient is the rate of increase in that direction, the greatest absolute directional derivative. Further, a point where the gradient is the zero vector is known as a stationary point. The gradient thus plays a fundamental role in optimization theory, where it is used to maximize a function by gradient ascent. In coordinate-free terms, the gradient of a function may be defined by:

<span class="mw-page-title-main">Kinetic energy</span> Energy of a moving physical body

In physics, the kinetic energy of an object is the form of energy that it possesses due to its motion.

<span class="mw-page-title-main">Normal distribution</span> Probability distribution

In statistics, a normal distribution or Gaussian distribution is a type of continuous probability distribution for a real-valued random variable. The general form of its probability density function is

In statistical mechanics, the virial theorem provides a general equation that relates the average over time of the total kinetic energy of a stable system of discrete particles, bound by a conservative force, with that of the total potential energy of the system. Mathematically, the theorem states

In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series.

In vector calculus, the divergence theorem, also known as Gauss's theorem or Ostrogradsky's theorem, is a theorem which relates the flux of a vector field through a closed surface to the divergence of the field in the volume enclosed.

In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Unlike an ordinary series, the formal power series is not required to converge: in fact, the generating function is not actually regarded as a function, and the "variable" remains an indeterminate. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general linear recurrence problem. One can generalize to formal power series in more than one indeterminate, to encode information about infinite multi-dimensional arrays of numbers.

<span class="mw-page-title-main">Lagrange polynomial</span> Polynomials used for interpolation

In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree that interpolates a given set of data.

In physics, an operator is a function over a space of physical states onto another space of physical states. The simplest example of the utility of operators is the study of symmetry. Because of this, they are useful tools in classical mechanics. Operators are even more important in quantum mechanics, where they form an intrinsic part of the formulation of the theory.

The Breit equation, or Dirac–Coulomb–Breit equation, is a relativistic wave equation derived by Gregory Breit in 1929 based on the Dirac equation, which formally describes two or more massive spin-1/2 particles interacting electromagnetically to the first order in perturbation theory. It accounts for magnetic interactions and retardation effects to the order of 1/c2. When other quantum electrodynamic effects are negligible, this equation has been shown to give results in good agreement with experiment. It was originally derived from the Darwin Lagrangian but later vindicated by the Wheeler–Feynman absorber theory and eventually quantum electrodynamics.

<span class="mw-page-title-main">Wavelet transform</span> Mathematical technique used in data compression and analysis

In mathematics, a wavelet series is a representation of a square-integrable function by a certain orthonormal series generated by a wavelet. This article provides a formal, mathematical definition of an orthonormal wavelet and of the integral wavelet transform.

In natural language processing, latent Dirichlet allocation (LDA) is a Bayesian network for modeling automatically extracted topics in textual corpora. The LDA is an example of a Bayesian topic model. In this, observations are collected into documents, and each word's presence is attributable to one of the document's topics. Each document will contain a small number of topics.

<span class="mw-page-title-main">METEOR</span>

METEOR is a metric for the evaluation of machine translation output. The metric is based on the harmonic mean of unigram precision and recall, with recall weighted higher than precision. It also has several features that are not found in other metrics, such as stemming and synonymy matching, along with the standard exact word matching. The metric was designed to fix some of the problems found in the more popular BLEU metric, and also produce good correlation with human judgement at the sentence or segment level. This differs from the BLEU metric in that BLEU seeks correlation at the corpus level.

In probability theory and statistics, partial correlation measures the degree of association between two random variables, with the effect of a set of controlling random variables removed. When determining the numerical relationship between two variables of interest, using their correlation coefficient will give misleading results if there is another confounding variable that is numerically related to both variables of interest. This misleading information can be avoided by controlling for the confounding variable, which is done by computing the partial correlation coefficient. This is precisely the motivation for including other right-side variables in a multiple regression; but while multiple regression gives unbiased results for the effect size, it does not give a numerical value of a measure of the strength of the relationship between the two variables of interest.

Various methods for the evaluation for machine translation have been employed. This article focuses on the evaluation of the output of machine translation, rather than on performance or usability evaluation.

<span class="mw-page-title-main">Precision and recall</span> Pattern-recognition performance metrics

In pattern recognition, information retrieval, object detection and classification, precision and recall are performance metrics that apply to data retrieved from a collection, corpus or sample space.

In mathematics, a line integral is an integral where the function to be integrated is evaluated along a curve. The terms path integral, curve integral, and curvilinear integral are also used; contour integral is used as well, although that is typically reserved for line integrals in the complex plane.

In mathematics, the FEE method, or fast E-function evaluation method, is the method of fast summation of series of a special form. It was constructed in 1990 by Ekaterina Karatsuba and is so-named because it makes fast computations of the Siegel E-functions possible, in particular of .

<span class="mw-page-title-main">Symmetry in quantum mechanics</span> Properties underlying modern physics

Symmetries in quantum mechanics describe features of spacetime and particles which are unchanged under some transformation, in the context of quantum mechanics, relativistic quantum mechanics and quantum field theory, and with applications in the mathematical formulation of the standard model and condensed matter physics. In general, symmetry in physics, invariance, and conservation laws, are fundamentally important constraints for formulating physical theories and models. In practice, they are powerful methods for solving problems and predicting what can happen. While conservation laws do not always give the answer to the problem directly, they form the correct constraints and the first steps to solving a multitude of problems.

Gestalt pattern matching, also Ratcliff/Obershelp pattern recognition, is a string-matching algorithm for determining the similarity of two strings. It was developed in 1983 by John W. Ratcliff and John A. Obershelp and published in the Dr. Dobb's Journal in July 1988.

References

  1. 1 2 3 "BLEU: A Misunderstood Metric from Another Age". 5 November 2022.
  2. Papineni, Kishore; Roukos, Salim; Ward, Todd; Zhu, Wei-Jing (2001). "BLEU". Proceedings of the 40th Annual Meeting on Association for Computational Linguistics - ACL '02. Morristown, NJ, USA: Association for Computational Linguistics: 311. doi: 10.3115/1073083.1073135 . S2CID   11080756.

Bibliography