FREE ELECTRONIC LIBRARY - Dissertations, online materials

«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



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


information 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.



[1] Bobrow, R.J., The RUS System, Report 3878, Bolt Beranek & Newman Inc., Cambridge, MA. (July 1978).

[2] Brachman, R.J, A structRral paradigm for representing knowledge, Report 3605, Bolt, Beranek, & NewmanInc., Cambridge, MA. (May1978).

[3] Fahlman, S.E., NETL: A System for Representing and Using Real World Knowledge (MIT Press, Cambridge, MA, 1979).

[4] Griffiths, T.V., & Petrick, S.R, On the relative efficiencies of context-free grammar recognizers, Comm. A M 5 (1965) 289-300.

C [5] 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).

[6] 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).

[8] Phillips, B., A model for knowledge and its application discourse analysis.

American Journal of Computational Linguistics, Microfiche 82 (1978).

[9] Quillian, M.R., Semantic memory, in Minsky, M. (ed.), Semantic Information Processing (MIT Press, Cambridge, HA, 1968).

[10] Ross, K.M., Parsing English Phrase Structures, Ph.D. Thesis, Dept. of Linguistics, University of Massachusetts (September 1981).

[11] Saenz, R.M., Local Grammar, Unpublished paper, Dept. of Linguistics, University of Massachusetts (February 1980).

[12] Schank, R.C., Conceptual Information Processing (American Elsevier, New York, 1975).

[13] 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).

Similar works:

«Midnight Warhorse Midnight-Warhorse Chapter 1 Midnight Birth As the clock struck 12 midnight, the muchawaited foal bounced awkwardly but strongly to her feet for the first time. The crystal clear waters of the Pages River flowed around the big bend with its high side cut well into the bank, while the new foal stood on the level, rich alluvial flat on the homestead side of the river. It was the 31 October 1905, the same day twelve years later she would come to a courageous end in a foreign land...»

«True West (1980) by Sam Shepard Characters AUSTIN: early thirties, light blue sports shirt, light tan cardigan sweater, clean blue jeans,white tennis shoes LEE: his older brother, early forties, filthy white t-shirt, tattered brown overcoat covered withdust, dark blue baggy suit pants from the Salvation Army, pink suede belt, pointed black fortiesdress shoes scuffed up, holes in the soles, no socks, no hat, long pronounced sideburns, GeneVincent hairdo, two days' growth of beard, bad teeth SAUL...»

«Portland Thorns Academy Tryouts and Information Oregon and Southwest Washington female soccer players, on behalf of the Portland Thorns, we would like to invite all interested players, U15-U18 to tryout for the Portland Thorns U16 and U18 academy teams, June 1, 2 and 3 and June 29, 30 and July 1 at Providence Park. Players interested in the academy program are required to attend tryouts and register at www.timbers.com or registration.timbers.com. Thorns Academy Tryout Schedule Dates: June 1, 2,...»

«Broken Toys is a personalzine by Taral Wayne, and does not imply that my other zine, New Toy, is a dead letter. In fact, I hope to begin work on it next month. The letter column this issue abounds with equal parts of news, good cheer, egoboo and even a little serious demeanor. As has been the case for a third of my life, I live in partly self-imposed exile at 245 Dunn Ave., Apt. 2111, Toronto Ontario M6K 1S6. However, contact or loc me at Taral@Teksavvy.com. The date is January 2013, hopefully...»

«Restricted THE COUNCIL Minutes of the meeting held on 4 July 2007. Present: Lord Elystan Morgan, President (in the Chair); Mr Huw WynneGriffith, Vice-President; Mr Richard H Morgan, Treasurer; Professor Noel G Lloyd, Vice-Chancellor and Principal; Professor Aled Jones, Dr John Harries, Professor Lyn Pykett, Pro Vice-Chancellors; Mr Roger Banner, Mr Ben Davies, Professor Roger Earis, Mr Gwynfryn Evans, Dr Gayner Eyre, Mrs Elizabeth France, Dr M Hopkins, Mrs Rachel Hubbard, Mr Gerallt Hughes, Mr...»

«THE RGF PANDEMONIUM: A LOW-LEVEL REPRESENTATIONAL MODEL FOR IMAGES ROSA RODRIGUEZ-SANCHEZ Departamento de Informatica. Escuela Politecnica Superior. Universidad de Jaen. 23071. Jaen. Spain. J.A. GARCIA and J. FDEZ-VALDIVIA Departamento de Ciencias de la Computacion e I.A. E.T.S. de Ingenier a Informatica Universidad de Granada. 18071 Granada. Spain. Corresponding author: J.A. Garc a Departamento de Ciencias de la Computacion e I.A. E.T.S. de Ingenier a Informatica. Universidad de Granada. 18071...»

«INTERPEçLLANZA La signora Francesca Machado-Zorrilla unitamente a due cofirmatari, presenta la seguente interpellanza: PREMESSA I tempi cambiano, si affacciano le giovani generazioni e cambiano anche le abitudini. Trenta o quaranta anni fa i giovani della regione e molti turisti si svagavano in discoteca. Ancor oggi ci si ricorda dell’ Ascona by night e delle sue mitiche discoteche come il Cincillà, l’Ascona Club, il Lago, Le Stelle. A Locarno c’era il Florida, ma si ballava anche alla...»

«Captiva InputAccel 6.5 Tutorial M. Scott Roth February 2012 v1.0 www.armedia.com msroth.wordpress.com Table of Contents 1 Introduction 1.1 Process Overview 1.2 Architecture Overview 2 CaptureFlow Designer 2.1 Process Design 2.2 IA Values and Custom Values 2.2.1 IA Values 2.2.2 Custom Values 2.2.3 My Assignments 2.3 Branching 2.4 Compiling 2.5 Installing the Process 2.5.1 Installation 2.5.2 Copy and Paste Settings 2.6 User Roles and Security 3 Module Setup 3.1 ScanPlus 3.1.1 Scanner 3.1.2 Event...»

«What a happiness it is to feel even once in a lifetime what a true actor must feel and do on the stage! When technique reaches the possibility of realizing this hope, our stage craftsmanship will become a true art. But where and how is one to seek those roads into the secret sources of inspiration? This is the question that must serve as the fundamental life problem of every true actor-Konstantin Stanislavsky THR 206 Acting II: Stanislavsky as an Approach to Scene Study Monday/Wednesday:...»

«POWER AND INITIATIVE IN TWENTIETH CENTURY GERMANY THE CASE OF HUGO JUNKERS by RICHARD WILLIAM EDWIN BYERS (Under the direction of John Morrow) ABSTRACT This dissertation explores the relationship between private enterprises and nation states in high technology research and applications. As the twentieth century progressed, this relationship became more contentious as state organs, citing national security priorities, attempted to assert their influence on private manufacturers. Nowhere is this...»

«Linguistics of the Tibeto-Burman Area Volume 31.2 — October 2008 SYNTACTIC ASPECTS OF NOMINALIZATION IN FIVE TIBETO-BURMAN LANGUAGES OF THE HIMALAYAN AREA1 Carol Genetti University of California, Santa Barbara Research Centre for Linguistic Typology A.R. Coupe Ellen Bartee Kristine Hildebrandt You-Jing Lin La Trobe University SIL SIUE UC Santa Barbara The goal of this paper is to describe some of the syntactic structures that are created through nominalization processes in Himalayan...»

«From Strategic Hyperlink Networks to Cognitive Issue Networks: Advancing a Dual Structurational Model of Social Issue Emergence on the Web Lindsay Young Media, Technology and Society Program Department of Communication Studies Northwestern University Paper Presented at ECPR General Conference Bordeaux, France September 4-7, 2013 Abstract The web is a forum for defining social issues and a source of information for evaluating them. As such, it is important to examine how its socio-technical...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.