Problems

1 / 1

BLEU Score

NLPMetrics & Evaluation

Hard

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:

p_n = \frac{\sum_{ng} \min(C_{ng},\; R_{ng})}{\sum_{ng} C_{ng}}

Compute the brevity penalty to penalize short translations:

BP = \begin{cases} 1 & \text{if } c \ge r \\ e^{1 - r/c} & \text{if } c < r \end{cases}

Combine into the BLEU score using the geometric mean of precisions:

\text{BLEU} = BP \cdot \exp\left(\frac{1}{N} \sum_{n=1}^{N} \log p_n\right)

If any precision is zero, BLEU is zero.

Loading visualization...

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

Try Similar Problems

Bag Of Words Tfidf Vectorizer Perplexity Computation Edit Distance Bigram Probabilities

Prev Next

BLEU Score

NLPMetrics & Evaluation

Hard

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:

p_n = \frac{\sum_{ng} \min(C_{ng},\; R_{ng})}{\sum_{ng} C_{ng}}

Compute the brevity penalty to penalize short translations:

BP = \begin{cases} 1 & \text{if } c \ge r \\ e^{1 - r/c} & \text{if } c < r \end{cases}

Combine into the BLEU score using the geometric mean of precisions:

\text{BLEU} = BP \cdot \exp\left(\frac{1}{N} \sum_{n=1}^{N} \log p_n\right)

If any precision is zero, BLEU is zero.

Loading visualization...

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

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

Try Similar Problems

Bag Of Words Tfidf Vectorizer Perplexity Computation Edit Distance Bigram Probabilities

Case 1

Case 2

candidate =

Accepts: array

reference =

Accepts: array

max_n =

Accepts: number

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:

p_n = \frac{\sum_{ng} \min(C_{ng},\; R_{ng})}{\sum_{ng} C_{ng}}

Compute the brevity penalty to penalize short translations:

BP = \begin{cases} 1 & \text{if } c \ge r \\ e^{1 - r/c} & \text{if } c < r \end{cases}

Combine into the BLEU score using the geometric mean of precisions:

\text{BLEU} = BP \cdot \exp\left(\frac{1}{N} \sum_{n=1}^{N} \log p_n\right)

If any precision is zero, BLEU is zero.