Fundamental Compressionist Philosophy.

[Brendan Macmillan]

Hi Gerry,


> > Thus, even though it is a perfectly wonderful idea, exponential search
> > space *absolutely* kills it in practice.  The only way around this is to
> > narrow the search space, and this requires prior knowledge.

> I agree that it is necessary to narrow the search space but I am not sure
> about this requiring prior knowledge.

> With pattern matching (which is a problem area with similar properties), one
> can narrow the search space by only accepting 'full' matches between
> patterns. This is how most 'conventional' computer programs work: if you
> type one character wrongly, the whole thing fails.
Probabilistic matches are certainly the way to go - however I don't an 
argument here for narrowing the search space (let alone doing so without
prior knowledge).

> The other main way to narrow the search space is to use heuristic techniques
> like hill climbing, similated annealing, genetic programming etc. Here, the
> search space is searched in stages and, at each stage, the system narrows
> the focus to areas which are looking promising (from information gleaned in
> previous stages of the search).
Knowing what "looks promising" requires prior knowledge.   And the decision
to use hill climbing requires a hunch that the search space is indeed hilly.
Usually, we can present data in a format that reveals its hilliness - but
then we ourselves have gone and done the difficult bit.

But yes, of course you are right - in principle.  In practice, it is
exponential all over again.  This means it takes forever.  It was very
difficult for me to grasp the absolute truth of this, until I had banged my
head on it for several months, and accumulated much empirical evidence.  I
encourage everyone to actually try some of these ideas out - in a tightly
constrained and limited form - to validate my claim.  I'd been forwarned (for
example, the guys trying to infer all mathematics from axioms - great at first,
then *kaBAMN* exponential explosion).

The absolutely fantastic corrollary for this (for me), is that when in a
*truly* new space (that is, without much prior knowledge), we humans are not
so good.  This means that truly great insights can be right in front of us,
but which we haven't noticed yet.  So it is *always* worth looking long and
hard, no matter how impossible something seems (this goes for all spheres of
life).  It does indeed seem to work.

> This is a bit like a geologist prospecting for minerals or a detective
> hunting for a criminal.
The crucial difference is the size of the search space.  (assuming there is
a criminal) when looking for him/herr criminals, it must be one out of 
10 billion.  And I'm afraid that that is practically infinitely small 
compared with the search space.

We do not realize just how much prior knowledge we utilize - we take it for
granted, of course, as we must.  It is indeed very very scary to meditate on
how little we really know about many "facts" that we take for granted.


> Both these ways of narrowing the search space can be quite effective but it
> is not obvious to me that they really involve prior knowledge. By the latter
> I assume you mean prior knowledge of the form that the solution is likely to
> take.
I didn't grasp your first argument, and your second does involve some knowledge
of the search space (hilliness, for example).  But the bottom line is to ask:
does it really make the problem more tractible, in a practical sense?

> How does this sound?
It sounds very, very sensible - pretty much what I thought before I tried it.;-)


Cheers,
Brendan
PS: I should add that I was immensely disappointed when I finally saw the
truth.  But the corrollary - being so human-affirming - was definitely worth
it, as truth always is.
-- 
e:  bren at csse.monash.edu.au                         v:  +61 (3)  9905 1502
Email is checked daily                              Phone is rarely attended