Word Expert Parsing

WORD EXPERT PARSING*

Chuck Rieger and Steve Small

Department of Computer Science University of Maryland College Park, Maryland 20742

An approach to natural language meaning-baaed parsing in which the unit of linguistic knowledge is the word rather than the rewrite rule is described. In the Word Expert Parser, knowledge about language is diatributed acroaa a povulation of procedural expert!. each representing a word of the language, and each an expert at diagnosing that word a intended usage in context. tne parser is structured around a coroutine control environment in which the generator-like word experts ask questions and exchange information in coming to collective agreement on sentence meaning. The Word Expert theory is advanced as a better cognitive model of human language expertise than the traditional rule-baaed approach. The technical discussion is organized around examples taken from the prototype LISP syatem which implements parts of the theory.

I. Background

~~r~~il~!~~ra ~=~~;~~n;a~~u~~em~~~er:t~~~n~fsh~~e~~ ~~;r~~s ;~~ organize linguistic and conceptual knowledge for the parser. Depending upon the level of analrsis desired (e.g., from simple keyword and key phrase recogn tion to "full" conceptual understanding in context), different methods suggest themselves. For the most part, models of parsing to this point have made the assumption that systems of rewrite rules are good media for ~~r;~!~!Y~ kn~~~~~~=f~rou~Y=~~;:nc:~Jev~~errr:!ngbas!~amg~esth1! =~=l~~~!~n i~~m b~heta:~~ l;r 0 ker:~~~ysn~!;;~~ o~v;IARY 1 ili! t~! syntactic analysis of LUNKR, up to more semantic and conceptual parsers such as those by Riesbeck (2), [3), and Wilks (4) 1 15). Although the implementation styles of these models ailfer markedly, they share the view that rules of language understanding are best captured by rules which span relatively large sentence constituents (e.g., a phrase a "picture proaucing" clause, a verb case framework). Thls assumption ~~~~~~~;~satat~:r!:~~e~~=wl~~ela~~daf~e~~~g~e~~~si~~r~~ 1 ~¥ 08 ~~~ language as tokens which simply participate in comprehension by virture of their inclusion in sentence and concept level rules.

~~~~a~~ i~a~ig~!Y !!~~!;s;~ati~n~hek?~~e~fea =~:~:~e~1rre~1~; rules! this form of representation defines a particular point of view n which individual words of the language mean nothing outside the system of rules which make reference to them. This seems peculiar, since we intuitively know that each word of our language is an object with an often very rich knowledge structure attached to it. We khow many contextual uses of each word (sense), we know its morphology perhaps its history in some usage, perhaps when we first learne~ lt, ita idiosyncratic uses perhaps even idiosyncratic uses of it with respect to some particular speaker we know. Intuitively, there is a considerable amount of knowledge associated with eacn word.

One can easily argue that all such knowledge can be captured in a system of rules which make reference to the word; indeed 1 each rule we add to the system will incrementally extena our knowledge about the words to which it makes reference. To extend the system, one adds new rules and revisea or deletes old ones. If asked what it knows about any given word the system can report all patterns in which the word participates. During comprehension, if the patterns of the syotem have been written to include enough sentential and conceptual r.ontext, exactly the right rules will filter to the fo~efront to drive the parser in its extraction of meaning and/or syntax. Such a system is clearly theoretically adequate.

We believe·! however, that the underlying assumptions of this traditiona approach are not correct. Out of curiosity a while back, we posed the following question: What would the knowledge in a language comprehension model look like if organized around words rather than systems of rewrite rules? suverfici~lly, this seems like an engineering matter; one symbol s forward pointer is another symbol's backward pointer! But, as we have found, a remarkably different set of issues arises! and a considerably different approach to parsing suggests itse f when the model defines the unit of knowledge to be the word rather than the rewrite rule.

This paper describes our "word expert" view of natural language

*The research described in this report is funded by the National Aeronautics and Space Administration under grant number NSG-7253. Thefr support 1a gratefully acknowledged.

~g:g~~he~:!~~· m~~eth:t~~!~~r!~g ~~;~io~~le~a~:~c~~~~em~h~ndt~ describe the architecture and operation of the Word Expert Parser, a LISP implementation of the ideas.

2. Word Experts

Our thinking on these matters was first stimulated by a simple observation about existing models. This observation was that no model (except for Wilko' model of preference aemantica) seems ==~~e~o h~fe m:~; moi:e~ha~~dto~~n ~~~em~~c:~u~=~~~inli:~~~~f: impressive parser, for example, while pioneering in many of ita ideas about control via conceptual dependencr achematal wsa designed in a way that made it awkward to dea with h ghly ambiguous words; although the system did (and does) clever rule and expectancy switching on a limited set of examples of conceptual ambiguitr, the system does not deal with the problem in generality. Wilko system! on the other hand, is designed to deal with exactly this prob em of word ambiguity, but at a more semantic (e.g., "things which are human eat things which are food") 1 rather than fully conceptual level where arbitrary world knowleage might be re~uired for understanding. It is a mixture of Riesbeck's and Wilka goals that moat cloaely defines our goals, since we feel that word sense disambiguation in the context of open-ended world knowledge 11 of ultimate importance in a natural languaae system.

We therefore took the point of view that mechanisms for dealina with word ambiguity ahould be deeply built in to the model, perhaps even the moat central mechanisms of the comprehension process. To gain some empathy for this point of view, consider almost any common English noun, verb or adjective. With twenty minute's thought, ana perhaps a few reminder& from Webster's, it ~~atu:~~a~Y (c~s~~;elo~~e~a=~t;~~d~ozt~~eof.~!(!!~enF,m~~:8esa~a "give" in some detail; each has dozens of distinct usages.)

~~~te~~ua!e ~~~~ch oihe .e~~bl~~ h~~ ~me~~~;in~orm ~= traditional approach would be to wrfte one rufe for each usage. Each such rule would contain enough contextual probes so that it would fire at exactly the appropriate momenta. But there are several negative features of this approach. First, each rule must be self-contained, and have enough information to fire only when the appropriate aentential and conceptual context pertained. This quickly leada to large, often highly redundant ~~~;~;~ete~e~~~!Ci!o~; rul~ .~~~~ra~~~~·mu:~c~~1st ~gm:el:~~f~~ "most appropriate" competitor from among the aeveral rules which will typically fire as potential interpretations. Third, bel~ separate from all the other competitors each rule must be able to place an absolute judgement on its relevance to the context at hand; there is no convenient way to have a rule decide on its ~ appropriateneu, with respect to ita competitors.

These observations pointed away from rule systemst and toward the idea of writing more unified word experts. his led us to the notion of word (sense) e:~~i~y· In our present model, each word expert isapr~ cognizant of all the possible ~~~~=~t~~ 1 a ;~~!~r~=t~~~~~~t ff.e~~ein~~~ed 1 ~f r~~r~~=r~!~nWh~~ the sentence, and given access to the neighboring experts and to a database of world knowledge context at tbat point in the comprehension of the larger fragment of which the sentence is a part), a word expert should be capable of issuing an orderly progression of inquiries about its context, and making a set of decisions based on the responses (or lack thereof) to its 1~~~;;~et:~fg~ ~1adit; 0 w~rd 1 !~ei~!~nco~~ex~~ E~~~tworaei:~i~~ is, in effect, a unified compilation of what otherwise would be a collection of rules deacribing the contextual varianta of the word. By unifying them, we create a central knowledge etructure which can pose more concise questions to differentiate contextual usages, and which superimposes a unifying framework on all possible interpretations of a word.

ln further pondering the nature of word experta, it occurred to us that what we are really talking about is not ao much words, but rather lexical unito that are capable of contributing meaning or structure to a sentence. From this idea, it becomes clear that we want experts not only for words, but also for common morphemes ( "-ing" , "-ed", etc.), and possibly even for punctuation. The sentence (and a host of others like it, studied heavily in linguistics circles) ''The aan eatinf opaghett! growled. " illustrateo very clearly the deairability o an -ing" expert. Looking to Its left and right experts (or the concepts they may already have conatructea) · "-ing" should be able to decide how the concepts referenced by man" and "eat" in this sentence best fit together. Becauae of observations like this one , we have come to take a broad view of ·enae experts that will allow meaning-contributing units other than words.

Parter Overview. Naturally, adopting the word and morpheme 'l"'t''ln' t'l!r!!"'nnrrule aa the baae unit expreaaina knowledge leada to differences in the orfanization ana control of the paraer. ~~~=~ tharsa u~~~~rm ;ulemoa~irpr~ier/~g~~~~Inathec~~~~01Ex~~~ intercommunication. Aa we are about to deacribe, in the Word Expert Parser , the parae of each sentence involves the pagiag in of all required experta the initialization of community and private workspsceo, then t~ control of the nuaeroua experto as they execute, suspend themaelves, ask questions of one-another, and contribute fragments of meaning to the final interpretation of the sentence. Because of its organization, the Word Expert Paraer must define not only the structure and content· of each expert, but also a cognitively plauaible control paradigm for coordinating the experts.

The body of the paper ia a description of our preaent model of word experts and their control. Briefly, each word expert Ia a generator-like coroutine whole decioion logic ia organized aa a aiacrimination net. Terminal· of the net are the diotinct uoagea of the word (ita aenaes), while non-terminals are multiple-choice question· which probe the run-time environment. Also at each non-terminal node io control information deacribing what to do in caae the queation ia not yet anawerable (e.g., make an asaumption 1 forward a auggeation to another expert! auapend temporari y). Meaning representation of the fina ~~~i~;rta~~~! ~}·et~e t~ ~~!) 1 n~a~~~~e~~!n !~or:~uea~n ~~ development of the paraer ~ thia point. We preaently uae predicates that are deacriptive of each of the different aenaeo of the word, and have not made attempta to develop a consiatent representation. Althouah the nature of the paraer may well be affected by eventual commitment· to one particular repreaentation, we have ao far been able to develop the ideas about word expert atructure and content and about paraer control without regard for the form of the linal repreaentation.

We hope to convey our intuitive feeling that word level oraan!zation of knowledge about language ia both natural and powerful. In addition to dictating an intereating atyle of paraer control, solving aome important problema about wora aenae ambiguity, ana addreaaing the iaaue of relative (rather than abaolute) oelection of the moat appropriate interpretation of each word, the word expert organization leada to aome other l~!~~!:~~ngw!deat.~~~~t !:~~~:fe'ofpa~~;~ 1 aia~a.a~~t t~nf~~~r section. AdditiQnal 4iacueeton of the Word Expert topic can be found in (6), (7 J, (8], and (9).

3. The ~ Expert f!!!!!.

!~· ~~i~r~:reri.~;~·; 1 ~t 8 ~~~:~g~;~e ~:::~ni~;~I~~~· ~~we:~ internal repreaentafion language of concepti and ideas. Aa a human reader proceaaea a sentence, various conceptual conglomerates are created that provide the key to his underatanding (10). The rrocess of creating theae structure· ia t~ t;~rt~~~c::.f~ ·~Iucaur::n~~~~=el~t~.~-d:~!n~~~ ~~pe~~=~~; earlier rrocessing, but sometimes the meanin~ ff , sentence ia ~=p~~~~! ~le!~f}~n~~~k~~ ~~~g~g!~ ~~~c!:·:o l~; 'wr~~!nah~~;~ aa well if any degree of ungrammaticality or fragmentation is to be tolerated . The Word Expert Parser is a model of conceptual language analyaia that etrivea for theoretical perapicuity of process.

3.1. ~ ~ = ~ Simple Example

We will firat deacribe the execution of the Word Expert Paraer on the phraoe "the heavy rain" to illuatrate the model'· procedural framework on a aimple example. Initialization of the paraer commence· with the creation of a sentence level workaface for this particular input. This wo~~ati o i collection of word bina and their aaaociated word aenae diacrimination ex a \V5fd rgm;;: or unu e:p:f~jJ;-A ""V'1"i! bin li I Up Tl!T"" tion""imt 'le word (or aub-lexical morpheme of the input and ito correaponding word expert contains the word-apectf!c (and procedural) linguiatic knowledge that direct· this particular execution of the paraer. Each word expert Ia capable of diaambiguating ita word in any context, and interactions among word experts determiniatically dto .. biguate the meaning of the oentence.

The "the" ex~~jt rune. The paraer befina execution with the word ~l't""'f1Sr .~tch Ia the f ret on the RUN-ME gueue (initialized to the input aentence). The flow of control now becomes unpredictable (in theory), ao the word experta themselves completely determine control atate change· and conceptual actiona of the model. The "the" expert triu to determine ito role in the aentence, knowing only that it ia the first expert t9 run. Since the role of "the" 1a uaually obvioua (aa it ia here) ita expert i ... diately chana·· the control otate deacripdon of the parser from "new aentence" to "picture construction". Thh a tate involvu ~he creation of a new conceptual object (called a co~~~t ~n) and aaaociattna with it a (partial) deacription. ~expert proceeds to create this concept, mark it "detendnate" · and terainate.

The ;~uvl~ ex~:f~ runa. The RUN-ME queue now condata of ~a d " --.:lid the expert for "heavy" 1a removed and atarted executing. ~!nee a concept bin Ia currently active "heavy" knows to contribute ita conceptual deacriptiona to thal ~~~. i~ ~~e:f~~o~~a~:.c~~~:~tat!~a~ 8 al~~~!v~oe:~~n I;nth:x~~~ deacribea the aame concept aa the one preceding it in the aentence, on the other hand/ ita expert performs aa tbe "heavy" expert aoea here. Thia !rat atep completed, the word expert must now discriminate among the aany aenseo of "heav( and ~::o~~~ y~~ :e:~nf~ ~~~·~~uti!Yr~~~~rt;: ~rga!:f~··its ~~:n~~ discriminate among the aenaea meaning "having !arge maao", "being in large quantity" , or "being aerloue or emotional".

~~o~:~f~~it~ntifu"!~ ~~ ::~r~het~r~u~ge~. ~~=ht~xe~~~i~~ expert to ouopend 1 it muat apecifi the condition· upon which it is to be reawakened and the ocation in the RUN-ME queue at which it should be placed. The "heavy" expert apecifiaa reaumption when the wora expert to ita right terminatea, the end of the sentence reached, or a new concept created. Before auapending, however! this expert alao poata a memo to the experta on ita r ght, tellin& them to expect one of the conceptual object types that heavy" could describe (e.g. "abatract object"), Expectations in the model are treateA differently from constraints -- they provide guidance but are not binding. The "heavy" expert is now suspended, and the execution stete of the model corresponds to Figure 1.

The resumption of suspended word expert proceasea ia throuah spontaneous mechaniame which raapond to both conceptual information and changea in the control atatea of model proceaaes. The restart condition· may be quite complex in general, and have been modeled after the apontaneoua com~utationa of Rieger [12). When a restart condition involves pro iii control states, it is called a control state demon. For control state demons to be practicable,~n~ ~au of information about the control structures of the model must be maintained. In the Word Expert Parser, the bulletin board is the center of this control knowledge:---coRtr~tate deacriptions of word experts, the paraer itoelf, and the concept bins tre delineated on the bulletin board. In addition 1 the model a expectations, such as those contributed by the "neavr" expert above, are posted on this board. By making th s knowledge of proceaa available to the word experts, control states and expectations of various model components can affect the execution of the others.

~~ e~f~~th~~c~~c~~=i~~r~~wo~oni~~~~.wit~i~e :;pe~~ procesa contributes its conceptual information to the exia~ng conceet bin! and as a consequence of "heavy"' a expectations and "rain 's s mple usage, immediatelY, determines ita sense and terminates. Termination of "rain' causes the apontaneouo reoumption of the "heavy" expert, which continues processing where it left off. Since two of "heavy"' s three aenaes become meaningless in describing rain, the "heavy" expert resolves upon "belnf in large quantity" and terminates. This cauaeo the model a single concept bin to cloae, completing the parae.

The control poooibilitiea are clearly quite complex, and the proceaoinf is not always going to give as clear and aucceaoful parae aa t did on "the heavy rain". However, the Word Expert Paraer ia a model of cognitive proceoaing, and aa such, the otete of the paroer after incomplfte processing must be of poychological appeal. The paraer 1 actions on ambiguous inyut \extremely rare when conaidered contextually) demonatrates t· coaency -- the end result would be a collection of partiall> completed suopended processes, coupled with a set of reawakening conditions apecifying the reasono f9r the ambiguity (actually, the requirements for its resolution).

3.2. Workspace Repreaentation

~er::~~~~ae ;:vela~~1ti~~;ep~fl·v:l ~~~~~ti~; th:.:~!!t~~: dafabaae · . The ~ata in a bin of either workspace ia therefore acceaaible by any of ita contenta and in fact, declarative repreaentationa can be retrieve~ aaaociatively from any bin. Deocriptors of a particular conceptual object can be acceaaed by the internal name of the concept (its bin), and more aignificantly, the objects in the concept-level are retrievable by their deacriptiona. In this way, a word expert determines the nature of any concepta in the workapace that could influence ita actiona.

The Sentence Level Workapace. In the initial state of the }! .~ Woi'if'"bins contiin tWO' piacea of information -- the iteral word corresponding to the name given it bi the paraer e.g.! "the" for WORD!) and the left and right ne ghbora of the word n the input aentence. These word bins acquire a more aubtle and interesting role, however, as the word expert procesaea are initialized. At thia point, ea~h word bin containa the reotart information (atack frame !13)) for the proceoo, including ito local variables and bindings, and inatruction pointer. By repreaenting this information in the word bins, a word expert can eaoily conatrain another bl oimflY ~!!~!~' ei;~utt~~~l variables or the place that it a arts or

The Co~rE~ Level Workapace. Each concept in the paraer haa a ~e ~ntiind the kind of information folind in its concept bin, The paroer counts three ouch conceptual objec~ types, pictures! ~gtU;,~· arid evento. A picture concept !14] involves phliica a act ob~and their deacriptiono. A oetting a a time, location 1 or situation. The creation of a setting ia frequently introauced by a preposition in the sentence. For example, .. in the morning", "in the house"', and "in trouble" are examples of time, location, and situation examples (reapectively) of aetting concepts. Event concepti conoiat of conceptual caae schemata.

The Bulletin Board. Poated on the bulletin board io a collection 15T""c~tTtF'Tnformation abont the proceaaing by the aodel. The proceao otate of each word eKpert in the model, the otatua of each conceptual object, and a deocription of the atate of the entire paraer are founa on thio board. Any opontaneoua computation triggered by aome in4ication of coQtrol atate io attached to a memo poating function (or oerver [15J) on the data channel to the bulletin board. ------

~=t~~;dNf~£~f~T~~t~~rp~~¥u~-~8N~¥luc¥foN~he following global SETTING-cONSTRUCTION, EVENT-CONSTRUCTION, or UNKNOWN. These designations describe the actiona of the paroer as a whole and are based on lower-level descriptions of expert states and concept states. A concept can be UNOP!N, OPEN, or CLOSED, depending on ita state of completion. Word experta are proceoses and are therefore described by the states INACTIVE, SUSPENDED, and TERMINATED. Ao work on the Word Expert Paraer continues [16) 1 refinements of theae otate descriptions will emerge, clarirring the strength of our work aa a process model of human cognit ve behavior.

*The modularity of the experts requires that external manipulation of restart pointera be carefully controlled. Each word expert contains a descriptive header that explicitly stateo how the expert may be constrained.

3.3. ~~Discrimination Experts

The principal knowledge structure in the Word Expert Parser is the word sense diocrimination expert. A word expert is a representation of the linguistic knowledge (procedural) needed to disambiguate the meaning of a single word in any context. A word's context includes both sentential and conceptual information -- not only are the immediate lexical neighbors of a word important, but conceptual knowledge of the entire text and t~~n t~e e~~aic:i ~~ldp:~1o~=q~~~ta1s~~~;f~!tf~n ~~~~;:~r~:icg asking context-ref:ted questions of the various components ot the parser or the story comprehension model in which it is embedded (see [7) and [8) about the GRIND story understanding model).

The important aspects of a word expert are the questions that it asks (and of whom it asks them) and the actions that it performs upon receiving the answers. Sometimes an action is taken ~=;~~~~on ~~tila~~ef~for::~~onf~~t~~~i~tle n~el~ntiru·~~~;~f states are reached at which point the availability is likely (or non-availability is significant). Other word expert actions include creating and building up concepto, constraining other experts, posting expectations on the bulletin board, and changing the control state of the paroer.

3.3.1. Word Expert Structure

Each word expert exists in two forma in the model -- a declarative representation which is a direc~ed acycli~raph and called a word oenae diocrimination network or aense ne ), and a procedura't-"TeytiiEritltibh like a-eomtttt ge'!ll'rft'o or ataek group [17)) which 1a called a word ~;~:rt gr~~:r;· Both representations are briefly diacUJJed , an raisons d'etre explained.

Network Resreoentation. A word sense discrimination network is a ~ te teientition of the contextual disambiguation of a single word. Thia structure was motivated by the central theoretical notion of the oenae net theory of languaae, that each word of Englioh carries with it the information neceasoary to determine ita contextual meaning. Each node in a sanae net represents an ordered aet of decialono that converge on a single appropriate sense of a word.

An example network for "deep" 11 shown in Figure 2, and ohowo several of ita aenoea. The first two queotlona of the ne;work are aimed at determining if "deep" denotu an obl~t ("the deep") or a deocription (e.g., "the deep thouglit ), Aa a question is answered one brancn of the graph is favored over others, and the number of possible senaes of a word ia reduced. Finally, a terminal node io reached, and a oingle word aenoe chosen.

The possibility arioea that a question cannot be anawered ~~~·~=~ a!;il~~r:~daino~u~~f~~=~!~naf~~.~th:;tne;~iksr~~o!~ ita location in the groph and wait for the information it needa to continue. Another aspect of inter-network activity io when a sense net determine· constraint· on another -- a network waiting for certain data io told to reotart at ita root node, or told to resume at a different node than it expecta. The influence of one senee net on another reflects the crucial contextual nature

~f their word sense disambiguation tasks.

:en·:ss a~Sg~f:ihi~~8hn~er'~r~ 0 i~to E:~e!~ec~~;~!! pi6c~!!e:he~·t~· is first called to perform its task. Although every word expert hes a representation as a sense network. this graphic representation lacks important aspects of a true executable expert process. In particular, whereas the details of an. expert's suspension and resumption, or interactions with other experts, may seem irrelevant at certain levels of explanation, they are in reality quite significant to the view of the paraer as a process model of human language analysia. The network representation also fails to capture the important side-effect actions performed by an expert. The structure and execution of word experts therefore will be outlined through the process ~e~~~=~g~~:ig~~ev~~~ ~f1!nc:~f:f~~~ ~:P~!~}~1~raph structure as

The compilation of a word expert is significant in that certain. nodes of a sense network may be pruned away before it becomes an expert process. ln this way, contextual information about the plot of a story, its characters, the current focus (aee 118)), and so forth, can be used to eliminate a word's irre evant senses . In reading "the ship cruised" in a nineteenth century story for example, a aenae of " ship" denoting something which travels between planeta can be pruned away immediately. Certain constraints cannot be made a priori, however, and in such cases, an already compiled process must be manipulated.

Word expert proceaaes are implemented in the model in a manner resembling CONNIVER ~eneratora. They can be auspended in the ~!~f!~yofo?xe~~ii~~ranpa~~=~=~ s~~~:ne~~~t~deac~~~dig!iytoth! standard patterns of conceptual dataL but data about the control states of other processes as well. rrocesaes can commmunicate by affecting the local variables of another, including those which tell the proceaa where to atart (or reaume) execution. Thia effectively prunes the implicit graph atructure of the expert. Word expert processes also provide information to other ~~f!;~~nb~ 0 ~~~~ing control data and expectations on the central

3.3.2. What~ Experts.£!!!.~

The role and significance of word experts in the model are most easily understood through an examination of both their internal actions like the queationa they aak, and their aide effects, actions that affect the rest of the model. A word expert can aak questions about the other words of the sentence, concepts ~~;r~~~~~~i s~~~:;t~ii~~~er ~~r~~~tr~ :;;!~to~a~heaf1;~~r,t~~ data found in word bins, concept bins, the bulletin board, and the process restart queue of apontaneOus computations.

Internal Process Actions. The fundamental internal actions of a ~r"~~nt:ttut2~:t!~~~~~angina~ev~l~nc~~~g.of 0 ~~eofw~~~ Expert Parser is the taxonomy of context-pro~ng queations aaked by experts. The nature of some of theae queations is emerging and is of several varieties-- lexical, conceptual global, and control. This last category consists of questions about the state of the cognitive proceasing task thus far, repreaentationally encompassing the states of word experts, the parser state, and the states of the bins.

The existence of a particular word to the iiiUDediate left or right of a given word can often discriminate among its aenaea. A word expert asks about the nature of the worda ar~itrarily far to its left and right in the sentence. Furtheraore, it can aak about a word's senaea lin totality or only those still remaining) through the word s conceptual categories, aubclaaaes of these categories, or the explicit names given to ita aenaes. When a word expert ia constrained, the pruning aay be done along any of theae same dimensions.

Conceptual information ia usually very important in diacriminating among word aenses, as are the poated expectation> about this information. The concept bin to which the executing proceas contributes also contains conceptual data from other ex~rts which is often crucial to understanding the current word. A simple example was given in the model overview, when the "heavy" expert needed information from ita own concept bin (i.e., data regarding "rain") before it could determine the correct sense. The concepts to the left and right of the active concept are uaeful in the same way. It ia likely, however, that in the initial left to right scan of the aentence, concept bins i~di~:t~!g~~~f.·.t:r~~ o~~:re~ 8 ~ca~ 0 ~f le!en~:~~·ia ~!ficf:~~ to parae it only if no expert needs information from concepts to its ri~ht. The organization of the Word Expart Parser therefore ~~~~;.· our common aenae intuition about conceptual parsing by

The Word Expert Parser is embedded w1 thin the GRIND a tory comprehension modfl, and as suchL has access to the global world of a children s story. xelevant aapecta Include the pereonalities of the characters, interactions among characters, the plot line, anaphoric rererencea, and current foci oi interest. The plot of a medieval atory! for exam~le, might tell the reader that "knighta", "lords", "ma da", and workera" take certain strict interpretations in local contexta. Or the focus of understanding in a atory might be the Algonquin Round Table, in which case "the deep" ought to be interpreted aa referring to those intelliaent peraona who regularly ate lunch together at that hotel. Global context aignificantly influences the understanding of certain aentencea of texts.

~~p~;:§i 1 fii~R:t ~o~~~o!nfni~~~;~!~~ i: 8 ~~~;ss~~let~~ (and often used bv) the discrimination processes. The fact that the expert to the · immediate left of the executing expert is suspended, or that the expert to its right has not yet executed. is often the central datum enabling its successful termination . The state of a concept bin is also useful information, particularl y in deciding where one concept ends and the next begins. A concept bin is closed only when the conceptual notion it represents is complete; that is 1 when a change in ita data requires the kind of severe backtracking that humans perform extremely rarely (on so-called "garden paths"). In the example parae of " the heavy rain" , the control state of the parser aided the executions of the ''heavy" and "rain" exrrts. Control state ~fo~~=~g:en~:nc!~~da~~n~~~ht~h;h!ni~~~:~s~~tu~~nc~ytu~~ean:!~!~~ processes and their relationship to the entire model (auspenaion and resumption), the self-examining knowledge of control flow and processing states is fundamental.

Process Side Effects. Conceptual analysis is an inherent part of natural Tiiiguage understanding but not the whole part. As such, word sense discimination br the Word Expert Parser must provide the information it acqu res to other components of a large understanding model to complete the task. Assimilation of new data into a picture of the world (see [19) for a discussion of modeling belief oystems) by making the neceasary inferences, disambiguating references, and ao forth (see [8J), constitute the other facets of understanding a text. The aide effects of the processing by a word expert provide the information required ~~aers~~~J~~~~ .:t~~!f a!"co~~pt~~ces;~ 1 f~~·~r~!s .e~:~ue~~ phases.

Conceptual knowledge is augmented by creating new conce~ts and storing new facts about old. concepts. A word expert s first task is t o determine the conceptual notion to which it ~~~i~i~~~~!; t~fc~n~~ig~r; ~~ni~~ ai{~~ew~~l~h:e;~m~h.~h~h:xe~~~ ~~eisw~~aintot 0 i~!sa~~}fuai~ ~~;t~~~~=~~!.iniih~os~~~c~~~c~~~ ~= active, or if the expert determines that its word starts a ne­ concept anyway, the word expert would open an new one. It is possible (in certain circumstances likely) that an expert would not know which bin to contribute to -- in this caae it would suspend its execution until the expert to its right has executed (this is usually enough).

When a word expert has determined its concept, it may atore facts there. If it opens the bin itself, it must provide a type (picture, setting, or event) to the bin. Otherwiae, it may provide the concept's class , or augment its descriptor. An expert that completes a concept may cloae ita concept bin, indicating that its word ia the last (rightmost) one contributing to that concept. If all expertf farticifating in ~~.;o~~~P~o~~=r~ 0 ~~e;oa:rm!~t~e~l:~~nao~:m~n t~e~l~;.e~g;·bi~ when the last of the relevant experts terminates.

~s:~~1 e:g!~iya~~ 0 t~!f:;i:er~er¥~!~e !~;e;~~~em~r~aim;~~~;~~r!~J include suspending itoelf and constraining other experts. The example execution of "the deep pit " (see below) demonstrate· this constraining action -- since neither "deep" nor "pit" can determine its correct aenae on the first trx, "deep finally tells "pit" to be one of the thinga that "deep can describe , namely, a hole in the fround or a peraon. It does this by changing the place in "pit" a network where it begins execution thus making it believe that it had successfully discriminated farther than it really had. After constraining it in this wa~, ~~s~a~!~ i~~e~T"g~~ih.~; ~~!~ .. P~~e~ 0 ~et~i. b~~~PH"!m~~' t e

t~f~~~io~usr:~:: if~ e~~~ti~~o~!e~~~g~od~:~ ~~I~ ~~cu~=~t~~~ expert stops execution and plants a demon to wake it up when the fact it needs becomes available. Theoe facts can be of any varietr, including data regarding the states of other proceaaea. A ty~ cal suspension consiata of an expart proceaa needinJ !~~~iningu~~~T ai~oth!:t-:::~~f=~ f~3§;~~Efi 0 o~t~~l~~¥to)a~o reoume. Another example in "in the morning" involves a setting, where the "in" network waits until a picture bin is cloaea before it resumeo. At that time, it can complete ita own setting concept, knowing the claaa and description of the picture to ito right. Ao a reault of theoe euopenaiona and spontaneous resumption· the range of control flowe in the conceptual analysis mOdel is wide and complex -- our confidence in the model's cogency is only atrengthenP~ by thts varietv.

3.4, Example : ~~.£.!.!.::

The Word Expert Parser is illustrated below through the example phrase "the deep pit ". An actual trace of the parser's execution is presented, accompanied in the righthand column by some explanatory annotations. The example phraAe causes the creat ion of a single concept of type "picture". The word sense ambi~uity of the component words causes a number of expert suspe nsion~ and resumptions, demonstrating the strength of the

sys tem.* Execution of "the deep pit" is an interesting example of the complexity of control flow in the Word Expert Parser. Since both "deep" and "pit " have more than a single sense , they must exchange pieces of information about themselves before either can succeea at determining its sense. EVAL : (r.PARSE: TilE DEEP PIT) C0~7ROL-STATE: NEW-SENTENCE VALUE: T EXECUTING 'THE' EXPERT: WORD! *****TRANSLATING SENSE EXPERT FOR WORD! **EXPERT COMPILE TIME: 56 **OPTIIIIZATION TIME: 1237 *****EXPERT FOR WORD! TRANSLATED ····) AT NODE: Nl NEW CONCEPT: CONCEPTI TYPE: PICTURE CONTROL STATE: PICTURE-CONSTRUCTION EXPERT TERMINATED: WORD! EXECUTING 'DEEP' EXPERT: WORD2 *****TRANSLATING SENSE EXPERT FOR WORD2 **EXPERT COMPILE TIME: 281 **OPTI~IZATION TIME: 5808 *****EXPERT FOR WORD2 TRANSLATED ····> AT NODE: NO ····> AT NODE: Nl EXPERT SUSPENDED: WORD2 EXECUTING 'PIT' EXPERT: WORD3 *****TRANSLATING SENSE EXPERT FOR WORD3 **EXPERT COMPILE TIME: 307 **OPTIMIZATION TIME: 5852 *****EXPERT FOR WORD3 TRANSLATED ·--·> AT NODE: NO ····> AT NODE: Nl ····> AT NODE: N2 **RESTART DEMON FOR WORD2 TRIGGERED: * (*EXPERT-STATE* WORD3 SUSPENDED) EXP~~¥~D~bEk8~D~oeg~D~UEUED FIRST EXECUTING 'DEEP' EXPERT: WORD2 ····> AT NODE: Nl --··> AT NODE: N4 **RESTART DEMON FOR WORD) TRIGGERED: * (*EXPERT-STATE* WORD2 SUSPENDED) **EXPERT !'OR WORD3 QUEUED LAST EXPERT SUSPENDED: WORD2 EXECUTING 'PIT' EXPERT: WORD3 --··> AT NODE : N2 ····> AT NODE: N3 CONTROL STATE: UNKNOWN **RESTART DEMON FOR WORD2 TRIGGERED: * (*EXPERT-STATE* WORD3 TERMINATED) **EXPERT FOR WORD2 QUEUED FIRST EXPERT TERMINATED: WORD3 EXECUTING 'DEEP' EXPERT: WORD2 ·--·> AT NODE: Nl ·--·> AT NODE: N3 ····> AT NODE: N2 EXPERT TERMINATED: WORD2 CONCEPT CLOSED: CONCEPTI VALUE: T EVAL: (~SCAH 'CONCEPTI) 1 *DESCRIP* !SIZE-DIMENSION DEPTH) WORD2) *DESCRIP* SIZE LARGE) WORD2) *DESCRIP* VOLUME-TYPE HOLE-IN-GROUND) WORD)) *DESCRIP* CLASS VOLUME) WORD3) f *DESCRIP* DETERMINATE WORD!) *CONCEPT-CLASS* VOLUME) *CONCEPT-TYPE* PICTURE) VALUE: CONCEPTI air in the ground.

The %PARSE function initializes tho parser workspace by retrieving (from a disk file) the word ~xperts for the input phrase, and creating for each one an associated data repository called a "word bin" . Each word expert is placed on the RUN-HE queue. and then executed in turn, with the experts themselves eventually determining the flow of control in the model.

The word expert for '' the" is translated from a ne twork representation into a coroutine which is then executed. It creates a new conce~t of tyRe PICT6RE, changes the parser state to PICTURE-CONSTRUCTION, and terminates.

The "deer expert is translated and started executing. After a ~~on. M~l. h~~~:rlh;t .. ~~~ll·e~~;~~m~~!o~0~r~tth~u~r~texfif~ "deep" temporarily suspends execution until ''pit"'s word expert has SUSPENDED or TERMINATED, Although permitted to do so, "deep" posts no expectations and D'takes no constraints, thereby insuring that the expert for "pit" has full freedom.

"'Pit" now ~~ns! but G&nnot di,criminate bet'men ita two noun senses of fru t pit and "hole in the ground·. It suspends its execution until something happens to help resolve its word sense ~::~!k~~~d. Since "pit" has now executed, "deep" is spontaneously

"Pit" now runs for the last time, its conatrainta focusing the discrimination, Since "pit" terminates, the restart demon for "deep" is triggered, and "deep" is queued,

Finally, "deep" runs for the last time, teminating with sense of "large volume". Although "pit" tried to close ~y~~~~a ~~ncl:~:er~es~~~~e~dw~~~ !~~~uat1~~1=~~d~o a~~=~n picture concept is now closed and the parae complete. th· its was the

As the Word Expe~t Parser analyzed the input phrase, it created and augmented a data repository of conceptual information. This "concept bin" contains description of the meaning content of the phrase as well as various pieces 9f control state data. The concept bin for "the deep pit" is called CONCEPTI and contains several descriptors which together deacribe a large volume of

4. ~ and Conclusions

We have mapped out a theory of organization and control for a meaning-based language understanding system. In this theory words, rather than rulea, are the units of knowledge, and aaaume the form of procedural entities which execute as generator-like coroutine&. Parsing a sentence in context demands a control environment in whi ch these experts can ask questions of each other, forward hints and suggestions to each other, and suspend. Our tneory is a cognitive theory of both language representation and parser control. It has stemmed from feelings about th· fundamental inadequacies of rule-based theories.

tn addition to the advantages already discussed, the word expert approach enjoys a number of other pragmatic and theoretical advantages. By way of conclusion, we enumerate what we feel are the important theoretical and practical characteristics of th~ theory.

1. It allows for the modular growth of language knowledge in the implemented model. Unlike a rule-baoed system (where obscure interactions and dependencies among seemingly unrelated rules can occur), each word expert is a relatively perspicuous, central aggregate of knowledge about one easily identified unit of language knowledge, i.e., the word. One can look at that structure and more easily say whether or not it takes any given usage into account. If it does not, it is clearer where knowledge about that new uaage should be grafted in.
2. It encourages a healthy type of redundancr in the codification of language knowledge. When writ ng a word exf:rt, one's goal Is to create a stand-alone agent ~~n~ex~~. fuU~ti~~ve 10 no~ic:adeth~~ri~~Is ~!arl~u~i~!;: leads to bi-directional handshaking when two experts interact; they come to some mutual agreement because they find common ground. This type of redundancy is healthy, since it is then leos likely that the shortcomings of one expert will block the comprehension of the sentence or concept In which that expert occurs.
3. It suggests some approaches to language acquisition. Since each word expert reflects the state of knowledge ~~~~!i:e~~venr~h~f w~~nne:ri~i~:s ag~ol~~= ~~f~s 8 ~~ g~=~~~bewf~~i~ewt~~nt~~A ~~p~~t~ 0 ~~i~ 1 ~r;~c~r~=e~ o~!~ ~=~~~;e ~~~ r~~=ti~:wd~;!:~~n;~ 1 ~~~~!~el;h:im~t!~t!~~ safer o~ration than generating an entirely new rule. Since the scope of the change is intuitively smaller, it is lesa likely to interfere with other experts in the system.
4. It encourages the codification of idiosyncratic uses of language by providin¥ uniform data structures os focal fg~~~ 1 isf~~ e~~;ri~ ~=~=: ~?o~~=d~rd l{ak!R~ ~~:mg!:d only sprout a branch of the "take" expert's decision logic to include it. Because of the branching logic organization of the experts, little overhead is incurred by adding special cases. We have felt all along that an organization which encourages knowledge about individual words to grow to large proportions r;t~~~~l~e~~:~~~~l!~e efficiency of the syotem at large
5. It adapts well to largeness. Even if there are 100,000 word experts, each of which on the average requires 1000 words of computer memory, actual memory s~ce required to parae any given sentence will be small. ~!~1!:dbi~a~~: ;~~t~~~=e~tr~:~ar~~ b~n}~ c~~:. ~hf:rf! :ys~~:s~he~=q~1Ie~~tru!~:nmu;~g:re~ep~ 0 i~ar~~reru!~ once (for efficiency) or where potentially complex paging systems muot be Aevised to interact with a rule system on maos otorage. While this is strictly an engineering ieaue! it has immediate consequences on today's computer·
6. It forces the parallel development of cognitively plausible theo~les of se~uential, eoroutine-like process model· of humans. If tne aoaumption about word (rather than rule) primacy in human· io correet we stand a chance of aaking reasonable conjectures a~out flow of control in a human language understander. That isi some fairly criop pictures of word expert control fo low directly from the structure of the word experts themselves. As we discover how to control the experts in a LISP model, we may also be discovering how humans think when comprehending language.

Although much remains to be worked out, we find ourselves increasingly convinced of the appropriateness of the word expert approach. In the near future, we hope to be able to demonatrate the system at work on complete sentences, and hope to provide convincing evidence that large experts with many word uoag< alternatives are practical to develop and coordinate. ·

ACKNOWLEDGEMENTS

The authors would like to thank the following people for interesting diocusaiono that helped refine the ideas preoented in this paper: Phil Agre, Hilt Grinberg Phil London, Jim Reggia, and Rich Wood. In addition, Steve ~mall wiahes to thank Profeooor James Meehan of the University of California at Irvine and Professor Robert Simmon· of the University of Texaa at Austin for comments on the reoearch proposal which led to the parser implementation discussed here.