BLEU

A basic, first attempt at defining the BLEU score would take two arguments: a candidate string ${\displaystyle {\hat {y}}}$ and a list of reference strings ${\displaystyle (y^{(1)},...,y^{(N)})}$. The idea is that ${\displaystyle BLEU({\hat {y}};y^{(1)},...,y^{(N)})}$ should be close to 1 when ${\displaystyle {\hat {y}}}$ is similar to ${\displaystyle y^{(1)},...,y^{(N)}}$, 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 ${\displaystyle {\hat {y}}}$ by checking how closely it follows the reference answers ${\displaystyle y^{(1)},...,y^{(N)}}$.

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") ${\displaystyle ({\hat {y}}^{(1)},\cdots ,{\hat {y}}^{(M)})}$, and for each candidate string ${\displaystyle {\hat {y}}^{(i)}}$, a list of reference candidate strings ${\displaystyle S_{i}:=(y^{(i,1)},...,y^{(i,N_{i})})}$.

Given any string ${\displaystyle y=y_{1}y_{2}\cdots y_{K}}$, and any integer ${\displaystyle n\geq 1}$, we define the set of its n-grams to be

$${\displaystyle G_{n}(y)=\{y_{1}\cdots y_{n},y_{2}\cdots y_{n+1},\cdots ,y_{K-n+1}\cdots y_{K}\}}$$

Note that it is a set of unique elements, not a multiset allowing redundant elements, so that, for example, ${\displaystyle G_{2}(abab)=\{ab,ba\}}$.

Given any two strings ${\displaystyle s,y}$, define the substring count ${\displaystyle C(s,y)}$ to be the number of appearances of ${\displaystyle s}$ as a substring of ${\displaystyle y}$. For example, ${\displaystyle C(ab,abcbab)=2}$.

Now, fix a candidate corpus ${\displaystyle {\hat {S}}:=({\hat {y}}^{(1)},\cdots ,{\hat {y}}^{(M)})}$, and reference candidate corpus ${\displaystyle S=(S_{1},\cdots ,S_{M})}$, where each ${\displaystyle S_{i}:=(y^{(i,1)},...,y^{(i,N_{i})})}$.

Define the modified n-gram precision function to be

$${\displaystyle p_{n}({\hat {S}};S):={\frac {\sum _{i=1}^{M}\sum _{s\in G_{n}({\hat {y}}^{(i)})}\min(C(s,{\hat {y}}^{(i)}),\max _{y\in S_{i}}C(s,y))}{\sum _{i=1}^{M}\sum _{s\in G_{n}({\hat {y}}^{(i)})}C(s,{\hat {y}}^{(i)})}}}$$

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

$${\displaystyle p_{n}(\{{\hat {y}}\};\{y\})={\frac {\sum _{s\in G_{n}({\hat {y}})}\min(C(s,{\hat {y}}),C(s,y))}{\sum _{s\in G_{n}({\hat {y}})}C(s,{\hat {y}})}}}$$

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

$${\displaystyle \sum _{s\in G_{n}({\hat {y}})}C(s,y)={\text{number of n-substrings in }}{\hat {y}}{\text{ that appear in }}y}$$

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 ${\displaystyle {\hat {y}}=aba,y=abababa,n=2}$, all the 2-substrings in ${\displaystyle {\hat {y}}}$ (ab and ba) appear in ${\displaystyle y}$ 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 ${\displaystyle ab}$ it contains only one, so we add a minimum function to correct for that:

$${\displaystyle {\sum _{s\in G_{n}({\hat {y}})}\min(C(s,{\hat {y}}),C(s,y))}}$$

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

$${\displaystyle {\frac {\sum _{s\in G_{n}({\hat {y}})}\min(C(s,{\hat {y}}),C(s,y))}{\sum _{s\in G_{n}({\hat {y}})}C(s,{\hat {y}})}}}$$

The normalization is such that it is always a number in ${\displaystyle [0,1]}$, 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.

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

$${\displaystyle BP({\hat {S}};S):=e^{-(r/c-1)^{+}}}$$

where ${\displaystyle (r/c-1)^{+}=\max(0,r/c-1)}$ is the positive part of ${\displaystyle r/c-1}$.

• When ${\displaystyle r\leq c}$, the brevity penalty ${\displaystyle BP=1}$, meaning that we don't punish long candidates, and only punish short candidates.
• When ${\displaystyle r>c}$, the brevity penalty ${\displaystyle BP=e^{1-r/c}}$

${\displaystyle c}$ is the length of the candidate corpus, that is,

$${\displaystyle c:=\sum _{i=1}^{M}|{\hat {y}}^{(i)}|}$$

where ${\displaystyle |y|}$ is the length of ${\displaystyle y}$. ${\displaystyle r}$ is the effective reference corpus length, that is,

$${\displaystyle r:=\sum _{i=1}^{M}|y^{(i,j)}|}$$

where ${\displaystyle y^{(i,j)}=\arg \min _{y\in S_{i}}||y|-|{\hat {y}}^{(i)}||}$, that is, the sentence from ${\displaystyle S_{i}}$ whose length is as close to ${\displaystyle |{\hat {y}}^{(i)}|}$ as possible.

There is not a single definition of BLEU, but a whole family of them, parametrized by the weighting vector ${\displaystyle w:=(w_{1},w_{2},\cdots )}$. It is a probability distribution on ${\displaystyle \{1,2,3,\cdots \}}$, that is, ${\displaystyle \sum _{i=1}^{\infty }w_{i}=1}$, and ${\displaystyle \forall i\in \{1,2,3,\cdots \},w_{i}\in [0,1]}$.

With a choice of ${\displaystyle w}$, the BLEU score is

$${\displaystyle BLEU_{w}({\hat {S}};S):=BP({\hat {S}};S)\cdot \exp \left(\sum _{n=1}^{\infty }w_{n}\ln p_{n}({\hat {S}};S)\right)}$$

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 ${\displaystyle w_{1}=\cdots =w_{4}={\frac {1}{4}}}$.[2]