前言

BLEU(bilingual evaluation understudy)算法是由IBM提出的用来自动评测机器翻译质量的算法。

N-gram

N-gram的N指连续的N个word用来匹配，即比较译文和参考译文之间N组词的相似占比。
例如：
  原文：今天天气不错
  机器译文：It is a nice day today
  人工译文：Today is a nice day
如果用1-gram匹配的话：

每1个word用来匹配，最终5个word匹配到了，所以最终1-gram的匹配度为 5/6
我们再以3-gram举例：

可以看到，原文可分为4个3-gram词组，其中2个命中参考译文，因此它3-gram的匹配度为 2/4

依次类推，我们可以很容易实现一个程序来遍历计算N-gram的一个匹配度。一般来说1-gram的结果代表了文中有多少个词被单独翻译出来了，因此它反映的是这篇译文的忠实度；而当我们计算2-gram以上时，更多时候结果反映的是译文的流畅度，值越高文章的可读性就越好。

召回率

上面所说的方法比较好理解，也比较好实现，但是没有考虑到召回率，举一个非常简单的例子说明：

原文：猫站在地上

机器译文：the the the the

人工译文：The cat is standing on the ground

在计算1-gram的时候，the 都出现在译文中，因此匹配度为4/4 ，但是很明显 the 在人工译文中最多出现的次数只有2次，因此BLEU算法修正了这个值的算法，首先会计算该n-gram在译文中可能出现的最大次数：

Count是N-gram在机器翻译译文中的出现次数，Max_Ref_Count是该N-gram在一个参考译文中最大的出现次数，最终统计结果取两者中的较小值。然后在把这个匹配结果除以机器翻译译文的N-gram个数。因此对于上面的例子来说，修正后的1-gram的统计结果就是2/4。

我们将整个要处理的将机器翻译的句子表示为Ci，标准答案表示为 Si=si1,…sim（m表示有m个参考答案）

n-grams表示n个单词长度的词组集合，令 W k W_k Wk​表示第k个n-gram

比如这样的一句话，”I come from china”，第1个2-gram为：I come; 第2个2-gram为：come from; 第3个2-gram为：from china;

h k ( c i ) h_k(c_i) hk​(ci​)表示 W k W_k Wk​在机器翻译句子Ci中出现的次数

h k ( s i j ) h_k(s_{ij}) hk​(sij​)表示 W k W_k Wk​在标准答案 S i j S_{ij} Sij​(第j个参考句子)中出现的次数

综上所述各阶N-gram的精度都可以按照下面这个公式计算：

m a x j ∈ m h k ( s i j ) max_{j∈m}h_k(s_{ij}) maxj∈m​hk​(sij​)表示某n-gram在多条标准答案中出现最多的次数
∑ i ∑ k m i n ( h k ( c i ) , m a x j ∈ m h k ( s i j ) \\sum_i\\sum_kmin(h_k(c_i),max_{j∈m}h_k(s_{ij}) ∑i​∑k​min(hk​(ci​),maxj∈m​hk​(sij​)表示取n-gram在翻译译文和标准答案中出现的最小次数

分子为所有n-gram的最小次数的和
分母为所有n-gram的和

短句惩罚因子

上面的算法已经足够可以有效的翻译评估了，然而N-gram的匹配度可能会随着句子长度的变短而变好，因此会存在这样一个问题：一个翻译引擎只翻译出了句子中部分句子且翻译的比较准确，那么它的匹配度依然会很高。为了避免这种评分的偏向性，BLEU在最后的评分结果中引入了长度惩罚因子(Brevity Penalty)。

BP的计算公式如上。 l c l_c lc​代表表示机器翻译译文的长度， l s l_s ls​表示参考答案的有效长度，当存在多个参考译文时，选取和翻译译文最接近的长度。当翻译译文长度大于参考译文的长度时，惩罚系数为1，意味着不惩罚，只有机器翻译译文长度小于参考答案才会计算惩罚因子。

BLEU

由于各N-gram统计量的精度随着阶数的升高而呈指数形式递减，所以为了平衡各阶统计量的作用，对其采用几何平均形式求平均值然后加权，再乘以长度惩罚因子，得到最后的评价公式：

BLEU的原型系统采用的是均匀加权，即 W n W_n Wn​=1/N 。N的上限取值为4，即最多只统计4-gram的精度。

实例

译文（Candidate）

Going to play basketball this afternoon ?

参考答案（Reference）

Going to play basketball in the afternoon ?

译文gram长度：7　　参考答案gram长度：8

先看1-gram，除了this这个单词没有命中，其他都命中了，因此：

 P1 = 6/7 = 0.85714…

其他gram以此类推：

 P2 = 4/6 = 0.6666…

 P3 = 2/5 = 0.4

 P4 = 1/4 = 0.25

再计算logPn，这里用python自带的：

∑logPn和为-2.8622 ；再乘以Wn，也就是除以4为 0.7156

B P = e ( 1 − 8 / 7 ) BP = e^{(1-8/7)} BP=e(1−8/7) 约等于 0.867

BLEU = 0.867 ∗ e ( ( P 1 + P 2 + P 3 + P 4 ) / 4 ) = 0.867 ∗ 0.4889 = 0.4238 0.867 * e^{((P1 + P2 + P3 + P4)/4)} = 0.867*0.4889 = 0.4238 0.867∗e((P1+P2+P3+P4)/4)=0.867∗0.4889=0.4238

代码

```python
\"\"\"
Description:
    BLEU
\"\"\"
import numpy as np
import re



def calculate_average(precisions, weights):
    \"\"\"Calculate the geometric weighted mean.\"\"\"
    tmp_res = 1
    for id, item in enumerate(precisions):
        tmp_res = tmp_res*np.power(item, weights[id])
    tmp_res = np.power(tmp_res, np.sum(weights))
    return tmp_res


def calculate_candidate(gram_list, candidate):
    \"\"\"Calculate the count of gram_list in candidate.\"\"\"
    gram_sub_str = \' \'.join(gram_list)
    return len(re.findall(gram_sub_str, candidate))


def calculate_reference(gram_list, references):
    \"\"\"Calculate the count of gram_list in references\"\"\"
    gram_sub_str = \' \'.join(gram_list)
    gram_count = []
    for item in references:
        # calculate the count of the sub string
        gram_count.append(len(re.findall(gram_sub_str, item)))
    return gram_count  # 返回列表，为每个 n-gram 在参考句子中数量


def sentence_bleu(candidate_sentence, reference_sentences, max_gram = 4, weights=(0.25, 0.25, 0.25, 0.25)):
    \"\"\"
    :param candidate_sentence:机翻句子
    :param reference_sentence:参考句子列表
    :param max_gram:计算至max_gram的N-gram，默认为 4
    :param weights:各N-gram的权重，默认为 (0.25, 0.25, 0.25, 0.25)
    :description: 此BLUE为改良的BLEU,采用了截断、加权平均及短句惩罚因子
    :return:精度
    \"\"\"
    candidate_corpus = list(candidate_sentence.split(\' \'))
    # number of the reference sentences
    refer_len = len(reference_sentences)
    candidate_tokens_len = len(candidate_corpus)
    # 首先需要计算各种长度的gram 的precision值

    # 计算当前gram 在candiate_sentence中出现的次数 同时计算这个gram 在所有的reference sentence中的出现的次数
    # 每一次计算时将当前candidate_sentence中当前gram出现次数与在当前reference sentence中出现的gram次数选择最小值
    # 作为这个gram相对于 参考文献j的截断次数
    # 然后将所有的参考文献对应的截断次数做最大值 作为这个gram在整个参考文献上的综合截断值 这个值就是当前gram对应的分子
    # 分母依然是这个gram 在candidate sentence中出现的次数
    # 在计算当前长度(n)的其他的gram的综合截断次数 然后加起来作为长度为n的gram的综合截断次数值 分母是所有长度为n的gram的相加的值
    # 两个值相除即可得到这个长度为n的gram 的precision值
    gram_precisions= []
    for i in range(max_gram):
        # calculate each gram precision
        # set current gram length
        curr_gram_len = i+1
        # calculate current gram length mole(分子)
        curr_gram_mole = 0
        # calculate current gram length deno(分母)
        curr_gram_deno = 0
        for j in range(0, candidate_tokens_len, curr_gram_len):
            if j + curr_gram_len > candidate_tokens_len:  # 判断是否是最后一个 n-gram
                continue
            else:  # curr_gram_list 为机翻的第j个 n-gram 列表
                curr_gram_list = candidate_corpus[j:j+curr_gram_len]
                gram_candidate_count = calculate_candidate(curr_gram_list, candidate_sentence)  #
                # print(\' current gram candidate count\')
                # print(gram_candidate_count)
                gram_reference_count_list = calculate_reference(curr_gram_list, reference_sentences)  # gram_reference_count_list 为计算 n-gram 在参考句子中数量的列表
                # print(\' current gram reference count list\')
                # print(gram_reference_count_list)
                truncation_list = []
                for item in gram_reference_count_list:
                    truncation_list.append(np.min([gram_candidate_count, item]))  # 在截断列表中添加该n-gram在机翻与各个参考句子中最小次数
                curr_gram_mole += np.max(truncation_list)  # 将该n-gram的截断count加入分子
                curr_gram_deno += gram_candidate_count  # 将该n-gram在机翻句子中数量加入分母
        print(\' current length %d and gram mole %d and deno %d\' % (i+1, curr_gram_mole, curr_gram_deno))
        gram_precisions.append(curr_gram_mole/curr_gram_deno)  # 将该阶n-gram的precisions加入列表gram_precisions
    # 此处得到的gram_precisions为 1 ~ N 的gram的 precision 的列表
    print(\'all the precisions about the grams\')
    print(gram_precisions)


    # 其次对多元组合(n-gram)的precision 进行加权取平均作为最终的bleu评估指标
    # 一般选择的做法是计算几何加权平均 exp(sum(w*logP))
    average_res = calculate_average(gram_precisions, weights)
    print(\' current average result\')
    print(average_res)

    # 最后引入短句惩罚项 避免短句翻译结果取得较高的bleu值, 影响到整体评估
    # 涉及到最佳的匹配长度 当翻译的句子的词数量与任意的参考翻译句子词数量一样的时候 此时无需惩罚项
    # 如果不相等 那么需要设置一个参考长度r 当翻译的句子长度(c) 大于 r 的时候不需要进行惩罚 而 当c小于r
    # 需要在加权平均值前乘以一个惩罚项exp(1-r/c) 作为最后的bleu 指标输出
    # r 的选择可以这样确定 当翻译句子长度等于任何一个参考句子长度时不进行惩罚 但是当都不等于参考句子长度时
    # 可以选择参考句子中最长的句子作为r 当翻译句子比r 长时不进行惩罚 小于r时进行惩罚
    bp = 1
    reference_len_list = [len(item.split(\' \')) for item in reference_sentences]
    if candidate_tokens_len in reference_len_list:
        bp = 1
    else:
        if candidate_tokens_len < np.max(reference_len_list):
            bp = np.exp(1-(np.max(reference_len_list)/candidate_tokens_len))
    return bp*average_res


if __name__ == \'__main__\':


    # full bleu test on references and candidate
    predict_sentence = \'Going to play basketball this afternoon\'
    train_sentences = [\'Going to play basketball in the afternoon\']
    bleu_score = sentence_bleu(predict_sentence, train_sentences, 4, weights=[0.25, 0.25, 0.25, 0.25])