Directed information

Directed information, ${\displaystyle I(X^{n}\to Y^{n})}$, is a measure of information theory that measures the amount of information that flows from the process ${\displaystyle X^{n}}$ to ${\displaystyle Y^{n}}$, where ${\displaystyle X^{n}}$ denotes the vector ${\displaystyle X_{1},X_{2},...,X_{n}}$ and ${\displaystyle Y^{n}}$ denotes ${\displaystyle Y_{1},Y_{2},...,Y_{n}}$. The term directed information was coined by James Massey and is defined as

${\displaystyle I(X^{n}\to Y^{n})\triangleq \sum _{i=1}^{n}I(X_{i:1};Y_{i}|Y_{i-1:1})}$,

where ${\displaystyle I(X_{i:1};Y_{i}|Y_{i-1:1})}$ is the conditional mutual information ${\displaystyle I(X_{1},X_{2},...,X_{i};Y_{i}|Y_{1},Y_{2},...,Y_{i-1})}$. An equivalent definition but with slightly different notation

${\displaystyle I(X^{n}\to Y^{n})\triangleq \sum _{i=1}^{n}I(X^{i};Y_{i}|Y^{i-1})}$,

where ${\displaystyle X^{i}\triangleq X_{i:1}\triangleq (X_{1},X_{2},...,X_{i})}$.

The Directed information has many applications in problems where causality plays an important role such as capacity of channel with feedback,[1][2] capacity of discrete memoryless networks with feedback,[3] gambling with causal side information,[4] compression with causal side information,[5] and in real-time control communication settings,[6][7] statistical physics.[8]

Estimation and Optimization of Directed Information

Estimating and optimizing the directed information is challenging because it is an expression of multi-letter, namely, it contains ${\displaystyle n}$ terms and as ${\displaystyle n}$ grows its more and more challenging.

Optimization

There exist algorithms for optimizing the directed information based on Blahut-Arimoto,[9] Markov decision process,[10][11][12][13] and Recurrent Neural network[14] and Reinforcement learning.[15] For the case of Blahut-Arimoto,[16] the main idea is to start with the last element of the directed information and go backward. For the case of Markov decision process,[17][18][19][20] the main ideas is to transform the optimization into an infinite horizon average reward Markov decision process. For Recurrent Neural network[21] the main idea is to model the input diestribustionusing using the 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 allows us to deal with large oe even contnouse alphabet.

Estimation

The estimation of dircted information from given samples is a very hard problem since the dircted information expression does not depends on samples but on the joint distribusion ${\displaystyle \{P(x_{i},y_{i}|x^{i-1},y^{i-1}\}_{i=1}^{n})}$ which is unknown. There exist several algorithms based on context tree weight [23] and on empirical parametric distributions [24] and using Long short-term memory.[25]

References

1. Massey, James (1990). "Causality, Feedback And Directed Information" (ISITA). CiteSeerX 10.1.1.36.5688. Cite journal requires |journal= (help)
2. 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.
3. 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.
4. 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.
5. Simeone, Osvaldo; Permuter, Haim Henri (June 2013). "Source Coding When the Side Information May Be Delayed". IEEE Transactions on Information Theory. 59 (6): 3607–3618. arXiv:1109.1293. doi:10.1109/TIT.2013.2248192. S2CID 3211485.
6. 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.
7. Tanaka, Takashi; Esfahani, Peyman Mohajerin; Mitter, Sanjoy K. (January 2018). "LQG Control With Minimum Directed Information: Semidefinite Programming Approach". IEEE Transactions on Automatic Control. 63 (1): 37–52. arXiv:1510.04214. doi:10.1109/TAC.2017.2709618. S2CID 1401958.
8. Vinkler, Dror A; Permuter, Haim H; Merhav, Neri (20 April 2016). "Analogy between gambling and measurement-based work extraction". Journal of Statistical Mechanics: Theory and Experiment. 2016 (4): 043403. arXiv:1404.6788. Bibcode:2016JSMTE..04.3403V. doi:10.1088/1742-5468/2016/04/043403. S2CID 124719237.
9. Naiss, Iddo; Permuter, Haim H. (January 2013). "Extension of the Blahut–Arimoto Algorithm for Maximizing Directed Information". IEEE Transactions on Information Theory. 59 (1): 204–222. doi:10.1109/TIT.2012.2214202. S2CID 3115749.
10. Permuter, Haim; Cuff, Paul; Van Roy, Benjamin; Weissman, Tsachy (July 2008). "Capacity of the Trapdoor Channel With Feedback". IEEE Transactions on Information Theory. 54 (7): 3150–3165. arXiv:cs/0610047. doi:10.1109/TIT.2008.924681. S2CID 1265.
11. Elishco, Ohad; Permuter, Haim (September 2014). "Capacity and Coding for the Ising Channel With Feedback". IEEE Transactions on Information Theory. 60 (9): 5138–5149. arXiv:1205.4674. doi:10.1109/TIT.2014.2331951. S2CID 9761759.
12. 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.
13. Peled, Ori; Sabag, Oron; Permuter, Haim H. (July 2019). "Feedback Capacity and Coding for the $(0,k)$ -RLL Input-Constrained BEC". IEEE Transactions on Information Theory. 65 (7): 4097–4114. arXiv:1712.02690. doi:10.1109/TIT.2019.2903252. S2CID 86582654.
14. Aharoni, Ziv; Tsur, Dor; Goldfeld, Ziv; Permuter, Haim Henry (16 May 2020). "Capacity of Continuous Channels with Memory via Directed Information Neural Estimator". arXiv:2003.04179 [cs.IT].
15. 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].
16. Naiss, Iddo; Permuter, Haim H. (January 2013). "Extension of the Blahut–Arimoto Algorithm for Maximizing Directed Information". IEEE Transactions on Information Theory. 59 (1): 204–222. doi:10.1109/TIT.2012.2214202. S2CID 3115749.
17. Permuter, Haim; Cuff, Paul; Van Roy, Benjamin; Weissman, Tsachy (July 2008). "Capacity of the Trapdoor Channel With Feedback". IEEE Transactions on Information Theory. 54 (7): 3150–3165. arXiv:cs/0610047. doi:10.1109/TIT.2008.924681. S2CID 1265.
18. Elishco, Ohad; Permuter, Haim (September 2014). "Capacity and Coding for the Ising Channel With Feedback". IEEE Transactions on Information Theory. 60 (9): 5138–5149. arXiv:1205.4674. doi:10.1109/TIT.2014.2331951. S2CID 9761759.
19. 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.
20. Peled, Ori; Sabag, Oron; Permuter, Haim H. (July 2019). "Feedback Capacity and Coding for the $(0,k)$ -RLL Input-Constrained BEC". IEEE Transactions on Information Theory. 65 (7): 4097–4114. arXiv:1712.02690. doi:10.1109/TIT.2019.2903252. S2CID 86582654.
21. Aharoni, Ziv; Tsur, Dor; Goldfeld, Ziv; Permuter, Haim Henry (16 May 2020). "Capacity of Continuous Channels with Memory via Directed Information Neural Estimator". arXiv:2003.04179 [cs.IT].
22. 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].
23. Jiao, Jiantao; Permuter, Haim H.; Zhao, Lei; Kim, Young-Han; Weissman, Tsachy (October 2013). "Universal Estimation of Directed Information". IEEE Transactions on Information Theory. 59 (10): 6220–6242. arXiv:1201.2334. doi:10.1109/TIT.2013.2267934. S2CID 10855063.
24. Quinn, Christopher J.; Kiyavash, Negar; Coleman, Todd P. (December 2015). "Directed Information Graphs". IEEE Transactions on Information Theory. 61 (12): 6887–6909. arXiv:1204.2003. doi:10.1109/TIT.2015.2478440. S2CID 3121664.
25. Aharoni, Z.; Tsur, D.; Goldfeld, Z.; Permuter, H. H. (June 2020). "Capacity of Continuous Channels with Memory via Directed Information Neural Estimator". 2020 IEEE International Symposium on Information Theory (ISIT): 2014–2019. arXiv:2003.04179. doi:10.1109/ISIT44484.2020.9174109.