易处理模型推理的统一框架

A Compositional Atlas of Tractable Circuit Operations: From Simple Transformations to Complex Information-Theoretic Queries

摘要：

电路表示正在成为表达和推理易处理的生成和鉴别模型的通用语言。在本文中，我们展示了机器学习中常见的这些模型的复杂推理场景(从计算决策树集成的期望到深度混合模型的信息论分歧)如何可以用电路上易处理的模块化操作来表示。具体而言，我们根据简单变换(和、积、商、幂、对数和指数)所操作的电路的充分结构约束来表征它们的易处理性，并针对这些性质不满足的情况给出新颖的硬度结果。在这些操作的基础上，我们得到了一个关于易处理模型的推理的统一框架，它概括了文献中的几个结果，并开辟了新的易处理推理场景

图表概览：

简介：

在这篇文章中，我们引入了一个统一的框架来推理易处理的模型类。概率ML和AI中常见的许多查询。通过将复杂的查询重写为简单操作的组合并通过后者推动充分的条件来研究易处理性，从而产生丰富的图谱，可以指导和启发未来的研究。

我们的属性驱动分析解决了许多关于电路特例的模型类查询的易处理性和困难性的公开问题。然而，其他有趣的问题仍然开放，并构成未来可能的方向。例如，演示我们的表示的无条件下限，或者将我们的分析扩展到涉及最大化的查询——也就是说，在概率分布上进行映射推断。另一方面，我们的图谱可以以不同的方式支持电路学习程序的设计。一、现有算法(Rahman et al .，2014；Vergari等人，2015年；Peharz等人，2019；Dang et al .，2020)可以通过我们的新转换来丰富，以生成易处理的结构。第二，我们的分析可以帮助设计新的算法来学习电路，这些电路被定制为一次有效地回答多个查询，在一种多目标优化场景中，算法在不同查询之间权衡电路大小。

完整内容请参考原论文。