Fundamental Compressionist Philosophy.

[Gerry Wolff]

----- Original Message -----
From: "Brendan Macmillan" <bren at mail.csse.monash.edu.au>
To: <gerry at informatics.bangor.ac.uk>
Cc: "Maillist CasC" <casc at sanna.com>
Sent: 29 May 2001 06:24
Subject: Re: Fundamental Compressionist Philosophy.
...


> > Other people may disagree but I would guess that 'prior knowledge' is
> > normally taken to mean specific knowledge about the domain and would
exclude
> > relatively general ideas related to methods of searching.
> I didn't mean it in the trivial sense of methods of searching, but that
> something needs to be known about the *way* that a particular search space
> is hilly.  Perhaps a better way of expressing this is to say that many
> search spaces are not hilly - that is, there is no relationship between
the
> goodness of points adjacent to each other.
>
> Of course, through much work and ceaseless exploration we have discovered
> some domains that are hilly.  For other domains, no hilliness has been
> apparent, until we have discovered a particular way to present it that
> exposes a hilliness (that may or may not have been obvious to us at
first).
>
> This discovery, of the way to present it usefully to a hill climbing
> algorithm, is the "proir knowledge" is the difficult bit.
>

I agree that prior knowledge can be useful but I am still not convinced that
it is necessary for problem solving. If you start searching and it turns out
that the domain is flat (no hills), you may have to settle for failure. But
there is nothing to prevent you starting to search and, if you achieve some
partial success, you may feel it worth continuing the search.

Flat areas in a search space are a bit like local peaks: both of them can
make it difficult to find an acceptably good solution to a problem. The
standard method of dealing with both situations is to widen the search. In
the case of local peaks, it is necessary to be prepared to go down hill. In
the case of flat areas in the search space it is necessary to search a wider
area.  In both cases, one may decide to try to escape from the difficulty by
jumping to some new part of the search space. Another way round these
problems is parallel searching: a bit like sending a team of rescuers up a
mountain to find an injured climber - each member of the team searches a
different part of the mountain.

...

> And, of course, once we look into a
> particular domain, we start to learn things, which we interpret through
our
> prior knowledge of the world.  It is this step where all the clever stuff
> happens.

The crucial point is that the process of searching gives us knowledge. It is
true, that prior knowledge may be helpful but I am not convinced that it is
necessary.

>
> Do you know the story of Hans, the mathematical horse?  He could be asked
> any mathematical question, and when given a choice of answer, would tap
his
> foot when the right one was spoken.  He caused a sensation.  But closer
> study revealed some odd facts - if his owner didn't know the answer,
neither
> did Hans.  And if his owner did the calculation wrong, Hans did too.  And
it
> only worked when the owner was with Hans.  It was finally realized that
Hans
> the horse was very sensitive to changes in his owner's demeanor, who
relaxed
> slightly and unconsciously when the right answer was given.
>
> By only presenting problems (or views of them) that are hilly (or
otherwise
> amenable to search), there is a similar effect for AI programs.  If the
> author was not there, feeding in the right type of problem, it couldn't do
it.
> Of course, it is happening at a higher and much more sophisticated level
than
> Hans the horse.
>

The process of biological evolution can be viewed as a search process where
reproductive success is the measure of 'up'. In Richard Dawkin's words, it
is a "Blind Watchmaker": there is no prior knowledge and no author feeding
the system with the right kinds of problems.

>
> > The key idea seems to be that, by deciding not to look everywhere, it is
> > possible to save huge amounts of searching.
> And what is the basis of deciding where not to look?

The measure of 'up' that you have chosen, conditioned by the problem you are
trying to solve.

>
> > The penalty is that you cannot guarantee to find the best possible
answer.
> > But by using heuristic techniques (hill climbing) etc, it is normally
> > possible to find answers that are acceptably good.
> This tradeoff is certainly true.  However, my conjecture is that - in
> general - even the "acceptably good" are so terribly sparse, in an
> inconceiveably vast space, that we can't even find the acceptably good -
unless
> we are only working with particular spaces that have previously been
discovered
> to be hilly or amenable to search in some other way.

As I say, if it turns out that you are in a very large flat domain, you may
have to accept failure. The process of searching quickly reveals whether the
domain is flat or not.

Regards,

Gerry