Re: [Please Help] Pattern Matching Comparison

[rbrown@xxxxxxxxxxxxxxx]

Hello, Computer-go enthusiasts!

In the last exciting episode, Mousheng Xu wrote:

> If you use 0 for empty, 1 for black, 2 for white, 3 for
> jie, then you can use 2 bits to represent one poisiton on the board.
  ^^^

I must ask; what is jie?  I don't recall ever having seen or having heard this
word.  I'm sorry that I am unfamiliar with the Chinese terms for go concepts.

Darren Cook responded with:

> A few thoughts about how humans use patterns (and IMHO how computers should
> use them):

[Four points with which I strongly agree -- for the most part -- and as many
footnotes.  Although I've snipped most of Darren's message for brevity's sake,
everyone is encouraged to re-read it; it provides context for my own comments.]

                                        -o-

One of the really difficult questions to answer if you want to use patterns
is this:  Just exactly what sort of patterns do you want to store, compare,
recognize, and manipulate?

Another difficult question (perhaps just a rephrasing of the above):  What makes
one pattern, or more precisely one pattern _classifier_ "better" than another?

It turns out that there are rigorous ways to unambiguously answer this question,
but they require pattern databases with at least some data in them.  Then we
can make measurements of the data, to so determine which classifier is "better".

We may have to live with a "bad" or imperfect choice of pattern classifier until
it becomes clear which of our classifiers is better.  Fortunately, this clarity
can usually be achieved even with "small" pattern databases.  That is, it is
possible to decide that one type of pattern classifier is better than another,
based on certain measurments of our data, even if we use only a small sampling
of each type.  There are ways of measuring data that yield this sort of answer.

> 3.The pattern accross time (a.k.a. moves sequences; joseki) is almost as
> important as the spatial pattern [1]. [2]

Here I must disagree.  Patterns of _behavior_ in go are far _more_ important,
not "almost" as important to the programmer than the spatial patterns are.
Although the states of the board are most certainly a necessary _context_, they
are not sufficient to tell us what we want to know:  Where do I play next?

In a way, the spatial or visual patterns we see on the board are not really
important at all.  What we are _really_ interested in is recognizing patterns
of _behavior_ so that we can correctly predict (or "guess") where a strong
player would play in a given situation.  The spatial patterns merely provide
a context within which our prediction occurs.

> [1]: Ooh! Clever word :-).
> 
> [2]: Just being pretentious. I'm not entirely sure what I mean by this.

With regard to footnote [1], yes, "spatial" is clever, and I like it.  Space
is what go is all about.  As for footnote [2], your point 3 above seems more
insightful than it does pretentious, though I quibbled about the _degree_ of
importance.  Maybe you don't know what you mean, but I do.  :-)

One very interesting thing about constructing a pattern classifier -- and this
is true whether the patterns we want to classify are medical histories, weather
patterns, fingerprints, or patterns of go behavior -- is that we may be able to
live with an imperfect classifier, and still get good results.

For example, consider a medical diagnostic test which uses patient data (blood
sugar level, white cell count, body temperature and so on) to classify a patient
as either having a certain disease or not.  Let's say that this test errs
occasionally, and suggests that some patient has the disease even though he
really doesn't.  On the other hand, it rarely, if ever, fails to identify
someone who does in fact have the disease.  Now just because there are a few
"false positives" from this test, we don't throw the test out as useless.

And even if there are "false negatives", that is, we fail to correctly diagnose
the disease in say, 1% of cases, the test will still be useful for 99% of the
people who have the disease, permitting them to seek treatment as a result of
the diagnosis.  So it is a "good" classifier, even though it makes mistakes.

So, although our pattern classifier may be flawed, if we can reduce the _rate_
of failure to a minimum (by choosing some particular classifier over another) we
know that we are at least headed in the right direction.

I'd like to take this opportunity to recommend a few books that have helped me
understand the nature of certain problems faced by us go programmers, as well as
by those who would like to represent and recognize other types of patterns, say,
pictures, or voices, or fingerprints, or the genetic information contained in
a sample of DNA.

Syntactic Pattern Recognition : An Introduction
Rafael C. Gonzalez and Michael G. Thomason

This is out of print, possibly because more recent advances in the field of
syntactic and structural pattern recognition have rendered some of it obsolete,
or at least dated it a bit.  But it was a real eye-opener for me, and I have a
soft spot in my heart for it.  Interested readers might be able to find it in a 
library.  Gonzalez also co-authored a book on classical decision-theoretic
pattern recognition:

Pattern Recognition Principles
J. T. Tau and R. C. Gonzalez

Both of these books were published by Addison-Wesley, I think, but they are at
my house, and I am not, so I can't verify that right now.  Amazon finds the
former, but does not list details, only "out-of-print"; it doesn't find the
latter at all.

Knuth's _The_Art_of_Programming_ used to be my favorite technical book, but the
following has won out over that old war-horse as my new Bible:

A Probabilistic Theory of Pattern Recognition 
Luc Devroye, Laszlo Gyorfi, and Gabor Lugosi
Springer Verlag; ISBN: 0387946187

The table of contents alone is worth reading.  It's at Devroye's web site:

http://www-cgrl.cs.mcgill.ca/~luc/pattrec.html

I say Bible because it has given me faith and inspiration, and instilled
a hope in me that says that the program I've been struggling to cobble
together with spit and baling wire lo! these many years, may actually have
a sound theoretical basis.  That is to say, what I thought was merely a
haphazard intuitive approach, may turn out, at the end of the day, to be
justified and vindicated by recent results in the general theory.  I do hope.

Oh!  I've said too much.  Next thing you know, somebody with a lot of money
will hire experts from the field of "syntactic pattern recognition" to write
a go program, and the race will be on, between them and me.  Oh, dearie me!

But, considering the inherent difficulty of our problem, I trust I am not
giving away the store when I say that I am encouraged by using these techniques
as a means of getting a computer to play go.  The competition -- you -- still
have to come up with a way of representing the patterns you want to recognize
and classify.  And that's the hard part.  What to observe?  How to observe it?

After that, it's an easy matter to apply cookbook algorithms.  Have fun!


Rich

-- 
Richard L. Brown              Office of Information Services
rbrown@xxxxxxxxxxxxxxxxx        University of Wisconsin System Administration
rlbrown6@xxxxxxxxxxxxxxxxx    780 Regent St., Rm. 246  /  Madison, WI  53715