- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Editors' Suggestion
  • Rapid Communication
  • Access by Xinjiang University

Signatures of infinity: Nonergodicity and resource scaling in prediction, complexity, and learning

James P. Crutchfield1,* and Sarah Marzen2,†

  • 1Complexity Sciences Center and Department of Physics, University of California at Davis, One Shields Avenue, Davis, California 95616, USA
  • 2Redwood Center for Theoretical Neuroscience and Department of Physics, University of California at Berkeley, Berkeley, California 94720-5800, USA

  • *chaos@ucdavis.edu
  • †smarzen@berkeley.edu
PDF

Phys. Rev. E 91, 050106(R) – Published 27 May, 2015

DOI: https://doi.org/10.1103/PhysRevE.91.050106

Abstract

We introduce a simple analysis of the structural complexity of infinite-memory processes built from random samples of stationary, ergodic finite-memory component processes. Such processes are familiar from the well known multiarm Bandit problem. We contrast our analysis with computation-theoretic and statistical inference approaches to understanding their complexity. The result is an alternative view of the relationship between predictability, complexity, and learning that highlights the distinct ways in which informational and correlational divergences arise in complex ergodic and nonergodic processes. We draw out consequences for the resource divergences that delineate the structural hierarchy of ergodic processes and for processes that are themselves hierarchical.

View figure in article

Article Text

References (53)

  1. J. P. Crutchfield and D. P. Feldman, Regularities unseen, randomness observed: Levels of entropy convergence, Chaos 13, 25 (2003).
  2. J. P. Crutchfield and K. Young, Computation at the onset of chaos, in Entropy, Complexity, and the Physics of Information, edited by W. Zurek, SFI Studies in the Sciences of Complexity Vol. III (Addison-Wesley, Reading, MA, 1990), pp. 223–269.
  3. W. Bialek, I. Nemenman, and N. Tishby, Predictability, complexity, and learning, Neural Comput. 13, 2409 (2001).
  4. N. Travers and J. P. Crutchfield, Infinite excess entropy processes with countable-state generators, Entropy 16, 1396 (2014).
  5. L. Debowski, On hidden Markov processes with infinite excess entropy, J. Theor. Probab. 27, 539 (2012).
  6. D. L. Turcotte, Fractals and Chaos in Geology and Geophysics, 2nd ed. (Cambridge University Press, Cambridge, UK, 1997).
  7. J. M. Beggs and D. Plenz, Neuronal avalanches in neocortixal circuits, J. Neurosci. 23, 11167 (2003).
  8. L. Debowski, Excess entropy in natural language: Present state and perspectives, Chaos 21, 037105 (2011).
  9. I. Dobson, B. A. Carreras, V. E. Lynch, and D. E. Newman, Complex systems analysis of series of blackouts: Cascading failure, critical points, and self-organization, Chaos 17, 026103 (2007).
  10. M. J. Kearns and U. Vazirani, An Introduction to Computational Learning Theory (MIT Press, Cambridge, MA, 1994).
  11. T. M. Cover and M. E. Hellman, The two-armed-bandit problem with time-invariant finite memory, IEEE Trans. Inf. Theory IT-16, 185 (1970).
  12. D. A. Berry, A Bernoulli two-armed bandit, Ann. Math. Stat. 43, 871 (1972).
  13. A. N. Kolmogorov, Three approaches to the concept of the amount of information, Probl. Inf. Transm. (Engl. Transl.) 1, 1 (1965).
  14. G. Chaitin, On the length of programs for computing finite binary sequences, J. ACM 13, 547 (1966).
  15. P. Martin-Lof, The definition of random sequences, Inf. Control 9, 602 (1966).
  16. A. N. Kolmogorov, Combinatorial foundations of information theory and the calculus of probabilities, Russ. Math. Surveys 38, 29 (1983).
  17. A. A. Brudno, Entropy and the complexity of the trajectories of a dynamic system, Tr. Mosk. Mat. Obs. 44, 124 (1982) [Entropy and complexity of trajectories of a dynamical system, Trans. Moscow Math. Soc. 44, 127 (1983)].
  18. M. Li and P. M. B. Vitanyi, An Introduction to Kolmogorov Complexity and its Applications (Springer-Verlag, New York, 1993).
  19. C. H. Bennett, Dissipation, information, computational complexity, and the definition of organization, in Emerging Syntheses in the Sciences, edited by D. Pines (Addison-Wesley, Redwood City, 1988), pp. 297–313.
  20. M. Koppel and H. Atlan, An almost machine-independent theory of program-length complexity, sophistication, and induction, Inf. Sci. 56, 23 (1991).
  21. J. P. Crutchfield, Between order and chaos, Nat. Phys. 8, 17 (2012).
  22. J. P. Crutchfield, P. Riechers, and C. J. Ellison, Exact complexity: Spectral decomposition of intrinsic computation, Santa Fe Institute Working Paper 13-09-028, arXiv:1309.3792.
  23. D. J. C. MacKay, Information Theory, Inference and Learning Algorithms (Cambridge University Press, Cambridge, UK, 2003).
  24. T. Hastie, R. Tibshirani, and J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed. (Spinger, New York, 2011).
  25. C. S. Wallace and F. P. Freeman, Estimation and inference by compact coding, J. Roy. Statist. Soc. B 49, 240 (1987).
  26. J. Rissanen, Stochastic Complexity in Statistical Inquiry (World Scientific, Singapore, 1989).
  27. H. Akaike, A new look at the statistical model identification, IEEE Trans. Auto. Control 19, 716 (1974).
  28. H. Akaike, An objective use of Bayesian models, Ann. Inst. Statist. Math. 29A, 9 (1977).
  29. J. J. Binney, N. J. Dowrick, A. J. Fisher, and M. E. J. Newman, The Theory of Critical Phenomena (Oxford University Press, Oxford, 1992).
  30. R. G. James, C. J. Ellison, and J. P. Crutchfield, Anatomy of a bit: Information in a time series observation, Chaos 21, 037109 (2011).
  31. A. J. Bell, The co-information lattice, in Proceedings of the Fifth International Workshop on Independent Component Analysis and Blind Signal Separation, edited by S. Makino, S. Amari, A. Cichocki, and N. Murata (Springer, New York, 2003), Vol. ICA, pp. 921–926.
  32. W. Lohr, Properties of the statistical complexity functional and partially deterministic HMMs, Entropy 11, 385 (2009).
  33. A. M. Walker, On the asymptotic behavior of posterior distributions, J. Roy. Statist. Soc. Ser. B 31, 80 (1969).
  34. C. C. Heyde and I. M. Johnstone, On asymptotic posterior normality for stochastic processes, J. Roy. Statist. Soc. Ser. B 41, 184 (1979).
  35. T. J. Sweeting, On asymptotic posterior normality in the multiparameter case, Bayesian Statistics, edited by J. O. Berger, A. P. Dawid, and A. F. M. Smith, Vol. 4 (Oxford University Press, 1992), pp. 825–835.
  36. R. C. Weng and W-C. Tsai, Asymptotic posterior normality for multiparameter problems, J. Stat. Plan. Infer. 138, 4068 (2008).
  37. J. A. Hartigan, Asymptotic normality of posterior distributions, in Bayes Theory (Springer, New York, 1983), pp. 107–118.
  38. E. L. Lehman and G. Casella, Theory of Point Estimation, 2nd. ed. (Springer, New York, 1998).
  39. W. Ebeling and G. Nicolis, Entropy of symbolic sequences: The role of correlations, Europhys. Lett. 14, 191 (1991).
  40. W. Ebeling and T. Poschel, Entropy and long-range correlations in literary English, Europhys. Lett. 26, 241 (1994).
  41. L. Wasserman, Asymptotic properties of nonparametric Bayesian procedures, in Practical Nonparametric and Semiparametric Bayesian Statistics (Springer, New York, 1998), pp. 293–304.
  42. S. Ghosal, Asymptotic normality of posterior distributions for exponential families when the number of parameters tends to infinity, J. Multivariate Anal. 74, 49 (2000).
  43. J. P. Crutchfield, The calculi of emergence: Computation, dynamics, and induction, Physica D 75, 11 (1994).
  44. S. Pressé, K. Ghosh, J. Lee, and K. A. Dill, Principles of maximum entropy and maximum caliber in statistical physics, Rev. Mod. Phys. 85, 1115 (2013).
  45. D. Lind and B. Marcus, An Introduction to Symbolic Dynamics and Coding (Cambridge University Press, New York, 1995).
  46. R. G. James, J. R. Mahoney, C. J. Ellison, and J. P. Crutchfield, Many roads to synchrony: Natural time scales and their algorithms, Phys. Rev. E 89, 042135 (2014).
  47. C. J. Ellison, J. R. Mahoney, and J. P. Crutchfield, Prediction, retrodiction, and the amount of information stored in the present, J. Stat. Phys. 136, 1005 (2009).
  48. C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27, 379 (1948); A mathematical theory of communication, 27, 623 (1948).
  49. Q. Shen, Q. Hao, and S. M. Gruner, Macromolecular phasing, Physics Today 59 (3), 46 (2006).
  50. E. van Nimwegen, J. P. Crutchfield, and M. Mitchell, Finite populations induce metastability in evolutionary search, Phys. Lett. A 229, 144 (1997).
  51. N. Chomsky, Three models for the description of language, IRE Trans. Inf. Theory 2, 113 (1956).
  52. H. W. Lau and P. Grassberger, Information theoretic aspects of the two-dimensional Ising model, Phys. Rev. E 87, 022128 (2013).
  53. D. P. Feldman, Computational Mechanics of Classical Spin Systems, PhD. thesis, University of California, Davis, 1998, published by University Microfilms Intl, Ann Arbor, Michigan.

Outline

Information

Phys. Rev. E 91, 050106(R)– Published 27 May, 2015
  • Received 1 April 2015
Article part of CHORUS

©2015 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation