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

<!-- Original PDF page 9 -->

FIGURE 1-1

<!-- Original PDF page 10 -->

p

[- One-Part-1I5

Supported-By In-Front-Of

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

<!-- Original PDF page 12 -->

Arch Near Miss

Arch Near Miss

Fd

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,

<!-- Original PDF page 14 -->

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,

<!-- Original PDF page 15 -->

FIGURE 1-8

FIGURE 1-3

<!-- Original PDF page 16 -->

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

<!-- Original PDF page 17 -->

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.

<!-- Original PDF page 18 -->

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

<!-- Original PDF page 19 -->

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,

<!-- Original PDF page 20 -->

FIGURE 2-1

<!-- Original PDF page 21 -->

FIGURE 2-2

Left-0F —,

Right -Of -

A-Kind-Of

Has-Property-Of

One-Part-15

Modlfication-Of

———— Modification-Of

Must-Not-Be-

Supported-By

Must-Be-

Supported-By

Must-Not-Be-Satellite

—— Opposite

Property=Of ,

Fork

Multi

Peak

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.

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

<!-- Original PDF page 32 -->

Wd — b Do |

<!-- Original PDF page 33 -->

<!-- Original PDF page 34 -->

FIGURE 2-13

<!-- Original PDF page 35 -->

Interior Line

Bottom Limes - *

Interior Line

Bottom Lines -~"

Interior Line

Bottom Lines

Bad Candidates

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

<!-- Original PDF page 45 -->

<!-- Original PDF page 46 -->

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

<!-- Original PDF page 47 -->

af

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.

<!-- Original PDF page 48 -->

<!-- Original PDF page 49 -->

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

<!-- Original PDF page 50 -->

FIGURE 2-39

FIGURE 2-32

BURIED Ls

FIGURE 2-31

FIGURE 2-33

<!-- Original PDF page 51 -->

5a

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

<!-- Original PDF page 52 -->

Physically Associated Lines Of A

Physically Associated Lines Of B

All Outer

Edges Found

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:

<!-- Original PDF page 59 -->

<!-- Original PDF page 60 -->

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

B K -

E - -

H Ij -

I - -

J - -

K H E

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

<!-- Original PDF page 61 -->

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

<!-- Original PDF page 62 -->

mere +--+ es,

FIGURE 2-42

<!-- Original PDF page 63 -->

FIGURE 2-43

<!-- Original PDF page 64 -->

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

<!-- Original PDF page 65 -->

FIGURE 2-44

<!-- Original PDF page 66 -->

a? !

FIGURE 2-45

-)

FIGURE 2-46

<!-- Original PDF page 67 -->

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,

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

<!-- Original PDF page 68 -->

FIGURE 2-47

FIGURE 2-48

FIGURE 2-43

<!-- Original PDF page 69 -->

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.

<!-- Original PDF page 70 -->

FIGURE 2-58

FIGURE 2-51

| Figure 2-52

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

<!-- Original PDF page 73 -->

FIGURE 2-55

<!-- Original PDF page 74 -->

FIGURE 2-56

FIGURE 2-57

<!-- Original PDF page 75 -->

FIGURE 2-58

<P

FIGURE 2-53

<!-- Original PDF page 76 -->

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,

<!-- Original PDF page 77 -->

q

FIGURE 2-68

<!-- Original PDF page 78 -->

<!-- Original PDF page 79 -->

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

<!-- Original PDF page 80 -->

FIGURE 2-62

<!-- Original PDF page 81 -->

FIGURE 2-63

<!-- Original PDF page 82 -->

<!-- Original PDF page 83 -->

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

<!-- Original PDF page 84 -->

FIGURE 3-1

FIGURE 3-2

<!-- Original PDF page 85 -->

ae

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.

<!-- Original PDF page 86 -->

One-Part-I5

Supported-By

Sa | *

a7

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

<!-- Original PDF page 89 -->

FIGURE 3-6

FIGURE 3-7

<!-- Original PDF page 90 -->

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

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

<!-- Original PDF page 98 -->

<!-- Original PDF page 99 -->

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.

<!-- Original PDF page 100 -->

A-Kind-Of

One-Part-I5

Supported-Ey Form

Has-Property-Of A-Kind-Of

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

<!-- Original PDF page 103 -->

Linked

— One-Part-1Is

Supported-

A-Kind-Of

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,

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

<!-- Original PDF page 105 -->

4+—— from linked pair LA - BA

One-Part-Is

Supported-By

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

<!-- Original PDF page 107 -->

Linked

Intersection

Pointer-Destination

Three

Ll. — /

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

<!-- Original PDF page 116 -->

Scene L Scene R

Supported-Eby

Scene L Scene R

C-Note

A-Kind-Of _- Left-Fointer

Supplementary -Pointer-

¢ _ Supported-By

Pointer-Destination

C=Note

A-Eind-Of

Has-Property-Of

“ Polnter-Destination

Negative-Satellite

Modification-Of

Right- Pointer

Pointer-Destination

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

<!-- Original PDF page 123 -->

Probably -Mabries

Pl = Maybe-Satellite

P2 = Probably-Satellite

P3 = Negative-Satellite

P4 = Must-Be-Satellite

Bs = Must-Not-Be-Satellite

A-Kind-Of —

- G-Note

A-Kind-Of

Left-Destination Right-Destinat Ion

A-Kind-Of

Brick

§ 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

<!-- Original PDF page 128 -->

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.

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

<!-- Original PDF page 129 -->

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

<!-- Original PDF page 130 -->

FIGURE 5-1

FIGURE 5-2

FIGURE 5-3

<!-- Original PDF page 131 -->

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.

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

<!-- Original PDF page 132 -->

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.

<!-- Original PDF page 133 -->

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.

<!-- Original PDF page 134 -->

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.

<!-- Original PDF page 135 -->

Example

—— First Model

Sample 1

—— Second Model

Sample 2

—— Third Model

Sample 3

—— Fourth Model

First Round Model

——— Second Round Models

Third Round Models

Fourth Round Models

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,

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

<!-- Original PDF page 137 -->

TS

Current Model Example

A-Eind-Of

A-Kind-Of

Merge

- Pointer

Left-Destination Right-Destination

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

<!-- Original PDF page 140 -->

One-Part-I5

Object

Scene 1 Scene 2

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,

<!-- Original PDF page 143 -->

‘One-Part-15

Must-Be~-Supported-By

—— One-Part-15

Must-Not-Be-Supported-By

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,

<!-- Original PDF page 145 -->

Current Model Near-Miss

Table

Action Of Concept Generator; Example Case

Action Of Concept Generator; Near Miss Case

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

<!-- Original PDF page 149 -->

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,

<!-- Original PDF page 150 -->

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

<!-- Original PDF page 151 -->

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

<!-- Original PDF page 152 -->

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,

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

<!-- Original PDF page 153 -->

TO) ex

Current Model Near-Miss

Current Model Near-Miss.

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,

<!-- Original PDF page 159 -->

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,

<!-- Original PDF page 160 -->

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.

<!-- Original PDF page 161 -->

<!-- Original PDF page 162 -->

FIGURE 6-1

Near Miss

Near Miss

Near Miss

One-Part=18

Supported-By

A-Eind-Of

One-Part-I5

———— A=-Kind-0Of

One-Fart-15

——Must-Be-Supforted-Ey

4-Kind-Of

Model L_ ————_

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

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

<!-- Original PDF page 166 -->

One-Part-I5

—— Must-Be-Supported-By

Must-Be-A-

Eind-Of

Model 1

Model 2

Model 3

Near Miss Near Miss

Near Miss Near Miss

Near Miss

Near Miss

Must-Be-A-Kind-Of J

Arch Near Miss

Near Miss Arch

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

<!-- Original PDF page 176 -->

FIGURE 6-26: WEDGE

<!-- Original PDF page 177 -->

A-Kind-Of

One-Part-15

Brick-Model

R = Rectangle

T = Triangle

— One-Part-Must-Be

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

One-Part-May-Be

One-Part-Must-Be

A-Kind-Of ——

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

<!-- Original PDF page 183 -->

FIGURE 6-32: WEDGE

<!-- Original PDF page 184 -->

Column

Near Miss

Column

| Figure 6-36

Near Niss

Near Miss

Column

A-Kind-Of

A-Kind-Of

Supported-By

One-Part-Must-Be

Must-Marry H Number-Of-

° Members

Must-Be-Supported-By

A-Eind-Of

A-Eind-0F

Number-0F =

In-Front-0F Members

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.

<!-- Original PDF page 194 -->

FIGURE 6-47: TABLE

<!-- Original PDF page 195 -->

One-Part-[5

Supported-By

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

Table Near Miss

Near Miss Near Miss

6 0Z/A

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

~Lon-Lsak

40-Noilvoiaigcon

Slittalys -49 -Lsak

40-Nollvilaigor

<!-- Original PDF page 200 -->

<!-- Original PDF page 201 -->

<!-- Original PDF page 202 -->

<!-- Original PDF page 203 -->

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.

<!-- Original PDF page 204 -->

scene) ERE 8

FIGURE ?-1

<!-- Original PDF page 205 -->

<!-- Original PDF page 206 -->

FIGURE 7-3

<!-- Original PDF page 207 -->

<!-- Original PDF page 208 -->

FIGURE 7-4

<!-- Original PDF page 209 -->

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

Right-0F

In-Froni- Of

Opposite

Opposite

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

<!-- Original PDF page 217 -->

<!-- Original PDF page 218 -->

FIGURE 7-12

FIGURE 7-13

<!-- Original PDF page 219 -->

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

<!-- Original PDF page 220 -->

Unenown Model

Must-Be-A-Kind-Of

— A-Kind-Of

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

House Pedestal

Tent Arch

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

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

<!-- Original PDF page 228 -->

f/f» £_/ cP oF

<!-- Original PDF page 229 -->

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

<!-- Original PDF page 230 -->

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

<!-- Original PDF page 231 -->

<!-- Original PDF page 232 -->

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

5 Identified As A Brick

4 Confirmed As A Wedge

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)

<!-- Original PDF page 237 -->

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

Simplified-

Description

A-Kind-Of

Next-Level

A-Kind-Of

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

<!-- Original PDF page 240 -->

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,

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

<!-- Original PDF page 241 -->

FIGURE 7-31

<!-- Original PDF page 242 -->

<!-- Original PDF page 243 -->

A-Ekind-Of

One-Part-I5

Supported-By

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

<!-- Original PDF page 246 -->

A-Kind-Of —

One-Part-I5

Supported-By

| - Supported-By

One-Part-1S

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.

<!-- Original PDF page 250 -->

& 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,

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

<!-- Original PDF page 251 -->

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

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

<!-- Original PDF page 253 -->

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.

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

<!-- Original PDF page 254 -->

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

<!-- Original PDF page 255 -->

<!-- Original PDF page 256 -->

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,

<!-- Original PDF page 257 -->

FIGURE A=6

<!-- Original PDF page 263 -->

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,

<!-- Original PDF page 264 -->

FIGURE A-7

FIGURE A-3

<!-- Original PDF page 265 -->

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,

<!-- Original PDF page 266 -->

FIGURE A-9

<!-- Original PDF page 267 -->