demers@beowulf.ucsd.edu (David E Demers) (10/29/89)
I recently promised to provide some follow up references on Kolmogorov Complexity, following a thread discussing how one might measure "complexity" of a model, such as a neural net. For Kolmogorov Complexity in general, the best place to start would be with an introduction to the notions of Kolmogorov Complexity and its application to a number of different problems which can be found in: Li, M. and Paul Vitanyi, Kolmogorov Complexity and Its Applications, in Handbook of Theoretical Computer Science, (J. van Leeuwen, Ed.) North-Holland, 1989. A preliminary version of the same work is in the Proceedings of the 3d IEEE Structure in Complexity Theory Conference, 1988. The same authors have a book out by Addison-Wesley, An Introduction to Kolmogorov Complexity and its Applications (1989). For original work, see the references in the bibliography of the above book. Let me point out the following which are probably most important: Kolmogorov, AN, "Three approaches to the quantitative definition of information" Problems in Information Transmission 1, 1-7, 1965; Shannon & Weaver, The Mathematical Theory of Communication, U. of Illinois Press, 1949 (for basics of information theory) Kolmogorov, A.N. "Logical Basis for information theory and probability theory", IEEE Trans. on Info. Theory ?? 1968 (sorry) Solomonoff, R.J., "A formal theory of inductive inference", Information & Control 30, 1-22 and 224-254 (1964). Chaitin, G.J., "Randomness and Mathematical Proof" Scientific American, 232 (May 1975), pp47-52 Chaitin, G.J., "Algorithmic Information Theory", IBM J. Res. Dev. 21, 350-359 (1977) Chaitin, G.J., Information, Randomness and Incompleteness. (World Scientific Pub, 1987) other surveys are: Zvonkin, A.K. and L.A. Levin, "The complexity of finite objects and the development of the concepts of information and randomness by the means of the Theory of Algorithms", Russ. Math. Survey 25, 83-124 (1970) Schnorr, C.P., "A survey of the theory of random sequences", in Basic Problems in Methodology and Linguistics (Butts, R.E. Ed.) 1977, pp. 193-210. Application of Kolmogorov Complexity, or similar ideas, can be seen in work of Valiant, Gold, Rissanen & others (maximum likelihood, maximum entropy...). I might mention Rissanen, J., "Modeling by the shortest data description", Automatica 14, 465-471 (1978) for a practical suggestion for statistical modeling - minimum description length - which has two components, one essentially computing the size of the model and the other computing the size of the data when encoded using the theory. APPLICATIONS: Can state and prove Goedel's incompleteness theorem using Kolmogorov Complexity, Can derive a prime-number theorem, # primes less than n is on the order of n/ (log n (log log n)^2) , can state and prove the pumping lemma for regular languages in a couple of lines, and so on... In the neural net world, Tenorio & Lee used a variant of Rissanen's minimum description length along with a stochastic growth method for determining when to add new nodes to a network (TR-EE 89-30, June 1989, Purdue University School of Electrical Engineering) Hope this is of interest! Dave DeMers Dept. of Computer Science & Engineering C-014 and Institute of Non-Linear Science UCSD La Jolla, CA 92093 demers@cs.ucsd.edu demers@inls1.ucsd.edu
lloyd@bruce.OZ (lloyd allison) (10/30/89)
try also J. Rissanen Stochastic Complexity and C. S. Wallace and P. R. Freeman Estimation and inference by compact coding Journal of the Royal Statistical Society (series B) V 39 No3 1987 pages 223-239 and 252-265 (Rissanen) and 240-265 Wallace and Freeman also C. S. Wallace and D. M. Boulton An information Measure for Classification Computer Journal 11(2) 185-194 1968 zzzzz