引用：
Christakopoulou, K., & Kalai, A. T. (2017). Glass-Box Program Synthesis: A Machine Learning Approach. arXiv preprint arXiv:1709.08669.
一、摘要
最近提出的从数据中学习编写计算机程序的模型，使用的是输入/输出实例或丰富的执行痕迹。相反，我们认为一个新的替代方法是使用一个 Glass-Box 损失函数，作为一个可以直接检查的程序本身给出。Glass-Box 优化涵盖了广泛的问题，从计算两个整数的最大公除数，到元学习问题。
在本文中，我们提出了一个智能搜索系统，它可以在给定部分程序和 Glass-Box 问题时学习程序空间上的概率。实证证明，我们的智能搜索过程与蛮力程序搜索相比，在准确度和时间上都有明显的改进。在我们的实验中，我们使用了受数字理论、文本处理和代数启发的丰富的无上下文语法。我们的结果表明，(i)执行 4 轮我们的框架通常可以解决大约 70%的目标问题，(ii)我们的框架即使在领域不可知的情况下也可以自我改进，(iii)它可以解决那些本来用蛮力搜索会太慢的问题。
二、介绍
对于计算机来说，要想对计算机进行编程，我们必须首先解决如何编程以表示问题和如何评价性能的问题。在程序合成领域，指定问题的方法主要有两种。(a)通过样例。Gulwani 等人在 2012 年的例子里，其中提供一些输入输出对(xi, yi)作为输入，目标是输出一个满足 f(xi)=yi 的函数 f，同时可能最小化其他标准(如短)；(b)通过规范。Manna 等人在 1980 年的研究中，其中给出一些特定语言的形式化规范。更一般地说，任何合成程序都有一个效用(有用性得分)。假设这个效用函数可以写成一个程序打分程序，我们提出的方法是让合成直接访问打分程序的源代码。(c)程序合成作为优化 Glass-Box 程序评分目标，Glass-Box 评分讲用于评价程序合成。在本文中，我们通过设计一个系统来说明 Glass-Box 程序合成方法的潜力，该系统可以学习合成程序，使各种 Glass-Box 目标的相应效用最大化。
Glass-Box 程序合成。
为了更好地理解 Glass-Box 的表示方法，可以考虑一个程序综合竞赛。在人类之间的编程竞赛中，问题往往是用英文描述的，并由自动评分程序根据其在某些输入上的输出(以及其他因素，如运行时间和提交时间)自动评分。当然，计算机很难理解英文描述，因此，我们提出通过评分程序的源代码向综合系统描述问题。在这种 "Glass-Box "模型中，不需要单独的问题描述或例子，只需要评分程序。如图 1 所示，如果问题是寻找字符串中出现频率最高的字符，那么一个程序输出字符串 x 上的字符 y 的得分就是 y 在 x 中出现的次数，总得分就是其在一些随机生成的字符串上的得分之和。需要注意的是，如果要用输入输出的例子来指定问题(图 1 上)，就需要在几个例子上解决问题，而且可能存在歧义，因为可能有多个不同的函数 f 将 x 映射到 y 上。
在把编程问题投向优化 Glass-Box 程序评分程序时，必须写出一个程序，精确定义合成程序的分数/效用。然而，这可以说是在一般情况下提出问题的必要步骤，而不仅仅是针对编程竞赛。术语 Glass-Box 与黑盒访问形成对比。黑盒访问将意味着能够在没有访问任何其他评分程序的情况下对任意程序进行评分。当然，Glass-Box 访问至少和黑盒访问一样强大，因为人们可以运行评分程序本身。可以应用 Glass-Box 程序合成的几种情况是：
传统的优化问题，如线性编程或旅行商问题(目标是出行的长度)。
数字理论问题，如最大公除法(GCD)或因子法。这些问题可以有效地进行评分，因为它很容易验证因数和基本性。
-例题编程(PBE)。在这种情况下，一个程序 P 通过其将固定的输入 xi 映射到输出 P(xi)=yi 的精度进行评分，并结合一个正则化项，例如，-λ(程序长度)，以防止过度拟合。
-在模拟中优化算法的性能。一个例子是设计一个网络协议，在网络模拟器中进行评估。在这种情况下，评分程序可以测量大型网络中的性能。
元优化，学会学习以学习。合成程序合成的问题本身可以以元评分器的形式提出，它从不同领域生成问题(即评分器)，在这些问题上运行候选综合程序，并对产生的程序分数进行平均。
通过对合成问题的学习来合成解决方案
在定义了编程问题的表示和评估之后，我们通过一个学习合成程序的系统来证明这种方法的可行性。就像运动员做各种练习来提高运动成绩一样，程序合成系统可以通过练习和学习合成各种问题的解决方案来提高。Menon 等人(2013)将一种机器学习(ML)方法引入到 PBE 合成，学习跨问题的合成。由于他们的真实世界问题库相对较小，他们选择了少量适合文本处理 PBE 的特征。
为了绕过这种数据的不足，我们生成了自己的问题，然后用这些问题来练习综合解决。特别是，一旦我们有了一组练习问题，我们就会按照 Menon 等人(2013)的做法，通过交错搜索和训练一个基于逻辑回归的模型来反复寻找这些问题的改进方案，该模型可以智能地引导搜索。回想一下，在 Glass-Box 合成中，一个问题就是一个评分函数，所以我们立即知道如何对任何合成程序进行评分。Balog 等人(2016)独立引入了类似的创建人造问题的方法。这项工作和我们的两个关键区别是，他们进行 PBE 合成，而我们进行 Glass-Box 合成；他们利用深度学习，而我们利用多类逻辑回归。
实验
我们表明在实践中，有可能合成一些感兴趣的问题的解决方案(例如 GCD)，而用朴素法会慢得令人望而却步。此外，我们还展示了我们的 Glass-Box 程序合成系统(GlassPS)即使在领域不可知的框架中也可以改进自己，其中考虑了来自不同领域的语法的联合。因此即使使用特定领域的语法可以取得更好的结果。
贡献
在本文中，我们将学习合成编程问题的成功解形式化为一个机器学习问题，使用 Glass-Box 优化。我们的主要贡献有三个方面。
我们引入了 Glass-Box 程序评分程序作为指定问题的一种新的选择。
我们通过综合实践问题和问题之间的学习模式以及截至目前发现的解决方案，正式确立了 Glass-Box 优化的机器学习框架。
我们提出了实验，证明了我们的框架能够学习生成跨领域的形式良好的 python 程序。
三、提出的框架
自然而然地，我们会尝试学习基于问题和解决方案对的集合来合成程序。要做到这一点，人们最好能获得大量的问题和解决方案程序的样本库。Menon 等人(2013)为文本处理 PBE 提供了一个小型的问题/解决方案对集。由于该集相对较小，他们使用领域知识来构建少量的手工编码特征进行学习。
相反，与 Balog 等人(2016)类似，我们合成了自己的练习问题，并合成了这些问题的解决方案。在我们的 Glass-Box 合成方法中，这相当于合成评分器即 Glass-Box 问题。对于每一个这样的评分者，我们都会合成一些针对该评分者的解题方案，并选择得分最高的方案。然后，我们从这些问题-解决方案对的集合中学习，以改进合成中使用的模型。我们通过交错搜索和训练一个有助于智能引导搜索的模型，反复寻找这些问题的改进方案。我们的框架概述如图 2 所示。
四、练习/测试问题集的结果
为了实证评估我们提出的框架，我们分别在两个实验设置下进行了实验。在第一个设置下，我们考虑了无上下文语法，只考虑了与我们试图解决的问题相关的语法，例如，对于解决字符串问题，我们考虑了字符串 CFG 等等。在第二个设置中，我们取了四个不同领域的所有语法规则的联合，并考虑了四个领域中每个领域的 250 个问题。我们将此称为全域实验。
对于第一个设置，我们考虑了 1,000 个练习训练问题和 100 个测试问题。我们逐步进行了四轮训练，因为更多的轮次似乎并没有提高学习效果。每轮训练运行 45 分钟。我们在图 4(a-c)中显示了随着学习轮次从 0 到 4 的进展，GlassPS 解决的练习火车/测试问题的分数。我们可以看到，执行 4 轮我们的框架通常可以解决大约 70% 的目标问题。字符串领域没有显示出来，因为每一轮甚至在学习之前都解决了 100%的问题。
对于第二种设置，我们在图 4(d)中显示了结果。为了达到与第一种设置中相似的训练/测试问题解决比例，每轮训练运行了双倍时间，即 90 分钟而不是 45 分钟。我们的结论是，虽然特定领域的学习可以取得更好的结果，但全领域实验是一个概念验证实验，即使不知道领域，GlassPS 也可以随着时间的推移而改进自己。
五、结论
在本文中，我们引入了一个学习编写计算机程序的通用框架，以使 Glass-Box 目标函数的得分最大化。我们将其表述为一个机器学习问题，作为一个概念证明，表明一个简单的分类器如逻辑回归，可以成功地学习评分程序的特征，以及生成的待评分解程序的特征之间的模式。我们已经通过实验表明，我们的框架可以随着时间的推移学习生成跨领域解决问题的 python 类型代码，即使我们没有提供类型，我们也没有提供每个问题来自的领域类型的访问权限。虽然学习肯定可以改进(例如使用深度学习)，但该方法被证明是健全的并且在某种程度上足够灵活，可以在一个系统中结合多个领域的综合。这为学习解决问题的多域学习系统开辟了有趣的方向。
致谢
本文由南京大学软件学院 2020 级硕士研究生唐昊杰翻译转述