Researcher: An Experimental Intelligent Information System

1 Introduction

In [Lebowitz 83a] we described the first stages of development of RESEARCHER, a prototype intelligent information system. RESEARCHER is intended to accept natural language input, patent abstracts in particular, and 1) understand the text, 2) add the acquired information to a long-term memory, generalizing as it does so, and 3) answer questions from its memory. In this paper, we will present an overview of the new areas that we are using RESEARCHER to study. In each of these areas we apply techniques derived from cognitive modelling approaches to language and learning. We are using people as our model to help us achieve better performance on very hard tasks (which, in return, gives us insight into the human processing methods).

2 Generalizing hierarchies

The patent abstracts that we have been looking at describe the physical structure of complex objects. Since such objects are most naturally represented as hierarchies of parts, our learning research has addressed the generalization of hierarchically structured descriptions. EXI is part of a typical patent abstract.

EXl - P81; U. S. Patent #4306258; Higashiyama Nobor et al.

A magnetic he~d supportin~. m~chamsm. equipfed w1th a magnet1c head positionmg carna~e o a interchangeable double side type flexible d1sc drive apparatus comprising a carriage having a pair of arms which is rotated in detachable to a double side type flexible disc and arms ...

*This research was supported in part by the Defense Advanced Research ProJects Agency under contract N00039-84-C-0165. Many people have contributed to RESEARCHER. In particular, the work on generalizing hierarchies has largely been conducted by Kenneth Wasserman and the work on question answering by Cecile Paris, co-advised by Professor Kathleen McKeown.

Our representation of patent abstracts such as this one includes three classes of information: 1) a parts hierarchy, that illustrates the components of each part; 2) interpart rdations, physical and functional relations between various components; and 3) properties of the objects. We have concentrated on the parts hierarchy and physical relations [Wasserman and Lebowitz 83]. We are currently working on classification schemes for functional relations and object properties (such as size and composition).

Full understanding r~q~ires that we integrate new representations with ex1stmg knowledge in memory. RESEARCHER has as one of its goals the incremental generalization of hierarchical descriptions of objects such as EX1 by finding similar examples in memory, comparing them with the new example, and abstracting out the similarities.

Generalizing hierarchical representations presents a number of difficult problems. Typical problems are: deciding how the components in the objects being compared correspond; dealing with differing Ievels of description of objects; and structuring memory so that maximally efficient inheritance of the sort used in semantic networks and frame systems (see [Barr et al. 82]) can be achieved automatically. In this paper, we will only give examples of how the generalization process works, and refer the reader to [Wasserman 85] for more details.

We can break generalization into two phases -- 1) when a new example is presented, deciding what other objects to compare it to (since RESEARCHER is not given examples designed to teach a specific concept), and 2) the comparison process itself, which abstracts out similarities.

We will Iook at the comparison process first, as it 1s involved in the search process. EX2 and EX3 are two simplified disc drive patents.

EX2 - A disc drive comprisin~ an enclosure surrounding the disc drive, sa1d disc drive including a spinning assembly, a disc and a readwrite head, said spinning assembly including a spindie connected to a motor, said enclosure comprising a cover on top of a support member.

EX3 - A disc drive comprising an enclosure surrounding the disc drive, sa1d disc drive including a spinning assembly, a magnetic assembly and a readwrite head, said spinning assembly including a spindie connected to a motor, said magnetic assembly comprising a disc, said enclosure comprising a cover on top of a support member.

A.s human understanders, we can easily see that patents EX2 and EX3 describe similar objects. However, to begin to generalize the similarities, RESEARCHER must decide how the parts of the representations correspond -- for example, that the enclosure in EX2 corresponds to the enclosure in EX3, and not to the spinning assembly, the magnetic assembly or the readwrite head, which are all parts of the disc drive in EX3. Here this is relatively easy, as the enclosures are identical, but we must be able to identify Jess perfect matches. RESEARCHER does this with a numerical scoring algorithm, similar to the one m [Winston 80].

Figure 1 shows RESEARCHER's generalization of these objects, taken from (Wasserman 85]. When RESEARCHER makes correspondences of the sort mentioned above, one problern arises in dealing with the discs. The disc in EX2 is described as part of the disc drive, while in EX3 the disc is part of a magnetic assembly which is part of the disc drive . To make the representations match, RESEARCHER must insert a "null" part, which may or may not actually exist in any given object. The two input representations are stored as variants of the generalized object, recording only how they differ from it (basically, in this case, how the null object is resolved; in real examples there would usually be more differences).

Even with just two hierarchical descriptions to compare, the matehing process involves a number of problems in determining how the components of the hierarchies correspond. One such problern is the need to insert Ievels in a hierarchy to obtain a good match, as described above. (While the insertion of a null Ievel by itse lf decreases the goodness of a match, it may increase the value of lower Ievel matches.) The problern is that there are an exponentially !arge number of places where null Ievels can be inserted, each requiring a complex recursive match to test. We have used RESEARCHER to experiment with a variety of different algorithms for deciding where null Ievels should be inserted for optimal matching, concentrating on ones that only try the most obvious places near the top of the hierarchy.

Since the examples given RESEARCHER are not expressly designed for learning specific concepts ( as they would be for a system being taught concepts), the program must decide which examples to compare for the purpose of generalization. This is done using a generalization-based memory of the sort in (Lebowitz 83b]. A hierarchy of concepts is created in memory (a hierarchy of hierarchies, in this case) that organizes specific examples.

In using its generalization-based memory, RESEARCHER takes each new example and searches down the tree for the example or generalized coricept most similar to it. This process involves matehing generalized concepts with the new example in much the same way as EX2 and EX3 were matched. We begin by matehing the new example with each of the children of the general izat ion t ree's root . RESEARCHER selects the best match and Iooks at that node's children. As long as one of the children produces a better match than the parent node, RESEARCHER continues down the tree. Eventually, it either reaches a leaf (an instance already in memory) or a maximally good generalization (i.e., all of the subordinate nodes contain factors that decrease the quality of the match).

Once the most simi lar previous example or ex1stmg generalization is found, RESEARCHER "factors out" similarities between these representations, and, if need be, creates a new generalization node. In any case, the new example is stored by recording how it differs from the generalizations in memory. This is an optimally space­ efficient method of storage, which also captures significant generalizations about the objects in the domain.

The current implementation of RESEARCHER's generalization scheme works quite weil on modest-sized examples. In addition to disc drive patents, a modified version of the program (CORPORATE-RESEARCHER [Wasserman 85]) has been tested on hierarchical descriptions of corporate organizations.

3 Text processing using memory

Since intelligent information systems such as RESEARCHER have available many examples in memory, it seems natural to make use of this information for text processing (beyond identifying lexical items). Patent abstracts, despite being written in legalese are, like the rest of natural language, quite ambiguous. We can use memory to help resolve many ambiguities.

We feel that the best way to use detailed memory information during text understanding in the context of current systems is to identify specific tasks where a piece of information from memory will be useful. More general methods, such as using memory to determine the interesting aspects of a text to focus processing, we leave for the future. We have identified a set of "questions" that arise during text processing that can most easily be answered (and often can only be answered) by accessing long-term memory.

It is important to keep in mind that we are proposing using memory for understanding, as opposed to general semantic information about words or concepts. While such general information is crucial for our conceptually-based understanding methods, in order to resolve many ambiguities it will be necessary to Iook at very detailed information in memory -- in our case, how the objects described in patent abstracts are constructed and how their pieces relate to each other. The use of the information base also reduces the need to initially hand-code information for RESEARCHER.

EX4 illustrates two kinds of ambiguities that arise m patent abstracts.

EX4 - A disc head supporting a spindie made of magnetic material.

The first ambiguity m EX4 involves "disc head". Although not syntactically ambiguous, an understanding system such as RESEARCHER must determine the conceptual relationship between the nouns. The phrase "made of magnetic material" is ambiguous in that we do not know whether it refers to the head or the spindle. Both of these ambi~uities can only be resolved by looking at memory. In fact, tt would be easy to construct seenarios where different states of memory would cause this example to be understood differently ( e.g., whether we knew about magnetic heads or magnetic spindles).

RESEARCHER makes ~se of relatively simple, but heavdy IT,Iemory-based, techmques for handling ambiguities of the sort m EX4. lts conceptual analysis type text processing algorithm ( described in [Lebowitz 83a; Lebewitz 84]) involves identify!ng objeet descriptio~s (usually noun gro~ps) and eonneetmg them wtth vanous relational words (usually preposttiO~s -- patent abstracts are quite short of verbs) whteh mdteate the vanous physieal, funetional and assembly­ eomponent relations mentioned in Seetion 2. Within this proeessing algorithm, we have identified plaees where ambiguity ean be identified and memory queried for resolution_. M~mory is ~ked which of two possible physieal eonstruettons ts more hkely or what relation is likely to oecur between two objeets. Questions in both classes are ansv:ered . by looking for examples of the possible eonftguratwns that already exist in memory.

Figure 2 lists some of the questions that RESEARCHER can eurrently ask memory for purposes of disambiguation. They primarily involve prepositional phrase attaehment and noun groups with multiple nouns. · Our analyses of these ambiguities sha:res. much with_ the linguistie work of [Levi 78] and the appheatwn of thts work to Al in [Finin 82]. However, our method of resolving the ambiguities -- the use of a dynamie, long-term memory -- is rather different.

Form: object-wordl object-word2 ExamT!/e: An a.ctua.tor housing ... Que.st10n: Wha.t is the rela.tion between object-wordl a.nd object-word2?

Form: modifier object-wordl object-word2 ExamT!/e: A metal drive cover .·. Quest10n: Does the modif'ier better apply to object-wordl or object-word2?

Form: object-wordl relation-wordl object-word2 rela.tion-word2 object-word3 ExamT!Ie: A coating _on a. disc touching a. spindie ... Que.stzon: Does rela.t10n-word2 connect obJect-word3 with object-wordl or object-word2?

Figure 2: Some disambiguation questions

The search for possible examples that answer a given questton ts a relat;vely simple one. RESEARCHER uses its dynamieally created deviee hierarchies to Iook for possible constructtons and relattons. lt begins its search with general obJect descnpttons and searches through more specific desenpttons untd a relevant example is found . Ir several possible construetions ( or relations) are found, the one assoctated wtth the most general description is used, as that represen~s RESEARCHER's most widely applicable mformatton. RESEARCHER's memory search disambiguation process ts described m more detail m [Lebowitz 84].

*The word types used in Figure 2 are functional , rather than syntaettc. However, obj ect words are usually nouns and relatton words are usually prepositions, although not always m etther case.

Our disambiguation methodology bears resemblance to that_ of [Sma;ll 80] and [Hirst 83], except, crucially, it relies on t~formatwn from a detailed, dynamic memory. Our alg~nt~m d_oes have the side-effect of making understanding subjecttve, m the sense of [Abelson 73; Carbonell 81] since new examples will be interpreted to eorrespond to old ones but we view this as inevitable if we wish to achieve robust understanding.

As an illustration of RESEARCHER's use of memory in text proeessing, we will show how it processes part of a real patent abstract, EXl, seen earlier.

~lt~ough it m_ay not be immediately obvious, the begt_nnmg of EXl ts extremely ambiguous. (It may not be obvw_us because people are so good at resolving ambiguity.) The mternal struetures of the various noun phrases and the determination of what is a part of what could all be resolved in several ways. Without any information in mem_orr, RE~EAR~HER would have to rely on general heunsttcs whtch mtght or mtght not work, and would, in any case, be quite ad hoc. Instead, we will provide RESEARCHER . with a few (admittedly somewhat artificial) examples that tt can use . Specifically, we will give it the following descriptions:

An apparatus with a support mechanism.

An interchangeable double sided floppy disc within a drive which has a magnetic head.

Having given RESEARCHER examples of support mechanisms and double sided floppy disc drives, we Iet it read EXl (Figure 3).

A number of aspects of RESEARCHER's text processing are shown in Figure 3. We will focus on its use of memory. Each memory access is indicated by "> > > ". The ftrst such use occurs when processing the initial noun group, "A magnetic head supporting mechanism". RESEARCHER uses a "save and skip" strategy for noun groups -- it saves words in a short term memory stack until the head noun is reached. Then it works backwards proc~ssing the stacked words. Here, it easily sets up two relattons between the head and the mechanism, both from the word "supporting", indicating that the mechanism supports and is connected to the head.

Next RESEARCHER must process "magnetic". It is syntactically ambiguous here whether the modifier applies to the head or the mechanism. (To see the other case consider, "a complicated head supporting mechanism".) So: RESEA_RCHER searches its memory for examples of magnette heads or magnetic meehanisms. lt finds the former, and appropriately resolves the ambiguity.

The proeessing of the next part of EX3, "equipped with a magnette head positioning earriage" is relatively sedate. "Magnetie" is again ambiguous, but this time refers to an object already described in the patent. Memory again becomes important in processing "a interchangeable double side type flexible disc drive apparatus".

The first problern arises in. determining the relation between the drive and the apparatus (remember, noun groups are processed, m effect, backwards). Here, since RESEARCHER has no examples in memory, it uses a

Running RESEARCHER at 6:03:19 PM

(A KAGIETIC BEAD SUPPORTIIG KECHAIISK EQUIPPED IlTH A KAGIETIC HEAD POSITIOIIIG CARRIAGE OF A IITERCHAIGEABLE DOUBLE SIDE TYPE FLEXIBLE DISC DRIVE APPARATUS COKPRISIIG

Proce .. ing:

A

IIAGIETIC

HEAD

SUPPORTIIG

IIECHAIISK

Iew in·tance word -- ·tip

Keaette aodifier; ·ave and Btip

Keaette within IP; ·ave and Btip

Purpo·e word witbin IP; Bave ana ·tip

KP word -- aeaette UJKIOII-ASSEKBLTt

Iew UJKIOII-ASSEKBLTt inatance (aKEK6)

Iew BEADt in·tance (&KEK7)

Eatabliahing R··COIIECTED-TO; SUBJECT: aKEK6 ('KECHAIISK'); OBJECT: &KEK7 (BEADt) [l!IEL2]

E·tabl1Bhi3~SUPPORTS; SUBJECT: aKEK6 ('KECHAIISK'); OBJECT: (BEADt) [l!IEL3]

>>> Select aeaette aodified bJ DEV-TTPE/KAGIETISK froa aKEK6 ('KECHAIISK') &KEK7 (HEADt)

Augaenting aKEK7 (BEADt) with teature: DEV-TTPE = IIAGIETISK

EQUIPPED IlTH Part· ot aKEK6 to tollbow

A

Iew inatance word -- atip

Keaette aoditier; ·ave and Btip

Keaette within IP; nve and Btip

KP word -- aeaette CARRIAGEt

POSITIOIIIG Purpose word within IP; ·ave and Btip

KAGJETIC HEAD

CARRIAGE

Iew CARRIAGEt in·tance (lKEKS)

EBtablhhilig P-GUIDES; OBJECT: tllEIIS (CARRIAGEt);

Recognized in·tance ot &KEK7 (HEADt)

SUBJECT: &KEK7 (HEADt) [l!IEL4]

Aaauaing &KEKS (CARRIAGEt) ia part of &KEK6 ('KECHAIISK')

OF (OFl)

: Part ot indicator

A·auaing &KEKS or &KEK6 ia part of the following

A

: Iew inatance word -- atip

IITERCHAIGEABLE : Keaette aodifier; ·ave and atip

DOUBLE SIDE Kemette aodifier; ·ave and ·tip

TYPE

DISC

FLEXIBLE

Keaette aodifier; save and Btip

DRIVE

APPARATUS

Stip (SI:IP)

Keaette within IP; ·ave and stip

KP word -- aeaette UIKIOWI-ASSEKBLTt

Keaette within IP; ·ave and atip

Iew UIKIOII-ASSEKBLTt inatance (&KEK9)

>>> Looting for relation between DRIVEt and &KEK9 ('APPARATUS')

Iew DRIVEt instance (tKEKlO)

Aasuaing tKEKlO (DRIVEt) ia partot &KEK9 ('APPARATUS')

>>> Looting tor relation between DISCt and one ot

Iew DISCt inatance (&KEK11)

&KEK9 ('APPARATUS') &KEK10 (DRIVEt)

Eatabli·hing R-IISIDE-OF( SUBJECT: &KEK11 (DISCt);

>>> Select aeaette aodified bJ RIGIDITT/IOIE froa

OBJECT : liEK10 (DRIVEtJ [l!IEL6]

&KEK9 ('APPARATUS') &KEK11 (DISCt)

Augaenting &KEK11 (DISCt) with teature: RIGIDITT = IOIE

>>> Select aeaette aoditied bJ IUKBER-OF-SIDES/2 troa

Augaenting lKEK11 (DISCt) with feature: IUKBER-OF-SIDES = 2

&KEK9 ('APPARATUS') &KEK11 (DISCt)

>>> Select aeaette aoditied bJ DEV-PURPOSE/KAIT troa

Augaenting &KEK11 (DISCt) with teature: DEV-PURPOSE = IIAIT

&KEK9 ('APPARATUS') &KEM11 (DISCt)

>>> Selecting coap tor &KEK9 ('APPARATUS') froa aaong

ABBuaing &KEK6 ('KECHAIISK') ia part of &KEK9 ('APPARATUS')

&KEKS (CARRIAGEt) &KEK6 ('KECHAIISK')

COKPRISIIG : Parts ot &KEK9 or &KEK6 to tollow

Figure 3: RESEARCHER using memory

heuristic to a.ssume that since "apparatus" describes a rather vague a.ssembly, the drive is probably a part of it. When " disc" is reached, the problern is more complex, since RESEARCHER must determine both whether the disc is related to the drive or the apparatus, and what the relation is. Here, a.s always, memory is used. Since RESEARCHER does not have an example of a relation between a disc and an apparatus, but knows of an example of a disc being inside a drive, it a.ssumes that the disc ts inside the drive here.

When the modifiers, "flexible", "double side" (RESEARCHER ha.s a phra.sal lexicon) and "interchangeable" are processed, the program must attach them to either the apparatus or the disc. (The drive is ruled out by syntactic considerations.) The processing is similar to the first noun group, using memory to resolve the conflict. Note that the disambiguation search ha.s a semantic ba.sis, so that the "floppy" disc 10 memory resolves the ambiguity over "flexible".

Finally, RESEARCHER must decide whether the apparatus ha.s a.s a part the carriage or the mechanism. (The " part of" relation is indicated by the word "of" .) Once again, the routine is the same -- search memory for examples and find one that resolves the ambiguity in favor of the mechanism. Different examples in memory would Iead to a different resolution.

We have much left to do 10 our integration of text processing and memory. However, we feel our generat approach is quite promising, a.s our work in building up memory ha.s a positive synergistic effect on text processing robustness. The identification of specific questions to a.sk memory seems to be much more effective than looking for more general applications of memory to understanding.

4 Q/ A in RESEARCHER

Once a substantial knowledge ba.se ha.s been built up by RESEARCHER, it is important that it can be queried intelligently. In [Lebowitz 83a; Paris 84] we described an early question answering module. Recent ly, our work ha.s concentrated on how RESEARCHER might tailor its answers for individual users. There are many elements to such tailoring, the goal of the user, for example, but here we will concentrate on just one factor -- the user's expertise. We have tried to determine the sorts of ba.sic answering strategies that would be appropriate for expert and naive users of the system* Eventually, we will also Iook at how expertise affects other Ievels of processing (such a.s word choice) a.s weil a.s other factors on answering.

In order to get an idea about the kinds of strategies that might be appropriate for various users, we have looked at texts that describe objects that are aimed at readers with different Ievels of expertise -- several adult and junior encyclopedia.s. As described fully in [Paris 85]. the strategies used in the adult and junior encyclopedia.s are quite different -- the adult encyclopedia.s, presumably aimed at relative experts, tend to describe the part structure of objects, while the junior encyclopedia.s describe the processes that take place in the device. EX5 and EXß show this distinction for descriptions of telephones.

EX5 - The hand-sets introduced in 1947 consist of a receiver and a transmitter in a sin!$le housing available in black or colored pla.sttc. The transmitter diaphragm is clamped rigidly at its edges to improve the high frequency response. The diaphragm is coupled to a doubly resonant system -- a cavity and an air chamber -- which broadens the response... (Collier's Encyclopedia, 1962)

* Actually, user expertise fall s into two areas -- famili ari ty with the system and familiarity with the domain . We are concerned here with the latter.

As we can see, EX5, taken from an adult encyclopedia, describes a telephone by presenting its parts. The description continues in this vein. It is using a construction quite similar to the constituency schema that McKeown used in her question answering work (McKeown 82], providing an almost tree-like description of the parts of the object. This is in cantrast with a description aimed at younger readers, EX6.

EX6 - When one speaks into the transmitter of a modern telephone, these sound waves strike against an aluminum di8k or diaphraqm and cause it to vibrate back and forth in JUSt the same way the molecules of air are vibrating ... (Britannica Junior, 1963)

Here the description is process-oriented. lt traces the process of transmitting sound, introducing part descriptions only when necessary. This is clearly a different presentation strategy, one that our study of texts indicates is much more widely used in texts aimed at less experienced readers. We feel that a process-oriented answer would be appropriate for RESEARCHER to use when dealing with a novice user not likely to know what various parts are used for.

We are currently in the early stages of implementing these two different strategies for describing the same object. We have implemented simple techniques for producing "expert" type responses using McKeown's constituency schema ( although our low-level generation, even here, is quite basic ). In addition to looking at the different generation strategies, we are also studying ways to determine the expertise of a user as weil as mixed strategies that make use of elements of each generation technique.

5 Conclusion

We have described here three areas of investigation in the study of intelligent information systems focused araund the program RESEARCHER. The generalization of hierarchical representations allows the system to learn about a wide range of complex objects and build up a rich memory. This memory is used extensively in text processing, primarily for disambiguation, to achieve robust performance. Finally, awareness of the expertise Ievel of a user will allow RESEARCHER to tailor it answers to each user. The sum of these three related areas of investigation should Iead towards the development of powerful intelligent information systems.

Heferences

(Abelson 73] Abelson, R. P. The structure of belief systems. In k. C. Schank and K. Colby, Ed. , Computer Model8 of Thought and Language, W. H. Freeman Co., San Francisco, 1973.

IBarr et al. 82] Barr, A., Cohen, P. R. and Feigenbaum, B. A., eds. The Handbook of Artificial 1ntelligence, Volume8 1 - S. William Kaufmann, Inc., Los Altos, California, 1982.

[Carbonell 81} Carbonell, J. G. Subjective tlnder8tanding: Computer Model8 of Belief Sy8tem8. UM! Research Press, Ann Arbor, Michigan, 1981.

[Finin 82} Finin, T. W. The interpretation of nominal compounds. in discourse. Technical Report MS-CIS-82-3, Moore School of Engineering, University of Pennsylvania, 1982.

(Hirst 83) Hirst, G. Semantic interpretation again8t ambiguity. Ph.D. Thesis, Department of Computer Science, Brown University, 1983. ·

(Lebowitz 83a) Lebowitz, M. RESEARCHER: An overview. Proceedings of the Third National Conference on Artificial lntelligence, Washington, DC, 1983, pp. 232 - 235.

(Lebowitz 83bl Lebowitz, M. Concept learning in a rich mput domain. l>roceedings of the 1983 International Machine Learning Workshop, Champaign-Urbana, Illinois, 1983, pp. 177 - 182. To appear in Machine Learning 11.

(Lebowitz 84) Lebowitz, M. Using memory in text understanding. Proceedings of ECAI-84, Pisa, ltaly, 1984.

[Levi 78) Levi, J. N. The . Syntax and Semantic8 of l:omplex Nomina18. McGraw Hili, New York, 1978.

fMcKeown 82] McKeown, K. R. Generating natural language text in re8pon8e to que8tion8 about databa8e 8tructure. Ph.D. Thesis, University of Pennsylvania, 1982.

rParis 84) Paris, C. L. Determining the Ievel of expertise. f>roceedings of the First Annual Workshop on Theoretical Issues in Conceptual Information Processing, Atlanta, Georgia, 1984.

[Paris 85) Paris, C. L. Description strategies for naive and expert users. Proceedings of the 23rd Annual Meeting of the Association for Computational Linguistics, Chicago, 1985.

[Small 80} Small, S. Word expert parsing: A theory of aistributed word-based natural language understanding. Technical Report TR-954, University of Maryland, Department of Computer Science, 1980.

[Wasserman 85} Wasserman, K. Unifying repre8entation and generalization: Under8tanding hierarchically 8tructured object8. Ph.D. Thesis, Columbia University Department of Computer Science, 1985.

fWasserman and Lebowitz 83} Wasserman, K. and Lebowitz, M. "Representing complex physical objects." Cognition and Brain Theory 6, 3 (1983), 333 - 352.

[Winston 80} Winston, P. H. "Learning and reasoning by analogy." Communication8 of the ACM 28 (1980), 689 - 702.