Panda参与

强化学习+树搜索:一种新型程序合成方法

程序合成一直都是计算机科学领域内一大重要研究方向。近日,普林斯顿大学的研究者提出了一种结合强化学习与树搜索实现程序合成的方法,为程序合成开启了一个新研究方向。这项研究目前仍在继续进行,机器之心对该研究的预印本论文进行了摘要编译。

在编程语言和机器学习领域,程序合成方面的研究都已经出现了复兴,该任务要做的是根据用户提供的规格(specification)自动生成计算机代码。由于计算能力的增长和深度神经网络的兴起,这个曾经无力解决的问题现在已经可以攻克了,并且也已经在很多领域得到了使用 [1],其中包括通过自动执行例程任务来提高程序员的效率 [2]、为没有编程知识的非专家人员提供直观的界面 [3]、为性能很关键的代码减少漏洞和提升运行效率 [4]。

在编程语言(PL)领域,程序合成通常使用枚举搜索来解决——通过简单直接地枚举候选项直到找到满足条件的程序来寻找满足给定规格的合适程序 [5,6,7]。通过将演绎组件集成进搜索过程来收窄搜索空间 [8,9,10],或通过将相关语言修改成具有更窄搜索空间的同等语言并在该空间中搜索 [11,12,13],这种方法可以得到解决。另一种常用方法是将合成任务约简成通过 SAT 求解器寻找一个满足条件的布尔公式配置 [14,15],但这只是将枚举搜索放进了求解器进行处理。

机器学习(ML)领域的研究者则在从另一个方向解决这个问题——不是单纯地全面搜索一个有限定的空间,而是使用一个学习了规格到程序的映射方式的模型,通过智能地搜索或采样搜索空间,从而在更大的搜索空间中有效地找到正确的程序。这些方法大都使用了监督学习方法——在一个大型的输入/输出样本和对应满足规格的程序的合成数据集上训练,然后给定一个相应的输入/输出示例集合 [16,17,18,19,20],使用基于循环神经网络(RNN)的模型依次输出目标程序的每一行。从概念上看,这种方法应该能与编程语言技术很好地结合起来——在小型搜索空间中进行智能搜索比在大型搜索空间中进行智能搜索要容易得多。那么,为什么这些技术通常没有一起使用呢?

机器学习领域内的大部分已有工作都严重依赖于被合成的领域特定语言(DSL)的结构来实现优良的表现,而且也不能轻松地泛化到新语言上。这些方法通常需要语言特征,比如语言的全可微分性 [19,20] 或规格和满足规格的程序对构成的大型训练集 [16,17,18]。这些要求使其难以将已有的基于机器学习的方法与编程语言社区开发的技术结合起来,它们在使用一种 DSL 进行有效合成时所需要的性质差异非常大。此外,大多数已有方法都主要注重以「一步式」的方式求解出程序,要么通过单次或少数几次尝试成功输出满足给定规格的程序,要么就无法得到这样的结果;随着程序空间变大,这种方法的扩展能力会变得更糟。相比之下,当基于搜索的方法枚举所有程序时,它们最终能解决任何合成任务,但所需的时间可能会超出可行范围。

强化学习引导的树搜索

我们的方法是强化学习引导的树搜索(RLGTS:reinforcement learning guided tree search),如图 1 所示。该方法旨在将基于搜索的方法和基于机器学习的方法的优势结合起来,并且让来自这两个研究领域的技术结合起来进一步提升效果。我们提出了一种程序合成新方法:将合成程序的过程表示成一个马尔可夫决策过程(MDP)[21] 并使用强化学习(RL)来学习求解程序,仅需给定该程序的一组输入/输出示例、一个语言规格和一个用于衡量给定程序的质量的奖励函数。在我们的基于强化学习的方法中,我们将程序状态和当前的部分程序看作是环境,并将该语言的代码行看作是寻求实现奖励函数最大化的动作。更进一步,我们还将我们的强化学习模型与一种基于树的搜索技术结合到了一起,这能极大提升该方法的表现。这种组合有助于解决很多强化学习应用中都会出现的局部极小值和高效采样的问题。

图 1:我们提出的系统的示意图。我们的程序合成方法将该问题看作是一个可用强化学习解决的马尔可夫决策过程,并且将其与一种优先搜索树组合起来通过避免局部极小值来加速求解过程,这能提升在固定数量的尝试次数内求解的程序的数量。给定一个输入记忆状态和对应的输出记忆状态集合,这种方法能使用一个为部分正确的解定义的奖励函数来引导学习过程,从而学习到一个策略——该策略能输出可将每个输入样本映射到对应的输出样本的代码行序列。

RLGTS 不依赖给定语言的训练数据的可用性,并且不对语言的结构做任何假设——只要求该语言允许执行和评估不完整的部分程序。此外,我们的基于强化学习的方法可以轻松且自然地与其它程序合成方法结合起来,这让用户可以受益于某些领域在基于搜索的合成上的大量研究成果。

总体而言,我们有以下贡献:

  1. 我们引入了强化学习引导的树搜索(RLGTS),这是一种将程序生成作为强化学习任务处理的程序合成方法。

  2. 我们描述了 RLGTS 在 RISC-V 汇编语言的一个子集上的实现,并且通过结合一个基于 Q 网络的策略与简单的树搜索方法为该任务创建了一个强化学习智能体。

  3. 研究表明,在随机程序构成的一个合成数据集上,相比于仅使用强化学习和仅使用枚举搜索的基准方法,我们的方法可求解的程序的比例分别提升了 100% 和 800%。此外,我们还比较了 RLGTS 与基于马尔可夫链蒙特卡洛(MCMC)的方法(该方法已经在 x86 代码的超优化上取得了很大的成功,并且也是合成汇编语言代码的当前最佳方法 [4]),结果表明我们的方法在更有难度的基准程序上有更优越的表现,在固定的程序评估限制内可求解的程序多出 400%;即使当该限制在 MCMC 看来增大了 50 倍时,我们的方法依然能在总体表现上保持竞争力。

图 2:我们的 Q 函数神经网络的示意图

 图 3:我们的 Q 函数与优先搜索树组合方法的示意图 

图 5:RLGTS 与基准方法的表现比较,左图展示了求解出的非凸程序的比例,右图展示了求解出的凸程序的比例。尽管 RLGTS 能有效求解凸程序,但它们也可以通过最佳优先搜索(Best-First Search)轻松解决,因此我们将它们从我们的其它实验中移除了,因为它们不能很好地代表该方法的表现。对于长度最多到 6 的程序,最大程序长度为 6;对于长度为 10 的程序,最大程序长度为 10。

 图 6:RLGTS 和 MCMC 作为程序长度函数(左图)和允许的指令数(右图)的表现比较。随着程序长度和搜索上限之间的差异的增大,RLGTS 一直都有更好的表现。让人惊讶的是,随着程序长度的增大,MCMC 的表现仅略有甚至没有下降。随着搜索的指令数的增大,MCMC 样本效率下降得快得多。MCMC-1m 给出了当 MCMC 的超时时间增加到 100 万次尝试时的表现,其它情况都使用了 20000 次尝试的限制。

论文:Program Synthesis Through Reinforcement Learning Guided Tree Search 

论文地址:https://arxiv.org/abs/1806.02932 

摘要:程序合成是根据提供的规格生成程序的任务。传统上该任务被编程语言(PL)社区看作是一个搜索问题,近期则被机器学习(ML)社区视为一个监督学习问题。我们在这里提出另一种方法,将合成给定程序的任务当作是可通过强化学习(RL)解决的马尔可夫决策过程。根据对部分程序的状态的观察,我们试图找到一个程序,且该程序在程序和状态对上依据所提供的一个奖励度量是最优的。我们在操作浮点数的 RISC-V 汇编语言的一个子集上实例化了该方法;并且受编程语言社区使用基于搜索的技术来进行优化的启发,我们将强化学习与一种优先搜索树组合到了一起。我们评估了这个实例,并且表明了我们的组合方法相比于各种基准方法的有效性,其中包括仅保留强化学习的方法和一种在该任务上当前最佳的马尔可夫链蒙特卡罗搜索方法。

理论论文强化学习树搜索
2
相关数据
神经网络技术
Neural Network

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

深度神经网络技术
Deep neural network

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

机器学习技术
Machine Learning

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

映射技术
Mapping

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合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)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

马尔可夫链技术
Markov chain

马尔可夫链,又称离散时间马尔可夫链,因俄国数学家安德烈·马尔可夫得名,为状态空间中经过从一个状态到另一个状态的转换的随机过程。该过程要求具备“无记忆”的性质:下一状态的概率分布只能由当前状态决定,在时间序列中它前面的事件均与之无关。这种特定类型的“无记忆性”称作马尔可夫性质。

马尔可夫决策过程技术
Markov decision process

马尔可夫决策过程为决策者在随机环境下做出决策提供了数学架构模型,为动态规划与强化学习的最优化问题提供了有效的数学工具,广泛用于机器人学、自动化控制、经济学、以及工业界等领域。当我们提及马尔可夫决策过程时,我们一般特指其在离散时间中的随机控制过程:即对于每个时间节点,当该过程处于某状态(s)时,决策者可采取在该状态下被允许的任意决策(a),此后下一步系统状态将随机产生,同时回馈给决策者相应的期望值,该状态转移具有马尔可夫性质。

强化学习技术
Reinforcement learning

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

监督学习技术
Supervised learning

监督式学习(Supervised learning),是机器学习中的一个方法,可以由标记好的训练集中学到或建立一个模式(函数 / learning model),并依此模式推测新的实例。训练集是由一系列的训练范例组成,每个训练范例则由输入对象(通常是向量)和预期输出所组成。函数的输出可以是一个连续的值(称为回归分析),或是预测一个分类标签(称作分类)。

机器之心
机器之心

机器之心编辑

推荐文章
返回顶部