在本章中,提出了用于获得与任务相关的,多分辨率的,环境抽象的问题的整数线性编程公式,用于资源受限的自主剂。该公式从信息理论信号压缩(特别是信息瓶颈(IB)方法)中利用概念来提出抽象问题,作为在多分辨率树的空间上的最佳编码器搜索。抽象以与任务相关的方式出现,作为代理信息处理约束的函数。我们详细介绍我们的配方,并展示如何以共同的主题统一信号压缩的层次结构结构,信号编码器和信息理论方法。提出了一个讨论来描述我们配方的好处和缺点的讨论,以及详细的解释,如何在为资源受限的自主系统生成抽象的背景下解释我们的方法。结果表明,在多分辨率树空间中所得的信息理论抽象问题可以作为整数线性编程(ILP)问题进行配合。我们在许多示例上演示了这种方法,并提供了与现有方法相比,详细说明所提出框架的差异的讨论。最后,我们考虑了ILP问题的线性程序放松,从而证明可以通过求解凸程序来获得多分辨率信息理论树抽象。
translated by 谷歌翻译
在本文中,我们开发了一种方法,该方法使自主机器人能够从点云数据构建和压缩语义环境表示。我们的方法从传感器数据中构建了环境的三维语义树表示,然后通过一种新型的信息理论树木修复方法来压缩。所提出的方法是概率的,并将其纳入现实世界中固有的语义分类中。此外,我们的方法允许机器人在生成压缩树时优先考虑单个语义类,以设计保留相关语义信息的多分辨率表示,同时丢弃不需要的语义类别。我们通过压缩大型户外,语义丰富,真实世界环境的语义OCTREE模型来演示方法。此外,我们还展示了如何使用OCTREE抽象来创建语义信息图以进行运动计划,并使用未知的图形构造方法(例如Halton序列)进行比较。
translated by 谷歌翻译
有损压缩和聚类的核心是学习代表的忠诚度和规模之间的权衡。我们的目标是绘制并研究量化此权衡的帕累托前沿。我们关注确定性信息瓶颈(DIB)目标在硬聚类空间上的优化。为此,我们介绍了原始的DIB问题,当优化在离散搜索空间上时,我们显示出比以前研究的拉格朗日放松的最丰富的领域。我们提出了一种算法,用于绘制原始DIB权衡的Pareto前沿,该算法也适用于其他两种目标聚类问题。我们研究了帕累托边境的一般特性,并提供了总体上对数稀疏性的分析和数值证据。我们提供的证据表明,尽管有超过指数的搜索空间,但我们的算法具有多项式缩放,此外,我们提出了对算法的修改,该算法可以在预期采样噪声显着的情况下使用。最后,我们使用算法来绘制三个不同任务的DIB前沿:压缩英语字母,从自然图像中提取信息性的颜色类别,并压缩了一个以群体理论为灵感的数据集,揭示了Frontier的有趣特征,并演示了如何展示的结构。边界可用于模型选择,重点是先前由凸船斗篷隐藏的点。
translated by 谷歌翻译
迄今为止,通信系统主要旨在可靠地交流位序列。这种方法提供了有效的工程设计,这些设计对消息的含义或消息交换所旨在实现的目标不可知。但是,下一代系统可以通过将消息语义和沟通目标折叠到其设计中来丰富。此外,可以使这些系统了解进行交流交流的环境,从而为新颖的设计见解提供途径。本教程总结了迄今为止的努力,从早期改编,语义意识和以任务为导向的通信开始,涵盖了基础,算法和潜在的实现。重点是利用信息理论提供基础的方法,以及学习在语义和任务感知通信中的重要作用。
translated by 谷歌翻译
组合优化是运营研究和计算机科学领域的一个公认领域。直到最近,它的方法一直集中在孤立地解决问题实例,而忽略了它们通常源于实践中的相关数据分布。但是,近年来,人们对使用机器学习,尤其是图形神经网络(GNN)的兴趣激增,作为组合任务的关键构件,直接作为求解器或通过增强确切的求解器。GNN的电感偏差有效地编码了组合和关系输入,因为它们对排列和对输入稀疏性的意识的不变性。本文介绍了对这个新兴领域的最新主要进步的概念回顾,旨在优化和机器学习研究人员。
translated by 谷歌翻译
即使机器学习算法已经在数据科学中发挥了重要作用,但许多当前方法对输入数据提出了不现实的假设。由于不兼容的数据格式,或数据集中的异质,分层或完全缺少的数据片段,因此很难应用此类方法。作为解决方案,我们提出了一个用于样本表示,模型定义和培训的多功能,统一的框架,称为“ Hmill”。我们深入审查框架构建和扩展的机器学习的多个范围范式。从理论上讲,为HMILL的关键组件的设计合理,我们将通用近似定理的扩展显示到框架中实现的模型所实现的所有功能的集合。本文还包含有关我们实施中技术和绩效改进的详细讨论,该讨论将在MIT许可下发布供下载。该框架的主要资产是其灵活性,它可以通过相同的工具对不同的现实世界数据源进行建模。除了单独观察到每个对象的一组属性的标准设置外,我们解释了如何在框架中实现表示整个对象系统的图表中的消息推断。为了支持我们的主张,我们使用框架解决了网络安全域的三个不同问题。第一种用例涉及来自原始网络观察结果的IoT设备识别。在第二个问题中,我们研究了如何使用以有向图表示的操作系统的快照可以对恶意二进制文件进行分类。最后提供的示例是通过网络中实体之间建模域黑名单扩展的任务。在所有三个问题中,基于建议的框架的解决方案可实现与专业方法相当的性能。
translated by 谷歌翻译
对于一个合作探索未知环境的多机器人团队,至关重要的是,收集的信息可以在机器人之间有效共享,以支持勘探和导航任务。无线通道的实际限制(例如有限的带宽和位率)敦促机器人仔细选择要传输的信息。在本文中,我们考虑了使用3D场景图对环境信息进行建模的情况,这是一个层次模型,描述了环境的几何和语义方面。然后,我们利用图理论工具,即图形跨度,以设计有效压缩3D场景图的启发式策略,以在带宽约束下启用通信。我们的压缩策略以导航为导向,因为它们旨在在感兴趣的位置之间近乎保留最短的路径,同时满足用户指定的通信预算约束。通过广泛的数值分析和现实模拟器中的合成实验证明了所提出的算法的有效性。
translated by 谷歌翻译
随机块模型(SBM)是一个随机图模型,其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型,并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展,无论是在信息理论和计算方案方面,以及各种恢复要求,例如精确,部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换,Kesten-Stigum阈值弱恢复的相变,最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导,特别是通过绘制绘制,半定义编程,(线性化)信念传播,经典/非背带频谱和图形供电。还讨论了其他块模型的扩展,例如几何模型和一些开放问题。
translated by 谷歌翻译
行为树(BT)是一种在自主代理中(例如机器人或计算机游戏中的虚拟实体)之间在不同任务之间进行切换的方法。 BT是创建模块化和反应性的复杂系统的一种非常有效的方法。这些属性在许多应用中至关重要,这导致BT从计算机游戏编程到AI和机器人技术的许多分支。在本书中,我们将首先对BTS进行介绍,然后我们描述BTS与早期切换结构的关系,并且在许多情况下如何概括。然后,这些想法被用作一套高效且易于使用的设计原理的基础。安全性,鲁棒性和效率等属性对于自主系统很重要,我们描述了一套使用BTS的状态空间描述正式分析这些系统的工具。借助新的分析工具,我们可以对BTS如何推广早期方法的形式形式化。我们还显示了BTS在自动化计划和机器学习中的使用。最后,我们描述了一组扩展的工具,以捕获随机BT的行为,其中动作的结果由概率描述。这些工具可以计算成功概率和完成时间。
translated by 谷歌翻译
在这项工作中,我们向不确定性的决策问题介绍了一种新的有效的解决方案方法,可以在一个可能的高维状态空间中作为信仰空间中的决策制定。通常,为了解决决策问题,根据一些目标,应该识别来自一组候选者的最佳行动。我们声称人们通常可以生成并解决类似的尚未简化的决策问题,这可以更有效地解决。明智的简化方法可以导致相同的动作选择,或者可以保证最佳状态最大损耗的方法。此外,这种简化与状态推断分离,并且不会损害其精度,因为所选动作最终应用于原始状态。首先,我们介绍了一般决策问题的概念,并为这一方法的连贯制定提供了理论框架。然后,我们几乎将这些想法应用于信仰空间中的决策问题,这可以通过考虑初始信仰的稀疏近似来简化。我们提供的可扩展信念稀疏算法能够产生保证与原始问题一致的解决方案。我们展示了方法在解决现实主动场所问题的解决方案中的好处,并设法显着降低计算时间,在解决方案的质量上没有损失。这项工作既有基础实用,又拥有众多可能的扩展。
translated by 谷歌翻译
This paper surveys the recent attempts, both from the machine learning and operations research communities, at leveraging machine learning to solve combinatorial optimization problems. Given the hard nature of these problems, state-of-the-art algorithms rely on handcrafted heuristics for making decisions that are otherwise too expensive to compute or mathematically not well defined. Thus, machine learning looks like a natural candidate to make such decisions in a more principled and optimized way. We advocate for pushing further the integration of machine learning and combinatorial optimization and detail a methodology to do so. A main point of the paper is seeing generic optimization problems as data points and inquiring what is the relevant distribution of problems to use for learning on a given task.
translated by 谷歌翻译
The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.
translated by 谷歌翻译
随着优化软件的显着改进,几十年前似乎棘手的大规模问题的解决方案现在已成为日常任务。这将更多的现实应用程序纳入了优化器的范围。同时,解决优化问题通常是将解决方案付诸实践时较小的困难之一。一个主要的障碍是,可以将优化软件视为黑匣子,它可能会产生高质量的解决方案,但是当情况发生变化时,可以创建完全不同的解决方案,从而导致对优化解决方案的接受率低。这种可解释性和解释性的问题在其他领域(例如机器学习)引起了极大的关注,但在优化方面却不那么关注。在本文中,我们提出了一个优化框架,以得出本质上具有易于理解的解释性规则的解决方案,在哪些情况下应选择解决方案。我们专注于代表解释性规则的决策树,我们提出了整数编程公式以及一种启发式方法,以确保我们的方法即使在大规模问题上也适用。使用随机和现实世界数据的计算实验表明,固有的可解释性成本可能很小。
translated by 谷歌翻译
基于AI和机器学习的决策系统已在各种现实世界中都使用,包括医疗保健,执法,教育和金融。不再是牵强的,即设想一个未来,自治系统将推动整个业务决策,并且更广泛地支持大规模决策基础设施以解决社会最具挑战性的问题。当人类做出决定时,不公平和歧视的问题普遍存在,并且当使用几乎没有透明度,问责制和公平性的机器做出决定时(或可能会放大)。在本文中,我们介绍了\ textit {Causal公平分析}的框架,目的是填补此差距,即理解,建模,并可能解决决策设置中的公平性问题。我们方法的主要见解是将观察到数据中存在的差异的量化与基本且通常是未观察到的因果机制收集的因果机制的收集,这些机制首先会产生差异,挑战我们称之为因果公平的基本问题分析(FPCFA)。为了解决FPCFA,我们研究了分解差异和公平性的经验度量的问题,将这种变化归因于结构机制和人群的不同单位。我们的努力最终达到了公平地图,这是组织和解释文献中不同标准之间关系的首次系统尝试。最后,我们研究了进行因果公平分析并提出一本公平食谱的最低因果假设,该假设使数据科学家能够评估不同影响和不同治疗的存在。
translated by 谷歌翻译
这项正在进行的工作旨在为统计学习提供统一的介绍,从诸如GMM和HMM等经典模型到现代神经网络(如VAE和扩散模型)缓慢地构建。如今,有许多互联网资源可以孤立地解释这一点或新的机器学习算法,但是它们并没有(也不能在如此简短的空间中)将这些算法彼此连接起来,或者与统计模型的经典文献相连现代算法出现了。同样明显缺乏的是一个单一的符号系统,尽管对那些已经熟悉材料的人(如这些帖子的作者)不满意,但对新手的入境造成了重大障碍。同样,我的目的是将各种模型(尽可能)吸收到一个用于推理和学习的框架上,表明(以及为什么)如何以最小的变化将一个模型更改为另一个模型(其中一些是新颖的,另一些是文献中的)。某些背景当然是必要的。我以为读者熟悉基本的多变量计算,概率和统计以及线性代数。这本书的目标当然不是​​完整性,而是从基本知识到过去十年中极强大的新模型的直线路径或多或少。然后,目标是补充而不是替换,诸如Bishop的\ emph {模式识别和机器学习}之类的综合文本,该文本现在已经15岁了。
translated by 谷歌翻译
We propose a path planning methodology for a mobile robot navigating through an obstacle-filled environment to generate a reference path that is traceable with moderate sensing efforts. The desired reference path is characterized as the shortest path in an obstacle-filled Gaussian belief manifold equipped with a novel information-geometric distance function. The distance function we introduce is shown to be an asymmetric quasi-pseudometric and can be interpreted as the minimum information gain required to steer the Gaussian belief. An RRT*-based numerical solution algorithm is presented to solve the formulated shortest-path problem. To gain insight into the asymptotic optimality of the proposed algorithm, we show that the considered path length function is continuous with respect to the topology of total variation. Simulation results demonstrate that the proposed method is effective in various robot navigation scenarios to reduce sensing costs, such as the required frequency of sensor measurements and the number of sensors that must be operated simultaneously.
translated by 谷歌翻译
这项工作将重新审视关节波束形成(BF)和天线选择(AS)问题,以及其在不完美的通道状态信息(CSI)下的稳健光束成型(RBF)版本。在射频链的数量(RF)链的数量小于发射器上的天线元件的情况下,出现了此类问题,这已成为大型阵列时代的关键考虑。关节(r)bf \&作为问题是一个混合整数和非线性程序,因此发现{\ it最佳解决方案}通常是昂贵的,即使不是完全不可能。绝大多数先前的作品都使用基于连续优化的近似来解决这些问题 - 但是这些近似不能确保解决方案的最佳性甚至可行性。这项工作的主要贡献是三倍。首先,提出了一个有效的{\ it分支和绑定}(b \&b)解决感兴趣问题的框架。利用现有的BF和RBF求解器,表明B \&B框架保证了所考虑的问题的全球最优性。其次,为了加快潜在昂贵的B \&B算法,提出了一种基于机器学习(ML)的方案,以帮助跳过B \&B搜索树的中间状态。学习模型具有{\ it图形神经网络}(GNN)的设计,该设计对无线通信中通常遇到的挑战有抵抗力,即,培训和测试中问题大小的变化(例如,用户数量)的变化(例如,用户数量)阶段。第三,提出了全面的性能特征,表明基于GNN的方法在合理的条件下保留了B \&B的全球最佳性,其复杂性可降低。数值模拟还表明,基于ML的加速度通常可以相对于B \&b实现速度的速度。
translated by 谷歌翻译
我们为保留部分顺序的部分有序数据的基于相似性的分层群集提供了一个目标函数。也就是说,如果$ x \ le y $,如果$ [x] $和$ [y] $是$ x $和$ y $的相应群集,那么有一个订单关系$ \ LE' $群集$ [x] \ Le'| Y] $。该理论将本身与现有的理论区分开了用于统称有序数据的理论,因为顺序关系和相似性被组合成双目标优化问题,以获得寻求满足两者的分层聚类。特别地,顺序关系在$ [0,1] $的范围内加权,如果相似性和顺序关系未对齐,则订单保存可能必须屈服于群集。找到最佳解决方案是NP-HARD,因此我们提供多项式时间近似算法,具有$ O \左的相对性能保证(\ log ^ {3/2} \!\!\,n \右)$ ,基于定向稀疏性切割的连续应用。我们在基准数据集中提供了演示,显示我们的方法优于具有重要边距的顺序保留分层聚类的现有方法。该理论是划分分层聚类的Dasgupta成本函数的扩展。
translated by 谷歌翻译
We review clustering as an analysis tool and the underlying concepts from an introductory perspective. What is clustering and how can clusterings be realised programmatically? How can data be represented and prepared for a clustering task? And how can clustering results be validated? Connectivity-based versus prototype-based approaches are reflected in the context of several popular methods: single-linkage, spectral embedding, k-means, and Gaussian mixtures are discussed as well as the density-based protocols (H)DBSCAN, Jarvis-Patrick, CommonNN, and density-peaks.
translated by 谷歌翻译
我们研究了由Biclesting问题激励的新型多终端源编码设置。两个单独的编码器观察两个i.i.d.分别序列$ x ^ n $和$ y ^ n $。目标是找到速率有限的编码$ f(x ^ n)$和$ g(z ^ n)$,最大化相互信息$ i(f(x ^ n); g(y ^ n))/ n$。我们讨论了对独立性,模式识别和信息瓶颈方法的假设检验的这个问题的联系。改善内部和外界的先前基数界限使我们能够彻底地研究二进制对称源的特殊情况,并在这个特殊情况下量化内部和外部边界之间的间隙。此外,我们调查了互信息约束的首席运营官(CEO)问题的多个描述(MD)延伸。令人惊讶的是,这个MD-CEO问题允许了可实现的区域的紧密单信表征。
translated by 谷歌翻译