Directed information is an information theory measure that quantifies the information flow from the random string to the random string . The term directed information was coined by James Massey and is defined as[1]
| This article provides insufficient context for those unfamiliar with the subject. (September 2016) |
where is the conditional mutual information .
Directed information has applications to problems where causality plays an important role such as the capacity of channels with feedback,[1][2][3][4] capacity of discrete memoryless networks,[5] capacity of networks with in-block memory,[6] gambling with causal side information,[7] compression with causal side information,[8] real-time control communication settings,[9][10] and statistical physics.[11]
The essence of directed information is causal conditioning. The probability of causally conditioned on is defined as[5]
- .
This is similar to the chain rule for conventional conditioning except one conditions on "past" and "present" symbols rather than all symbols . To include "past" symbols only, one can introduce a delay by prepending a constant symbol:
- .
It is common to abuse notation by writing for this expression, although formally all strings should have the same number of symbols.
One may also condition on multiple strings: .
Causally conditioned entropy
The causally conditioned entropy is defined as:[2]
Similarly, one may causally condition on multiple strings and write
.
A decomposition rule for causal conditioning[1] is
- .
This rule shows that any product of gives a joint distribution .
The causal conditioning probability is a probability vector, i.e.,
- .
Directed Information can be written in terms of causal conditioning:[2]
- .
The relation generalizes to three strings: the directed information flowing from to causally conditioned on is
- .
Estimating and optimizing the directed information is challenging because it has terms where may be large. In many cases, one is interested in optimizing the limiting average, that is, when grows to infinity termed as a multi-letter expression.
Estimation
Estimating directed information from samples is a hard problem since the directed information expression does not depend on samples but on the joint distribution which may be unknown. There are several algorithms based on context tree weighting[14] and empirical parametric distributions[15] and using long short-term memory.[16]
Optimization
Maximizing directed information is a fundamental problem in information theory. For example, given the channel distributions , the objective might be to optimize over the channel input distributions .
There are algorithms to optimize the directed information based on the Blahut-Arimoto,[17] Markov decision process,[18][19][20][21] Recurrent neural network,[16] Reinforcement learning.[22] and Graphical methods (the Q-graphs).[23][24]
For the Blahut-Arimoto algorithm,[17] the main idea is to start with the last mutual information of the directed information expression and go backward. For the Markov decision process,[18][19][20][21] the main ideas is to transform the optimization into an infinite horizon average reward Markov decision process. For a Recurrent neural network,[16] the main idea is to model the input distribution using a Recurrent neural network and optimize the parameters using Gradient descent. For Reinforcement learning,[22] the main idea is to solve the Markov decision process formulation of the capacity using Reinforcement learning tools, which lets one deal with large or even continuous alphabets.
Massey's directed information was motivated by Marko's early work (1966) on developing a theory of bidirectional communication.[25][26] Marko's definition of directed transinformation differs slightly from Massey's in that, at time , one conditions on past symbols only and one takes limits:
Marko defined several other quantities, including:
- Total information: and
- Free information: and
- Coincidence:
The total information is usually called an entropy rate. Marko showed the following relations for the problems he was interested in:
- and
He also defined quantities he called residual entropies:
and developed the conservation law and several bounds.
Directed information is related to transfer entropy, which is a truncated version of Marko's directed transinformation .
The transfer entropy at time and with memory is
where one does not include the present symbol or the past symbols before time .
Transfer entropy usually assumes stationarity, i.e., does not depend on the time .
Massey, James (1990). "Causality, Feedback And Directed Information". Proceedings 1990 International Symposium on Information Theory and its Applications, Waikiki, Hawaii, Nov. 27-30, 1990.
Permuter, Haim Henry; Weissman, Tsachy; Goldsmith, Andrea J. (February 2009). "Finite State Channels With Time-Invariant Deterministic Feedback". IEEE Transactions on Information Theory. 55 (2): 644–662. arXiv:cs/0608070. doi:10.1109/TIT.2008.2009849. S2CID 13178. Kramer, G. (January 2003). "Capacity results for the discrete memoryless network". IEEE Transactions on Information Theory. 49 (1): 4–21. doi:10.1109/TIT.2002.806135. Permuter, Haim H.; Kim, Young-Han; Weissman, Tsachy (June 2011). "Interpretations of Directed Information in Portfolio Theory, Data Compression, and Hypothesis Testing". IEEE Transactions on Information Theory. 57 (6): 3248–3259. arXiv:0912.4872. doi:10.1109/TIT.2011.2136270. S2CID 11722596. Charalambous, Charalambos D.; Stavrou, Photios A. (August 2016). "Directed Information on Abstract Spaces: Properties and Variational Equalities". IEEE Transactions on Information Theory. 62 (11): 6019–6052. arXiv:1302.3971. doi:10.1109/TIT.2016.2604846. S2CID 8107565. Sabag, Oron; Permuter, Haim H.; Kashyap, Navin (January 2016). "The Feedback Capacity of the Binary Erasure Channel With a No-Consecutive-Ones Input Constraint". IEEE Transactions on Information Theory. 62 (1): 8–22. doi:10.1109/TIT.2015.2495239. S2CID 476381. Aharoni, Ziv; Sabag, Oron; Permuter, Haim Henri (18 August 2020). "Reinforcement Learning Evaluation and Solution for the Feedback Capacity of the Ising Channel with Large Alphabet". arXiv:2008.07983 [cs.IT]. Sabag, Oron; Permuter, Haim Henry; Pfister, Henry (March 2017). "A Single-Letter Upper Bound on the Feedback Capacity of Unifilar Finite-State Channels". IEEE Transactions on Information Theory. 63 (3): 1392–1409. arXiv:1604.01878. doi:10.1109/TIT.2016.2636851. S2CID 3259603. Marko, H. (December 1973). "The Bidirectional Communication Theory--A Generalization of Information Theory". IEEE Transactions on Communications. 21 (12): 1345–1351. doi:10.1109/TCOM.1973.1091610. S2CID 51664185.