excel表格_excel函数公式大全_execl从入门到精通
AAAI 2017｜北航：神经网络示例编程2024-07-05 22:42:48
AAAI 2017 Machine Learning Applications
神经网络示例编程
Neural Programming by Example
北京航空航天大学
Beihang University
【摘要】示例编程(PBE)的目标是自动推断计算机程序，从简单的输入和输出中完成某个任务。在本文中，我们提出了一种基于深度神经网络DNN(Deep Neural Networks)的神经网络示例编程(NPBE)，该模型可以从输入输出的字符串中学习，并能诱导解决字符串处理问题的程序。我们的NPBE模型有四个基于神经网络的组件：一个字符串编码器、一个输入输出分析器、一个程序生成器和一个符号选择器。我们在电子制表软件系统中通过训练它端到端地解决一些常见的字符串处理问题的处理来展示NPBE的有效性。结果表明，该模型能有效地诱导字符串操作程序。我们的工作是向教授DNN生成计算机程序的一步。
1 引言
示例编程(Programmingby Example，PBE，也称为通过演示进行编程，或归纳合成)(Lieberman2001; Cypher and Halbert 1993; Gulwani 2011)给机器提供了推理和生成新程序的能力，而不需要大量的人力监督。在PBE系统中，用户(通常是非专业的程序员)提供了一个含有他们想要执行的任务的输入输出示例的机器，该机器能自动为完成任务推理一个程序。PBE的概念已经成功应用于电子制表软件系统，如MicrosoftExcel (Gulwani et al. 2015)、计算机辅助教育(Gulwani2014)和数据提取系统(Le和Gulwani 2014)。
例如，如果用户提供以下输入和输出示例：
john@example.coimjohn
james@company.com james
PBE系统应该理解用户想从电子邮件地址提取用户名。它会自动地合成一个程序Select(Split(x，@)，0)，其中x是输入字符串，拆分Split是根据分隔符拆分一个字符串，选择Select是从字符串数组中选择一个子字符串。如果有一个新的电子邮件地址jacob@test.com，这个程序将输出字符串jacob。
Lau等(2003)应用版本空间代数来寻找可能的程序。最近的PBE方法(Gulwani 2011)主要采用搜索技术来查找满足输入输出示例的预定义函数的组合(如字符串拆分和连接)。这些方法创建了一个有向无环图(DAG)，并搜索可以从给定输入状态生成输出字符串的函数序列。这些方法可以有效地生成复杂的字符串处理程序，但需要复杂的程序合成算法的设计。
在本文中，我们提出了一种基于DNN的示例编程方法。我们训练神经网络使其能自动从输入输出的例子中推断程序。在过去的几年里，DNN的研究在计算机视觉(Krizhevsky,Sutskever,Hinton2012)、语音识别(Mohamed,Dahl, Hinton 2012)，自然语言处理(UNKbert et al. 2011)和APIlearning(Gu et al. 2016)等多种领域取得了显著的成果。最近，研究人员已经探索了应用DNN解决编程和计算相关问题的可行性(Neelakantan, Le, and Sutskever 2015; Reedand de Freitas 2015; Graves, Wayne, and Danihelka 2014; Kurach, Andrychowicz,and Sutskever 2015)。我们的工作是基于类似的想法，即应用DNN来推断和执行计算机程序。不同于现有的工作，我们将目标对准PBE问题，并对输入、输出和程序三元组的神经网络PBE模型进行训练。
我们的方法，称为NPBE(NeuralProgramming by Example，它教DNN为字符串操作编写一组预定义的原子操作。给定一个输入输出字符串对，NPBE模型被训练成合成一个程序——一系列函数和相应的参数，将输入字符串转换为输出字符串。这个程序是由原子函数生成的，一个函数可以使用以前一个函数的执行结果。因此，该模型能够仅使用几个预定义的操作组成复杂的程序。
我们已经在大量的输入输出字符串上为45个字符串操作任务对NPBE进行了大量的实验评估，结果令人鼓舞。我们发现我们的模型可以泛化超越训练输入/输出字符串和训练参数设置。我们的工作是将DNN应用于编程问题的早期尝试之一。
2 相关工作
Reed等人(2015)开发了一种名为神经网络编程解释器的框架，通过神经网络来诱导和执行程序。他们的方法把程序当作嵌入，使用神经网络来生成程序执行的函数和参数。他们的模型接受了执行跟踪的训练，并且可以在许多不同的场景中使用。然而，他们的模型不能直接应用于PBE的问题，因为他们的模型的输入是由任务编码的环境，而我们的工作是致力于PBE，而且我们的模型的输入是输入-输出的例子。
神经网络程序员(Neelakantan,Le, and Sutskever 2015)是一种神经网络，可以通过几个步骤来调用一组操作来增强。它被训练用于输出程序执行的结果，而我们的模型被训练成输出由符号表示的程序。NeuralEnquirer (Yin et al. 2015)是一个完全神经网络的端到端微分模型，能够建模和执行表查询相关程序。在数据表上使用神经网络，神经网络询问器的执行是“柔和”的，而我们的工作并不适用于输入输出字符串的软执行。Bosnjak等(2016)提出了一种用于语言等的抽象机器的神经网络实现。它可以从输入输出数据的训练中学习程序的行为。然而，它需要程序草图作为输入。
我们的模型也与使用递归神经网络解决编程和计算相关问题的工作有关。Graveset al .(2014)开发了一种神经网络图灵机，它能够通过外部存储器学习和执行简单的程序。Zarembaet al .(2015)使用执行跟踪来训练递归神经网络学习简单的算法。Linget al .(2016)开发了一种从自然语言和结构化规范中生成程序代码的模型。指针网络PointerNetworks (Vinyals, Fortunato, Jaitly 2015)使用一个关注的递归模型来解决复杂的算法问题。
有一些机器学习方法用于解决PBE问题。Lau等(2003)应用版本空间代数，有效地搜索可能的程序。根据输入输出对，遗传编程(Banzhafet al. 1998)可以从候选群体中演化出有用的程序。Liang等(2010)提出了一种采用分层贝叶斯方法在给定的例子中来学习简单程序的方法。Melon等(2013)使用机器学习，通过学习与文本特征相关的权重来加速搜索可能的程序。他们的方法需要精心设计的特性来减少搜索空间，而我们的方法则减少了搜索空间，并通过DNN的学习表示避免了特征工程。
3 NPBE模型
问题声明：让S表示字符串的集合。对于输入字符串x∈S和输出字符串y∈S，我们的模型是引入一个函数f∈SS，所以y=f(x)。我们的模型的输入是输入输出对z:=(x,y)∈S2，我们希望得到正确的函数f，使得当用户输入另一个字符串∈S,我们可以生成所需的输出，而不需要用户显式指定函数。
图1 NPBE总体架构
本文提出的NPBE模型(图1)由四个模块组成：
一个字符串编码用于对输入和输出字符串进行编码；
一个输入输出分析器，它生成描述输入和输出字符串之间关系的转换嵌入；
一个程序生成器，它可以在几个步骤中生成函数/参数嵌入；
一个符号选择器来解码函数/参数嵌入并生成人类可读的符号。
程序生成器将运行几个步骤，每个步骤都可以访问先前步骤的输出，从而使模型能够仅使用一些预定义的原子函数来组成强大的程序。而传统的深度学习模型试图对给定的x生成输出y，并最终拟合出函数f使得y=f(x)，我们的模型直接学习生成函数f，并拟合出高阶函数g使得f = g(x,y)且f满足y = f(x)。
3.1 字符串编码器
给定一个由一系列字符{i1, i2，…iL}组成的字符串，字符串编码器输出一个字符串嵌入和一个字符嵌入列表。首先，通过随机初始化和可训练的嵌入矩阵，将序列中的每个字符ik映射到8维原始嵌入e(ik)。为了更好地呈现和处理一个字符，每个字符的上下文都与字符的原始嵌入相融合，以构建字符嵌入。让l(ik)表示字符ik的左上下文和r(ik)作为ik的右上下文。l(ik)和r(ik)分别用式(1)和式(2)计算得到l(0)= r(L + 1)=[0]c。在我们的实施中，fl和fr是LSTM(Hochreiter和Schmid - huber 1997)的更新函数。
每个字符的字符嵌入是字符ik和e(ik)的左/右上下文的组合，如式(3)所示，其中[;]表示向量的连接，max是点集最大池element-wisemax-pooling。We和be是构建全字符嵌入的参数矩阵和矢量。
Ck将会被程序生成器的注意力机制所使用。
我们还需要一个可以总结整个字符串的表示，这样我们就可以从输入和输出字符串的字符串嵌入中诱导转换。我们使用多层双向LSTM(Graves和schmidthuber 2005)来概况Ck。每一层的前向和后向LSTM的输出被连接并成为下一层的前向和后向LSTM的输入。将前向和后向LSTM的前几层的最后一个隐藏状态进行合并，通过一个最后的全连接层产生字符串嵌入s∈RS。输入和输出字符串的处理是分开但同享同一个神经网络架构和参数，因此对输入和输出字符分别生成cI,1,……,cI,L, sI和co,1,……co,L, so。
3.2 输入/输出分析器
输入/输出分析器将输入和输出字符串嵌入到转换嵌入中，从而描述输入和输出字符串之间的关系。令t∈RT表示这个变换嵌入。sI∈RS，sO∈RS分别是输入和输出字符串嵌入。输入/输出分析器可以表示为式(4)，在我们的实现中，fIO只是一个具有激活函数tanh的2层全连通神经网络。
3.3 程序生成器Program Generator
图2 程序生成器的图表
程序生成器(图2)是NPBE的核心。它会一步一步地生成几个函数和相应的参数“嵌入”。在t时刻函数的嵌入计算方程为(5)，这是一个完全连接的神经网络，它采取t时刻的变换嵌入和程序生成器的执行历史ht-1∈RH(h0=t)作为输入。同样，在t时刻的函数的参数嵌入由式子(6)计算。然而，函数的参数通常非常复杂，很难准确预测。所以注意力机制(类似于一个用于神经机器翻译模型(Bahdanau,Cho,Bengio2014))应用于在输入和输出字符串上用注意力去完善的原始参数嵌入ar,t。这是在式(7)中总结出来的。最后，函数嵌入ft，完善的参数嵌入at，以及之前的历史嵌入ht-1，都被嵌入到如式(8)所示的新历史嵌入。Wh和bh分别是参数矩阵和生成的新历史向量。
函数ffunc和fargs可以是多层完全连接的神经网络，在我们的实验中，我们只使用一层神经网络。式(7)中的函数fatt是通过对输入和输出字符串按照如下处理来实现的：
W1，W2，vI和W3，W4，vo分别是处理输入和输出字符串的参数。请注意，用于输入和输出字符串的注意力架构是相同的，但有不同的参数。最终的参数嵌入是通过将注意力集成在输入、输出和嵌入的原始参数之上生成的：
Watt和batt是组合的参数。
3.4 符号选择器
符号选择器使用函数嵌入ft和由程序生成器生成的参数嵌入at来选择合适的函数和该函数的相应参数。由式(16)产生在P原子函数之上的概率分布αfunc,t∈[0,1]p，其中Uf∈RP*F是存储原子函数表示的矩阵。由RNN(Choet al. 2014)解码的参数嵌入at(表示参数的摘要)是根据之前的输出和式子（17）中的at来表示。st,0,…,st,i-1是LSTM的隐藏状态，其中st,0=[0]H。这样，参数序列由RNN生成。第i个参数在t时刻在Q可能的参数αarg,i,t∈[0,1]Q的概率分布是用式(18)产生的，其中Ua∈RQ*A是存储可能参数的表示的矩阵。
3.5 训练
我们使用输入输出字符串对{Хi,Уi}以及作为函数序列和相应参数的程序来对NPBE端到端进行训练。每个程序可以将Х转换为Уi，其中i表示第i个训练样本。对于每个输入输出对我们可以生成一个T个函数的序列，而且每个函数都有一个参数列表a∈AM，其中A是一组可能的参数，M是一个函数可以取的最大的参数个数。在我们的执行中，T=5, M=5。
训练是在给定{Хi,Уi}情况下，由直接最大化正确程序的log似然可能指导的：
其中θ是我们模型的参数。将随机高斯噪声(Neelakantanet al. 2015)注入到转换嵌入和参数嵌入中，以提高NPBE的泛化能力和稳定性。
4 实验
4.1 实验设置
NPBE模型需要诱导一个程序，该程序由一个仅基于一个输入输出字符串对的函数序列组成。在本节中，我们将描述对NPBE模型的评估。在我们的实验中，我们定义了7个基本的字符串操作函数和1个空函数作为原子函数(表1)。为了简单起见，每个程序最多可以由5个函数组成。我们定义了一组常量符号(表2)，我们的模型可以从中选择参数。常量符号包括整数和分隔符。Select函数使用整数作为字符串数组的索引。负整数用于从尾部访问数组元素。整数符号的设计支持访问最多7个元素的数组。分隔符被拆分Split和连接Join使用，以拆分字符串或通过分隔符连接字符串数组。我们还定义了一些特殊的符号。例如，符号x表示输入字符串、ol、o2、o3和o4分别表示第一、第二、第三和第四个操作的输出。NoArg符号表示当前位置没有预期的参数。请注意，尽管在我们的实验中，我们对程序中的函数和参数提供了一些约束，但是我们的模型可以很容易地扩展以支持新的函数和参数。
表1 原子函数
表2 我们模型的常量符号
为了获得培训数据，我们首先根据45个预定义的任务在不同层次的复杂性上生成程序。任务是按特定顺序排列的函数序列，但是每个函数的参数不是固定的。定义任务的原因是我们希望我们的模型生成的程序是语法正确和有意义的。45项任务范围从简单的任务，如输入到某个常量字符串的连接，到更复杂的任务，包括拆分、连接、选择、ToUpper和连接函数等。例如，拆分split和加入join的任务是先将输入字符串拆分为分隔符，然后使用另一个分隔符加入和拆分字符串数组。程序源自这个任务可是Join(Split(x,/”),“:”)，它将输入字符串x根据分隔符“/”分离，然后将生成的子字符串使用分隔符“：”组合。完成一个任务的平均函数数是3.5个。
对于所有的任务，我们总共产生了大约69000个训练程序。我们为每个程序Pi生成一个随机的输入字符串Xi，它应该是一个有效的程序Pi的输入。接下来,我们在Xi上，通过实际运行Python程序实现以应用程序Pi，得到输出字符串Yi。我们将Xi和Yi最长限定为62个字符。之后，我们使用{Xi, Yi}作为输入数据，输入到我们的模型，而Pi作为训练目标。这个程序产生的方式是，如果有多个程序可以导致相同的Xi，那么只选择一个特定的程序。因此，对模型的预测希望的程序是没有歧义的。给定程序Pi，输入字符串Xi总是随机动态生成以减少过拟合。表3为模型提供了一些具体的输入输出示例。
表3 用于NPBE的输入输出对例子。对应的程序（从上到下）分别是：1）Concatenate(“Hello ”, Select(Split(x, “@”), 0), “, have fun!”)；2）Concatenate (ToUpper(Select(Split(x, “/”),1)), “-”, Select(Split(x, “/”), 0))；3)Select (Split (Select (Split (x, “/”), -1), “.”), 0). 注意，GetConstString是一个占位符，第一个被评估为“Hello”，第二个被评估为“，havefun!”
为了训练NPBE，我们选择了RMSProp(Tieleman和Hinton 2012)作为优化器，并将最小批mini - batch大小设置为200。我们将变换嵌入t和历史嵌入的维数h设为256，将函数嵌入f设为16，并且将参数嵌入a设为64。实际的训练过程依赖于一个自适应的课程 (Reed和de Freitas 2015)，其中一个特定任务的训练频率与测试的错误率成正比。每10个时期，我们估计预测误差。我们使用具有足够温度的softmax来采样每项任务的频率，这些任务将在接下来的10个周期进行。因此，具有较高错误率的任务将比在接下来的10个时代中错误率低的任务更频繁地被取样。
NPBE的评估是为了回答以下研究问题：
4.1.1 研究问题1: 在生成程序中NPBE的精确度是什么？
在这个研究问题中，我们使用随机生成的输入输出字符串来评估NPBE生成程序的准确性。例如，给定一个随机输入输出对：25/11/16和25:11:16 (没有出现在训练数据)，我们想测试是否还能生成正确的程序Join(Split(x,“/”),“:”)。要回答这个研究问题，我们为每个任务生成随机输入输出字符串1000次，并应用训练的NPBE模型。由NPBE产生的程序只有当模型正确预测所有五个功能(如果不到五个，则填充上NoFunc符号)和所有的参数函数(也填充上NoArg符号)是才被认为正确的(因此总共5+ 5 * 5 = 30个位置)。我们还将我们的模型与RNN编码器-解码器模型(Cho et al. 2014)进行了比较，该模型使用LSTM和LSTM注意力机制进行了实现，所有的参数都与我们的模型相似。
4.1.2 研究问题2: NPBE能用之前看不到的参数生成程序吗？
在这个研究问题中，我们测试了NPBE的泛化能力。我们使用参数设置没有出现在训练集中的程序来评估我们的模型。例如，如果程序Join(Split(x,“/”),“:”)出现在训练集中，我们想知道是否NPBE还可以用于没有出现在训练集中的Join(Split(x,“@”),“-”)。为了回答这个研究问题，我们设计一个包括大约19000个前所未有参数的程序测试集。这个实验是在19个有复杂的参数组合的任务中进行的(对于简单的任务，很少可以选择参数，所以我们跳过它们)。
4.2 实验结果
研究问题1: 在生成程序中NPBE的精确度是什么？
表4给出了NPBE预测程序的评价结果。NPBE取得的Top1的平均精度为74.1%，这意味着在测试中74.1%的输入输出对，NPBE能够成功地生成相应的程序。我们发现模型预测错误最有可能发生在Select的整数参数上，因为神经网络不擅长计数。因此，我们也让模型在尝试预测Select的整数参数时给出3或5个预测。Top3和Top5的平均精度结果分别为85.8%和91.0%，这意味着在测试中85.8%和91.0%的输入输出对，NPBE分别在前3和前5的结果中成功返回相应的程序。结果表明，NPBE模型可以为大多数任务生成正确的程序。
表4 生成程序的结果
作为一个例子，给定输入字符串“17/apr/2016”和输出字符串“APR-17”，我们的模型需要诱导一个由Split，Select，Case Change，Concatenate组成的程序。对于这个任务，我们的模型在35.8%的案例中给出了完全正确的程序。如果我们允许模型对Select的整数参数给出3个或5个预测，那么精确度将提高到73.2%或94.0%。
LSTM和具有注意力机制的LSTM(即LSTM-a)的结果也见表4。请注意，LSTM和LSTM-a的Top1、Top3和Top5精度几乎相同，因此只报告了Top1的准确性。我们发现，普通的编码器解码器模型可以解决最简单的任务，但不能解决更复杂的任务。结果表明，NPBE显著优于普通的编码器解码器模型。
研究问题2: NPBE能用之前看不到的参数生成程序吗？
我们测试了NPBE对具有看不见参数设置的程序的泛化能力。表5给出了平均Top5精度结果。结果表明，对于可见和不可见的参数设置，我们的模型实现的精度没有太大的差异。例如，Split任务，Join首先将一个输入字符串分隔符(如“/”)，然后用其他分隔符(如“:”)连接生成的子字符串。这个任务在训练集上达到了93.6%的准确率。对于不同的参数(例如，先用“@”将输入字符串拆分，然后再由“-”来连接产生的子字符串)，在训练集中不存在，NPBE仍然可以得到93.9%的准确率。结果表明，NPBE可以推广到不可见的程序参数，而不需要对特定的参数组合进行过度拟合。
表5 具有可见参数和不可见程序参数的结果
4.3 讨论和未来工作
NPBE背后的意图是使模型能够自动地从输入输出字符串中学习相关的特性，并利用所学的特性来归纳出正确的程序。本文的目的不是直接与现有的PBE系统竞争。相反，我们证明DNN的使用可以识别字符串转换中的特性，并且可以通过输入输出对学习精确的程序。
目前，NPBE不能推广到完全看不见的(如分割、加入、连接)，从来没有出现在训练集的任务。在未来的工作中，我们将努力构建模型，真正“理解”原子函数的含义，从而能归纳到看不见的任务。
5 结论
在本文中，我们提出了基于DNN的实例编程(PBE)模型。NPBE可以通过推理出函数的组成和相应的参数来诱导基于简单输入输出对的字符串操作程序。我们已经证明，利用DNN的新方法可以成功地应用于实例系统的编程。我们的工作也探索了在深度学习中学习高阶函数的方法，是向DNN传授计算机程序的一步。
论文下载链接:
https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14482/13948
留言 点赞 发个朋友圈
我们一起探讨AI落地的最后一公里
标签: excel随机生成权重