Ergodic decomposition of excess entropy and conditional mutual information

• Autorzy: Dębowski Ł.

Warianty tytułu

PL

Rozkład ergodyczny entropii nadwyżkowej a warunkowa informacja wzajemna

• Języki publikacji: EN

Abstrakty

EN

The article discusses excess entropy defined as mutual information between the past and future of a stationary process. The central result is an ergodic decomposition: Excess entropy is the sum of self-information of shift-invariant sigma-field and the average of excess entropies for the ergodic components of the process. The result is derived using generalized conditional mutual information for fields of events, developed in the paper anew. Some corollary of the ergodic decomposition is that excess entropy is infinite for the class of processes with uncountably many ergodic components, called here uncountable description processes (UDP's). UDP's can be defined without the use of measure theory and the article argues for their potential utility in linguistics. Moreover, it is shown that finite-order excess entropies (some approximations of excess entropy) are dominated by the expected excess lengths of any universal code. Hence, universal codes may be used for rough estimation of excess entropy. Nevertheless, the excess code lengths diverge to infinity for almost every process with zero excess entropy, which is another corollary of the ergodic decomposition.

PL

W artykule omówiono pojęcie entropii nadwyżkowej zdefiniowanej jako informacja wzajemna między przeszłością a przyszłością procesu stacjonarnego. Centralnym rezulatem jest rozkład ergodyczny entropii nadwyżkowej: Entropia nadwyżkowa równa jest sumie entropii sigma-ciała niezmienniczego i wartości oczekiwanej entropii nadwyżkowej losowej miary ergodycznej procesu. Rezultat ten wynika z własności uogólnionej warunkowej informacji wzajemnej, rozwiniętej w artykule w nowatorski sposób. Korzystając z otrzymanego rozkładu ergodycznego, udowodniono, że entropia nadwyżkowa jest nieskończona dla klasy procesów o nieprzeliczalnie wielu składowych ergodycznych, nazwanych procesami nieprzeliczalnego opisu (PNO). Pokazano, że PNO można zdefiniować bez użycia aparatu teoriomiarowego, i zaargumentowano za ich potencjalną użytecznością w lingwistyce. Ponadto udowodniono, że entropie nadwyżkowej skończonego rzędu (pewne przybliżenia entropii nadwyżkowej) są majoryzowane przez nadwyżkowe długości dowolnego kodu uniwersalnego. Zatem kody uniwersalne mogą służyć do zgrubnego szacowania entropii nadwyżkowej. Jednakże, z rozkładu ergodycznego wynika także, że nadwyżkowe długości kodów uniwersalnych rozbiegają do nieskończoności dla prawie każdego procesu o zerowej entropii nadwyżkowej.

Słowa kluczowe

EN

conditional mutual information for sigma-fields; ergodic decomposition; excess entropy; uncountable description processes; halting probability; universal coding; algorithmic mutual information

PL

warunkowa informacja wzajemna dla sigma-ciał; rozkład ergodyczny; entropia nadwyżkowa; procesy nieprzeliczanego opisu; prwdopodobieństwo stopu; kodowanie uniwersalne; algorytmiczna informacja wzajemna

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2006
• Tom: Nr 993
• Strony: 1--34
• Opis fizyczny: Bibliogr. 53 poz.

Twórcy

autor

Dębowski Ł.

• Instytut Podstaw Informatyki PAN Ul. Ordona 21 01-237 Warszawa Polska,

Bibliografia

• [1] J. M. Barzdins and Preivalds. On the prediction of general recursive functions. Soviet Mathematics. Doklady, 13:1251-1254, 1972.
• [2] J. Beran. Statistics for Long-Memory Processes. New York: Chapman & Hall, 1994.
• [3] V. Berthe. Conditional entropy of some automatic sequences. Journal of Physics A, 27:7993-8006, 1994.
• [4] W. Białek, L Nemenman, and N. Tishby. Complexity through nonextensivity. Physica A, 302:89-99, 2001.
• [5] W. Białek, L Nemenman, and N. Tishby. Predictability, complexity and learning. Neural Computation, 13:2409, 2001.
• [6] P. Billingsley. Ergodic Theory and Information. New York: Wiley, 1965.
• [7] P. Billingsley. Probability and Measure. New York: Wiley, 1979.
• [8] P. Bloomfield, N. P. Jewell, and E. Hayashi. Characterizations of completely nondeterministic stochastic process. Pacific Journal of Mathematics, 107:307-317, 1983.
• [9] R. C. Bradley. On the strong mixing and weak Bernoulli conditions. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 50:49-54, 1980.
• [10] P. J. Brockwell and R. A. Davis. Time Series: Theory and Methods. New York: Springer, 1987.
• [11] G. J. Chaitin. A theory of program size formally identical to information theory. Journal of the ACM, 22:329-340, 1975.
• [12] M. Charikar, E. Lehman, A. Lehman, D. Liu, R. Panigrahy, M. Prabhakaran, A. Sahai, and A. Shelat. The smallest grammar problem. IEEE Tmnsactions on Information Theory, 51:2554-2576, 2005.
• [13] T. M. Cover, P. Gacs, and R. M. Gray. Kolmogorov's contributions to information theory and algorithmic complexity. Annals of Probability, 17:840-865, 1989.
• [14] T. M. Cover and J. A. Thomas. Elements of Information Theory. New York: Wiley, 1991.
• [15] J. P. Crutchfield and D. P. Feldman. Regularities unseen, ran-domness observed: The entropy convergence hierarchy. Chaos, 15: 25-54, 2003.
• [16] L. D. Davisson. Universal noiseless coding. IEEE Transactions on Information Theory, 19:783-795, 1973.
• [17] Ł. Dębowski. Excess entropy for stochastic processes over various alphabets. PhD thesis, Institute of Computer Science, Polish Academy of Sciences, 2005. In Polish.
• [18] Ł. Dębowski. Menzerath's law for the smallest grammars. In R. Köhler and P. Grzybek, editors, The Exact Science of Language and Text. 2006. To appear.
• [19] Ł. Dębowski. On Hilberg's law and its links with Guiraud's law. Journal of Quantitative Linguistics, 13:81-109, 2006.
• [20] R. L. Dobrushin. A generał formulation of the fundamental Shannon theorems in information theory. Uspekhi Matematicheskikh Nauk, 14(6):3-104, 1959. In Russian.
• [21] R. G. Downey. Some recent progress in algorithmic randomness. In J. Fiala, V. Koubek, and J. Kratochvil, editors, Mathematical Foundations of Computer Science 2004, 29th International Symposium., pages 42-83. Springer, 2004.
• [22] J. Durbin. The fitting of time series models. Review of the International Statistical Institute, 28:233-244, 1960.
• [23] W. Ebeling and G. Nicolis. Entropy of symbolic sequences: the role of correlations. Europhysics Letters, 14:191-196, 1991.
• [24] W. Ebeling and G. Nicolis. Word frequency and entropy of symbolic sequences: a dynamical perspective. Chaos, Solitons and Practals, 2:635-650, 1992.
• [25] W. Ebeling and T. Pöschel. Entropy and long-range correlations in literary English. Europhysics Letters, 26:241-246, 1994.
• [26] Y. Ephraim and N. Merhav. Hidden Markov processes. IEEE Transactions on Information Theory, 48:1518-1569, 2002.
• [27] P. D. Finch. On the covariance determinants of autoregressive and moving average models. Biometrika, 47:194-211, 1960.
• [28] L M. Gelfand, A. N. Kolmogorov, and A. M. Yaglom. Towards the general definition of the amount of Information. Doklady Akademii Nauk SSSR, 111:745-748, 1956. In Russian.
• [29] T. Gramss. Entropy of the symbolic seąuence for critical circle maps. Physical Rewew E, 50:2616-2620, 1994.
• [30] R. M. Gray and L. D. Davisson. The ergodic decomposition of stationary discrete random processses. IEEE Transactions on Information Theory, 20:625-636, 1974.
• [31] R. M. Gray and L. D. Davisson. Source coding theorems without the ergodic assumption. IEEE Transactions on Information Theory, 20: 502-516, 1974.
• [32] U. Grenander and G. Szegö. Toeplitz Forms and Their Applications. Berkeley: University of California Press, 1958.
• [33] P. Grunwald and P. Vitanyi. Shannon Information and Kolmogorov complexity. http: //www. arxiv. org/abs/cs. IT/0410002, 2004.
• [34] P. D. Grunwald and P. M. B. Vitanyi. Kolmogorov coinplexity and information theory (with an interpretation in terms of questions and answers). Journal of Logic, Language, and Information, 12: 497-529, 2003.
• [35] L. Györfi, I. Pali, and E. C. van der Meulen. There is no universal source code for infinite alphabet. IEEE Transactions on Information Theory, 40:267-271, 1994.
• [36] W. Hilberg. Der bekannte Grenzwert der redundanzfreien Information in Texten — eine Fehlinterpretation der Shannonschen Experimente? Prequenz, 44:243-248, 1990.
• [37] J. R. M. Hosking. Practional differencing. Biometrika, 68:165-176, 1981.
• [38] O. Kallenberg, Foundations of Modern Probability. New York, Springer, 1997.
• [39] J. C. Kieffer and E. Yang. Grammar-based codes: A new class of universal lossless source codes. IEEE Transactions on Information Theory, 46:737-754, 2000.
• [40] M. Li, X. Chen, X. Li, B. Ma, and P. M. B. Vitanyi. The similarity metric. IEEE Transactions on Information Theory, 50:3250-3264, 2004.
• [41] M. Li and P. M. B. Vitanyi. An Introduction to Kolmogoroy Complexity and Its Applications, 2nd ed. New York: Springer, 1997.
• [42] A. Milosavljevič. Discovering dependencies via algorithmic mutual information: A case study in DNA sequence comparisons. Machine Learning, 21:35-50, 1995.
• [43] F. L. Ramsey. Characterization of the partial autocorrelation function. The Annals of Statistics, 2:1296-1301, 1974.
• [44] W. Rytter. Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theoretical Computer Sci­ence, 302:211-222, 2003.
• [45] T. Seidenfeld, M. J. Schervish, and J. B. Kadane. Improper regular conditional distributions. The Annals of Probability, 29:1612-1624, 2001.
• [46] C. Shannon. Prediction and entropy of printed English. Bell System Technical Journal, 30:50-64, 1950.
• [47] P. C. Shields. The Ergodic Theory of Discrete Time Series. Providence: American Mathematical Society, 1996.
• [48] J. M. Swart. A conditional product measure theorem. Statistics & Probability Letters, 28:131-135, 1996.
• [49] H. van Halteren, R. H. Baayen, F. Tweedie, M. Haverkort, and A. Neijt. New machine learning methods demonstrate the existence of a human stylome. Journal of Quantitative Linguistics, 12:65-77, 2005.
• [50] T. Weissman. Not all universal source codes are pointwise universal. http://www.stanford.edu/~tsachy/interest.htm,2004.
• [51] R. W. Yeung. First Course in Information Theory. Dordrecht: Kluwer Academic Publishers, 2002.
• [52] J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23:337-343, 1977.
• [53] J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24:530-536, 1978.