Using Relational Operators to Structure Long-Term Memory

USING RELATIONAL OPERATORS TO STRUCTURE LONG-TERM MEMORY Alan L. Tharp and Gilbert K. Krulee The Technological Institute

Northwestern University Evanston, Illinois

(nouns) in natural language passages. The other class, denoted (2', cons.ists of words that are logical connectives: ·most of them are conjunc­ tions which, in traditional grammar, connect sen­ tences. The relational operators, e~, bind sentences into larger semantic units.

SUMMARY

This paper describes a system for "remember­ ing" a story or passage in English and for the subsequent retrieval of responses to questions. Although it functions as an information retrie­ val system, it is also intended as a model for long-term human memory. Information is stored in the form of predicates and property lists. In translating from natural language, the system carries out a transformational analysis of each sentence and identifies its deep structure inter­ pretation. This grammatical analysis is essential to the identification of the predicates as well as relationships among them.

The first two subsystems carry out the gramma­ tical analysis. A third identifies the predi­ cates and property lists, determines a time and priority structure, forms a logical ~ap of rela­ tionships among predicates, and eliminates some predicates based on an assignment of priority. The fourth subsystem is used to answer inquiries about the stored information.

The method is illustrated with references to one story that has been processed and with ex­ amples of questions that might be asked.

Keywords and phrases: Memory, information retrieval, relation, relational operations, pre­ dicate, information retrieval, questio~-answering system.

This paper describes an information retrieval system although it may also be interpreted as a simulation of long-term memory. More specifical­ ly, the system simulates the ability to read a story or some form of connected material written in English, to store a representation of that story, and later to be able to answer questions about it based on the ability to recall.

In designing this system, we have been influ­ enced by some related studies which have used an intermediate formalism for the storage 1 of infor­ mat~on. ~uch syst~ms inclu~e BASEBA6L , SAD SAM , SIR , DEACON , ALTAI~ , SAFARI , 8 and the systems 9 developed by Woods , Rosenbaum , and Hillman · The relative success of these efforts indicates that an intermediate formalism is an important part of the simulation. In addition, each of these systems accepts natural language (English) inputs. The system described in this paper also allows natural language inputs and uses relational operators as an intermediate for­ malism.

A relational operator connects two entities in a qualitative manner. Two classes of rela­ tional operators are used in constructing the model. The first class is denoted e and con­ sists of verbs, which usually join entities The first level formalism of a predicate logic is used to represent each sentence of an in­ put passage. The relational eperators are the key elements in the predicates, which provide the basic memory structure for the model. A sentence may be transformed into a ~wo-place predicate which i:s written e (. d> (3 J' where e is the re la­ tional operator, d> is the deep structure subject of the sentence, and d is the deep structure ob­ ject of the sentence. If d> is null, the sentence is imperative. If I is null, the sentence is in­ transitive. If d> and (3 are both null, the predi­ cate represents a participle used as an argument of another predicate.

Sentences joined by the relational operators, e ' are treated as n-place predicates, where n is the number of sentences connected by a speci­ fic operator. For example, the linked.sentences "S 1 , and s 2 , and s 3 " may be represented:

Some operators which connect sentences have pre­ cedence over others. For example, the relational operator "implication," represented by the logi­ cal connectives "if ·.· then," is more binding than the relational operator "and."

In translating from natural language into a series of predicates, the system carries out for each sentence a transformational analysis and assigns to each a structural description repre­ senting its deep str~5ture interpretation. (See Jacobs and Rosenbaum for a detailed description of transformational theory which includes the concepts of deep and surface structure.) '!-fue jt!J&<'I t5.fiMJ-I!ion for this grammatical analysis is essen­ tially as follows. Given a kernel sentence, one can easily translate from English into a predi­ cate. Kernel sentences are closely related to active declarative sentences such that the verb names the predicate and the subject and possibly the object of the verb become the arguments of the predicate. When transformations are applied to kernel sentences, they complicate the rela­ tionship between sentence and predicate. For example, the passive transformation reverses the order of the arguments; by using more complex transformations, one creates sentences which may contain two or more kernel sentences. Given a deep structure interpretation of a sentence, one can readily identify the kernel sentences as well as the relationships among them and the process of translating into a series of predicates is facilitated.

The system has been used to process chil­ dren's non-fiction storles about famous inventions taken from Childcraft 11 ~d makes use of four sub­ systems. The EDIT component accepts passages which have been manually translated into a re­ stricted subset of English, and these restrictions are necessary because of the limiations inherent in the second subsystem for carrying out the gram­ matical analysis. (The appendix contains the translated form of the passage "What a Bother.") EDIT replaces pronouns with their corresponding nouns according to the heuristic "replace a pro­ noun with the most recent noun of the same gen­ der." The pronouns may have referents across sen­ tence boundaries. EDIT then isolates the senten­ ces and forms a map to record the logical rela­ tionships among them.

In the second subsystem, Petrick's recogni­ tion procedure PI2grf~ed in LISP for transformational grammars ' is used to assign structural descriptions to the input sentences isola­ ted by EDIT. Before the sentences can be ana­ lyzed, however, it is necessary to apply manually an inverse number agreement transformation and an inverse verb-affix transformation. In addition, words such as participles, plurals, and verbs in the past tense have to be separated into their constituent morphemes before the analysis can be performed. Although the grammar chosen for the system was the most extensive one available at the time, it contains many features which limit the class of sentences that it can process. The gram­ mar cannot handle such it~ms as sentence fragment~ possessive or reflexive pronouns, most preposi­ tional .phrases and its ability to handle adjec­ tives and adverbial phrases is limited. Clearly, the capabilities of the system could be expanded by the elimination of these and then restrictions from the grammar.

Within its limits, the recognition procedure ass igns to the sentences structural descriptions representing their deep structures .. For example, the sentence, "The store-owner shoved the papers," would be assigned the structural description:

Sl9(NP(DET(DEF THE))(N STORE-OWNER)) (AUX(AUXA(TNS PAST)))

(VP(V SHOVE) (NP(DET(INDEF S)) (N PAPER))).

This LISP S-expression corresponds to the tree di agram l n ·Flgure 1.

The symbols used as nodes in the tree structure are defined in Table 1. The symbol "Sl9" speci­ fies that the structure describes the nineteenth sentence in a passage.

s - sentence

NP- noun phrase

AUX- auxiliary

VP - verb phrase

TNS - tense

V - verb (non-copula)

EE - verb (copula)

NDUM - dummy noun NPROP - proper noun NOM - nominative DET - determiner DEF - definite INDEF - indefinite N - noun IT - dummy introduc­ ing an embedded sentence

Table 1

DIGEST, the system's third component, has two sections. The first segment of the routine forms property lists and predicates and assigns priori­ ties to the predicates. DIGEST scans the struc­ tural descriptions of a sentence, such as the one above, and searches for the verb. If the verb is a copula ( BE), the structural description is con­ verted into a property list. If the verb is not a copula (V), the structural description is con­ verted into a predicate. The second segment orders the predicates and then condenses and el i ­ minates information.

To illustrate how DIGEST operates, the struc­ tural description of the sentence represented in Figure 1 will be converted into the intermediate formalism. The structural description is decom­ posed into a noun phrase

(DET(DEF THE))(N STORE-OWNER),

an auxiliary

(AUXA(TNS PAST)),

and a verb phrase

(V SHOVE)(NP(DET(INDEF S))(N PAPER)).

The noun "store-owner" is isolated from the noun phrase and becomes the first argument of the pre­ dicate.

The verb phrase is decomposed into the verb "shove" and the noun phrase (NP(DET(INDEF S))(N PAPER)). The verb is the relational operator which will be used in the formation of the predi­ cate. The noun "paper" is isolated from the second noun phrase and is labeled as argument two of the predicate. With the second argument iso­ lated, the predicate representation of the sen­ tence is complete:

predicatel9 = shove(store-owner,paper).

Instead of forming a predicate, DIGEST forms a property list if the sentence, such as "The era­ ser would be handy always," has a copula verb.

The recognition procedure would assign to the sen­ tence the structural description:

The noun "eraser" is isolated from the noun phrase, and the auxiliary is again ignored.

S35(N (DET(DEF THE))(N ERASER))(AUX(AUXA(TNS PRES) (M WOULD)))(VP BE(PRED(ADJ HANDY))(ADVB ALWAYS)). A tree diagram corresponding to this analysis ap­ pears in Figure 2.

The structural description is aga:ln decomposed in­ to the noun phrase

(DET(DEF THE))(N ERASER))~

the auxiliary

(AUXA(TNS PRES)(M WOULD),

and the verb phrase

BE(PRED(ADJ HANDY))ADVB ALWAYS).

When the verb phrase with the copula is de­ composed, the adjective "handy'! i s isolated as a member of the class "PRED," and the adverb "al­ ways" is also isolated. In forming the property list, both the adjective and the adverb are consi­ dered as values of the attributes which they des­ cribe. How these attributes (properties) are categorized is expla i ned in the discus s i on of DIGEST's lexicon. The adjective "handy" speci­ fies the property of expedience; while the adverb "always" specifies the property of frequency. The noun "eraser," isolated previously, is la­ beled as the name (head) of the list. The pro­ perty list formed is

eraser,(expedience,handy)(frequency ,always).

The property list is compared with all pre­ viously formed property lists, and if an identical list exists, no action is taken. However, if the list is a new one, it is added to the set of pro­ perty lists for the passage and labeled with the letter "L" followed by an identifying number. The system will process more complicated sentences such as "The store-owner who was Hyman Lipman sim­ plified wirting using a pencil." The structural description for this sentence is given in Figure 3 and from it a suitable series of predicates and property lists will be obtained.

__---s The lexicon (internalized dictionary) for DIGEST, which is used in the preparatory segment of the rout-in:e, has two classes of entries: one for adjectives and adverbs, and one for verbs. The definitions of adverbs and adjectives are used in forming property lists; while the definitions of verbs contain information for assigning priori­ ties to the predicates DIGEST has formed.

The entries for adjectives and adverbs are constructed on a principle similar to that used in constructing a thesarus. A thesarus, rather than defining words, groups them on the basis of simi­ larity into approximately 900 categories. In set­ ting up the lexicon for DIGEST, a more stringent requirement was established: the categories would be mutually exclusive. Since an adjective or ad­ verb may then appear in one and only one category, assigning words to categories tends to be diffi­ cult and somewhat arbitrary. The categories cho­ sen are £embinations of the categories in Roget's Thesarus · For example, the two categories, heat and cold, were combined into one named "heat;" cold is the lack of heat. Each dictionary entry consists of the word, its part of speech (either adjective, ADJ, or adverb, ADV) and its attribute category.

Verbs provide the second type of entry in the lexicon for DIGEST. The entry consists of the verb, a notation which indicates whether it is transitive (VT) or intransitive (VI), and a pri­ ority number which indicates the relative impor­ tance of the verbs in a passage. DIGEST uses this priority number along with several other factors in order to provide an index of the rela­ tive importance of each predicate in forming the memory structure. To the best of our knowledge, no empirical data exists to support our procedure for the assignlll!nt of priorities; it should be interpreted as an educated "guess" about how one might evaluate the relative importance of each predicate in a given passage. The following fac­ tors are used in the assignment of priorities.

• (a) Syntactic class of the verb: transitive verbs are more important than intransi­ tive verbs, which, in turn, are more impor­ tant than equational verbs (be, become, feel, seem ··. ) .

16

• (b) Semantic class of the verb (Katz): acti­ vity verbs (eat, speak, walk) are more important than process verbs (grown, freeze, dress), which in turn are more important than state of being verbs (s leep, wait, suffer).
• (c) Semantic sub-class of the verb: verbs of a physical nature (chase, run) are more important than verbs of a mental nature (think, remember) within the same seman­ tic class.
• (d) Attachement of a preposition to the verb: a preposition attached to a verb reduces the verb's transitivity or forcefulness.
• (e) Number of meanings of the verb: .the informa­ tion content of a verb is inversely propor­ tional to the number of its menaings.
• 16· (f) Frequency of use of the verb (Kochen) the information content of a verb is inversely proportional to the frequency of its use.

After the individual verb (relational opera­ tor) priority numbers have been assigned and stored in the lexicon, they are used i n DIGEST's computation of sentence (predicate) priorities. Three other factors, in addition to that of rela­ t i onal operator priority, are also used in deter­ mining predicate priority.

These are the precedence level of the rela­ tional operators (if .·. then, and, or, etc.) as previously defined; the location of a sentence in a passage with those at the beginning and end re­ ceiving a higher priority and higher priority is given to active sentences over their passive equivalents.

The assignment of predicate priorities, mak­ ing use of the formula

predicate priority=relational operator(verb) priority

+ relational operator ( ~ ) priority

+ location priority

- correction for passive

completes the first segment of the DIGEST routine.

Condensing the predicates into the most eas i ­ ly remembered information involves several dif­ ferent processes. The predicates are first or­ dered in a time-priority structure for the ini­ tial elimination and condensation. To determine the most important person of the passage, the pre­ dicates are then represented as a connected graph . A centrality 1 tndex as defined by Harary, Norman, and Cartwright is computed for each argument. This index is used in order to identify the most important person. The most important person has the highest centrality index while the main i dea is that predicate with the highest priority. After this determination, the predicates are ar­ ranged in a matrix for further elimination and final storage. The time and priority structure is a linear time axis on which the predicates and their assigned priorities are ordered. Along it, the tenses are ordered as follows: past perfect, simple past, present perfect, present, future per­ fect, and simple future. The auxiliary part of s sentence, isolated in the first segment of the routine and denoted by the symbol AUX, is inter­ rogated to determine the tense of the verb used in a sentence.·

fmce the tense of a verb is determined, the predicate which corresponds to the sentence con­ taining the verb is placed upon one of six tense lists. Each list is push-down: the most recent i tem added to the list appears at the top. After all the sentences of a passage have been conver­ ted i nto the predicate notation and placed on the tense lists, the lists are joined together in the r everse order of thP- tense listing above. The resulting ordering along a time axis produces the t i me and priority structure.

The completed time and priority structure is used twice in the condensation. First it is scan­ ned for predicates with priorities less than one­ half the largest priority . Since predicates with such low priorities are evaluated as not impor­ tant to the main or supporting themes in the pas­ sage, they are eliminated. Next, the time and priori ty structure is checked for identical predi­ cates. Since predicates that occur more often in a passage are more likely to be remembered, the priorities of identical paredicates are increased.

The predicates which remain after the initial condenstaion are converted into a series of con­ nected graphs, and from these graphs, the most important person, character, or idea in a passage is determined.

For the efficient retrieval, straight-forward revision, or simple addition of a predicate, the graph structure is stored in an n x m matrix, where n equals the number of distinct first argu­ ments of predicates in a passage, and m equals the number of distinct second arguments. The entry for each element of the matrix contains an ordered set of three fields. The first field de­ notes the name (number) of the predicate; the second, the name of the relational operator ( verb) joining the two arguments of the predicate; and the third, the predicate's priority number.

Once the information about the predicate is stored in the matrix, the final condensation can be made. To determine the final priority of the predicates, the most important argument is loca·· ted. For each predicate that contains this argu­ ment, the priority is increased. With the final priorities assigned, another search of the predi­ cates is made, and all predicates with priorities less than one-half of the largest priority are eliminated.

After the final condensation, the following information is then available from the DIGEST routine for use as a data base in the retrieval section of the system:

1. The matrix containing the information about the predicates,
2. The set of property lists,
3. The set of secondary (embedded) pre­ dicates,
4. The time and priority structure,
5. The logical map formed by EDIT, with predicate and property list names (numbers) substituted for the appropriate sentences.

Using the SNOBOL programming language and operating with a CDC 6400 computer, DIGEST's analysis of the passage "What a Bother" took 138.4 seconds to execute using 140,000 octal loca­ tions of computer central memory. The average time per statement was 8.8 ms.

In the fourth subsystem of the text-based information- retrieval system, information ob­ tained from the data base output of DIGEST is used to answer inquiries about the natural lan­ guage passages that were inputs to the EDIT rou­ tine. This retrieval routine has not been imple­ mented; instead, manual simulations of its func­ tions have been performed.

The routine accepts two kinds of inqui r j es: questions and imperatives. The quest i ons are in­ quiries about a single predicate whereas the imperatives are inquiries about the relations of one sentence (predicate) to another in the pas­ sage. The questions are parsed according to the same procedure used for the input passages; hence the questions must also be stated in the same restricted subset of EngHsh. One advantage of parsing over the keyword matching used in many retrieval systems is that parsing allows a ques­ tion to be phrased in several ways and yet be mapped into the same predicate. Mapping the ques­ tions into the same type of predicate used to represent the input sentences allows a straight­ forward method of retrieval. Since the impera­ tives, on the other hand, deal with more than one predicate, the predicate formalism obtained from the parsing output is not useful in answer­ ing the second type of inquiry. Hence keywords were used in analyzing imperatives.

Throughout the retrieval segment, inqu1r1es are answered individually. If an answer cannot be determined, the following is printed out: "I do not know the answer to your inquiry (question): could you please rephrase it." If an answer can be located, both answer and inquiry are printed out.

Inquiries seeking information from one pre­ dicate fall into two categories: the yes-no question and the WH question. As the name im­ plies, yes-no questions can be answered with either "yes" or "no." WH questions are intro­ duced by an interrogative pronoun (who, what, when, where, which) and are usually answered with a noun phrase. Both categories are subdivided into several question types.

Two types of yes-no questions are differen­ tiated according to whether the verb is a copula or a non-copula. When the verb is not a copula, the question is parsed and transformed into a predicate. The storage matrix is searched to de­ termine if the predicate exists. The element of the matrix indexed by the predicate's two argu­ ments is scanned to discover if it contains the predicate's relational operator. If it does, the answer is "yes;" if not, the answer given is "yes;" if not, the answer given is "no." If an element with the given indices is not found, the "I do not know" answer is printed out.

The other type of yes-no question, that with a copula verb, is also parsed, but it is trans­ formed into a property list instead of a predi­ cate. The set of property lists is searched to determine if a list with the appropriate name has the attribute-value pair specified. If a pro­ perty list with the given name is not found, the answer is, "I do not know."

The second major category of questions has six basic types. An interrogative pronoun from one of three functional classes introduces each WH question, which may ~Ave either a copula or non-copula verb. Sledd , whose classification has been used in the retrieval routi.ne, calls the wh words "interrogative words," rather than pro­ nouns, because they also function as adjectives or adverbs. Examples of these three functions

include:

1. pronouns "~ hit the ball?" "What did you see?" "Who is tall?"
2. adjectives "Which man is tall?" "What" man hit the ball?"
3. adverbs "When (where) did the man hit the ball?"

A WH question is converted into either a predicate or a property list, and an unknown is sought. If the verb is a non-copula, the question is conver­ ted into a predicate with the unknown as one of the arguments. The storage matrix is then searched for possible values of the unknown. If the verb is a copula, the question is converted into a property list whose listname is unknown. In this case, the set of property lists is scan­

ned for possible answers.

There are also inquiries which seek informa­ tion from a passage rather than from an indivi­ dual sentence in the form of imperatives which seek the semantic relation between the sentences (predicates) of the passage and imperatives which ask about the passage as a whole. A semantic re­ lation is the cause, implication, or other link that builds meaning from two or more sentences. Imperatives seeking such relations are answered primarily with information contained in the logi­ cal map (formed in EDIT). A typical inquiry about an entire passage, on the other hand, seeks such information as the main topic or outline. This type of inquiry is answered with information from the storage matrix, especially from the prio­ rities. An imperative inquiry is handled by locating the keywords in a command. The keyword "give" always introduces an imperative. Repre­ sentative examples of inquiries and responses for the passage "What a Bother" are given in· the appen­ dix. In addition, deductive capabilities could be added to the system as in the inf£~ation re2 0 trieval system of Green and Raphael Kuhns also has chosen a predicate logic to rorm the data base for his deductive proposal and his method of question answering by computer would use theorem­ proving techniques to deduce ·non-explicit answers from the data base. Such techniques of deduction could also be incorporated into this information­ retrieval system, since it also represents sen­ tences with predicates.

APPENDIX

"What a Bother" translated into the restricted

subset of English. 1

The store-owner could not find the eraser. He rummaged through the papers that were scat­ tered on the desk that he had been writing on. He frowned angrily as he shoved around the papers . He became impatient because ·the eraser was missi.ng.

The store-owner was tired and he was hungry because he had worked all day. He worked i n a store that sold stationery. But he could not go to the home until he finished figuring. He kept a record which told how many items were sold each

day.

As he finished writing in the book, all things went wrong. He made mistakes that needed erasing. As he reached for the eraser, it dis­ appeared among papers on the desk. It bounced

across the floor.

The store-owner groaned as he picked up the evasive eraser. He looked at the rubber piece he was holding.

He wasted some time as he looked for the era­ ser. Other people who use pencils must waste some time as they c~se erasers. Erasers should

be convenient as we are writing.

The store-owner picked up a pencil and he looked at the top. Pencils having erasers that fitted into tops could be made. If a small era­ ser was glued at the top that a pencil has, then it would be handy always when it was needed.

The store-owner who was Hyman Lipman simpli­ fied writing using a pencil.

• 1 original version from the 1968 Edition of Child­ craft--The How and Why Library, used with permis­ sion of Fi~ld Enterprises Educational Corporation.

• Note: 1f attached to an output indicates t hat a predicate with this information many have been eliminated by DIGEST.