The Modeling of Simple Analogic and Inductive Processes in a Semantic Memory System

I. Introduction

The model described in this paper represents an attempt to formalize a number of general cog­ nitive processes. Although these processes may be said to be "simpl e" in the sense of being primitives input text is t r anslated into an appropriate proof cognitive behavior, they are by no means simpl e to make explicit in their full generality. Within program is applied (rather than added) to the data the confi nes of thi s paper we could not begin to discuss all of the intricacies of modeling these processes, and if we could, the r eader could not begin to sort out t he main ideas underlying the model. Ther efor e we have chosen t o present the el ements of the model in an oversimplified form designed to bring out the major ideas they embody; then i n separate sections (Sections II.C, III.B, and V. B) we indicate what elaborations must be made in order for the model to be truly gener al. In Section V. B we also discuss the formidable problems that arise in validating a model such a s this one.

Relat ion to other Research

We will briefly indica~e where the present model stands with respect to other semantic systems which are current ly under development. Obviously it is unjust to characterize such complex models in a phrase or two, but i t is impossible to compare them in detail her e.

~ The r esearch reported here was supported in part by the Advanced Research Projects Agency of the Office of the Secretary of Defense (SD-183 ).

Most of the semantic memor y systems that have been proposed are designed ar ound the pr oblem of dealing with natural l anguage . A primary component of the "understanding" of an i nput text is its t ranslation i nto some formal, language-free repr e­ sentation, In the systems of ~illian [1,2] and Simmons et al [3], the input is translated directly into a format consistent with the r est of the general semantic memor y. A distinctly different approach is being pursued by Kellogg [4], Woods (5], and Kochen [6], who divide their semantic systems into two components: a data base (in a non-gener al format) and a procedural programming language which operates on this data base . In these systems the gram in the procedural language, and then this base. The semantic system which we will pr esent her e contains el ements of both appr oaches . The semantic memory is a single structure in a format whi ch is claimed to be gener al, but this format is itself procedural.

The formalism is a l so closely allied to the pr edicate calculus r epr esentation adopted by many workers who are concerned with preserving deductive capacity within the system, e. g. Green and Raphael [7], McCarthy [8], and Bl ack [9]. At the same time, we have striven to maintain consistency with what little is known of the psychology of human memor y, as discussed by Bartlett [10] and Oldfield [11], and with the bel ief-system simulations of Col by [12], and Abelson and Carroll [13].

The notion of "analogy" appears t o have r eceived extremely little attention in the tech­ nical literature. Evans [14] in his analogy-test taker of course deals with the concept , but only in a very constrained context. Much deeper studies into analogic reasoning have been made by Kling [15] A. Consequence and Criteriality in his analysis of analogies between mathematical proofs. Although Kling's investigations also are limited to a highly restricted problem domain, they are in many r espects richer than those reported in the present paper (see Section III.B).

Before introducing the syntax of the memory structure, we will discuss the two notions which most sharply differentiate it f rom other models which have been proposed: that of "consequence" and that of "criteriality" · 1

There have been any number of schemes proposed under the name "induction", with the paradigm of sequence extrapolation gaining perhaps the greatest amount of attention (including an empirically-based model by Simon and Kotovsky [16] and an exhaustive analysis by Persson [17]). Unfortunately, it is difficult to find any useful relationship between these "induction" models and the "generalization­ over-cases" process described in the present paper. One striking difference is that in our model the general law is manufactured directly out of the instances from which it is inferred, rather than being selected from some narrowly-specified set or grammar of possible laws. The two procedures which seem closest to our generalization-over-cases are the generalization techniques discussed by Evans [14] which operate on the item. Thus, a given Rule may and Doran [18]. These are certainly noteworthy studies, but again in these models there is a fixed set of dimensions along which gener alization can occur.

Finally, there is a considerable literature on the process of "concept formation", including detailed simulations by Hunt et ~ [19]. Since our generalization process falls slightly short of being concept formation (see Section IV.A), we will not attempt any comparison with concept-formation models here.

II. The Semantic Memory Structure

In this section we will describe the semantic structure which is the basis of the present model. What is defined here is actually a reduced version of the syntax of the structure; the necessary elaborations are given in Section II.C. Throughout the paper we make the convention of capitalizing a word if it is used as a formally-defined term rather than in its usual English meaning (e.g. "Situation").

Consequence. The principal unit of infor­ mation in this model, called the Rule, contains an arrow"~", whose function is to introduce serial ~as a primitive of the data structure. The number of reasons for desiring such a primitive is so large that we can give only a sampling of them here. The idea of "consequence" in an expr ession such as "lightning ~ thunder" has at least four possible interpretations: (1) temporal sequence, (2) ~ law, (3) logical implication, and (4) behavioral r esponse (e. g. "given lightning, predict thunder"). What is important is that we can store this item of data in a noncommittal fashion by means of the "~" primitive, and leave the precise interpretation up to the processes at one time behave as a predicate calculus formula, and at another time as a "pattern-operation" rule or "production-language" procedure for behavior. This use of serial order as a basic feature of memory is of course consistent with almost ever y psychological observation or theory, from Associationism to Stimulus-Response. A particularly insightful discussion of its importance is given by Iashley [21].

Criteriality. Given formal structures A and B such that B is a sub-structure of A, we will want a measure of the degree to which the presence of B in A is responsible for the distinctive identity of A. This we will call the "criteriality" of B with respect to A. For example, if it is irrelevant whether or not B is present in A, then B may be said to have zero criteriality with respect to A. The formal utility of such a notion will become clear in Section IV; at this point we may give an informal motivation in t erms of the phenomenon of "attention". When we perceive the world, various aspects of the situation at hand receive varying degr ees of attent ion, These vari at ions must be r ecor ded in the semantic memor y, for they clearly affect t he r ecall and further processing of our per ceptions, Criteriality, at l east in its initia l a ssignment, is merely the frozen record of attent ion,

1/ The idea of criteriality was introduced by Quillian (20], but has been relegated to a minor role in his latest model, Quillian [2).

B, Description of the Memory Structure

The "objects" in this memory system are actually gr aph structures (i.e, pointer nests), but it is generally more convenient to work with them in a notation which disguises their net-like nature, The r eader must bear in mind (as when progr amming i n LISP) that the notation does not tell the full story, and that an "occurrence of an object" is identically the same as a pointer to some graph structure,

Two types of objects, ~ and Rules, are used t o encode the content of any assertion, s i tuation, or event , We will begin by describing the pieces from which Facts and Rules are built up,

The Node, A ~ is a nest of two-way pointers, Two Nodes are equal if and only if they are identically the same Node, Thus, the Node is the "atom" of the system, like the Atom in LISP except that here the pointers are two-way, Intui­ tively, Nodes represent "concepts", Some of these are bound to individual, distinct entities (e . g. Eugene-McCarthy, Paul-Bunyan), while others may be considered as classes of other Nodes (e. g, Minnesotan, hero), We will usually denote Nodes by English words, but this notation is for convenience only, and bears no relation to the r epr esentation of English words within the model, When we need to discuss Nodes for individual objects which, unlike Eugene McCarthy, do not have names assi gned to them already, we will invent names of the form AA, BB, etc, We will also use a special symbol "@", which designates "the Situation in whi ch this symbol occurs" (a "Situation" is defined below),

The Kernel, A ~ is an ordered n-tuple of Nodes, wher e to each Node is assigned an integer between 0 and 6, called its (Node-)Criteriality, The Kernel is interpreted as an (n-1)-ary predicate and ar guments (i. e, its pr esence indicates the assertion of that relation) , wher e the fir st Node is the predicate name , The integer s exhibit criterialities on a ? -point scal e , A Node of zero Criteriality is called a ~· For convenience in the examples presented i n this paper, we will conventionally attach a Crit eriality of 3 to a Node unless we have a particular r eason to do otherwise , In the notation, Kernels will be enclosed in pointy brackets, and Node-Criterialit i es will be written as superscripts, e,g, <give~ Max5 Olga 0 AA5> , The Situation, A Situation is an unordered set of Kernels , wher e to each Kernel is assigned an integer between -6 and 6, called its (Kernel-) Criteriality. The Situation is int erpreted as the conjunction of the statements made by its Ker nels , The negative Criterialities indicate the importance of the absence of a given condition; they serve to introduce a scaled logical negation. In the notation, Situations will be enclosed in wavy br ackets, and Kernel-Criterialities will be written after the Kernels , preceded by a colon, e , g.:

On occasion (e.g, Figure 6) we will write a Kernel outside of the Situation to which it belongs, with a two-way arrow joining it to its proper locat ion within the brackets ,

Weights. In order f or a semantic memory to be complete, it must store with each it em of infor­ mation a considerable number of data ~ that item, f or example: the subjective probability that it is true, its degree of surprisingness or incon­ sistency given the rest of the information in memory, its trace-strength or possibly the time elapsed since it was last referred to, its degree of pleasantness, etc, In the modeling of cognitive processes, this "meta-informat ion" about an item must play a role second only to its content i n determining what is done with t he item in a given process, Unfortunately, this role is difficult to describe, and the notation for many weights is messy. Therefore in this paper we will consider only the behavior of the weight for Subjective Probability in any detail, We will note points in Sect i on IV at whi ch the absolute l ikelihood of an item i s cr itical i n determi ni ng the course of i ts pr ocessi ng.

We now intr oduce the two types of unit i n which information i s stor ed, the Fact and the Rule.

The Fact , A Fact is, syntact i cally, simply a Si tuation, The term "Fact" mer ely di stingui shes those Situations which stand f r ee, from those whi ch occur in Rules.

The Rule , A Rule is an order ed pair of Si tuati ons . It is interpr eted as assert ing that the second Situation (called the Right Hal f) i s a "consequence" of the fir st (cal led the Left Hal f) , in the unspecified sense discussed in Sect ion II.A In the notation, the two Situations are written between square br ackets, with an arrow between them, as in Fi gure 2 (above). 1 Any Dummy whi ch occurs in the Left Half of a Rule is implici tly universally quantified; any Dummy whi ch appear s only in the Right Half of a Rule i s implicitly existentially quantified, such as the following : Thus we have t r anslations

(2)

(See Step 4.3, Section IV. B, for justification of these conventions ,) Fi nal ly, attached to each Rule i s a number between 0 and 1, interpr eted as the Subjective Probabili ty that the Ri ght Half actually i s a consequence of the Left Half, In the notation, we may displ ay this "S ,P, " to the right of the Rule, but i n most cases we will suppress it .

c. El abor at i ons of the Syntax

For the purpose of simplicity in this pr esen­ tation, we have shorn the data format of the sever a l forms of r ecursi ve nesting it must have if it is in fact to be abl e to r epr esent arbitrary informat i on. A Node must be abl e to denote any Fact or Rule (in the way that "@" denotes a Situat i on), A Situation must be able to contain Facts and Rul es as well as Ker nels, and this leads to the need for a canonical form for Situations . And Rul es may be composed out of other Rules, as well a s Situations.

The l atter form of nesting a l lows us to define a not i on of equivalence of representations, whose role i n the completed model is extremely significant . For the pr esent we wil l content ourselves with giving an example of what can be done . We can essent i a l ly define the Node "gives" by creating two Rules whi ch expand a Situation involving "gives" into a Rule composed of more pr imitive predicates . 2 This "defi nition" might look something like Figure 4 (below) · 3

g} Such expansions of single predicates into more basi c terms r aise the inter esting issue of the existence of "semantic primitives" . The matter is still ver y much open; see Bendix [22] for the most thor ough discussion to date ,

d) In Figure 4 we use a double arr ow "<>" merely as a notat i onal device to expr ess two distinct Rules (one each way) in the same diagram.

-------------------------------------------------------------------------------------------------- ---- -- - As an additional extension of the syntax, the Rule must be redefined to be a sequence (of Situations and Rules) of ~ l ength .

III. Analogy between Situations

We will gi ve a semi-formal definition of the notion of an analogy between two Situations, discuss the features and inadequacies of this definition, and then consider the role of analogy formation in cognitive processing.

A. Basic Definition of Analogy

The intuitive idea we are striving to capture is that an analogy between two situations is a motivated correspondence between the elements of the situations. In essence, then, an Analogy between two Situations s 1 and s 2 is defined to be a one- to- one mapping of the Kernels o.f s 1 onto the Kernels of s 2 · Each Kernel-to-Kernel pairing induces a mapping of the Nodes in one Kernel onto the Nodes in the other; we will denote such mappings in set - theoretic notation of the form ((a,b); ··· }. Here the Justifying Information is on the right, We require that all of the Node-to-Node mappings be consistent (i.e, that their union be one-to-one), To formalize the idea that these mappings be "motivated", we further r equire that for each non­ identical pair of Nodes n 1 ES 1 and ~ES 2 mapped into each other, we be abl e to exhibit some further information which will "justify'' the identification of n 1 with ~ · More pr ecisely: we r equir e the existence of a Situation z 1 containing n 1 , and a Situation z 2 containing ~' such that, given the identification (n 1 ,~), ~i and z 2 are themselves Analogous . There are two possible sources of each item of Justifying Information zi, namely as a sub­ Situation of the gi ven Situation Si' or as an independent Fact retrieved from memory. and the vertical arrows denote correspondences between Nodes , Expressed in English: Willy's teasing Twirpy is analogous to Willy's teasing Twinky in that both Twirpy and Twinky are parakeets . It is important to note that our definition of Analogy is r ecursive (at the point where ~l and z 2 are r equired to be Analogous, given the proposed identification), The insistence that the Node-to­ Node mapping be one-to-one makes "is Analogous to" a symmetric relation by giving each Analogy a well­ defined i nverse , The definition can easily be extended into a definition of analogy between Rules, B. Elaborations of the Definition

An example may serve to clarify this discussion, Suppose that memory contains the Fact F = ( <membe~ Twirp; parakeet3> :3}, and we are presented· with:

A reasonable Analogy between s 1 and s 2 will match the Kernel <teases 3 Will; Twirp;> of S 1 with the Kernel <teases3 Will; Twink;> of s 2 · This match induces the identification (Twirpy,Twinky). According to the definition, we must now seek further information about Twirpy and Twinky which will justify our mapping these Nodes into each other. The Fact F presents itself as information about Twirpy; the sub-Situation of s 2 consisting of the Kernel <membe~ Twink; parakeet3> constitutes a Fact about Twinky, The definition r equires that these two Facts be Analogous, given the identification (Twirpy,Twinky), which is the case since they in fact become identical under that substitution, We may diagram the Analogy between s 1 and s 2 as :

'

As complex as the definition above may seem, it is still far too simple to be adequate for the analogy-formation situations that arise in the actual modeling of cognitive processes, Below we will mention several extensions which must be made to this definition, None of these el aborat ions will be pursued in the present paper.

It may occur that two Situations will match closely except for a corresponding pair of Nodes such that no additional information is available for one or both of these Nodes, In such a case one would probably want to risk identifying the two Nodes , especially if they were of low Criteriality. It will also occur in gener al that only a subset of one Situation can be mapped into a subset of the other. Whether or not the presence of unmatched Kernel s voids the analogy must depend on their number and their Criterialities . We see, then, that a working definition of analogy must actually be based on a complex scoring function involving the number of matched and unmatched objects, their Criterialities, the depth to which the r ecursion must be pushed, and so on.

The intricacies of this definition multiply when we consider the need for recognizing similar­ ities which transcend simple Kernel- to-Kernel matching. For exampl e, the conjunct ion of the Kernels <eats 3 AA 3 B~> and <propert; AA 3 hungr;> should certainly match a single Kernel of the form <devours 3 cc3 DIY> · In fact, a single Kernel may even paraphrase a whole Rule, Clearly the notion of equivalence illustrated in Section II.C must be used to supplement the simple one-to-one mapping of Kernels on which our original definition was based,

There are other ways in which situations may be said to be analogous, besides corresponding directly. They may, for example, have similar consequences: eating cyanide and jumping off a bridge are very different activities, but they are analogous inasmuch as they have similar results. Or two situations may have similar antecedents : a rainbow and a puddle are quite dissimilar, yet both betoken the occurrence of rain. Since these other types of analogy involve the notion of consequence, they too may be defined in our system.

to offer the best insight so far available into what makes an analogy "meaningful" and useful .

c. Uses of Analogy Formation in Cognition

We may distinguish two major functions which analogies can perform in cognitive processing : they provide a means of dealing with novel situ­ ations, and they serve to arrange semantic infor­ mation in an organized structure suitable for further processing. These two uses of analogy formation are of course aspects of one and the same process, but we may discuss them separately.

Response to Novel Situations. We have mentioned (Section II.A) that a Rule may be regarded as a routine for behavior written in a "pattern- operation" language. If we pursue such a notion, we soon realize that "left-half matching" for Rules is not at all a straightforward process, since we very seldom encounter the same situation twice, and we are often called on to respond to situations which are only vaguely similar to those we have met before , Evidently this idea of "vaguely similar situations" can be made precise by our definition of Analogy between Situations . This suggests the following prediction paradigm for dealing with

novel Situations:

We make an Analogic mapping M between the given Situation and the Left Half of a Rule taken from memory, We then apply the inverse of the Analogy to the Right Half of the Rule, to obtain a prediction of what will happen next,

Exactly the same operation can be applied to derive overt responses, as soon as we are provided if we let " ( --- )" denote an instruction to a

definitions we have discussed is that they are only with a formalism for representing them, That is, produced will be semantically meaningful - i.e. that perceptor or effector, then we have:

We might consider this as a crude model of "Stimulus-Response" behavior, including the phenomenon of "stimulus generalization" . The

An inherent limitation of all the various syntactic; they cannot ensure that the analogies the Justifying Information will in fact be "relevant" , These definitions must be regarded mer ely as the syntactic "necessary conditions" for analogy, wher e the mustering of truly relevant information is the responsibility of the larger process which makes use of analogy formation as a subroutine. The investigations of Kling [15] seem paradigm might also be said to model the "assimilation of schemata" central to Piaget [23], where we identify the notion of "schema" with that of "Rule".

Organizing Information from Memory. As can be seen from Figure 6, an Analogy, once formed, presents a goodly amount of information in a very organized structure. This structure grows in an orderly way as levels of recursive Analogies are applied to the Justifying Information; the sets ~ become strung out in what we may call the Path of the Analogy. For exampl e, a diagram such as Figure 6, if extended by two levels of recursion, would look like:

The simplest way of gleaning information from such a Path is to take the unions s 1 u~ 1 u ··· and s 2 u~ 2 u... Note that semantically, SiUEiu ··· has the meaning of SiA~iA ··· , since a Situation is interpreted as the conjunction of the Kernels it contains. We will call the process of taking such unions ~ Compression.

The information provided by an Analogy is structured enough to serve as a starting point for many cognitive processes, including deduction. In the next section we will examine in detail the role played by Analogies in a process of inductive generalization.

IV. The Modeling of an Inductive Process

A. A Sketch of the Process

The cognitive behavior which we would usually term "generalization" is in general a complex problem-solving process, involving strategies of guessing, deductions from "general principles", and so on. In this section we will be discussing an operation which is very much simpler and more primitive; but which nevertheless seems to merit being called "inductive". We may describe this process very schematically as follows:

Suppose that ~ and ~ are two properties, behaviors, etc., and that for a number of entities X we observe Cfl:x: and ~X to co-occur. If enough such cases accumulate, and especially if ~ and ~ are ~ priori unlikely individually, we might attempt to explain their co-occurrence by postu­ lating that one entails the other, e.g. that ~ ~ ~ · That is, we generalize over the individual cases X to postulate: Vx [~ ~ ~ ] · X X This proposed law may be tested by finding new cases Y for which ~ , and noting whether or not the prediction of ~y is satisfiedo The formation and testing of such generalized implications will be called the Generalization-over-cases process .

If the induced rule is in fact successful, a logical next step is to consider the two new entities: ¢ = (xi ~x} and ~ = (xi ~x} · The generalization may now be rewritten as Vx [x€¢ ~ X€~ ] , which can be neatly compressed to: ¢ c ~ · Since ¢ and ~ are classes of entities, they are "concepts" in the traditional psychological sense, and the process we have just described is evidently a meaningful form of concept formation. Note that in the expression ¢ c ~ we have attained a "higher-order" relation which may be considered without reference to the individual cases from which it arose . This compression of an implication into a single higher-order predicate (in this case, "c") is mediated by an equivalence of precisely the sort illustrated in Section II.C · We will not discuss concept formation further in this paper, but it clearly can be represented within our formalism.

Although the above description may seem rather straightforward, the complete modeling of Generalization-over-cases is actually a very complex matter. Rather than attempt to present an immense algorithm abstractly, we will content ourselves with following in detail how the process might work in a particular example. This form of exposition has its perils, of course. The example probably would not work as described. It is some­ times difficult to distinguish properties of the particular example from the general behavior of the algorithm. And it is often not clear why, at a given point, one thing is done next and not another . For these deficiencies we can only beg the reader's indulgenceo With respect to the last objection we may note that in cognitive processes the factors which determine precisely what is operated on next need not be closely relevant to the operation itself (nor very interesting: e. g. the precise connectivity of the semantic memory at the time the process takes place) .

B. Example of Generalization-over-cases

For the purpose of clarity in our exampl e, we will not indicate Node-Criterialities except where we have particular interest in them. Where they are omitted, the r eader may assume they have the conventional value 3 ·

Phase I: The first structuring of information. Synopsis : Three Facts F 1 , F 2 , and F 3 exist in memory. A new Fact F 4 is found to be Analogous to F 2 , with F 1 and F 3 serving as Justifying Infor­ mation. By Path Compression two new Facts are formed : F 5 = F 2 AF 1 , and F 6 = F 4 AF 3 ·

Steps 1. 1-1.3 : At various times the following three Facts find their way into our semantic memory:

Step 1. 4: At some time, presumably whil e visiting Peoria, we notice that :

It would be possible simply to r ecord this new Fact without analyzing it further , but we seldom r ecord input without trying to "understand" it . One aspect of understanding a novel situation is to relate it to something already known. In our model, this means to f ind an Analogy with some Situation alr eady in memory.

Step 1. 5: We seek an Analogic match for F 4 in memor y, and propose F 2 as a candidate, with M = ((BB,AA);(Cyrus,Wilfred)} · The correspond­ ence (BB,AA) is justified by <member BB suspenders> and <member AA suspenders> (also by the shared property of r edness) , ivhile the ident ification

(Cyrus,Wilfred) is justified by F 3 and F 1 · Sad to say, the Kernels <time@ Thursday> of F 2 and <location @ Peoria> of F 4 map neither into each other nor into anything else .

When a Kernel is not immediately matched in what is an otherwise promising Analogy, a search is instituted for information that will correspond with it. We would, for example, search memory (or, if possible, the r eal world) to determine whether or not F 4 was occurring on a Thursday. I f such information is unavailable and the Kernel must r emain unmatched, this fact must duly be taken into account in scoring the Analogy (recall Section III. B) . Even i f the Analogy i s accepted, this failure to match will affect further pr ocessing (Step 3 .3) . Let us assume that in our example these two Kernels go unmatched, but the Analogy is accepted anyhow.

The mere construction of the Analogy does not in itself produce anything that we would be willing to call the "under standing" of the new Situation. What is significant is the structuring of the four previously unrelated Facts into a Path of Analogy:

Step 1. 6 : Our Analogy, in relat i ng F 2 to F 1 , suggests that these two Facts about Wilfred may somehow be "relevant" to each other. It seems reasonable to commemorate this r elat ionship at least by r ecording a new Fact which is their conjunction: F 5 = F~F 1 · We note that syntactically F 5 is merel y the union of F 2 and F 1 , and so we have just performed the operation of Path Compression defined in Section III.C · Written explicitly, F 5 is:

Analogously, we form F 6 = F !('F 3 ·

Phase II: The Analogy perpetuates itself. Synopsis: A new Fact FB is encountered and found

to be Analogous to F 5 · The formation of the new Analogy is facilitated by a remnant of the old Analogy (namely the copy of F 1 embedded in F 5 ), which allows the pr ediction of a Fact F 7 which serves as Justifying Information . A new Path Compression forms F 9 = FeAF 7 ·

Step 2.1: At some point we r ecord that:

F 7 : (<member Rupert fireman> :3} ·

Step 2.2: Later, at the Firemen's Ball, we are keeping tabs on Rupert when we suddenly notice that :

Presumabl y this observation is sufficiently striking that we will attempt t o "understand" it.

Step 2. 3 : A search is made through semantic memor y f or Situations r esembling F 8 . Let us suppose that F 5 happens to present itself as a can'didate f or matching.

Step 2 . 4: In constructing an Analogy between F 8 and F 5 ther e are three unmatched Kernels: <dances-with Rupert Maude> i n F8' and <time @ Thursday> and <member Wilfred fir eman> in F 5 · As noted in Step 1.5, each of these induces a search thr ough memor y for corresponding information. I n this case, the first two left­ overs presumably f ind no match, but happily the Kernel <member Wilfred f ireman> does r etrieve an item f rom memor y, namel y F 7 · The Path which just i f i es the identification (Rupert,Wilfred) is ther efor e :

( .. Rupert . . }

There is a significant improvement in the way in whi ch the "firemanhood" Justifying Information was found here, in contrast with Step 1.5 · In the Phase I Analogy, the Facts relating Cyrus and Wil f r ed were turned up by a poorly-guided or non­ guided search. In this new Analogy, on the other hand, the Kernel <member Wilfred fireman> served as a clue to search for a specific item, namely the corresponding Fact (<member Rupert fireman>} · Recall that this Kernel was descended of F 1 via the Phase I Analogy. Thus the old Analogy has greatly facilitated the formation of a new Analogy similar to it.

Step 2. 5: A new Path Compression gives us yet another Fact :

Phase III : Conjunction is r estructured into implication. Synopsis: The successful pr ediction of F 7 triggers a re-exami nat ion of the Facts F 5 , F 6 , and F 9 , which ar e found to be mutually­ Analogous conjunctions . The conjunction is split up and r eorganized as two tentative implications (Rules) R 1 and ~' one goi ng each way. The Criterialities withi n R 1 and ~ ar e based on information provided by the Analogies among F 5 , F 6 , and F 9 ·

Step 3.1: The successful sear ch for F 7 in Step 2.4 may be r egarded as a "prediction" that Rupert is a fir eman. Since "Rupert" and "fireman" ar e both low- f r equency concepts, the success of this pr ediction may be so surprising as to cause us to re-examine the conjunctions which F 5 and F 9 represent. In particular, we search memory for other similar (Analogous) items, and turn up F 6 Step 3.2: We r econstruct the three Analogies among F 5 , F 6 , and F 9 · The three are parallel to each other, thus :

Step 3.3: Picking one of these Facts as typical, 1 say F 9 , we now convert its conjunction into a pair of implications, thus implicitly following the reasoning of Section IV.A · These implicat ions will of course be represented as Rules. We will have basically, but not exactly: R 1 = F 7 ... F 8 and ~ = F 8 -+F 7 · We must now consider the modifi­ cations to be made to F 7 and F 8 before they ar e combined into R 1 (the story is identical f or R 2 ).

1/ The arbitrariness of this choice, and of many other aspects of the process we describe her e, reflect the almost total l ack of psychologi cal data on which to base the al gorithm. Hopefull y, future studies along the lines of Posner and Keele [24] will eventually enable us to make far more accurate models of when and how generalization takes place.

Analogi es, as we have said, are a superb source of inf ormation, and there is a great deal of infor­ mation l eft in the Analogies made in Step 3 .2 that can cont ribute to the content of R 1 examination of these Analogies will determine the Criterialities of the various parts of R 1 , as follows .

Node-Criterialities : The thr ee Facts F 5 , F 6 , and F 9 differ significantly only in the two triplets of corresponding Nodes : Wilfred, Cyrus, Rupert; and AA, BB, CC · Clearly these ar e the ~ which the Analogi es gener alize ~· It appears that the presence of one or another of these Nodes is not crucial to the general law which unites the three Facts . Ther efor e, by definition these Nodes ar e less criterial to R 1 than those Nodes which are constant over all t hree Facts.

Step 3.4: The data structure requires that the new Rules R 1 and ~ be a ssigned Subjective Probabilities . Since we have as yet no r eason t o pr efer one of these Rules over the other, their init i al S.P.'s In particular, should be equal. We might assign init i al values of ~ , and t hereafter treat the S. P. a s the r atio of number of suc:es~es when the Rule is used number of predict1ons predictively (as below) . This particular treatment of S. P. ' s , and the particular scheme we use in adjusting Criterialities, were concocted for illustrative purposes in present ing this example ; the actual manipulations must of course be more subtle.

Kernel-Criterialities: The Kernels which never found Analogic matches have shown themselves to be dispensable in, or per haps even irrelevant to the gener alization which underlies the three Facts. They thus are less criterial to R 1 than those Kernels which f ound mates in all thr ee Analogi es .

Thus, in assembling R 1 f rom F 7 and F 8 we i ncr ease the Criterialities of those structures which through their constancy give evidence of being r elevant to the Rule, and decrease the Criterialities of those structures whose presence shows signs of being i nessential. Given that all of the Node-Criterialit i es wer e originally 3, the new Rule R 1 will be as shown in Figure 17 (above).

We should mention that these adjustments of Criteriali t i es, like everything else in life, are falli ble. It mi ght have happened, for instance, that by coincidence both Wilfred and Rupert were observed t o wear r ed suspenders on a Thursday. We as sume that with the accumulation of evidence (as in Phase IV below) , such coincidences will wash out of the inductions .

Phase IV: New evidence argues for a generalization, Synopsis: A new Fact F 10 is matched Analogically with the Left Half of R 1 · The inverse of the Analogy is applied to the Right Half of R 1 to obtain a predicted Situation. This Situation is in fact observed, and R 1 is r ewarded for its success . Step 4. 1: At some arbitrary time after Phase III has taken place, a new Fact comes to our attention: F 10 : (<member Otis fireman> :3} ·

Step 4.2: In an attempt to understand F 10 , we seek an Analogic match for it in memory. Suppose that the Left Half of R 1 comes up as a candidate for matching . Although we have no Justifying Infor­ mation for the identificat ion (Otis,Ruper t) , the Situations are otherwise identical, so we may assume that the Analogy is accept ed.

We are now in a position to follow the "predi ction paradigm" of Figure 7· That is, we may apply the inverse of our Analogy, namely the mapping M-l = ((Rupert,Otis)} , to the Right Half of R 1 to obtain a Situation which we may expect t o observe or to find already r ecorded in memory.

Step 4.3: The application of M-l t o the Right Half of R 1 encounters an interesting dif fi culty. This Right Half contains a Node, CC, whose law Criter­ iality indicates that it has been generalized over, - 1 We would expect the Analogy M again to map CC

i nto some other Node, but M in fact provides no Analogy formed between the Right Half of R 1 and the (Note that the translations of quantifiers in terms zero relevance has no place in a Situation. The

-1 such Node . Hence in this and similar cases we are l ed t o predict the existence of ~ entity i n the new Situation, corresponding in this case to ee . of Dummies (Figure 3) arise f rom just this sort of argument .) We may optimistically create a name f or our new entity, say XX. We thus predict a Situation of the form:

The Kernel-eriterialities here, which are taken from those in the Right Half of R 1 , assume a new role : they indicate the zeal with which we should seek a realization of the given Kernel. That is, the dominant eriteriality of <:wears otis XX> tells us that our main job is to l ook for something otis wears; the low eriteriality of <dances-with otis Maude> suggests that we should not give much concern to finding such a condition, since this Kernel is under suspicion of being irrelevant to the prediction.

Step 4.4: We may search for the predicted Situation in our semantic memory or in the r eal world. If it is i n fact true that all firemen wear red suspenders, then we will indeed find such a Situation. We will find an object to which we can attach the name XX, and in all likelihood there will be no match for

the Kernel <dances-with otis Maude> · Step 4.5: This successful prediction gives us valuable information with which we may adjust the Rule R 1 · We may raise and lower Node- and Kernel-eriterialities in accordance with the pr edicted Situation. In particular, the unmatched Kernel <dances-with Rupert Maude> attains a eriteriality of 0 and disappears, since a Kernel of successful prediction of course increases the Subjective Probability that the Rule is a valid one. Thus from R 1 we derive a new Rule Ri, shown in Figure 19 (below).

Steps 4.6+: After enough r ecurrences of Steps 4.1-4.5, our successful induction will approach the form shown in Figure 20 (below). Her e the zero eriterialities of the Nodes "Rupert" and "ee" indicate that these occurrences have completely lost their identities and become Dummies. Like dummy variables in mathematical notation, these Nodes could be r eplaced (consistently, of course) by any symbols, e.g. "x" and "y". In view of the transl ation between Dummies and quantifiers given in Figure 3, Rl expr esses precisely the proposition:

Which is to say, "Firemen wear red suspenders."

Phase V: New evidence may argue against a gener alization. We recall that a Rule ~ was formed along with R 1 , and is its converse. The statement made by ~ is that "If a person wears red suspenders, t hen he is a f ireman" . Although this proposition is false in the absolute, it will be worth r etaining if its statistical validity is significantly greater than zero. Therefore we will reward this Rule as per Phase IV when it succeeds, simply adjust its Subjective Probability when it fails, and expunge it if the Subjective Probability

falls below some threshold. In this way our model becomes capable of retaining "half-truths" - a capacity which is very valuable to a semantic memory (among other things, it allows the storage of contradictory information).

V. Discussion

A. The Relation Between Analogy and Generalization of arbitrary decisions in designing an algorithm.

If we examine the Generalization-over-cases process closely, we find that an interest ing statement can be made of the relation between analogy and generalization. In Step 3.3 we saw how a great deal of information supplied by Analogi es was incorporated into the representation of the generalized Rule. Thus, analogy takes part in generalization. But in Phase IV we found that the induced Rule led to the search for a Situation which was in fact Analogous to previously-known Facts, and which might have gone unnoticed if the inductive generalization had not existed. Thus, There are other factors which complicate the issue of what should be done when and for how long . In the first place, many cognitive processes contain no inherent termination condition. Like memory search or the construction of Analogies according to a recursive definition, they are bounded only by the size of semantic memory. In the second place, a cognitive operation is seldom totally successful or totally unsuccessful. As in generalizations facilitate the finding of new our discussion of Analogies, success must be analogies. In fact, the search for the new Analogy defined by a scoring function and threshold. These was guided by precisely that information which had considerations would seem to imply that a general been contributed to the Rule by the old Analogy cognitive process cannot be represented as an (i.e. Criterialities, see Steps 3.3 and 4.3), so we orderly succession of tidy operations, but instead might say that analogies perpetuate themselves via must be couched in a welter of effort-limiting and generalizations. On the other hand, we could also summarize Phase IV by saying that generalizations perpetuate themselves via new analogies. In any case, we have certainly shown that analogy and generalization are mutually r einforcing processes which can hardly be separated from each other. evaluation heuristics.

B. Problems in Modeling Cognitive Processes

We are at present attempting to construct a computer implementation (in the LISP language) of the processes outlined in this paper. Such an effort necessarily leaves one sadder but wiser with r egard to the prospects for formulating and testing explicit cognit ive models. In this section we will discuss some of the more forbidding obstacles we have encountered. We feel that the problems brought out below correspond not to deficiencies in our particular model (although there are enough of those, heaven knows), but rather to major dilemmas attending the construction of ~ general cognitive model in a large semantic memory system.

We have already mentioned that the choice of "what to do next" in a cognitive process ls often poorly specified, Because of the extreme scarcity of psychological data regarding such choices, the model builder is confronted with a small infinity The cumulative effect of these low-level choices may well wash out the central theoretical propo­ sitions that the model was designed to test .

Of all of the issues we have sidestepped in Sections III and IV, certainly none is mor e worrisome than the problem of memory search. Not only must r elevant information be brought forth, but this must be done without exhaust ive sear ch (i.e, rapidly), despite the fact that 99% of the contents of memory will be irrelevant to the given search. Moreover, the phenomena of "set" and "effect of context" show us that in human memory the memory structure (or, equivalently, the means of search access into it) is continuously adapting in response to ongoing cognitive activity. Certainly no process involving a large, general semantic memory can be adequately modeled until some progress is made on this most ref r actor y set of problems.

The necessary size and intricacy of a semantic memory create a host of methodological problems in validating the algorithms which operate in such a system. It becomes extremely time-consuming to construct a suitable data-base on which to test an algorithm - especially if that data-base is to be r ealistic in being 99% irrelevant to the test problem, Sometimes it becomes very difficult to distinguish which properties of a program's behavior are inherent in its algorithm, and which stem from its interaction with the particular test data-ba se used. In addition, any algorithm will contain dozens of arbitrarily-set parameters and ar bi t rarily-made decisions. Ideally, one would linguistics, The linguist (not to be confused wi th the metatheorist, or prophet) spends his time trying to model particular aspects of a particular language, e.g. negation or nominalization, He does not have a complete grammar of the language available to him, nor does he attempt to construct one, He knows that his limited model is guaranteed not to be fully consistent with empirical obser­ vations of language, because in language too it is impossible in r eality to isolate one aspect f rom all the others. In the face of a host of counterevaluate these by varying them one at a time, using examples, exceptions, and phenomena not covered by a lar ge number of test data-bases, but such a his model, the linguist calmly decides to judge procedure is out of the question in practice, the worth of his theory by subjective criteria such as internal elegance and explanator y power. He is happy with a model i f it gives him ~ better We hope that the model presented in this paper gives the reader a better understanding than he had before.

Many of the ideas put forth in this paper rightfully belong either to Jerome Feldman of Stanford University, or to Ross Quillian of Bolt Beranek and Newman Inc, I would al so like to acknowledge my great personal indebt edness to these two gentlemen. This research was originally inspired by Kenneth Colby of Stanford, and he has contributed much to the model. I am most gr ateful to Daniel Bobrow of Bolt Beranek and Newman, and to Nils Nilsson, Bertram Raphael, and Charles Rosen of Stanford Research Institute for their encouragement and for the opportunity to use their computing machines in developing the LISP imple­ mentation of the model.

• [l) Quillian, M, Ross, "Word concepts: a theory and simulation of some basic semantic capabilities," Behavioral Science, 12(5), Sept. 1967, 410-430 -
• [2) Quillian, M, Ross, "The Teachable language Comprehender: a simulation program and theory of language," Jan. 1969 (forthcoming)

The ultimate problems in validation arise when one strives, as we have striven, to characterize general "subroutines" of cognitive behavior, understanding than he had before. r ather than attempting to build a beginning-to-end model of a particular type of performance in a well-defined cognitive task. The processes of Analogy formation, Generalization-over-cases, and the prediction paradigm of Section III.C are not by themsel ves sufficient to model ~ particular cognitive behavior. They are intended rather to represent elementary sub-processes which may be observed to participate in a very wide range of psychologi cal phenomena, from sensory perception to natural language understanding, Our approach is in accord with the venerable programming dogma that the best and often the only way to come to grips with a complex process is to decompose it into easily-conceptualized. subroutines , Certainly this law must apply to that most complex of processes, human cognition. But the question immediately arises of how one is to validate a proposed algorithm for a "cognitive subroutine". It is essentially impossible for experimental techniques to provide data on a single cognitive sub-process t aken in isolation from all others, But with no data as to how the subroutine is supposed to perform, one cannot even debug a proposed algorithm, much less validate it! Acknowledgments References

Is it not intolerable, in a scientific investigation, to be asked to consider models for which empirical validation is next to impossible? We think not. Consider the situation in

• (3] Simmons, Robert F.; Burger, John F.; and Schwarcz, Robert M. , "A computational model of verbal understanding," SP-3132, System

• Development Corporation, Santa Monica, Calif., April 1968
• [ 4] Kellogg, Charles H., "A natural language compiler for on-line data management ," Proceedings, Fall Joint Computer Conference, AFIPS, Dec. 1968, 473-492
• Woods, William A., "Procedural semantics for a question-answering machine," Proceedings, Fall Joint Computer Conference, AFIPS, Dec. 1968, 457-471
• Kochen, Manfred, "Automatic questionanswering of English-like questions about simple diagrams," Journal of the ACM, l6(l), Jan. 1969, 26-48 -
• Green, C. Cordell and Raphael, Bertram, "The use of theorem-proving techniques in question-answering systems," Proceedings, 23rd National Conference, ACM, Aug. 1968, l69-l8l
• McCarthy, John, "Programs with common sense," Memo No.7, Stanford Artificial Intelligence Project, Stanford, Calif., Sept. 1963
• Black, Fischer, "A deductive questionanswering system," in Semantic Information Processing, Marvin Minsky ed., MIT Press, Cambridge, Mass., 1968, 354- 402
• Bartlett, Sir Frederic c., Remembering, Cambridge University Press, Cambridge, England, 1932
• [ll] Oldfield, R. C., "Memory mechanisms and the theory of schemata," British Journal of Psychology, ~ 1954, 14-23
• [ 12] Colby, Kenneth M., "Computer simulation of change in personal belief systems," Behavioral Science, l2(3), May 1967, 248-253
• [l3] Abelson, Robert P. and Carroll, J. Douglas, "Computer simulation of individual belief systems," American Behavioral Scientist, 8(9), May 1965' 24-30 -
• [ 14] Evans, Thomas G., "A program for the solution of a class of geometric- analogy intelligence­ test questions," AFCRL-64-884, Air Force Cambridge Research Laboratories, Hanscom Field, Mass., Nov. 1964
• Kling, Robert E., "Reasoning by analogy with applications to logical pattern recognition," Ph.D. Thesis, Department of Electrical Engineering, Stanford University, Stanford, Calif. (forthcoming)
• Simon, Herbert A. and Kotovsky, Kenneth, "Human acquisition of concepts for sequential patterns," Psychological Review, 7.Q(6), 1963, 534-546
• Persson, Staffan, "Some sequence extr apo­ lating programs: a study of representation and modeling in inquiring systems," Technical Report No. CS 50, Department of Computer Science, Stanford University, Stanford, Calif., Sept . 1966
• Doran, James E., "Planning and generali­ sation in an automaton/ environment system," Presented to Fourth Machine Intelligence Workshop, Edinburgh, Scotland, Aug. 1968
• [l9] Hunt, Earl B.; Marin, J.; and Stone, F., E?q?eriments in Induction, Academic Press, New York, 1966
• Quillian, M. Ross, "A notation for repre­ senting conceptual information: an application to semantics and mechanical English para­ phrasing," SP-1395 , System Development Corporation, Santa Monica, Calif., Oct . 1963
• [2l] Lashley, Karl s., "The problem of serial order in behavior," in Cerebral Mechanisms in Behavior, L. A. Jeffress ed., Wiley, New York, l95l, ll2-l36
• Bendix, Edward H., "Componential analysis of general vocabulary: the semantic structure of a set of verbs in English, Hindi, and Japanese," International Journal of American Linguistics, 2_g(2), Part II, 1966
• Piaget, Jean, The Psychology of Intelligence, Humanities Press, New York, First published 1947
• Posner, Michael I. and Keele, Steven w., "On the genesis of abstract ideas," Journal of Experimental Psychology, IL(3), Part 1, July 1968, 353-363