Xinyun Chen、Chang Liu、Dawn Song作者Geek AI 张倩编译

程序翻译新突破:UC伯克利提出树到树的程序翻译神经网络

程序翻译是将一种语言的遗留代码迁移到用另一种语言构建的生态系统的重要工具。本文作者首次使用深度神经网络来解决程序翻译问题。他们观察到程序翻译是一个模块化的过程并据此设计了一个树到树的神经网络,将源树转换为目标树。与其他神经翻译模型相比,该方法始终比对比基线好 15 个百分点以上。此外,该方法的性能在实际项目的翻译上比目前最先进的程序翻译方法高 20 个百分点。

程序是构建计算机应用、IT 产业和数码世界的主要工具。为了方便程序员为不同的应用开发程序,人们发明了各种编程语言。与此同时,当程序员想要将用不同语言编写的程序组合在一起时,这些编程语言的差异就为这项工作带来了困难。因此,实现不同编程语言之间的程序翻译是十分必要的。

如今,为了在不同的编程语言之间翻译程序,程序员通常会自己亲自研究两种语言语法之间的对应关系,然后开发一个基于规则的翻译器。然而,这个过程可能效率低下,而且十分容易出错。在本文的工作中,我们首次尝试检验是否可以利用深度神经网络来自动构建一个程序翻译器。

凭直觉看,程序翻译问题在其形式上类似于自然语言翻译问题。先前的一些工作提出将基于短语的统计机器翻译(SMT)用于代码迁移 [26,20,27]。最近,基于序列到序列Seq2Seq)的模型等神经网络方法在机器翻译方面取得了当前最佳性能 [5,10,14,15,36]。在本文中,作者研究了使用神经机器翻译方法来处理程序翻译问题。然而,使基于序列到序列的模型失效的一个巨大挑战是:与自然语言不同,编程语言有严格的语法,它不能容忍拼写错误和语法错误。已经证明,当编程语言序列变得太长时 [21],基于 RNN 的序列生成器很难生成句法正确的程序。

在本文的工作中,我们注意到,RNN 很难生成句法正确程序的主要原因是它将两个子任务——学习语法及对齐序列与语法——纠缠在了一起。当这两个任务可以被分别处理时,模型的性能通常会提高。例如,Dong 等人使用了一个基于树的解码器来分离两个任务 [12]。特别是 [12] 中的解码器利用树结构信息:(1)使用 LSTM 解码器在解析树的相同深度生成节点;(2)展开一个非叶子节点并在解析树中生成它的子元素。这种方法已被证明可以在一些语义解析任务上取得目前最好的结果。

受到这个观测结果的启发,我们假设可以利用源解析树和目标解析树的结构信息来实现这种分离。受这种直觉的启发,我们提出树到树的神经网络,将树编码器和树解码器结合在一起。特别地,我们注意到在程序翻译问题中,源程序和目标程序都有各自的解析树。此外,跨语言的编译器通常遵循一个模块化过程,将源树中的各个子组件转换为相应的目标组件,然后使用它们组合成最终的目标树。因此,我们设计了一种树到树神经网络的工作流程来配合这个过程:当解码器展开一个非叶子节点时,它会使用注意力机制在源树中定位对应的子树,并利用子树的信息来引导非叶子节点展开。特别需要注意的是,树编码器在这种情况下有很大的作用,因为它可以将子树的所有信息聚合到它的根的嵌入中,这样嵌入就可以用来指导目标树的非叶子节点扩展。

我们根据上述直觉来设计树到树的转换模型。一些现有的工作 [34,22] 提出了基于树的自动编码器体系架构。但是,在这些模型中,解码器只能访问表示源树的单个隐藏向量,因此它们在翻译任务中不够高效。在我们对模型的评价过程中,我们证明了在没有注意力机制的情况下,翻译性能在大多数情况下为 0%,而使用注意机制可以将性能提升到 90% 以上。论文「Towards neural machine translation with latent tree attention」提出了一种用于自然语言翻译的基于树的注意力编码器-译码器架构,但其模型的性能甚至比注意力序列到序列的对比基线模型更差。一个主要原因是,它们的注意力机制独立地计算每个节点的注意力权值,这并不能很好地捕获解析树的层次结构。在本文的工作中,作者设计了一个父亲节点注意力反馈机制,该机制建立了不同节点之间的注意力映射依赖关系,作者证明了这种注意力机制进一步提高了树到树模型的性能,特别是当解析树变大时(即获得了 20%−30% 的性能提升)。据我们所知,这是目前针对翻译任务提出的树到树神经网络架构的首次成功展示。

为了检验我们的假设,我们开发了两个新的程序翻译任务,并使用现有的 Java 到 c# 的程序翻译工作 [26,27] 进行对比基准测试。首先,我们在提出的两个任务上,对我们的方法和一些神经网络方法进行了对比。实验结果表明,我们的树到树模型在程序翻译任务上优于其他最先进的神经网络,在单词翻译的准确率上提升了 5%,在程序翻译的准确率上提升了 15%。此外,我们将我们的方法与以前在 Java 到 c# 对比基准上的程序翻译方法进行了比较,结果显示,我们的树到树模型在程序翻译的准确率上比以前的技术领先 20%。这些结果表明,我们的树到树模型在解决程序翻译问题上是很有发展前景的。同时,我们认为我们提出的树到树神经网络也可以适用于其他树到树的任务,这将是我们未来的工作。

论文:Tree-to-tree Neural Networks for Program Translation

论文链接:https://arxiv.org/pdf/1802.03691.pdf

摘要:程序翻译是将一种语言的遗留代码迁移到用另一种语言构建的生态系统的重要工具。在本文的工作中,我们首次使用深度神经网络来解决程序翻译问题。我们观察到程序翻译是一个模块化的过程,在这个过程中,源树的子树在每一步都被转换成相应的目标子树。为了利用这种直觉,我们设计了一个树到树的神经网络,将源树转换为目标树。同时,我们为树到树模型开发了一种注意力机制,当解码器在目标树中展开一个非叶子节点时,注意力机制会在源树中定位相应的子树来引导解码器展开。我们将树到树模型的程序翻译能力和一些目前最先进的方法进行比较,从而对其进行评价。与其他神经翻译模型相比,我们的方法始终比对比基线好 15 个百分点以上。此外,我们方法的性能在实际项目的翻译上比以前最先进的程序翻译方法提高了 20 个百分点。

2 程序翻译问题的形式化定义

定义 1(程序翻译)

给定两种编程语言 L_s 和 L_t,每种编程语言都有一组实例(p_k,T_k),其中 T_k 是这种语言对应的解析树。我们假设存在标准的翻译结果 π,它能将 L_s 中的实例完美地映射到 L_t 的实例上。给定一个实例对(i_s,i_t)的数据集,我们有 i_s ∈ L_s, i_t ∈ L_t 且 π(i_s) = i_t,本文研究的问题就是如何学习到一个函数 F 能够将每个 i_s ∈ L_s 映射到 i_t = π(i_s) 上。

3 树到树的神经网络

3.1 将程序翻译看做一个树到树的翻译问题

图 1:将一个 CoffeeScript 程序翻译成一个 JavaScript 程序。CoffeeScript 程序的子组件及其在 JavaScript 中相对应的翻译结果被高亮显示了出来。

图 1 展示了一个从 CoffeeScript 到 JavaScript 的翻译示例。我们注意到程序翻译问题的一个有趣特性是,翻译过程可以是模块化的。图中高亮显示了源树中对应于 x=1 的子组件及其在目标树中对应于 x=1 的翻译结果;这种对应关系独立于程序的其他部分。当程序变得更长,这样的情况可能重复发生多次时,序列到序列模型可能很难仅基于没有结构信息的 token 序列来捕获对应关系。因此,当将目标树中的非叶子节点扩展为子树时,这样的对应关系使得在源树中定位引用的子树成为一种自然的解决方案。

3.2 树到树的神经网络

在上述动机的启发下,我们设计了树到树的神经网络,它遵循了一个编码器-解码器框架,将源树编码为嵌入,并将嵌入解码为目标树。为了利用模块化翻译过程的直觉,解码器在展开非叶子节点时采用了注意力机制来定位相应的源子树。我们在图 2 中展示了树到树模型的工作流。

图 2:树到树模型的工作流:箭头表示计算流。蓝色实箭头表示指向左子节点/从左子节点流入的流,橙色虚线箭头表示右子节点的流。从源树根到目标树根的黑色点箭头代表 LSTM 状态被复制。绿色框表示扩展节点,灰色框表示队列中待扩展的节点。与扩展节点对应的源树的子树用黄色高亮显示。右下角列出了预测扩展节点值的公式。

4 模型评价

在本章中,作者在程序翻译任务上评价了本文提出的树到到树神经网络和其它一些对比基准方法。

表 1:在 CoffeeScript 和 JavaScript 之间进行翻译的程序准确率。token 准确率见附录 C。

表 2:在 Java 到 C# 的翻译中的程序准确率。在括号中,我们给出了可以通过增加训练集来达到的程序准确率

理论程序翻译NIPS 2018NIPS
2
相关数据
自动编码器技术

自动编码器是用于无监督学习高效编码的人工神经网络。 自动编码器的目的是学习一组数据的表示(编码),通常用于降维。 最近,自动编码器已经越来越广泛地用于生成模型的训练。

神经机器翻译技术

2013 年,Nal Kalchbrenner 和 Phil Blunsom 提出了一种用于机器翻译的新型端到端编码器-解码器结构 [4]。该模型可以使用卷积神经网络(CNN)将给定的一段源文本编码成一个连续的向量,然后再使用循环神经网络(RNN)作为解码器将该状态向量转换成目标语言。他们的研究成果可以说是神经机器翻译(NMT)的诞生;神经机器翻译是一种使用深度学习神经网络获取自然语言之间的映射关系的方法。NMT 的非线性映射不同于线性的 SMT 模型,而且是使用了连接编码器和解码器的状态向量来描述语义的等价关系。此外,RNN 应该还能得到无限长句子背后的信息,从而解决所谓的「长距离重新排序(long distance reordering)」问题。

基准技术

一种简单的模型或启发法,用作比较模型效果时的参考点。基准有助于模型开发者针对特定问题量化最低预期效果。

注意力机制技术

我们可以粗略地把神经注意机制类比成一个可以专注于输入内容的某一子集(或特征)的神经网络. 注意力机制最早是由 DeepMind 为图像分类提出的,这让「神经网络在执行预测任务时可以更多关注输入中的相关部分,更少关注不相关的部分」。当解码器生成一个用于构成目标句子的词时,源句子中仅有少部分是相关的;因此,可以应用一个基于内容的注意力机制来根据源句子动态地生成一个(加权的)语境向量(context vector), 然后网络会根据这个语境向量而不是某个固定长度的向量来预测词。

解析树技术

解析树是一个内部结构,由编译器或解释器在解析一些语言结构时创建,解析也被称为“语法分析”。

机器翻译技术

机器翻译(MT)是利用机器的力量「自动将一种自然语言(源语言)的文本翻译成另一种语言(目标语言)」。机器翻译方法通常可分成三大类:基于规则的机器翻译(RBMT)、统计机器翻译(SMT)和神经机器翻译(NMT)。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

准确率技术

分类模型的正确预测所占的比例。在多类别分类中,准确率的定义为:正确的预测数/样本总数。 在二元分类中,准确率的定义为:(真正例数+真负例数)/样本总数

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

统计机器翻译技术

随着统计学的发展,研究者开始将统计模型应用于机器翻译,这种方法是基于对双语文本语料库的分析来生成翻译结果。这种方法被称为统计机器翻译(SMT)

序列到序列技术

长短期记忆网络技术

长短期记忆(Long Short-Term Memory) 是具有长期记忆能力的一种时间递归神经网络(Recurrent Neural Network)。 其网络结构含有一个或多个具有可遗忘和记忆功能的单元组成。它在1997年被提出用于解决传统RNN(Recurrent Neural Network) 的随时间反向传播中权重消失的问题(vanishing gradient problem over backpropagation-through-time),重要组成部分包括Forget Gate, Input Gate, 和 Output Gate, 分别负责决定当前输入是否被采纳,是否被长期记忆以及决定在记忆中的输入是否在当前被输出。Gated Recurrent Unit 是 LSTM 众多版本中典型的一个。因为它具有记忆性的功能,LSTM经常被用在具有时间序列特性的数据和场景中。

深度神经网络技术

深度神经网络(DNN)是深度学习的一种框架,它是一种具备至少一个隐层的神经网络。与浅层神经网络类似,深度神经网络也能够为复杂非线性系统提供建模,但多出的层次为模型提供了更高的抽象层次,因而提高了模型的能力。

推荐文章
暂无评论
暂无评论~