compressibility and generalization

[Juergen Schmidhuber]

Eric Baum wrote:

>>>
(1) While it may be that in classical Lattice gas models, a gas does
not have high Kolmogorov complexity, this is not the origin of
the predictability exploited by physicists. Statistical mechanics
follows simply from the assumption that the gas is in a random one
of the accessible states, i.e. the states with a given amount of
energy. So *define* a *theoretical* gas as follows: Every time you
observe it,it is in a random accessible state. Then its
Kolmogorov complexity is huge (there are many accessible states)
but its macroscopic behavior is predictable. (Actually
this an excellent description of a real gas, given quantum mechanics.)
<<<

(1) The key expression here is ``the assumption that the gas is
in a random one of the *accessible* states''.  Since the accessible
states are defined to be those with equal energy, this greatly
restricts the number of possible states. By definition, it is
trivial to make a macro-level prediction like ``the total energy
will remain constant''.  In turn, there are relatively short
descriptions of a given history of such a gas.  With true random
gas, however, there are no invariants eliminating most of the
possible states. This makes its history incompressible.

(2) Back to: what does this have to do with machine learning? As a
first step, we may simply apply Solomonoff's theory of inductive
inference to a dynamic system or ``universe''. Loosely speaking,
in a universe whose history is compressible, we may expect to
generalize well.  A simple, old counting argument shows: most
computable universes are incompressible. Therefore, in most
computable universes you won't generalize well (this is related
to what has been (re)discovered in NFL).

(3) Hence, the best we may hope for is a learning technique with
good expected generalization performance in *arbitrary* compressible
universes. Actually, another restriction is necessary: the time
required for compression and decompression should be ``tolerable''.
To formalize the expression ``tolerable'' is subject of ongoing
research.

Juergen Schmidhuber
IDSIA
juergen at idsia.ch