BLEU Score
Implement the BLEU score calculation for machine translation evaluation.
BLEU measures the overlap of n-grams between a candidate translation and reference translations.
Simplified BLEU (up to bigrams):
- Compute modified precision for unigrams and bigrams
- Modified precision clips each n-gram count to the max count in any reference
- Compute brevity penalty: BP = exp(1 - ref_len/cand_len) if cand_len < ref_len, else 1
- BLEU = BP * exp(0.5 * log(p1) + 0.5 * log(p2))
Where p1 = clipped unigram matches / candidate unigrams, p2 = clipped bigram matches / candidate bigrams.
Input format:
- Line 1: Candidate translation (space-separated words)
- Line 2: Number of references R
- Lines 3 to R+2: Reference translations
Output: BLEU score rounded to 4 decimal places. If any precision is 0, output 0.0.
Example:
the cat sat on the mat 1 the cat is on the mat
0.6687
Candidate: the cat sat on the mat (6 words) Reference: the cat is on the mat (6 words)
Unigram precision: Candidate unigrams: the(2), cat(1), sat(1), on(1), mat(1) Clipped by ref: the(2), cat(1), sat(0), on(1), mat(1) => 5/6
Bigram precision: Candidate bigrams: (the,cat)(1), (cat,sat)(1), (sat,on)(1), (on,the)(1), (the,mat)(1) Ref bigrams: (the,cat)(1), (cat,is)(1), (is,on)(1), (on,the)(1), (the,mat)(1) Matches: (the,cat), (on,the), (the,mat) => 3/5
Brevity penalty: len(cand)=6 = len(ref)=6, so BP = 1.0
BLEU: 1.0 * exp(0.5log(5/6) + 0.5log(3/5)) = exp(0.5*(-0.1823) + 0.5*(-0.5108)) = exp(-0.3466) = 0.7072...
The exact value depends on the implementation details.
Constraints:
- Use uniform weights (0.5, 0.5) for unigrams and bigrams
- Clip n-gram counts to max reference count
- Use the closest reference length for brevity penalty
- If candidate has fewer than 2 words (no bigrams possible), output 0.0
Background Knowledge
The BLEU score is a widely used metric in Natural Language Processing (NLP) to evaluate the quality of machine translation systems. It measures the similarity between a candidate translation and one or more reference translations. The score is based on the concept of n-grams, which are sequences of n items (in this case, words) in a sentence. For example, the sentence "the cat sat" can be broken down into unigrams (individual words: "the", "cat", "sat") and bigrams (sequences of two words: "the cat", "cat sat").
The BLEU score calculation involves computing the modified precision for each type of n-gram (unigrams and bigrams in this simplified version). This means counting the number of n-grams in the candidate translation that also appear in the reference translations, and then clipping this count to the maximum count in any reference translation. This ensures that the candidate translation is not penalized for having more occurrences of an n-gram than the reference translations. The brevity penalty is also applied to penalize candidate translations that are shorter than the reference translations.
In Machine Translation, the BLEU score is used to evaluate the quality of a translation system by comparing its output to one or more reference translations. A higher BLEU score indicates a better translation. The score is calculated using the formula: BLEU=BP×exp(0.5×log(p1)+0.5×log(p2)), where p1 and p2 are the modified precisions for unigrams and bigrams, respectively, and BP is the brevity penalty.
Algorithm/Approach
The general approach to solving this problem involves the following steps:
- Tokenize the candidate and reference translations into individual words and n-grams
- Compute the modified precision for each type of n-gram
- Calculate the brevity penalty
- Use these values to compute the BLEU score
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.