A Linear Programming Approach for Resource-Aware Information-Theoretic Tree Abstractions

• URL: http://arxiv.org/abs/2208.04220v1
• Date: Mon, 8 Aug 2022 15:44:09 GMT
• Title: A Linear Programming Approach for Resource-Aware Information-Theoretic Tree Abstractions
• Authors: Daniel T. Larsson and Dipankar Maity and Panagiotis Tsiotras
• Abstract summary: We present an integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, environment abstractions for resource-constrained autonomous agents. We show how hierarchical tree structures, signal encoders, and information-theoretic methods for signal compression can be unified under a common theme. 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.
• Score: 16.565205172451662
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Learning to Solve Abstract Reasoning Problems with Neurosymbolic Program Synthesis and Task Generation [0.8701566919381223]
  We present TransCoder, a method for solving abstract problems based on neural program synthesis. We conduct a comprehensive analysis of decisions made by the generative module of the proposed architecture.
  arXiv  Detail & Related papers  (2024-10-06T13:42:53Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• Ideal Abstractions for Decision-Focused Learning [108.15241246054515]
  We propose a method that configures the output space automatically in order to minimize the loss of decision-relevant information. We demonstrate the method in two domains: data acquisition for deep neural network training and a closed-loop wildfire management task.
  arXiv  Detail & Related papers  (2023-03-29T23:31:32Z)
• Explainable Data-Driven Optimization: From Context to Decision and Back Again [76.84947521482631]
  Data-driven optimization uses contextual information and machine learning algorithms to find solutions to decision problems with uncertain parameters. We introduce a counterfactual explanation methodology tailored to explain solutions to data-driven problems. We demonstrate our approach by explaining key problems in operations management such as inventory management and routing.
  arXiv  Detail & Related papers  (2023-01-24T15:25:16Z)
• Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
  A dataset of inter-dependent signals is defined as a matrix whose columns demonstrate strong dependencies. A neural network is employed to act as structure prior and reveal the underlying signal interdependencies. Deep unrolling and Deep equilibrium based algorithms are developed, forming highly interpretable and concise deep-learning-based architectures.
  arXiv  Detail & Related papers  (2022-03-29T21:00:39Z)
• Information-Theoretic Abstractions for Resource-Constrained Agents via Mixed-Integer Linear Programming [11.247580943940916]
  We present a mixed-integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, graph abstractions for resource-constrained agents. A non-trivial numerical example is presented to demonstrate the utility in employing our approach to obtain hierarchical tree abstractions for resource-limited agents.
  arXiv  Detail & Related papers  (2021-02-19T16:34:47Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Information-Theoretic Abstractions for Planning in Agents with Computational Constraints [16.565205172451662]
  We show how a path-planning problem in an environment can be systematically approximated by solving a sequence of easier to solve problems on abstractions of the original space. A numerical example is presented to show the utility of the approach and to corroborate the theoretical findings.
  arXiv  Detail & Related papers  (2020-05-19T17:32:10Z)
• Invariant Causal Prediction for Block MDPs [106.63346115341862]
  Generalization across environments is critical to the successful application of reinforcement learning algorithms to real-world challenges. We propose a method of invariant prediction to learn model-irrelevance state abstractions (MISA) that generalize to novel observations in the multi-environment setting.
  arXiv  Detail & Related papers  (2020-03-12T21:03:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.