智能在程序合成研究中遇到的提取任务上的评估

智能在程序合成研究中遇到的提取任务上的评估

　　报价

　　Raza，M.＆Gulwani，S ..（201 7)。使用预测程序合成的自动数据提取。AAAI201 7.

　　一、摘要

　　近年来，人们对使用示例编程技术来帮助用户完成数据处理任务越来越感兴趣。该技术依靠用户定义的输入和输出实例规范来自动合成程序。但是，在各种各样的数据提取任务中，人类观察者仅需要观察输入数据本身即可轻松预测所需的提取结果。在程序综合研究中还没有探索这种预测智能，这也是我们在这项工作中要解决的问题。我们描述了一种预测性程序合成算法，该算法可以仅以输入示例为例，以提取DSL（域特定语言）的一般形式导出程序。我们在文本提取和网络提取这两个实际应用领域中描述了此类DSL和合成算法的具体示例，并介绍了我们的技术来评估一系列实践中遇到的提取任务。

　　二、简介

　　随着世界数据的不断增长，近年来，学术界和工业界对使用自动编程技术解决数据纠缠问题越来越感兴趣：数据科学家面临的挑战是如何处理来自不同领域的*敏*感*词*来源。各种格式的数据，并将这些原创数据转换为适合其分析工具的形式。数据预处理是一项耗时的活动（在某些情况下，多达80％的活动（Kandel等，2011）），并且通常需要具备编程技能才能编写强大的提取或转换脚本。

　　这也是自动生成此类程序的一个非常有利的地方-它不仅加快了数据排序过程的速度，而且还允许非熟练程序员的数据分析人员和知识工作者使用它。与数据处理中不透明的自动推理技术相比，用户对推断的转换了解甚少，并且自动程序合成是可重用的（一次性学习轻量级脚本，以后可以存储并应用于类似的数据集） ），以及透明性和可编辑性的优点：转换是受经典编程语言启发的程序，必要时可以手动进行编辑。

　　为了实现此目标，许多作品都通过示例（PBE）方法探索了各种编程方法。在PBE中，用户可以通过提供一些输入和输出示例来指定他们的预期任务，然后系统尝试自动生成符合给定示例的特定领域语言（DSL）程序。在该领域的显着商业成功是基于PBE技术的Microsoft Excel中的Flash Fill功能。

　　但是，PBE方法依赖于用户要执行的任务的明确意图规范，这通常需要用户正确理解示例以帮助系统推断正确的程序，并且还可能需要许多用户。任务类型花费大量的精力。在这项工作中，我们发现并解决了各种数据提取任务。该系统可以在没有明确的示例规范的情况下运行，并且仅基于输入数据的属性以纯预测性的方式生成提取脚本。因此，这可以视为仅从输入实例而不是输入和输出实例进行推断。我们首先在这里研究的两个特定应用领域中说明这种提取方案，然后再更详细地讨论预测方法及其好处。

　　文本提取

　　图1显示了一种文本提取方案，其中输入数据集（如上所示）收录来自Web服务器日志的条目。每行是一个文本字符串，其中收录客户端IP地址，日期和其他值，这些值由此日志格式唯一的各种分隔区域分隔。我们的目标是将这些值提取到单独的列中，如图底部表格所示，其中突出显示了代表单独区域的列。

　　在诸如CSV之类的简单文本格式中，此提取任务相对简单，因为通常使用固定的单字符定界符来分隔数据值。但是通常，如图1所示，可以在同一数据集中使用任意数量的字符串定界符，并且某些地方甚至某些地方甚至可以使用特定的字符串作为定界符，而在其他地方则不使用。例如，在图1中，“ /”字符是分隔HTTP协议版本的分隔符，但不应在URL中用作分隔符。因此，不可能简单地将所有出现的特定字符串分开。实际上，在许多情况下，两个数据值之间实际上没有分隔符。例如，图2在Excel帮助论坛上显示了一个用户的提取任务，该用户正在尝试将具有很大变化的数据集中的值和度量单位分开。在这种情况下，显然没有定界字符，因此我们的目标实际上是找到零长度定界区域，该区域是字符串中的单点，由左侧数字和右侧字母的上下文定义。

　　网页提取

　　自动数据提取的另一个领域是从网页中提取表信息，尤其是在网页中没有显式可视化（逐列）表的情况下。例如，图3显示了提取Amazon产品搜索结果的任务。每个结果项都有许多字段，例如标题，日期，各种价格等。这些字段未按清晰的逐行列表排列。其中一些字段丢失。在网页的DOM（文档对象模型）树结构中，使用不同的格式属性代替简单的HTML表格标签来表示它们。而且某些字段（例如“新”和“二手”的价格）实际上在格式上是相同的，并且只能通过检查文本内容来区分。

　　因此，由于每个网站使用不同形式的信息表示，因此在每种情况下都需要特殊的提取脚本。尽管基于特定标签或视觉属性进行自动表检测的工作很多，但是大多数非视觉表的提取都是在用户提供的示例的帮助下进行的。

　　预测性程序综合

　　以上提取方案已通过各种PBE方法解决，这些方法要求用户通过特定的提取示例来说明其意图。但是，在所有这些情况下，人们都可以通过观察输入数据本身轻松地预测所需的提取，而无需告知要提取什么。在程序综合研究中尚未探索这种预测智能，这是我们在此工作中要解决的问题：从仅输入示例中自动学习和提取程序。与以前基于PBE的技术相比，我们在此提出的预测方法具有许多优势。

　　我们首先定义了用于执行数据提取的DSL的一般形式。以这种形式，程序被构造为具有不同数据字段的独立子例程的组合。我们使用为文本和Web提取字段设计的特定DSL来说明这一点。这些DSL基于经典语言，例如正则表达式和CSS（级联样式表）选择器，它们可以表达上述场景中描述的一系列转换。然后，我们描述了一种新颖的预测综合算法，用于针对给定的输入数据集推断提取DSL中的程序。这是一个与领域无关的算法。它通过生成语义上等效的程序以有效的自下而上的方式运行，并使用子程序之间的对应关系概念作为中心排序原则。我们描述了该算法的特定示例以及文本和网络域之间的排名关系，并描述了我们的技术对从日志文件，真实用户和网络获得的实际测试场景的评估。最后，我们讨论了结论和未来的工作。

　　三、 ColumnSplit的评估评估

　　为了在文本域中进行评估，我们从产品团队，帮助论坛和组织中的真实用户那里采集了20个基准案例集，这些用户为我们提供了他们想要提取的数据集。其中许多数据集来自各种日志文件，例如Web服务器，但它们还包括其他基于文本的数据集。我们评估的目的是测量系统可以提取的最大字段数。

　　我们的系统在这些基准上的平均性能结果如图9所示。每个数据集的平均值为1 3. 95个字段，其中第一次尝试检测到1 0. 3个字段，[通过进一步拆分一些列来提取k30] 45个字段（在任何测试情况下，最多需要拆分三层），根本无法提取0. 2个字段。所有未提取的字段都在一个测试用例中，这是一项在不同输入上涉及不同数量字段的任务。对于可能遗漏的这种类型的字段，通常无法确定所需的字段对齐方式，因为存在不同的选择，因此可以通过用户的某个输出规范（例如示例）来最好地处理此类任务。每个任务的平均执行时间为4. 2秒，并在2秒内完成16个任务。可以观察到，在综合算法的每次迭代中，内存使用量大约增加了一倍，仍处于可容忍的范围内，因为该算法仅在给定的输入状态价格下保持程序的状态空间为语义等。

　　为了进行比较，我们还评估了我们的系统，而没有使用原创文本第3节中描述的特定于操作员的提升功能，并且观察到执行时间急剧增加，每个任务平均需要210秒。我们还研究了系统对提供给DSL Lt的标准数据类型标签的依赖性，并仅使用5个基本正则表达式标签（数字，小写字母，大写字母，字母数字和特殊字符）进行了重新实验。我们发现，在20个测试用例中，与其他案例中的大多数字段一样，提取了14个案例中的所有字段。

　　WebExtract的评估

<p>在提取网页的情况下，我们对20个网页的集合进行了系统评估。这些网页中收录的表格数据未由显式HTML表格标记表示。评估结果如图10所示。我们的系统平均每页提取5. 85个字段。但是，页面上的某些（0. 9)字段未提取为单独的字段，而是“分类为”其他字段（例如，父节点收录两个具有不同字段的子节点，但被提取为字段）。 ）。平均0.的25个字段完全没有提取，这仅发生在4个网页中。每个任务的平均执行时间为6. 41秒，尽管在2秒钟内完成了15个任务。提升了过滤器运算符的功能，执行时间增加到27秒，再次显示出明显的性能下降，以及为什么以前的自下而上的综合方法无法用于我们的预测环境（无论是文本区域还是网页区域）。