论文标题
资源感知信息理论树抽象的线性编程方法
A Linear Programming Approach for Resource-Aware Information-Theoretic Tree Abstractions
论文作者
论文摘要
在本章中，提出了用于获得与任务相关的多分辨率，环境抽象的问题的整数线性编程公式。该公式从信息理论信号压缩（特别是信息瓶颈（IB）方法）中利用概念，以在多分辨率树的空间上作为最佳编码器搜索提出抽象问题。抽象以与任务相关的方式出现，作为代理信息处理约束的函数。我们详细介绍我们的配方，并展示如何以共同的主题统一信号压缩的层次结构结构，信号编码器和信息理论方法。提出了一个讨论，描述了我们配方的好处和缺点，以及详细的解释，如何在为资源受限的自主系统生成抽象的背景下解释我们的方法。结果表明，在多分辨率树空间中所得的信息理论抽象问题可以作为整数线性编程（ILP）问题进行配合。我们在许多示例上演示了这种方法，并提供了与现有方法相比，详细说明所提出框架的差异的讨论。最后，我们考虑了ILP问题的线性程序松弛，从而证明可以通过求解凸程序来获得多分辨率信息理论树抽象。
In this chapter, an integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, environment abstractions for resource-constrained autonomous agents is presented. The formulation leverages concepts from information-theoretic signal compression, specifically, the information bottleneck (IB) method, to pose an abstraction problem as an optimal encoder search over the space of multi-resolution trees. The abstractions emerge in a task-relevant manner as a function of agent information-processing constraints. We detail our formulation, and show how hierarchical tree structures, signal encoders, and information-theoretic methods for signal compression can be unified under a common theme. A discussion delineating the benefits and drawbacks of our formulation is presented, as well as a detailed explanation how our approach can be interpreted within the context of generating abstractions for resource-constrained autonomous systems. It is shown that the resulting information-theoretic abstraction problem over the space of multi-resolution trees can be formulated as a integer linear programming (ILP) problem. We demonstrate the approach on a number of examples, and provide a discussion detailing the differences of the proposed framework compared to existing methods. Lastly, we consider a linear program relaxation of the ILP problem, thereby demonstrating that multi-resolution information-theoretic tree abstractions can be obtained by solving a convex program.
