Is the universe finite?

[hicks@cs.titech.ac.jp]

I would like to make 2 points.
One concerns a clarification of David Wolperts definition of the universe.
The second one is a thought problem meant to be an illustration 
of the inevitability of structure.

Point 1: 
David Wolpert writes:
(1) >Practically speaking of course, none of this is a concern in the real
>world. We are all (me included) quite willing to conclude there is
>structure in the real world.  But as was noted above, what we do in
>practice is not the issue. The issue is one of theory.

(2) >Okay. Now take all those problems together and view them as one huge
>training set. Better still, add in all the problems that Eric's
>anscestors addressed, so that the success of his DNA is also taken
>into account. That's still one training set. It's a huge one, but it's
>tiny in comparison to the full spaces it lives in.

The above statements seem  to me to be contradictory in some meaning.
"(1)" is saying we should, when discussing generalization, 
not concern ourselves with the real universe in which we live,
but should consider theoretical alternative universes as well.

On the other hand "(2)" seems to say that the real universe in which we live
is itself sufficiently "diverse" that any single approach to generalization
must on average be the same.

What is the universe about which we are talking?  Since mathematical models
exist in our minds and on paper in this universe, are they included?

I feel we ought to distinguish between a single universe (ours for example),
and the ensemble of possible universes.

Point 2:

Lets suppose a universe which is an N-dimensional binary (0/1) vector 
random variable X,
whose elements are iid with p(0)=p(1)=(1/2).  Apparently there is no structure
in this universe.

Now let us consider a universe which is a 
binary valued N by M matrix random variable AA
whose elements are also iid with p(0)=p(1)=(1/2).  
Let us draw a random instance A from AA.

Now we define an M-dimensional integer random variable Y
depending on X by p(y=Ax) = p(Ax), where x and y are instances of 
X and Y respectively.

If A happens to be chosen such that y is merely a subset of the elements
of x, then the prior p(y), like the prior p(x), will be uniform.
But for most choices of A, p(y) will not be uniform at all.

So, out of all the possible universes Y, most of them have structure.
This happens even though Y and AA have no structure.
The structure that Y will have is drawn from a uniform distribution 
(over AA), but we are only concerned with whether there will be structure
or not.

Of course, this proves nothing.  And now I am going to make a 
giant leap of analogy.

The following statements are not contradictory.

(a) In a universe drawn at random from 
the ensemble of all possible universes, we cannot expect to 
see any particular structure to be more likely that any other structure.

(b) In any given universe, we can expect structure to be present.

Would I be correct in saying that only (b) needs to be true in order
for cross-validation to be profitable?




Craig Hicks

Craig Hicks           hicks at cs.titech.ac.jp | Hisakata no, hikari nodokeki
Ogawa Laboratory, Dept. of Computer Science | Haru no hi ni, Shizu kokoro naku
Tokyo Institute of Technology, Tokyo, Japan | Hana no chiruran 
lab:03-5734-2187 home:03-3785-1974 | Spring smiles with sun beams 
fax (from abroad):		   | sifting down through cloudy dreams 
  +81(3)5734-2905 OGAWA LAB  	   | towards the anxious hearts
03-5734-2905 OGAWA LAB (from Japan)| beating pitter pat
[ Poem from Hyaku-nin i-syuu ->    | while flower petals scatter.