虽然目前的通用游戏(GGP)系统促进了用于游戏的人工智能(AI)的有用研究,但它们通常是特定的,并且计算效率低。在本文中,我们描述了一个名为Ludii的“ludemic”通用游戏系统的初始版本,该系统具有为AI研究人员以及相关领域的游戏设计师,历史学家,教育工作者和从业者提供有效工具的潜力。 Ludiidefines游戏作为ludemes的结构,即高级,易于理解的游戏概念。我们通过概述其主要优点来建立Ludii的基础:通用性,可扩展性,可理解性和效率。实验上,Ludii优于Tiltyard GGP存储库中所有可用游戏的基于命题网络的最有效的Game DescriptionLanguage(GDL)reasoners之一。
translated by 谷歌翻译
如果以结构化的方式呈现示例,人类往往会更快地学习复杂的抽象概念。例如,当学习如何在游戏中玩游戏时,通常学习的第一个概念之一是游戏如何结束,即。导致终端状态(赢,输或抽奖)的动作。首先学习最终游戏的优势在于,一旦理解了导致终端状态的动作,就有可能逐步学习远离终端状态的动作的后果 - 我们称之为终极游戏优先课程。目前,一般棋盘游戏的最先进的机器学习播放器,Google DeepMind的AlphaZero,确实采用了结构化的培训课程;而是始终从整个游戏中学习。通过采用终端游戏优先培训课程来培训一名AlphaZero激励球员,我们凭经验表明,与未使用培训课程的球员相比,在训练的早期阶段可以提高人工智能球员的学习速度。
translated by 谷歌翻译
我们研究了在$ T $是Toeplitz的假设下估计adistribution $ \ mathcal {D} $超过$ d $ -dimensional向量的协方差矩阵$ T $的查询复杂度。这种假设出现在许多信号处理问题中,其中任何两个测量之间的协方差仅取决于那些测量之间的时间或距离。我们对估计策略感兴趣,这些估计策略可能选择仅查看每个矢量样本$ x ^ {(\ ell)} \ sim \ mathcal {D} $中的条目子集,这通常等同于减少无线信号处理应用中的硬件和通信要求高级成像。我们的目标是最小化1)从$ \ mathcal {D} $中抽取的矢量样本数量和2)每个样本中访问的条目数量。我们提供了一些关于利用$ T $的Toeplitz结构的这些样本复杂性度量的第一个非渐近边界,并且通过这样做,显着改进了通用协方差矩阵的结果。我们的界限来自对经典和广泛使用的估计算法(以及一些新变体)的分析,包括基于根据所谓的稀疏标尺从每个矢量样本中选择条目的方法。在许多情况下,我们将上层边界与匹配或几乎匹配的下边界配对。除了适用于任何Toeplitz $ T $的结果之外,我们进一步研究了当$ T $接近低等级时的重要设置,这通常是实践中的情况。我们表明,基于稀疏标尺的方法在这个设置中表现得更好,样本复杂度在$ d $中线性地缩放。受此发现的推动,我们开发了一种新的协方差估计策略,该策略进一步改进了低秩情况下的所有现有方法:当$ T $排名为$ k $ ornearly rank- $ k $时,它实现了样本复杂度,取决于$ k的多项式$并且仅以$ d $对数。
translated by 谷歌翻译
在本文中,我们重新审视了从头顶图像中检测到的船舶(海上船舶)的分类问题。尽管在过去十年中对这一非常重要和相关的问题进行了研究,但它仍然没有得到很好的解决。在海事领域中对船舶和其他物体进行检测和分类的主要问题之一是缺乏必要的大量地面实况数据来构建最先进的机器学习算法。我们通过使用Unity游戏引擎和3D船模建立一个大型(200k)合成图像数据集来解决这个问题。我们证明,通过使用合成数据,分类性能会显着提高,尤其是在培训中使用的注释图像很少时。
translated by 谷歌翻译
蛋白质的生物学功能源于其三维结构,其在热力学上由其氨基酸结构单元之间的原子间力的能量学决定(氨基酸的顺序,称为序列,定义蛋白质)。考虑到通过X-晶体学等实验手段确定蛋白质结构的成本(时间,金钱,人力资源),我们能否以更加有效的方式更好地描述和比较蛋白质3D结构,从而获得有意义的生物学见解? Webegin通过考虑一个相对简单的问题,将自己局限于只是蛋白质的二级结构元素。从历史上看,已经设计了许多计算方法来将蛋白质链中的氨基酸残基分类为几个离散二级结构中的一个,其中最明确的几何常规$ \ alpha $ -helix和$ \ beta $ -sheet;不合理的结构模式,如“转弯”和“循环”,不太了解。在这里,我们提出了深度学习技术的研究,以分类界定$ \ alpha $ -helices的循环式端盖结构。以前的工作使用高度经验启发式方法手动分类螺旋加盖图案。相反,我们直接使用结构数据 - 包括(i)从三维结构计算的主干扭转角,(ii)大分子特征集(例如,物理化学性质),和(iii)螺旋盖分类数据(来自CAPS-DB) - 作为背景真相训练双向长短期记忆(BiLSTM)模型对螺旋帽残留物进行分类。我们尝试了不同的网络架构和扫描超参数,以便训练和评估几个模型;我们还提供了一个支持向量分类器(SVC)作为基线。最终,通过深度BiLSTM模型实现了85%的级别平衡精度。
translated by 谷歌翻译
通常会遇到必须解决一系列相似计算问题的情况。在每个实例上运行具有最坏情况时间保证的标准算法将无法利用在问题实例中共享的有价值的结构。例如,当通勤驾驶从工作到家庭时,通常只有少数路线将是最短的路径。一个不利用这种共同结构的天真算法可能会花费大部分时间来检查永远不会在最短路径上的道路。更一般地说,我们经常可以忽略那些可能永远不会包含最优解的大片空间。我们提出了一种算法,该算法学习在重复计算时最大限度地修剪搜索空间,从而减少运行时间,同时以高概率可靠地输出每个周期的正确解。我们的算法使用类似于在线算法中使用的简单探索 - 利用技术,尽管我们的设置是完全不同的。我们证明,对于我们的修剪搜索空间模型,我们的方法是最优的,直到恒定因子。最后,我们说明了我们的模型和算法对三个经典问题的适用性:最短路径路由,字符串搜索和线性规划。目前的实验证实,我们的简单算法有效地显着减少了解决重复计算的运行时间。
translated by 谷歌翻译
在这项工作中,我们从算法的角度研究生物神经网络,重点是理解计算时间和网络复杂性之间的权衡。我们的目标是抽象真实的神经网络,同时不捕获所有有趣的特征,保留高级行为,并允许我们做出生物学相关的结论。为了实现这一目标,我们考虑在$ stochastic \ spiking \ neural \ networks $的简单的生物学合理模型中实现算法原语。特别地,我们展示了如何利用这个模型中的神经元的随机行为来解决基本的$ symmetry-breaking \ task $,其中我们给出了具有相同激发率的神经元并且想要选择一个区分的神经元。在计算机神经科学中,这被称为胜者通吃(WTA)问题,并且它被认为是许多任务中的基本构建块,例如学习,模式识别和聚类。我们在随机尖峰神经网络模型中提供WTA电路的有效构造,以及在给定数量的步骤中需要将Wod收敛到WTA的辅助神经元数量的下限。这些下限表明我们的结构在某些情况下几乎是最优的。这项工作涵盖并提供了[LMP17a]中原始发表的一系列结果的更深入的证据。它改编自C.Musco博士的最后一章。论文[Mus18]。
translated by 谷歌翻译
在缺少条目的低秩近似中,给定$ A \ in \ mathbb {R} ^ {n \ times n} $和二进制$ W \ in \ {0,1 \} ^ {n \ times n} $,目标是得到一个等级 - $ k $矩阵$ L $,其中:$$ cost(L)= \ sum_ {i = 1} ^ {n} \ sum_ {j = 1} ^ {n} W_ {i,j } \ cdot(A_ {i,j} - L_ {i,j})^ 2 \ le OPT + \ epsilon \ | A \ | _F ^ 2,$$其中$ OPT = \ min_ {rank-k \ \ hat {成本(\帽子L)$。这个问题也称为矩阵完成,并且取决于$ W $的选择,捕获低秩加上对角分解,强大的PCA,从单调丢失数据中的低秩恢复,以及许多其他重要问题。其中许多问题都是NP难的,虽然在某些情况下已知具有可证明保证的算法,但它们要么1)及时运行$ n ^ {\ Omega(k ^ 2 / \ epsilon)} $,或2)做出强有力的假设,例如,$ A $是不连贯的或$ W $是随机的。在这项工作中,我们考虑$ bicriteria \ algorithms $,它输出$ L $ withrank $ k'> k $。我们证明了一个常见的启发式方法,它只需将$ A $设置为$ 0 $,其中$ W $为$ 0 $,然后计算一个标准的低秩近似值,达到上面的近似值,等级为$ k'$,具体取决于$ communication \ $ W $的复杂性$。也就是说,将$ W $解释为aBoolean函数$ f(x,y)$与$ x,y \ in \ {0,1 \} ^ {\ log n} $的通信矩阵,只需设置$ k'即可= O(k \ cdot 2 ^ {R ^ {1-sided} _ {\ epsilon}(f)})$,其中$ R ^ {1-sided} _ {\ epsilon}(f)$是随机通信$ f $的复杂性与$ 1 $ -sided errorprobability $ \ epsilon $。对于许多问题,这产生了具有$ k'= k \ cdot poly((\ log n)/ \ epsilon)$的双目标算法。我们使用随机通信复杂性和$ 2 $ -sided错误证明了类似的界限。此外,我们展示了针对问题的自然变体的不同通信模型。例如,多玩家通信复杂性将张量分解和非确定性通信复杂性连接到布尔低秩分解。
translated by 谷歌翻译
消费级3D打印机使得制作美学物品和静态组件变得更加容易,为这些物体的自动化设计打开了大门。然而,虽然静态设计很容易通过3D打印生成,但是具有移动部件的功能设计更难以生成:搜索空间是高维的,3D打印部件的分辨率不够,并且难以预测不完美的3D打印机构的物理行为。一个典型的挑战是生产一系列可靠的有效齿轮机构,这些齿轮机构可以在生产后使用而无需进行广泛的后处理。为了应对这一挑战,使用新颖性搜索创建和演化基于逆流神经网络(RNN)的间接​​编码。每一代的Theelite解决方案都经过3D打印,以评估其在物理测试平台上的功能性能。该系统能够发现难以通过其他方法发现的有序设计规则。与使用遗传算法(GA)演化的直接编码相比,其设计在几何上更加多样化,功能更加有效。因此,它为3D打印的功能机制的生成设计奠定了良好的基础。
translated by 谷歌翻译
在学习现实领域的政策时,会出现两个重要问题:(i)如何有效地使用预先收集的非政策性,非最佳行为数据;以及(ii)如何在不同的竞争目标和约束之间进行调解。研究多约束下批量策略学习的问题,并提供系统的解决方案。我们首先提出一种灵活的元算法,它允许任何批量强化学习和在线学习过程的子程序。然后,我们提出了一个特定的算法实例,并为主要目标和所有约束提供性能保证。为了证明约束满足,我们提出了一种新的简单的非政策政策评估方法(OPE),并推导出PAC风格的界限。我们的算法在不同的领域中实现了强有力的实证结果,包括在模拟汽车驾驶的挑战性问题中受制于多种约束,例如车道保持和平稳驾驶。我们还通过实验证明,我们的OPE方法在独立的基础上优于其他流行的OPE技术,特别是在高维设置中。
translated by 谷歌翻译