Gödel, Escher, Bach: An Eternal Golden Braid (118 page)

Read Gödel, Escher, Bach: An Eternal Golden Braid Online

Authors: Douglas R. Hofstadter

Tags: #Computers, #Art, #Classical, #Symmetry, #Bach; Johann Sebastian, #Individual Artists, #Science, #Science & Technology, #Philosophy, #General, #Metamathematics, #Intelligence (AI) & Semantics, #G'odel; Kurt, #Music, #Logic, #Biography & Autobiography, #Mathematics, #Genres & Styles, #Artificial Intelligence, #Escher; M. C

BOOK: Gödel, Escher, Bach: An Eternal Golden Braid
8.97Mb size Format: txt, pdf, ePub

FIGURE 120. Bongard
problem 47. [From M. Bongard, Pattern Recognition.]

Thus, a typical box-say I-F of BP 47 (Fig. 120)-could be variously described as having: three shapes

or

three white shapes

or

a circle on the right

or

two triangles and a circle

or

two upwards-pointing triangles

or

one large shape and two small shapes

or

one curved shape and two straight-edged shapes

or

a circle with the same kind of shape on the inside and outside.

Each of these descriptions sees the box through a "filter". Out of context, any of them might be a useful description. As it turns out, though, all of them are "wrong", in the context of the particular Bongard problem they are part of. In other words, if you knew the distinction between Classes I and II in BP 47, and were given one of the preceding lines as a description of an unseen drawing, that information would not allow you to tell to which Class the drawing belonged. The essential feature of this box, in context, is that it includes

a circle containing a triangle.

Note that someone who heard such a description would not be able to reconstruct the original drawing, but would be able to recognize drawings

FIGURE 121
. Bongard problem 91. [From M. Bongard, Pattern Recognition.]

which have this property. It is a little like musical style: you may be an infallible recognizer of Mozart, but at the same time unable to write anything which would fool anybody into thinking it was by Mozart.

Now consider box I-D of BP 91 (Fig. 121). An overloaded but "right" description in the context of BP 91 is

a circle with three rectangular intrusions.

Notice the sophistication of such a description, in which the word "with" functions as a disclaimer, implying that the "circle" is not really a circle: it is almost a circle, except that

. . . Furthermore, the intrusions are not full rectangles. There is a lot of "play" in the way we use language to describe

things. Clearly, a lot of information has been thrown away, and even more could be thrown away. A priori, it is very hard to know what it would be smart to throw away and what to keep. So some sort of method for an intelligent compromise has to be encoded, via heuristics. Of course, there is always recourse to lower levels of description (i.e., less chunked descriptions) if discarded information has to be retrieved, just as people can constantly look at the puzzle for help in restructuring their ideas about it. The trick, then, is to devise explicit rules that say how to

make tentative descriptions for each box;

compare them with tentative descriptions for other boxes of either Class; restructure the descriptions, by

(i) adding information,

(ii) discarding information,

or (iii) viewing the same information from another angle; iterate this process until finding out what makes the two Classes differ.

Templates and Sameness-Detectors

One good strategy would be to try to make descriptions
structurally similar to
each other
, to the extent this is possible. Any structure they have in common will make comparing them that much easier. Two important elements of this theory deal with this strategy. One is the idea of "description-schemas" or
templates
; the other is the idea of Sam-a "sameness detector".

First Sam. Sam is a special agent present on all levels of the program.

(Actually there may be different kinds of Sams on different levels.) Sam constantly runs around within individual descriptions and within different descriptions, looking for descriptors or other things which are repeated. When some sameness is found, various restructuring operations can be triggered, either on the single-description level or on the level of several descriptions at once.

Now templates. The first thing that happens after preprocessing is an attempt to manufacture a template, or description-schema-a un form format for the descriptions of all the boxes in a problem. The idea is that a description can often be broken up in a natural way into subdescriptions, and those in turn into subs ubdescriptions, if need be. The bottom is hit when you come to primitive concepts which belong to the level of the preprocessor. Now it is important to choose the way of breaking descriptions into parts so as to reflect commonality among all the boxes; otherwise you are introducing a superfluous and meaningless kind of

"pseudo-order" into the world.

On the basis of what information is a template built? It is best to look at an example. Take BP 49 (Fig. 122). Preprocessing yields the information that each box consists of several little o's, and one large closed curve. This is a valuable observation, and deserves to be incorporated in the template. Thus a first stab at a template would be:

large closed curve:-----

small o's:-----

FIGURE 122.
Bongard problem 49. [From M. Bongard, Pattern Recognition.]

It is very simple: the description-template has two explicit
slots
where subdescriptions are to be attached.

A Heterarchical Program

Sow an interesting thing happens, triggered by the term "closed curve". one of the most important modules in the program is a kind of semantic net--the concept network-in which all the known nouns, adjectives, etc., are linked in ways which indicate their interrelations. For instance, "closed curve" is strongly linked with the terms "interior" and "exterior". The concept net is just brimming with information about relations between terms, such as what is the opposite of what, what is similar to what, what often occurs with what, and so on. A little portion of a concept network, to be explained shortly, is shown in Figure 123. But let us follow what happens now, in the solution of problem 49. The concepts "interior"

and "exterior" are activated by their proximity in the net to "closed curve". This suggests to the template-builder that it might be a good idea to make distinct slots for the interior and exterior of the curve. Thus, in the spirit of tentativity, the template is tentatively restructured to be this:

large closed curve: ----

little o's in interior: ----

little o's in exterior:----

Now when subdescriptions are sought, the terms "interior" and "exterior" will cause procedures to inspect those specific regions of the box. What is found in BP

49, box I-A is this:

large closed curve:
circle

little o's in interior:
three

little o's in exterior:
three

And a description of box II-A of the same BP might be

large closed curve:
cigar

little o's in interior:
three

little o's in exterior:
three

Now Sam, constantly active in parallel with other operations, spots the recurrence of the concept "three" in all the slots dealing with o's, and this is strong reason to undertake a second template-restructuring operation. Notice that the first was suggested by the concept net, the second by Sam. Now our template for problem 49 becomes:

large closed curve:----

three little o's in interior: -----

three little o's in exterior:-----

FIGURE 123.
A small portion of a concept network for a program to solve
Bongard Problems. "Nodes" are joined by "links", which in turn can be linked. By
considering a link as a verb and the nodes it joins as subject and object, you can
pull out some English sentences from this diagram.

Now that "three" has risen" one level of generality-namely, into the template-it becomes worthwhile to explore its neighbors in the concept network. One of them is "triangle", which suggests that triangles of o's may be important. As it happens, this leads down a blind alley-but how could you know in advances It is a typical blind alley that a human would explore, so it is good if our program finds it too!

For box II-E, a description such as the following might get generated: large closed curve:
circle

three little o's in interior:
equilateral triangle

three little o's in exterior:
equilateral triangle

Of course an enormous amount of information has been thrown away concerning the sizes, positions, and orientations of these triangles, and many other things as well. But that is the whole point of making descriptions instead of just using the raw data! It is the same idea as funneling, which we discussed in Chapter XI.

The Concept Network

We need not run through the entire solution of problem 49; this suffices to show the constant back-and-forth interaction of individual descriptions, templates, the sameness-detector Sam, and the concept network. We should now look a little more in detail at the concept network and its function. A simplified portion shown in the figure codes the following ideas:

"High" and "low" are opposites.

"Up" and "down" are opposites.

"High" and "up" are similar.

"Low" and "down" are similar.

"Right" and "left" are opposites.

The "right-left" distinction is similar to the "high-low" distinction.

"Opposite" and "similar" are opposites.

Note how everything in the net-both nodes and links-can be talked about. In that sense nothing in the net is on a higher level than anything else. Another portion of the net is shown; it codes for the ideas that

A square is a polygon.

A triangle is a polygon.

A polygon is a closed curve.

The difference between a triangle and a square is that one has 3 sides and the other has 4.

Other books

Broken Mirrors by Pratt, T. A.
The Child Bride by Cathy Glass
Allegiance by Trevor Corbett
Hunt at the Well of Eternity by Gabriel Hunt, James Reasoner
Masked Definitions by A. E. Murphy
William W. Johnstone by Phoenix Rising
Forging Zero by Sara King