使用学习概率模型加速基于搜索的程序合成

众所周知，预期程序中包含重复和可预测的模式。在此基础上，我们提出了一种加速基于搜索的程序合成的新方法。我们的技术核心是学习程序的概率模型并用它来引导搜索。为此，我们的方法模块化地解决了两个问题：（1）如何引导给定概率模型的搜索 （2）如何学习得出良好的概率模型。

我们以标准公式(SyGus)为目标解决第一个问题。SyGus 建立了各种合成基准，使用上下文无关文法来描述可能的程序空间。我们利用概率模型对该文法进行了拓展。在无限加权图中，我们将程序的似然枚举问题归结为源节点到目标节点间的最短距离问题。我们使用 A*搜索算法有效地解决了这一问题，同时还展示了如何为给定的文法和概率模型自动导出启发式函数。

我们以概率高阶模型（PHOG）为目标解决第二个问题。PHOG 模型通过允许对除了父非终结符以外的每个产生规则进行条件化来对概率上下文无关文法进行概括。因此，它可以捕获丰富的上下文来有效地对可能的和不可能的程序进行区分。现有的技术已经了解决一些合成问题，提供了一些解决方案，我们就利用这些已知的解决方案进行模型学习。但在这些合成问题中，如果直接进行学习，得出的模型通常会具有规范过拟合的问题。我们提出了新的基于迁移学习的学习方法。该方法从规范的特征中学习模型，这些特征由领域专家提出。

2. 加权搜索算法

在这一部分中，我们对基于 A*搜索的加权搜索算法进行描述。我们首先用带有概率程序模型的 CEGIS 过程来阐述基于搜索的合成问题；然后，我们提出一个基本算法来对可能的候选解决方案进行优先级排序；最后，我们使用两个广泛应用于现有搜索策略的正交优化来扩展该算法。

2.1 带引导搜索的 CEGIS

统计程序模型：上下文无关文法 G 的统计程序模型 Gq = ⟨G,C,p,q⟩是由 G 生成的语言构成的程序的概率分布，其中 C 是有限条件集，p 是函数，q 是根据给定规则从而形成概率分布。换句话说，上下文可以通过在当前句型上应用函数 p 来计算，并且允许对概率相关的下一条产生规则的扩展进行条件化处理。

算法 1 采用了统计程序模型来引导搜索：

算法 1

2.2 加权枚举搜索

2.2.1 简述

加权有向图由一组顶点和一组具有实值权重的边组成。我们的加权枚举算法将对句型的加权有向图进行操作，该图由一个开始节点 S 和（可能）无限个目标节点组成，它们都是 P 中的程序。

2.2.2 基于 A*的搜索

我们对句型的派生图使用 A*搜索，见算法 2。该算法除了为抽象过程 WEIGHTED_SEARCH 提供了必需的输入外，还提供了一个启发式函数 g 作为算法的输入。对于一个给定的统计程序模型，启发式函数可以一次性自动导出，并在整个搜索过程中使用。

​

算法 2

2.2.3 启发式函数

理想情况下，如果我们对每个节点 n 使用精确的距离，那么我们能得到最好的性能。但是，由于从 n 可能到达无限多个目标节点，因此我们无法对所有节点进行求值。直观地说，我们在不考虑影响未来产生式的上下文的情况下对猜测的未来距离进行计算。函数 g 定义如下：

​

其中 ni 指的是句型 n 中第 i 个符号。对于非终结符号 A∈N，h(A)表示可从 A 导出的表达式的概率上界。对所有 A∈N，h(A)应满足以下条件：

​

总之，我们的启发式函数 g 总是低于精确的未来距离。

2.3 优化

在这一节中，我们将说明如何将现有搜索策略中广泛采用的两个强大正交优化技术结合到基本算法中。

2.3.1 等价类修剪

程序等价类概念广泛应用于现有的枚举搜索策略，而句型等价类则是它的拓展。我们在方法中应用句型等价类概念进一步提升搜索效率。

定义 3（句型的等价性）：对于一个给定句型的派生图和输入集 pts，如果从 ni 到 nj 派生的所有程序对(Pi,Pj)分别具有与 pts 相同的输入-输出行为，则两个句型是以 pts 为模等价。形式上：

一般来说，计算上述等价关系是不可能的，因为从给定的句型可以衍生出无限个程序。因此，我们进一步使用下面的关系进行计算。

定义 4（句型的弱等价性）对于一个给定句型的派生图和输入集 pts，如果 ni=nj 或

其中<表示子序列关系，则两个句型是以 pts 为模等价。

2.3.3 分治枚举

当我们想要合成有条件程序时，我们可以采用分治枚举的方法来进一步提高搜索效率。这种方法允许合成大型条件表达式，其思想是找到适用于不同输入子集的不同表达式，并将它们统一为适用于所有输入的解决方案。使用枚举找到子表达式，然后使用决策树学习将其统一到程序中。

算法 3 描述了使用分治策略的加权枚举。它采用了两种统计程序模型。这意味着我们需要分别使用这两种文法训练两个统计模型。

算法 3

3.PHOGs 的迁移学习

在这一节中，我们介绍了一种学习 PHOGs 的新方法，它可以很好地推广到具有不同概率分布解的合成问题中。下面首先对 PHOG 进行初步介绍，然后介绍我们的迁移学习方法。

我们提出了基于迁移学习的学习方法。当训练数据和测试数据遵循不同的概率分布时，迁移学习是一个有用的技术。在我们的场景中，训练数据和测试数据是由上下文无关文法 G 定义的搜索空间*P*的合成问题的解。

迁移学习减少了训练数据和测试数据的概率分布之间的差异。我们找到并构造了一个公共空间(*P*除外)，其中与训练数据有关的元素的概率分布和与测试数据有关的元素的概率分布接近。

为此，我们设计了一个特征映射，将*P*中程序转移到另一个空间，在这个空间中找到训练数据和测试数据的共同特征。新空间也由上下文无关文法定义，称为 pivot 文法。我们为 pivot 文法学习了统计程序模型，该模型评估给定测试实例的概率。

在引导搜索一个新的合成问题的解时，我们将学习到的 pivot PHOG 用于统计模型。回想一下，在加权搜索算法中我们使用了统计程序模型 Gq。现在我们使用一个统计模型，该模型来自于 pivot 文法，已知现有句型 s，q 指定下一个可能产生式的概率，如下：

​

其中 η∈[0,1]是使概率之和为 1 的系数。由相同特征规则实例化来的规则被赋予相同的概率。

4. 结论

我们提出了一种加速基于搜索的程序合成的一般方法，该方法利用概率程序模型来引导搜索，使搜索朝向预期的程序。我们的方法包括一个适用于广泛的概率模型的加权搜索算法。我们还提出了一种基于迁移学习的方法，避免了新产生的概率模型 PHOG 出现过拟合问题。我们从不同的应用领域证明了该方法对大量合成问题的有效性。实验结果表明，我们的方法优于现有的通用领域和特定领域的合成工具。