Lei Mao bio photo

Lei Mao

Machine Learning, Artificial Intelligence. On the Move.

Twitter Facebook LinkedIn GitHub   G. Scholar E-Mail RSS

Introduction

BLEU is a standard algorithm for evaluating the machine translations against the human translations. At first I thought it should be very straightforward to use. However, it turns out that there are a lot of caveats.


In this blog post, I am going to show the BLEU algorithm in detail and talk about the caveats.

English Translation Example

We will use the following examples to illustrate how to compute the BLEU scores.

Example 1

Chinese: 猫坐在垫子上

Reference 1: the cat is on the mat

Reference 2: there is a cat on the mat

Candidate: the cat the cat on the mat

Example 2

Chinese: 猫坐在垫子上

Reference 1: the cat is on the mat

Reference 2: there is a cat on the mat

Candidate: the the the the the the the the

Precision

We count each of the ngram in the candidate sentence whether it has shown in any of the reference sentences, gather the total counts for each of the unique ngram, sum up the total counts for each of the unique ngram, and divided by the number of ngrams in the candidate sentence.

Example 1

We first compute the unigram precision for example 1. All the unigrams in the candidate sentences have shown in the reference sentences.

Unigram Shown?
the 1
cat 1
the 1
cat 1
on 1
the 1
mat 1

We then merge the unigram counts together.

Unique Unigram Count
the 3
cat 2
on 1
mat 1

The total number of counts for the unique unigrams in the candidate sentence is 7, and the total number of unigrams in the candidate sentence is 7. The unigram precision is 7/7 = 1.0 for example 1.


We then try to compute the bigram precision for example 1.

Bigram Shown?
the cat 1
cat the 0
the cat 1
cat on 1
on the 1
the mat 1

We then merge the bigram counts together.

Unique Bigram Count
the cat 2
cat the 0
cat on 1
on the 1
the mat 1

The total number of counts for the unique bigrams in the candidate sentence is 5, and the total number of bigrams in the candidate sentence is 6. The bigram precision is 5/6 = 0.833 for example 1.

Example 2

We first compute the unigram precision for example 2. All the unigrams in the candidate sentences have shown in the reference sentences.

Unigram Shown?
the 1
the 1
the 1
the 1
the 1
the 1
the 1
the 1

We then merge the unigram counts together.

Unique Unigram Count
the 8

The total number of counts for the unique unigrams in the candidate sentence is 8, and the total number of unigrams in the candidate sentence is 8. The unigram precision is 8/8 = 1.0 for example 2.


We then try to compute the bigram precision for example 2.

Bigram Shown?
the the 0
the the 0
the the 0
the the 0
the the 0
the the 0
the the 0

We then merge the bigram counts together.

Unique Bigram Count
the the 0

The total number of counts for the unique bigrams in the candidate sentence is 0, and the total number of bigrams in the candidate sentence is 7. The bigram precision is 0/7 = 0 for example 2.

Drawbacks

We can see from example 1 and 2 that unigram precision is very easy to be over-confident about the quality of the machine translation. To overcome this, clipped count and modified precision were proposed.

Modified Precision

For each unique ngram, we count its maximum frequency in each of the reference sentences. The minimum of this special count and the original count is called the clipped the count. That is to say, the clipped count is no greater than the original count. We then use this clipped count, in place of the original count, for computing the modified precision.

Example 1

Unique Unigram Count Clipped Count
the 3 2
cat 2 1
on 1 1
mat 1 1

The total number of clipped counts for the unique unigrams in the candidate sentence is 5, and the total number of unigrams in the candidate sentence is 7. The unigram modified precision is 5/7 = 0.714 for example 1.

Unique Bigram Count Clipped Count
the cat 2 1
cat the 0 0
cat on 1 1
on the 1 1
the mat 1 1

The total number of clipped counts for the unique bigrams in the candidate sentence is 4, and the total number of unigrams in the candidate sentence is 6. The bigram modified precision is 4/6 = 0.667 for example 1.

Example 2

Unique Unigram Count Clipped Count
the 8 2

The total number of clipped counts for the unique bigrams in the candidate sentence is 0, and the total number of unigrams in the candidate sentence is 8. The unigram modified precision is 2/8 = 0.25 for example 2.

Unique Bigram Count Clipped Count
the the 0 0

The total number of clipped counts for the unique bigrams in the candidate sentence is 0, and the total number of bigrams in the candidate sentence is 7. The bigram precision is 0/7 = 0 for example 2.

Advantages

Compared to precision, we found that modified precision is a better metric, at least for unigrams.

BLEU

Algorithm

BLEU is computed using a couple of ngram modified precisions. Specifically,

where $p_n$ is the modified precision for $n$gram, the base of $\log$ is the natural base $e$, $w_n$ is weight between 0 and 1 for $\log p_n$ and $\sum_{n=1}^{N} w_n = 1$, and BP is the brevity penalty to penalize short machine translations.

where $c$ is the number of unigrams in the candidate sentence, and $r$ is the smallest number of unigrams in all reference sentences.


It is not hard to find that BLEU is always a value between 0 and 1. It is because BP, $w_n$, and $p_n$ are always between 0 and 1, and

Usually, BLEU uses $N = 4$ and $w_n = \frac{1}{N}$.

Example 1

We have computed the modified precision for some of the ngrams. It is not hard to compute the others. Concretely, we have

We plugin these values to the BLEU equation, the BLEU is

We further compare the BLEU to the BLEU computed using NLTK.

>>> import nltk
>>> reference_1 = "the cat is on the mat".split()
>>> reference_2 = "there is a cat on the mat".split()
>>> candidate = "the cat the cat on the mat".split()
>>> bleu = nltk.translate.bleu_score.sentence_bleu(references=[reference_1, reference_2], hypothesis=candidate, weights=(0.25,0.25,0.25,0.25))
>>> print(bleu)
0.4671379777282001

The value of bleu is 0.467 which is exactly matching to the BLEU we computed manually.

Example 2

Similarly,

When we plugin these values to the BLEU equation, actually we would need to compute $\log 0$ which is not mathematically defined. We use a small number $10^{-100}$ instead of $0$ for $p_2$, $p_3$ and $p_4$. The BLEU is

We further also compare the BLEU to the BLEU computed using NLTK.

>>> import nltk
>>> reference_1 = "the cat is on the mat".split()
>>> reference_2 = "there is a cat on the mat".split()
>>> candidate = "the the the the the the the the".split()
>>> bleu = nltk.translate.bleu_score.sentence_bleu(references=[reference_1, reference_2], hypothesis=candidate, weights=(0.25,0.25,0.25,0.25))
>>> print(bleu)
1.2882297539194154e-231

The value of bleu is 0 which is exactly matching to the BLEU we computed manually.

Caveats

In some scenarios, BLEU does not score the translation very well, especially for those short translations with few reference sentences. For example,


Chinese: 你准备好了吗?

Reference 1: are you ready ?

Candidate: you are ready ?

>>> import nltk
>>> reference_1 = "are you ready ?".split()
>>> candidate = "you are ready ?".split()
>>> bleu = nltk.translate.bleu_score.sentence_bleu(references=[reference_1], hypothesis=candidate, weights=[0.25,0.25,0.25,0.25])
>>> print(bleu)
1.133422688662942e-154

This is actually a very good machine translation to me. However, the BLEU score is 0, which means that the machine translation is totally wrong.


In NLTK, you are allowed to provide smoothing functions. For example,

>>> import nltk
>>> reference_1 = "are you ready ?".split()
>>> candidate = "you are ready ?".split()
>>> bleu = nltk.translate.bleu_score.sentence_bleu(references=[reference_1], hypothesis=candidate, weights=[0.25,0.25,0.25,0.25], smoothing_function=nltk.translate.bleu_score.SmoothingFunction().method7)
>>> print(bleu)
0.4002926439114545

This time, the value of bleu is 0.4, which is magically higher than the vanilla one we computed without using smoothing functions.


However, one should be always cautious about the smoothing function used in BLEU computation. At least we have to make sure that the BLEU scores we are comparing against are using no smoothing function or the exact same smoothing function.

References