语法分析程序输出分析树_基于多模态数据集的程序合成

引用

Thakoor S, Shah S, Ramakrishnan G, et al. Synthesis of Programs from Multimodal Datasets[C]//Thirty-Second AAAI Conference on Artificial Intelligence. 2018.

摘要

MultiSynth 是一个基于样本多模态数据集的、用于合成领域特定程序的框架。给定一个领域特定语言(DSL)，如果 DSL 中没有一个通用于所有样本的程序，那么数据集是多模态的。此外，即使用一组程序概括数据集中的样本，这些程序的域也可能不相交，这将导致合成具有二义性。MultiSynth 是一个框架，它以最小泛化概念推动程序合成，满足了精确预测的需要。我们从以下三方面展示框架的实现过程：

(1)数据集的转换驱动分区

(2)输入和输出的广义规范的最小一般普化

(3)学习排序，估计特征权重，以便在二义性的情况下将输入映射到最合适的模式。

结果表明我们的框架能够有效应用于两种情况：在第一种情况下，我们扩展了现有的将 XML 树转换程序合成为模糊多模态数据集的方法；在第二种情况下，MultiSynth 通过学习源端句的分析树的结果排列，对机器翻译中的单词进行预排序。

1. 预备工作

我们考虑给定领域特定语言(DSL)上下文中的程序合成问题。DSL 使我们能够表示输入输出空间中的元素，并提供了让输入输出元素相互转换的机制。特别地，DSL 提供了表示输入(或输出)空间子集的语法。当输入(或输出)空间的子集可以用 DSL 表达式表示时，该表达式称为子集的泛化，子集的元素是泛化的实例。

设 E 表示输入或输出空间的子集，泛化 g 是输入(或输出)空间的一组子集的最小一般普化，如果(i)每个 Ei 都包含在 g 中，(ii)对任何 DSL 表达式 g‘，每个 Ei 都包含在 g‘中，同时 g 也包含在 g‘中。

MultiSynth 对 DSL 提供的泛化机制作出如下假设：

(i)可归纳性是自反、对称和传递的，

(ii)一组 DSL 表达式的泛化属于相同的等价类。

(iii)可归纳的两个 DSL 表达式 x 和 y 必须具有最小一般普化(LGG)。

程序 P 是一个泛化对(g，G)。P 的域是它输入泛化 g 的实例集。如果 g 包含 i，我们就说 P 包含一个输入 i。对于输入 i，程序 P 的输出是通过将 g 和 i 匹配，获得 g 中变量的绑定，并用这些绑定实例化 G 而获得的。我们还定义了程序通用性度量(GM)的概念，其中当 g 包含 g‘且 G 包含 G‘时，有 GM((g,G))>GM((g‘,G‘))。

给定数据集 D 和一组程序 S={P1…Pk}，我们将 sat(S)定义为样本 e=(I,o) ∈D 的部分，这样就存在一个程序 Pj∈S 使得 Pj(i)=o。显然，sat 是一个单调子模函数。如果 sat(S)=1，就称 S={P1…Pk}是数据集的候选集。

(i)通常只有 k>=1 的候选集存在，那么这个数据集是多模态的。在存在 k=1 的候选集的情况下，那么这个数据集是单模态的。

(ii)给定 θ∈[0,1]，如果 sat(S)>=θ，则 S 是一个 θ 候选集

2.MultiSynth 框架

为了处理数据集的多模态特性，MultiSynth 将程序与每个模式相关联，并使用函数将每个输入映射到最合适的模式上。MultiSynth 综合了一组程序和映射函数。

我们的目标是在混乱性和不确定性间取得平衡。混乱性是多模态设置的核心，而不确定性可以应用于单模态。大多数数据集是多模态的，因此对于给定的点存在许多潜在的转换，这导致了混乱性。另一方面，不确定性是一个点对应于所有可用模式的问题，这是多模态程序合成的核心问题。因此，我们在权衡中激发一种偏好，以最小化混乱性而不是不确定性。

我们将 S∗ 限制为 θ 候选集，此外，出于最小化混乱性的考虑，我们限制 S∗ 具有一般性测度 GM 的最小值。

我们使用加权线性组合对排序函数f建模。我们的优化公式表述为：

​

确定最优可行集：

考虑到泛化机制的假设，我们注意到创建的分区必须由所有属于同一等价类的点组成(见第 1 节)。在 θ=1 的特殊情况下，D 中每个点必然属于某个分区。

引理：设 θ=1，基于广义关系将数据集划分为等价类，得到最优可行集。

确定排序函数：

(i)设计和计算特征向量：领域特定特征可以是输入或单独分区的属性，或者是输入和分区之间“匹配”程度的度量。

(ii)学习排序：我们通过利用 RankSVM 公式的现有切割平面算法来学习上述特征的权重。

3.XML 转换的程序合成

现在，我们将描述我们框架中在 XML 转换领域使用的部分。其中包括 DSL、泛化机制以及排序所需的特征。

树通过以下两个操作达成泛化：

(i)允许树中某些节点称为迭代器，迭代器表示特定树表达式的任意数量的实例。

(ii)允许将字段名映射到由变量表示的无关值。

如果可以通过用具体树替换变量和用其它替换替换迭代器的方法得到，则称具体树与树表达式匹配。

一旦对数据集进行分区并将每个分区的输入输出泛化为各自的 LGG，合成算法便会推断输入和输出树表达式的变量和迭代器之间的关系。如果输出树表达式仅包含输入树表达式中的变量和迭代器，则程序成功合成。

特征：给定输入下，决定程序使用的特征如下：

(i)分区中数据点的数量

(ii-v)在对输入进行泛化之前/之后分区 LGG 中迭代器/变量的数量

(vi，vii)LGG 和输入之间匹配的迭代器和变量的数量

4.机器翻译的程序合成

我们通过学习转换输入句子分析树的规则，将预排序问题作为一个树转换问题来研究。我们将预排序规则提取问题看作是一个使用 MultiSynth 的程序合成问题。

虽然这种预排序涉及多种树转换，但为了证明 MultiSynth 在 MT 预排序中的有效性，我们将问题的范围限制在学习分析树产生级的转换上，即源端分析树的每个节点的子树排列上。这样的程序以给定分析树的产生式作为输入，以产生式的 RHS 排列作为输出。

使用标准的源端语法分析器对训练数据进行预处理，得到源端和目标端句子的语法树，并以源树为参考自下而上构造目标树。此外，所有产生式，它们的特征和对应的理想排列都作为合成器的训练数据集。

DSL&泛化：使用产生式级排列的语法树转换的 DSL 包括以下内容：

(i)终结符，非终结符和变量。一个产生式在 LHS 中有一个非终结符，在 RHS 中有一个终结符/非终结符序列，该产生式还定义了语言的语法规则。语法树的根是表示句子的非终结符。对于任何父节点及其有序的子节点列表，必须存在包含作为 LHS 的父节点和作为 RHS 的子节点的一个有效产生式。

(ii)泛化树是一个语法树，其叶子是终结符或变量

(iii)原始操作的集合，这些操作时不同产生式的所有可能排列

我们的泛化机制如下：给定两棵树 t1,t2，设 G(t1,t2)表示 t1 和 t2 的泛化。设 r(c1…c

n)表示以 r 为根节点的树，其子节点和子树用 c1…cn 表示。接着 G(r1(C1…Cn),r2(d1…dm))，由以下递归定义给出：

(i)如果 r1=r2 且 n=m，r1(G(c1,d1)…G(cn,dn))

(ii)否则，则为能从{r1,r2}中取值的变量 X

上述定义也可以扩展到对一组树的泛化。

节点是语法树中的非终端或终端。我们将树中节点的子树定义为该节点的内容。节点的内容是一个元组，由其父节点，父节点的子节点列表和一个表示列表中节点索引的整数组成。节点的深度是它和语法树根节点的距离。

特征：将给定测试输入与候选分区之间匹配程度的度量作为特征：

(f1)包容指示：一个二进制值，指示测试输入产生式的内容是否被候选分区中点内容的 LGG 包含

(f2)匹配分数：介于 0-1 之间的值，指示测试输入内容在候选分区中点的 LGG 内容中的包含程度

(f3)相对频率：候选分区的大小与所有候选分区总大小的比值

(f4)给定输入产生式下候选分区的数量

(f5)输入分析树中输入产生式的相对深度

(f6)内容指示：二进制值，指示内容是否在候选产生式的内容列表中

(f7)内容频率：与测试输入含有相同内容的候选分区中训练实例的数量

5.结论与未来工作

本文的具体贡献是(1)结合 LGG，实现多模态数据集泛化程序的有效合成。(2)以两个应用领域为例，证明在混乱数据点上学习排序的有效性。在以后的工作中，我们可以考虑在 θ<1 时多模态程序的合成问题。

致谢

国家重点研发计划课题：基于协同编程现场的智能实时质量提升方法与技术(2018YFB1003901)和国家自然科学基金项目：基于可理解信息融合的人机协同移动应用测试研究(61802171)

本文由南京大学软件学院 2020 级硕士袁博翻译转述。