Towards a generalization of information theory for hierarchical partitions

• URL: http://arxiv.org/abs/2003.02911v2
• Date: Tue, 30 Jun 2020 22:11:19 GMT
• Title: Towards a generalization of information theory for hierarchical partitions
• Authors: Juan I. Perotti, Nahuel Almeira, Fabio Saracco
• Abstract summary: We introduce a generalization of information theory that works with hierarchical partitions. In particular, we derive hierarchical generalizations of many other classical information-theoretic quantities.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Complex systems often exhibit multiple levels of organization covering a wide range of physical scales, so the study of the hierarchical decomposition of their structure and function is frequently convenient. To better understand this phenomenon, we introduce a generalization of information theory that works with hierarchical partitions. We begin revisiting the recently introduced Hierarchical Mutual Information (HMI), and show that it can be written as a level by level summation of classical conditional mutual information terms. Then, we prove that the HMI is bounded from above by the corresponding hierarchical joint entropy. In this way, in analogy to the classical case, we derive hierarchical generalizations of many other classical information-theoretic quantities. In particular, we prove that, as opposed to its classical counterpart, the hierarchical generalization of the Variation of Information is not a metric distance, but it admits a transformation into one. Moreover, focusing on potential applications of the existing developments of the theory, we show how to adjust by chance the HMI. We also corroborate and analyze all the presented theoretical results with exhaustive numerical computations, and include an illustrative application example of the introduced formalism. Finally, we mention some open problems that should be eventually addressed for the proposed generalization of information theory to reach maturity.

Related papers

• Learning Discrete Concepts in Latent Hierarchical Models [73.01229236386148]
  Learning concepts from natural high-dimensional data holds potential in building human-aligned and interpretable machine learning models. We formalize concepts as discrete latent causal variables that are related via a hierarchical causal model. We substantiate our theoretical claims with synthetic data experiments.
  arXiv  Detail & Related papers  (2024-06-01T18:01:03Z)
• Class-wise Generalization Error: an Information-Theoretic Analysis [22.877440350595222]
  We study the class-generalization error, which quantifies the generalization performance of each individual class. We empirically validate our proposed bounds in different neural networks and show that they accurately capture the complex class-generalization error behavior.
  arXiv  Detail & Related papers  (2024-01-05T17:05:14Z)
• Derivation of Standard Quantum Theory via State Discrimination [53.64687146666141]
  General Probabilistic Theories (GPTs) is a new information theoretical approach to single out standard quantum theory. We focus on the bound of the performance for an information task called state discrimination in general models. We characterize standard quantum theory out of general models in GPTs by the bound of the performance for state discrimination.
  arXiv  Detail & Related papers  (2023-07-21T00:02:11Z)
• DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion [66.21290235237808]
  We introduce an energy constrained diffusion model which encodes a batch of instances from a dataset into evolutionary states. We provide rigorous theory that implies closed-form optimal estimates for the pairwise diffusion strength among arbitrary instance pairs. Experiments highlight the wide applicability of our model as a general-purpose encoder backbone with superior performance in various tasks.
  arXiv  Detail & Related papers  (2023-01-23T15:18:54Z)
• Bridging the gap between classical and quantum many-body information dynamics [0.0]
  Study sheds light on the nature of information spreading in classical and quantum systems. It opens new avenues for quantum-inspired classical approaches across physics, information theory, and statistics.
  arXiv  Detail & Related papers  (2022-04-06T18:03:29Z)
• Rate-Distortion Theoretic Generalization Bounds for Stochastic Learning Algorithms [12.020634332110147]
  We prove novel generalization bounds through the lens of rate-distortion theory. Our results bring a more unified perspective on generalization and open up several future research directions.
  arXiv  Detail & Related papers  (2022-03-04T18:12:31Z)
• Effect Identification in Cluster Causal Diagrams [51.42809552422494]
  We introduce a new type of graphical model called cluster causal diagrams (for short, C-DAGs) C-DAGs allow for the partial specification of relationships among variables based on limited prior knowledge. We develop the foundations and machinery for valid causal inferences over C-DAGs.
  arXiv  Detail & Related papers  (2022-02-22T21:27:31Z)
• CPM Categories for Galois Extensions [0.0]
  We develop an infinite hierarchy of probabilistic theories, exhibiting compositional decoherence structures. These decoherences reduce the degrees of freedom in physical systems, while at the same time restricting the fields over which the systems are defined. These theories possess fully fledged operational semantics, allowing both categorical and GPT-style approaches to their study.
  arXiv  Detail & Related papers  (2021-06-02T14:52:41Z)
• In Search of Robust Measures of Generalization [79.75709926309703]
  We develop bounds on generalization error, optimization error, and excess risk. When evaluated empirically, most of these bounds are numerically vacuous. We argue that generalization measures should instead be evaluated within the framework of distributional robustness.
  arXiv  Detail & Related papers  (2020-10-22T17:54:25Z)
• The Role of Mutual Information in Variational Classifiers [47.10478919049443]
  We study the generalization error of classifiers relying on encodings trained on the cross-entropy loss. We derive bounds to the generalization error showing that there exists a regime where the generalization error is bounded by the mutual information.
  arXiv  Detail & Related papers  (2020-10-22T12:27:57Z)

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.