Response to no-free-lunch discussion

[Eric B. Baum]

Barak Pearlmutter remarked that saying
	We have *no* a priori reason to believe that targets with "low
	Kolmogorov complexity" (or anything else) are/not likely to
	occur in the real world.
(which I gather was a quote from David Wolpert?)
is akin to saying we have no a priori reason to believe there is non-random
structure in the world, which is not true, since we make great
predictions about the world.

Wolpert replied:
> To illustrate just one of the possible objections to measuring
> randomness with Kolmogorov complexity: Would you say that a
> macroscopic gas with a specified temperature is "random"? To describe
> it exactly takes a huge Kolmogorov complexity. And certainly in many
> regards its position in phase space is "nothing but noise". (Indeed,
> in a formal sense, its position is a random sample of the Boltzmann
> distribution.) Yet Physicists can (and do) make extraordinarilly
> accurate predictions about such creatures with ease.

Somebody else (Jurgen Schmidhuber I think?)
argued that a gas does *not* have high Kolmogorov complexity, because
its time evolution is predictable. So in a lattice gas model, given
initial conditions (which are relatively compact, including compact
pseudorandom number generator) one may be able to
predict evolution of gas.

Two comments:
(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.)

(2) Point 1 is no solace to those arguing for the relevance of
Wolpert's theorem, as I understand it. We observe above that
non-randomness arises purely out of  statistical ensemble effects.
This is non-randomness none-the-less. Consider the problem of learning
to predict the pressure of a gas from its temperature. Wolpert's theorem,
and his faith in our lack of prior about the world, predict,
that any learning algorithm whatever is as likely
to be good as any other. This is not correct.

Interestingly, Wolpert and Macready's results appear irrelevant/wrong here
in an entirely *random*, *play* world. We see that learnable structure
arises at a macroscopic level, and that our natural instincts
about learning (e.g. linear relationships, cross-validation as
opposed to anti-cross validation) hold. We don't need to appeal to
experience with physical nature in this play world. We could prove
theorems about the origin of structure. (This may even be a fruitful
thing to do.)

Creatures evolving in this "play world" would exploit this structure and
understand their world in terms of it. There are other things they would
find hard to predict. In fact, it may be mathematically valid to say that
one could mathematically construct equally many functions on which
these creatures would fail to make good predictions. But so what?
So would their competition. This is not relevant to looking for
one's key, which is best done under the lamppost, where one has a
hope of finding it. In fact, it doesn't seem that the play world
creatures would care about all these other functions at all.

What was the Einstein quote wondering about the surprising
utility of mathematics in understanding the natural world?
Maybe mathematics itself provides an answer?

-- 
-------------------------------------
Eric Baum
NEC Research Institute, 4 Independence Way, Princeton NJ 08540
PHONE:(609) 951-2712, FAX:(609) 951-2482, Inet:eric at research.nj.nec.com
http://www.neci.nj.nec.com:80/homepages/eric/eric.html