学界 | 循环神经网络自动生成程序:谷歌大脑提出「优先级队列训练」

选自arXiv

作者:Daniel A. Abolafia、Mohammad Norouzi、Quoc V. Le

机器之心编译

参与:路雪、李泽南

由谷歌大脑 Quoc V. Le 团队提交的论文提出了一种使用循环神经网络进行程序合成的新方法——优先级队列训练(PQT)。目前,该论文已提交 ICLR 2018 大会,正在接受评议。

GitHub 链接:https://github.com/tensorflow/models/tree/master/research/brain_coder

自动程序合成是一项具备广泛应用潜力的任务。传统方法(如 Muggleton & de Raedt (1994); Angulin (1987))通常不使用机器学习,因此需要编程语言和手动启发式方法方面的专业知识来加速底层组合搜索。为了创建无需领域专业知识的更通用的编程工具,近期大量研究开始开发神经模型,可促进某种形式的内存访问和符号推理(如 Reed & de Freitas (2016); Neelakantan et al. (2016); Kaiser & Sutskever (2016); Zaremba et al. (2016); Graves et al. (2016))。尽管这些研究取得了很大成果,但是没有一种方法能够用富于表达性的编程语言合成源代码。

近期出现了多项使用神经网络从输入-输出示例导出程序的成功尝试(Riedel et al., 2016; Bunel et al., 2016; Balog et al., 2017; Parisotto et al., 2016),甚至从非结构化文本生成程序(Parisotto et al., 2016),但是它们通常使用限制性编程语法,需要真正程序或正确输出形式的监控信号。与之相反,本论文提倡使用富于表达性的编程语言 BF,其语法简单,且图灵完备。此外,本论文旨在使用强化学习合成程序,只需要一个 solution checker 就可以计算奖励信号。你可以将代码长度罚分或执行速度纳入奖励信号,进而搜索高效的短程序。因此,相比训练过程中需要程序或正确输出的其他方式,基于奖励的程序合成具备更高的灵活性。

为解决基于奖励信号的程序合成,本论文研究了两种不同方法。第一种方法是策略梯度(PG)算法(Williams, 1992),训练一个循环神经网络(RNN)来生成程序,每次生成一个 token。然后执行该程序并打分,奖励反馈将返回至 RNN 以更新参数,这样随着时间,生成的程序将越来越好。第二个方法是一种欺骗性的简单优化算法——优先级队列训练(priority queue training,PQT)。训练过程中保持 K 个最优程序的优先级队列可见,对队列中前 K 个程序使用对数似然目标函数来训练 RNN。然后从 RNN 中采样新程序,更新队列,进行迭代。本论文还对比了遗传算法(GA)基线(之前证明其可生成 BF 程序,Becker & Gottschlich (2017))。令人惊讶的是,论文发现 PQT 算法显著优于 GA 和 PG 方法。

论文在 BF 编程语言上评估了提出方法的有效性。BF 语言是图灵完备的语言,仅有 8 条指令。BF 语言的极简语法使之易于生成语法正确的程序,这与比较高级的语言相反。本论文考虑了不同字符串操作、数值和算法任务。结果显示文中考虑的所有搜索算法在大部分任务中都能够找到正确的程序,而论文提出的方法是最可靠的,因为它是在最随机的种子上找到解决方案的,且可以解决的任务也是最多的。

本论文的主要贡献:

  • 提出一个程序合成学习框架,训练过程中仅需要奖励函数(无需真正程序或正确输出)。此外,论文提倡使用简单且富于表达性的编程语言 BF 作为程序合成的基准环境(还可以参考 Becker & Gottschlich (2017))。
  • 受 Liang et al. (2017) 论文的启发,本论文使用优先级队列和 RNN 的搜索算法进行实验,并展示了将优先级队列作为 RNN 的训练目标是一种高效、稳定的方法。
  • 提出一种实验方法来对比不同的程序合成方法,包括遗传算法和策略梯度方法。该方法评估了每个合成方法的平均成功率,并提供了一种调整超参数的标准方法。使用该方法,研究者发现使用优先级队列训练的循环神经网络优于基线模型。

方法

研究者实现了一个程序生成模型,即每次输出一串 BF 语言字符串的 RNN。图 2 展示了 RNN 模型,允许用自回归方式采样 BF 字符串,即将前一个预测作为下一步的输入。第一步的输入是特殊的 START 符号。RNN 生成特殊的 EOS 符号时终止,该符号表示字符串终结,或者程序长度超出预先指定的最大长度。每个时间步的预测通过多项式分布(一种多个时间步共享权重的 softmax 层)进行采样。程序序列的联合概率是所有 token 概率的积。

图 1:合成器图示。合成器是一个循环神经网络,以自回归的方式生成程序。

表 3 展示了相同的算法加上均匀随机搜索的成功率,以及训练和评估测试案例的成功率。研究者还在最后一行列出平均值,进行各列之间的整体对比。从表中可知,根据训练和评估平均值,PQT 要明显优于 PG 和 GA。PG+PQT 仅与 PQT 相当。由于过拟合,在很多情况下评估成功率要低于训练成功率。

表 3:当执行程序的最大数(max NPE)是 20M 时,在所有任务上合成方法成功的数量(25 个之中)。单元格中有斜杠分割的两个数。第一个数是训练测试案例中的成功数量,第二个数是留出评估测试案例中的成功数量。对于无法合成满足某个任务训练案例的方法,用短线进行标记。

表 4:用于已解决任务的合成 BF 程序。所有程序由原本的智能体发现,并且没有任何代码字符被删除或改变。注意,一些程序与任务产生过拟合。我们标红了代码方案过拟合的所有任务(经过手动检查确定)。

论文:Neural Program Synthesis with Priority Queue Training

论文链接:https://arxiv.org/abs/1801.03526

摘要:我们认为程序合成任务是在程序的输出中存在一个奖励函数,目标是找到奖励最大的程序。我们采用了一种迭代优化方案,在这种方法中,我们在目前已生成的 K 个最佳程序数据集上训练一个 RNN 模型。随后,我们合成新的程序,并通过 RNN 采样将它们添加到优先级队列中。我们使用一种简单但富于表达性的图灵完备语言 BF,对该算法(优先级队列训练,PQT)与遗传算法和强化学习基线进行了对比。实验结果证明简单的 PQT 算法显著优于基线。通过在奖励函数中添加程序长度罚分,我们就可以生成简短、人类可读的程序。

本文为机器之心编译,转载请联系本公众号获得授权。

原文发布于微信公众号 - 机器之心(almosthuman2014)

原文发表时间:2018-01-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

多图|入门必看:万字长文带你轻松了解LSTM全貌

作者 | Edwin Chen 编译 | AI100 第一次接触长短期记忆神经网络(LSTM)时,我惊呆了。 原来,LSTM是神经网络的扩展,非常简单。深度学...

33970
来自专栏大数据挖掘DT机器学习

决策树--从原理到Python实现

决策树基本上是每一本机器学习入门书籍必讲的东西,其决策过程和平时我们的思维很相似,所以非常好理解,同时有一堆信息论的东西在里面,也算是一个入门应用,决策树也有回...

33370
来自专栏人工智能头条

放弃 RNN/LSTM 吧,因为真的不好用!望周知~

28360
来自专栏人工智能

如何使用TensorFlow实现神经网络

如果你一直关注数据科学或者机器学习等领域,你肯定不会错过深度学习和神经网络的热潮。许多组织都正在寻找深度学习人才,将深度学习运用于各个领域。从参与竞赛到运用于开...

46990
来自专栏hadoop学习笔记

处理数据缺失的结构化解决办法

数据缺失是数据科学家在处理数据时经常遇到的问题,本文作者基于不同的情境提供了相应的数据插补解决办法。没有完美的数据插补法,但总有一款更适合当下情况。

5900
来自专栏大数据文摘

论文Express | 自然语言十项全能:转化为问答的多任务学习

Salesforce最新论文提出了一个可处理多项自然语言处理的通用模型:decaNLP,处理机器翻译、文本分类等NLP任务统统不在话下!

15120
来自专栏机器之心

学界 | 不会写作文?试试这个文本模板生成系统呗

作者:Sam Wiseman、Stuart M.Shieber、Alexander M.Rush

11720
来自专栏决胜机器学习

机器学习(五) ——k-近邻算法进一步探究

机器学习(五)——k-近邻算法进一步探究 (原创内容,转载请注明来源,谢谢) 一、概述 现采用k-近邻算法,进行分类应用。数据源采用《机器学习实战》提供的数...

34340
来自专栏编程

用Python进行速度预测

这次分享一段数据特征挖掘准备工作的套路~ 数据格式是这样的: ? task 预测值:速度 特征值: Region 区域 Length 长度Volume 流...

34290
来自专栏吴生的专栏

人人都会深度学习之Tensorflow基础快速入门

《Tensorflow基础快速入门》课程的目的是帮助广大的深度学习爱好者,逐层深入,步步精通当下最流行的深度学习框架Tensorflow。该课程包含Tensor...

15030

扫码关注云+社区

领取腾讯云代金券