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