我们将Kearns-Vazirani学习算法扩展到能够处理随时间变化的系统。我们提出了一种新的学习算法，该算法可以重复使用和更新以前学习的行为，在Learnlib库中实现它，并在大型示例中对其进行评估，我们在算法的两次运行中进行了少量调整。在这些实验中，我们的算法显着优于经典的Kearns-Vazirani学习算法和当前最新的自适应算法。
translated by 谷歌翻译
我们根据三个主要方面提出了一种针对PDFA的新的主动学习算法：对状态的一致性，该状态考虑了临时符号概率分布，一种应对分布差异的量化以及有效的基于树的数据结构。实验显示有关参考实现的显着性能提高。
translated by 谷歌翻译
识别概率上下文无语法的问题有两个方面：第一个是确定语法的拓扑（语法规则），第二个是估计每个规则的概率权重。考虑到一般来说，尤其是学习无上下文语法的硬度结果，尤其是概率语法，大多数文献都集中在第二个问题上。在这项工作中，我们解决了第一个问题。我们将注意力限制在结构上明确的无上下文语法（SUWCFG）上，并为\提供了一种查询学习算法，用于\结构上明确的概率无上下文语法（SUPCFG）。我们表明，可以使用\ emph {Co-Linear多重树自动机}（CMTA）表示SUWCFG，并提供一种学习CMTA的多项式学习算法。我们表明，学到的CMTA可以转换为概率语法，从而提供了一种完整的算法，用于学习结构明确的概率上下文无语法（语法拓扑和概率权重），并使用结构化的成员资格查询和结构化的等价Queries。这项工作的摘要版本在AAAI 21上发布。
translated by 谷歌翻译
复杂的事件识别（CER）系统在过去二十年中变得流行，因为它们能够“立即”检测在实时事件流上的模式。然而，缺乏预测模式可能发生在例如由Cer发动机实际检测到这种发生之前的模式。我们提出了一项正式的框架，试图解决复杂事件预测（CEF）的问题。我们的框架结合了两个形式主义：a）用于编码复杂事件模式的符号自动机; b）预测后缀树，可以提供自动机构的行为的简洁概率描述。我们比较我们提出的方法，以防止最先进的方法，并在准确性和效率方面展示其优势。特别地，预测后缀树是可变的马尔可夫模型，可以通过仅记住足够的信息的过去序列来捕获流中的长期依赖性。我们的实验结果表明了能够捕获这种长期依赖性的准确性的益处。这是通过增加我们模型的顺序来实现的，以满足需要执行给定顺序的所有可能的过去序列的所有可能的过去序列的详尽枚举的全阶马尔可夫模型。我们还广泛讨论CEF解决方案如何最佳地评估其预测的质量。
translated by 谷歌翻译
行为树（BT）是一种在自主代理中（例如机器人或计算机游戏中的虚拟实体）之间在不同任务之间进行切换的方法。 BT是创建模块化和反应性的复杂系统的一种非常有效的方法。这些属性在许多应用中至关重要，这导致BT从计算机游戏编程到AI和机器人技术的许多分支。在本书中，我们将首先对BTS进行介绍，然后我们描述BTS与早期切换结构的关系，并且在许多情况下如何概括。然后，这些想法被用作一套高效且易于使用的设计原理的基础。安全性，鲁棒性和效率等属性对于自主系统很重要，我们描述了一套使用BTS的状态空间描述正式分析这些系统的工具。借助新的分析工具，我们可以对BTS如何推广早期方法的形式形式化。我们还显示了BTS在自动化计划和机器学习中的使用。最后，我们描述了一组扩展的工具，以捕获随机BT的行为，其中动作的结果由概率描述。这些工具可以计算成功概率和完成时间。
translated by 谷歌翻译
我们回答以下问题，哪些结合性查询以多种方式上的许多正和负面示例以及如何有效地构建此类示例的特征。结果，我们为一类连接的查询获得了一种新的有效的精确学习算法。我们的贡献的核心是两种新的多项式时间算法，用于在有限结构的同态晶格中构建前沿。我们还讨论了模式映射和描述逻辑概念的独特特征性和可学习性的影响。
translated by 谷歌翻译
结构分解方法，例如普遍的高树木分解，已成功用于解决约束满意度问题（CSP）。由于可以重复使用分解以求解具有相同约束范围的CSP，因此即使计算本身很难，将资源投资于计算良好的分解是有益的。不幸的是，即使示波器仅略有变化，当前方法也需要计算全新的分解。在本文中，我们迈出了解决CSP $ P $分解的问题的第一步，以使其成为由$ P $修改产生的新CSP $ P'$的有效分解。即使从理论上讲问题很难，我们还是提出并实施了一个有效更新GHD的框架。我们算法的实验评估强烈提出了实际适用性。
translated by 谷歌翻译
行为树（BT）在机器人界变得越来越流行。BT工具非常适合决策应用程序，允许机器人执行复杂的行为，同时也可以向人类解释。验证使用的BT在安全性和可靠性要求方面已经很好地构建是必不可少的，尤其是对于在关键环境中运行的机器人。在这项工作中，我们建议对行为树的形式规范和一种证明已经使用过的树的不变性的方法，同时使最终用户的树木形式化的复杂性保持简单。允许在行为树的特定实例中测试行为树的特定实例，而无需了解更抽象的形式化级别。
translated by 谷歌翻译
行为树起源于视频游戏，是一种控制NPC的方法，但此后在机器人学界获得了吸引力，它是描述执行任务的框架。Behaverify是一种从PY_TREE创建NUXMV模型的工具。对于标准化的复合节点，此过程是自动的，不需要其他用户输入。自动支持各种叶子节点，不需要其他用户输入，但是自定义的叶节点将需要其他用户输入才能正确建模。Behaverify可以提供一个模板以使其更轻松。Behaverify能够创建具有100多个节点的NUXMV模型，NUXMV能够直接和通过反例验证该模型上的各种非平凡LTL属性。该模型具有并行节点，选择器和序列节点。与基于BTCompiler的模型的比较表明，由Behaverify创建的模型表现更好。
translated by 谷歌翻译
2020-07-24
决策树学习是机器学习中广泛使用的方法，在需要简洁明了的模型的应用中受到青睐。传统上，启发式方法用于快速生产具有相当高准确性的模型。然而，一个普遍的批评是，从精度和大小方面，所产生的树可能不一定是数据的最佳表示。近年来，这激发了最佳分类树算法的发展，这些算法与执行一系列本地最佳决策的启发式方法相比，在全球范围内优化决策树。我们遵循这一工作线，并提供了一种基于动态编程和搜索的最佳分类树的新颖算法。我们的算法支持对树的深度和节点数量的约束。我们方法的成功归因于一系列专门技术，这些技术利用了分类树独有的属性。传统上，最佳分类树的算法受到了高运行时的困扰和有限的可伸缩性，但我们在一项详细的实验研究中表明，我们的方法仅使用最先进的时间所需的时间，并且可以处理数十个数据集的数据集在数千个实例中，提供了几个数量级的改进，并特别有助于实现最佳决策树的实现。
translated by 谷歌翻译
监督的学习算法通常假设有足够的内存能够在培训和测试阶段存储其数据模型。但是，在物联网中，当数据以无限数据流的形式出现或将学习算法部署在具有减少内存量的设备上时，此假设是不现实的。在本文中，我们将在线蒙德里安森林分类算法调整以在数据流上的内存约束。特别是，我们设计了五种失调策略，以在达到内存限制时使用新数据点更新蒙德里安树。此外，我们设计了修剪机制，使蒙德里亚树在记忆约束下概念更加坚固。我们在各种真实和模拟数据集上评估了算法，并以有关它们在不同情况下使用的建议得出的结论：扩展节点策略在所有配置中都是最佳的设备外策略，而应采用不同的修剪机制取决于是否期望概念漂移。我们所有的方法均在ORPAILLECC开源库中实现，并准备在嵌入式系统和连接的对象上使用。
translated by 谷歌翻译
我们研究动态算法，以便在$ N $插入和删除流中最大化单调子模块功能的问题。我们显示任何维护$（0.5+ epsilon）$ - 在基数约束下的近似解决方案的算法，对于任何常数$ \ epsilon> 0 $，必须具有$ \ mathit {polynomial} $的摊销查询复杂性$ n $。此外，需要线性摊销查询复杂性，以维持0.584美元 - 批量的解决方案。这与近期[LMNF + 20，MON20]的最近动态算法相比，达到$（0.5- \ epsilon）$ - 近似值，与$ \ mathsf {poly} \ log（n）$摊销查询复杂性。在正面，当流是仅插入的时候，我们在基数约束下的问题和近似的Matroid约束下提供有效的算法，近似保证$ 1-1 / e-\ epsilon $和摊销查询复杂性$ \ smash {o （\ log（k / \ epsilon）/ \ epsilon ^ 2）} $和$ \ smash {k ^ {\ tilde {o}（1 / \ epsilon ^ 2）} \ log n} $，其中$ k $表示基数参数或Matroid的等级。
translated by 谷歌翻译
尽管对连续数据的归一流流进行了广泛的研究，但直到最近才探索了离散数据的流量。然而，这些先前的模型遭受了与连续流的局限性。最值得注意的是，由于离散函数的梯度不确定或零，因此不能直接优化基于流动的模型。先前的作品近似离散功能的伪级，但不能在基本层面上解决该问题。除此之外，与替代离散算法（例如决策树算法）相比，反向传播可能是计算繁重的。我们的方法旨在减轻计算负担，并通过基于决策树开发离散流程来消除对伪级的需求，这是基于有效的基于树的基于有效的树的方法进行分类和回归的离散数据。我们首先定义了树结构化置换（TSP），该置换量（TSP）紧凑地编码离散数据的排列，其中逆向易于计算；因此，我们可以有效地计算密度值并采样新数据。然后，我们提出了一种决策树算法来构建TSP，该TSP通过新标准在每个节点上学习树结构和排列。我们从经验上证明了我们在多个数据集上方法的可行性。
translated by 谷歌翻译
Angluin的L*算法使用会员资格和等价查询了解了常规语言的最低（完整）确定性有限自动机（DFA）。它的概率近似正确（PAC）版本用足够大的随机会员查询替换等效查询，以使答案获得高级信心。因此，它可以应用于任何类型的（也是非规范）设备，可以将其视为合成自动机的算法，该算法根据观测值抽象该设备的行为。在这里，我们对Angluin的PAC学习算法对通过引入一些噪音从DFA获得的设备感兴趣。更确切地说，我们研究盎格鲁因算法是否会降低噪声并产生与原始设备更接近原始设备的DFA。我们提出了几种介绍噪声的方法：（1）嘈杂的设备将单词的分类W.R.T.倒置。具有很小概率的DFA，（2）嘈杂的设备在询问其分类W.R.T.之前用小概率修改了单词的字母。 DFA和（3）嘈杂的设备结合了W.R.T.单词的分类。 DFA及其分类W.R.T.柜台自动机。我们的实验是在数百个DFA上进行的。直言不讳地表明，我们的主要贡献表明：（1）每当随机过程产生嘈杂的设备时，盎格鲁因算法的行为都很好，（2）但使用结构化的噪声却很差，并且（3）几乎肯定是随机性的产量具有非竞争性语言的系统。
translated by 谷歌翻译
我们提出了一种改善机器学习（ML）决策树（DTS）的准确性拦截权衡的方法。特别是，我们将最大的满足技术应用于计算最低纯DTS（MPDT）。我们提高了先前方法的运行时，并证明这些MPDT可以优于ML Framework Sklearn生成的DTS的准确性。
translated by 谷歌翻译
This paper presents a new approach for analyzing and identifying potentially useful generalized plans. It presents a new conceptual framework along with an algorithmic process for assessing termination and reachability related properties of generalized plans. The presented framework builds upon classic results on the analysis of graphs to decompose generalized plans into smaller components in a novel algorithm for conducting a hierarchical analysis for termination of arbitrary generalized plans. Theoretical analysis of the new framework establishes soundness of the presented algorithms and shows how it goes beyond existing approaches; empirical analysis illustrates the scope of this approach. Our analysis shows that this new approach can effectively identify termination for a significantly larger class of generalized plans than was possible using existing methods.
translated by 谷歌翻译
Monte Carlo Tree Search (MCTS) is a recently proposed search method that combines the precision of tree search with the generality of random sampling. It has received considerable interest due to its spectacular success in the difficult problem of computer Go, but has also proved beneficial in a range of other domains. This paper is a survey of the literature to date, intended to provide a snapshot of the state of the art after the first five years of MCTS research. We outline the core algorithm's derivation, impart some structure on the many variations and enhancements that have been proposed, and summarise the results from the key game and non-game domains to which MCTS methods have been applied. A number of open research questions indicate that the field is ripe for future work.
translated by 谷歌翻译
图数据管理和查询具有许多实际应用。当图形非常异构和/或用户不熟悉其结构时，即使用户无法描述连接，他们也可能需要找到如何在图中连接两个或多个节点的组。这仅由现有查询语言部分支持，这些语言允许搜索路径，但不适合连接三个或更多节点组的树。后者与NP-HARD组Steiner树问题有关，以前已考虑用于数据库中的关键字搜索。在这项工作中，我们正式展示了如何在诸如SPARQL或Cypher之类的图形语言中集成连接的树模式（CTPS，简称CTP），从而导致扩展查询语言（或简而言之）。然后，我们研究一组评估CTP的算法；我们概括了先前的关键字搜索工作，最重要的是（i）考虑双向边缘遍历遍历和（ii）允许用户选择任何分数功能来排名CTP结果。为了应对非常大的搜索空间，我们提出了一种有效的修剪技术，并正式建立了大量的情况，即使我们的算法molesp也可以完成修剪。我们的实验验证了我们在大量合成和现实世界中的CTP和EQL评估算法的性能。
translated by 谷歌翻译
深度神经网络（DNN）越来越多地用于安全至关重要的系统中，迫切需要保证其正确性。因此，验证社区设计了多种技术和工具来验证DNN。当DNN验证者发现触发错误的输入时，很容易确认；但是，当他们报告不存在错误时，就无法确保验证工具本身没有缺陷。由于在DNN验证工具中已经观察到了多个错误，因此这将DNN验证的适用性提出了质疑。在这项工作中，我们提出了一种具有证明生产能力的基于简单的DNN验证符的新型机制：产生易于检查的不可满足性的见证人，这证明了没有错误的情况。我们的证明生产是基于众所周知的Farkas引理的有效适应，并结合了处理分段线性函数和数值精确误差的机制。作为概念的证明，我们在Marabou DNN验证者之上实施了我们的技术。我们对避免空中碰撞的安全至关重要系统的评估表明，在几乎所有情况下，证明生产都成功了，只需要最小的开销。
translated by 谷歌翻译
测量分类器的性能是机器学习中的一个重要任务。计算测量的算法的运行时间在离线设置中播放非常小的作用，例如，当研究员正在开发分类器时，在离线设置中起着非常小的作用。然而，如果我们的目标是监视分类器随时间的性能，则运行时间变得更加重要。在本文中，我们研究了三种算法以维持两种措施。第一个算法在ROC曲线（AUC）下维护区域，并在$ O（\ log n）$ time中的数据点删除。这是通过维护在自平衡搜索树中排序的数据点来完成的。此外，我们增强了搜索树，允许我们在$ O（\ log n）$ time中查询数据点的ROC坐标。这样做，我们能够维护$ O（\ log n）$ time。我们的接下来的两种算法涉及维持$ H $ -MEASURE，这是基于ROC曲线的替代度量。计算该度量是两步处理：首先，我们需要计算ROC曲线的凸壳，然后在凸船上的总和。我们证明我们可以使用经典凸船体维护算法的次要修改来维护凸船体。然后，我们显示在某些条件下，我们可以在$ o（\ log ^ 2 n）$ time中，计算$ h $ -measure，如果没有满足条件，那么我们可以估计$ h $ -measure $ o（（\ log n + \ epsilon ^ { - 1}）\ log n）$ time。我们凭经验展示了我们的方法明显比基线更快。
translated by 谷歌翻译