Bialek et al., 2001a

Back to the full Publications list.

W Bialek, I Nemenman, and N Tishby. Complexity through nonextensivity. Physica A, 302:89-99, 2001. PDF, arXiv.

Abstract

The problem of defining and studying complexity of a time series has interested people for years. In the context of dynamical systems, Grassberger has suggested that a slow approach of the entropy to its extensive asymptotic limit is a sign of complexity. We investigate this idea further by information theoretic and statistical mechanics techniques and show that these arguments can be made precise, and that they generalize many previous approaches to complexity, in particular, unifyingideas from the physics literature with ideas from learningand codingtheory; there are even connections of this statistical approach to algorithmic or Kolmogorov complexity. Moreover, a set of simple axioms similar to those used by Shannon in his development of information theory allows us to prove that the divergent part of the subextensive component of the entropy is a unique complexity measure. We classify time series by their complexities and demonstrate that beyond the ``logarithmic complexity classes widely anticipated in the literature there are qualitatively more complex, ``power-law classes which deserve more attention.

Comments

This is a shortened version of Bialek et al., 2001b. Compared to Bialek et al., 2001b, this paper also advances our understanding of connections to Kolmogorov complexity.