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: Philosophically, yes. According to common use, no.

gollark: Kind of fooling you into believing you're talking to a human isn't exactly an indicator of human level intelligence.

gollark: That's kind of ad hominem. Stuff can still be true if a deterministic process says it.

gollark: Well, the free will thing here seems to just be that somehow you magically get nondeterminism introduced somewhere.

gollark: I mean, if you have some neuron which happens to randomly flick on and off nondeterministically, does that add free will now?

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.