Fundamental Compressionist Philosophy.

[Brendan Macmillan]

> > 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.

> OK, it is possible to call these things 'prior knowledge' and if the term is
> used in that way, you are right.

> 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.


Cheers,
Brendan


> It seems to me that AI is full of examples where huge search spaces
> (including infinite search spaces) are tamed by using heuristic techniques
> and the like.
A linear search space is also infinite - that it be exponential aspect is
important too.

That you describe them as specific "examples" is interesting, as it suggests
that they are indeed particular domains, which have been discovered to be
hilly, or a view of them has been discovered that reveals a hilliness - or
other amenability to efficient search.  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.

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 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 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.


> With the kind of pattern matching that my SP61 model is doing,
Sorry, I'm not familiar with your SP62 model - is it as powerful as the
theoretical inference engine that Detlef mentioned, to which I responded?
It sought completely general patterns (from my understanding) - and it is
not the infiniteness of the search space that is the problem, but its
exponentiality and generality.

It sounds like you have done extremely well in discovering how to search the
particular space of this "kind of pattern matching" - something for which I
would credit yourself, and not your program.   ;-)

And I said I wouldn't get drawn into this, or incite debate!  Silly me ;-)


Cheers,
Brendan
-- 
e:  bren at csse.monash.edu.au                         v:  +61 (3)  9905 1502
Email is checked daily                              Phone is rarely attended