BLEU Score

Score a candidate translation against a reference.

BLEU multiplies a brevity penalty by the geometric mean of clipped n-gram precisions, for n from 1 to max_n:

p_n = (clipped matches of n-grams) / (total candidate n-grams)
BLEU = BP * exp( (1/max_n) * sum_n log p_n )

Clipping is the part that makes it work. An n-gram in the candidate can only be counted as many times as it appears in the reference, so a candidate of ["the"] * 10 against a reference containing one "the" scores 1/10, not 10/10.

The brevity penalty stops the model gaming precision by emitting one very confident word:

BP = 1                        if len(candidate) > len(reference)
BP = exp(1 - len(ref) / len(cand))   otherwise

If any p_n is zero the geometric mean is zero, so return 0.0. Return 0.0 for an empty candidate too.

Both arguments are lists of tokens.

Function signature

def bleu(candidate, reference, max_n=4):

Example

Input

bleu(["the", "cat", "sat"], ["the", "cat", "sat"], max_n=2)

Output

1.0

Reasoning

The candidate is the same as the reference, so every unigram and bigram matches and p_1 = p_2 = 1. The lengths are equal, so BP = exp(1 - 3/3) = 1, and BLEU is 1.0.

Constraints and notes

• Clip each n-gram count to its count in the reference.
• Return 0.0 for an empty candidate, or when any p_n is 0.
• Both arguments are lists of tokens.