BLEU

Bilingual Evaluation Understudy

BLEU is a method of evaluating a trained NLP model for translation whether it can be a LSTM or a Transformer model as long as we have Candidates and References we can evaluate our model efficiency, Fluent-ness using BLEU.

Papers References :

So there are two terms :

Candidates : These are generated by the model
References : These are the actual translation from the corpus or by a human

Example :

Candidates
----------

Candidate 1 :
It is a guide to action which ensures that the military always obeys
the commands of the party

Candidate 2 :
It is to insure the troops forever hearing the activity guidebook
that party direct.

References 
----------

Reference 1 : 
It is a guide to action that ensures that the military will forever
heed Party commands.

Reference 2 : 
It is the guiding principle which guarantees the military forces
always being under the command of the Party.

Reference 3 : 
It is the practical guide for the army always to heed the directions
of the party.

Source : https://aclanthology.org/P02-1040.pdf

BLEU gives us the way of evaluating on the n-gram basis by comparing the Candidates with the References. In order to compare we basically select the tokens in Candidates which appear in the references and get the score, So for the above example we will get something like :

For Candidate 1 :

Candidate 1 : It is a guide to action which ensures that the military always obeys the commands of the party

Reference 1 : It is a guide to action that ensures that the military will forever heed Party commands.

Reference 2 : It is the guiding principle which guarantees the military forces always being under the command of the party.

Reference 3 : It is the practical guide for the army always to heed the directions of the party.

As we can here that Candidate 1 has refs to all three references but I feel that Candidate 2 is a better translation If I were provided with a choice. Now we can calculate the scores like this in a unigram, bigram .... n-gram way and check which candidate scores the best. But there is a problem in this method which can be shown using an example given in the BLEU paper :

Candidate : 
the the the the the

Reference 1 : 
The cat is on the mat

Reference 2 : 
There is a cat on the mat

If we were to do a unigram scoring the Candidate scores a perfect score of 1.0 (explanation below) :

Candidate : the the the the the

Reference 1 : the cat is on the mat

Reference 2 : There is a cat on the mat

Go word by word (unigram) in the Candidate and then ask if the word 
is in any of the references 

For our candidate all the words are present in both of the references 
Therefore 

Candidate w.r.t Reference 1 --> 5 / 5
Candidate w.r.t Reference 2 --> 5 / 5

Now we can see the problem that any model can cheat by providing repeated generation of tokens at least for the unigram scoring. This would lead to a worse model score better and translations might be all wrong or incomprehensible. Now we need to write an algorithm to do BLEU for us. To tackle this we have a simple solution which is to clip the count of the token in candidate to the maximum count of occurence of that token in the References. So our Count formula becomes :

\text{Count}_{\text{clip}}(\text{token}) = \text{min}(\text{occurrences in candidate}, \text{maximum in any reference})

So for the example above we get the score of $\frac{2}{5}$ down from a perfect score of $1$ . That's progress right ?? There is one problem we solved the overgeneration of tokens but undergeneration of tokens is not solved (we will look into it after precision calculation). Undergeneration of tokens can game the score too, If the Candidate was just the token "the" then we would get a perfect score of $1$ again which is not ideal.

Precision Calculation

We can calculate the $\mathrm{precision} = \frac{\mathrm{matches}}{\text{candidate length}}$ and to do this for all the Candidates is not optimal and the corpus precision will not be correct. So we aggregate over the candidate corpus $\mathcal C$ , where $G_n(C)$ is the set of n-grams in candidate $C$ .

p_n = \frac{ \sum_{C \in \mathcal C} \sum_{g \in G_n(C)} \operatorname{Count}_{\mathrm{clip}}(g) }{ \sum_{C \in \mathcal C} \sum_{g \in G_n(C)} \operatorname{Count}(g) }

This is the precision for n-gram. In practice if we want to combine different n-gram precissions we will be using weighted average of the corpus precisions. Now let's look into the problem of undergeneration of tokens by taking length into account. Now the most general way to do this is by using recall.

\mathrm{Recall} = \frac{\text{matches}}{\text{reference length}}

Suppose:

Candidate: the cat
Reference: the cat is on the mat (6 tokens)

Unigram matches: 
the and cat both appear in the reference, so 2 matches.

Precision = 2/2 = 1.0, everything the candidate said was correct.
Recall = 2/6 ≈ 0.33, but it captured only a third of what the reference contained

The issue is that we have multiple references.

Sentence Brevity Penalty

In paper Brevity Penalty (BP) factor is introduced so that a high scoring candidate translation must now match reference translation length (also in word choice and word order). BP should be $1.0$ when candidate length is same as any of the references (this is called as best match length). BP is calculated over the whole test corpus.

Procedure

Compute the test corpus' effective reference length, $r$ . We choose the best match length for each candidate and sum them to givbe $r$ .
BP is to be decaying exponentialy in $\frac{r}{c}$ , where $c$ is total length of the candidate translation corpus.

Formula :

\text{BP} = \begin{cases} 1 & \text{if } c > r \\ \exp\!\left(1 - \dfrac{r}{c}\right) & \text{if } c \le r \end{cases}

\boxed{\; \text{BLEU} = \text{BP} \cdot \exp\!\left( \sum_{n=1}^{N} w_n \log p_n \right) \;}

sacreBLEU

It consumes detokenized model output and applies one standard tokenization internally, so every model's scores are computed the same way and are actually comparable.
It manages the standard test sets so users stop accidentally using different or re-processed reference files.
It emits a version signature a kind of string encoding every parameter that affects the score:
- tokenizer version
- case sensitivity
- number of references
- smoothing method
- tool version. Something like BLEU+case.mixed+numrefs.1+smooth.exp+tok.13a+version.x.x.x. One reports that signature next to the number and now score is reproducible and unambiguously comparable to anyone else who reports the same signature.

Extra Stuff

After reading the BLEU paper I got a thought that maybe we can use BLEU to RL our pre trained translation model to the most correct candidates to improve our translation quality. Then I found out there is already a paper released 10 years ago : )

Ranzato et al., "Sequence Level Training with Recurrent Neural Networks" (2016)

We can use this concept to even make a SOTA translation model. Of course corpus and RL environments do matter.