[paper note]代码生成评估模型-CodeBLEU原理分析

在这里插入图片描述

论文信息

论文标题：CodeBLEU: a Method for Automatic Evaluation of Code Synthesis

发表时间：2020年9月

论文原文：CodeBLEU: a Method for Automatic Evaluation of Code Synthesis

论文内容

摘要

评价指标对一个领域的发展起着至关重要的作用，因为它定义了区分模型好坏的标准。在代码综合领域，常用的评估指标是 BLEU 或精确匹配，但它们是不太适合评估代码能力，因为BLEU最初是为了评估自然语言而设计的，忽略了代码的重要语法和语义；而精确匹配因太过严格，导致低估具有相同的语义逻辑的不同输出。为了解决这个问题，我们引入了一个新的自动评估指标，称为CodeBLEU。它吸收了BLEU在n-gram匹配中的优势，并进一步通过抽象语法树（AST）引入代码语法，通过数据流引入代码语义。我们通过评估CodeBLEU与程序员在三个代码合成任务（即文本生成码、代码翻译和代码优化）上分配的质量分数之间的相关系数来进行实验。实验果表明，与BLEU和精确匹配相比，我们提出的Code-BLEU可以与程序员分配的分数实现更好的相关性。

主要思路

论文主要的思想是，在BLEU算法的基础上，增加了其余的三个指标用于解决BLEU的三个问题。

BLEU对每个单词都是一样的，而代码其实是有保留字和声明名称的。对于语言的保留字和声明名称（如变量名、类名等）、常量数值（字符串、数值等），其重要性远远大于普通的名称声明。在这篇论文中，引入了带权重的 BLEU 算法，将保留字的权重设置为普通词的4倍，以应对该问题。
BLEU将代码作为一串普通文本进行对比，忽略了代码语法。实际上，代码作为一个人为创建的语言，具备很强的逻辑性。该论文引入了AST语法树，通过对比语法树来引入对于代码语法的评估。
BLEU将代码以自然语言的形式理解，忽略了代码语义。代码作为逻辑性很强的语言，一个语义的差别，可能带来的结果却是天差地别。该模型引入了数据流，以图的形式比较数据流的相似性，将代码语义引入评估模型中。

根据上述描述，CodeBLEU的最终得分公式如下：

$CodeBLEU =α · BLEU + β · BLEU_{weight} + γ · Match_{ast} + δ · Match_{df}$

典型示例

论文中给了一正一反两个示例，来证明CodeBLEU比BLEU更加准确。

反例

在这里插入图片描述

这个例子中，参考代码是将一个double类型的数据转化为int类型。而候选代码则将数据转化成了float类型。使用BLEU算法，计算出的相似度为75.43。而考虑了语法和语义的CodeBLEU则对于返回类型的差异做了惩罚扣分，最终结果为69.73。

正例

在这里插入图片描述

参考代码的逻辑和反例相同，而候选代码中，只是变量名称换了，这丝毫不影响代码的整体逻辑。如果是人工评测，我们会打100分，因为这两段代码的功能是一样的。然而BLEU算法的打分只有68.14分，而考虑语法和语义的CodeBLEU算法的得分为83.97，一定程度上修正了误判。

实现细节

加权N‑Gram匹配

原始 BLEU 比较候选和参考之间的 n 元语法，并计算匹配的 n 元语法的比率。与自然语言的词汇量庞大、词序自由相比，编程语言是人工设计的，只有“int”、“public”等少数几个关键字。将传统的BLEU直接应用到代码综合中会忽略关键字的重要性。因此，我们引入加权n‑gram匹配，为不同的n‑gram分配不同的权重，使得关键词具有更高的权重。

计算公式如下：

$p_n =\frac{\sum_{C∈Candidates}^{}\sum_{i=1}^{l}µ^i_n·Count_{clip}(C(i, i + n))}{\sum_{C^{'}∈Candidates}^{}\sum_{i=1}^{l}µ^i_n·Count(C^{'}(i, i + n)}$

其中n表示n‑gram的长度，C(i, i + n)是从位置i到位置i + n的n‑gram， $Count_{clip}(C(i, i + n))$ 是最大值候选代码和一组参考代码中同时出现的 n 元语法的数量。 µ 表示不同关键字或 n‑gram 的权重。在本文中，关键词的μ是其他标记权重的5倍。同样的，参考BLEU，也使用了惩罚因子，规避算法对短结果的偏向。

$BP=\begin{cases}1 & \text{ if } c>r \\ e^{1-\frac{r}{c} } & \text{ if } c\le r \end{cases}$

其中c是候选代码的长度，r是有效参考语料库的长度。最终加权 n-Gram 语法匹配得分计算如下：

$BLEU_{weight} = BP · exp(\sum_{n=1}^{N} \omega _n \log_{P_n})$

在这篇的论文中，关键字仅在 unigram（单个词语）中考虑，因此 N 和 $\omega_n$ 等于 1。请注意，需要为每种编程语言预定义一个关键字列表。

语法AST匹配

除了序列级匹配之外，论文还通过匹配语法树结构来考虑CodeBLEU中的语法信息。与自然语言不同，编程语言具有自然的树结构，例如抽象语法树（AST）。 AST 是编程语言抽象语法结构的树表示。我们可以获得tree‑sitter解析结果中的所有子树，然后通过比较候选子树和参考子树来计算准确性。在 AST 中，每个节点表示源代码中出现的一个构造。AST 的叶子代表函数的名称和所有变量。然而，我们只是想使用代码的语法结构，命名并不重要，因此我们省略了原始 AST 树中的所有叶子节点。

计算句法 AST 匹配算法公式如下：

$Match_{ast} = Count_{clip}(T_{cand})/Count(T_{ref})$

其中 $Count(T_{ref})$ 是参考子树的总数， $Count_{clip}(T_{cand})$ 是与参考子树匹配的候选子树的数量。这个分数可以从语法的角度评估代码质量，因为诸如 token 缺失、数据类型错误之类的语法错误可以通过它们 AST 之间的差异来捕获。

语义数据流匹配

在编程语言中，源代码的语义与变量之间的依赖关系高度相关。以下图为例，功能是计算一个数组的平均值。尽管候选项和引用之间的差异很微妙（返回 y → 返回 x），但它们的语义完全不同。然而，加权 n 元语法匹配和句法 AST 匹配仍然给出了很高的分数，因为这两个部分代码具有相同的 AST，并且它们的 token 高度重叠。因此，论文还考虑了CodeBLEU中的语义信息。使用数据流将源代码表示为图，其中节点表示变量，边表示每个变量值的来源。与 AST 不同，下图中两个代码的数据流不同，因为它们的返回值分别来自 x 和 y。这样的语义图可以用来测量候选和参考之间的语义匹配。

在这里插入图片描述

基于上述，计算语义数据流匹配分数分为三个步骤。

步骤1： 获取候选和参考的数据流图。基于 AST，我们首先利用叶子来识别变量序列，表示为 V = {v0, v1, …, vm}。

然后我们将每个变量作为图的一个节点，一条有向边 = vi , vj从vi到vj表示第 j 个变量的值来自第 i 个变量。图 G© = (V ; E) 用于表示代码 C 的变量之间的关系，如图 1 中的红色箭头所示。

步骤2： 标准化数据流项。为了简单和统一，我们忽略变量位置并标准化它们的名称。我们收集数据流项中的所有变量并将它们重命名为 var_i，其中 i 是所有数据流项中出现的变量的顺序。

步骤3： 计算语义数据流匹配分数为：

$Match_{df} = Count_{clip}(DF_{cand})/Count(DF_{ref})$

其中 $Count(DF_{ref})$ 是参考数据流的总数， $Count_{clip}(DF_{cand})$ 是和参考数据流匹配的候选数据流数量。

实验过程

对三个代码合成任务进行了实验，即文本到代码（Java）、代码翻译（从Java到C#）和代码细化（Java）。这些任务的先前工作使用 BLEU 或完全匹配进行评估。在本文中，将以提出的CodeBLEU作为评估指标，看看CodeBLEU是否更合理。对于每个任务，计算 Pearson 相关系数，以检查 CodeBLEU 给出的分数与程序员分配的分数（人类评估分数）之间的相关性。详细的实验过程，可以查看论文原文，这里不赘述。