Coding and Complexity

Inspired by the algorithmic notion of complexity, Solomonoff (1964), Kolmogorov (1965), Chaitin (1966), as well as Akaike’s work, Akaike (1977), I some ten years ago proposed the shortest code length for the observed data as a criterion for model selection, Rissanen (1978), which in the subsequent papers, Rissanen (1983), (1984), (1986a), (1987), gradually evolved into stochastic complexity. The word “stochastic” was meant to suggest that the models, relative to which the coding ought to be done, were probabilistic rather than being defined by programs in a universal computer as in the algorithmic theory. Having presented the material to numerous audiences I frequently was asked the question to the effect that “why should we be interested in the code length as a measure of model’s performance if the models are not used for coding purposes”. Although this measure in itself has a strong intuitive appeal and its success can be supported both by applications and theoretical analysis, a deeper answer would clearly be desirable. It turns out that a search for such an answer, which is the main topic in this talk, will force us to look at the fundamental process of learning by statistical inference. This, incidentally, is quite different from the customary statistical thinking, in which one makes an arbitrary assumption about the data, namely, that they form a sample from some unknown distribution. This, then, will be estimated and the work is done. To quench any lingering doubts the estimation procedure may further be supported by an analysis of its optimality in the light of the assumed distribution. But because in current statistics there is no rational means to compare two distinct models, a critical step required for learning is lacking, and nothing beyond the initial guess is learned from the data.