Directed information

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

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

,

where $I(X_{i:1};Y_{i}|Y_{i-1:1})$ is the conditional mutual information $I(X_{1},X_{2},...,X_{i};Y_{i}|Y_{1},Y_{2},...,Y_{i-1})$ .

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 $n$ terms and as $n$ grows its more and more challenging. There exists algorithms for optimizing the directed information based on Blahut-Arimoto algorithm such as [9] where the main idea is to start with the last element of the directed information and go backward. For estimation there exists an algorithm based on context tree weight [10] and on empirical parametric distributions [11].

gollark: solarflame5 = somewhat bees.

gollark: Most modern ARM/x86 chips have hardware acceleration for crypto operations.

gollark: Obviously it's just a bunch of transistors physically.

gollark: I mean that in the general sense.

gollark: Hardware encryption means your device is using a hardware mechanism to store keys or do the crypto operations.

References

Massey, James (1990). "Causality, Feedback And Directed Information" (ISITA). CiteSeerX 10.1.1.36.5688. Cite journal requires |journal= (help)
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.
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.
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.
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.
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. doi:10.1109/TAC.2017.2709618.
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. doi:10.1088/1742-5468/2016/04/043403.
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.
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.
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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[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.

[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.

[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.

[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.

[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. doi:10.1109/TAC.2017.2709618.

[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. doi:10.1088/1742-5468/2016/04/043403.

[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.

[10] 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.

[11] 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.