Predictability, complexity and learning
  We define {\em predictive information} $I_{\rm pred} (T)$ as the mutual
information between the past and the future of a time series. Three
qualitatively different behaviors are found in the limit of large observation
times $T$: $I_{\rm pred} (T)$ can remain finite, grow logarithmically, or grow
as a fractional power law. If the time series allows us to learn a model with a
finite number of parameters, then $I_{\rm pred} (T)$ grows logarithmically with
a coefficient that counts the dimensionality of the model space. In contrast,
power--law growth is associated, for example, with the learning of infinite
parameter (or nonparametric) models such as continuous functions with
smoothness constraints. There are connections between the predictive
information and measures of complexity that have been defined both in learning
theory and in the analysis of physical systems through statistical mechanics
and dynamical systems theory. Further, in the same way that entropy provides
the unique measure of available information consistent with some simple and
plausible conditions, we argue that the divergent part of $I_{\rm pred} (T)$
provides the unique measure for the complexity of dynamics underlying a time
series. Finally, we discuss how these ideas may be useful in different problems
in physics, statistics, and biology.
