BLEU Score
BLEU Score
BLEU (Bilingual Evaluation Understudy) is the standard metric for evaluating machine translation quality. It measures how many n-grams in the candidate translation appear in the reference, with a penalty for translations that are too short.
Given a candidate translation, a reference translation (both as token lists), and a maximum n-gram order, compute the BLEU score.
Algorithm
- For each n-gram order from 1 to max_n, compute modified precision by clipping candidate n-gram counts by reference counts:
- Compute the brevity penalty to penalize short translations:
- Combine into the BLEU score using the geometric mean of precisions:
If any precision is zero, BLEU is zero.
Examples
Input:
candidate = ["the", "cat", "sat", "on", "the", "mat"], reference = ["the", "cat", "sat", "on", "the", "mat"], max_n = 4
Output:
1.0
A perfect translation match. All n-gram precisions are 1.0 and the lengths are equal (no brevity penalty).
Input:
candidate = ["the", "cat", "is", "here"], reference = ["the", "cat", "was", "here"], max_n = 2
Output:
0.5
Unigram precision: 3/4 (is does not match). Bigram precision: 1/3 (only "the cat" matches). Geometric mean: exp((log(0.75) + log(0.333)) / 2) = 0.5. No brevity penalty since lengths are equal.
Hint 1
For each n, extract all n-grams from candidate and reference using sliding windows. Use dictionaries to count occurrences. For each candidate n-gram, clip its count by the reference count using min(). Sum clipped counts and divide by total candidate n-grams.
Hint 2
Use tuple(candidate[i:i+n]) as dictionary keys for n-grams. After computing all precisions, check for zeros. Then compute BP = exp(min(0, 1 - r_len/c_len)) and BLEU = BP * exp(sum(log(p_n)) / max_n).
Requirements
- Compute modified n-gram precision for each order from 1 to max_n, clipping counts by the reference
- Apply the brevity penalty when the candidate is shorter than the reference
- Combine precisions using a uniform-weight geometric mean
- Return 0.0 if the candidate is empty or any precision is zero
- Return the BLEU score as a float
Constraints
- candidate and reference are lists of string tokens
- max_n >= 1
- Return a float between 0.0 and 1.0
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: number
BLEU Score
BLEU Score
BLEU (Bilingual Evaluation Understudy) is the standard metric for evaluating machine translation quality. It measures how many n-grams in the candidate translation appear in the reference, with a penalty for translations that are too short.
Given a candidate translation, a reference translation (both as token lists), and a maximum n-gram order, compute the BLEU score.
Algorithm
- For each n-gram order from 1 to max_n, compute modified precision by clipping candidate n-gram counts by reference counts:
- Compute the brevity penalty to penalize short translations:
- Combine into the BLEU score using the geometric mean of precisions:
If any precision is zero, BLEU is zero.
Examples
Input:
candidate = ["the", "cat", "sat", "on", "the", "mat"], reference = ["the", "cat", "sat", "on", "the", "mat"], max_n = 4
Output:
1.0
A perfect translation match. All n-gram precisions are 1.0 and the lengths are equal (no brevity penalty).
Input:
candidate = ["the", "cat", "is", "here"], reference = ["the", "cat", "was", "here"], max_n = 2
Output:
0.5
Unigram precision: 3/4 (is does not match). Bigram precision: 1/3 (only "the cat" matches). Geometric mean: exp((log(0.75) + log(0.333)) / 2) = 0.5. No brevity penalty since lengths are equal.
Hint 1
For each n, extract all n-grams from candidate and reference using sliding windows. Use dictionaries to count occurrences. For each candidate n-gram, clip its count by the reference count using min(). Sum clipped counts and divide by total candidate n-grams.
Hint 2
Use tuple(candidate[i:i+n]) as dictionary keys for n-grams. After computing all precisions, check for zeros. Then compute BP = exp(min(0, 1 - r_len/c_len)) and BLEU = BP * exp(sum(log(p_n)) / max_n).
Requirements
- Compute modified n-gram precision for each order from 1 to max_n, clipping counts by the reference
- Apply the brevity penalty when the candidate is shorter than the reference
- Combine precisions using a uniform-weight geometric mean
- Return 0.0 if the candidate is empty or any precision is zero
- Return the BLEU score as a float
Constraints
- candidate and reference are lists of string tokens
- max_n >= 1
- Return a float between 0.0 and 1.0
- Time limit: 300 ms
Log in to take notes on this problem
Accepts: array
Accepts: array
Accepts: number