This paper addresses the question of how the complexity of a time series of events, such as a spike train, can be quantified. In an attempt to distinguish complexity from randomness, the authors determine that a reasonable measure of complexity are the divergent parts of the subextensive entropy. They identify these parts with the predictive information, i.e. the information about the future we gain from observing the past. They go on to make connections with supervised and unsupervised learning, highlighting possible measures of learning efficiency in neural systems.