Coding and Complexity

J. Rissanen
Additional contact information
J. Rissanen: IBM Almaden Research Center

A chapter in Sequences, 1990, pp 312-325 from Springer

Abstract: Abstract 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.

Keywords: Model Class; Predictive Distribution; Code Length; Minimum Description Length; Arithmetic Code (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_25

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_25

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().