Information Flow in Computational Systems
arXiv:1902.02292 · doi:10.1109/TIT.2020.2987806
Abstract
We develop a theoretical framework for defining and identifying flows of information in computational systems. Here, a computational system is assumed to be a directed graph, with "clocked" nodes that send transmissions to each other along the edges of the graph at discrete points in time. We are interested in a definition that captures the dynamic flow of information about a specific message, and which guarantees an unbroken "information path" between appropriately defined inputs and outputs in the directed graph. Prior measures, including those based on Granger Causality and Directed Information, fail to provide clear assumptions and guarantees about when they correctly reflect information flow about a message. We take a systematic approach---iterating through candidate definitions and counterexamples---to arrive at a definition for information flow that is based on conditional mutual information, and which satisfies desirable properties, including the existence of information paths. Finally, we describe how information flow might be detected in a noiseless setting, and provide an algorithm to identify information paths on the time-unrolled graph of a computational system.
Significantly revised version which was accepted for publication at the IEEE Transactions on Information Theory
References in corpus (7)
- Kernel-based Conditional Independence Test and Application in Causal Discovery
- Nonnegative Decomposition of Multivariate Information
- Estimating Mutual Information for Discrete-Continuous Mixtures
- Mitigating the effects of measurement noise on Granger causality
- Testing conditional independence using maximal nonlinear conditional correlation
- Interactive Martingale Tests for the Global Null
- In reply to Faes et al. and Barnett et al. regarding "A study of problems encountered in Granger causality analysis from a neuroscience perspective"