神经网络从其执行轨迹的图像中模拟排序算法

神经网络在诸如计算机视觉，自然语言处理等各个领域的适用性方面的最新进展，引起了人们对程序归纳方法的兴趣。 （Kitzelman [1]，Gulwani等人[2]或Kant [3]。）

执行程序归纳任务时，在所有可能将输入映射到输出的可能程序中搜索是不可行的，因为可能的指令组合或指令序列的数量过多：至少基于生成的程序长度呈指数增长。而且，不存在制定这样的程序归纳任务的通用框架，并且当前的计算限制不允许在计算机程序生成领域中非常广泛的机器学习应用。

在这项研究中，我们分析了执行跟踪作为程序归纳设置中神经网络模型的学习表示形式的有效性。我们的目标是生成程序执行动态的可视化效果，尤其是排序算法的可视化效果，并在它们上应用机器学习技术以捕获其语义并使用神经网络模拟其行为。

我们首先对在有限数量的数组上工作的算法（例如各种排序和数据结构算法）的执行轨迹图像进行分类。接下来，我们尝试检测较大程序的跟踪序列内的子程序模式。最后一步是预测执行各种排序算法的未来步骤。更具体地说，我们尝试通过观察它们的执行轨迹来模拟它们的行为。我们还将讨论对其他类别程序的概括，例如1-D细胞自动机。

我们的实验表明，如果将足够的执行跟踪作为数据提供，则神经网络能够对简单算法的基础机制进行建模。我们将程序归纳模型的性能与Graves等人的其他类似实验结果进行了比较。 [4]和Vinyals等。 [5]。我们还能够证明排序算法既可以视为显示空间模式的图像，也可以视为领域特定语言的顺序指令，例如交换两个元素。我们针对三种难度越来越大的任务测试了我们的方法：检测，识别和仿真。

我们证明了可以使用神经网络对简单算法进行建模，并提供一种方法来将特定类的程序表示为特定领域语言中的图像或指令序列，以便神经网络可以学习其行为。我们考虑了各种设置的复杂性，以便根据数据表示类型进行一些改进。我们从实验中获得的见识可用于设计更好的程序归纳模型。

查看全文