Knowledge Representation and Natural Language ... [PDF]

Knowledge Representation and Natural Language Processing ~

~

~

~~~

RALPH M. WEISCHEDEL Invited Paper

In principle, natural language and knowledge representation are closely related. This paper investigates this by demonstrating how severalnaturallanguagephenomena,such as definite reference, ambiguity, ellipsis, ill-formed input, figures of speech, and vagueness, require diverse knowledge sources and reasoning. The breadth of kinds of knowledge needed to represent morphology, syntax, semantics, and pragmatics is surveyed. Furthermore, several current issues in knowledge representation, such as logic versus semantic nets,general-purpose versus special-purpose reasoners, adequacy of first-order logic, wait-and-see strategies, and default reasoning, are illustrated in terms o f their relation to natural language processing and h o w natural language impacts the issues. We conclude thatasignificantbreakthroughineithernatural language processing or in knowledge representation could lead to a breakthrough in the other.

I.

INTRODUCTION

The goals of this paper are to introduce the breadth of kindsofknowledge needed to process natural language, some ways thatknowledgemight be used i n processing natural language, and some typical issues inknowledge representationthat arise in natural language processing. The paper will cite some key references for each point, but it is not intended as aliterature survey. Furthermore, it is notintendedto represent thehistoricaldevelopmentof natural language processing and knowledge representation. We assume that the goal of natural language processing is to understandand generate natural language with as much fluency as anative speaker would; in that way we may explore the depths of knowledge representation and reasoning needed. However, this is not to say that certain naturallanguage tasks cannotbe achieved with simpler knowledge representationsandsimplereasoningmechanisms. Systemshave been build that use substantially less knowledge representation and reasoning than are proposed here. An example is METE0 [I]; this system successfully Manuscriptreceived September 24, 1985; revised January 30, 1986. Thiswork has beenpartiallysupported by theNational Science Foundation under Grant IST-8419162. The author i s w i t h BBN Laboratories Inc., Cambridge, M A 02238, USA.

translates weather reports from English to French; a(human)post-editor handles problemsbeyondthe system’s capabilities. The paper covers issues in both natural language understandingandgeneration. Sincefar moreeffort has been placed in the last 15 years on natural language understanding,thispaper focuses more on understandingthan on generation. In principle, aspects of natural languageresearch and knowledgerepresentationshouldbe closelyrelated. First, potentially any fact, rule of thumb, or principle statable in English might be needed i n a knowledge-based system for someartificialintelligence (AI) application. Therefore, the semantics of classes of forms of English is a (long-term) goal for knowledge representation. Second, neither natural language understanding norgenerationcanachievefluency without a wide variety of knowledge and adequate reasoning based on that knowledge; demonstrating that is one of the chief goals of this paper. The goals of knowledge representation include:

-

providing substantial expressive p o w e r , the class of statements that can be made in the language; enabling inference of what is logically deducible from the language; supportingplausibleconclusions.

The degree of success required for each of these goals may vary from application to application. Thevariouskindsofknowledgeemployedin natural language understanding and generation have been divided here o n traditional grounds: morphologicalandphonetic (Section II), syntactic(Section Ill), semantic(Section IV), and pragmatic (Section V); the paper focuses on the semantic and pragmatic issuessince the classes of knowledgerequiredthere are far more general than inmorphology and syntax. Some of the semantic issues discussed are logical form (to represent the meaning of a sentence), case constraints,andpresuppositions. The pragmatic phenomena discussed include anaphora, lexical ambiguity, el-

0 0 1 8-9219/86/0700-0905$01 . o O 01986 I E E E

PROCEEDINGS OF THE IEEE, V O L . 74, NO 7, J U L Y 1986

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

905

lipsis, intention,theintendedformbehind an ill-formed input, vagueness, and discourse structure. Issues in knowledge representationthat are particularly raised in studying natural language are covered i n Section VI. These include: logic versus semantic nets, general-purpose versus special-purpose approaches, support for waitand-see strategies, anddefaultreasoning.Section VI also includes a highly abbreviated introduction to a straightforwardapproach to representing facts i n first-orderlogic. Section VI1 concludes the paper. As evident in the list of semantic and pragmatic phenomena above, it should be clear that a breakthrough in knowledge representation and reasoning would have a dramatic impact on natural language studies. O n the other hand, it is converselytruethatbreakthroughsin natural language studies focussing on the topics above could have dramatic impact on knowledge representation and reasoning, potentiallyregarding expressive power,shallow reasoning, the role of special-purposereasoners (including hybrid systems), and default reasoning. 11.

PHONETICS, SPELLING, AND MORPHOLOGY

Language requires knowledge of morphology, the study oftherelationbetween a word, its root(s), andderived forms. First, if one can recognize regular inflected forms of a word by morphological analysis, one can cut down on the number of lexicalentries in the dictionary. Thisis clearly useful for generation so that one can use the appropriate inflectedform giventherootword,morphological rules, and the features involved in inflection. In thatway, one can generate the present participle form of study without having to havean explicitdictionaryentry for studying. The sameis trueregarding understanding; morphological rules can be used to determinefroma regular inflectedform such as studying, the root form study andthe feature of being a present participle. Second, morphological rules are used to generate novel forms, not present in the normal language. Recently I heard someone use Walter as a verb, with a regular -ed ending to indicate the pasttense.To Walter a situation meant to do what Walter would have done. In order to be able to understand or generate such novel forms, morphological rules thatexplainhowto deriveone formof a wordfrom another are essential. Knowledgeofspellingmight at first seem trivial since morphological analysis andtablelookupmightbesufficient, However, knowledge regarding typical kinds of misspellings seems critical to understanding misspelled input. Many spelling errors can be viewed as typical typographical [2] tries to capturetypographical errors. Onealgorithm errors via several patterns: omitting a single letter, inserting asingleletter,transposing t w o adjacentletters, or substituting one letter for another. However, there are particularpatterns ofspelling errors in English which are not capturedbysuch a simple synopsis.Some spelling errors seem t o arise more from phonetic similarity and/or phonetic transcription than from the kind of patterns indicated in the heuristicfortypographical errors mentioned above. For instance, one can confuse ph and f or spell confidence as confidents. Such ”spelling errors” arise frequently in proper names. A system that is to understand written language as

906

well as a human can would appear to need knowledge of such spelling errors. As aconsequence, some phoneticknowledgewould appearusefulevenforunderstanding systems meant only t o process written ortypedtext.Knowledge of homophones’ is important too for recognizing what is intended when someone uses their for there or fo for too, etc. O f course,phoneticknowledge is critical to understanding spoken input, as it is to generating spoken output. Theknowledgedescribedinthissection illustratesone issue in discussingknowledge representation. Sometypes of knowledge may best be expressed and employed when defineddeclaratively; namely, without reference to the process that will employ it nor to procedural side effects. O n the other hand, some knowledge is best ”compiled”; one way to compile knowledge is to store it in data structures orientedtothe procedures that use it. Spelling knowledgeandmorphologicalknowledge are examples that typically are compiled into tables,trees, etc., used by algorithms for lexical processing. O n e can also “compile” a long chainof inferences by recording the assumptions in the chain and the final conclusion. Thismayproveparticularlyusefulfor encoding pragmatic knowledge used to infer intent behind conventional requests, such as Can you pass the salt? This is not a request about an ability to pass the salt, but a request to pass it. Though reasoning about the intention behinduse of a sentence is critical, the full generalityneed not be used each time as ifstartingfrom scratch. Compilingthe reasoning for conventional forms such as the example above is attractive. Ill.

SYNTACTIC KNOWLEDGE

Knowledgeofthe syntax of a language is clearlyevidenced in humans by various phenomena. It is rather easy and natural for us to correct grammatical errors in language and improve grammatical form, in spite of the fact that we do not employ that grammatical knowledge flawlessly at all times. As a consequence, grammatical knowledge must be a part of a high-quality generation system. Another example of our use of syntax is the humor that results from reading somesyntacticallymisleadingitems such as theheadline Squad Helps Dog Bite Victim. Clearly syntax has suggested an interpretation which we find humorous because of the misleading form of the headline. Furthermore, syntax is a significant knowledge source in understanding; it helpscut downthe space of possible interpretations. Syntax alone suggests theproperinterpretationof Mary kissed John; by virtueof Mary beingin subjectposition,weknowthatMary is asserted as the initiator of the kiss. Similarly, in the following two forms, a very simple syntactic constraint,that a subject must agree in person and number with its verb, determines which of two meanings is intended. 1)

List the assets of any company which were purchased by XYZ Corporation in 1981.

’Homophones are words that sound alike ently.

but are spelled differ-

PROCEEDINGS OF THE IEEE, V O L 74,

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

NO

7, J U L Y 1986

2)

List the assets of any company that was purchased by XYZ Corporation in 1987.

Notice that this knowledge is useful even though subject-verbagreement is a constraintthat is oftentimes violated by poor syntax. Since languagecan be syntactically ill-formed,particularly in speech, inwritten language of disadvantaged individuals,and inboth spokenandwritten language of nonnative speakers, knowledgeofthekindsof syntactic ill-formedness could also prove useful. For instance, errors i n subject-verbagreement i n English do occur at times, though interpretations where subject and verb agree should be preferred. Severalsystems[3]-[SIhave beenbuiltthat employbothknowledge of well-formed syntax andpatterns of possible errors. As seen in the examplesabove, syntactic form is part of theinformationdeterminingthemeaningof an input. Therefore, one would like a strong model of grammar for language generation to help convey what the system means and to avoid misleading the user. For instance, one would like to avoidgenerating misleading headlines,such as Squad Helps Dog Bite Victim. One would like to generate a form that obeys syntactic constraints both for clarity of meaning and for readability. Furthermore, since syntax is instrumental in directing attention from sentence to sentence [6],[7], it is important to correctlyconvey such subtle cues as syntax provides. There are numerous papers thatdescribe formalisms for encoding knowledge about syntax [8]-[Ill. IV.

SEMANTICS

There is n o general agreement on the boundary between semantics and pragmatics. As a consequence, one author’s “semantic knowledge” is another author’s “pragmatic knowledge.”Wewill discuss threephenomenaand/or types of knowledge that we will call semantic: logical form, case constraints, and presuppositions. A. Logical Form

Many assume the following:

-

one of themajor goals ofunderstandingnaturallanguageis t o determine the semantic representation of the literal interpretation of an input; language generation proceeds from some similar semantic representations.

Those semanticrepresentations are oftenencodedin a notation equivalent to a subset of logic and therefore are called logicalforms. Alogical form is generallymeant to capture in an artificial language the common semantics of many varying surface syntactic forms of the language, such as mapping john’s friend and the friend of john into the same form. There are several implications of this: The meaningof any given wordand i t s senses in so that context must be indicated, normally in the lexicon, the word’s semantics might be captured in the logical form. For instance,for the noun sense of ship, we might represent i t s meaning as a unary predicate vessel(x). A mechanism for combining the meanings of the words in an input must be provided, so that the composition of

the meaning canbecaptured in the logicalform. This is often accomplished by designating with a grammatical rule orwiththe structure it produces how the meanings of phrases contribute to themeanings of the whole, For instance, a grammatical rule would say that an adjective can modify anoun;themeaningoftheadjectiveshould be conjoinedto thatofthenoun. Thus, themeaningof American ship would be vessel(x) & american(x).2 There is substantialvariation inwhatone means by logicalform [12]. There areseveral additionalunresolved issues regarding logical form: Shouldthelogicalforminvolvea large numberof predicatesperhaps close to thenumberofwordsinthe language, or should the logical form employ a small subset of primitives whose composition represents the meaning of all the words of the language?Arguments on the side of primitives [13], [I41 and on the side of predicates near the level of the word senses of the language [15], [I61 appear. 1s first-orderlogicsufficient, orare higherlogics required? Some [17], [I81 argue for higher order logics; others (191 believe first-order logic adequate. Howmuch is needed to represent intersentential semantics? A number of proposalsforintersententialrelations exist [20]-[22].

-

6. Case Constraints One of the oldest proposals regarding semantics within the linguistic framework is that of constraints on the types of arguments that can fill a given predicate. The constraints may be stated at the level of the words employed, in which case they are called selection restrictions; or at the level of a component of the someabstractpredicaterepresenting meaning of the surface word or phrase, in which case they are called deep case constraints. The value of these constraints is to eliminate interpretations that are inconsistent with the normal world. Since these constraints state normalcy conditions on the arguments of predicates, one tries t o assign classes to what canbedescribedbycommonnounsandproper nouns, since they generally identify argument fillers. Similarly, one tries t o assign to the predicates of the language ( e g , verbs, adjectives,prepositions,etc.)constraints on the types of argumentsthat may appear with the givenpredicate. For the sense of ball as aformal dance, we would assign its class as a social activity; for its sense as a spherical physical object, we would assign it a class of physical object. For the adjective green in i t s sense as acolorofsomething,we could say it requiresaphysical object as argument; in its sense as unripe, we could say it requires a fruit or vegetable as itsargument; i n its sense as immature, we could say it requires a human as its argument. Given that analysis, the phrase a greenball has only one interpretation satisfying the selection restrictions on green; namely, a green colored, sphericalphysicalobject. Of course,such constraints are not sufficient to totally disambiguate the senses employed i n a sentence, even when all syntactic information is used as well. For instance, the sentence I am looking for a ball, ’This is just one simple rule about premodifiers of nouns. Other rules would account for phrases like former champion, which does not mean former(x) & champion(x).

WEISCHEDEL KNOWLEDGE REPRESENTATION A N D NATURALLANGUAGE PROCESSING

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

907

allowsboth interpretationsfor ball, since one mayseek either a physical object or a social activity. Such constraints may beemployedforeliminating an inappropriate interpretation arising from ambiguous syntax, as well as those arising from lexical ambiguity. In Show me the location of all ships deployed last week, the reduced relative clause deployed last week couldmodify location or vessels. Though there is some syntacticpreferencefor the reduced relative to modify the closest noun phrase, it is not a strong constraint compared with semantics; an examships of Spain deployed last week. ple is Showmethe Since theobject ofa deploymentmust be a vessel or collection of vessels, this case constraint can eliminate the syntactic ambiguity in the two examples above. The semantic constraints described above are essentially selectionrestrictions because theywere associated primarilywiththe lexical item used.However, wecould imagine,particularlyifthe semanticrepresentations use a small set of primitives heavily, that the semantic constraints are associated withtheunderlying predicates that the surface words are translated into. Suppose that a single predicate called ATRANS [I41underlies part of the meaning of each of the following sentences: John gave Mary some flowers. Mary received some flowers from John. John sold Marysome flowers. Mary bought some flowers from John. John traded some flowers to Mary for some candy

ATRANSstands for the transfer of possessionor ownership of an entity from someone (at that person's initiative) to another.We can assign deep case constraints to the arguments of ATRANS rather thantothe surface words give, receive, sell, buy, and trade. Therefore, the actoror agent of an ATRANS must be a person or, institution. The object argument of ATRANS must be a physical object, etc. Whether one uses more surface-oriented constraints as i n selection restrictions or one uses deep case constraints, the goal is the same: to eliminate syntactic and lexical ambiguity. If onetries t o use such constraints while parsing to eliminatesyntacticor lexical ambiguity, there are some pitfalls, resulting from the fact that the constraints apply t o what is described rather than to the expressions themselves. One pitfall is that certain noun phrases are semantically neutral. For instance, in English the pronoun they can refer t o almost any set of things. The word gift can refer to any physical object other than humans, to anyabstract object such as ideas, andeven to humans in cultures permitting slavery. In the face of such semantically neutral terms, the case constraints must accept those neutral terms blindly. Asecond kindofproblem is figures of speech. Metaphorical usage allows us to say M y car drinksgasoline meaningfully even though drink requires an animate drinker. Metonymy, the use of a description of one thing to refer to another which is closely associated with it, allows one to meaningfully state propositions such as TheFrederick says that it's R R I radar is down. Vessels say nothing; one means the officers of the Frederick rather than the vessel itself. In a similar way personification lets one say My dog says when he wants to go o u t . Therefore, the challenge in applying these constraints in

908

understanding, as with applying syntactic constraints, is to employ them to cut down the search for meaningful interpretations, while allowing those constraints to be violated a t times. Approaches to this problem have been developed [51,~ 3 1 ~, 4 1 . Thediscussion above has focused on issues in understanding.In generation, inverse problems arise. For instance, i n generatingfrom semanticprimitivesthat use deep cases, one must determine in context which of several words should be representedcorresponding to thepredicate ATRANS.The class ofthe arguments plays acritical role, as do the patterns of formulas;oneapproach to this problem has been developed [25]. Also, i n generationonemustdecidewhichinformation t o presentandwhich to suppress. This will affect the surface order and convey slight differences in meaning. For instance, Someonebrokethe vase and The vase broke conveymuchthe same information,thougha clear difference in meaning i s present. Furthermore, Someone broke the vase and The vase was brokenbysomeone have a differentimpacton focus, which may affect pronominal usage [7], [26]. To generate a figure of speech, the systemmusthave a model of the goal to achieve in using one, when it is likely to be understood,andwhenit is preferable to a literal description. This is an area for future research.

C. Presuppositions and Entailments Inference is at the heart of both language understanding, and language generation. Though many inferences are context-specific and highly dependent upon the belief systems oftheparticipantsinthecommunication, there are two classes of inferencesthat appear particularlylinguistic ir-1 nature, that is, dependent only on the syntax of the input andonthe lexicalitems present in theinput. These arc' presupposition and entailment. Though their definition has been at times a matter of debate, we will assume that thev are semantic, rather than pragmatic, in nature. A sentence S presupposes a proposition P , if P must be true whether S is true or false. That is, if a presupposition is false, thenthe sentence S is anomalous.Presuppositions seem to arise from two sources: the use of particular syntactic constructions and the use of particular lexical items. As an example, all definite references presuppose that there is some entity that can be referred to. Thegreatest prime speaker benumber is 23 seems to presupposethatthe lieves that there is a greatest prime number; the fact that there is not, makes theutterance seem anomalous to the hearer. Other syntactic constructions exhibiting this semantic phenomenon include cleft sentences and nonrestrictive relative clauses. The cleft sentence It is John who the sentence left seems to presupposethatsomeoneleft; Richard,whomI'veknown formorethan 15 years, is sometimes difficult to get along with seems to presuppose that I have known Richard for more than 15 years, whether is sometimesdifficult to get alongwith.An ornothe interesting sidelight ofthisdiscussion is that the use of a syntactic construction can, therefore, carry meaning, since presuppositions are definitely part of the meaning representation of sentences. The use of particularlexicalitemscan also conveypreI regret thatsmoking is not suppositions.Thesentence

PROCEEDINGS OF THE IEEE. VOL

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

71.NO 7 J U L Y 1986

permitted in the auditorium presupposes thatsmoking is not permitted in the auditorium whether or not the speaker regrets it. In a similar way, to say John failed to meet his deadline seems to presuppose that John tried to meet his deadline,whetherornot he was able to do so. Awide variety of lexicalitems have beenidentified as having presuppositions [27]-[30]. Asentence S entails a proposition P if P mustbetrue whenever S is true. The last example above, illustrates that some lexical items have entailments as an indigenous part of their meaning. That is, john failed to meet his deadline entails that John did not meet his deadline. A few systems have incorporated presupposition computationandchecking as a means ofprovidinghelpful responses.Since the presuppositions as defined abovearise from the use of particular syntactic constructions and particularlexical items,and since certainentailments arise directly from the use of particular lexical items, they could becomputedduring parsingandsemanticinterpretation, since they are part ofthemeaningrepresentationofthe sentence. A parser that computes presuppositions and entailmentsofthekind described above has beenimplemented [31],[32]. Kaplan [33] showed how the failure of presuppositionscorrespondingtothe existence of a nonempty set, e.g., those corresponding to definite references, couldbe used to trigger helpful responses in a database question-answeringenvironment. For instance,thequestion H o w many students failed CSlW last semester? presupposes that some students failed CSlCG lastsemester. If i n fact the course was not offered at all last semester, it is better to answer CSICG was not offered last semester, than to respond potentially misleadingly with the answer None. The class ofhelpful responses could be much greater than simply those corresponding to failures of extensional a presuppositions,i.e.,thosepresumingtheexistenceof nonempty set. Anintelligent computer-assisted language instruction system[34] demonstrated how presuppositions could beused t o detect several kinds of student errors including:

-

inappropriate use of some words, not answering the question posed, generatinganoun phrase that has nomeaningin context.

It seems unlikely that the full potential of this class of inferences has been employed yet in natural language understanding systems. Natural language generation must verify before selecting a particular lexical item or syntactic construction that any associated presuppositions are true. V.

PRAGMATICS

It is i n pragmatics that one encounters the greatest variety of knowledge neededto supportnatural language understandingandgeneration. Furthermore, it is in pragmatics thatone sees thedepthofknowledgeandvirtualunboundedness of that knowledge i n order to fully use natural language. We divide this section based on a number of linguistic phenomena that exhibit the variety of knowledge needed; however, this is not intended as an exhaustive list of thephenomenaneeding such knowledge.Inthe next section, we turn to issues in knowledge representation that

particularly pertain to nomena.

natural language problems and

phe-

A. Definite Reference

Definite reference is the usage of a term to identify some entity recognizable in the discourse context. An interesting thing about such expressions is thattheyobeysyntactic, semantic,and pragmaticconstraints. For instance, in John shot him, him cannot refer to John if the language is being usedcorrectly. A syntacticconstraint on such pronominal usage has been called C-command [35]. Naturally, semantic constraints come into play as well; in the example above, if the language is being used correctly (and nonfiguratively), then him could only refer to a male person. Unfortunately, examples seem t o indicate that an almost unbounded class of pragmatic knowledge is necessary to understand some definite references. For instance, The soldiers fired at thecondemned, and they fell down,seems to require common sense reasoning. Syntactic and semantic grounds do not eliminateeitherthesoldiersorthecondemnedindividuals as thereferentofthey. No matter whether as phrased above, or as The condemned were fired at by thesoldiers, and they fell down, the preference is still thatthey refers to thecondemned. The common sense reasoning that animate entities that are fired upon may be hit and that entities thatare hit by projectiles may fall down makes theinterpretationwherethey refers tothecondemned individuals more likely. (Of course, it is this preferencethat would make a skit,where the soldiers fell, humorous.) Anotherexampleillustratingthe same point is due to Winograd [36]. Comparing the following twosentences, we see that knowledge about what is normal seems to affect the interpretation of the pronouns. The city councilmen refused the protesters a permit because they advocated violence. 2)The city councilmen refused the protesters a permit because they feared violence.

1)

Knowledge of what city councilmen are likely to be concernedabout and whatthey are likely to advocate compared to protesters seems to shift the preferred interpretation of thepronounthey. Consequently, knowledgeof what is plausible comes into play. Similar problems arise with otherdefinite references, such as definitenoun phrases.These neednot refer to something that was mentioned previously in the discourse. For instance, it is perfectlyreasonable t o say I finished a novel the other day.The author had only written nonfiction before. Knowledge that books have authors, and that novels are books is necessary to understand what the author refers to. Consequently, a second type of pragmatic knowledge is about class hierarchiesandtypical associations between classes. As with spelling, syntactic, and semantic knowledge, it is certainlypossible to violatethenormalcy constraints of languageregardingdefinite references as well.Goodman [37]reports o n variousrelaxation strategies formodifying definitedescriptionsthat have n o referent so thatthe modified description does have one. Constraints on uses of anaphora can also be violated. In Boston, the Red Line of

WEISCHEDEL KNOWLEDGE REPRESENTATION A N D NATURAL LANGUAGE PROCESSING

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

909

the subway system splits at a certain point into two differentroutes.Alongtheportionofthelinewherethetwo routes are the same, a woman entering the subway asked me Does this go to Braintree? I replied I don't know. I get off before it splits. In the last utterance, it must refer to the subway line, which had notbeenmentionedintheconversation at all.In spite of myapparent violationofthe rules for generating understandable anaphora, the woman seemed t o understand. The problems for generation are manifold: H o w canconstraints as indicated above be used to generateunderstandablepronounsanddefinite descriptions? Whenwould insertionofapronoun make thetext more readable? How much should adefinitedescriptioninclude/exclude to make the identification of the referent clear to the listener without being verbose?

-

the example above, the appropriate sense of run into is to enter. Correctly handling such cases of lexical ambiguity is an unsolved problem. to lexical ambiguity Applying pragmatic knowledge therefore is an interestingproblemshowingthe synergy betweenknowledge representationandnaturallanguage. The need is a means of making a decision among conflicting alternatives by weighing the evidence while still allowingforthedecisionto be reversedlater inlightofnew evidence, withoutblind backtracking.Abreakthrough in knowledgerepresentationwouldhelpinthe most problematic cases i n lexicalambiguity.Similarly, a general approach to the knowledge representation problem springing from study ofthe problematic cases of lexicalambiguity might generalize to a broad class of nonlinguistic problems whereadecision based onconflicting evidence must be made and potentially re-evaluated if new evidence surfaces.

C. Ellipsis 6. Lexical Ambiguity

The problem of lexical ambiguity is to determine which of several word or idiom senses is intended in context. Like reference,lexicalambiguity is a problemthat seems to require knowledge from syntax,semantics, andpragmatics to coverallexamples. Syntactic knowledgeprovides just onepowerful means ofeliminating lexical ambiguity.In Drain lines are always a problem syntax can indicate that both Drain and lines are nouns forming the nominal compoundwhich is the subject ofthe sentence. Semantic information is also quite powerful as indicated in the example, a green ball, in Section IV-B. However,pragmatic knowledge is also necessary, as the following two examples demonstrate:

1) 2)

The policeman found his crook The shepherd found his crook.

The knowledge of those entities normally associated with policemenand thoseentitiesnormally associated with shepherds suggests one word sense for crook as more likely than another. Knowledge of what makes sense in context is critical. (Several techniques [38]-[40] for encoding and using such knowledge exist.) An unsolved problem is when to decide among alternative word or idiom senses. It seems safe to employ syntactic and semantic information while parsing the sentence. However, employing pragmatic knowledgethat early, without thepossibilityof reversing thedecision made on those grounds, could lead to problems. Examples anddiscussion ofthis appear inthe sectionregarding early decisions versus wait-and-see strategies. Asecondproblem is weighingthe various kinds of pragmatic knowledge. An interesting example presented by Birnbaum [41] appears below While / was drivinghome, / remembered / needed some milk. / ran into a 7-11 and picked up a half gallon.

Driving certainly carries along the concept of the potential o f having accidents; having accidents certainly should suggest the sense of run into corresponding to colliding. Yet in

910

Contextual ellipsis is a fragmentary form which in context expresses a complete thought. Again, all three sources of examples, knowledge can be employed. In the following syntactic knowledge suggests the appropriate complete interpretations.

A: B:

D i d you go to New York? Last month.

A: B:

Were you pleased? Very.

In the first case, last month can be interpreted in context as an adjunct on a form resulting from a straightforward syntactic transformation of the request:namely, Last month / wenttoNew York. The secondexample caneasily be interpreted as the complete form I was very pleased. The secondexample seems particularlywell-handledby syntacticknowledge. O n theother hand, the firstexample above requires at least some semantic knowledge to realize that Last month cannot be a reasonable substitutionfor either the description of the person ( I ) or for the description of the city(New York).Techniques based on this have been studied [42], [43]. Thekindsofsubstitutionsthat are possibleneed not follow parallel syntactic forms. An example due to Carbonell [44] is the query What is the price of the three largest single which canbe followedbythe portfixed-mediadisks?, elliptical form Disk with two ports. O n questioning individuals about what the elliptical form meant in thatcontext, largest the generalresponse was What is the price of the fixed-media disk with two ports?To be able to predict that, it appears that one needs to find the semantic parallels and carryoversemanticdescriptorsthat are not replacedby corresponding semanticdescriptors intheellipticalform. Strategies capturing semanticparallelswere implemented i n PLANES [45] and have been extended [44]. Nevertheless, it is clear that syntactic and semantic knowledge are not sufficient either. An example from Carberry [46] is, Could you cash this check for me? Small billsonly,please. In order to understandthefragment Small billsonly, please, it seems imperative to have a model of a plan for cashing checks, in which case identify-

PROCEEDINGS OF THE IEEE, L O L 74, NO 7. JULY 198b

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

ing smallbills has a meaningfulrole.Therefore,another kindof pragmaticknowledgeuseful in naturallanguage understanding is a set of plans for achieving goals. The problem for generation is to know when an elliptical form would be preferable to a complete form, how much can be omitted, and when the knowledge necessary can be assumed common between speaker and audience. 0. Understanding Intention

Natural language systems must be able to understand the intention behind what a usersays ifthey are to respond appropriately, indicate alternative courses of action when a request is impossible to satisfy,or fulfill theinformation needs of the user. Consider how frustrating the following interchange would be to a Navy commander sitting in front of a graphical display of a map with ship locations. User: I cannot see the Enterprise. System: Information assimilated. If the user request is interpreted as a literal statement, the corresponding response, while accurate, is hardlyworthwhile. It appears that a rule is needed that says that if one cannot achieve a goal G, then an appropriate response is to try to fulfill that goal. If the system cannot fulfill the goal G, theappropriate response is to indicatewhyitcannot be fulfilled. To achieve such behavior seems to require not only rules of the kind mentioned above, but also knowledge of the underlying system capabilities, knowledge of the goals and subgoalsofthe user, and knowledge of possible ways of achievingthose goals. Currentnaturallanguageinterfaces do not have that depth of knowledge, and therefore tend to interpret all requests literally. Of course, exceptions can be made to interpreting all requests literally by various ad hoc strategies, such as having a pattern Could you do X ? automaticallytranslatedto a request to perform X . Some very promising research is underway and has been reported [46]-[SO] offering strategies to determine user intention and to employ that in natural languageinterfaces.Responding appropriately when user intentions cannot be carried out is a new area of research in language generation [SI]. Noticethatthe area of user intention evidences the synergy of knowledge representation and natural language processing. To model user intention and providecooperativeresponses,adequaterepresentation of goalsand of planningknowledge is assumed, includingtheability to reasonabout conjoined, possibly conflicting goals. At the same time, natural language descriptions of plans, modifying plans, and analysis of plans offerfodderforplanning research. Abreakthrough in planrecognition in natural language research would carry over to other planning tasks, such as learning plan knowledge from examples and inferring from examples what a (formal language) computer user is trying to accomplish [ 5 2 ] . E, Understanding 111- Formed Input As we have seen in the last two subsections, it is clear that understanding the intention of an individual is critical to providing appropriate, helpful responses and to under-

standing at least some classes of elliptical inputs. Intention is also critical to understanding atleastsome instances of "ill-formed" input, and, more generally, input that violates some syntactic, semantic, or pragmatic constraint. The problemwith such an input is thatthere is nointerpretation which satisfies alltheconstraintsimposed by the various sources of knowledge. As a result, one or more constraints must be relaxed. Since the constraints are the mechanism that limit search, the need to relax them opens the search space, resulting in even greater likelihood of finding multiple interpretations. What complicates the situation even more is that one may need to modify the input string itself in order to come up with thecorrectinterpretation.Considerthe case of a typographical or spelling error that results in a word already known to the system,such as to for too or form for from. That something is wrong is likely to be noticedduring parsing, as syntactic and semantic constraints eliminate all possibleinterpretationsthataccountfor allwords in the input. However, there are any number of reasons why that could happen, either from user error or system inadequacy. A partial list includes at least the following: a spelling/typographical error of the kind described, an inadequacy in the lexicon, insufficient grammatical information, some syntactic error on the part of the user, a case constraintthat is omitted or onethat is too restrictive, a semantic error on the part of the user, sometelegraphicform (with one or moreomitted words).

Pragmatic knowledge itself can be violated, as in the examples presented i n the subsection on definite reference. In light of the many possible sources of failure to find an interpretation for an input, any knowledge of what the user might have intendedcould be invaluable in determining what is wrong and what the user meant. Numerous systems for processing ill-formed input or input that in one way or another violates the constraints and knowledge of the natural language understanding systemhave been built [3],[SI, [53], [54]. A systemthat has a strong model of user intent and can employ that model for understanding such problematic input is still a key area of research. Natural language interfaces should do what you intend. F. Figures of Speech

As we have seen in the section on semantics, figures of speechpresentproblemsforparsing since theyviolate normal semantic constraints. In addition, finding the meaningbehind the phrases is a problem. For metonymythis means pragmatic knowledge about possible normalassociations between two entities, such as a part forthewhole, the whole for a part, a location instead of the memorable event that occurred at that location, an institution for the people represented by the institution, etc. One must make that connection so that one knows the intended reference behindthe expression used. Furthermore,thepragmatic knowledge must be able to predict an ordering to the reasonableness of the reference in context. For instance, in the

WEISCHEDEL: KNOWLEDGE REPRESENTATION A N D NATURAL LANGUAGE PROCESSING

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

9 11

following example there are at least two ways the metonymy could be interpreted. Pearl Harbor caused us to enter World War 11.

Presumablytheintendedinterpretation in this case is the eventgenerally associated with Pearl Harbor,namelythe surprise attack by the Japanese on Pearl Harbor. Nevertheuses less, there is another possible metonymy where one Pearl Harbor as thelocationforthe naval baseatPearl Harbor and the institution to represent the officials of that naval base. (Thissecondmetonymy is presumablythe intendedonein an expression such as 70 Downing Street reported today that new austerity measures are planned.) With metaphor one needs to parse the sentence in spite of the violated semantic constraints and to infer the figurative meaning behind it. Having a way ofacceptingforms that violate semantic constraints is only part of the understanding.Lookingforfigurativemeaning, e.g., any invited inferences, is also critical to understanding. In M y car drinks gasoline, theviolated semanticconstraint is thatonly animateentitiesdrinkliquids. The pragmaticknowledge that animate objects typically drink liquid to sustain life is the key to suggesting that the car consumes gasoline like an animateentityneedingto sustain itself.Giventhat basic knowledge, it is possibletoinferthatthe car in question consumes an abnormal amount of gasoline. As with metaphor,similarproblems can arise with personification. The need to draw an inferenceintendedby the speaker is evenmore clear perhaps with examples of “depersonification,” referring to a person as if he/she were not one. The expected inference in the sentence, For that behavior, that turkey should be expelled, is that the person referenced is as stupid as a turkey. Figures of speech are still a fertile area of research. Though we have discussed them from the point of view of understanding, it is clear that substantial problems arise in generation as well, for the system must be able to identify whether an association iseasy enoughforthelistener to recognizebeforegenerating a metonymy. Beforethe system could use a metaphor or personification, it must have an implication thatit chooses to conveybythefigureof speech and must be reasonably assured that the listener can draw the intended inference. Figures of speech are not just a colorful way of expressing something; they can convey information highly compactly. For instance, while Someone representing the White House announced today.. .conveys the same information as The White House announced t o d a y , ,. , one is far more crisp. Consider how unwieldly language would be, if one had to say The break-in a t the Watergate Hotel and its aftermath rather than the metonymous expression Watergate.

G. Vagueness Vagueness is such a part ofnaturallanguagecommunication that we hardly notice it. It is certainly one of the key reasons thatnaturallanguagecan express complex ideas succinctly, but is also a key reason that miscommunication can occur. Vagueness occurs frequently in definite nounphrases. For instance, consider that Where w a s it Tuesday? means Where

912

was it on the most recent Tuesday? Proper nouns are also vague, for we may know of many Peters, though in context the simple reference Peter is unambiguous. As with other references, the problem for understanding is to determine is what is intended in context; the problem for generation to determine what description is adequate to identify the entity without making the description excessively long. Vagueness is also inherent in requests that canbe satisfiedinmorethanone way or forwhichthe goalsare incompletely specified. An example due to Wilensky [55] in a humorous way exhibits the need to infer unstated goals.

User: System:

How can I getmore Type “delete *.*“.

disk space?

I f the system does not infer that the user has an unstated goal to retain his/her existing files, the ludicrous response intheexamplecould veryconceivablyoccur.Therefore, once again we see that knowledge of the goals of the user is critical to understanding. For generation, the problem is to know when goals can reasonably be unstated and when goals must be elaborated without belaboring the communication. Another example is the introduction of vagueness on the part of the system to appropriately address the user‘s needs. Woods [56] pointed out that I need a flight arriving a t nine o’clock mustbeunderstoodmorevaguelythanactually stated. For instance, it is unlikely that a flight between the t w o cities would arrive exactly at nine o’clock; rather, the systemmustreasonabout an appropriatetimeinterval to generate an apcentered around nine o‘clock in order propriate response. More general work regarding the substitution of a revised request in order to address the user’s need appropriately is underway [51], [57]. Muchinformation can be omittedin descriptionsof episodes and stories to the extent that they follow a stereotypical pattern that can be assumed part of episodic memory. For instance,supposewe are discussing U.S. college football. The following description is highly succinct.

The Boston College Eagles won the coin toss and marched 86 yards for a touchdown.

Given our knowledge of stereotypical football games in the U.S., we can concludethat BostonCollegeelectedto receive the kickoff, that there was a kickoff, etc. Such knowledge also enabled the author to use the definite reference thecoin toss withoutintroducing a referentearlier. A model of such knowledge has been devised by Schank [58] and employed in several ways 1591-[61]. As with most other sources ofknowledge,thestereotypicalpattern can be violated, as in After the Eagles won the coin toss, a power failure caused the game to be canceled. Understanding i n the light of violations of episodic knowledge is still an open area of research. Vagueness is a difficult,openproblemforbothunderstanding systems and generation systems. It isan important device for shortening messages in language generation, as one can see above. If a generation system spelled out every detail in a narrative description, it i s possible that no human would read the output. Therefore, the goal for generation must be crisp, natural descriptions such as the one above regarding a touchdown by Boston College.

PROCEEDINGS OF THE IEEE, L O L 74, NO, 7, J U L Y 1986

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

H. DiscourseStructure

Grosz and Sidner [49] have recently argued that discourse structureconsistsof atleast threedistinct,thoughinterrelated structures:

-

focus, the set of things in the immediate context and, therefore, able to be referenced, intention, the specific goal(s) of the speaker/author, discourse,the way thediscourseitselfdivides into logical, coherent units.

Many [20], [21], [62], [63] have argued that there are various relationsbetween discourse segments,such as repetition, elaboration, and support. The computation of such relations and the recognition of discoursestructure is obviously a difficult problem where muchwork can still be done. McKeown [64]has investigatedrhetorical strategies as a meansof generating paragraphlengthtextsexhibitinggood discoursestructure. A taxonomy I211 is work preparatory to enabling generation systems to produce paragraph lengthandmultiparagraph length texts that flow naturally. VI.

ISSUES IN KNOWLEDGEREPRESENTATION AND THEIR IMPORTANCE IN NATURAL LANGUAGE PROCESSING

Anumberof issues inknowledgerepresentation have direct import for natural language processing; these include first-order logic versus semantic networks, expressive power versus special-purpose inference engines, granularity, completeinitial understanding versus wait-and-see strategies, and the role of default reasoning. We will discusseach of these in turn in subsections that follow. The semantics of natural language requires a distinction between what an expression means andwhat it denotes. These are usually distinguished as the intension and extension of an expression. The extension of an expression is the actual entity that that expression refers to. The intension is the meaning of the expression without any commitment to whether there is an entity in the real world corresponding to the description. One can discuss unicorns in a conversation without any commitment to suchbeastsever having existed. When one says John wants to hire the best candidate,theexpressionbestcandidatecould have either an extensional or intensional reading. In the extensional reading, if Mary is the best candidate, then John wants to hire the best candidate is equivalent to John wants to hire Mary. In the intensional reading, John may not know at all who is but whenever he findshim/her,he thebestcandidate intends to hire the individual. Since that statement is a kind ofknowledge,ourknowledgerepresentation languages need to represent both extensions and intensions. One common way ofrepresentingknowledge is logic; those already familiar with first-order logic may wish to skip to Subsection VI-A. Since one way to express knowledge is in natural language itself, we can consider how to represent themeaningofcertainnatural language expressions in a first-order logic as a way ofdemonstratingonecommon approach to encoding knowledge. At the ground level, one needs a way of identifying unique, individual entities; this is doneusing constantsof logic. Some individuals have unique entities associated with them, such as thelength,

a vessel. One could representthem in draft, and beam of logic via a function applied to the constants, one function per attribute. Naturally, not all entities are related functionally one to another; therefore, relations are needed as well, such as therelationbetween a vessel andtheindividual members of the crew assigned to that vesselatany given time. We will call the names of those relations predicates. Syntactically, a term will refer to a constant, a variable, or a function applied to terms. A proposition will correspond to a predicate applied to terms, a disjunction of propositions, a conjunction of propositions, a negation of a proposition, or a quantifier applied to a proposition. Typical quantifiers in first-order logic are the symbol for universal quantification or for existential quantification; a quantifier, the variable to which the quantifier applies, and the proposition to which the quantification applies form a proposition. Thesemanticsof a logic is normallydefined via set theory, and is specified by stating several entities: a set S of individuals, a set F of functions mapping from individuals of

S (or n-tuples of members of 5) to S, a set of relations R over n-tuples of members of S. A semanticsforthequantifiers,disjunction,conjunction, andnegation is assumed. Of course, whenbuilding or describing a natural language system, a semantics for each predicateandfunction is notnormallydefined as above. Normally, one presents intuitive definitions for human consumption and a set of axioms for an inference process. Consider n o w a simple strategy for encoding knowledge in first-order logic. In understanding, once a definite reference has been understood, the logical form for it could be a constant. Attributes of entities could be represented either as the function symbols or predicate symbols. Thatis, the length of a given vessel could be represented as the value oflength(A) or as theargumentof a relationlength(A, IOOO); it is a matterofchoiceand style as to which form one prefers. Considertheoverallcombatratingof a Naval vessel regarding its readiness or ability to accomplish the goals it was designedfor. Thatdoesvary overtime;furthermore, the history of its rating values is important as a measure of the state of the vessel over a period of years and as part of a statistical study of vessels of that class. Therefore, we could represent the readiness of a vessel as a three-place predicate: one argument for the vessel’s identity, one argument for the rating itself, and one argument for the time interval. Alternatively, we could represent it as a two-place function: one argument for the vessel’s identity, and one for the time interval. It is sometimes useful to note typical patterns regarding parts of speech in English and the kinds of forms in logic that represent their meaning. Usually, common nouns such as man or vessel correspondto one place predicates, man(x) or vessel(x). Some common nouns are relations such as the nouns corresponding to familial relations. Mother could be represented as a two-place relation between the individual motherandtheindividualchildofthatmother.Similarly, as a two-placerelationbecommander could be viewed tweentheindividualcommander andthe unit thatthat commander commands. Many adjectives can be viewed as

WEISCHEDEL. KNOWLEDGE REPRESENTATION A N D N A T U R A L LANGUAGE PROCESSING

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

913

oneplacerelations;forinstance red maybe viewed as a one-place relation over the entity that is colored red. Again as a matter of style, for certain purposes one may prefer t o treat that adjective as a binary relation, color-of, relating the entity and the color red. Verbshavea very richsemanticstructureand exhibit a range of predicates. Rain as a verb could betreated as a nullary relation (i,e,, a relation with no arguments). Intransitive verbs such as sleep, couldbeviewed as one-place relations, the one argument being the entity that is sleeping. Transitive verbshave at least two arguments;kiss has the agent as one argumentand therecipient as another argument, Give hasat least three arguments: the giver, the object, and the recipient. In thisdiscussion we have ignored timealtogether.Onecould treat time as an additional argument on each of the predicates. Thesnapshotgiven above may leave almost as many questionsunanswered as there aresuggestions. Adverbial elements are difficult to represent. They could be treated as predicates o n propositions,thoughthatwouldrequire a logic richer than first order. O n the other hand, one could try a less elegant solution where the meaning of the adverb is part of the predicate itself such as a predicate run-quickly forthenotionof running quickly. There are far more quantifiers in English thansimplyuniversalandexistential quantification. Examples includemany,few, several, and most. The semantics of changeover timeand reasoning based on it is a well-known unsolved problem. Modalities, such as something being possible or necessary, statements about belief and reporting, and statements of certainty are additional classes of semantics that are not treated in the framework aboveand may require far richerlogics.Brief surveys of a number of higherorder logics are available [65]. A. Logic versus Semantic Nets

Logic, as a means of stating knowledge, has:

-

awell-defined semantics, including a definitionof truth, a definitionof inference, a bodyof analysis regardingthecomputationaland mathematicalpropertiesofthe language andalgorithms for processing it.

However, there are several concerns in using knowledge in naturallanguage processing, and,more generally, in artificialintelligence,which are notspecifically addressed by “traditional logic.” These include:

-

organization of knowledge, so thatone can know what items are closely associated with an entity and, therefore, are foregrounded for possible reference whenever that entity is mentioned in context; plausible inferences, which need not be valid; reasoningfrom ignorance, employingdefaultknowledge.

Of course, traditional logicscanbeextended toallow plausible inference and default reasoning [66]-[69],but this is still a research problem. One response to the above observations has beenthe development of semantic networks. Semantic networks are directed graphs whose nodes represent some semantic

91 4

entity andwhoselinks representrelations between those entities. Numerous semantic net formalisms have been proposed, though few have the advantages mentioned above forlogic.Tosome extentthey address theshortcomings mentioned above. For example, the structure of nodes and links near agivennode providesa means oforganizing knowledge. Proper treatment of plausible inference and of default reasoning are still active research topics. I n terms of the class of knowledge that can be expressed, it is generally agreed thatsemanticnetworks are formally equivalent to some subset of logic. For instance, suppose w e take the nodes ofa semantic networkto represent one-place predicates in logic; then, the links between nodes in the graph are binary predicates. One can always achieve the effect of n-ary predicates in the semantic networks via a simple translation mechanism. If we have a predicate P that takes argumentpositions a , , a 2 , . . . ,a,, then one can rewrite that n-ary predicate in terms of one unary predicate P’ and n binary predicates d l , a 2 , . . . ,a,. An expression

can be written as the following expression:

A wide variety of formalisms o f semantic networks and of the underlying semantics of those formalisms exist. Rather than doing an exhaustive survey, which itself would require a paper at least as long as the current one, we present the backbone that underlies the family of knowledge representation languages: KL-ONE [70], KRYPTON [71], and KL-TWO [72],[73]. In this family of languages,nodesrepresent concepts, that is, one-place predicates in logic. Links between nodes come in two forms: SUPERC, astatementthateverythingsatisfyingthe definition of a concept (normally drawn at the tail of an arrow) must satisfy the definition of a second concept (normally drawn at the head of an arrow), roles, binaryrelationsbetween concepts,and indicated by a circle inscribing a square in the middle of the link. Concepts are denoted in the diagrams by ellipses; SUPERC by the broad arrow; and roles by the links that are broken by acircleinscribing a square. Inthe diagram of Fig. 1, there are four unary predicates A , 13, C, and D. There are

Fig. 1. A simple network in the KL-ONE family.

also t w o binary predicates R 1 and R 2 . By virtueofthe SUPERC relationship between C and A , the following fact (expressed equivalently in first-order logic)is known:

The meaning of the link labeled

R 1 could be expressed in

PROCEEDINGS OF THE IEEE, V O L 74, NO 7. J U L Y 1986

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

the first-order logic expression as follows: (Vx)(Vy)[A(x)

84

R l ( x , Y)

-,

B(Y)l.

One of the properties of A subsuming C is that all ROLES leaving A are inherited by those concepts subsumed by A. In the example, therefore, C actually has two ROLES leaving it, R1 and R 2 . Therefore, the first-order logic equivalent of those facts can be stated as follows:

(vX)(vY)[c(x) & R l ( x , Y ) (VX)(~Y)[C(X)

-,

B( Y)].

R 4 x , Y) -, D( Y ) ] .

Some of the distinctive features of this family of network formalisms are the following facts:

--

semantic

A formal semantics has been defined for them. A limited class of knowledge is expressible. Limiting the set of knowledge that can be expressed in the language has enabledefficientinference algorithms to be defined over the formalism. The knowledge representation was defined with applications i n natural language processing in mind.

Toillustratethepoint regardingorganizationof knowledge, consider the knowledge needed to understand Iread a good novel the other day. The author was new to me.The t w o factsexpressed below could account for the definite reference the author: @'X)[ novel( X )

-,

book( X ) ]

(VX)(W)[book(X)

-, author(X,

there is n o agreementthat these are preferable to a nonfirst-order treatment. Modal expressions are anotherphenomenoncalling for special treatment. These include the following: I t is possible that. . ,

I t is necessary t o , . . Modal logics [74] focusspecificallyonthe semantics of such structures. Some adjectivesdependsemantically onthe class of entity they modify. An example is big, since what is big for a mouse is quite different than what is big for an elephant. One way t o express this is with a function(big)mapping predicates to predicates,e.g., big(elephant)(x) and big(mouse)(x). Suchexpressionsare not part of first-order logic;consequently, some alternativerepresentation or a higher order logic is needed. There are expressions in natural language whose semantics seem to require representing the intension of an expression. An example is the verb seek, fortheentity soughtneednot exist, andthereforeneednot have an extension.Similarly, fake andformer seem to operate on the meaning (intension)ofthe noun they modify. A fake weapon is not a weapon; a former criminal is not a criminal. At present the most widespread logic addressing each of the phenomena of this subsection is due to Richard Montague. Space does not permit describing that logic, but thorough introductions are available [17], [18].

Y)].

As can be seen from the discussion of KL-TWO, this knowledge can be very easily expressed as in Fig. 2.

C. General- Purpose versus Special- Purpose Approaches Inknowledge representationandreasoning systems in general,there is continuing debateregardinggeneral-purpose knowledge representation and reasoning systems versus limitedknowledge representationsand reasoners. The advantages of a very general approach such as first-order logicandcompletetheorem proversbased on first-order logic are: the breadth of knowledge that can be stated, the soundness and completeness of the ~ y s t e m , ~ the simplicity of the inference process.

Fig. 2. A knowledge fragment

Whatone has gained inthenetworkpotentially is a means of defining those entities that are closely associated with another when referenced; this clearly can be of value atleast fordefinite references andpotentiallyforother inference processes in natural language processingand artificialintelligence. Such a notion is nota partof the formal semantics of the representationlanguage, but may be a useful property of the system. B. Adequate Expressive Power

An open question i s whetherthere is an adequate, extended,first-orderlogicforthe semantics of naturallanguage, or what logic is most appropriate. One phenomenon where the issue arises is predicates on propositions, such as believingaproposition to be true. Extensions within a first-order framework have been proposed [16], [19], though

WEISCHEDEL KNOWLEDGE REPRESENTATION A N D NATURALLANGUAGE

A special-purpose knowledge representation and inference mechanismoffersthe prospect ofdeveloping a smaller class of expressible knowledgeand special-purposealgorithmsforthat smaller class whichmight have properties that are more desirable. The procedures for such sound and complete inference in first-order logic can be proven equivalent to the halting problem. That is, theproblemofsoundandcomplete inference in first-order logic is semi-decidable. Any procedurethat is sound and complete forfirst-orderlogic is guaranteed to halt on an input that is true; however, there are inputs that are not true for which a procedure could not halt. Naturally, there are three alternatives one could try to improve efficiency: one could try to improvetherun-timeefficiencyof

'Soundness of an inference algorithm means that everything that is provable given the axioms is true; completeness of an inference algorithm means that everything that i s true is provable.

PROCESSING

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

915

-

complete first-order theorem provers so that the average time when a theorem is proved is diminished; one can devise algorithms that are not complete, since therequirementforcompletenessrequiresthat any first-order theorem prover i s semi-decidable; one can seekan appropriate subset of first-order logic whichwouldpotentially have soundandcomplete theorem provers that are decidable.

Severalresearchershave taken the first approach [75], [76]. Thesecondapproach can be seen to some extent in PROLOG [77]. In PROLOG, Horn clauses let one state much of what one could say in first-order logic; however, the unit resolution strategy for inference is not complete. The traditional implementation of PROLOG exhibits rather efficient run-time performance even though it is not guaranteed to halt. It is fairly easy to construct examples that would not halt even for inputs that are theorems; it is assumed to be the responsibility of the programmer to avoid writing forms that would exhibit such behavior. The third approach is exhibited by hybrid reasoning systems. A hybrid reasoning system is one where two or more distinctinferencetechniquesemployingdifferent sets of facts communicatetoinfermorethaneitherinference technique could prove on its own. KL-ONE, KL-TWO, and CAKE [78] are examples.KL-ONEand KL-TWO have been used in natural language applications; CAKE is motivated by applications in intelligent computer aids to programming. KL-ONEandKL-TWObothemploythebackboneof information about unary and binary predicates discussed in the previous section. By constraining the formalism, several inferenceproblemsonthat class ofknowledge have not onlysoundandcompleteinferenceproceduresbut also efficient procedures that are guaranteed to halt in all cases. Three of the typical inference problems are: 1) 2)

3)

Is class X a subclass of class Y ? Is class X disjointfrom class Y ? Given a description X of a potentially new concept, Y , and what is itsmostspecificsubsumingconcept what are the most general concepts it subsumes?

For questiononetheimplementationinKL-TWO is, in fact, so efficient that it can be part of the inner loop in the semantic interpreter of IRUS [8]. Whenever a noun phrase is recognizedbythe parser, thesemanticinterpreterpostulatesthe class ofentitiesthenoun phrase refers toif interpreted literally. When the main predicate of theclause, forinstance, is proposed, its case constraints are checked againstthenoun phrase which has beenproposed. The simplest case of the case constraint would be a straightforward check whether the class of the noun phrase i s contained within the class specified in the case constraint. Besides the taxonomic backbone in KL-TWO, there is a propositional reasoning component. By restricting the knowledge representation to propositional logic rather than first-order logic onecan have a propositional theorem prover which is sound, complete, guaranteed to halt for all inputs, and rather efficiently implemented [79] (though of necessity it is stillexponentialinthe size ofthetheorem to be proved). KL-TWO is a hybrid system in that it has a welldefined communication mechanism between the taxonomic reasoner and the propositional reasoner. This allows one to get all the theorems from the taxonomic knowledge

91 6

base, plus all the theorems from the propositional knowledge base, plus theorems that arise due to the combination of the two knowledge bases, all without sacrifice of guaranteed halting and relative run-time efficiency. CAKE includesthe same propositional reasoner as in KL-TWOplus a secondcomponenttailoredtoreasoning about programs. This second component represents knowledge about plans, such as their operations, data structures, f l o w of data, and flow of control. third apKRYPTON is a combination of thefirstand proaches. It is a hybridreasoning system thatincludes a taxonomic backbone similar to that in KL-TWO, and therefore does not have the full expressive power of first-order logic. However, KRYPTON includes a sound and complete resolution theorem prover for first-order logic as well. The classes in thetaxonomy canbe disjointnesstestbetween coded so efficiently that it is part of the inner loop of the resolution theorem prover employed in KRYPTON; disjointness is a generalizationofthe test to see whether two clauses can be resolved. The issue of general-purpose versus special-purpose knowledgerepresentations andreasoning systems is particularly important in natural language processing. It seems highly unlikely that the kind of general-purpose inference mechanism needed to prove mathematical theorems in set theory is an integral process in real-time understanding or generationofspoken or written language. The different demands that natural language imposes compared to those necessary forotherapplications such as planningmultiagent activities, proving theorems, solving puzzles, or writing programshavebeeninvestigated [80]. The intuition amongmanycomputationallinguists is that far shallower reasoning is necessary forlanguage processing. This helps explainthedevelopmentof such limitedformalisms and reasoners as in semanticnetworksandlimitedmemory retrieval [81],[82]. D. Early Decisions versus Wait-and-See Strategies

Theconceptof a wait-and-see strategy was first introduced by Marcus [83] in the context of parsing. He argued against blindly looking at alternatives when there is insufficient information to make a preference among the alternatives. Conversely, he argued for adopting strategies which would letonemaintainthevariousalternativesinone search pathuntilsufficientinformation was available to determine among the alternatives. Thus the shrewd design of the representation enables one to branch in the search space only when necessary rather than every time a disjunction of alternatives is possible. Knowledgerepresentationsthatsupportwait-and-see strategiesandthereasoning based onthem is clearly an important area of research. Thereseem to be many problems in understanding natural languagethat suggest waitand-see strategies: lexical ambiguity, quantifier scope,and determining user intention.Inapplyingpragmaticknowledge the question is when there is sufficient information to rule out all alternatives except one. Before illustrating this point in pragmatic knowledge, we brieflyrecount someofthe ways ofdealing with this problemin parsing.Onewellknown way is to keep a well-formed substring table (WFST). Using a WFST, a procedure can search, exploring onealternative,butrecording

P R O C E E D I N G S OF T H E IEEE, VOL 74, NO. 7 , J U L Y 1986

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

any well-formed phrases parsed in the input string beyond the point where the decision to follow that alternative was made. As a result, the knowledge gained in exploring that alternative isshared with otheralternatives ifthey are processed. A different tactic is to design the syntactic parsing process t o keep the various interpretations together in one search alternative. In IRUS [8], three aspects are treated in this way: In general, ambiguous lexical items are held jointly in onealternative, while syntacticandsemanticconstraints successively eliminate possibilities. Before the top-down, left-to-right searchstarts looking for a new constituent, simple lookahead tests are employed t o prevent clearly unnecessary proposals. For a given syntactic alternative, all semantic interpretations of that syntacticalternative are carried i n parallel. (Semantic interpretation in IRUS is performed incrementally as the syntactic processor proposes elements for incrementing a partially complete constituent.) Marcus [84]is trying to develop a means of holding many syntactic interpretations in onealternativewhere no commitment is made in the data structure to the various interpretations. Rather, the data structure holds a set of partial constraints which definea set of possible parses; as additionalsyntacticinformation is learned,this is added to the data structure, further constraining the alternatives and thereforefurtherpruningthe set ofpossible parses that satisfy the complete set of constraints. It is clear that the issue of whether to employ wait-and-see strategies and how to employthem,ifthey exist,arises regarding the use of pragmatic knowledge as well. As a first example consider the problem of lexical ambiguity. Even a quick perusal of a dictionaryof English willshowthat a substantialpercentageofthewords have morethan one part of speech and, for a given part of speech,have more than one meaning orsense. Consequently, elimination of lexical ambiguity i s a serious problem for natural language processing. Some [85]have advocated elimination of lexical ambiguity as early as possible. However, as the two following examples show, it is not safe to throw away all interpretations for a lexically ambiguous word even at the end of a sentence. The sentence following the use of run into determines its meaning. While downtown yesterday, I ran into Fred. We had a good chat. While downtown yesterday, / ran into Fred. Though it could have been serious, neither of us was hurt.

Eliminating as much lexicalambiguity based on syntactic andsemanticgrounds seems perfectly reasonable while parsingasentence. If there are still multiple senses for a given word after processing a sentence,examplessuch as those above suggest one of two alternatives: makingaselection based o n pragmatic knowledge about what is most plausible in context, or holding allalternativesthatremainafterprocessing the sentence, waiting to see whether additional sentences provide information to resolve the ambiguity. This is an open area of research. Another example problem is quantifier scope. If semantic

interpretationshould translate themeaningof sentences into a version of first-order logic, one would normally try to determine the scope of quantifiers. This is particularly desirable i n natural language interfaces to databases. However, quantifier scope decisions are influenced by syntactic, semantic,andpragmaticknowledge. N o comprehensive solution is known. Furthermore, some [86]have argued that quantifer scope decisions are not normally made by people when understanding text and have raised the question as to whethercomputational systems should do so. Naturally then, this is another problem where a wait-and-see strategy might be employed; one might try to make quantifier scope decisions onlywhen the test’s applicationincontext requires it. Some preliminary proposals alongthisline have beenmade [87].Theissue ofquantifier scope in natural language understanding is still a research problem. Though we have illustrated the issue of whether and how to employ wait-and-see strategies for the problems of lexical ambiguityandquantifier scope only,it mayarise in manyotherphenomenathat seem to requirepragmatic knowledge. Determining user intention certainly seems to be a candidate. E. Default Reasoning

The term default reasoning is used to describe a wide range of phenomena. One kind of default knowledge seems to be associated with classes.For instance, elephants typically have four legs, typically have a tail,and are not normally attacked by any creature other than humans. Many [W], [89]have tried to associate defaultinformationwith classes i n semantic networks, though some [90]have argued thatthisconflates various kinds of knowledge in a problematic way. Moore [91]has identifiedautoepistemic reasoning as a secondkindof defaultreasoning. For instance,onecan reason as follows: If George Washington had been born on Christmas, I would know it. Since I don’t know that, he wasn’t born on Christmas.

Third, there is a kind of defaultreasoningfrequently employed in AI systems, called the closed-world assumption. Asystem employingtheclosed-world assumption uniformly reasons thatif a proposition is notknown by the system then that proposition must be false. This is built into PROLOG. A fourth kind of default reasoning is to assume that the (semantic) presuppositions of a speaker are true if one has noinformationcontradictingthosepresuppositions. For instance, a friend of mine went on a long hiking trip in the mountainsjustaroundthetimethat President Nixonresigned. The headline of the firstnewspaper hesaw upon returningmentioned PresidentFord. Thoughhe did not know the circumstances of how Gerald Ford became president,he nevertheless immediately assumed thatGerald Ford was president, merely from the semantic presupposition. Fifth, it is argued [92]that discourse conventions can give rise to default reasoning, For instance, if I ask at 11:OO p.m. Where is the nearest gas station?, my default reasoning might be that you will address my unstated goal to find the nearest open gas station.Therefore, if you mention a gas

WEISCHEDEL. KNOWLEDGE REPRESENTATION A N D NATURAL LANGUAGE PROCESSING

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

91 7

station,and if I believeyou are beingcooperative, I will assume you believe it open unless stated otherwise. In the examples above it is clear that default reasoning languageundercanplay a very importantpartinnatural standing and generation. Some of the instances include: selecting an interpretation based uponwhat is most plausible, assumingdetailnot stated, determiningunstated,implicit goals, assumingdiscourseconventions hold, such as helpfullyaddressingthe goals oftheparticipants inthe communication and stating true presuppositions. Default reasoning is therefore not only a topic in knowledge representation and reasoning but also a topic in natural languageprocessing.It is interestingthatthestudyof natural language processing has suggested kinds of default reasoning that might not have been recognized otherwise. Theexamplesaboveregardingassumingsemanticpresuppositions are true and assuming that discourse conventions are being followed arise particularly from studies in natural language processing. VII.

CONCLUSIONS

The paper has illustrated several points. First, a variety of knowledge is required to understand and generate natural language. This includes: morphological, phonetic, and spelling knowledge, syntax, case constraints, the meaning of a word, idiom, or phrase type, including any semantic presuppositions, subclass relationshipsand classes that are closely related in the domain of application, knowledge about what is plausible, typical goals andtypicalplansforachievingthose goals, episodic knowledge, knowledge of discourse conventions. Second, pragmatic knowledge is indispensable for proper understandingandgenerationcorrespondingtoparticular linguisticphenomena such as definite reference, lexical ambiguity,ellipsis,intention,ill-formedinput, figures of speech, vagueness, and discourse structure. Third, the paper has itemized a number of issues in knowledge representation andreasoningwhileillustratinghowthose issues impactnatural languageprocessing.Fourth,thepaper illustrates how naturallanguage has contributed to knowledge representation. Whenone considersthe issues involved in resolving lexical ambiguity in context, in recognizing user intention, in theneedforwait-and-see strategies, and in default reasoning, t w o additional points stand out. A breakthrough in knowledge representationandreasoning would have a dramatic impact on natural language studies. O n the other hand, it is converselytruethatbreakthroughs in natural language studies focussing on the topics above could have dramaticimpactonknowledgerepresentation and reasoning, potentially regarding expressive power, shallow reasoning,theroleofspecial-purpose reasoners (including hybrid systems), and default reasoning.

918

a numberofimportant Inaccomplishing thesegoals, research issues have been enumerated. These include:

how much reasoning and what kind of reasoning and knowledge are requiredtocorrectlyunderstandand use definite reference,ambiguouswords,elliptical forms, brief (but vague) communication, implicit goals, and figures of speech; at what point in the processing the knowledge should be brought to bear, for instance, while understanding a given sentence or taking a wait-and-see strategy; how to organizeknowledgefor purposesofranking interpretations and inference mechanisms; what expressive power is needed; reawhether uniform approaches, special-purpose soners, or hybrid reasoning systems should be used. Natural language research is at a truly exciting point, for a largenumberofpeople have begunthedifficult task of determining how to use diverse sources ofknowledgeto solvevariousproblems in pragmaticsofnaturallanguage. At the same time, contributions to knowledge representation and reasoning may result either as integral parts or as side-effects of that research. There is room for many more individuals to make significant contributions. REFERENCES system," in PracticalExperience of Machine Translation, V. Lawson, Ed. Amsterdam, The Netherlands: North-Holland, 1982, pp, 39-44. I. Durham, D. Lamb, and J. Saxe, "Spelling correction in user interfaces,'' Commun. ACM, vol. 26, no. 10. pp. 764-773, Oct. 1983. K . Jensen, G . E. Heidorn, L. A.Miller,and Y. Ravin, "Parse fittingand prosefixing:Gettingaholdonill-formedness," Amer. 1. Comput.linguistics, vol. 9, no. 3-4, pp. 147-160, luly-Dec. 1983. S . C. Kwasny and N. K . Sondheimer, "Relaxation techniques for parsing grammatically ill-formed input i n natural language understanding systems," Amer. 1, Comput. linguistics, vol. 7, no. 2, pp. 99-108, April-June 1981. R. M. WeischedelandN. K. Sondheimert"Meta-rules as a basis forprocessingill-formedinput," Amer. /. Comput. linguistics, vo1. 9, no. 3-4, pp, 161-177, July-Dec. 1983. B. Crosz, A. K . Joshi, and S. Weinstein, "Providing a unified account of definite noun phrases i n discourse," in Proc. 27st Annu.Meet. Assoc. Comput. Linguistics (Cambridge, MA, June 1983), pp, 44-50. C. L. Sidner,"Focusing i n thecomprehensionofdefinite anaphora," in Computational Models of Discourse, M. Brady, Ed. Cambridge, MA: MIT Press, 1982. M. Bates, D. Stallard, and M . Moser, "The IRUS transportable natural language database interface," in Expert Database Systems, L. Kerschberg, Ed. Menlo Park, CA:CummingsPubl., 1985. W. C. Mann and C. M. I. M . Matthiessen, "Nigel: A systemic grammarfortextgeneration," i n SystemicPerspectives on Discourses: Selected Theoretical Papers from the 9th InternationalSystemicWorkshop, R. Freedle, Ed. Norwood,NJ: Ablex, in press. S . M. Schieber, AnIntroductiontoUnification-BasedApproaches to Grammar (Assoc. Comput. Linguistics, 1985, presented as a Tutorial Sessionat the 23rd Annu. Meet. of the Assoc. for Comput. Linguistics). T. Winograd, language As a Cognitive Process-Vol. I: Syntax. Reading, M A : Addison-Wesley, 1983. N. Cercone, C. McCalla,and P. McFetridge,"Themany dimensions of logical form," Tech. Rep. 85-8, Laboratory for Computer and Communications Research, Simon Fraser Univ., Burnaby, BC, Canada, 1985. W. Lehnert and Y. A. Wilks, "A critical perspective on KRL," B. Thouin, "The METE0

PROCEEDINGS OF T H E IEEE. V O L 74, NO 7 , J U L Y 1986

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

Cognitive sci., vol. 3, no. 1 , pp, 1-28, Jan.-Mar. 1979. R . C. Schank, Conceptual lnformation Processing, New York, NY: Amer. Elsevier, 1975, D. G . Bobrow and T. Winograd, "KRL: Another perspective," Cognitive Sci., vol. 3, no. 1, pp. 29-12, jan.-Mar. 1979, J. R. Hobbs,"Granularity," i n Proc.lICAl85. Los Altos,CA: Morgan Kaufmann Publ. (Int. Joint Conf. on Artificial Intelligence, Inc., Los Angeles, CA, Aug. 1985), pp. 432-435. D. R . Dowty, R. E. Wall, and S . Peters, Introduction to Montague Semantics. Dordrecht, The Netherlands: D. Reidel, 1981 R . Montague,"Thepropertreatmentofquantificationin ordinary English," in Formal Philosophy, R . Thomason, Ed. N e w Haven, CT: Yale Univ. Press1974, pp. 247-270. D. Perlis, "Languages with self-reference I : Foundations," Artificial Intell., vol. 25, no. 3, p p 301-322, Mar. 1985. J. R. Hobbs,"Coherenceandcoreference," Cognitive Sci., vol. 3, no. 1, pp. 67-90, Jan.-Mar. 1979. W . C. Mann and S . A. Thompson, "Relational propositions in discourse,'' Tech. Rep. RR-83-115,USC, lnformation Sciences Institute, Marina del Rey, CA, Nov. 1983. 5. Nirenburg, V. Raskin, and A. B. Tucker, "Interlingua design for TRANSLATOR," in Theoretical and Methodological lssues in Machine Translation o f Natural languages, Aug. 1985, pp.

224-244. N. K . Sondheimer, R . M. Weischedel,and R . J , Bobrow, "Semantic interpretation using KL-ONE," in Roc. COlING-84 and the 22nd Annu. Meet. Assoc. Comput. linguistics. (AssociationforComputationalLinguistics, Stanford, CA, July 1984), pp, 101-107. Y . A.Wilks,"Apreferentialpattern-seeking semantics for natural language inference,'' Artificial Intell., vol. 6, pp, 53-74, Spring 1975. N.M. Goldman,"Conceptualgeneration,"in Conceptual lnformation Processing, R . Schank, Ed. Amsterdam, The Netherlands: North-Holland, 1975, ch. 6, pp. 289-371. 8. J. Grosz, A. K . Joshi, and 5. Weinstein, "Providing a unified account of definite noun phrases i n dlscourse," i n Proc. 21st A n n u .M e e t . Assoc. Comput. Linguistics (Assoc. Comput. Linguistics, June 1983). exercise in semantic C. J. Fillmore,"Verbsofjudging:An description," in Universals in linguistic Theory, E. Bach and R. Harms, Eds. New York, NY:Holt,Rinehart,andWinston, 1968. T. Civon,"The time-axisphenomenon," language, vol. 49, no. 4, pp, 890-925, Dec. 1973. E. L. Keenan, "TwokindsofpresuppositioninnaturalIanguage," in Studies in linguistic Semantics, C. ]. Fillmore and D. T. Langendoen, Eds. New York,NY: Holt, Rinehart,and Winston, 1971. P. Kiparskyand C. Kiparsky, "Fact," in Semantics, D. D. Steinbergand L. A.Jakobivits, Eds. New York, NY:Cambridge Univ. Press, 1971. A. K . Joshi and R . M. Weischedel, "Computation of a subclass of inferences: Presupposition and entailment," Amer. /. Comp u t . Linguistics, vol. 4,no. 1, July-Dec. 1977. R . M. Weischedel, "A new semantic computation while parsing: Presupposition and entailment," in Syntax andSemantics, VOI. 11, Presupposition, C. K . O h and D.A.Dinneen, Eds. N e w York, NY: Academic Press, 1979, pp. 155-182. 5. J. Kaplan,"Indirect responses toloadedquestions,"in Theoretical Issues inNaturallanguage Processing-2 (Assoc. Comput. Mach., Assoc. Comput. Linguistics, and Assoc. Comput. Mach.-SICART, July 1978), pp. 202-209. R. M. Weischedel, W . Voge, and M. James, "Anartificial intelligenceapproach to language instruction," Artificial lntell., vol. I O , pp. 225-240, May 1978. T. Reinhart, Amphora and Semantic Interpretation. London, England: Croom Helm Ltd., 1983. T. Winograd, UnderstandingNaturallanguage. New York, NY: Academic Press, 1972. B. A.Goodman,"Communicationandmiscommunication,'' Ph.D.dissertation,Dept.ofCompt. Sci. Univ.ofIllinois, Urbana, IL, Oct. 1984. (Also, Tech. Rep. 5681,BBN Lab., to be published.) C. Hirst, "A foundation for semantic Interpretation," in Proc. 27st Annu. Meet. Assoc. Comput. linguistics (Assoc. Com-

WEISCHEDEL KNOWLEDGE REPRESENTATION A N D NATURALLANGUAGE

put. Linguistics, Cambridge, MA, June 1983), pp. 64-73. D. McDermott, "Assimilation of new information by a natural language-understanding system," Tech. Rep. 291, MIT AI Lab., Cambridge, MA, 1974. R . Granger, K. Eiselt, and J. Holbrook, "The parallel organization of lexical, syntactic and pragmatic inference processes," i n Proc. 7 s t Workshop on Theoretical lssues inConceptual lnforrnation Processing (Atlanta, CA, 1984), pp, 97-106, L. Birnbaum, "Lexical ambiguity as a touchstone for theories of language analysis," in Proc. IjCAI85. Los Altos, CA: MorganKaufman Publ. (Int.Jointconf.onArtificialIntelligence, Inc., Los Angeles, CA, Aug. 1985), pp, 815-820. G . Hendrix, et a/., "Developing a natural language interface to complex data," ACM Trans.DatabaseSyst., vol. 3, no. 2, pp. 105-147, June 1978. R . M. Weischedeland N. K . Sondheimer, "Animproved heuristicforellipsisprocessing,"in Proc.20th Annu. Meet. Assoc. Comput. linguistics (Assoc. Comput. Linguistics, June 1982), pp. 85-88 J . C. Carbonell, "Discourse pragmatics and ellipsis resolution intask-oriented natural languages interfaces," i n Proc. 21st Annu. M e e t . Assoc. Cornput. Linguistics (Assoc. Comput. Linguistics, June 1983), pp. 164-68. D. L. Waltz and B. A. Goodman, "Writing a natural language data base system," in Proc. 5th l n t . C o n f . on Artificial lntelligence (Int. Joint Conf. on Artificial Intelligence, Cambridge, M A , 1977), pp. 144-150. M . 5. Carberry, "A pragmatics-based approach to understanding intersentential ellipsis," in Proc. 23rdAnnu. Meet. Comput. Linguistics (Assoc. Comput. Linguistics, Chicago, IL., July 1985), pp. 188-197. J. F. Allenand C. R. Perrault, "Analyzingintentioninutterances," Artificial Intel/,, vol. 15, no. 3, pp. 143-178, Dec. 1980. response recognitiC. L. Sidner, "Plan parsingforintended tion in discourse," Comput. Intell., vol. 1, no.1,pp. 1-10, Feb. 1985. B. J. Groszand C. L. Sidner, "Discoursestructureandthe propertreatmentofinterruptions,''in Proc. ljCAl85. Los Altos, CA: Morgan Kaufmann Publ. (Int. Joint Conf. on Artificia1 Intelligence,Inc.. Los Angeles, CA, Aug. 1985), pp, 832-839. M. S. Carberry, "Tracking user goals in an information-seekProc. Nat.Conf. on ArtificialIntel/;ingenvironment,"in gence (Amer. Assoc. Artificial Intell., Aug. 1983), pp. 59-63. A. K . Joshi. B. L. Webber, and R . M. Weischedel, "Living up to expectations:Computingexpert responses," in Proc. Nat. C o n f . on Artificial lntelligence (Amer. Assoc. Artificial Intell., Austin, TX, Aug. 1984), pp. 169-175. [521 N. F. Carver, V. R. Lesser, and D. L. McCue, "Focusing in plan Proc. Nat. Conf. on ArtificialIntelligence recognition,"in (Amer. Assoc. ArtificialIntell.,Austin, TX, Aug. 1984), pp,

42-48. R. H. Granger, "The N O M A D system: Expectation-based detectionandcorrectionof errors duringunderstandingof syntactically and semantically ill-formed text," Amer. /. Comput. linguistics, vol. 9, no. 3-4, pp. 188-198, July-Dec. 1983. J , G . Carbonell and P. J. Hayes, "Recovery strategies for parsing extragrammatical language," Amer. /. Cornput. Linguistics, vol. 9, no. 3-4, pp, 123-146, July-Dec. 1983. R. Wilensky,"Talking to UNlX i n English: Anoverviewof UC," in Proc. 8th Nat. Conf. on Artificial Intelligence. (Amer. Assoc. Artificial Intell., Pittsburgh, PA, 1982), pp, 103-106. W. A. Woods, "Semantics for a question answering system," Tech. Rep. NSF-19, Harvard Univ.Comput. Lab., Sept. 1967. Also,Ph.D.dissertation,Divisionof Eng. andAppl. Phys., HarvardUniv.Availablefrom NTlS as PB-176-548, andreprinted with a new preface i n 1979 byGarlandPublishing, Inc., New York, NY, as a volume in the series: Outstanding Dissertations in the Computer Sciences. M. S. Carberry,"Understandingpragmaticallyill-formedinput," i n Proc. COlING-84 and the 2 n d Annu. Meet. Assoc. Comput. Linguistics (Assoc. Comput.Linguistics, Stanford, CA, July 1984), pp, 200-206. R. C. Schank, "Atheorybehindtheprograms:Atheoryof context,'' i n lnsideComputerUnderstanding, R . C. Schank and C. K . Riesbeck, Eds. Hillside, NJ: Lawrence Erlbaum Associates, Inc., 1981, pp, 27-40.

PROCESSING

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

919

R . Cullingford, “SAM,” i n Inside Computer Understanding, R .

C. Schank and C. K. Riesbeck, Eds. Hillside, NJ: Lawrence Erlbaum Associates, Inc., 1981,pp. 75-119. J , R . Meehan, “TALE-SPIN,” in Inside Computer Understanding, R . C. Schank and C K . Riesbeck, Eds. Hillside, NJ: Lawrence Erlbaum Associates, Inc., 1981,pp, 197-226. R. Wilensky,“PAM,” i n Inside Computer Understanding, R . C. Schank and C. K . Riesbeck, Eds. Hillside,NJ:Lawrence Erlbaum Associates, Inc., 1981,pp. 136-179. R . Cohen, “A computational theory of the function of clue words in argument understanding,” i n Proc. COLING-84 a n d the22ndAnnu.Meet. Assoc. Comput. Linguistics (Assoc. Comput. Linguistics, Stanford, CA, July 1984), pp, 251-258. R. Reichman,“Plain-speaking:Atheoryand grammar of spontaneous discourse,” Ph.D.dissertation, Dep.Comput. Sci., HarvardUniv. 1981.Also, B B N Rep. 4681,Bolt Beranek and Newman Inc., Cambridge, M A . K. R . McKeown, Text Generation: Using Discourse Strategies a n d Focus Constraints to GenerateNatural Language Text. Cambridge, England: Cambridge Univ. Press, 1985. R . Turner, Logics for ArtificialIntelligence. Chichester, England: Ellis Horwood Ltd., 1984. J . McCarthy,“Circumscription-Aformofnon-monotonic reasoning,” Artificial Intell., vol. 13, no. 1, 2, pp. 27-39,Apr.

1980. R . Reiter, “A logic for default reasoning,” Artificial Intell.,

vol.

13, pp. 81-132,June 1980. L. A. Zadeh, “A meaning representation language for natural languages,” Int. 1. Man-Machine Studies, vol. IO, no. 4,pp.

395-460,July 1978. “A theoryof commonsenseknowledge,” i n Aspects of Vagueness, H. J. Skala, 5. Termini, and E. Trillas, Eds. Dordrecht, The Netherlands: D. Reidel, 1984. R . J. Brachman and J. Schmolze, “An overview of the KL-ONE knowledge representation system,” Cognitive Sci., vol. 9, no. 2,pp. 171-216,Apr. 1985. R . J. Brachman, R . E. Fikes. and H. J. Levesque, “KRYPTON: A functional approach to knowledge representation,” /€E€ Computer Mag., vol. 16,no. IO, pp, 67-73,Oct. 1983,Also available as Fairchild Tech. Rep. 639 or as FLAIR Tech. Rep.

16. [721 M. G. Moser, “An overview of NIKL, the new implementation of KL-ONE,” i n Research in KnowledgeRepresentationfor Natural Language Understanding-Annual Report, 7 September 1982-31 August 1983, C. L. Sidner et a/., Eds.,BBN Lab, pp. 7-26 Rep. 5421, 1983, M. Vilain,“Therestricted language architecture of a hybrid representation system,” in Proc. IJCAI85. Los Altos, CA: Morgan Kaufmann Publ. (Int. Joint Conf. on Artificial intelligence, Inc., Los Angeles, CA. Aug. 1985),pp, 547-551, J. Y. Halpern and Y. 0. Moses, “A guide to the model logics of knowledge and belief: Preliminary draft,” i n Proc. //CABS. Los Angeles, CA: Morgan Kaufmann Pub. (Int. Joint Conf. on ArtificialIntelligence,Inc., Los Angeles, CA, Aug. 1985), pp,

480-490. W . Bibel, “Mating in matrices,” Commun. ACM, vol. 26,no. 11, pp. 844-852,NO^. 1983. M. E. Stickel, ”A nonclausal connection-graph resolution the-

920

orem-proving program,” in Proc. Nat.Conf. on Artificial Intelligence(Amer. Assoc. ArtificialIntell.,Pittsburgh, PA, 1982), pp. 229-233. R. Kowalski,LogicforProblemSolving.New York, NY: North-Holland, 1979. C. Rich, “The layered architecture of a system for reasoning aboutprograms,’’ i n Proc.IIACI85. Los Altos,CA:Morgan KaufmannPubl.(Int.JointConf.onArtificialIntelligence, Inc., Los Angeles, CA, Aug. 1985), pp. 540-546. D. A. McAllester, “Reasoning utility package user’s manual,” AI M e m o 667,Mass. Inst. Technol. Artificial Intell. Lab., Apr.

1982. E. Charniak, “A common representation for problem-solving andlanguagecomprehensioninformation,”ArtificialIntell., vol. 16,no. 3, pp. 225-255, July 1981. A. M. Frisch and J. F. Allen,”Knowledgeretrieval as limited inference,” i n Lecture Notes in Computer Science: 6th Conference on Automated Deduction, D. W. Loveland, Ed. New York, NY: Springer-Verlag, 1982. J. L. Kolodner,RetrievalandOrganizational Strategies in ConceptualMemory:AComputerModel. Hillsdale, NJ: Lawrence Erlbaum Assoc., 1984. M. Marcus, ”A computational account of some constraints on language,” i n Proc. Theor. Issues in Natural Language Processing-2 (Assoc. Comput. Linguistics and Comput. Mach. -SICART, Urbana-Champaign, IL, July 1978), pp. 236-246.. M. P. Marcus, D. Hindle, and M. M. Fleck, ”D-Theory: Talking about talking about trees,” in Proc. 27st Annu. Meet. Assoc. Comput. Linguistics (Assoc. Comput. Linguistics, Cambridge, MA, June 1983), pp, 129-136. 5. Small, “Word expert parsig,” i n Proc. 17th Annu.Meet. Assoc. Comput.linguistics (Assoc. Comput. Linguistics, La Jolla, CA, Aug. 1979),pp. 9-14. K. Van Lehn, “Determining the scope of English quantifiers,” Lab. Cambridge, MA, Tech.Rep. 483,MITArtificialIntell.

1978. J. R . Hobbs,“Animpropertreatmentofquantificationin ordinary English,’’ i n Proc. 27st Annu. Meet. Assoc. Comput. Linguistics (Assoc. Comput. Linguistics, Cambridge, MA, June 1983),pp. 57-63. S. E. Fahlman, NETL: A System forRepresenting and Using Real- World Knowledge. Cambridge, MA: MIT Press, 1979. M. Minsky,“Aframeworkforrepresentingknowledge,” in The Psychology o f ComputerVision, P. H.Winston, Ed. N e w York, NY: McGraw-Hill, 1975. 1901 R . J. Brachman, V. P. Gilbert, and H. J. Levesque, “An essential hybrid reasoning system: Knowledge and symbol level IICI85. Los Angeles, CA: accountsofKrypton,”inProc. Morgan Kaufmann Publ. (Int. Joint Conf. on Artificial Intelligence, Inc., Los Angeles, CA, Aug. 1985), pp. 532-539. R . C. Moore, “Semanticalconsiderationsonnonmonotonic logic,’’ i n Proc. 8th Int. joint Conf. on Artificial Intelligence (Int.JointConf.onArtificialIntelligence, Karlsruhe, West Germany, 1983), pp, 272-279. [921 A. K. Joshi, B. L. Webber,and R. M. Weischedel,“Default reasoning in interaction,” in Proc. Non-Monotonic Reasoning Workshop (Amer. Assoc. Artificial Intell., New Paltz, NY, Oct. 1984), pp. 144-150.

PROCEEDINGS

Authorized licensed use limited to: Technical University Kosice. Downloaded on November 18, 2009 at 05:09 from IEEE Xplore. Restrictions apply.

OF THE IEEE, V O L 74, NO 7 , J U L Y 1986