BLEU

The problem, from first principles

When the answer is a whole sentence rather than a short span, string equality is hopeless and we measure overlap instead. BLEU asks how many of the n-grams (runs of n consecutive words) in the candidate also appear in the reference. Counting matches naively is exploitable: a candidate that repeats "the the the the" matches the word "the" every time. So each candidate n-gram is credited at most as often as it appears in the reference (clipping). Precision alone also rewards very short outputs, so a brevity penalty reduces the score of candidates shorter than the reference. The final score is the geometric mean of the precisions for n = 1 to 4 times that penalty.

From theory to code

Implement modified_precision and bleu.

Constraints

• Candidates and references are lists of tokens. references is a list of reference token lists.
• modified_precision(candidate, references, n) is the number of candidate n-grams after clipping divided by the number of candidate n-grams. Clipping credits each n-gram at most max over references of its count in that reference times. Return 0.0 if the candidate has no n-grams of that order.
• bleu(candidate, references, max_n=4) is BP * exp(mean(log p_n)) for n = 1..max_n, and 0.0 if any p_n is zero (no smoothing). BP = 1 if c > r else exp(1 - r / c) where c is the candidate length and r is the length of the reference closest in length to c (the shorter one on ties).
• Return Python floats.

Hints