论文阅读 - Deep 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。

此工作的主要贡献如下:

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

a framework for programming language correction tasks

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

states

一个 state 用一个 < string , cursor > 表示，string 表示程序文本，cursor $\in$ { 1,…,len(string) }，len(string) 表示 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

1. 一个 episode 的

   • 开始

     string：一个错误的程序文本

     cursor：string 的第一个 token

   • 结束

     到达 goal state ：编辑后的程序被编译器成功编译

2. termination 终止

   • 在一个 episode 中，agent 被允许到达最大数目的 time steps，即 max_episode_len 时终止

   • 在一个 episode 中，agent 只允许通过整个程序一次，即 agent 一旦经过程序的最后一个 token，这个 episode 就终止了

3. 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) 。更新网络参数前，计算累积梯度：

$H$ 是熵，$\beta$ 是它的正则化项超参数。

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 需要在整个事件中采取正确的行动来达到目标状态并获得奖励。如果它采取断断续续的指导，那么它仍然无法达到目标状态。

experiments

https://bitbucket.org/iiscseal/rlassist/src/master/