«A MESSAGE-PASSING CONTROLS R C U E F R TEXT U D R T N I G TUTR O N E S A DN Brian Phillips and JamesA. Hendler Texas Instruments Inc. Dallas, Texas, ...»
COLING82, J. Horeck~ (ed.)
North-Holland Publishing Company
© Academia, 1982
A MESSAGE-PASSING CONTROLS R C U E F R TEXT U D R T N I G
TUTR O N E S A DN
Brian Phillips and JamesA. Hendler
Texas Instruments Inc.
Dallas, Texas, USA
This paper describes an object-oriented, message-passing
system for natural language text understanding. The
application domain is the texts of Texas Instruments' patent descriptions. The object-oriented environment permits syntactic analysis modules to communicate with domain knowledgemodules to resolve ambiguities as they arise.
1.0 INTRODUCTION As syntactic and conceptual coverage increase to meet the requirements of practical language understanding systems the computational effort to search the larger knowledge spaces tends to grow exponentially in current systems.
Clearly, this search problem is one of (many) problems that have to be resolved.
One solution is to eliminate many of the alternatives as they are encountered.
We are investigating a control structure that allows syntactic and semantic knowledge sources mutual access to allow early selection of appropriate alternatives.
W wish to include in our system the multiple facets of linguistic structure and e to maintain their descriptive autonomy, accordingly other suggestions that have been made to constrai~ searching (e.g., Hendrix (1977), Schank (1975)) do not satisfy this design criterion. W also want the system to simultaneously build e a conceptual representation of the text and to be able to f e e d semantic predictions to syntax. In the Rus system (Bobrow (1978)) the semantic component critiques the constructs of syntax but does not generate predictions.
2.0 OBJECTSA D MESSAGE-PASSING N W have adopted a pseudo-parallel, object-oriented approach to writing our e system (Hewitt (1976)). Objects encapsulate data and their operations. Actions on data can only be performed by sending messages to appropriate objects. A request for action may require that the object enlist the aid of other objects, which i t does by further message-passing. Any object can communicate with any other object (though objects can receive messages they cannot process).
Further, an object need not get a reply to a message. Objects have memory and can retain their state between activations. This flow of control amongobjects is more general than stack-oriented activation of subprograms.
307 / I 308 B. PHILLIPS af,d J.A. HENDLER I n t e r l i s p, Simula, Smalltalk, and LispMachine Lisp (Weinreb & Moon (1981)) have features that encompass the object n o t i o r. Our system is being implemented using the " f l a v o r " system in Lisp Machine Lisp.
3.0 THE APPLICATION We are using working abstracts of descriptions of Texas Instruments' issued patents. These are w r i t t e n in a r e s t r i c t e d s t y l e by by the attorneys and the topics are l i m i t e d to s o l i d - s t a t e m i c r o - e l e c t r o n i c devices. Thus we are able to use n a t u r a l l y occurring data without immediately confronting the problems of incomplete syntactic and conceptual coverage that would be encountered in many
other domains. An example is:
A modulator comprising two t r a n s i s t o r s each having c o l l e c t o r, emitter and base electrodes, means f o r applying a d i r e c t voltage across said e m i t t e r electrodes, a center-tapped source of a l t e r n a t i n g signals connected between said base electrodes, said c o l l e c t o r e l e c t r o d e s being connected together and to the center tap of said source. A load impedance connected between said c o l l e c t o r electrodes and said emitter electrode of one of said t r a n s i s t o r s, and a v a r i a b l e r e s i s t o r connected between the base electrode and the emitter electrode of said one t r a n s i s t o r.
The i n t e r a c t i o n of embedding and conjunction gives a high degree of syntactic ambiguity to the t e x t s. The texts can also be ungrammatical, whence the desire to be building the conceptual representation in p a r a l l e l with the syntactic analysis in order that some meaning w i l l be extracted from the t e x t even when the syntactic analysis is not completed.
The goal of the project is to build a conceptual representation for the t e x t, then add r e t r i e v a l c a p a b i l i t i e s that w i l l be more f l e x i b l e than a word-matching scheme.
4.0 THE SYSTEM The objects of our system correspond to the organizing p r i n c i p l e s of the components. In syntax we have constituency objects that can take grammar rules and t r y to match them against input. In semantics we have taxonomy objects, case-frame objects, causal-chain objects, meta objects ( t h a t handle a form of lambda-abstraction), etc.
Small & Rieger (1981) also have an object viewpoint of language analysis.
However, in t h e i r scheme each word is an object, motivated by t h e i r view that "human knowledge about language is organized p r i m a r i l y as knowledge about words r a t h e r than as knowledge about rules" ( p. l ). Our system is organized around rules.
Kornfeld (1979) has given an example of a (pseudo-)parallel communicationsystem that passes information between objects to reduce the respective search spaces;
he terms the phenomenon."combinatorial I__MMplosion". The interaction between syntax and semantics allows the the conceptual representation of sentence fragments to be b u i l t in parallel with the syntactic analysis. Semantic predictions arm fed back to syntax to try to achieve the combinatorial implosion.
4.1 The Syntax The formalism we are using is "local grammar" (Saenz (1980), Ross (1981)) which consists of a context-free phrase structure grammarwith augmentations. The augmentations are blocking and percolation rules. For example, the auxiliary rule in our system is verb-group = aux v e r b - g r o u p structure rule aspect (1) = affix (2) blocking rule affix (0) = affix (1) percolation rule Figure I: The auxiliary rule The structure segments are numbered l e f t to right, starting at 0 for the left-hand-side of the rule. The values of the features "aspect" and "affix" are established in the dictionary for terminal items and percolated up the analysis tree for higher level phrases.
The parsing algorithm is a modified left-corner routine (Griffiths & Petrick (1965)). The modifications are to use the object environment to produce all parses in parallel and to merge commonsubparses.
Figure 2 gives an exampleof the state variables of a constituent object that is using the auxiliary rule.of Figure 1. "Category" is the left-hand-side of the structure rule, "part-parse" is the fragment of the right-hand-side so f a r.
matched, and " r u l e - t a i l " is the remaining part of the structure rule.
"Augmentations" are the percolation and blocking rules. The "goals-list" gives other constituent objects that are awaiting completionof this constituent (there may be several because of merged paths). The word "being" has just been processed as the f i r s t segmentof the part-parse and the segment counter now I 310 B. PHILLIPS and J.A. HENDLER points to the second position. The object has processes for (a) advancing the analysis with a new input word, (b) for advaacing the analysis when a subparse has been completed (the parse can only be immediately advanced when the next element of the r u l e - t a i l is a terminal symbol; otherwise i t has to create another object to process a rule expanding the non-terminal category), and (c) for merging with another path.
4.2 The KnowledgeBase General knowledge of the domain is represented in a semantic network (Phillips (1978)). The conceptual analyses w i l l be instantiations of general knowledge with novelty introduced from the texts.
Semantic nets are usually seen as data (e.g., Qillian (1968), Brachman (1978)) with various routines for performing operations such as taxonomysearches, finding paths from node to node, and binding variables in the network. Each node of our network is an object having associated processes dependent on the types of links i t has to other nodes.
Thus in Figure 3, which shows part of our semantic network, links indicate the other nodes to which a node can send a message, as opposed to a physical pointer. A node is actually implemented as a "mix" of objects for the kinds of links i t h a s ; thus as new links are added so are new processes. A node need not know anything about the internal format of data in other nodes to get
A CONTROL STRUCTURE FOR TEXT UNDERSTANDING 311information from t h e m. Further, when a message is sent to a node, the sender need not know whether this is a "simple" or "complex" message: a simple message can be answered by the qode i t s e l f, a complex message requires the node to send messages to other nodes. Thus a "part-whole" message to establish whether a d i r e c t - v o l t a g e source can be part of a modulator or part of a t r a n s i s t o r, w i l l also use intervening taxonomy, decomposition (meta) links (Figure 3) without t h i s being specified in the o r i g i n a l query. A node receiving this message would " pass a similar message to i t s neighbouring nodes i f i t cannot i t s e l f respond.
4.3 Flow Of Control
Processing of t e x t is i n i t i a t e d from a task specific knowledge object, in this case a "patent knowledge expert" that has an expectation of finding a patent.
I t passes a message to the t r a n s l a t o r that sees i f i t has any data that w i l l match this expectation. Since no part of the t e x t has been examined by syntax, nothing can be found. A s t a r t message is sent to syntax.
The translator object should pass predictions to syntax but this d o e s not, in general, seem possible as the r e a l i z a t i o n s of a concept include a l l possible descriptive references. Thus the t r a n s l a t o r maintains i t s l i s t of predictions and, when syntactic constituents are received, matches t h e i r translations against the predictions. A match causes a message to be sent to the source of the prediction, which can extend the conceptual representation and produce f u r t h e r predictions.
When no matches are found, the t r a n s l a t o r seeks a knowledge structure that corresponds to the syntactic structure. This occurs, f o r example, when the syntactic objects are confronted with the attachment of the "means for applying..." phrase in the example given above: is the correct analysis "modulator comprising... means... " or " t r a n s i s t o r s each having... means... " ? A path through the network of Figure 3 shows that a modulator can have a direct voltage source but no such path exists for t r a n s i s t o r s. The appropriate i n s t a n t i a t i o n of the network is created and the unacceptable syntactic path is eliminated from f u r t h e r consideration.
Processing is complete when the t e x t has been consumed and a l l the concepts from the t e x t are connected to the topic of patent, though ungrammaticality may cause an e a r l i e r end.
5.0 CONCLUSION Our understanding of language and cognitive processes is growing and novel programming languages are developing. With this knowledge and these tools, we are getting closer to viable natural language systems in limited domains.
There are other developments that w i l l contribute to building natural language systems, namely the decreasing cost and increasing power of hardware. Also advances in computer-aided design give promise of c o s t - e f f e c t i v e special purpose machines with hardware routines for processes now implemented in software (Fahlman (1979)). M o r e power w i l l c e r t a i n l y aid in constructing language understanding systems. But the power w i l l be wasted i f i t is used to attack a problem that can be resolved by some other approach, say by constructing an object-oriented system as presented above.
312 B. PHILLIPS and J.A. HENDLER
6.0 REFERENCES Bobrow, R.J., The RUS System, Report 3878, Bolt Beranek & Newman Inc., Cambridge, MA. (July 1978).
 Brachman, R.J, A structRral paradigm for representing knowledge, Report 3605, Bolt, Beranek, & NewmanInc., Cambridge, MA. (May1978).
 Fahlman, S.E., NETL: A System for Representing and Using Real World Knowledge (MIT Press, Cambridge, MA, 1979).
 Griffiths, T.V., & Petrick, S.R, On the relative efficiencies of context-free grammar recognizers, Comm. A M 5 (1965) 289-300.
C  Hendrix, G.G., Human engineering for applied natural language processing, in Proceedings of the 5th International Joint Conference on A r t i f i c i a l Intelligence (Cambridge, 1977).
 Hewitt, C., Viewing control structures as patterns of passing messages, AI Memo410, MIT AI Laboratory, Cambridge, MA. (December1976).
[ 7] Kornfeld, W.A., Using parallel processing for problem solving, AI Memo561, MIT AI Laboratory, Cambridge, MA. (December1979).
 Phillips, B., A model for knowledge and its application discourse analysis.
American Journal of Computational Linguistics, Microfiche 82 (1978).
 Quillian, M.R., Semantic memory, in Minsky, M. (ed.), Semantic Information Processing (MIT Press, Cambridge, HA, 1968).
 Ross, K.M., Parsing English Phrase Structures, Ph.D. Thesis, Dept. of Linguistics, University of Massachusetts (September 1981).
 Saenz, R.M., Local Grammar, Unpublished paper, Dept. of Linguistics, University of Massachusetts (February 1980).
 Schank, R.C., Conceptual Information Processing (American Elsevier, New York, 1975).
 Small, S.L., & Rieger, C., Parsing and Comprehending with Word Experts, Technical Report I039, A r t i f i c i a l Intelligence Group, University of Maryland (April 1981).
[ 14] Weinreb, D., & Moon, D., Lisp Machine Manual (MIT AI Laboratory, Cambridge, MA, 1981).