Abstract of FKI-194-94

Document-Name:  not ftp-available (in preparation)
Title:		Discovering Problem Solutions with Low Kolmogorov Complexity
                and High Generalization Capability
Authors:	Juergen Schmidhuber 
Revision-Date:  August 1, 1994
Category:	Technical Report (Forschungsberichte Künstliche Intelligenz)
Abstract:	Many machine learning algorithms aim at finding ``simple'' 
                rules to explain training data. The expectation is: the 
                ``simpler'' the rules, the better the generalization on test 
                data (--> Occam's razor). Most practical implementations, 
                however, use measures for ``simplicity'' that lack the power,
                universality and elegance of those based on Kolmogorov 
                complexity and Solomonoff's algorithmic probability.
                Likewise, most previous approaches (especially those of the 
                ``Bayesian'' kind) suffer from the problem of choosing 
                appropriate priors. This paper addresses both issues.
                It first reviews some basic concepts of algorithmic
                complexity theory relevant to machine learning, and
                how the Solomonoff-Levin distribution (or universal
                prior) deals with the prior problem.  The universal prior 
                leads to a method for finding ``algorithmically
                simple'' problem solutions with high generalization capability.
                The method is based on Levin complexity (a time-bounded 
                generalization of Kolmogorov complexity) and Levin's  optimal
                universal search algorithm. A probabilistic variant of
                universal search, designed for conventional digital machines,
                is introduced. With a given problem, solution candidates are 
                computed by efficient ``self-sizing'' programs that influence 
                their own runtime and storage size. Universal search finds 
                the ``good'' programs (the ones computing algorithmically 
                probable solutions fitting the training data). Simulations 
                focus on the task of discovering ``algorithmically simple'' 
                neural networks with high generalization capability.
                It is demonstrated that the method, at least in certain
                simple cases where it is computationally feasible, can lead to
                generalization results unmatchable by previous neural net 
                algorithms. The final part of the paper concerns extensions of
                universal search designed for incremental learning.
Keywords:	Generalized Kolmogorov complexity, 
                Solomonoff-Levin distribution,
                generalization, universal search, self-sizing programs,
                neural networks.
Size:		23 pages
Language:	English
ISSN:		0941-6358
Copyright:	The ``Forschungsberichte Künstliche Intelligenz''
		series includes primarily preliminary publications,
		specialized partial results, and supplementary
		material. In the interest of a subsequent final
		publication these reports should not be copied. All
		rights and the responsability for the contents of the
		report are with the authors, who would appreciate
		critical comments.

Gerhard Weiss