> Imported from a scanned report using OCR. The transcription may contain recognition errors; consult the PDF for authoritative text and figures.

Patrick H. Winston

September 1970

Project MAC
Massachusetts Institute of Technology
Cambridge, Massachusetts 02139

Report: MIT/LCS/TR-76

Abstract

The research here described centers on how a machine can recognize concepts and learn concepts to be recognized. Explanations are found in computer programs that build and manipulate abstract descriptions of scenes such as those children construct from toy blocks. One program uses sample scenes to create models of simple configurations like the three-brick arch. Another uses the resulting models in making identifications. Throughout emphasis is given to the importance of using good descriptions when exploring how machines can come to perceive and understand the visual environment.

This report reproduces a thesis of the same title submitted to the Department of Electrical Engineering, Massachusetts Institute of Technology, in partial fulfillment of the requirements for the degree of Doctor of Philosophy, January 1970.

Acknowledgment

Marvin Minsky, Janet Winston, and Seymour Papert contributed significantly to the technical content of this work.

Work reported herein was supported in part by Project MAC, an M.I.T. research project sponsored by the Advanced Research Projects Agency, Department of Defense, under Office of Naval Research Contract Nonr-4102(02).

1 Key Ideas

How do we recoonize exaniples of various concents?

How do we learn to make such recoonitions?

How can machines do these things?

How important i$ careful teachina?

In this naper I describe a system that sheds some lieht on these ouestions by demonstrating how a machine can be taught to see anc learn new visual concepts, It works in the domain of three-dimensional structures made af bricks, wedges, and other simple objects.

Sood descriptive metheds are of central importance to this work, This is demonstrated repeatedly in my system's facilities for scene description, description cemparison, concept learning, and identification.

It is my opinion that the framework for learning that I describe suqgests a unity between learning from examples, learning Ey imitation, and learning ty be ine told, This unity lies in the necessary ability to cenerate ane manipulate good abstract de scriptions.

l also arque the importance of sood training sequences prepared by good teachers, I think it is reasonable to believe that neither machines nor children can be expected to Jearn much without then,

Equally important is the notion of the near miss, By

1.1 Scene Description and Comparison

near miss I mean a sample in a training sequence quite like the concept to be learned but which differs from that concept in only a few significant points at most. These near misses prove to convey essential points much more directly than repetitive exposure to ordinary examples,

.1 Scene Description and Comparison

Much of the system to be described focuses on the problem of analyzing scenes consisting of the simple objects that one finds in a child's toy box. There are two very simple examples of such scenes in fiaure 1-1.

From such visual images, the system builds a very coarse description. (figure 1-2) Structurina the scene's description in terms of objects is already a certain commitment, for structuring it in other terms is possible, In any case, analysis proceeds, inserting more detail. (fiaure 1-3) And finally there is the very fine detail about the surfaces, lines, vertexes, and their relations,

Such descriptions permit one to compare and contrast scenes through programs that compare and contrast descriptions, Of course, one hopes that the descriptions will be similar or dissimilar to the same dearee that the scenes they represent seem similar or dissimilar to human intuition, Then with a general plan for such manipulations,

there is further hope that the same machinery can be useful

FIGURE 1-1

[- One-Part-1I5

FIGURE 1-2

f- ONE-PART-1[S

Supported-By In-Front-Of

FIGURE 1-3

in situations ranging far from visual ones, giving the work a certain generality.

Certainly the necessary matching pronrams must be well endowed with ability, for a rich description capability requires a matching program that can cope with and perform reasonably in an environment where many matches are possible, both good and bad,

After two scenes are described and corresponding parts related by the matching prooram, differences in the descriptions must be found, catecorized, and themselves described, The program that does this must be able to examine the descriptions of fioure 1-3 with the help of a matching program and deduce that the difference between the scenes is that there is a supported-by relation in one case, while there is an in-frant-of relation in the other, But the faculty must be much more powerful than this simple example indicates in order to face more complex pairs of scenes exhibiting the entire spectrum between the nearly identical and the completely different,

1.2 Concept Generation and Learning

To build a machine that can analyze line drawings and build descriptions relevant to seme comparison procedure is useful in itself. But this is just a step toward the more

ambitious goal of creating a program that can learn to

Arch Near Miss

FIGURE 1-4 FIGURE 1-5

Arch Near Miss

FIGURE 1-6 FIGURE 1-7? |

1.2 Concept Generation and Learning

recognize structures. I will describe a program that can use samples of simple concepts to oenerate models,

Figure 1-4 and the next few following it show a sequence

of samples that enables the machine to learn what an arch is, First it gets the general idea by studying the first sample in figure l-4. Then it learns refinements to its original conception by comparing its current impression of what an arch is with successive samples, It learns that the supports of an arch cannot touch from figure 1-5, It learns that it does not matter much what the top object is fron figure 1-6. And then from figure 1-7 it learns the fact that for one object to be supported by the others is a definite requirement, not just a coincidence carrying through all of the samples.

Such new concepts can fn turn help in making other, more complex abstractions, Thus the machine uses previous learning as an aid toward further learning and further analysis of the environment, As yet these procedures are clumsy, and the descriptions uncomfortably restricted, but the results are encouraging enough to suqgest that these

methods may lead to inereasingly powerful performance,

1.3 Identification

Identification requires additional programs that use the results of comparison programs, There are many problems and many alternative methods involved because identification can be done in a variety of contexts,

In one simple form of identification, the machine compares the description of some scene to be identified with a repertoire of models, or stored concepts, Then at the very least there must be some method of evaluating the comparisons between the unknown and the models so that some match can be defined as best.

But many sophistications lie beyond this skeletal scheme, For one thing, the identification can be sensitive to context. In figure 1-8, for example, one hidden object is more likely to be a wedge than in the other case, although both hidden objects present exactly the same Tine configuration, The identification could te further prejudiced if the objective is to locate a particular type of object, Thus the hidden object in figure 1-9 should be tentatively identified as a possible trapezoidal solid,

rather than a wedoe, if trapezoidal solids are in demand,

FIGURE 1-8

FIGURE 1-3

1.4 Psychological Modeling

Simulation of human intelligence fs not a primary goal of this work. ‘Yet for the most part I have desiqned programs that see the world in terms conforming to human usage and taste, These programs produce descriptions that use notions such as left-of, on-top-of, behind, big, and part-of,

There are several reasons for this, One is that if a machine is to learn from a human teacher, then it is reasonable that the machine shoud understand and use the same relations that the human does. Otherwise there would be the sort of difference in point of view that prevents inexperienced adult teachers from interacting smoothly with small children.

Moreover, if the machine is to understand its environment for any reason, then understanding it in the same terms humans do helps us humans to understand and improve the machine's operation. Little is known about how human intelligence works, but it would be foolish to ignore conjectures about human methods and abilities if those things can help machines. Much has already been learned from programs that use what seem like human methods, There are already programs that prove mathematical theorems, play qood chess, work analogy problems, understand restricted forms of

English, and more, Yet in contrast, little knowledoe about

intelligence has come from perceptron work and other approaches te intelligence that do not exploit the planning and hierarchical organization that is characteristic of human thought.

Another reason for desianing programs that describe scenes in human terms is that human judgement then serves as a standard. There will be no contentment with machines that only do as well as humans. fut until machines become better than humans at seeing, doing as well isa reasonable qoal, and comparing the performance of the machine with that of the

human is a convenient way to measure success.

2 Building Descriptions

2.1 The Network

There are many ways to store facts about a scene. ne

simple format is the unordered list:

A is on top of G

Al is a side of &

Bois in front of C Such an arrangement is desperately inefficient because the whole of memory must be searched to oather all facets about some particular cemponent of the scene, Jt is natural, therefore, ta record facts in a mere structured way to facilitate retrieval.

In this connection, one hears such terms as lists, trees, rings, and nets, each of which suggests a form of storage. In selecting one, attention must be paid to several criteria, I have already mentioned the problem of rapid access, There may also be a need to use memory space efficiently, Dut in the research nhase, perhaps it is most important that the storace format be im some sense natural with respect to the information to be stored, This means that the transformation from a situation to its representation should be sinmnle, not awkward, Sinnle lists suffice for a trip to the grocery store, while tree-like

charts frequently picture command hierarchies or genealogical

histories.

But many more complex situations require the net, A qood example is the description of the words in a natural language. Each word jis described easily in terms of relationships with other words which in turn are similarly described, The result is a dictionary im which each word may be thought of as a node which is related to other nodes through the pointers that constitute its definition.

Similarly the network seems to have the appropriate blend of flexibility and elenance needed to deal straightforwarly with scenes, It is the natural format. Like words in a dictionary, each object is naturally thought of in terms of relationships to other objects and to descriptive concepts like large, rectanqular, and standing. In figure 2-1, for example, one has concents such as OBJECT- ABC and OBIECT-DEF, These are represented diagrammatically as circles. (figure 2-2) Labelled arrows or pointers define the relationships between the concepts. (finure 2-3) Other pointers indicate membership in general classes oar specify particular properties. (figure 2-4) And pointers to circles representing the sides extend the depth of the description and allow more detail. (figure 2-5)

Now notice that notions like SUPPOPTED-BY, ABCVE, LEFT-

OF, BENEATH, and A-KIRD-OF may be used not only as relations,

FIGURE 2-1

FIGURE 2-2

Left-0F —,

)

Right -Of -

FIGURE 2-3

A-Kind-Of

Has-Property-Of

FIGURE 2-4

One-Part-15

FIGURE 2-5

but also as concepts, Consider SUPPORTED-BY. The statement, "The WEDGE is SUPPORTED-BY the BLOCK," uses SUPPORTED-BY as a relation, But the statement, "SUPPORTED-BY is the opposite of NOT-SUPPORTED=BY," uses SUPPORTED-BY as a concept undergoing explication. Consequently SUPPORTED~BY is a node in the network as well as a pointer label, and SUPPORTED-5Y itself is defined in terms of relations to other nodes,

Figure 2-6 shows some of the surrounding relations and

concepts,

SUPPORTEU-BY may therefore appear in diagrams as a circle label or as a pointer label denending on its function. A circle pierced by an arrow indicates simultanecus use as a relation and as a concept. (figure 2-7)

Thus, descriptions of relationships can be stored in a homogeneous network along with the descriptions of scenes that use those relationships. This permits biq steps toward program generality, A program to find neqatives need only know about the relation NEGATIVE-SATELLITFE and have access to the general memory met. There is no need for the program itself to contain a distended table, This way programs can Operate in many environments, both anticipated and not anticipated, Algorithms desianed to manipulate networks at the level of scene description can work as easily with

descriptions af objects, sides, or even of objects’

Modlfication-Of

j NBeat TVE-SATELLITE

MUST-BE- Sen

———— Modification-Of

Must-Not-Be-

Supported-By

Must-Be-

Supported-By

Must-Not-Be-Satellite

FIGURE 2-6

—— Opposite

FIGURE 2-7

functions, given the appropriate network. .2 Preliminary Processing

Consider now the seneration of a scene description, The starting point is a line drawinn, without perspective distortion, and the result is to be a network relating and describing the various objects with nointers such as IN- FRONT-OF, ABOVE, SUPPORTED-BY, A-KIND-OF, ABUTS, and HAS-

Property=Of ,

First, drawings of three-dimensional scenes are communicated to the machine using a promram by B, EK. P, Horn together with a special pen whose position on a companion tablet can be read by the machine directly. Then a program written by H, N. Mahabala [1] classifies and labels the vertexes according to the number of converaing lines and the angles between them, Fiaure 2-8 displays the available categories. Notice that Mahabala's program fines pairs of Ts where the crossbars Tie between collinear uprights. These are called matched Ts. Such pairs occur frequently when one object partially occludes another as in figure 2-9,

The program then proceeds to create names for all of the regions in the scene. Riqorcusly "recion" as used here simply refers to any maximal area in which one can move from any point to any other point without crossing a line, Includina

the background figure 2-9 has eight reaions, Various

Fork

Multi

FIGURE 2-8

MATCHED Ts

Peak

FIGURE 2-3

FIGURE 2-18

FIGURE 2-11

properties are calculated and stored for these remions. Among these are a list of the vertexes surrounding each region and a list of the neighboring regions,

These results are then supplied to the elegant program named SEE developed by A. Guzman [2]. This prooram conjectures about which regions belong to the same objects. For fioure 2-9, the end result of the program is the commentary:

Body 1 consists of AEC

Body 2 consists of ) EF G I! Surprisingly the program contains no explicit models for the objects it expects to see, It simply examines the vertexes and uses the vertex classifications to determine which of the neighboring reaions are likely to be part of the same object. Arrows, for example, stronoly suqgest that the two narrow. angle regions belong to the same body, (figure 2-10) This sort of evidence, together with a moderately sophisticated executive, can sort out the renions in scenes as complicated as that in fiqure 2-11, berrowed from Guzman's thesis,

Twelve objects are reported and the regions of each are

remembered, This, then, is the sort of information ready for further

processing by my deseription-building procrams,

2.3 The Alaorithms

The following sections describe the ideas behind proarams that lock for the relations ABOVE, SUPPORT, IN- FRONT-OF, LEFT, RIGHT, and MARRYS, Generally these programs produce descriptions that are in remarkable harmony with those of human observers, Sometimes, however, they make conjectures that most humans disagree with, Gn these occasions one should remember that there is no intention to precisely mimic psycholoogical phenomena. The opal is simply to produce reasonable descriptions that are easy to work with, Right now it is important to desian and experiment with a capable set of programs and postpone the question of how the proqrams mioht be refined to be more completely lifelike.

2.3.1 Above and Support

T joints are strona clues that one object partly obscures another, but then one may ask if the obscuring occurs because one object is above the other or because one is in front of the other. Even in the simple two brick case there seems to be an enormous number of confiourations,

Figure 2-12 shows just a few possibilities.

But in spite of this variety, there is a simple procedure that often seems to correctly decide the ABOVE

versus IN-FPONT-OF question. Consider the lines that form

Wd — b Do |

FIGURE 2-13

Interior Line

Bottom Limes - *

FIGURE 2-14

Interior Line

Bottom Lines -~"

FIGURE 2-15

FIGURE 2-16

Interior Line

Bottom Lines

This is really a rule and two corollaries, rather than three separate rules, Xs and Ks result primarily when arrows appear incognito, camouflaged by an alianment of objects as illustrated by figure #@-15 and 2-16, Consequently, the corresponding rules amount to locating the arrow-forming parts of the vertex and then acting on that basic arrow,

One further step is necessary before a line can become an approved bottom-line, fs shown by fieure 2-17, some of the lines qualifying so far must be eliminated, They fail because they are too vertical, or more precisely, because they are too vertical with respect to the arrow's shaft, The effective way to weed out bad lines is as follows:

Rule: Eliminate any bottom line candidate which is more

vertical than the shaft of the arrow sucoestine that

candidate,

Of course the preoram extends rudimentary bottam lines through certain vertexes, Fiqure 2-10 shows the obvious situations in which the bottom line property is extended through the crossbar of a T or the shafts of a pair of matched Ts.

This whole alaorithm is based on an assumption that the machine observes the scene from above. If the confiauration dangles from the ceiling, simple chanoes adapt the proeram to

discriminate between UNDER and IN-FRONT-OF, rather than ABOVE

‘oe

Bad Candidates

FIGURE 2-17

FIGURE 2-18

and the

line

IN-FRONT-OF, One examines instead the hioher vertexes of interior lines, substitutes the term top lines for bottom

s in the vertex inspection rules, and the resulting lines

usually Separate objects from those above them,

2.3.1.1

By searching for both the ABOVE and the BELOW relations, the machine may often be able tno quess its own height, Consider finure 2-19, Figure 2-20 shows the same scene with top and bottom lines highlighted and with the cansenuent above and below relations, At least in this case, the machine can correctly deduce that its

eye is level with object ™ because both a chain of above relations and a chain ef below relations originate at “,

Discussion

This algorithm works effectively because of

circumstances all likely but not certain to ke true in any

particular scene, The method works best when a scene

consists of bricks and wednes with one side parallel to the

table. In many other cases, the method works anyway,

sometimes by coincidence and sometimes ty principles not yet

fully explored,

objec

relat

Unfortunately, in explanation I am frequently forced to appeal to intuitive notions about what is likely and what is not, I know of no way to establish a reasonable probability metric on the situations | discuss. All that can be said now is that any such metric should reflect human disposition toward configurations exhibiting alionment and symmetry,

The first likely circumstance or principle is that ts tend to support other objects by contact through

ively horizontal sides, Objects not so supported tend

FIGURE 2-19

FIGURE 2-28

to slip, although not always as demonstrated by figure 2-21,

Imagine now that the top object in fiqure 2-22 were completely transparent except for a layer of paint on the crucial, relatively horizontal bottom side. Since the scene is viewed from above, this bared bottom side will obscure part or sometimes all of the supportina object. See figure 2-23, Consequently, some faces of the supporting object generally border on lines resultinn from the edges of the bottom side,

Of course many of the bottom side's ednes vanish when the object fis restored to opacity, Nevertheless, the ones that remain still tend to form part of the seam between the supported and the supporting objects,

Now most of the vertexes of objects are formed by three edges meeting together as in the tip of a pyramid. This forms the so-called trihedral angle. Consequently, when two observable edaes of the bettom side form a concave anole, one can expect a third edoe of the object to leave the same vertex and form the shaft of a downward direeted arrow,

Slight alteration could permit the proaram to deal with many objects with non-trihedral vertices, The object in figure 2-24, for example, has two interior

lines merging at vertex V. By treating this as a

generalized arrow, with multiple shafts, the same

algorithm can be used to define bottom lines,

So far the locic is as follows: If one object obscures

FIGURE 2-21 FIGURE 2-22

FIGURE 2-23 FIGURE 2-24

another because it is on top of the other, then the seam between the two is likely to form the barbs of one or more downward directed arrows belonging to the top object. Reversing this, one would hope for the statement: The barbs of downward directed arrows define seams across which one likely finds the supporting object or objects. Unfortunately one often finds non-supportina objects as well.

2.3.1.2 Refinement

Figure 2-25 sugcests a serious kind of over enthusiasm.

The pillar, brick 8, elevates the bottom lines of brick A and they appear between the viewer's eye and a side of the massive background brick, brick C. In the two brick case, a brick's bottems lines border on the side of another brick only when the one is in fact supported by the other. hen more objects are involved, wrong answers may result because the bottom lines can wander into regions of objects that do not offer support.

To handle this nroblem, I use a two part procedure. The first part is simply the above aloorithm as described so far, which now may be thought of as qeneratina a set of possible supports. The second part, described below, criticizes these possible supports and filters out some of the bad ones,

Now one reason brick A in figure 2-25 clearly does not

lie on brick C fis that it is absurd to think that an object

can rest ona vertical side of some other object. Part 2 of the support alcorithm makes sure that just such conjectured supports are eliminated from the list of candidates, To do this, it eliminates a candidate if the only bottom-1 inebordering side seems vertical, It assumes a side is vertical if an edge belonging to it is vertical,

There are two exceptions to this rule that occur when an object obscures the entire top of its sunporting object as block § obscures block G and as block B obscures block € in figure 2-26, First, if two bricks are alioned as are brick A-and brick 6, forming the familiar X vertex, nm rejection takes place. Second, if the top brick averlaps the support as brick B overlaps brick C, at least one unmatched T appears and again no rejection takes place,

If ty this time zero or one support candidate remains, then part 2 terminates, and the sunport, if any, is announced, There are some common situations, however, that require part @ to undertake additional computation, Cornare figure 2-27 with fiqure 2-25. The vertical-side filter cannot eliminate the possibility of supnort from brick C in either fioure because one of C's bottom-line bordering sides is clearly mot vertical. Yet human observers qenerally claim the top brick in figure 2-27 cannot be other than sinaly

supported, whereas they admit there may well be support from

the large rear black, C, in fiocure 2e-P8,

Since the only difference is in the heioht of brick £, this judoement must be the result of a height comparision.

Stated simply, the program makes height judgements by assuming an object is supported by the tallest of the support candidates surviving so far. It is simply above the others. The heiaht ef a stack cannot always be computed rioorcusly, however, In simple cases it is sufficient to Tecate a vertical line belonging to the object and measure it, Brick C in figure 2-27 is such a block, Sut the verticals of block B disappear into T joints and only minimum heinhts can be calculated from such lines without complicated and unexplored object extranolation techniques, Cansequently, 4s the algorithm reviews the heiqhts and minimum heiahts presented to it, it first selects the maximum of these. Then any candidate whese height is known exactly is rejected if that height is less than the maximum just calculated, All whose exact heights are unknown are allowed to pass.

Figure 2-29 shows why the support alaorithn frequently

resorts ta recursion, If the support for block C is to be calculated, the heiaht of blocks D and E must be compared. But this in turn requires knowledae of their supnort so that total heights can be added up fram the chain af supports and

used in this last filtering operation of part 2.

This completes discussion of the support algorithm as it now stands, It is not hard to delude it deliberately, but it nevertheless operates with a reliability sufficient for use by programs that build upon its results,

Improvements can be made in many ways, The followina are a few ideas high on my priority list: 1, A planned modification involves using Ls in the search for bottom Jines. So far the system gags on the scene in finure 2-30, finding no bottom lines, But if one line of an L is nearly vertical and the other is nearly horizontal, then the nearly horizontal line should be an excellent tottom line, Of course Ls are frequently buried just as arrows are, Buried Ls are found im certain Ts, Xs and forks as shown in fiqure 2-31. 2. The discovery of bottom lines can be fouled by introducing small objects that obscure crucial vertexes.

Figure 2-32 shows how, This could be corrected by a

procedure that extends lines, perhaps after the object is identified, 3, The filtering operation could be strenathened in its ability to detect vertical sides, $0 far ft knows a side is vertical only if the side has a vertical edne. Fioure 2-33 shows how it can run aground as a result. None of the sides of brick C appear vertical and the algorithm consequently reports brick A is om top of brick C as well as

on brick By

FIGURE 2-39

FIGURE 2-32

BURIED Ls

FIGURE 2-31

FIGURE 2-33

2.3.2 In-front-of

Once a program can discover the SUPPORTED-8Y relation, then it can frequently deduce IN-FRONT-OF relations by default. That is, if one of two blocks appears to obscure another but is not above it, then the relation IN-FRONT-OF is a strong possibility, In pursuing this I again use a two part program: the first part proposes possible objects that a given object may be in front of; the second part rejects the bad ones, While simple and direct, this program also succeeds admirably on complex scenes.

Part 1 tries to find all objects that the object jin question obscures. First it gathers up most of the obscured abjects through search for particular types of T joints on the periphery of the object. Supoose one defines a line to be physically associated with a particular object when that line in the two dimensional drawino results from an edoe or intersection of planes on the object, rather than from some obscuring object. Figure 2<34 illustrates, Then the types of Ts sought are just those for which one can be reasonably sure that the crossbar belongs to the object conjectured to be the obscuror,

Figure 2-35 shows two kinds of qualifying T joints, The

first kind occurs when the wide angle region associated with

the T belonas to or is physically associated with the object

Physically Associated Lines Of A

Physically Associated Lines Of B

FIGURE 2-34

from which IN-FRONT-OF relations are sought, Both of the ather regions, the ones borderina the shaft of the T, belong to a second object. This nearly always indicates the second object is obscured,

The second kind of T joint illustrated in figure 2-35 occurs when one shaft-borderina reqion belangs to an object while the other belongs to the backoround, This again assures the machine that the crossbar belongs to the potentially obscuring object.

Figure 2-36 indicates by counter example why nothing can

be deduced if the shaft-bordering reqions belone to distinet objects. The trouble is that the crossbar of the T is not a real edoe of block C, but rather the crossbar is composed of edges belonging to A and B,

Still another way to locate appropriate Ts is more global, The idea is to use whatever means are available to find genuine edges belonging te a body and then to see if any Ts lie along such lines. ecall that the selection af bottom lines involves inspection of arrows, {s and Es at the bottom ends of interdor lines, Furthermore the rationale behind the support algorithm depends on the likelihood that such bottom lines are physically associated with the same object as the interior line of the arrow, X, or K, Consequently the machine

can generate a whole family of peripheral lines likely to be

physical edaes by simply examining the arrows, Xs, and Ks at both ends of the interior lines, rather than just these at the bottom ends. Then if any of these physically assoc iat ed lines end at an L, the other line forming the L is added to the list. It is very unusual for one leg of an L to belong to an object without the other lea belonaing also,

How if any physically associated line is the crossbar of aT, then the parent object obscures some other object or objects. Fioure 2-37 demonstrates what Find of edges and Ts are found by this method.

Notice that the Ts referenced by figure 2-37 are also noticed by the previously discussed local inspection since they exhibit the recuired configuration of objects about the Ts lines, Figure 2-38 demonstrates that both methods contribute, however, since only the local method works on Ts marked L while only the modified bottom-line finder helps on those marked G.

All of this yields obscured objects which are candidates far relating to the object studied by the relation IN-FRONT- OF, Next, part 2 requests help from the support program and then immediately rejects all the candidates for which the ABOVE relation is known to hold, This however is often not completely sufficient. In figure 2-39, the machine knows

brick A obscures brick C by virtue of vertex V, But A is not

All Outer

Edges Found

FIGURE 2-37

FIGURE 2-38

directly above C. Clearly, the above check must be expanded to the presence of chains of ABOVE relations in order to bring the algorithm into line with human taste, In the course of this check, the program for ABNVE may be called many times if the ABOVE relations have not yet been established, Any candidate that survives this check is thought to be behind the object studied.

The most annoying weakness of this algorithm is that the seam between the obscured and the obscuring object may not exhibit the required type of T joints, Figure 2-40 shows how this can happen, I suspect that further progress can be made in these situations of alignment through close consideration of Xs and perhaps Fs.

2.3.3 An Example

Figure 2-41 provides a somewhat more comnlex scene for

the IN-FRONT-OF and SUPPORTED-B8Y finding crograms to try.

The results are as follows:

A supported-by BC in-front-of F &

B K -

Cc DE - u - E

E - -

F E od & - -

H Ij -

I - -

J - -

K H E

The only bad choice is the neglect of G as a support of F, The reason is that the support criticizing prooram has a built in assumption that a supported object's bottom jis level, Therefore it believes E is the only support for F because it is higher than G, the other possibility.

2.3.4 Left and Right

Two programs exist for deciding if one object is left of, right of, or neither with respect ta another. The first Computes in a straightforward, simple way, It simply compares the x coordinates of the vertexes of both objects,

If there is no overlap, that is if

xcor(any vertex of one object)

xcor(any vertex of other object)

then the first object is to the left of the other, If there is overlap, then no statement can be made.

This program, based on the no-cverlap criterion, could be greatly improved through the use of an object extending program, The machine is naive to think that object ¢ in figure 2-42 is left of object A. Humans tend to fill in the obscured portions of object C to form a complete block.

But even with an ability to imagine the hidden parts of objects, such a program refuses to really acree with human judgements. Consider the spectrum of situations in figure 2-43, For the first pair of objects, the relations LEFT-OF and RIGHT-OF are clearly appropriate. For the last, they are clearly not appropriate, To me, the crossover point seems to be between the situations expressed by pairs 4 and 5.

Now notice that the center of area of one object jis to the left of the left-most point of the other object in those cases where LEFT-OF seems to hold. It is not so positioned 1f LEFT-OF does not hold, Such a criterion seems in

reasonable agreement with intuitive pronouncements for many

mere +--+ es,

FIGURE 2-42

FIGURE 2-43

of the cases I have studied, It also yields reasonable answers in figure 2-44 where in one case A is to the left of 8 and in the other case it is not, Notice that the relation is not symmetric, however, as the center of area of the much longer brick, brick B, indicates B is to the right of A in both cases,

Figure 2-45 requires extra attention, No matter what

the center of mass relations, humans are reluctant to use either LEFT-OF or ? IGHT-OF if one object extends beyond the other in both directions, One must additionally specify a rule against this, leaving the following for LEFT-0F:

Say A is left of B <=>

The center of area of A is left of the leftmost point of B,

The rightmost point of A is left of the rightmost point of &,

The rule for SIGHT-GF is of course parallel in form,

Many people feel their perception of the relation LEFT-OF differs considerably from either of the two possibilities exhibited here, I believe the center-ofarea method is reasonable for the machine now, but it would be interesting to more fully explore the question of what humans think to see if other formulas are better. Intuitive notions of LEFT-OF vary wildly and the program can only ke said to generally reflect my personal preferences. Indeed, deciding if one object is to the left of another stimulates far more argument than do questions involving relations like IN-FRONT-OF and SUPPORTED-BY, People have difficulty verbalizing how they perceive LEFT-OF and tend to waver in their methods, but implications are that criteria change depending on whether the objects involved are also

FIGURE 2-44

a? !

FIGURE 2-45

FIGURE 2-46

related by IN-FRONT-OF, ON-TOP-OF, BIGGER-THAN, and so on.

Professor Marvin Minsky has pointed out to me that the orientations of objects are also a strong influence, In figure 2-46, for example, the cube seems left of the arch's entrance even though all its vertexes are clearly right of all the arch's vertexes, In view of this observation, my procedure could probably do better by asking basi¢alty the same questions as before, but about lines through the left-most, right-most, and center-ofarea points in the direction of orientation instead of what amounts to vertical projection of the points to the x-axis, Put then there is the problem of finding an object's intrinsic orientation, At the moment I know of ho general heuristics for this,

2.3.5 Marrys

The abuts and aligned-with relations arise frequently, perhaps because of some human predilection to order, As intuitively used, however, neither of these words corresponds to the notion T want the machine to deal with, To avoid confusion, I therefore prefer to use the term marry which I define as follows:

Definition: An object marrys another if those objects

have faces that touch each other and have at least one

common edce. Thus the objects in figure 2-47 are said to marry one another. Those in figure 2-48 do not because they have no common edge, Similarly those in figure 2-49 do not because they have no touching faces.

The MARR YS relation is sensed by methods resembling those previously described, First the vertexes along the

border are collected. Then the Xs, Ts and Ks are further

FIGURE 2-47

FIGURE 2-48

FIGURE 2-43

examined:

The Xs are simple to handle, If exactly two of the lines are collinear and if the other two separate two objects, then those objects are very likely to deserve the MARRYS relationship because such a vertex is strongly associated with aligned stacks or rows. Fioure 2-50 illustrates these situations, Fioure 2-51 shows why the two objects must be separated by the two non-collinear lines. There three sides belong to the same object and the MARRYS relation does not hold.

If there are four objects at the vertex and there are two pairs of collinear lines, then the likely situation is a field of objects with those sharing lines marrying each other, See figure 7-52,

Ks are strongly correlated with the sort of alignment illustrated by figure 2-53, The rule is simple: If there are two objects with sides at a K vertex, then they probatly marr ys

When three objects meet at a T one of the following

holds:

The objects with the stem in between marry each other and both obscure the third object,

The third object is the obscuring object, In this case the two other objects may or may not marry.

FIGURE 2-58

FIGURE 2-51

| Figure 2-52

FIGURE 2-53

FIGURE 2-54

All three objects marry. 4. Something else,

Of these, my programs check for case l only. The central program looks for chains of IN-FRONT-OF and SUPPORTS relations between the shaft-bordering objects and the largeangle object. If such chains are found for both, they likely both obscure the large anqle side and marry each other.

Figure 2-54 shows examples,

Now consider the situation where only two objects meet ata T with the wide angle side and one of the other sides belonging to one object. As figure 2-55 suqgests, this sort of T frequently becomes a K when seen from some other angle. Like the Kk, the machine considers it strona enough evidence for a MARRYS relation,

Figure 2-56 illustrates both of the T joint situations

that confirm marryment.

Note that the machine is conservative in using this MARRYS relation; the relation is not placed in ambiguous situations such as those of figure 2-57,

2.3.6 Shape

Before an object can be identified, the limes that are really edges of that object must be sorted from those that are edoes of obscuring objects. It would not do to think

object B in figure 2-58 has sides shaped like those in

FIGURE 2-55

FIGURE 2-56

FIGURE 2-57

FIGURE 2-58

FIGURE 2-53

figure 2-59,

The idea of an edge belonging to a body has been discussed. The shape program I use first gathers together those lines found to be genuine physically associated edges by the program that looks for IN-FRONT-OF relations. To these it adds any lines that lie between two reqions of a body, the interior lines. Then if these lines include both uprights in a pair of matched Ts, it adds a line joining the two Ts, And finally, any line shared with the backoround or other body known to be below or behind is certainly included. These rules are sufficient to identify many of the lines that belong to any qiven object, while rejecting many that do not belong.

Figure 2-60 shows how this program sees object 8 of

figure 2-58, Lines L, M, N, and OQ are interior lines, Line P is a segment between matched Ts with the required kind of uprights. Q qualifies by way of the IN-FRONT-OF algorithm, while R, 5, T, U, and Y qualify both by way of the IN-FRONT- OF algorithm and the rule adding lines lying between the object and the background, Figure 2-61 shows how the rest of the scene in figure 2-58 is dissected by this program.

Notice that the shapes are reasonably well defined,

FIGURE 2-68

2.3.7 Size

Piaget has shown that at a certain age children generally associate physical size with greatest dimension {3]. They will, for example, adamantly maintain that a tall thin beaker has more water in it than a short fat one even though they have seen them filled from other beakers of equal size.

Adults do not develop as far beyond this as might be expected. Ido not think we really use the notion of volume naturally. Apparent area seems much more closely related to adult size judgement. Notice that beaker A in figure 2-62 appears to have about the same amount of water in it as does beaker B, even though it must contain twice as much. Unless a subject consciously exercises a formula for volume, he is likely to report that object B in figure 2-63 is approximately ten times larger than object 4, even if told both objects are cubes, The true factor of twenty-seven times seems large when the trouble is taken to calculate it,

Consequently, the size generating program does not trouble with volume, Instead it calculates the area of each shape produced by the shape detecting algorithm, Next it adds together the areas of all shapes belonging to an object to get its total area. Then using these areas it can compare

two objects in size or consult the following table for a

FIGURE 2-62

FIGURE 2-63

3 Discovering Groups of Objects

When a scene has more than a few objects, fit is usually useful to deepen the heirarchy of the description by dividing the objects into smaller groups which can be deseribed and thought of as individual concepts. Fioure 3-1, for example, seems to divide naturaliy into three groups of objects, one being three objects tied together by SUPPORTED-BY pointers, another being three similar objects on top of a fourth, and the third being a set of objects in the arch configuration, There are other kinds of grouping humans use, but in this work TI primarily explore only the three illustrated by this figure 3-1. Grouping by identification with a known model is discussed later in the chapter on identification, This chapter deals with grouping on the basis of pointer chains and on the basis of property similarities,

3.1 Sequences

A simple kind of group consists of chains of SUPPORTED- BY or IN-FRONT-OCF pointers as in the tower of figure 3-1. The first act of the groupine program is to find sets of objects that are so chained together, All such sets with

three or more elements qualify as groups.

In the event the sequence of pointers closes on itself, a ring is formed, In figure 3-2? there is such a group

because each of the three objects rests partly on one of the

FIGURE 3-1

FIGURE 3-2

other two, The result is a circular chain of SUPPORTED-BY pointers as shown in figure 3-3.

Using chains to define groups can become fairly comm lex as illustrated by the scene in figure 3-4, A chain of SUPPORTED-BY pointers splits into two branches jn scene one at the point where object C is supported by two objects, D and —, In scene two, two chains of SUPPORTED-8Y pointers join at M which supports both I and L. The current version of the grouping program terminates chains at junction points without further fuss. This seems reasonable for it seems natural to think of the scenes in fioure 3-4 as a set of groups consisting of f-B-C, G-H-I, and J-K-L.

Another kind of problem arises when objects tied together by a simple chain of relations should not constitute a qroup because of other factors. Figure 3-5 shows one kind of situation that can occur, for which I have only ideas but no programs, In this scene the machine perceives a sinole object conalomerate, grouped together by virtue of an unbroken chain of SUPPORTED -BY pointers, But most humans see a short tower on top of a board on top of another tower, This must be partly because of the size differences and partly because of the fact that the top group is not directly aver the other objects, In any case, it would seem that radical change in object properties should be possible grounds for breaking a chain. With this, one is into territory where irrevocable committments should be avoided, Perhaps the best thing would be to have the croupina program offer alternative groupings of tricky scenes and postpone decision until higher level identification programs indicate which arrangement leads to the best match of the scene against known models.

One-Part-I5

Supported-By

FIGURE 3-3

@| :

> B

Sa | *

3.2 Common Properties

When several objects have the same or very nearly the same description, they are immediately solid candidates for a group, The legs on the table in figure 3-6 are typical, 411 are bricks, all are standing, and all are supports for the top board,

This kind of manipulation is slightly dangerous in that my criteria for forming a group and admitting members to it are a bit flimsy. So far the rules are based on the following demands:

1, All candidates for group membership must be related

to one or more particular objects in the same way, For the table case, all four objects are related to the board by SUPPORTED-BY, This restriction appears necessary because uniform relationship to a single object seems to have strong binding power, The standing bricks in figure 3-7 naturally constitute two groups, not one,

There must be three or more members in the group, and the members of the croup must share many of their properties.

Figure 3-8 outlines the procedure for forming such

groups. The basic idea is to make a generous guess as to what objects to include in a group and then to eliminate objects which seem atypical until a fairly homogeneous set

remains, To do this, a pregran first finds a candidate group by

locating @ set of objects that relate to one particular

FIGURE 3-6

FIGURE 3-7

Find Objects Related

To Some Particular

Object In The Same Way

Form

Common-Relationships-Li8T

Remove Atypical

Objects From

The Group

Were Any Eliminated?

Supplement The Net

With Information

About The New Group

FIGURE 3-8

object in the same way, Next comes formation of a commonrelationships-list through a listing of all relationships exhibited by more than half of the candidates in the set.

Figure 3-9 helps explain this process, Objects A

through F are immediately perceived to be a possible group because they all have a relationship, SUPPORTED-BY, with a single object, G. The relationships exhibited by the candidates are: Ay By, and Cr 1 SUPPORTED-BY pointer to G 2 MARRYS pointer to G

a A-KIND-OF pointer to BRICK 4 HAS-PROPERTY-OF pointer to MEDIUM-SIZE

1 SUPPORTED-BY pointer to G

2 MARRYS pointer to G

3 A-KINU-OF pointer to BRICK

4 HAS-PROPERTY-OF pointer to SMALL E and Fr

1] SPPORTED-BY pointer to G 2 MARRYS pointer to G 3 A-KIND-OF pointer to WEDGE 4 HAS-PROPERTY-OF pointer to SMALL Three relations appear in the common-relationships-1 ist because they are found in more than half of the candidates’

relationships lists:

FIGURE 3-3

common-relationships-list: 1 SUPPORTED-BY pointer to G 2 MARRYS pointer to G 3 A-KIND-OF pointer to BRICK After this common-relationships-list is formed, all candidates are next compared with it to see how typical each is. The measure is simply the fraction of the total number of properties of the candidate and the common-relat ionshipslist that are shared, Said in a more formal way, the measure

number of properties in intersection

number of properties in union

where the union and intersection are of the candidate's relationships list and the common-relationships-list.

Figure 3-10 represents abstractly a situation in which the

candidate and the common-relationships-list are quite different, The shared properties, represented by the shaded area, is but a very small fraction of the total area, both shaded and unshaded. Figure 3-11 gives the opposite extreme,

There is considerable overlap and the value is near one, the

maximum possible,

Using this similarity formula to compare the various objects of the figure 3-9 example with the commonrelationships-list, one has:

A versus the common-relationships-list --> 3/4 = .75 B versus the common-relationships-list <--> 3/4 = .75 C versus the common-relationships-list --> 3/4 = .75 OD versus the common-relationships-list -->} 3/4 = .75 E versus the common-relationships-list --) 2/5 = ,20 F versus the common-relationships-list --? 2/5 = ,20

A, B, C, and D do not have scores of 1 only because the common-relationships-list does not yet have a property indicating size, The reason is that there fs no size common to more than half of the currently possible group members, A, B, C, 0, E, and F.

The much lower scores of E and F reflect the additional fact that as wedges they are different from the standard type. They are immediately eliminated according to the following general rule:

Eliminate all candidate objects whose similarity scores are less than 90% of the best score any object attains,

This insures that the group will have members all with a

nearly equal right to belong,

Next the process is repeated because those properties

common to the remaining candidates may differ from those properties common to the original group enough that one or more changes should be made to the common-relat ionships-list. This repetition continues until the elimination process fails to oust a candidate or fewer than three candidates remain. After the first elimination of objects leaves A, B, Cy and 0, there is a new common-relationships-list: common-relationships-list: 1 SUPPORTED-8Y pointer to G 2 MARRYS pointer to G 3 &#-KIND-OF pointer to BRICK 4 HAS-PROPERTY-OF pointer to MEDIUM-SIZE Notice that there is now a size property since three of the four remaining objects have a pointer to medium size. The

new comparison scores are:

A versus the common-relationships-list --> 4/4

B versus the common-relationships-list --> 4/4 C versus the common-relationships-list --) 4/4 = 1 D versus the common-relationships-list --) 3/5 = .6 This time 0 is rejected because its uncommon size causes a low score, leaving a stable group in which the objects are

all quite like one another.

3.3 Other Kinds of Grouping

There obviously cannot be a single universal groouping procedure because attention must be paid not only to the scene involved, but also to the needs of the various programs that may request the grouping activity. 1 have discussed two grouping modes that programs can now do in response to various demands, There remain many others to be explored,

One of these involves looking for things that fit together, Children frequently do this at play without prompting, amd adults do it extensively in solving jiasaw puzzles.

Another kind of grouping, one particularly sensitive to the goals of the request, is grouping on the basis af some specified property. The idea is to pick out all things satisfying some criteria, such as all the biq standing bricks. The result could be a focusing of attention,

Still another way to group involves overall properties that are not obvious from purely local observations, Techniques here are again largely unexplored, but it seems that overall shape can sometimes impose unity on a complete hodge-podge, Figure 3-12 illustrates this point. All of the objects fit together to form a brick-shaped aroup. This is clearly not inherited from any consistency in how the

parts are shaped or how they interact with their immediate

3.4 Describing a Group: The Typical Member

neighbors,

The machine needs some means of describing groups. The method it uses seems to work, but there is room for improvement.

First, the parts of the group are gathered together under a node created specifically to represent the group as a conceptual unit. Figure 3-13 illustrates this step for a group of three objects, A B and C,

Next comes a concise statement of what membership in the group means, This is done through the use of a typicalmember nade, Properties and relations that most of the group members share contribute to this node's description. If some group were composed of three standing bricks arranged in a tower, then the result would be the description shown in figure 3-14, The typical member is there described as a kind of brick, as standing, and as on top of another member of the group. Notice also the FORM pointer to SEQUENCE which

indicates the kind of group formed.

A-Kind-Of

One-Part-I5

FIGURE 3-13

Eroup-members

Supported-Ey Form

Has-Property-Of A-Kind-Of

FIGURE 3-14

4 Similarities and Differences

4.1 Network Matching

Powerful scene description programs are essential to scene comparison and identification, Matching is equally important since the machine must know which parts of two descriptions correspond before it can compute similarities and differences. Figure 4-1 briefly illustrates, A process explores the two descriptive networks and decides which nodes of the twe best correspond in the sense that they have the same function in their respective networks, The nodes in a pair that so correspond are said to be linked tao each other, The job of the matching program is simply to find the linked pairs. Node LC and node RC in figure 4-1 both have only A- KIND-OF pointers to BRICK, Since no other nodes have similar descriptions, it is clear that LC and RC should be a linked pair. Similarly, L& and RB should be a linked pair since both have A-KIND-OF pointers to WEDGE and both have SUPPORTED -BY pointers to parts of a pair of nodes already known to be linked.

Of course the job of the matching program is not so easy when the two scenes and the resulting two networks are not identical, In this case the process forms linked pairs involving nodes that may not have identical descriptions, but

seem most similar nevertheless. More details are described

Linked

+#—-----------+3

— One-Part-1Is

Supported-

A-Kind-Of

FIGURE 4-1

4.2 The Skeleton

in the appendix,

Gnce the matching process has examined two networks and has established the linked pairs of nodes, then description of network similarities proceeds, The result is simply a new chunk of network that describes those parts af the compared networks that correspond. This chunk is called the skeleton because it is a framework for the rest of the comparison description. As figure 4-2 suggests, each linked pair contributes a node to the skeleton, Certain pointers connect the new nodes together. These occur precisely where the compared networks both have the same pointer from one member of some linked pair to a member of some other linked pair. Notice that the skeleton jis basically a copy of the structure that the compared networks duplicate,

4.3 Comparison Notes

Complete comparison descriptions consist of the skeleton together with a second group of nodes attached to the skeleton like grapes on a arape cluster, Each of the nodes in this second category is called a c-note, short for

comparison note, The most common type af c-note 15 the

intersection c-nate which describes the situation im which both members of a linked pair point to the same concept with

the same pointer. Suppose, for example, that a pair of

4+—— from linked pair LA - BA

One-Part-Is

Supported-By

KR from linked pair LC - REC

from linked pair LE - RB

FIGURE 4-2

corresponding objects from two scenes are both wedges, Then both concepts exhibit an A-KIND-OF pointer to the concept WEDGE. (figure 4-3) In English one can say:

1, There is something to be said about a certain

linked pair.

There is an intersection involved,

The associated pointer is A-KIND-OF,

The intersection occurs at the concept WEDGE,

Figure 4-4 shows how each of these simple facts translates to

aonetwork entry. First, a pointer named C-NOTE extends from the skeleton comcept corresponding to the linked pair to a new concept that anchors the intersection description, The A-KIND-OF pointer identifies this concept as a kind of intersection, Finally other pointers identify the pointer, A-KINO-OF, and the concept, WEDGE, associated with the intersection,

All of the c-notes look like this intersection paradigm,

3.1 Digression: Evans’ Program

Embodying difference descriptions in the same network

format permits operation on those descriptions with the same network programs. Thus two difference descriptions can be

compared as handily as any other pair of descriptions,

Those familiar with Tom Evans’ vanguard program, ANALOGY

[4], can understand why this is a powerful feature, rather

Linked

Gee e ene?

FIGURE 4-3

Intersection

Pointer-Destination

FIGURE 4-4

than simply a contribution toward memory homogeneity. Evans' program worked on two dimensional geometric figures rather than drawings of three dimensional configurations. Nevertheless his ideas generalize easily and fit nicely into the vocabulary used here.

Figure 4-5 suggests the standard sort of intelligence

test problem involved. The machine must select the scene X which best completes the statement: A is to Bas C is to Xx, In human terms one must discover how B relates to A and find an X that relates to C in the same way,

Using the terminology of nets and descriptions, one solution process can be formalized in the following way: First compare A with B and denote the resulting comparisondescribing network by

d[A:8].

Similarly compare C with the answer figures generating descriptions of the form d[C:X]. The result is a complete set of comparisons describing the transformations that carry one figure into another. Next one should compare the description of the transformation from A to B, d[A:8], with the others to see which is most like it. The best match is associated with the best answer to the problem, If M is a metric on comparison networks that measures the difference

between the compared networks, one can say

Three

choose X such that M(d[d[4:8):d[0:x%]]) is minimum

The metric Iuse is not fancy. It is the one discussed later in chapter 7 that serves to identify some scene with some member of a group of models, It! works because that problem entirely parallels the problem of identifying a given transformation description with some member of a group, The identification program, together with a short executive routine, handles the problem of figure 4-5 easily, correctly reporting scene three as the best answer. Reasonably enough, the machine thinks scene one is the second best answer,

The machine does as well on the slightly altered problem in figure 4-6, reporting four as the best answer,

Of course if the machine's answers are to be those of the problem's formulator, then the machine's describing, comparing, and comparison measuring processes should all give results that resemble his, Moreover, a really good analogy program should have available alternatives to its basic describing, comparing, and comparison measuring processes, Then fn the event no single answer is much better than the others, the program can try some of its alternatives as one or more of its basic functions must not be operat ing

according to what the problem maker intended, Evans' program

is superior ta mine in this respect because it can often compare two drawings in more than one way, It can visualize the change in figure 4-7, for example, as either a reflection or any one of several rotations,

Given my formulation of the analogy problem, it is easy to see how certain interesting generalizations can be made, After all, once an X is selected, the network symbolized by d(d[AsB)id[C:X]] describes the prohlem, and as a description, it can be compared with the descriptions of other problems, By thus applying the comparison programs for the third time, one can deal with the question, Analogy problem alpha is most like which other analogy problem? Alternatively, one can apply the analogy solving program to problem descriptions instead of scenes and answer the question, Analogy problem alpha is to analogy problem beta as analogy problem gamma is to which other analogy problem? This involves four levels of comparison, But of course there is no limit, and with time and memory machines could happily think about extended analogy problems involving an arbitrary number of comparison levels,

$.3.2 Another Digression: Newell, Shaw, and Simon's Program

A-classic piece of work in artificial intelliaence is

that of Newell, Shaw, and Simon on the scheme known as the

General Problem Solver, always abreviated GPS [5]. One form

Ll. — /

FIGURE 4-7

of GPS provides another example of how comparisons may be usefully compared with other comparisons.

From an abstract point of view, GPS involves the notion that problems may be thought of in terms of some solution or goal, G, together with a current state C, Additonally there are operators, O(i}, that convert classes of states into others. One may abreviate their action by writing

O(i):F-IN(i) --> F-OUT(i), meaning that operator O(i) tends to convert states of the form F-IN(i) into states of the form F-OUT(i).

GPS notices the difference between the current state C and the desired state G and then tries to apply an operator relevant to reducing that difference, This oroduces a new current state somewhat closer to the desired state. Applying this process iteratively, GPS may eliminate the difference between C and B, thereby solving the problem,

In early versions of GPS the programmers supplied a table giving the relevant operations for all the differences between C and G that might be observed. But Jater on Newell described an approach [6] that I think may be more transparently represented using the same motions of second order comparison minimization that is useful in discussing analogy problems. The idea is that the operators, O(i), may

be described by the difference between their input and output

forms, d[FeIN(G):F-QUT(i)]. Then Newell feels it is heuristically sound to apply the operator whose description is most like the difference between the current and desired states, d[C:G], One can say more formally, choose the operator O(7) such that M(d(d[F-IN(G):F-OUT(4)]:d[C:6]]) is minimum,

Notice that the selection of an operator fs curiously like solving an analogy problem for which one chooses a pair, (M(i),¥Ci)) from a set of offered pairs that beast completes the statement: A is to B as X(i) is to ¥(i}.

4.4 4 Catalogue of C-note Types

4.4.1 The Supplementary-pointer

Consider the scenes in figure 4-8 and their descriptions in figure 4-9. Scene L has the pointer SUPPORTED-BY between LA and LB, but scene R does not have a pointer between the objects linked to LA and LB. The note describing this situation is called a supplementary-pointer c-note and has the form shown in figure 4-10,

Figure 4-1] suggests a related situation, Here the

linked concepts Land R differ only in that L has an

Scene L Scene R

FIGURE 4-8

Supported-Eby

Scene L Scene R

FIGURE 4-9

C-Note

A-Kind-Of _- Left-Fointer

Supplementary -Pointer-

¢ _ Supported-By

Pointer-Destination

FIGURE 4-10

FIGURE 4-11

additional pointer identifying it as standing, This differs from the supplementary-pointer case in that STANDING is not linked to anything in the other scene, A pointer to the concept EXIT signals this situation. (figure 4-12) Exits involve concepts generated by the scene description program as well as concepts like STANDING that reside in the net permanently, If one scene contains more objects than another, the concepts left over and not matched end up in exit packages. .4.2 Pointer Modifications

Suppose the networks in figure 4-13 are compared, Notice the MARRYS pointer between LA and LB and the OOES-N0T- MARRY pointer between RA and RB, These could be handled individually as unrelated supplementary-pointer c-notes, but this would ignore the close relationship between MARRYS and DOES-NOT-MARR Y, Consequently a different type of c-note is used that recoqnizes the relationship. It is the negativesatellite-pair c-note. With it, the comparison looks as shown in figure 4-14, To find such negative-satellite-pair c-notes, the comparison programs peruse the descriptions of unmatched pointers between linked pairs for evidence of relationship. For example, NARRYS is described in part by a NEGATIVE-SATELLITE pointer to UOES-NOT-NARRY, Now of course

there are other pointers that are also just one step removed

C=Note

A-Eind-Of

Has-Property-Of

“ Polnter-Destination

FIGURE 4-12

Negative-Satellite

Modification-Of

FIGURE 4-13

Right- Pointer

A-KIND-OF uo BEET: POTNTER

Pointer-Destination

FIGURE 4-14

from a basic relation. All such pointers that are modifications of the basic relation are called satellites because they cluster around the basic relation to which they are attached by the pointer MODIFICATION-OF. Uncertainty, for example, is expressed by PROBABLY satellites or MAYBE satellites, The MUST satellites and the MUST-NOT satellites are others of particular importance in model construction. These inform the model matching programs that the presence or absence of some pointer is vital if some unidentified network is to be associated with a particular model network containing such a pointer. Figure 4-15 shows some of the satellites of MARRYS.

Each type of satellite is associated with a type of cnote forming an open ended family. Thus in addition to negative-satel lite-pair c-notes, there are probabl ysatellite-pair c-notes, maybe-satellite-pair c-notes, mustsatellite-pair c-notes, must-not-satellite-pair c-notes and so on,

4.4.3 Concept Modifications :

Frequently the members of a linked pair both have pointers to closely related concepts. For example, if a brick in one scene is linked to a cube in another, the situation is as shown in figure 4-16, This is very much like

the pointer-satellite idea with A-KIND-0F replacing

Probably -Mabries

Pl = Maybe-Satellite

P2 = Probably-Satellite

P3 = Negative-Satellite

P4 = Must-Be-Satellite

Bs = Must-Not-Be-Satellite

FIGURE 4-15

A-Kind-Of —

FIGURE 4-16

- G-Note

A-Kind-Of

Left-Destination Right-Destinat Ion

FIGURE 4-17

MNODIFICATION-OF. In any case, the description generator recognizes this and similar situations and again generates a group of c-note types. The first of these is the A-KIND-OF chain illustrated by the above situation, This causes the cnote of figure 4-17.

The a-kind-of-chain c-note also includes situations in which one concept is related to another not directly, but rather through two or three A-KINO-OF relations, Suppose, for example, a cube is linked with an object for which no identification can be made, There is still an a-kind-ofchain c-note because cube is linked to the general concept, OBJECT, by a sequence of A-KIND-OF relations. (figure 4-18)

Another kind of ponular concept modification is the akind-of-merge c-note, These a-kind-of-merge c-notes occur if there is no A-KINO-OF chain as described above, but each concept has a chain of A=-KIND-OF pointers to some third concept, For example, WEDGE and BRICK are both connected to

the concept, OBJECT, by A-KIND-OF. (figure 4-19)

A-Kind-Of

Brick

FIGURE 4-18

FIGURE 4-19

5 Learning and Model Building

5.1 Learning

§ Learning and Model Building

In this chapter I discuss learning to recognize simple block configurations, Although this may seem like a very special kind of learning, I think the implications are farranging.

It is possible to assuime extreme positions on the subject of learning. One person may think learning to do things is very complicated, while learning to recognize things is comparatively simple, because one merely aquires templates or some such, Conversely, another nerson may think learning to do is simple, but learning to recognize involves deep Gestaltist problems of synthesis or other imped imenta,

My opinion is that learning by examples, learning by being told, learning by imitation, learning by reinforcement and other forms are much like one another.

In the literature there is frequently an unstated assumtion that these various forms are fundamentally different. But I think the classical boundaries between the various kinds of learning will disappear, once superficially different kinds of learning are understood in terms of processes that construct and manipulate descriptions, No kind of learning need be desperately complicated once the

descriptive machinery is available, but all constitute

opaque, intractable processes without it.

Then once the problem of using descriptions is thoroughly understood, it will be possible to give meaningful thought to a deeper problem, that of learning to use descriptions, It does not seem simple, but using this point of view, it seems less than impossible.

The notions of learning and teaching are broad and confused, Generally, people think of these things as occurring together, so that whenever something learns, something else teaches. Gut somehow intuitive notions fail when it comes to thinking about machines, Computers can now play tolerable and improving chess and do marvelous symbolic integrations. Yet while people freely use the word "teach" in descriting what the programmers do, hardly anyone thinks of the machine as learning,

The reason seems to be that the human programmer has supplied so much detail that the machine 1s more a mimic than a thine with learning ability. The machine acquires its skill without ever really knowing what ifs going on or how it might improve without the laborious services of an information processing surgeon, The unfortunate machine is in the position of school pupils who know facts and perhaps memorize simple algorithms, but are never programmed to learn. The programs to be discussed here are an effort to show that a machine can do better and can learn in a realistic sense, given a chance.

5.2 Descriptions and Models

I want to make a clear distinction between a description of a particular scene and a model of a concept. A model is like an ordinary description in that it carries information about the various parts of a configuration. But a model is

more in that it exhibits and indicates these relations and

properties that must and must not be in evidence in any example of the concept involved.

Suppose, for example, the description generating programs report the following facts in connection with the arch in figure 5-1:

Qbject A is a brick, 2, Object A is supported by B and C,

Now suppose the description containing these facts were compared with the scene in figure 5-2, where object A is a wedge, and with the scene in figure 5-3, where object A lies on the table. In both cases comparison could te made and differences appropriately noted, but the identification of one or the other of these mew scenes as arches would be risky indeed because so far the machine knows only what one arch looks like without knowing what in that description is important!

Humans, however, have no trouble identifying the scene in figure 5=2 as an arch because they know that the exact shape of the top object in an arch is unimporta nt, On the other hand, na one fails to reject the scene in figure 5-3 because the support relations of the arch are crucial, Consequently, it seems that a description must indicate which relations are mandatory and which are inconsequential before

that description qualifies as a model. This does not require

FIGURE 5-1

FIGURE 5-2

FIGURE 5-3

any descriptive apparatus not already on hand, One need only substitute emphatic forms like MUST-BE-SUPPORTED-BY for basic pointers like SUPPORTED-BY or, in some cases, add new pointers. QDiscovering where and when to perform these operations can be somewhat involved, however, and requires the bulk of this chapter for discussion.

5.3 Examples, Near-misses, and Non-exanples

Suppose it is desirable to train a machine to recognize the letter 4 without restriction as to type size or font. The designer then has two sets of options: He must decide how his machine is to work; and he must decide what to show the machine. One idea is to show the machine vast numbers of As and hope that it will benefit from such an expertence by somehow noticing the features which apnear repeatedly, But this assumes that the frequently seen properties are essential ones, which can be a bad rule. Moreover, there is little possibility for skillful teaching, There is no obvious way the teacher could quickly convey a particular idea such as the notion that the crossbar of an A is important, even if the teacher realized it. Finally, such samples generally only suagest properties a candidate for match should have -- it is hard for them to indicate forbidden properties.

This is true because expert description programs

would be needlessly overburdened and would promote

confusion if they were always to indicate all neaative

properties and those not observed, Therefore a

property's consistent absence can be easily overlooked,

If the description program does list all properties in

spite of inefficiency, then many properties are .

statistically likely to be missing fram a short training

sequence, But the statistic-gathering machinery would think such properties should not be present in examples of the model, even though their absence was by

coinc idence,

One might attempt to train basically the same machine to handle a whole repertoire of concepts by showing examples of each member, Thus if the repertoire were the alphabet, examples of all the letters would be shown, rather than just As, This shifts the question to Which description does an unknown best match? It still avoids the more fundamental question, What is it about each character that is essential and permits it to be recognized? The machine now may use fs and non-/s, but the difficulties are only obscured, not circumvented, There remains no way to directly convey an idea, and there remains the fallacy that frequent appearance means importance. The problem of indicating what properties preclude identification with a particular model is only tangentially and occasionally addressed in that sometimes a property converts one description into another, as in the case of adding a forbidden midline crossbar to a C. The

machine does not know a C cannot have a crossbar; it only

knows such a crossbar makes a figure more like an E.

In my judgement, near misses are the really important examples in learning. In conveying the idea of an arch, an arch certainly should be shown first. But then there should be some samples that are not arches, but do not miss being arches by much, Small differences permit the machine to localize some part of its current opinion ahout a concept for improvement. If one wants the machine to learn that the uprights of an arch cannot marry, one should show it a scene that fails to be an arch only in this respect. If the machine is to know a C cannot have a crossbar, it should see a character that fails to be a C only because of a crossbar, Such carefully selected near misses can suggest to the machine the important qualities of a concept, can indicate what properties are never found, and permit the teacher to convey particular ideas quite directly.

It is curfous how little there is in the literature of machine learning about mechanisms that depend on good training sequences. This may be partly because previous schemes have been too inadequete to bear or even invite extensive exploration of this centrally important topic. Perhaps there is also a feeling that creating a training sequence is too much like direct programming of the machine to involve real learning, This is probably an exaggerated fear, I agree with those who believe that the learning of children is better described by theories using the notions of programming and self-procramming, rather than by theories advocating the idea of selforganization, It is doubtful, for example, that a child could develop much intelligence without the programming implicit in his instruction, guidance, closely supervised activity, and general interaction with other humans.

5.4 Model Development

The machine's model building program starts with a description of some example of the concept to be learned, This description is itself the first model of the concept. Subsequent samples are either examples of the concept or near misses, These examples and near misses reveal weaknesses and lead to a new models, Section 5.5 shows in some detail how the comparison between the current model and the description of a new sample produce a new model in the case where only one difference is found,

One then has a sequence of more and more sophisticated models, See figure 5-4, Frequently, several responses may appropriately address the comparison between the current model and a new sample. When this happens, branches occur in the model development sequence and it is convenient to talk about a tree of models. Figure 5-5 shows such a tree, Section 5.6 discusses how the alternative branches come about. The machine selects one branch at each point for further development, The meandering path leading from the top of the tree down to the current model is called the main line, The main line changes course when a particular sequence of branch selections leads to untenable situations,

Section 5.7 describes how and when this happens.

Example

—— First Model

Sample 1

—— Second Model

Sample 2

—— Third Model

Sample 3

—— Fourth Model

FIGURE 5-4

First Round Model

——— Second Round Models

Third Round Models

Fourth Round Models

FIGURE 5-5

5.5 The Elementary Model Building Operations

This section considers the case in which the matching program finds only one difference between the current model and a new example or near miss. The table at the end of this section summarizes the results,

5.5.1 The A-kind-of-merge: Current Model and Example

First consider the model and example in figure 5-6,

Figure 5-7 shows the resulting comparison description, Only

one difference is found: the object of the model points to BRICK while the object of the example points to WEDGE, Sut since both BRICK and WEDGE relate by A-KIND-OF to OBJECT, the a-kind-of-merge c-note occurs. Several explanations and companion responses are possible. One is that the source of the c-note may in general point to either of the things pointed to by the A-KIND-OF pointer in the two scenes. Thus the object could be either a WEDGE or a BRICK. Another possibility is that the A-KINO-OF pointers from the object do not matter at all and can be dropped from the model, Still another option and the one preferred by the program is that the object may be any member of some class in which both WENGE and BRICK are represented. In the example one such class is simply the concept OBJECT and has already been located as the intersection of A-KIND-OF paths. The program

responds by replacing the pointer in the comparison network

Current Model Example

FIGURE 5-6

A-Eind-Of

A-Kind-Of

Merge

- Pointer

Left-Destination Right-Destination

FIGURE 5-7

that points to the a-kind-of-merge c-note by an A-KINO-0F pointer to the intersection or merge concept. In this case an A-KIND-OF pointer is installed between the c-note origin and the concept OBJECT, Then the altered comparison network is the new model shown in figure 5-8,

The primary response I have selected for the machine represents a moderate stand with respect to a rather serious induction problen, I could have been more conservative and used an A-KIND-OF pointer to a concept representing the ordinary O% of BRICK and WEDGE, On the other hand, I could have been far more radical by pointing the A-KIND-OF pointer to THING, the universal class, “y actual choice of pointing to the node indicated by the merge concept to be the intersection of A-KINO-OF chains seems more flexible than either of the extreems,

Since the merge concept is itself defined in terms of the metwork's content, the generalizations made will change as the net grows, Cut since the appropriate response should after all depend on the universe the machine is operating in, the generalization changes are likely to be improvements, Amd in any case this commitment is only one among many,

5.5.2 The Supplementary-pointer C-note

Now suppose scene 1 in figure 5-9 represents the current model while scene 2 contributes as a near miss. The matching routine soon discovers that scene 1 produces a SUPPORTED-B8Y relation between the two objects whereas scene 2 does not, A supplementary-pointer c-note results. Of course the implication is that the concept studied requires the two abjects to stand tonether under the support relation,

Consequently, when such a supplementary-nointer c-note turns

One-Part-I5

q A-KIND-OF

Object

FIGURE 5-8

Scene 1 Scene 2

FIGURE 5-3

up, it transforms to the emphatic MUST version of the pointer involved, Thus the new model is the one in figure 5-10,

Of course the supplementary pointer can turn up in the hear miss as well as in the current model. Suppose scene 1 in figure 5-9 is the near miss instead of the current model, One concludes A cannot be on 6, The supplementary-pointer cnote now indicates a relation that apparently cannot hold. Appropriately, the MUST-NOT version of the supplementary pointer is substituted in and the new net appears as in figure 5-11,

5.5.3 The Must-satellite-pair C-note

Frequently comparison between the current model and a new sample displays c-notes that do not reveal any new feature, but rather result because of previous refinements in the model. Suppose, for example, that the current model has a MUST-MARRY pointer in a given location, while the sample has a MARRYS pointer, Now clearly the MARRYS pointer is appropriate in the description and the must-satellite-pair cnote consequent to matching it with MUST-MARRY should be replaced again by MUST-MARRY, Thus the emphatic form in a must-satellite-pair situation is retained and not interfered with by refinement operations attempted subsequent to its

formation,

‘One-Part-15

Must-Be~-Supported-By

FIGURE 5-10

—— One-Part-15

Must-Not-Be-Supported-By

FIGURE 5-11

5.5.4 The A-kind-of-merge: Current Model and Near Miss

Sometimes a c-note offers two or more nearly equal explanations. Consider the super simple current model and near miss in figure 5-12. The c-ncte is an a-kind-of-merae announcing that the current model points with HAS-PPOPERTY-OF

to STANDING, the near miss to LYING, and both LYING and STANDING have A-KIND-OF paths to ORTENTATIONS, How the near miss may fail either because it is lying or because it is not standing. Responding to these explanations, the model builder might replace the a-kind-of-merge c-note by a MUST - NOT-HAVE-PROPERTY-OF pointer to LYING or by a MUST -HAVE= PROPERTY-OF pointer to STANDING, Since most concepts humans discuss are defined in terms of properties rather than anti-

properties, the MUST version is considered more likely,

Current Model Near-Miss

FIGURE 5-12

Table

Action Of Concept Generator; Example Case

c-note type

a-kind-of-chain

a-kind-of-merge

negative-satel lite

pair

mus t-be-satel lite pair

mus t-not-be satellite pair

Supplementary-pointer or exit

pointer invalyed

negative-satellite or fundamental pointer in the model

negative-satellite or fundamental painter in the example

must-be-satellite

must-not-be-satellite

response

point to intersection with model's pointer

point to intersection with model's pointer 2. drop model's pointer drop model's pointer retain model's pointer

contradiction

drop model's pointer

ignore

contradiction

retain model's pointer

TABLE (cont.)

Action Of Concept Generator; Near Miss Case

c-note type

a-kind-of-chain

a-kind-of-merge

negative-satel lite pair

must-not-be-extension pair

supplementary-pointer

pointer involved

fundamental pointer in the model

fundamental pointer in the near miss

negative-satel lite in the model

negative-satellite in the near miss

response

1, if model's node is at the end of the chain add must-not-be satellite 2, if near miss' node is at the end of the chain, use must-be satellite to model's node

replace model's pointer by its must-be satellite

replace model's pointer by must-not-be satellite of near miss' pointer

replace model's pointer by its must-be satellite

retain model's pointer

replace pointer with its must-be satellite

insert pointer into the using must-not-be satellite

replace pointer with its must-not-be satellite

insert pointer into model using must-be satellite

5.6 Multiple C-notes

Comparisons yielding sinnle c-notes are rare, More often, the model builder must make sense out of a whele group of c-notes, If the comparison involves a near miss, any one of the c-notes might be the key to proper model refinement, Moreover, many of the c-notes have alternative interpretations that make further demands on executive expertise,

The model builder must therefore consider the c-notes and all the possible interpretations of each, Then it must produce the set of hypotheses that form the model tree's branches, These in turn must be ranked so that the best may be pursued first.

The case of refinement through an example is simpler than through near misses, Since none of the observed differences are sufficient to remove the example from the class, it is assumed that all of the differences found act in concert to loosen the definition embodied in the model, Censequently each c-note can be transformed independently and a new model qenerated by their combined action, There is no problem of deciding if one difference is more important than another,

Consequently, if all the c-notes had but one

interpretation, only one new branch would be oenerated., The

a-kind-of-merge c-note has three possible interpretations, however, and if ome such c-note occurs, it is only reasonable to create three branches instead of just one, The action an the other cenotes is the same for ell three branches.

Near misses cause more severe problems, If two differences are found, either of them may be sufficient to cause the sample to be a near miss, while the other difference mav be equally sufficient or merely irrelevant.

If the differences have multiple interpretations or more than two differences occur, the number of possibilities explodes and the machine cannot work simply by generating an alternative for each possibility.

The model builder clearly must decide which interpretation of which differences are most likely to cause the near miss.

The machine first forms two lists: a primary list and a secondary list. Each c-note eventually ends up in one Vist or the other.

Now some c-nates can never make the primary list because they are of themselves insufficient to explain why a given sample is a near miss. All of these go immediately to the secondary c-note list. ne example is the situation in which a pointer in the near miss corresponds in the current model

to an instance of the MUST-SATELLITE version of the peinter,

A must-satellite-pair c-note results but certainly is no grounds for excluding the near miss from the class since the required pointer is in fact present, Some other explanation must be found.

The next and most obvious way to sort differences is by level, This assumes only that the differences nearer the origin of the comparison description are the more important, This certainly is a reasonable heuristic since a missing group of -locks generally impresses a human as being more important than a shape change, which in turn dwarfs a minor blemish. Consequently, the program determines the depth of the remaining c-notes which are nearest the oriqin of the comparison description. All those candidates found at greater depth are relegated to the secondary list.

The primary c-note list allows quick formation of little theories about why the near miss misses and what to do as a consequence. These theories are called hypotheses. A complete hypothesis specifies one c-note as the sole cause of the miss and it further specifies which interpretation of that c-note is assumed. Consequently there is a hypothesis for each interpretation of each c-note on the primary list.

The c-note specified as crucial by a hypothesis is transformed as if it were the only cenote., The other c~-

notes, both on the secondary and primary lists, are assumed

by the hypothesis to be insufficient cause for the near miss. Consequently as a new model is formulated according to the

hypothesis, all of the c-notes but one are treated exactly as

if the near miss were not a miss at all!

So far a single c-note is assumed to be the exclusive cause of the miss, Were all possible combinations considered as well, not only would the branching increase enormously, but the ranking of those branches would be difficult, Rather than face this, I have decided that only one special combination of two c-notes is ever permitted to form a

hypothesis,

In this I have exercised what one micht call the first heuristic of science: FEenqin with the linear model, the one that assumes all thinos act independently: then consider interactions as necessary, I next discuss a particular case in which it does seem necessary to consider the joint action of two differences, It would be unreasonable, however, to try for a general method for handling multiple differences, In science as a whole, each particular method for treating interacting effects is usally a major problem in itself and over-ambitious search for completely general methods is of law utility when premature,

Further justification for my appproch lies in certain observations of Piaget's that indicate that children seem to pay sharp attention to only a single feature at any one time [3]. In comparine volumes, for example, they use mainly height. Yet, in spite of using what appear to be linear comparisons, these same children can learn physical concepts with a talent far in excess of my goal for this thesis,

Hypotheses based on two contributing c-notes are added

to the hypothesis list only when two c-notes with nearly

identical descriptions occur, Consider figure 5-13, Since exactly the same thing characterizes both blocks in the near miss, there is no particular reason to suppose that one difference should be singled out. Consequently a third hypothesis is formed, namely that both differences act cooperatively. This additional hypathesis takes precedence over the two hypotheses that consider the differences separately, It seems heuristically sound that coincidences are significant. The machine creates new models with such hypotheses by transforming both of the specified c-notes in the miss-explanation mode,

5.7 Contradictions and Backing Ip

Cy now one may wonder why the prooram should deal with alternatives to the main line of model development at all, To be sure, maxinum likelihood assumptions may be wrong, but then how could the machine ever know when such a decision is an error? The answer is that the main line assumptions may lead to contradiction crises which in turn cause the model building program te retreat up the tree and attempt model development along other branches,

Consider again the very simple situation presented in figure 5-14, The current model and the near miss combination generate an a-kind-of-merge c-note for which the

priority interpretation is that examples of the cancept must

TO) ex

Current Model Near-Miss

FIGURE 5-13

Current Model Near-Miss.

FIGURE 5-14

FIGURE 5-15

be standing, The alternative, that examples must net be lying, causes a side branch in the model development tree, But suppose one really wants the concept to exclude Tying but not insist on standing. Showing the machine the example in figure 5-15 does the job, The tilted trick certainly fs not standing and its description has no HAS-PRCPERTY-OF pointer to STANDING, Yet the current model has a “IUST-HPVE-PROPERTY- OF painter to STANDING. This is a contradictory situation,

When contradictory situations occur, the program assumes it has made an incorrect choice somewhere, closes the branch to further exploration, and backs up one level to select another alternative if any are available there, If no alternatives are available, the program backs up still more Jevels until either an unexplored alternative is found, or the top level is reached. If the top level is reached with no other options found, the program succumbs and admits failure. More often an acceptable unexplored alternative fs soon found and an effort is made to extend the model tree down that branch, Of course, the first alternative a contradiction causes to be explored may itself lead to contradiction, Sack up then starts from the new contradiction and proceeds as before.

In the case at hand, an alternative is found and the

must-not-be-lying interpretation of the comparison between

the scenes in figure 5-14 leads to a new intermediate model. This in turn is refined by the scene of figure 5-15 which originally caused the contradiction on the former main line. fia cantradiction occurs on the new path because the “UST-NOT- HAV E=PROPERTY=OF = LYING combination of the intermediate model has nothing to clash with in the example, Indeed the new example lends no new information to model development along this path, the model being the seve before and after comparison, The new example served solely to terminate development of an improper path in the model development tree,

5.8 Other Backing Up Possibilities

Many possible refinements to the elementary backina up procedure invite attention. For one thing there are other reasons why the learning program might want to back up. In addition to the situation of direct contradiction, attention should move back up the model tree if there are so many differences between the current model and the sample that hopeless confusion is suggested. The cause of such confusion is likely to lie in the selection of a wrong branch at some higher point in the model tree. Similarly retreat is in order if the program is forced to propose an unlikely explanation te account for observed differences,

Right now the learning program backs up level by level,

blindly exploring all possible paths from one branch point before backing up to the next higher branch point. It would be better if attention could move directly to the point in the tree where the problem beaan, There a better alternative could be elected and learning could more likely procede in an orderly way,

Certainly the selection of the appropriate paint is easy in the case of direct contradiction. As explained before, these situations occur when some relation is found to be essential at some point in model development only to be absent from some subsequent example of the concept. The crucial point is the place where the decision was made that the relation was essential, This is the point where

attention should qo and an alternative explanation should be

sought,

6 Some Generated Concepts

6.1 Physical Models and Functional Models

In this chapter I explore some of the properties of the model generator through a series of examples, In the course of this discussion, words like house, arch, and tent occur frequently as they are convenient names for the ideas the machine assimilates. Pe cautioned, however, to avoid thinking of these entities in terms of functional definitions, To a human, an arch may be somethina to walk through, as well as an appropriate alionment af bricks, And certainly, a fiat rock serves as a table to @ hungry person, although far removed from the image the word table usually calls to mind.

But the machine does not yet know anything of walking, residing, or eating, so the programs discussed here handle only some of the physical aspects of these human notions,

There is nothing mystical about this, There is no inherent obstacle forbidding the machine ta enjoy functional understanding. It is a matter of generalizing the machine's descriptive ability to acts and properties required by those acts. Then chains of pointers can link TABLE to FOOD as well as to the physical image of a table, and then the machine will be perfectly happy to draw up its chair to a flat rock with

the human, given that there is something on that table which it wishes to eat.

FIGURE 6-1

Near Miss

FIGURE 6-3

Near Miss

(Dx

FIGURE 6-2

Near Miss

FIGURE 6-4

One-Part=18

Supported-By

A-Eind-Of

FIGURE 6-3

One-Part-I5

———— A=-Kind-0Of

FIGURE 6-6

One-Fart-15

——Must-Be-Supforted-Ey

4-Kind-Of

FIGURE 6-7

Model L_ ————_

Model 2.6. —————————_

FIGURE 6-8

both of these steps cause bifurcation of the model tree, The reason is that the machine cannot be completely sure the miss occurs because the old praperty is lost or because the new property is added, The program prefers the old-pronerty-islost theory and moves down the corresponding branch unless contradicted, In both of these situations, the preferred theory is correct resulting in the final model and tree shown in fioure 6-9 and figure 6-10,

6.3 The Pedestal

Development of a pedestal model proceeds much as does the house with only two essential differences, First, the top object must be a brick rather than a wedoe, fecond, the upper object must not marry the lower, The scene in fioure 6-11 yields the starting model. Fiowre 6-12 forces the top cbiect to he a brick while fioure 6-13 forces the bottom object to be a brick as well. Finure 6-14 emphasizes support. And finally, fioure G-15 forbids the “ARRYS relation,

&.4 The Tent

Think of the tent as two wedoes, marrying each ather. As such it illustrates the handlina of two similar differences simultaneously.

Suppose the base model is the description of the scene

in fiqure 6-16 and the first sample is the near miss in

One-Part-I5

—— Must-Be-Supported-By

Must-Be-A-

Eind-Of

FIGURE 6-9

Model 1

Model 2

Model 3

MODEL 4 ee

FIGURE 6-10

FIGURE 6-11: PEDESTAL

Near Miss Near Miss

FIGURE 6-12 FIGURE 6-13

Near Miss Near Miss

FIGURE 6-14 FIGURE 6-15

FIGURE 6-16

Near Miss

FIGURE 6-17

Near Miss

FIGURE 6-18

la ONE~PART-18

FIGURE 6-19

Must-Be-A-Kind-Of J

FIGURE 6-20

FIGURE 6-21: ARCH

Arch Near Miss

FIGURE 6-22 FIGURE 6-23

Near Miss Arch

FIGURE 6-24 FIGURE 6-25

supplying two APRYS pointers to the description, This

cannot be allowed. Pesponding, the machine inserts MUST-NOT-

MARRY pointers between the two supports in the model,

Some may think that in asserting the MUST-NOT-"APRY

relations, the machine overlooks what they consider the real principle, that of a hole or passage, But for a child building with blocks, to have a hole and to have two non-touching supports are very nearly the same idea, Consequently the machine's opinion seems adequate for the moment. Experiments such as these may help to

expose exactly what kinds of network relations are adequate for a model of human thinking, from infant to

adult, Finally, the top object is not necessarily a brick, The

sample in figure 6-25 teaches the machine that anything in the class OBJECT will do, since OBJECT lies but one step removed by an A-KINU-OF pointer from both WEDGE and BRICK,

6.6 The Wedge

The capabilities of the model builder certainly extend beyond the level of object configurations, whose descriptions allow the machine to learn about scenes, Here the development of the wedge model illustrates the point.

Given the wedge in figure 6-26, the description

generated is that of figure 6-27, ext, comparison with a brick establishes a MUST-BE-/A-

KIND-OF pointer to TRIANGLE. (figure 6-28) But now suppose the partly occluded object in

figure G-29 is compared first with the current model of wedoe

FIGURE 6-26: WEDGE

A-Kind-Of

FIGURE 6-27

One-Part-15

FIGURE 6-28

FIGURE 6-29: NOT A WEDGE

Brick-Model

R = Rectangle

T = Triangle

FIGURE 6-30

— One-Part-Must-Be

A-Elnd-Of Must-Be-A-Kind-Of —

FIGURE 6-31

One-Part-May-Be

One-Part-Must-Be

A-Kind-Of ——

FIGURE 6-33

just refined the model, the one in fioure 6-29, the result is an exit c-note bearing an emphatic pointer, (lE-PART-MUST-FE, Such a c-note strongly suggests bad match to the evaluation Program, and the apparent inadequacy disappears,

The scene in figure 6-32 establishes a final refinement. This wedge shows only two sides, After a bit of thinking, the program decides one of the two rectangular sides is optional and produces its final model. (figure 6-33)

6.7 The Composite Calumn

When a concept involves groups of objects, the model generation problem really is no more difficult, It just becomes a matter of concentratina on relationships between the typical members of the groups studied,

Consider the notion of the composite column, hereafter referred ta simply as the column, Figure 6-34 shows such a column and fioure 6-40 shows part of the correspond ina descriptive network, This description is gradually transformed into a reasonable model in the following way:

Figure 6-35, with fits bricks askew but otherwise the

same, introduces the MUST-MARRY pointer, Fioure 6-36, made of wedges instead of bricks, relaxes the inclination toward bricks, And figure 6-37 causes replacenent of SUPPORTED-AY by AUST-BE-SUPPORTED-BY,

Wext, fiqure 6-38 contributes the most important part of

FIGURE 6-32: WEDGE

Column

FIGURE 6-34

Near Miss

FIGURE 6-35

Column

| Figure 6-36

Near Niss

FIGURE 6-38

Near Miss

FIGURE 6-37

Column

FIGURE 6-39

A-Kind-Of

MARRIES ~ x aeheRe . J

Supported-By

FIGURE 6-40

One-Part-Must-Be

Must-Marry H Number-Of-

° Members

Must-Be-Supported-By

FIGURE 6-41

FIGURE 6-42: ARCADE

A-Eind-Of

A-Eind-0F

Number-0F =

In-Front-0F Members

FIGURE 6-43

FIGURE 6-44: NEAR MISS TO ARCADE

FIGURE 6-45: NEAR MISS TO ARCADE

FIGURE 6-46: NEAR MISS TO ARCADE

Study the table in figure 6-47 and the description in figure 6-48, The essential features of the table are introduced by the following sequence of steps:

First the table should have bricks for legs, This idea is easily conveyed by the non-table of figure 6-49, Moreover, this conception of table excludes structures such as that in figure 6-50, a fact which is handily incorporated through a MUST-NOT-MARRY pointer, ext, since the non«table in figure 6-51 has only two supports, no grouping occurs, which leads to insistence on a groun in the next model refinement, This entirely parallels the process by which the column was found to involve a group, Finally, the scene in figure 6-52 leads to replacement of the SUPPORTED=BY pointer by MUST-BE-SUPPORTED-BY. Figure 6-53 shows the last model in this development.

6.10 The Arch in tupth

So far the illustrations have shown networks only to that depth appropriate for understanding, Figure 6-54 shows the model for the arch in somewhat fuller bloom and better indicates the breadth of the information available to

programs that use the model.

FIGURE 6-47: TABLE

One-Part-[5

Supported-By

A-Kind-Of ————— Has-Property-Of

FIGURE 6-438

Table Near Miss

FIGURE 6-49 FIGURE 6-58

Near Miss Near Miss

6 0Z/A

FIGURE 6-51 FIGURE 6-52

One-Part-I5

One-Part-Must~Be

A-Kind-Of

Hust-Be-

Supported-By

-— Has-Property-Of

Must-Not-Marry Must-Be-A-Kind-Of

FIGURE 6-53

vS-9 JYNdI4

SLITTaLVS

~Lon-Lsak

INdy¥-LON-LSnH

40-Noilvoiaigcon

Slittalys -49 -Lsak

40-ALY9d 0Ud -SVH

~H8-LSAn

40-dho#s

XN SI-LUVd -3N0

40-Nollvilaigor

7 Identification

7.1 Matching and Identification Alternatives

7.2 Exact Match

If two scenes are identical, then the networks describing those scenes must be isomorphic. The nodes of the two networks must relate with each other in the same ways, and the nodes must relate te general concepts such as BRICK and STANDING in the same ways, Consequently, comparing two such networks produces a simple kind of comparison description, There is a skeleton, which indicates how the parts of the scenes interrelate, and there is a group of intersection c-notes that describe how the parts of the scene are anchored to the general store of concepts. ilone of the other types of c-notes appear because identical scenes cannot produce two networks with the necessary aberrations of form,

Conversely, if comparison of two networks results in intersection c-notes only, then the parent scenes must be identical in the sense that the description generating mechanisns employed produce exactly matching networks, There can be variation, but nothing so great as to vary the action of the description cenerator., The scenes in ficure 7-1 are identical with respect to the descriptive power of my programs because in both cases the relations observed are LEFT-OF and RIGHT-CF. “ore capable programs might complain that FAR-TO-THE-LEFT-OF and FAR-TO-THE-RIGHT-CF hold in one

scene, while only LEFT-OF and RIGHT-OF hold in the other.

scene) ERE 8

FIGURE ?-1

FIGURE 7-3

FIGURE 7-4

In-Froni-0Of -—-——~,

Right-0F

FIGURE 7-5

In-Froni- Of

FIGURE 7-6

aa Ul we

oo WU as

Opposite

FIGURE 7-9

FIGURE 7-11

scene descriptions, One obvious ability of such a

program would be that of noticing a preponderance of

similar c-notes, I think that this and some of the double comparison ideas proven useful in doing analoaoy problems are just the things the machine needs to learn about symmetry.

7.4 Elementary Identification

Suppose a scene is to be identified, if possible, as a HOUSE, PEDESTAL, TENT, or ARCH, The obvious procedure is to match its description against these for each of the models and then somehow determine which of the four resultina difference descriptions implies the best match,

Recall that models generally contain must-be satellites and must-not-be satellites while ordinary descriptions do hot, Consequently, comparing an ordinary deserintion against amodel leads to a variety of c-notes not found when ordinary descriptions are compared, mong these are must-be-satell ite pairs, must-not-be-satellite pairs, and various flavors of exits and supplementary-pointers., “Such c-netes are decisive in the identification process,

Consider the case where some pointer in a scene's description corresponds to its must-not-be satellite in the model, This clearly means a relation is present that the model specifically forbids. The resulting must-not-be-

satellite-pair c-note in the difference network is such a

serious association impediment that identification of the

FIGURE 7-12

FIGURE 7-13

KIND-OF pointers lead to a common intersection. Figure 7-14 shows such a situation, In this case the unknown is a kind of wedge while the corresponding object in the model must be a kind of brick, Both WEDGE and BRICK are kinds of objects, which directly leads to a merge c-note associated with a MUST-BE-A-KIND-OF pointer in the model. But the fact that the unknown has a property in the same class as a property required by the model is insufficient. To insure reject ion of such matches, the rule is: Refuse identification if the model's pointer contributing to the merge c-note is a mustbe-satellite.

Figure 7-15 summarizes the procedure used on each c-

note.

Natch of the scene in fiqure 7-16 against the PEDESTAL, the TENT, and the ARCH all lead to difference descriptions with c-notes that forbid identification, The PEDESTAL fails because a merge indicates that the required A-KIND-OF relation between the top object and BRICK is missing, The TENT similarly fails because both of its objects must be wedges, The ARCH fails because the model has a MUST-BE- SUPPORTED-BY pointer to an object missing in the unknown, This in turn causes a fatal exit c-note in the difference

description,

Of course the machine can also match the samnle

Unenown Model

Must-Be-A-Kind-Of

— A-Kind-Of

FIGURE 7-14

Is C-Hote A

Must-Not-Be-

Satellite Pair?

Is C-Note A

Suppl Imentary -Pointer

Or An Exit?

Is C-Note An

A-Ekind-Of-Merge?

Is Model Pointer

Involved A

Must-Be Satellite?

No Cause Reject The Model-

To Reject No Identification

FIGURE 7-15

House Pedestal

FIGURE 7-16 FIGURE 7-17

Tent Arch

FIGURE 7-18 FIGURE 7-193

pedestal, tent, and arch of figure 7-17, figure 7-18, and figure 7-19 against the same list of models. It makes the correct identification in each case,

The next problem emerges because some unknown may acceptably match more than one model in a trial list,

Suppose one defines a new sort of arch that is just like the old arch except that the top object must be a wedge rather than just any object. Call this new model the WEOGE-ARCH, Then the scene in figure 7-20 certainly matches with both the ORDINARY-ARCH and the new WEDGE-ARCH, There is only one slight variation in the difference descriptions. In the WEDGE-ARCH case, one has a must-be-satellite-nair c-note because the unknown has an A-KIND-CF pointer to WEDGE and the model has a MUST-BE-A-KIND-OF pointer, In the ORD INARY-ARCH case, there fs simply an A-KIND-OF pointer from the model to OBJECT, which with the unknown's A-KIND-OF pointer to WEDGE forms an a-kind-of-merge c-note,

OF course there is nothing really wrang with report ing both OROINARY=ARCH and WENGE-ARCH as the identification of the unknown, Still, given several possible identifications, there should be some way of ordering them such that one could be reported to be best in some sense. Todo this I associate each kind of difference with a number and combine the numbers

te form a score for each comparison. Figure 7-21 shows the

FIGURE 7-28

—— Must-Be-Satellite-Pair

+—_ Intersect Ion

~—— A-Kind-Of-Merge Not Involving Any

Must-Be Satellites

<— 1. Must-Not-Be-Satellite Pair Of

2, Exit Or Supplementary-Pointer Involving

A Must-Not-Be Satellite

4— Exit Or Supplementary-Fointer Involving

No Satellites:

~<—— Negatlve-Satellite Pair

— A-Kind-Of-Merge Involving Must-Be Satellite

4— Exit Or Supplementary-Pointer Involving

Must-Be Satellite

4— Must-Not-Be-Satellite Pair

FIGURE 7-21

ra ra we

scale associating difference types with numbers, It evolves

heuristically from observations like the following:

The intersection c-note has an assiqned value of 1. This anchors the scale as all other numbers are fixed according to how good or bad the corresoonding c-note seems relative to the intersection c-note,

A must-be-satellite-pair c-note suggests qood match even more strongly than the intersection because it indicates that relations are present that are known to be essential, A value of 3 aives it three times the weight of a simple intersection,

Exit or supplementary-pointer c-notes that involve must-be-satellites are distinctively bad because they indicate vital preperties are missinn, The value is a damagine =5,

Other exit and supplementary-pointer c-notes are bad but not nearly so bad, A score of -2 seems about right,

‘tustenot-be-satellite pairs are very Fad evidence indesd, The worst score of -6 is deserved,

The a-kincd-of-merge is nesitive or negative depending on whether either of the pointers are must-be satellites, If a must-be satellite is involved, an important pronerty is missinn, resulting in a -4, Otherwise, it indicates lorse association, not as tight as that announced by an intersection, A .5 is usec,

Once differences are noted and number associations

are made, a program must combine the numbers in a

reasonable way, If SCORE[U:"] represents the score of

comparing unknown U against model “%, then I use

SCORELU:M] = WCTIN(1) # 4m )n(n) where

Wi) = expl-L{i}]

and

N(i) is the number associated with the ith difference,

Wi) is the weighting factor that reduces the influence of lower level differences,

L(i} is the level of the ith difference,

Combining the terms additively is convenient, and the weighting terms, the "s, handily reduce the influence of the lower level differences, IT have no stromoer reasons for using this linear formula, and it is not somethina to be defended to the death. Gut Ido not think it would pay to put much effort into tuning such a formula because more knowledoe about the priorities of differences should lead to far better programs that do not use numbers at all,

7.5 Identification in Context

Exanine figure 7-22, Notice that object & seems to be a brick while object 0 seems to be a wedge, This is curious because — and D show exactly the same arrangement of lines and faces, The result also seems at odds with the machine's models and identification process, as

described so far, because so far anything identified as a

f/f» £_/ cP oF

wedge must have a triangular face,

but of course context is the explanation. Different rules must be used when programs try to identify objects or groups of objects that are only parts of scenes, rather than the whole scene. In the case where the question is whether or not the whole scene can be identified as a particular model, it is reasonable to insist that all relations deemed essential by the model be present, while all those forbidden, be absent. But when the question is whether or not a few parts of a scene can be identified as a particular model, then there is the possibility that some important part may be obscured by other objects, In these situations, my icentification program uses two special heuristics:

First, the coincidence of objects lying in a line seems to suqgest that each object is the same type as the one obscuring it unless there i$ qood reason to reject this hypothesis. This is what suagests object D is a wedee in figure 7-22,

Second, essential properties in the model may be absent in the unknown because the parts involved are hidden. This is why identification of object D with wedge works even though 0 lacks the otherwise essential

triangular face, The requirement that forbidden

properties do not occur remains in force, however,

Elaborate work can be done on the problem of deciding if the omission of a particular feature of some model is admissable in any particular situation, My program takes a singularly crude view and ignores all omissions, Rejection of the hypothesis that the obscured is like the obscuror happens only if the machine notices details specifically forbidden by relations in the model. Thus the effort is not to select! the test matching model, but only to verify that a particular identification is not contradictory. This means that object EB in fiqure 7-23 is confirmed to be brick-like while brick-ness is denied to D because of the ruinous apparent triangularity of the side face,

Of course if the propagation of a property like brick-ness or wedge-ness down a series of objects is interrupted, then the unknown must be compared with a battery of models, with the program still foraiving omissions, but now searching for the best of many possible identifications.

Ho matter what the method by which a partly obscured object is identified, the use of a PROBABLY-A-KIND-OF pointer instead of the basic A-KINO-OF is used to qualify

the conjectured relationship between the object and the

Identify

Front Object

More Objects In

The Row?

Examine Next Object

Is There Reason

To Believe It 15

Kot Of The Same Type

As The Object In

Front Of It?

Identify It Using

Full Model List

Assume It 15

The Same As

The Object In

Front Of It

FIGURE 7-24

5 Identified As A Brick

4 Confirmed As A Wedge

FIGURE 7-25

FIGURE 7-26

these pointers indicate ‘7 concept similarity and contain descriptions of the similarity in their own descriptions,

FIGURE 7-27

the differences between an unknown and a Particular model is compared with the descriptions of the similarity net, If the difference between the unknown and a particular model matches the difference between that model and some other model, then identification with that other model is likely,

For example, the scene of fiqure 7-26 relates to the model of a pedestal in roughly the same way that the model of a house relates to the model of a pedestal, House is consequently elevated to the top of the list of trial models, Figure 7-25 clarifies the procedure,

7.6.1 Similarity Lescriptions

The similarity descriptions are simplifications of the comparison descriptions and are part of the description of each pointer that relates similar concepts, When a losing identification reminds the program of some difference structure it has seen, no serious commitment is made and mistaken conjectures do not hurt much, Consequently it fs desirable to strip the difference descriptions to the important elements, thereby Saving storage space and increasing matching speed, even though some wrong models may be proposed as likely identifications, The simplified description therefore

consists in part of a sort of skeleton, (fiqure 7-29)

Try To [Dentify

Unenown With Next

Model On Model List

Does Identification

Succeed

18 Difference

Quantitatively Small?

Does Difference

Descriptlon Ldentife

With Any Knows Difference

Relating Thes Model

To Some Other Model?

Place Best

Matching Model At

The Front Of The

Model List

FIGURE 7-28

Simplified-

Description

A-Kind-Of

Next-Level

FIGURE 7-29

A-Kind-Of

FIGURE 7-30

Intersection c-notes and others associated with positive numbers on the evaluation scale are iqnored because only the disruptive c-notes are of interest here, These disruptive c-notes, which suggest poor match, are hung on the skeleton.

Figure 7-30 shows the simplified difference

description resulting from comparison of the house model with the pedestal model, Notice that it is exactly the same under this simplification transformation as that resulting from comparison of the pedestal model and the scene in figure 7-26,

7.6.2 Gefinition of Quantitatively Small

This whole similarity scheme depends on the fact that two models may have only one or a few differences that make them stronaly different in a qualitative sense, Indeed, the similarity links should exist only when the models involved are reasonably close in the sense of producing few differances, When this is true, an unknown that nearly identifies with one model in the sense of few differences is assured of matching well with the other, particularly when the two sets of differences match, Thus there must be some rule for deciding if the number of differences is sufficiently small to warrant a pair of

pointers in the similarity network, Currently the machine

considers sufficiently small to mean the number of mismatch-causing c-notes is either less than two or less than one-third of the number of other c-notes,

7.7 The feedle in the Haystack

The scene of figure 7-31 is curious in that one can find an arch, a pedestal, a house, and a tent in it if one is looking for them, But if they are not specifically searched for, mention of these particular models is unlikely to appear in a description of the scene, Although the configurations are present, they are hidden by extraneous objects so well that general orouping programs are unlikely to sort them out. Yet the question, "Does a certain model appear in the scene?" is certainly a

reasonable one, One way to attack it divides nicely into

three parts:

Find those objects in the scene that have the best chance of heing identified with the model, If the model has unusual pointers or references unusual concepts, the program pays particular attention to them. Similarly, extra attention is paid to the emphasized parts of the model, for if mates cannot be established for them, solid identification cannot be affirmed. Happily, my standard network matching program does these things without augmentation, The result is a set of links between the objects of the model and their nearest analogues in the scene. The other parts of the scene remain unlinked and end up appearina in exit c-notes,

2, Once a good group of objects is picked, then the pointers relating these objects to the other

FIGURE 7-31

A-Ekind-Of

One-Part-I5

Supported-By

FIGURE 7-32

FIGURE 7-33

to external objects dictate the relations of the croup. Any knowledgeable machine knows that a house configuration rests on whatever its bottom object rests on, fore generally, the fallowing rule seems reasonable: Suppose A and B are oroups of objects identified as substructures, then if an object of A relates to an object of B by SUPPORTED-BY, then substructure A relates to substructure B by SUPPORTED-BY, In consequence, the net in fioure 7-32 becomes that in figure 7-34,

7.8.1 Examples

Using this same procedure, the scene in fiaure 7-35 soon reaches the state of illumination shown fn figure 7-37. By examining either the picture or the net, it is easy to see that the arches AT, AL, and AR themselves constitute a sort of super-arch with arches as parts instead of objects, The machine does not refuse this substitution since the model for ARCH has only ONE- PART-IS pointers to BRICK and OBJECT, not ONE={PART=NUST-BE pointers, The matching score is simply lower than it would be for arches made of bricks, The final description essentially states that the scene consists of a sort of arch supported by an arch composed of three arches,

Figure 7-36 shows a richer example including

instances of a pedestal, Again the machine identifies

A-Kind-Of —

One-Part-I5

Supported-By

FIGURE 7-34

FIGURE 7-35

eae

FIGURE 7-36

| - Supported-By

One-Part-1S

(to parts of AL)

FIGURE 7-37

groups, establishes relations between the ident ified groups, and then tries to identify groups of groups, reporting eventually that there is an arch composed of an arch on top with two pedestals for supports. It then notices that this generalized arch is supported by two ordinary arches, Gut the generalized arch on top of two supporting arches again is a kind of arch, the fifth and last discovered,

7.8.2 Other Relations

I have not thought much about the calculation of other group properties, It seems reasonable, however, that a set of programs using the following ideas should work to some extent, albeit crudely, To find IN-FRONT-OF relations between groups one can use the above rule for SUPPORT with the obvious exchange of IN-FRONT-OF for SUPPORTED-BY. To establish the size of a group one can add together the individual areas of its objects, To check for LEFT-OF and ®1S1T-OF, one uses the center of area and extreme points of the entire group rather than those of an individual object, But otherwise the left-

right algorithm may remain the same.

8 Closing Remarks

8.1 A System

& Closing Remarks

The flow diagram in figure 8-1 shows how the techniques fit together with those of others to form a primitive scene-perceiving system, At the very becinning lies the scene, from which all information ultimately derives, A program developed by Griffith [7] watches the scene through an eye resembl ing television camera, The result is a line drawing, Next programs of Mahabala [1] and Guzman [2] classify vertexes and group regions into bod jes, Next is a stage in which object identification is done, Following closely, one has the determination of object-object relations and then group identification, Finally there is identification of group-group relations,

Beyond this, action depends on intent. Gn one path one finds attempted identification of the entire scene with a known model or models, On another, an effort is made to find an instance of some particular model in the scene. Still another path involves use of the description to help form new concepts,

8.2 Conclusions

This collection of ideas and techniques supports four major contentions, each of which depends on those

preceding it. These things are small steps for a man, but

Contribute To Formation

‘Of A New Concept

Identify Groups

Find Objeci-Object

Relations

Use Guzman'S

Region Grouping

Program

Use Mahabala'S

Vertex Classifying

Program

Use Binford'S Or

Griffith'S Line

Finding Program

FIGURE 8-1

qiant leaps for a machine, 1. A computer can produce a detailed scene description consisting of the same sort of facts humans observe,

2, These descriptions lead in turn to descriptions of how scenes compare with one another,

3, An understanding of how scenes compare permits the computer to learn models for new concepts from examples and leads to a new way af thinking about learning,

4, These models finally endow the machine with the ability to recognize instances of previously learned concepts,

8.3 Background Issues

In a more cosmic sense, the goal behind this work is to make a@ machine that can understand the environment Just as we humans seem to, Some critics of Artificial Intelligence think that this is not possible, perhaps because they cannot imagine how it can be done, I think the real hang up must lfe in the understanding one has about the notion of understanding, A review of a few dictionaries convinces me that the editors are hard pressed to define the word without using it. It is as if it were a word so basic that it cannot be deserdbed in simpler terms.

But surely to understand must involve the formation

of a descriptive plateau of knowledge lying somewhere

between raw, totally unprocessed data and detailed answers

to problems, Ido net wish to belabor this point, but I feel that the sort of abstraction represented by the network description of a scene can be viewed as constituting a sort of understanding, If so, depth of understanding corresponds roughly to the elaborateness of a description, dense networks suggesting more understanding than sparse ones.

Another notion of lono standing concern to philosophy is that of the ideal form, Yet little work seems to have gone intc careful study of what humans mean by such simple concepts as that of the TABLE. I believe study and improvement of the concept generator constitutes a fresh approach to this problem and may lead ta interesting new results.

8.4 Suggestions for Further Work

Improvements to and extensions of this work can be understood in terms of two extremes: miner change and major overhaul, The minor-change category is large because the highest priority goal in such work must be a

complete system, A complete system, however flimsy, serves to guide resource allocation into the most deserved problem areas, Without experience with such a system, one risks suffering from the phenomenon of diminishing

returns, expending great effort for mareinal improvements

on relatively strong pieces of the system, Put the

natural result is that there is much room for further

improvement of the system's parts. Some possibilities

have already bean mentioned, but it is appropriate te

mention them here as a convenience for those whe wish to

work in the area,

1, Nearly all the programs that establish relations

between objects can be improved, The program that looks for support blunders sometimes because obvious bottom lines are overlooked and sometimes because a scene fas tipped hackoround objects. The program that looks for in-front-of relationships cannot handle situations in which objects are aligned, “lany of these programs could

benefit from a progran that could iwagine hidden lines,

Ho distinctions are made between okvious, unarguable properties and borderline cases. It might be oood if the analytic programs could report things like certainly-left-of or sort-ofleft-of instead of invariable, undifferentiated left-of,

The rules for the identification of a scene with a medel need refinement. The weighting associated with the various differences and the way those weights are combined have a specious quality, It would be fine if some way could be devised to eliminate the numbers altogether, perhaos through a more intellioent program with a built-in understanding of priorities.

. The schemes for recognizing reasonable clusters of

objects is particularly primitive and has undergone too little testing, Mechanisms must be found for producina and handline alternatives to the first partition devised.

The entire concept generation procedure and its ramifications certainly should absorb great

and there is the option of using or not using warious relation-finding and crouping procedures. but the forte of an internally interactive system will probably involve selection of one method from several possibilities amonq which there are trades between speed and accuracy,

Another amorphous problem is that of wedding the visual capabilities of this system with other systems that specialize in different kinds of perception, A real robot should understand the environment not only in terms of vision but alse in terms of touch, sound, language, and perhaps other mediums, Understanding each of these is a major problem, but as work proceeds, there will be the super-problem of understand ing how various perceptions of

the environment should interact to form a unified

understand ing.

I understand neuroanatomical evidence is that evolution has come to arins with this problem only lately and only in man with any finesse. Morman Geschwind reports that monkeys have very limited ability to correlate things they learn via the visual, auditory, and somesthetic senses [a]. Indeed it may be reasonable to say each monkey is really three monkeys occupying the same skull, a visually oriented monkey, a auditory one, and a somesthetic one, an apparently avoids this through a chunk of cortex that somehow matches up these perceptions, The chunk believed responsible by Geschwind is called the inferior parietal lobule,

Appendix

This appendix is a cursory introduction to the network matehina program essential to many of the system's operations, Its job is to determine which nodes of two descriptions best correspond, The corresponding nodes are said to be the linked pairs.

The program starts with the entry nodes of two descriptions, It immediately inquires if there is evidence that the two nodes should be considered a linked pair. The answer is yes if beth nodes have a comman pointer to some common intersection node. Thus % and x! are a linked pair in figure A-l, but they are certainly not in figure A-2, since nodes X and X' have neither Pointers nor nodes in common,

Tf no linking can occur, the program moves down one level through the most common pointer present to daughters of the currently inspected nodes and tries to find linked pairs among them, [In fiqure A-3, the entry nodes are not linked on first inspection since there are no common pointers to any common node, They both have dauchter nodes, however, and these are next examined, P is the most numerous pointer, so nedes Cl, C2, Cl", and C2' form

two groups in which the program tries to find good pairs

FIGURE A-1

FIGURE A-2

-F

FIGURE A-3

FIGURE A-4

2e7

to establish as linked. (figure A-4) Since Cl and C1' both have the same pointer to a common node they are good candidates for the formation of a linked pair, Nodes C2 and C2' are even more alike, however, since they have two pointers to two common nodes, Consequently, C2 and C2! are linked first, with action on Cl and Cl! postponed,

Each time a pair of nodes is linked, the program trys to link up any of their daughter nodes that are not intersections, In the example this means that an effort is made to find a linked pair between the left node, £1, and the right nodes, E1' and E2', all of which are found at the end of P pointers. (fieure A-5) This is the first example of a contest. Both £1" and £2' share conman intersections with £1, The winning pair picked by the machine is always the one with the highest count of commen pointers te intersectons or previously linked pairs. In this case, E]-El' scores higher because there is not only @ set of pointers to the intersection node, but also a set to the previously linked pair C2-C2'.

The linking of El and £1" causes examination of their daughters, Fl on the left, Fl' and F2' on the riaht, (figure h-6) Fl and F2" both have a pointer — to a common node, Fl', however, has the must-he version of the

pointer f to the same node, Such satellites occur

FIGURE A-5

q--- 0+ -------4

Must-Be-Satellite

FIGURE A=6

frequently in models, indicating mandatory relations, Priority is given to matches in which satellites correspond to the pointers they are modifications of, This means the R with MUST-BE-R pointer match between nodes Fl and Fl' has somewhat more weight than the match of R with R that one would have between Fl and F2', The FI-Fi' match therefore is considered the better one and results in a linked pair,

Fi and F1' have no daughters to be naired so no further penetration of the net occurs, The next job is to re-examine the next higher parent nodes because links just formed may provide enough new evidence to Tink two higher nodes, In this case backup first considers nodes E17 and bt, El and El' are already linked, Attention therefore pops up still another level to Cl and C1', Cl and Cl' are linked, Re-examination of their unlinked daughters, 0 and EZ, reveals nothing new,

Once more the praqrams attention shifts upward, this tine to A and A‘, Now there is a pair of pointers to linked nodes supplying linking evidence, (figure A-7) A is consequently linked ta A‘,

Next comes further examination of the remaining daughters of A and A’, @ is now the most common pointer

to unaccounted for nodes, pointing as it does to Gi, G2,

FIGURE A-7

FIGURE A-3

and G2". (figure A-8) Among these nodes there 1s the same amount of evidence for linking Gl and G2' as there is for linking G2 and G2', When this is the case amd no further evidence can be collected from linking lower level nodes, a linking is selected randomly from those possible, Here G2 and &G2' are linked.

This leaves only reexamination of C2 and C2', The intersection evidence is clear ard they are linked, Since A and A' have no more daughters and since they are the entry nodes, the process terminates reporting the linkages

indicated om the fully displayed network of figure A-4,

FIGURE A-9

References

C1] . tl. Mahabala, “Preprocessor for Programs which Recaoqnize Scenes," Artificial Intelligence, Memo. No, 177 (Cambridge, ‘!ass.: Project MSC, MIT, August 1969),

{2] Adolfo Guzman, “Computer Recognition of Three- Dimensional Objects in a Visual Scene," Report MAC-TR-59 (iggy 18) (Cambridge, Wass.: Project “AC, MIT, December 1968).

(3] Jean Piaget, The Child's Conception of Number (New York: Wumanities Press, 1952).

{4] Thomas G. Evans, "A Heuristic Program to Solve Geometric-Analogy Problems," PhO. Thesis, Department of Mathematics, MIT (Cambridge, Mass.: MIT, May 10, 1963),

[5] George HW. Ernst and Allen flewell, GPS: A Case Study im Generality and Problem Solving New York: Academic Press, 1969),

C6] Allen Newell, "Learning, Generality, and Problemsolving," Procecdings of the IFIP Canaress: 407-412 (fmsterdam: North Holland Publishing Co., 1969),

[7] Arnold Griffith, “Computer Recognition of Prismatic Solids, PhO. Thesis, Department of Mathematics, MIT (Cambridge, Mass.: MIT, June 1970),

[8] Norman Geschwind, Disconnexion Syndromes in Animals and Man, Brain @B: 237-294, 585-644, 1965,

Bibiliooranhy

Ernst, George W. and Newell, Allen, GPS: & Case Study in Generality and Problem Solving. New York: Academic Press, 1969,

Evans, Thomas G. "A Heuristic Program to Solve Geemetric- Analogy Problems." PhO, Thesis, Department of Mathematics, MIT, Cambridge, Mass.: MIT, May 10, 1963,

Geschwind, Norman, Disconnex fon Syndromes in Animals and Man, Part I, Brain &f: 237-294, dune 1965,

Geschwind, Norman, Disconnex ion Syndromes in Animals and Man, Part TI. Brain 88: 505-644, Sept. 1965,

Griffith, Arnold, Computer Recoanition of Prismatic Solids, PhO. Thesis, Uepartment of Mathematics, MIT. Cambridge, Masse: MIT, June 1970,

Guzman, Adolfo, "Computer Recognition of Three- Ginensional Objects in a Visual Scene," Report MAC- TR-59 (Thesis). Cambridge, Mass.,: Project MAC, MIT, December 1968,

Mahabala, H. N. "Preprocessor for Programs which Recognize Scenes." Artificial Intellicence, “emo. Ho, 177. Cambridge, Yass.: Project MAC, MIT, August 1969,

Newell, Allen. “Learning, Generality, and Problem. solving." Proceedings of the IFIP Congress: 407- 412. Amsterdam: Morth Holland Publishing Co,, 1969,

Piaget, Jean, The Child's Conception of Number New Yorks Humanities Press, 1952,