BLEU Score

mediumPROMachine TranslationNLP 3: Advanced

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

Input

the cat sat on the mat
1
the cat is on the mat

Output

0.6687

Reasoning

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

Learn this in

Introduction to NLPNLP Study Plan Machine TranslationNLP Study Plan

More from NLP 3: Advanced

Temperature Samplereasy ROUGE-1 Score Calculatoreasy Context Window Findereasy Keyword Answer Extractoreasy Levenshtein Distanceeasy

Concept primerPREVIEW

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 \times \exp(0.5 \times \log(p1) + 0.5 \times \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

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results