Information-Theoretic Abstractions for Resource-Constrained Agents via Mixed-Integer Linear Programming

• URL: http://arxiv.org/abs/2102.10015v1
• Date: Fri, 19 Feb 2021 16:34:47 GMT
• Title: Information-Theoretic Abstractions for Resource-Constrained Agents via Mixed-Integer Linear Programming
• Authors: Daniel T. Larsson, Dipankar Maity, Panagiotis Tsiotras
• Abstract summary: 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.
• Score: 11.247580943940916
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, a mixed-integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, graph abstractions for resource-constrained agents is presented. The formulation leverages concepts from information-theoretic signal compression, specifically the information bottleneck (IB) method, to pose a graph 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, and are not provided to the system a priori. We detail our formulation and show how the problem can be realized as an integer linear program. A non-trivial numerical example is presented to demonstrate the utility in employing our approach to obtain hierarchical tree abstractions for resource-limited agents.

Related papers

• Consciousness-Inspired Spatio-Temporal Abstractions for Better Generalization in Reinforcement Learning [83.41487567765871]
  Skipper is a model-based reinforcement learning framework. It automatically generalizes the task given into smaller, more manageable subtasks. It enables sparse decision-making and focused abstractions on the relevant parts of the environment.
  arXiv  Detail & Related papers  (2023-09-30T02:25:18Z)
• Promise and Limitations of Supervised Optimal Transport-Based Graph Summarization via Information Theoretic Measures [3.179831861897336]
  Graph summarization is the problem of producing smaller graph representations of an input graph dataset. We consider the problem of supervised graph summarization, wherein by using information theoretic measures we seek to preserve relevant information about a class label. We propose a summarization method that incorporates mutual information estimates between random variables associated with sample graphs and class labels into the optimal transport compression framework.
  arXiv  Detail & Related papers  (2023-05-11T21:03:34Z)
• 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)
• A Linear Programming Approach for Resource-Aware Information-Theoretic Tree Abstractions [16.565205172451662]
  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.
  arXiv  Detail & Related papers  (2022-08-08T15:44:09Z)
• Towards Explanation for Unsupervised Graph-Level Representation Learning [108.31036962735911]
  Existing explanation methods focus on the supervised settings, eg, node classification and graph classification, while the explanation for unsupervised graph-level representation learning is still unexplored. In this paper, we advance the Information Bottleneck principle (IB) to tackle the proposed explanation problem for unsupervised graph representations, which leads to a novel principle, textitUnsupervised Subgraph Information Bottleneck (USIB) We also theoretically analyze the connection between graph representations and explanatory subgraphs on the label space, which reveals that the robustness of representations benefit the fidelity of explanatory subgraphs.
  arXiv  Detail & Related papers  (2022-05-20T02:50:15Z)
• 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)
• Abstractive Query Focused Summarization with Query-Free Resources [60.468323530248945]
  In this work, we consider the problem of leveraging only generic summarization resources to build an abstractive QFS system. We propose Marge, a Masked ROUGE Regression framework composed of a novel unified representation for summaries and queries. Despite learning from minimal supervision, our system achieves state-of-the-art results in the distantly supervised setting.
  arXiv  Detail & Related papers  (2020-12-29T14:39:35Z)
• 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)
• On the Information Bottleneck Problems: Models, Connections, Applications and Information Theoretic Views [39.49498500593645]
  This tutorial paper focuses on the variants of the bottleneck problem taking an information theoretic perspective. It discusses practical methods to solve it, as well as its connection to coding and learning aspects.
  arXiv  Detail & Related papers  (2020-01-31T15:23:19Z)

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.