论文阅读 - 01 DeepFix: Fixing Common C Language Errors by Deep Learning

program repair ≈ grammar correction in nlp 作者提出了一个端到端的，带 attention 的多层 seq2seq neural network，包括 RNN 编码器，和带 attention 的 RNN 解码器。该网络可以预测程序出错的位置并附上正确的修复。对比其他修复特定编程任务的工作，DeepFix 可以用在任何未预见的任务上。不易解决的错误需要考虑到程序文本中的长期依赖。DeepFix 通过带注意力机制的 seq2seq 模型来捕捉长期依赖。它的优势在于：(1) 利用端对端的基于深度学习网络解决普遍的编程问题；(2) 可以迭代地解决一个程序中的多个错误；(3) 在上千 C 程序评估中得到很好的结果。

Program Representation

程序文本由不同类型的标记组成，如类型、关键字、特殊字符(如分号)、函数、文字和变量。其中，类型、关键字、特殊字符和库函数构成了跨不同程序的共享词汇表。作者在表示程序时保留它们，对其他类型的 token 进行如下建模。首先定义一个固定大小的名称池，然后为每个程序构造一个单独的编码映射 encoding map ，方法是将程序中每个不同的标识符(变量名或函数名)随机映射到池中唯一的名称，并选择一个足够大的池来为数据集中的任何程序创建上述映射。这种转换不会改变程序的语义，且是可逆的。字面量的确切值对学习任务无关紧要，因此，根据字面值的类型将其映射为特殊的 token ，例如，将所有整数字面值映射为 NUM ，将所有字符串字面值映射为 STR 。用表示标记序列的结束。

由于一个程序用 seq 的 tokens 表示时，要产生类似长度的准确修复后的 seq 非常困难，且一个程序通常包含上百个 token。所以作者把代码行号也进行标记，将一个 K 行的程序 P 表示为 $(l_{1}, s_{1}), . . . (l_{k}, s_{k}) < e o s >$ ，l 和 s 分别是对行号和语句的标记。一个 fix 包括 $l_{i}, s_{i}$ ，这比用全部的 token 作为输出简单得多。

Neural Network Architecture

基于 Neural Machine Translation by Jointly Learning to Align and Translate ，NLP 中 encoder-decoder 中第一个使用 attention 机制的工作，将 attention 机制用到了神经网络机器翻译(NMT)。https://arxiv.org/pdf/1409.0473.pdf

这里编码器和解码器 rnn 都由 N 个堆叠的门控循环单元(GRUs)组成。编码器将输入序列中的每个 token 映射到一个称为 annotation 的实向量。对于输入序列 $x_1，…，x_{T_x}$ , t 时刻的隐藏单元激活计算如下:

$h_t^{(1)} = GRU(h_{t-1}^{(1)},x_t)$

$h_t^{(n)} = GRU(h_{t-1}^{(n)},h_t^{(n-1)}),\forall n \in \{ 2,...,N \}$

解码器网络的隐藏状态被初始化为用编码器网络的最终状态，然后更新：

$d_t^{(n)} = GRU(d_{t-1}^{(n)},d_t^{(n-1)}),\forall n \in \{ 2,...,N \}$

$d_t^{(1)} = GRU(d_{t-1}^{(1)},z_t)$

其中 $z_{t}$ 是输出 $\hat{y}_{t-1}$ 在 $t - 1$ 和上下文向量 $c_{t}$ 的连接，定义如下:

$c_t = \sum_{j=1}^{T_x} a_{tj}h_j^{(N)}$

$a_{tj} = \frac{exp(e_{tj})}{\sum_{k=1}^{T_x}exp(e_{tk})}$

$e_{tk} = \Phi(d_{t-1},h_k^{(N)})$

c 就是全部隐状态的一个加权和，用到归一化权重 a 。a 就是一个对齐模型，用来评估当前预测词，与输入词每一个词的相关度。将上一个输出序列隐状态 $d_{t-1}$ 和输入序列隐状态 $h$ 输入网络，然后做 softmax 归一化，计算出权重。

Iterative Repair

DeepFix 使用简单而有效的迭代策略来修复程序中的多个错误。oracle 的工作是通过检查更新后的程序是否比输入的程序好来决定是否接受修复。如果更新后的程序不会比输入程序产生更多的错误消息，则使用编译器并接受修复。我们还使用一些启发式方法来防止对输入程序的任意更改。例如，如果 oracle 不保留原始语句 $s_{i}$ 中的标识符和关键字，则它拒绝 fix $s_{i}$ 。一旦修复程序被接受，DeepFix 将再次向网络显示更新后的程序。

这种迭代策略停止的条件：(1) oracle 确定更新程序没有任何错误；或 (2) 网络视输入程序是正确的，发出一种特殊 token "fix"；或 (3) oracle拒绝修复,或 (4)达到预定的迭代的数量上限。

除了决定是否替换语句，网络还会决定新的一行是否要插入在行前或行后，用 $l_{i}^{-}, l_{i}^{+}$ 代替 $l_{i}$ ，如果要删除行，则将 $l_{i}$ 带上空字符 $\epsilon$ 。oracle 使用程序特殊的编码映射，将修复好的 token sequence 重构回原来的标识符。它使用修复中的行号，并用输入程序中相应行中的字面值替换诸如 NUM 和 STR 等特殊标记。如果 oracle 不能重建程序文本，那么它拒绝修复。

作者提出的修复策略有几个优点。(1) 程序完整地呈现在网络上。识别和修复编程错误通常需要能够推断长期依赖关系的全局分析。网络架构能够有选择地参与程序的任何部分，可以推理结构和语法约束，以预测错误的位置和需要的修复。(2) 在输入和输出中都包含行号，降低了粒度，从而降低了预测任务的复杂性。(3) DeepFix可以迭代地修复程序中的多个错误。(4) oracle用于跟踪进度，防止无用的或任意的更改。(5) DeepFix的修复策略比较泛化。例如，如果我们试图修复逻辑错误，我们可以使用测试引擎和测试套件作为oracle。如果修复程序通过了更多的测试，那么它将被接受。

Experiments

https://bitbucket.org/iiscseal/deepfix

数据集：两类程序，一种是编译的程序(正确的程序)，另一种是不编译的程序(错误的程序)。一个学生可能会提交几个错误的程序，作者在每个学生的每个编程任务中随机选择一个错误的程序，以避免测试结果的偏差。

论文阅读 - 02Deep Reinforcement Learning for Programming Language Correction

新手编程者经常饱受程序语言正规语法的折磨，为了协助他们，作者设计了一个基于强化学习的新型程序语言纠正框架，这个框架允许一个智能体 agent 模仿人类行为进行文本导航和编辑，展示了一个 agent 可以通过直接从原始的输入自我探索来进行训练，自我探索就是说，程序文本它自己，不利用程序语言正规语法的任何经验。我们充分利用专家案例作为 1/10 的训练数据，来加速训练。

程序语言规定程序文本的语法规则检验。一个不遵守规则的程序文本不会被编译执行，这给新手编程者带来了障碍。在目前大量的线上编程课程中，从指导者获得个性化反馈是十分不可实行的。因此，作者的工作旨在利用技术帮助新手编程者，通过自动化修正程序中的通用语法错误。

作者通过强化学习提出这个问题。当面对一个错误，一个程序员根据程序文本找到错误的位置，然后修正编辑来修复错误。作者提出了一个新型程序语言修正框架，在这里，一个 agent 可以模仿这些行为。一个 agent 可以访问和修改一个程序文本，对它来说，检查程序文本语法有效性的编译器是一个黑盒子。编译器通常不会精确地指明错误的位置。所以，不能依赖编译器来找到错误的位置和进行修正。作者利用编译器生成的错误信息的数量设计了一个 reward function。agent 的目标是将程序成功编译所必要的编辑行为表现的最好。

框架的挑战是为程序文本的 agent 学习一个 control policy，不通过任何带有程序语言正规语法知识的agent。通过深度学习，agents 可以被训练到专家水平来玩视觉文字游戏，有趣的是，这些技术直接从原始输入，如像素、文本等。在这项工作中，第一次展示了它在程序空间中的可能性。

如图1，修复了税收算法，有两个语法错误：第四行的 scanf 使用错误，第12行的 "}" 缺失。程序以被标记化的形式展现给 agent，agent 的指针位置被初始化为程序的第一个 token。在程序中 agent 的导向性的动作用箭头表示，系列动作如图所示。agent 准确定位和修复所有错误。首先，agent 导向错误的位置行4，用逗号替代不正确的分号，在错误2中插入丢失的 "}" 。这些编辑操作完成后，程序成功编译，agent 停止。这比蛮力列举编译修正高效很多。

通过长短期记忆网络 LSTM 网络进行编码，agent 被允许执行一系列的导航和编辑行为来修复程序。每一步修复错误的编辑都获得一些小的奖励，最大化达到目标状态的奖励，即程序的无错误状态。agent 的 control policy 就是学习使用 A3C 算法。

训练一个agent的难点有两个：（1）agent 要同时定位错误并在此做出精确的编辑来修复程序。错误的编辑会导致引入更多的错误，使得任务更加困难。为了克服这个问题，我们设定环境来拒绝这样的编辑。这显著的削减了 state space。（2）随着时间增长，任务的 state space 越来越大，state 探索收集的信息越来越多，的强化学习趋向越来越慢。一个方法是利用专家表示来引导 agent。在我们的工作中，这些表示是自动生成的而不是人类干预，我们将此称为 RLAssist。

DeepFix 是目前修复程序错误中表现最好的工具。作者在需要修复的 C 程序上对比该工具和 RLAssist 。作者证明了RLAssist可以通过只使用错误程序自我探索来训练，同时仍然可以达到 DeepFix 的性能。通过专家演示加速训练，为 10% 训练集生成专家演示，90% 的数据集没有演示。RLAssist完全修复了测试集中26.6%的程序，并解决了39.7%的错误消息。与DeepFix相比，这两个版本分别提高了14%和29%。因此，RLAssist在一小部分训练数据上使用专家演示，表现优于DeepFix。

此工作的主要贡献如下:

设计了一种新颖的程序设计语言校正框架，可用于强化学习。
我们使用A3C来纠正编程语言，并通过专家演示加速培训。
我们的实验表明，我们的技术只使用了十分之一的训练数据，其性能超过了最先进的工具DeepFix。此外，我们的技术也可以在没有任何演示的情况下工作，但仍然可以匹配DeepFix的性能。
RLAssist的实现将是开源的。

a framework for programming language correction tasks

当面对一个错误时，一个程序员会定位程序中错误的位置并编辑操作来修复错误。出现大量错误时，程序员会重复如上步骤，此文提出程序语言修正框架，一个agent可以模仿以上的行为。

states

一个 state 用一个 $< s t r i n g, c u r s o r >$ 表示，string 表示程序文本， $cursor \in \{ 1,...,len(string)\}$ ， $l e n (s t r i n g)$ 表示 string 中 token 的数量。env 跟踪 string 中错误的数量。这些错误可以从 ground truth 确定(当 ground truth可获取时)，也可以从编辑器编译 string 时产生的错误消息来估计。对于编译器，我们使用 GNU C 编译器。

编码 state 到 a sequence of tokens。首先，将程序字符串转换成词汇序列，这些词汇是不同的类型，例如关键字、操作符、类型、函数、字面量和变量。此外，我们还保留换行符作为词汇，以允许在程序文本上进行二维导航操作。state 中 cursor 部分由一个特殊的 token 表示，插入到序列中，刚好在游标持有索引的 token 之后。

接下来，在所有程序中构建一个共享词汇表。除了一些常见的库函数(如 printf 和 scanf )外，所有其他函数和变量标识符都映射到一个特殊的 token ID。类似地，所有的字面值都根据其类型映射到特殊的 token ，例如，数字映射到 NUM ，字符串映射到 STR 。所有剩余的 tokens 都包含在词汇表中，无需任何修改。这种映射减少了 agent 看到的词汇表的大小。请注意，此编码仅在将 state 反馈给 agent 时才需要。基于这样的编码，agent 预测到的 actions，在原始程序 string 上被 env 执行。

actions and transitions

agent 的动作可以分为两类，一类是更新 cursor，一类是修改 string。我们将第一类称为导航操作，第二类为编辑操作。导航操作允许 agent 在 string 中导航。这些操作只改变一个 state 的游标，而不是 string 。另一方面，编辑操作用于纠错，只修改 string 而不修改游标。错误的编辑操作会在 string 中引入更多错误，而不是修复它们。我们将环境配置为拒绝所有此类编辑，以删除使修复程序变得更加困难的状态空间。此外，拒绝错误的编辑可以防止对程序的任意更改。

对于我们的任务，我们只允许两个导航操作，右移和下移。它们分别将光标设置为右侧的下一个 token 或下一行的第一个 token 。如果光标已经设置为一行的最后一个 token ，则右移动作没有效果；或者光标是最后一行的任何 token 时，向下移动没有效果。注意，向下移动操作是可能的，因为我们在状态编码中保留了换行符。

基于对程序员新手常见的排版错误的研究，我们设计了三种类型的编辑操作。第一个参数化插入 token 操作，插入参数 token 到光标位置之前。参数可以是一个修复的 token 集合中的任何 token ，称之为可变 tokens。第二个是删除操作，删除光标上的token，只有在来自可变 tokens 时才能删除。我们限制可变 tokens 为以下五个类型的 token：分号、括号、大括号、句号和逗号。第三个是是参数化的将 token1 替代为 token2 操作，将光标位置上的 token1 替换为 token2。在这个类中有四个操作：（1）“；”替换为“，”，（2）“，”替换为“；”，（3）“.”替换为“；”，（4）“；）”替换为“）；”。尽管可以用一系列的删除和插入操作替换原子替换操作，但使用它们可以防止组成的删除和/或插入操作被环境拒绝的情况。

episode，termination，and rewards

一个 episode 的
- 开始
  
  string：一个错误的程序文本，cursor：string 的第一个 token
- 结束
  
  到达 goal state ：编辑后的程序被编译器成功编译
termination 终止
- 在一个 episode 中，agent 被允许到达最大数目的 time steps，即 max_episode_len 时终止
- 在一个 episode 中，agent 只允许通过整个程序一次，即 agent 一旦经过程序的最后一个 token，这个 episode 就终止了
reward 奖励

在每一步，agent 会受到一个小的步长惩罚，一个较高的编辑惩罚
- step_penalty 步长惩罚：鼓励 agent 学会在最小步长中来修复程序
- edit_penalty 编辑惩罚：编辑操作开销较大，需要调用编译器来验证，所以不鼓励 agent 做不必要的编辑
- maximum_reward 最大奖励：agent 达到 goal state
- intermediate_reward 中间奖励：纠正至少一个错误的编辑操作

model

首先，使用 LSTM 网络将 state 的 token 嵌入到实向量中，最终的 state 是输出向量的各个元素均值。

考虑到 state 的嵌入，作者采用两个独立的全连接线性层，来生成策略函数 $\pi (a|s; \theta)$ 和值函数 $V (s; w)$ 。更新网络参数前，计算累积梯度：

$d \theta \leftarrow d \theta + {\Delta }_{\theta '} log \pi (a_t | s_t ; \theta ')(R - V(s_t ;w'))$

$dw \leftarrow dw + {\Delta }_{w'}(R-V(s_t;w'))^2$

$R = \sum _{i = 0}^{k-1}\gamma^ir_{t+i}+\gamma^kV(s_{t+k};w')$

![alt]()

$H$ 是熵， $b e t a$ 是它的正则化项超参数。

expert demonstrations

RLAssist可以不使用任何演示进行训练，但会耗费更长的训练时间。原因是在A3C算法，每一个 episode 中，一个 agent 从一个随机 state 开始，然后使用它的 policy function 与环境进行交互。由于 policy network 是随机初始化的，因此在训练开始时，这种交互随机进行探索。在只进行随机探索的情况下，agent 会发现很难到达目标状态，也很难获得奖励。因此，训练速度减慢。

作者使用专家演示来加速训练。专家演示是指向事件目标状态的一系列动作。给定一对 (p, p') ，其中 p 是一个不正确的程序， p' 是它的正确版本，将自动生成如下的演示。从 p' 中的第一个 token 开始，每个未修改的行 (w.r.t. p) 都会通过一个向下移动操作跳过。在第一个错误行，光标通过向右移动操作向右移动，直到到达错误位置并生成适当的编辑操作。这个过程一直重复，直到程序中的最后一个错误被解决。我们将 agent 设定为使用以下专家演示。对于可以进行演示的 episodes ，agent 遵循所提供的预定动作序列，而不是由 policy 驱动的 sampling 。对 policy network 参数的更新就像预先确定的动作 sampled 一样。对于其他 episode ，代理将按照标准的 A3C 算法，使用 policy 来 sample 的动作。请注意，演示是在 episode 级别提供的，而不是在更细粒度的转换级别上提供的。因为 agent 需要在整个事件中采取正确的行动来达到目标状态并获得奖励。如果它采取断断续续的指导，那么它仍然无法达到目标状态。