code2seq: Generating Sequences from Structured Representations of Code笔记

前言

方法有点编译原理的味道，这种结合语法结构的思想很好，能用编译原理的知识我觉得确实会有帮助，就是具体方法或许可以优化。

算法地址：https://code2vec.org/
论文地址：https://arxiv.org/abs/1808.01400
作者地址，暂时只有数据集：https://urialon.cswp.cs.technion.ac.il/publications/

Overview

论文旨在encode source code时利用编程语言的语法结构，用抽象语法树(AST)中组合路径的集合表示代码片段，其中每条路径被用LSTMs压缩成固定长度vector。并且在解码时使用注意力机制选择相关的路径，生成每个token。从而实现端到端的代码片段到自然语言的翻译，并且对多种编程语言都适用。

论文中的方法表现超过了一些专门为某一语言设计的方法。

Model Architecture

基于encoder-decoder架构的NMT模型是为了建模条件概率：

x是source sequence，z是a sequence of continuous representations，y是target sequence。
基于注意力的模型，decode阶段的每个step t，都会算一个context vector ct，典型的方法是用一个LSTM，通过z与decoding state ht算出来：

然后ct与ht结合推断target token yt，之前的工作在计算ct和如何与ht结合的方式有所不同。
一个标准的方法是将ct和ht作为MLP的输入，然后用softmax推断下一个token的概率：

论文使用NMT标准的encoder-decoder架构，但一个标志性的区别在于encoder并不将输入作为扁平的token句子(a ?at sequence of tokens)读取，而是由encoder为AST中的每个路径分别创建一个vector表示。decoder便处理这些encoded AST paths。

REPRESENTING CODE AS AST PATHS

AST的叶节点代表标识符和变量名，非叶节点代表语言中结构的限制集，比如循环，变量声明，正则式。

论文将成对叶节点之间的路径当做包含路径上所有节点的sequence，然后用这些带有叶节点的路径表示代码片段本身。将代码片段当做token的sequence则会忽略掉体现方法相似的语法路径。

比如图二中的红色路径，除了DoStmt与ForStmt的不同，忽略掉叶节点变量名的不同，其余是一致的，表明了两个方法功能上的相似性。也正因为AST normalize了许多表面上的variance，使得encoder在面对没有见过的例子时表现更好。

因为论文中路径是组合的，所以即使路径不相同，encoder也能generalize。但又由于这样的路径可以是任意数量，所以采样k个，并且在每个训练iteration都会重新采样k个新的来避免bias。论文中k设置200，超过300似乎不再提升，降至100会有小小的恶化。

下面这段符号不好打，就直接贴图：

下标记录长度，上面区分路径。

Encoder

所以我们的source sequence就是代码的一组路径，xi是一个路径：

论文中路径上每个节点用学到的embedding matrix Enodes表示，使用双向LSTM encode每个路径的整个sequence，将最终状态作为各自的表示：

箭头向右代表正向，所以最终状态是最末的h，反之亦然。
叶节点是代码中的token，论文将token分割为subtoken，比如一个token值为ArrayList，将其分为Array和List。驼峰式命名法这样的编码习俗提供了明确的分割。
类似于之前対节点的encode，使用学到的embedding matrix Esubtokens表示每个subtoken，然后求和代表之前的token：

LSTM decoder在每个step或许也会推断subtoken，比如生成函数名时。
在表示整个路径时，我们将路径的表示与每个叶节点的表示拼接起来，并应用一个全连接层：

value就代表(6)中的w

decoder的起始状态是z的平均值：

输入路径的顺序没有考虑，每个路径 xi 都是分别encode得到zi，然后结合的representation通过mean pooling初始化decoder的状态。所以源码就被表示为一个任意路径的集合。
注意力机制与seq2seq相似。
优化目标是交叉熵
具体实验设置可以看论文。实验结果当然很好了。

ABLATION STUDY