Repository: nltk/nltk
Pull request: Added multi Bleu functionality and tests
Feature as per #2320

from bleu_score import corpus_bleu

```
references = [[['this', 'is', 'a', 'test'], ['this', 'is' 'test']]]
candidates = [['this', 'is', 'a', 'test']]
print('Individual 1-gram: %f' % corpus_bleu(references, candidates, weights=(1, 0, 0, 0)))
print('Individual 2-gram: %f' % corpus_bleu(references, candidates, weights=(0, 1, 0, 0)))
```
```
Individual 1-gram: 1.000000
Individual 2-gram: 1.000000
```



Problem statement:
One-shot BLEU-[2, 3, 4] computation
Hello everyone,

I need to compute the BLEU score with more than one ngram length (ideally, BLEU2, BLEU3, BLEU4, and BLEU5). In my case, this is a very long task, as every hypothesis has some thousand references.

Reading the implementation of the corpus_bleu function, which takes weights:Tuple between its parameters - and thus calculating BLEU-[len(weights)] - , I found out that it gets all the information to compute BLEU-m s.t. 2 <= m < len(weights).
Wouldn't it be nice to have a more general function that can compute BLEU with different ngram lengths at the same time? A possible implementation would be the weights parameter accepting a list of weight tuples as value, computing precisions that are useful for the longest tuple and using those precisions to get all the desired BLEU scores using the weights list.

This would result in a more general implementation and it would avoid the computation waste of calculating the same values more than one time.

Hints from issue discussion:
This would be nice to have... it's a question of who would like to implement it.
Hi, I was looking at getting involved with contributing to NLTK and saw this with the 'goodfirstbug' tag. I will take a crack at this problem if that is OK.
Feel free to take a look at https://github.com/nltk/nltk/blob/develop/CONTRIBUTING.md and create a pull-request and someone will review it before merging.
Hi @stevenbird @alvations if its currently open can I get involved with it??
@BatMrE Yes, you may. We welcome contributions!
Feel free to look at [CONTRIBUTING.md](https://github.com/nltk/nltk/blob/develop/CONTRIBUTING.md) for more information.
@ tomaarsen @alvations 
From the issue raised statement:
`Wouldn't it be nice to have a more general function that can compute BLEU with different ngram lengths at the same time? `


I will ultimately be calling the Bleu funnction for each of the  2 , 3 ,4 ... len(weights) , so how will it be saving computation waste of calculating the same values more than one time??
@BatMrE 
`corpus_bleu` (and also `sentence_bleu`) are called with a `weights` parameter. This is a list or tuple of floats with a certain length, such that the weights generally sum to 1. The length of this list or tuple determines whether BLEU-2, BLEU-3, BLEU-4, etc. is used. For example, with a length of 2, BLEU-2 is used. 

For each BLEU-k, the computation has to compute all k-grams, all k-1-grams, k-2-grams, ..., 2-grams, 1-grams. This can be noticed in the following section of the corpus_bleu algorithm:
https://github.com/nltk/nltk/blob/f989fe65d421e7ea4d1037a00f07eaeee3ad6a29/nltk/translate/bleu_score.py#L174-L179

In short, calculating BLEU-4 requires going over all 4-grams, 3-grams, 2-grams and 1-grams. If we then also want to compute BLEU-3, then `corpus_bleu` (or  `sentence_bleu`) is called again, which recomputes the 3-grams, 2-grams and 1-grams. The idea is that BLEU-3 could also be computed in the original call for BLEU-4.

There's a few options to implement this. One option is to always compute the lower ngram order BLEU's and cache them, so if they are requested, no recomputation is needed. However, this would increase the overhead a lot when a user isn't interested in the lower order ngram BLEU's. 

Another option is to add a boolean parameter to `corpus_bleu` and `sentence_bleu` - if this parameter is True, then a dictionary (or tuple, perhaps?) of the BLEU scores is returned. 

Something to think about:
Say BLEU-4 is being computed with weights (0.3, 0.3, 0.3, 0.1), which weights should be used to compute BLEU-3? Simply a reweighed version of `weights[:3]`? Or should the user supply multiple weights?
If so, this should be known from the function documentation.

Or should the user be able to optionally supply a list of weights? In the event that this occurs, multiple BLEU scores will be computed, one for each of the weights. Perhaps it would then still be possible to reuse computation of ngrams.

- Tom Aarsen

Commit message: Added multi Bleu functionality and tests

Patch to review:
diff --git a/nltk/test/bleu.doctest b/nltk/test/bleu.doctest
index a116dcb613..4ea6b8ac9c 100644
--- a/nltk/test/bleu.doctest
+++ b/nltk/test/bleu.doctest
@@ -9,7 +9,7 @@ If the candidate has no alignment to any of the references, the BLEU score is 0.
 >>> bleu(
 ...     ['The candidate has no alignment to any of the references'.split()],
 ...     'John loves Mary'.split(),
-...     [1],
+...     (1,),
 ... )
 0
 
diff --git a/nltk/test/unit/translate/test_bleu.py b/nltk/test/unit/translate/test_bleu.py
index 0a1811f031..ccabcc89ed 100644
--- a/nltk/test/unit/translate/test_bleu.py
+++ b/nltk/test/unit/translate/test_bleu.py
@@ -120,7 +120,7 @@ def test_zero_matches(self):
 
         # Test BLEU to nth order of n-grams, where n is len(hypothesis).
         for n in range(1, len(hypothesis)):
-            weights = [1.0 / n] * n  # Uniform weights.
+            weights = (1.0 / n,) * n  # Uniform weights.
             assert sentence_bleu(references, hypothesis, weights) == 0
 
     def test_full_matches(self):
@@ -130,7 +130,7 @@ def test_full_matches(self):
 
         # Test BLEU to nth order of n-grams, where n is len(hypothesis).
         for n in range(1, len(hypothesis)):
-            weights = [1.0 / n] * n  # Uniform weights.
+            weights = (1.0 / n,) * n  # Uniform weights.
             assert sentence_bleu(references, hypothesis, weights) == 1.0
 
     def test_partial_matches_hypothesis_longer_than_reference(self):
@@ -153,7 +153,7 @@ def test_case_where_n_is_bigger_than_hypothesis_length(self):
         references = ["John loves Mary ?".split()]
         hypothesis = "John loves Mary".split()
         n = len(hypothesis) + 1  #
-        weights = [1.0 / n] * n  # Uniform weights.
+        weights = (1.0 / n,) * n  # Uniform weights.
         # Since no n-grams matches were found the result should be zero
         # exp(w_1 * 1 * w_2 * 1 * w_3 * 1 * w_4 * -inf) = 0
         self.assertAlmostEqual(
@@ -269,3 +269,127 @@ def test_corpus_bleu_with_bad_sentence(self):
                 )
         except AttributeError:  # unittest.TestCase.assertWarns is only supported in Python >= 3.2.
             self.assertAlmostEqual(corpus_bleu(references, hypotheses), 0.0, places=4)
+
+
+class TestBLEUWithMultipleWeights(unittest.TestCase):
+    def test_corpus_bleu_with_multiple_weights(self):
+        hyp1 = [
+            "It",
+            "is",
+            "a",
+            "guide",
+            "to",
+            "action",
+            "which",
+            "ensures",
+            "that",
+            "the",
+            "military",
+            "always",
+            "obeys",
+            "the",
+            "commands",
+            "of",
+            "the",
+            "party",
+        ]
+        ref1a = [
+            "It",
+            "is",
+            "a",
+            "guide",
+            "to",
+            "action",
+            "that",
+            "ensures",
+            "that",
+            "the",
+            "military",
+            "will",
+            "forever",
+            "heed",
+            "Party",
+            "commands",
+        ]
+        ref1b = [
+            "It",
+            "is",
+            "the",
+            "guiding",
+            "principle",
+            "which",
+            "guarantees",
+            "the",
+            "military",
+            "forces",
+            "always",
+            "being",
+            "under",
+            "the",
+            "command",
+            "of",
+            "the",
+            "Party",
+        ]
+        ref1c = [
+            "It",
+            "is",
+            "the",
+            "practical",
+            "guide",
+            "for",
+            "the",
+            "army",
+            "always",
+            "to",
+            "heed",
+            "the",
+            "directions",
+            "of",
+            "the",
+            "party",
+        ]
+        hyp2 = [
+            "he",
+            "read",
+            "the",
+            "book",
+            "because",
+            "he",
+            "was",
+            "interested",
+            "in",
+            "world",
+            "history",
+        ]
+        ref2a = [
+            "he",
+            "was",
+            "interested",
+            "in",
+            "world",
+            "history",
+            "because",
+            "he",
+            "read",
+            "the",
+            "book",
+        ]
+        weight_1 = (1, 0, 0, 0)
+        weight_2 = (0.25, 0.25, 0.25, 0.25)
+        weight_3 = (0, 0, 0, 0, 1)
+
+        bleu_scores = corpus_bleu(
+            list_of_references=[[ref1a, ref1b, ref1c], [ref2a]],
+            hypotheses=[hyp1, hyp2],
+            weights=[weight_1, weight_2, weight_3],
+        )
+        assert bleu_scores[0] == corpus_bleu(
+            [[ref1a, ref1b, ref1c], [ref2a]], [hyp1, hyp2], weight_1
+        )
+        assert bleu_scores[1] == corpus_bleu(
+            [[ref1a, ref1b, ref1c], [ref2a]], [hyp1, hyp2], weight_2
+        )
+        assert bleu_scores[2] == corpus_bleu(
+            [[ref1a, ref1b, ref1c], [ref2a]], [hyp1, hyp2], weight_3
+        )
diff --git a/nltk/translate/bleu_score.py b/nltk/translate/bleu_score.py
index 654609847d..d4bc387054 100644
--- a/nltk/translate/bleu_score.py
+++ b/nltk/translate/bleu_score.py
@@ -150,8 +150,8 @@ def corpus_bleu(
     :type list_of_references: list(list(list(str)))
     :param hypotheses: a list of hypothesis sentences
     :type hypotheses: list(list(str))
-    :param weights: weights for unigrams, bigrams, trigrams and so on
-    :type weights: list(float)
+    :param weights: weights for unigrams, bigrams, trigrams and so on, (one or list of weights)
+    :type weights: tuple(float) or list(tuple(float))
     :param smoothing_function:
     :type smoothing_function: SmoothingFunction
     :param auto_reweigh: Option to re-normalize the weights uniformly.
@@ -169,11 +169,15 @@ def corpus_bleu(
         "The number of hypotheses and their reference(s) should be the " "same "
     )
 
+    if isinstance(weights, tuple):
+        weights = [weights]
+    max_weight_length = max(len(weight) for weight in weights)
+
     # Iterate through each hypothesis and their corresponding references.
     for references, hypothesis in zip(list_of_references, hypotheses):
         # For each order of ngram, calculate the numerator and
         # denominator for the corpus-level modified precision.
-        for i, _ in enumerate(weights, start=1):
+        for i in range(1, max_weight_length + 1):
             p_i = modified_precision(references, hypothesis, i)
             p_numerators[i] += p_i.numerator
             p_denominators[i] += p_i.denominator
@@ -187,23 +191,23 @@ def corpus_bleu(
     # Calculate corpus-level brevity penalty.
     bp = brevity_penalty(ref_lengths, hyp_lengths)
 
-    # Uniformly re-weighting based on maximum hypothesis lengths if largest
-    # order of n-grams < 4 and weights is set at default.
-    if auto_reweigh:
-        if hyp_lengths < 4 and weights == (0.25, 0.25, 0.25, 0.25):
-            weights = (1 / hyp_lengths,) * hyp_lengths
+    # # Uniformly re-weighting based on maximum hypothesis lengths if largest
+    # # order of n-grams < 4 and weights is set at default.
+    # if auto_reweigh:
+    #     if hyp_lengths < 4 and weights == (0.25, 0.25, 0.25, 0.25):
+    #         weights = (1 / hyp_lengths,) * hyp_lengths
 
     # Collects the various precision values for the different ngram orders.
     p_n = [
         Fraction(p_numerators[i], p_denominators[i], _normalize=False)
-        for i, _ in enumerate(weights, start=1)
+        for i in range(1, max_weight_length + 1)
     ]
 
     # Returns 0 if there's no matching n-grams
     # We only need to check for p_numerators[1] == 0, since if there's
     # no unigrams, there won't be any higher order ngrams.
     if p_numerators[1] == 0:
-        return 0
+        return 0 if len(weights) == 1 else [0] * len(weights)
 
     # If there's no smoothing, set use method0 from SmoothinFunction class.
     if not smoothing_function:
@@ -215,9 +219,19 @@ def corpus_bleu(
     p_n = smoothing_function(
         p_n, references=references, hypothesis=hypothesis, hyp_len=hyp_lengths
     )
-    s = (w_i * math.log(p_i) for w_i, p_i in zip(weights, p_n))
-    s = bp * math.exp(math.fsum(s))
-    return s
+
+    bleu_scores = []
+    for weight in weights:
+        # Uniformly re-weighting based on maximum hypothesis lengths if largest
+        # order of n-grams < 4 and weights is set at default.
+        if auto_reweigh:
+            if hyp_lengths < 4 and weight == (0.25, 0.25, 0.25, 0.25):
+                weight = (1 / hyp_lengths,) * hyp_lengths
+
+        s = (w_i * math.log(p_i) for w_i, p_i in zip(weight, p_n))
+        s = bp * math.exp(math.fsum(s))
+        bleu_scores.append(s)
+    return bleu_scores[0] if len(weights) == 1 else bleu_scores
 
 
 def modified_precision(references, hypothesis, n):


Code review comments:
diff_hunk: @@ -150,8 +150,8 @@ def corpus_bleu(
     :type list_of_references: list(list(list(str)))
     :param hypotheses: a list of hypothesis sentences
     :type hypotheses: list(list(str))
-    :param weights: weights for unigrams, bigrams, trigrams and so on
-    :type weights: list(float)
+    :param weights: weights for unigrams, bigrams, trigrams and so on, (one or list of weights)
+    :type weights: tuple(float) or list(tuple(float))
path: nltk/translate/bleu_score.py
text: @user1:
```suggestion
    :type weights: tuple(float) / list(tuple(float))
```
I believe the proper way (In Sphinx default documentation) to specify that a parameter may be one of multiple types is using a `/`. Perhaps in the future we can rework all of this using the Python 3.5+ type hinting, or the Python 3 `typing`'s `Union[Tuple[float], List[Tuple[float]]` - but this is something for later, for the entire codebase (or large sections) at once.

Also see https://github.com/nltk/nltk/blob/f989fe65d421e7ea4d1037a00f07eaeee3ad6a29/nltk/translate/chrf_score.py#L77 for an example of this.

@user1:
Fixed in c730dc3. I'm open to suggestions or changes.

diff_hunk: @@ -169,11 +169,15 @@ def corpus_bleu(
         "The number of hypotheses and their reference(s) should be the " "same "
     )
 
+    if isinstance(weights, tuple):
+        weights = [weights]
path: nltk/translate/bleu_score.py
text: @user1:
This is a little bit dangerous. People might be using `list` weights right now, and that would stop working. Perhaps a safer solution is to check `if weights and isinstance(weights[0], float):`?

Currently, the following program will break:
```python
from nltk.translate.bleu_score import corpus_bleu
# define ref's and hyp's here, left out for conciseness.
weights = [0.2, 0.8]
bleu_scores = corpus_bleu(
    list_of_references=[[ref1a, ref1b, ref1c], [ref2a]],
    hypotheses=[hyp1, hyp2],
    weights=weights,
)
```
Throws the following exception:
```python
Traceback (most recent call last):
  File "[...]\nltk_2793.py", line 110, in <module>
    out = bleu_scores = corpus_bleu(
  File "[...]\nltk\translate\bleu_score.py", line 174, in corpus_bleu
    max_weight_length = max(len(weight) for weight in weights)
  File "[...]\nltk\translate\bleu_score.py", line 174, in <genexpr>  
    max_weight_length = max(len(weight) for weight in weights)
TypeError: object of type 'float' has no len()
```

This didn't break before. People will expect that something that worked before to still work later.

@user1:
@author I think the functionality of using weights like `[0.2, 0.8]` like in my example above should still be supported. I would rather not merge this PR until that is resolved.

diff_hunk: @@ -187,23 +191,23 @@ def corpus_bleu(
     # Calculate corpus-level brevity penalty.
     bp = brevity_penalty(ref_lengths, hyp_lengths)
 
-    # Uniformly re-weighting based on maximum hypothesis lengths if largest
-    # order of n-grams < 4 and weights is set at default.
-    if auto_reweigh:
-        if hyp_lengths < 4 and weights == (0.25, 0.25, 0.25, 0.25):
-            weights = (1 / hyp_lengths,) * hyp_lengths
+    # # Uniformly re-weighting based on maximum hypothesis lengths if largest
+    # # order of n-grams < 4 and weights is set at default.
+    # if auto_reweigh:
+    #     if hyp_lengths < 4 and weights == (0.25, 0.25, 0.25, 0.25):
+    #         weights = (1 / hyp_lengths,) * hyp_lengths
path: nltk/translate/bleu_score.py
text: @user1:
Commented code is dead code, you can just remove it.

@user1:
Fixed in c730dc3. I'm open to suggestions or changes.