EVANS JL Cunningham, February 1983
CONTENTS - (Use <ENTER> g to access sections)
-- WHAT THIS UNIT IS ABOUT
-- EVANS ANALOGY PROGRAM
-- EXERCISE 1
-- EXERCISE 2
-- DIGRESSION
-- EXERCISE 3
-- EXERCISE 4 (optional)
-- WINSTON'S ARCHES
-- EXERCISE 5
-- READING
-- WHAT THIS UNIT IS ABOUT --------------------------------------------
This unit is intended to show you several things, including:
a) The importance of how information is represented in an intelligent
system.
b) Two more examples of famous AI programs.
c) A more general notion of matching, and the importance of matching as
a mechanism for producing intelligent behaviour.
d) How generalising from particular instances can be done by a
computer.
e) Some computational models of Learning
The important concepts to be learnt are, firstly:
that the same entity, for example a "turtle" picture, can be represented
in the computer in different ways, in particular at different levels of
abstraction. For example, a turtle picture could be represented as a
database describing what lines are in the picture. Some tasks that would
be hard to do directly on a turtle picture represented as a lot of
asterisks ("*") and spaces (" ") are relatively easy with such a
database description. The task this unit looks at would be hard even at
the database-of-lines level of description, so it will be necessary to
go to an even higher level of abstraction, throwing away some of the
positional information that is irrelevant to the problem considered.
Incidentally, people don't find lists of database assertions a
particularly convenient representation, and so theorists often visualise
such a database as a graphical network of nodes and relations. E.g. we
can represent the following database:
[[fido isa dog][fido likes beer]
[felix isa cat][felix likes fish]
[felix hates fido]]
-> database;
by the following network:
likes hates isa
fish <--------- felix ----------> fido ----------> dog
| |
|isa |likes
| |
V V
cat beer
Such networks can be regarded as a convenient representation for
databases. (Some network terminology: the arrows are called "arcs" and
the things the arrows join are called "nodes". You'll need to remember
these terms to understand some of exercise 1.)
The second thing to be learnt is that analogy problems, and learning
from example sequences, requires the comparison of descriptions, i.e.
when we are representing descriptions as assertions in a database, these
problems can be looked at as requiring the comparing of networks like
the one above.
-- EVANS ANALOGY PROGRAM ----------------------------------------------
This section is a brief summary of the stuff based on Evans' Analogy
program that you should read about in the references given in the
section headed "READING".
Basically, Evans' Analogy is a program designed to do a certain class of
IQ test questions. These questions are phrased in the form:
A is to B as C is to which of D1, D2 or D3?
where A, B, C, D1, D2 and D3 are simple pictures involving a few simple
geometric shapes. Examples are given in all the references, although you
are probably familiar with the type of question.
There are several possible ways (all basically similar) of tackling this
problem on the computer, Bundy describes one way, Winston another. The
method Winston describes consists of three steps:
1) comparing the descriptions of the pictures A and B (i.e. matching
the networks representing A and B) to find the differences
2) comparing C with each of the possibilities for D, in the same way as
at step (1)
3) finding out which set of differences from step (2) is most like the
differences from step (1): the corresponding D picture is the answer.
The crucial thing to realise, at this point, is that the description of
the differences between two nets can itself be represented as a list of
database assertions (and can be viewed as a net), so step (3) just
involves matching networks as in steps (1) and (2), except that now the
networks are representing descriptions of differences between pictures.
-- EXERCISE 1 ---------------------------------------------------------
A simplified program working in the way described in the previous
section is in LIB ANALOGY. For fun, this program works from turtle
pictures, rather than from low-level descriptions of a picture; although
there is the option of using low-level picture descriptions to save some
time.
To run it, do
lib analogy
This will compile the library program, which may take some time. There
may be a saved image available that you can get running far more
quickly, by doing
on VMS - give the DCL command:
$ pop11/analogy
on UNIX - give the SHELL command:
% pop11 - analogy
If you get a message saying 'SAVED IMAGE NOT FOUND' then you have to
use the LIB ANALOGY command to load the program.
When that is done, you can make available some sample pictures, thus:
lib evpics
Then run the program by typing, to pop-11
evans();
The program will then prompt you for the name of picture A.
At this point, the program is expecting the name of a procedure to draw
a simple turtle picture. It calls this procedure to draw the picture.
However, a turtle picture is not a useable representation for
geometrical analogy problems, so the program next uses FINDLINES and
some procedures using ALLPRESENT to find simple shapes in the picture.
The only shapes it can recognise are triangles, squares and "dots"
(composed of a little block of four marks). Single dots, and other
shapes will either confuse it or it will ignore them. There are some
procedures in LIB EVPICS that work for this purpose, (when the library
is loaded, it tells you the names of the procedures it defines); you can
use them in answer to the request for the names of pictures
A,B,C,D1,D2,D3. (For details: SHOWLIB EVPICS)
The result of FINDLINES and shapefinding is a low-level description of
the scene depicted in the picture. To save time later, you are given the
option of storing this low-level description, so that the name of the
picture is now the name of a list rather then the name of a procedure.
Variables whose values are such lists may be used instead of procedures
to draw pictures.
The next stage of processing is to make a network description of the
picture. Because a more general network matcher turned out to be very
slow when matching two networks which both contain more than a few arcs,
there are some conventions adopted by this matcher, which you need to
know about.
1) The network matcher distinguishes two kinds of arc, and two kinds
of node (representing things and classes). It won't match dissimilar
kinds of arc or dissimilar kinds of node.
2) The first kind of arc is between the two kinds of node. It is
represented by a three element list. The first element is of the
first kind of node (a thing), the third of the second kind (a
class). Here is an example:
[FIDO ISA DOG]
3) The second kind of arc is between two nodes of the first kind
(things). It is represented by a four element list. Here is an
example:
[EMOTES FELIX HATES FIDO]
The second and fourth elements are nodes of the first kind, the
first and third elements together make up the name of the relation,
but are matched separately.
4) The matcher can match arcs of the second kind where the order of
the nodes is reversed, but obviously the order of the nodes cannot
meaningfully be reversed for arcs of the first kind.
Now you are ready to give the program its second picture. It goes
through the same performance as before, to build a network description
of the second picture. Then it compares the descriptions of the two
pictures. The simpler and more similar the two pictures are the faster
the comparison is. Good example pictures are PIC1 and PIC2 from LIB
EVPICS.
Now give it the third picture. After this, you will be asked if you want
it to predict the answer. Unless you are getting good response from the
machine, it is best to answer "no".
Carry on until it has "seen" all the pictures. Incidentally, because the
matcher is not very smart, there is no guarantee that it will always get
the "right" answer, but in any case it is not clear that there always is
a unique right answer.
-- EXERCISE 2 ---------------------------------------------------------
To get some feel for what is going on, try to find a match between the
following two networks, but do it "by hand", i.e. not with the computer.
Here are the two networks (in the format used by the analogy program
above, but with all names replaced by meaningless symbols, so you don't
get any additional clues):
GRAPH1
[1 isa a][2 isa a][3 isa b][p 1 z 2]
[q 2 w 1][q 2 w 3][p 3 x 2][p 3 x 1]
GRAPH2
[4 isa b][5 isa a][6 isa b][p 5 x 4]
[p 5 x 6][q 5 w 6][p 6 z 4][q 4 w 6]
Before trying to match these networks, and before reading on, try
drawing them on some paper.
Below are my attempts to draw the corresponding graphs:
GRAPH1
[a] [a] [b]
| w | x |
| <---------- | <---------- |
->(1) z (2) w (3)-
| ----------> ----------> |
| x |
----------------------------------
GRAPH2
[a] [b] [b]
| x | w |
| ----------> | <---------- |
--(5) w (6) z (4)<-
| ----------> ----------> |
| x |
-----------------------------------
The procedure which is used by the analogy program to match graphs is
called COMPGRAPH. It takes two arguments, each a list of arcs in any
order. It expects the values of variables N1 and N2 to be the names of
the graphs. It returns no result, but after it is called DATABASE
contains a description of the comparison. If you want to compare your
answer with that produced by COMPGRAPH you should be warned that it
takes rather a long time on this example.
Your description of the comparison between the two graphs can be in any
format, but the format produced by COMPGRAPH (if you want to compare
your comparisons) is (obviously) the same format as you see when running
EVANS().
-- DIGRESSION ---------------------------------------------------------
Another type of "A is to B as C is ..." question commonly encountered in
IQ tests and puzzles uses words rather than pictures. For example,
MAN is to BOY as WOMAN is to what?
As in the picture problems, there may be a list of possible Ds which you
must choose from.
Obviously, to do this sort of question requires knowing what the words
mean - most of us couldn't do the equivalent Icelandic problem without a
dictionary. (Question: what sort of pre-knowledge, if any, is
necessary to do picture analogy questions?)
The ANALOGY demonstration program defines a variable called DICTIONARY.
If you print out DICTIONARY, you will see that it contains a database of
"definitions" of some words. Each definition is itself a database, of
the form used by the ANALOGY matcher. For example "girl" is defined as
[[female sex person] [young age person]]
The program has been modified so that if you give as the name of a
picture a word which is not a POP11 variable, it will use the dictionary
to find a database for that word, and it will use this database as the
description of the "picture". Otherwise the program works as for turtle
pictures. The matching is now fast enough that it is reasonable to use
the "predict" option.
Try giving the program the question '"man" is to "boy" as "woman" is to
"girl", "boy" or "horse"?'. You do this by typing the word as the name
of a "picture" when you run the program.
You can try extending the dictionary with your own definitions. Remember
the format described above!
-- EXERCISE 3 ---------------------------------------------------------
If you use the "predict" option in the analogy program, you will see
that it does not convert the predicted database back into a word using
the dictionary.
1) How might this be done? (It is not necessary to write a program, a
written answer is sufficient.)
2) Is the analogy dictionary a good representation of the information
needed to do this problem?
-- EXERCISE 4 (optional) ----------------------------------------------
An earlier version of the ANALOGY library program worked by using
"semantic features" for dictionary definitions. By this, I mean that
instead of a "semantic net" description, the "meaning" of an English
word was just a POP list of other words, meant to be the "semantic
features" of the English word. For example, the meaning of "children"
might be represented by the list
[person young plural].
Comparing lists of features is simpler than comparing networks.
Using this "semantic features" representation, have a go at writing a
word-analogy program that will give an answer as for the LIB ANALOGY
predict option. Convert semantic features back into words as far as
possible. You won't need to use any LIBs. Before you start, try to
answer the following questions:
a) How do you think the prediction process works? Try out a few
examples using the demo program, for inspiration, if you can't think of
a way.
b) What is the best way to represent the dictionary to make
converting words into features and back again as easy as possible?
c) What is the best representation for a list of features?
-- WINSTON'S ARCHES ---------------------------------------------------
Re-read the section in Winston on Winston's program (second part of
chapter two.)
-- EXERCISE 5 ---------------------------------------------------------
If you have time, you might like to think some more about matching
graphs.
For example, the description of the comparison produced by the demo
Analogy program is very impoverished. Is it too impoverished to be used
as a basis for a mini-Winston demo program?
Think of some problems that cannot be solved in terms of matching
graphs: are there any?
Write a SHORT essay on graph-matching, either considering one of the
above questions, or another equally exciting question of your own
invention.
-- READING ------------------------------------------------------------
The file TEACH * PICDEM may give you some relevant ideas.
The original thesis work by Evans is reported in the collection:
M.Minsky (ed) Semantic Information Processing, MIT Press 1968
It is not easy to read.
You should read the whole of chapter 2 in P Winston's
book: Artificial Intelligence.
There is a useful discussion of Analogy in M Boden's "Artificial
Intelligence and Natural Man" (Look up "Analogy" in the subject index)
The very first section (section 1.1, about 6 pages) in A Bundy's
"Artificial Intelligence: An Introductory Course" is an explanation of
another very simple approach to analogy, based upon Evans' idea. This
approach is slightly different to the approach in the exercises, so you
may find it helpful to compare it with the approach here.
There is also a very condensed account, by M Minsky, of Evans' program
in the Scientific American book: "Information".
TEACH * SCHEMATA
HELP * ANALOGY
--- C.all/teach/evans --------------------------------------------------
--- Copyright University of Sussex 1988. All rights reserved. ----------