语法推断是计算学习理论中的一个经典问题，也是自然语言处理中更广泛影响的话题。我们将语法视为计算模型，并提出了一种新型的神经方法，以从正面和负面实例中诱导常规语法。我们的模型是完全可以解释的，其中间结果可直接解释为部分分析，并且可以在提供足够的数据时将其用于学习任意的常规语法。我们的方法始终在各种复杂性测试中获得高召回和精确得分。我们使详细的结果和代码随时可用。
translated by 谷歌翻译
识别概率上下文无语法的问题有两个方面：第一个是确定语法的拓扑（语法规则），第二个是估计每个规则的概率权重。考虑到一般来说，尤其是学习无上下文语法的硬度结果，尤其是概率语法，大多数文献都集中在第二个问题上。在这项工作中，我们解决了第一个问题。我们将注意力限制在结构上明确的无上下文语法（SUWCFG）上，并为\提供了一种查询学习算法，用于\结构上明确的概率无上下文语法（SUPCFG）。我们表明，可以使用\ emph {Co-Linear多重树自动机}（CMTA）表示SUWCFG，并提供一种学习CMTA的多项式学习算法。我们表明，学到的CMTA可以转换为概率语法，从而提供了一种完整的算法，用于学习结构明确的概率上下文无语法（语法拓扑和概率权重），并使用结构化的成员资格查询和结构化的等价Queries。这项工作的摘要版本在AAAI 21上发布。
translated by 谷歌翻译
复杂的事件识别（CER）系统在过去二十年中变得流行，因为它们能够“立即”检测在实时事件流上的模式。然而，缺乏预测模式可能发生在例如由Cer发动机实际检测到这种发生之前的模式。我们提出了一项正式的框架，试图解决复杂事件预测（CEF）的问题。我们的框架结合了两个形式主义：a）用于编码复杂事件模式的符号自动机; b）预测后缀树，可以提供自动机构的行为的简洁概率描述。我们比较我们提出的方法，以防止最先进的方法，并在准确性和效率方面展示其优势。特别地，预测后缀树是可变的马尔可夫模型，可以通过仅记住足够的信息的过去序列来捕获流中的长期依赖性。我们的实验结果表明了能够捕获这种长期依赖性的准确性的益处。这是通过增加我们模型的顺序来实现的，以满足需要执行给定顺序的所有可能的过去序列的所有可能的过去序列的详尽枚举的全阶马尔可夫模型。我们还广泛讨论CEF解决方案如何最佳地评估其预测的质量。
translated by 谷歌翻译
任何涉及一组随机变量的概率模型的主要用途是在其上运行推理和采样查询。经典概率模型中的推理查询是通过计算作为输入的事件的边际或条件概率的计算。当概率模型是顺序的时，涉及复杂语法的更复杂的边际推理查询可能会在计算语言学和NLP等领域中引起人们的关注。在这项工作中，我们解决了在隐藏的马尔可夫模型（HMMS）中计算无上下文语法（CFG）的可能性的问题。我们提供了一种动态算法，用于确切计算无上下文的语法类别的可能性。我们表明问题是NP-HARD，即使输入CFG的歧义性程度小于或等于2。然后我们提出了一种完全多项式随机近似方案（FPRAS）算法，以近似案例的可能性多项式结合的模棱两可的CFG。
translated by 谷歌翻译
将已知的原始概念重组为更大的新型组合是一种典型的人类认知能力。NLP中的大型神经模型是否在从数据中学习时获得此能力是一个悬而未决的问题。在本文中，我们从形式语言的角度看一下这个问题。我们使用确定性有限状态传感器来制作具有控制组合性的可控属性的无限数量数据集。通过对许多传感器进行随机采样，我们探讨了它们的哪些属性（状态数，字母大小，过渡次数等）有助于通过神经网络的组成关系可学习。通常，我们发现模型要么完全学习关系。关键是过渡覆盖范围，以每个过渡为400个示例设置软可学习性限制。
translated by 谷歌翻译
可靠的概括是安全ML和AI的核心。但是，了解神经网络何时以及如何推广仍然是该领域最重要的未解决问题之一。在这项工作中，我们进行了一项广泛的实证研究（2200个模型，16个任务），以研究计算理论中的见解是否可以预测实践中神经网络概括的局限性。我们证明，根据Chomsky层次结构进行分组任务使我们能够预测某些架构是否能够推广到分布外输入。这包括负面结果，即使大量数据和训练时间也不会导致任何非平凡的概括，尽管模型具有足够的能力完美地适合培训数据。我们的结果表明，对于我们的任务子集，RNN和变形金刚无法概括非规范的任务，LSTMS可以解决常规和反语言任务，并且只有通过结构化内存（例如堆栈或存储器磁带）可以增强的网络可以成功地概括了无上下文和上下文敏感的任务。
translated by 谷歌翻译
源代码的最先进的神经模型倾向于在代码的生成时进行评估，并且通常在长地平任务中的产生，例如整个方法体的产生。我们建议使用静态程序分析仪的弱监督来解决这一缺陷。我们的神经统计方法允许深入的生成模型来象征地计算它已经生成的代码中的静态分析工具，长距离语义关系。在培训期间，该模型观察这些关系，并学习生成条件上的程序。考虑到包含该方法的类的剩余部分，我们将我们的方法应用于生成整个Java方法的问题。我们的实验表明，该方法显着地优于最先进的变换器和模型，明确试图在制作程序中没有基本语义错误的程序以及在句法匹配地面真理方面来学习此任务的模型。
translated by 谷歌翻译
大多数低编码平台的用户，例如Excel和PowerApps，都以特定于域的公式语言编写程序来执行非平凡的任务。用户通常可以编写他们想要的大部分程序，但是引入了一些小错误，这些错误会产生破损的公式。这些错误既可以是句法和语义，也很难让低代码用户识别和修复，即使只能通过一些编辑解决。我们正式化了产生最后一英里维修问题等编辑的问题。为了解决这个问题，我们开发了Lamirage，这是一种最后一英里的维修发动机发电机，结合了符号和神经技术，以低代码公式语言进行最后一英里维修。 Lamirage采用语法和一组特定领域的约束/规则，它们共同近似目标语言，并使用它们来生成可以用该语言修复公式的维修引擎。为了应对本地化错误和对候选维修进行排名的挑战，Lamirage利用神经技术，而它依赖于符号方法来生成候选维修。这种组合使Lamirage可以找到满足提供的语法和约束的维修，然后选择最自然的修复。我们将Lamirage与400个Real Excel和PowerFX公式的最新神经和符号方法进行了比较，其中Lamirage的表现优于所有基线。我们释放这些基准，以鼓励在低代码域中进行后续工作。
translated by 谷歌翻译
整数序列对于承认完整描述的概念的建模至关重要。我们介绍了有关学习此类概念的新颖观点，并放下一组基准测试任务，旨在通过机器学习模型进行概念理解。这些任务间接评估模型的抽象能力，并挑战它们，以在观察代表性示例中获得的知识，从插值和外向上进行推理。为了进一步研究知识代表和推理的研究，我们介绍了事实，即“精选抽象理解工具包”。该工具包围绕着包含有机和合成条目的整数序列的大型数据集，用于数据预处理和生成的库，一组模型性能评估工具以及基线模型实现的集合，从而实现了未来的进步，以实现未来的进步舒适。
translated by 谷歌翻译
聚类函数（例如对数或差异）满足了许多代数身份。对于对数，所有身份都来自产品规则。对于Diologarithm和更高的经典细分线虫，这些身份可能涉及五个或更多功能。在与粒子物理学相关的许多计算中，聚集体的复杂组合通常来自Feynman积分。尽管集成产生的初始表达通常简化，但通常很难知道要应用哪些身份以及按什么顺序应用。为了解决这种瓶颈，我们探索机器学习方法可以帮助您。我们考虑了一种强化学习方法，在该方法中，身份类似于游戏中的动作，也是变压器网络方法，在该方法中，该问题类似于语言翻译任务。尽管这两种方法都是有效的，但变压器网络似乎更强大，并且在数学物理学中的符号操纵任务中实现了实际使用的希望。
translated by 谷歌翻译
Probabilistic context-free grammars have a long-term record of use as generative models in machine learning and symbolic regression. When used for symbolic regression, they generate algebraic expressions. We define the latter as equivalence classes of strings derived by grammar and address the problem of calculating the probability of deriving a given expression with a given grammar. We show that the problem is undecidable in general. We then present specific grammars for generating linear, polynomial, and rational expressions, where algorithms for calculating the probability of a given expression exist. For those grammars, we design algorithms for calculating the exact probability and efficient approximation with arbitrary precision.
translated by 谷歌翻译
即使机器学习算法已经在数据科学中发挥了重要作用，但许多当前方法对输入数据提出了不现实的假设。由于不兼容的数据格式，或数据集中的异质，分层或完全缺少的数据片段，因此很难应用此类方法。作为解决方案，我们提出了一个用于样本表示，模型定义和培训的多功能，统一的框架，称为“ Hmill”。我们深入审查框架构建和扩展的机器学习的多个范围范式。从理论上讲，为HMILL的关键组件的设计合理，我们将通用近似定理的扩展显示到框架中实现的模型所实现的所有功能的集合。本文还包含有关我们实施中技术和绩效改进的详细讨论，该讨论将在MIT许可下发布供下载。该框架的主要资产是其灵活性，它可以通过相同的工具对不同的现实世界数据源进行建模。除了单独观察到每个对象的一组属性的标准设置外，我们解释了如何在框架中实现表示整个对象系统的图表中的消息推断。为了支持我们的主张，我们使用框架解决了网络安全域的三个不同问题。第一种用例涉及来自原始网络观察结果的IoT设备识别。在第二个问题中，我们研究了如何使用以有向图表示的操作系统的快照可以对恶意二进制文件进行分类。最后提供的示例是通过网络中实体之间建模域黑名单扩展的任务。在所有三个问题中，基于建议的框架的解决方案可实现与专业方法相当的性能。
translated by 谷歌翻译
归纳逻辑编程（ILP）是一种机器学习的形式。ILP的目标是诱导推广培训示例的假设（一组逻辑规则）。随着ILP转30，我们提供了对该领域的新介绍。我们介绍了必要的逻辑符号和主要学习环境;描述ILP系统的构建块;比较几个维度的几个系统;描述四个系统（Aleph，Tilde，Aspal和Metagol）;突出关键应用领域;最后，总结了未来研究的当前限制和方向。
translated by 谷歌翻译
当前独立于域的经典计划者需要问题域和实例作为输入的符号模型，从而导致知识采集瓶颈。同时，尽管深度学习在许多领域都取得了重大成功，但知识是在与符号系统（例如计划者）不兼容的亚符号表示中编码的。我们提出了Latplan，这是一种无监督的建筑，结合了深度学习和经典计划。只有一组未标记的图像对，显示了环境中允许的过渡子集（训练输入），Latplan学习了环境的完整命题PDDL动作模型。稍后，当给出代表初始状态和目标状态（计划输入）的一对图像时，Latplan在符号潜在空间中找到了目标状态的计划，并返回可视化的计划执行。我们使用6个计划域的基于图像的版本来评估LATPLAN：8个插头，15个式嘴，Blockworld，Sokoban和两个LightsOut的变体。
translated by 谷歌翻译
本文提出了一种新的方法，称为模块化语法进化（MGE），以验证以下假设，即限制了神经进化的解决方案空间到模块化和简单的神经网络，可以有效地生成较小，更结构化的神经网络，同时提供可接受的（在某些方面）案例优于大型数据集的精度。 MGE还在两个方向上增强了最新的语法演化（GE）方法。首先，MGE的表示是模块化的，因为每个个体都有一组基因，并且每个基因都通过语法规则映射到神经元。其次，所提出的表示形式减轻了GE的两个重要缺点，即表示较低的表示性和弱位置，以生成具有大量神经元的模块化和多层网络。我们使用MGE定义和评估具有和不具有模块化的五种不同形式的结构，并找到没有耦合更有效的单层模块。我们的实验表明，模块化有助于更快地找到更好的神经网络。我们使用了十个具有不同尺寸，功能计数和输出类计数的众所周知的分类基准验证了提出的方法。我们的实验结果表明，MGE相对于现有的神经进化方法提供了卓越的准确性，并且返回分类器比其他机器学习生成的分类器要简单得多。最后，我们从经验上证明，MGE在局部性和可伸缩性属性方面优于其他GE方法。
translated by 谷歌翻译
We present a differentiable stack data structure that simultaneously and tractably encodes an exponential number of stack configurations, based on Lang's algorithm for simulating nondeterministic pushdown automata. We call the combination of this data structure with a recurrent neural network (RNN) controller a Nondeterministic Stack RNN. We compare our model against existing stack RNNs on various formal languages, demonstrating that our model converges more reliably to algorithmic behavior on deterministic tasks, and achieves lower cross-entropy on inherently nondeterministic tasks.
translated by 谷歌翻译
手写数学表达识别（HMER）是具有许多潜在应用的挑战性任务。 HMER的最新方法通过编码器架构实现了出色的性能。但是，这些方法符合“从一个字符到另一个字符”进行预测的范式，由于数学表达式或厌恶的手写的复杂结构，这不可避免地会产生预测错误。在本文中，我们为HMER提出了一种简单有效的方法，该方法是第一个将语法信息纳入编码器编码器网络的方法。具体而言，我们提出了一组语法规则，用于将每个表达式的乳胶标记序列转换为一个解析树。然后，我们将标记序列预测建模为具有深神经网络的树遍布过程。通过这种方式，提出的方法可以有效地描述表达式的语法上下文，从而减轻HMER的结构预测错误。在三个基准数据集上的实验表明，与先前的艺术相比，我们的方法实现了更好的识别性能。为了进一步验证我们方法的有效性，我们创建了一个大规模数据集，该数据集由从一万个作家中获取的100k手写数学表达图像组成。该工作的源代码，新数据集和预培训的模型将公开可用。
translated by 谷歌翻译
在本文中，我们试图通过引入深度学习模型的句法归纳偏见来建立两所学校之间的联系。我们提出了两个归纳偏见的家族，一个家庭用于选区结构，另一个用于依赖性结构。选区归纳偏见鼓励深度学习模型使用不同的单位（或神经元）分别处理长期和短期信息。这种分离为深度学习模型提供了一种方法，可以从顺序输入中构建潜在的层次表示形式，即更高级别的表示由高级表示形式组成，并且可以分解为一系列低级表示。例如，在不了解地面实际结构的情况下，我们提出的模型学会通过根据其句法结构组成变量和运算符的表示来处理逻辑表达。另一方面，依赖归纳偏置鼓励模型在输入序列中找到实体之间的潜在关系。对于自然语言，潜在关系通常被建模为一个定向依赖图，其中一个单词恰好具有一个父节点和零或几个孩子的节点。将此约束应用于类似变压器的模型之后，我们发现该模型能够诱导接近人类专家注释的有向图，并且在不同任务上也优于标准变压器模型。我们认为，这些实验结果为深度学习模型的未来发展展示了一个有趣的选择。
translated by 谷歌翻译
随着未来以数据为中心的决策，对数据库的无缝访问至关重要。关于创建有效的文本到SQL（Text2SQL）模型以访问数据库的数据有广泛的研究。使用自然语言是可以通过有效访问数据库（尤其是对于非技术用户）来弥合数据和结果之间差距的最佳接口之一。它将打开门，并在精通技术技能或不太熟练的查询语言的用户中引起极大的兴趣。即使提出或研究了许多基于深度学习的算法，在现实工作场景中使用自然语言来解决数据查询问题仍然非常具有挑战性。原因是在不同的研究中使用不同的数据集，这带来了其局限性和假设。同时，我们确实缺乏对这些提议的模型及其对其训练的特定数据集的局限性的彻底理解。在本文中，我们试图介绍过去几年研究的24种神经网络模型的整体概述，包括其涉及卷积神经网络，经常性神经网络，指针网络，强化学习，生成模型等的架构。我们还概述11个数据集，这些数据集被广泛用于训练Text2SQL技术的模型。我们还讨论了无缝数据查询中文本2SQL技术的未来应用可能性。
translated by 谷歌翻译
自然语言处理（NLP）已成为当前人工智能繁荣中的主要应用领域之一。转移学习已经启用了大量深入学习的神经网络，接受了语言建模任务，以大大提高了所有语言任务的性能。有趣的是，当模型培训使用包含软件代码的数据培训时，它们在从自然语言规范中生成功能计算机代码时展示了显着的能力。我们认为这是一种难题，用于神经模型为生成词组结构语法提供了一种替代理论，以说明语言有效。由于编程语言的语法由短语结构语法决定，因此成功的神经模型显然是对编程语言的理论基础的理论基础，以及通过扩展，自然语言来实现。我们认为语言模型的术语模型是误导性的，因为深度学习模型不是语言的理论模型，并提出采用语料库模型，这更好地反映了模型的成因和内容。
translated by 谷歌翻译