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,
generalization, universal search, self-sizing programs,
Size: 23 pages
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