HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS		QUICK SEARCH:   [advanced] Author: Keyword(s): Year:  Vol:  Page:

This Article Full Text Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Similar articles in this journal Similar articles in PubMed Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Bialek, W. Articles by Tishby, N. Search for Related Content PubMed PubMed Citation Articles by Bialek, W. Articles by Tishby, N.

Predictability, Complexity, and Learning

NEC Research Institute, Princeton, NJ 08540, U.S.A.

Ilya Nemenman

NEC Research Institute, Princeton, New Jersey 08540, U.S.A., and Department of Physics, Princeton University, Princeton, NJ 08544, U.S.A.

Naftali Tishby

NEC Research Institute, Princeton, NJ 08540, U.S.A., and School of Computer Science and Engineering and Center for Neural Computation, Hebrew University, Jerusalem 91904, Israel

We define predictive information I_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_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_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 the analysis of physical systems through statistical mechanics and dynamical systems theory. Furthermore, 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_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 problems in physics, statistics, and biology.

This article has been cited by other articles:

				F. Creutzig and H. Sprekeler Predictive Coding and the Slowness Principle: An Information-Theoretic Approach Neural Comput., April 1, 2007; 20(4): 1026 - 1041. [Abstract] [Full Text] [PDF]

				M. B. Kennel, J. Shlens, H. D. I. Abarbanel, and E. J. Chichilnisky Estimating Entropy Rates with Bayesian Confidence Intervals Neural Comput., July 1, 2005; 17(7): 1531 - 1576. [Abstract] [Full Text] [PDF]

				E. E. Thomson and W. B. Kristan Quantifying Stimulus Discriminability: A Comparison of Information Theory and Ideal Observer Analysis Neural Comput., April 1, 2005; 17(4): 741 - 778. [Abstract] [Full Text] [PDF]