A Semantic Expert Using an Online Standard Dictionary

A SEMANTIC EXPERT USING AN ONLINE STANDARD DICTIONARY'

.lean-Louis Binot B.I.M. Kwikstraat, 4 83078 Everberg, Belgium

ABSTRACT

A system has been developed to find the most likely attachment for prepositional phrases in English sentences in a fairly unrestricted way. The system receives as input a syntactic sentence parse pro­ vided by a general-purpose computational grammar called PEG (PLNLP English Grammar). The semantic decision that is neces­ sary to make the right attachments is made (a) by parsing (also with PEG) the natural language definitions of an online standard dic­ tionary, in this case Webster's Seventh New Collegiate Dictionary; (b) by relating words to other words in the dictionary; and (c) by reasoning heuristically about the comparative likelihood of different possible attachments. 'The basic assumption of this research is that natural language itself is a knowledge representation language that can be conveniently accessed and richly exploited. Techniques such as those presented here offer hope for eliminating the time­ consuming and often incomplete band coding of semantic informa­ tion that has been conventional in natural language understanding systems.

I. INTRODUCTION

Programming a computer to make a reasonable syntactic analysis of a sentence is possible. Programming a computer to understand that sentence is more difficult, largely because the computer lacks the kind of prior experience that would enable it to "know· what it is supposed to "understand. · There have been various frontal as­ saults on overcoming this difficulty. 'These have generally involved the manual encoding of information in specific systems: "semantic lexicons· (e.g., Johnson 1984); "deep semantics· for a subdomain (e.g., Sager 1981); or attempts to specify world knowledge in some more exhaustive way, usually by reducing experience to formu­ lations in predicate logic (e.g., Lenat et al., 1986).

This line of work has produced interesting results but has also raised difficult problems. On the one hand, to encode manually the knowledge necessary for any large scale application is an enormous and possibly self-defeating task. On the other hand, encoding means choosing a specific representation, which is by no means easy given that nobody has yet a complete picture of the kind of information that must be represented. Some researchers have even challenged recently the notion that an encoding of any type could lead to any real form of natural language understanding (Winograd and Flores 1986).

We suggest another approach based on the fact that natural language words are also symbols and, as such, can be handled very well by computers. Most knowledge can be directly expressed in natural language, a fact which has already been recognized (Kayser 1982, Zadrozny forthcoming). Moreover, large bodies of know­ ledge, such as human dictionaries and encyclopedias, are already available online. If computers can access that information, and use it to solve natural language processing ambiguities, they (and we) would be much further ahead.

This research was entirely performed at the tnM Thomas J. Watson Research \..enter.

Karen .Jensen Computer Science Department IBM Thomas .1 . Watson Research Center P.O. Box 704 Yorktown Heights, New York 10598, U.S.A.

The research presented here is aimed toward that goal. i\s a first step, we are concentrating on the disambiguation of prepositional phrase attachments, a difficult problem which is of considerable current interest (Lytinen 1986, · Dahlgren and McDowell 1986, Schubert 1986). We arc developing and implementing techniques for processing the definitions of an online standard dictionary in order to extract from them the semantic information necessary to resolve such ambiguities. Possible extensions include the processing of other kinds of attachment ambiguities and word meaning disambiguation.

This work addresses the areas of natural language understanding, reasoning, knowledge representation, and, briefly, learning. Under­ standing is approached by treating online reference works as know­ ledge bases. i\ heuristic reasoning component gives robust results. One of the most interesting directions of this research is the sug­ gestion that natural language itself is a knowledge representation language that can be conveniently accessed and richly exploited. At the end of the paper, we make a small incursion into the domain of learning, suggesting that formal knowledge bases could be pro­ gressively built by automatically extracting information from natural language sources.

The computational principles discussed here offer hope for eliminating the time-consuming, and often incomplete, hand coding of semantic information that has been conventional in natural lan­ guage understanding systems.

II. PREPOSITIONAL PHRASES ATTACHMENT AMBIGUITIES

Consider the following sentences:

• (I) I ate a fish with a fork .
• I ate a fish with many bones.
• I ate a fish with my fingers.
• I went to Boston by bus.
• ( 5) I will have finished this work by noon.

At the syntactic level, all these examples offer attachment am­ biguities. Sentences (I) to (3). were discussed in (Binot 1985); sen­ tence (4) is discussed in (Sowa and Way 1986). However, in both cases, the attachment ambiguity was solved by hand-coded know­ ledge. We are designing a semantic expert which is able to decide by consulting automatically a standard dictionary what is the correct attachment for the prepositional phrase in each case, and also what is the intended meaning of the preposition. The input to this system is a syntactic parse tree for the ambiguous sentence, produced by a grammar called PEG.

The computational grammar PEG (PLNLP English Grammar) analyzes English sentences by using syntactic information in aug­ mented phrase structure rules with a bottom-up, parallel processor (Jensen forthcoming). The system that provides these facilities is PLNLP, or the Programming .Language for Natural Language Processing (Heidorn 1975). PEG produces useful sentence parses for a large amount, and a wide variety, of English text. lbese parses contain syntactic and functional (subject, object, etc.) information, but, as yet, no semantic information, or other information beyond the functional level.

PEG's method for dealing with attachment ambiguities is to at­ tach modifiers in a single arbitrary pattern (usually to the closest possible head), but to mark other possible attachment sites so that they can be referred to for later semantic processing. A question mark indicates these possible attachment sites (sec Figure I). Tlus mark triggers the intervention of the semantic expert, which at­ tempts to solve the ambiguity.

DECL NP PRON* "i" VERB* "aten NP DET ADJ>~ "a" NOUN* "fish" pp PREP "with" QUANT ADJ* "many" NOUN* "bones"

Ill. ESTABLISHING SEMANTIC CONNECTIONS

Disambiguation is not a matter of exact deduction, but rather of finding the "most likely· interpretation in a given context. Our sys­ tem does that by consulting dictionary entries for specific words in the context in order to assign to each possible interpretation a 1ikelihood factor."' These factors, like the certainty factors in MYCIN (Shortliffe 1976), may range from -I (absolute disbelief) to + I (absolute belief), with 0 denoting complete uncertainty. This process of assigning likelihood factors is directed by declarative rules which, making use of expert system technology, try to capture in some sense the semantic expertise brought to bear by a person while consulting a dictionary. Figure 2 shows the answer that the system gives to the problem posed by the ambiguity in Figure I :

((WITH <EAT> <FORK>) (INSTRUMENT 0.72 )(MANNER 0.252) (COAGENT -0.3)(PARTOF -1. )(ASSOCIATION -1. )) ((WITH <FISH> <FORK>) (ASSOCIATION 0. 1 )(PARTOF -0.3 ) (COAGENT -! .)( INSTRUMENT -1. )(MANNER -1. ))

This answer is an ordered list of the possible constructs, each construct being provided with an ordered list of the possible inter­ pretations of the preposition for that construct. The likelihood fac­ tor of a construct is defined as the likelihood factor of its best interpretation. Translated into English, Figure 2 says that there are two possible attachments for the with-PP: to the main verb ·eat· (WITH <EAT> <FORK>), or to the immediately preceding noun "fish" (WITH <FISH> < FORK>). Por the frrst construct, the INSTRUMENT meaning of the preposition receives a rating of 0.72, the MANNER meaning a rating of 0.252, etc. Thus, ac­ cording to the system, the most likely interpretation of the ambi­ guity in example (I) is to attach ·fork· to "cat· with an instrumental meaning.

The system works by evaluating successively each possible con­ struct and each possible meaning of the involved preposition. Due to space constraints, we shall only discuss here the INSTRUMENT

For now, we are using only the context or the immediate sentence; hut we have plans to move to interscntcntial context.

and PARTOF mearungs of "with," and the INSTRUMENT and TIME meanings of "by: although other meanings arc handled hy the system, as Figure 2 shows.

The basic strategy for evaluating a construct is to use the dic­ tionary in order to find some semantic connection between the two terms of the proposed construct (the head and the complement). Dictionary entries contain several kinds of information that arc of interest for this aim: the definition(s), example sentences and phrases, synonyms, and usage notes and other comments. In the first stage of this research, we are using only the defmitions provided hy Webster's Seventh New Collegiate Dictionary (W7).

Finding semantic connections in the dictionary is . possible he­ cause there are specific words and phrases in definitions, forming what we shall here call patterns, which are almost systematically used to express specific semantic relations (Markowitz ct al. 1986). For the two meanings of ·with" illustrated in the previous examples, some of these patterns are:

PAR TOP: part of, arises from, end of, member of, etc. INSTRUMENT: for, used for, used to, a means for , etc.

These patterns generally take, as their objects, some central term (or terms) in the defmition of the complement word . An attempt can then be made to link that term with the head of the construct that is being studied. We shall illustrate this with sentence (1) . The sys­ tem starts by looking up in W7 the definitions of the ambiguous prepositional complement: "fork," and by parsing each of them. The first defmition reads:

fork: I. An implement with two or more prongs used esp [or taking '!£ (as in eating), pitching or digging.

The corresponding parse tree as produced by PEG is shown in Figure 3.

The system will apply to such parse trees a pattern-matching mechanism looking, in this case, for one of the INSTRUMENT patterns mentioned above. Each pattern is formally represented as a recursive formula like the one shown in Pigure 4:

( CTAKE !lEAD ( ( SEGTYPE PP) (HAS PRP ((BASE FOR))) (CHAS HEAD ((PRESPART))) ))

Such formulas use the fact that every parse tree node and every word is represented in PLNLP as a record with attributes and val­ ues. This specific pattern instructs the system to look in the parse tree for a node having a type of PP (Prepositional Phrase), having a PRP (PRePosition) attribute pointing toward a record represent­ ing the preposition "for: and having a HEAD attribute pointing toward a term marked as a present participle (PRESPART). If such a record is found, its head should be returned as value by the pattern-matching mechanism (or, if it is a coordinate structure, the heads of all conjuncts should be returned) .

Applying this pattern to the parse tree of Pigure 3, the system will fmd one PP node satisfying the description: "especially for taking ... : The heads of the VP conjuncts inside that PP then yield three possible instrument indications: "take," ·pitch: and ·dig." The system will try to relate these terms with · eat · by using synonym or taxonym relations also extracted from the dictionary. (For the present, we deliberately avoid the definition phrase ·as in eating" -­ which offers a direct match -- in order to show that our approach does not rely on such lucky coincidences.)

Basically, the taxonym relations arc established by extracting the heads of the dictionary definitions, using the same techniques as above. In this case, ·take· is defined as a direct hypcmym of ·cat· in W7, because one of the defrnitions of ·cat· is ·to take in through the mouth .. : Thus, a plausible meaningful connection has been established between ·fork· and ·eat· using an INSTRUMENT link; this constitutes a strong positive indication in favor of the likelihood of the interpretation ·INSTRUMENT(eat,fork)". 'The connection found can be viewed as forming a path in a semantic network, as illustrated in Figure 5:

It must be emphasized that this .network is only an implicit structure illustrating the connections found by the system, and has not been provided as hand-coded knowledge. The main character­ istic of our approach is that connections between concepts are es­ tablished by tracing word relationships in the natural language entries of a standard dictionary.

No stronger indication will be found for the other possible con­ struct ·(WITH <FISH> <FORK>): or for the other possible meanings of the preposition (in particular, there is no PARTOF pattern in the definitions of ·fork· that would aUow us to connect ·fork· to ·fish}. Thus, ·JNSTRUMENT(eat,fork)" will be the preferred interpretation of this example.

Let us now ·tum our attention to sentence (2). When evaluating the construct .(WITH <FISH> <BONE>)", the system will find the following PARTOF pattern in the definition of bone:

bone: I . One of the hard parts of the skeleton of a vertebrate.

This yields two possible PARTOF indications: ·skeleton· and ·vertebrate: The system tries to relate each of these terms to ·fish: Since ·fish· is a direct hyponym of ·vertebrate· in W7, we find an ea.,y connection (shown figure 6), which gives a strong indication in favor of the interpretation ·rARTOF(fish,bone)".

Again, as no shorter path wilt be found for any other possible interpretation, this will be the preferred interpretation.

IV. USING INFERENCES

In many cases, the dictionary entry for the prepositional comple­ ment does not provide the necessary information. Specific inference rules can then be tried. 'fbese rules depend on the nature of the connection that the program is trying to establish, and they will usually direct the examination of other dictionary entries.

1bus, in sentence ( 4), the system will not be able to find directly a useful INSTRUMENT pattern in the definitions of the preposi­ tional complement "bus·. But we can make the reasonable infer­ ence that a term can have the same instrumental uses as its hypernyms. The system will go up one level in the hierarchy, and try to frnd INSTRUMENT patterns for the direct hypernyms of 'bus·. One of these hypernyms in W7 is ·vehicle·, which offers the following INSTRUMENT pattern:

vehicle: 3. a means of carrying or transporting something ...

This gives us two instrument indications: ·carry· and ·transport: The taxonomic information offers different ways to connect ·carry· and ·go·, as shown in Figure 7.

The value of the likelihood factor returned by a rule is related to the length of the connection path found. 'Thus the instrumental interpretation will receive a weaker likelihood factor for ( 4) tha~ for (1). However, once again, no stronger preference can be obtam~d for the other interpretations, and ·JNSTRUMENT(go,bus)" wtll be preferred.

In sentence (3), neither "fmger· nor its direct hypernyms will offer any useful INSTRUMENT pattern in their defmitions. How­ ever, "fmger· i! ~efmed as ·~me ofthe]rve terminating members o[a hand, a "hand 1s charactenzed asJ;!rasC,i't}lrgan and "grasp· IS related to "eat· via "take: By m g t e erence that if some­ thing can play an instrumental role, then a part of this something can pia~ the same role, the system is able to establish the following connection:

This inference is at best approximate, and the connection is thus regarded as ~e~er than t~e ones in Figures 5 and 7. However, no other possibility prov1des a stronger connection, and "INSTRUMENT(eat,fmger)* will be the preferred interpretation.

Example sentence ( 5) illustrates another kind of inference using a PARTOF link. The criterion for evaluating the TIME interpre­ tation of *by* is to try to establish a connection between the com­ plement "noon· and one of the terms "time" or "period". No direct taxonomic relation can be found. However "noon· is defmed as "the middle of the day", and "day· is a direct hyponym of "time" in W7. By using the inference that a part of a time can also be a time, the system establishes a strong connection between "noon· and "time: which will lead to the preference of the interpretation "TIME(fmish,noon)":

V. IMPLEMENT AT/ON OF THE DICT/ONAR Y SEMANTIC EXPERT

A standard dictionary is plagued by incompleteness and inconsist­ ency; moreover, the information that it carries, being expressed in natural language form, is complicated. Therefore our rules are de­ signed as heuristics, which can only provide approximate results. The cumulative effect of many heuristics, and not the perfection of each one taken separately, has to do the job.

Heuristics can make use of syntactic and semantic information for determining likelihood factors (LF), as can be seen in the fol­ lowing English description of the rule handling the PARTOF meaning of the preposition "with" (as, for example, in the con­ struction ·a fish with bones}:

H2- checking for a P ARTOF relation between a head and a "with" complement:

1. if the head is not a noun, the relation doesn't hold (I,F = -I);
2. if some P ARTOF pattern exists in the dictionary definition of the complement, and if this pattern points to a defining term that can be linked with the head, then the P ARTOF relation probably holds (LI' = 0. 7);
3. else as.~ume that there is more chance that the relation doesn't hold (LF = -0.3).

Each rule appears as a list of clauses, with each clause containu1g a condition and an action. The conditions are evaluated in se­ quence until one of them is satisfied. The corresponding action (indicated in parentheses in the rule description) defmes the resulting likelihood factor (LF). The first clause of rule H2 is a syntactic test expressing the fact that we want only to consider a possible PARTOF meaning for "with" when the head is a noun. The second clause directs the search for a semantic connection using a PARTOF link, as illustrated in ~ection 3. The third clause provides a default value to be used when all other tests in the rule have failed.

Different preposition meanings may require different types of inferences in order to establish meaningful connections and may also have different syntactic cues. Therefore the system includes at least one rule for each meaning of each preposition it knows about. Several rules may apply to the same preposition meaning; their re­ sulting likelihood factors will then be combined, as in MYCIN, by the formula "LF = I- (I- LFJ)·(J-LF2)" where LFI and LF2 are the factors to be combined.

As an example, we give below another rule used when checking for PARTOF connections. This rule uses a syntactic cue. It ex­ presses our strong intuition that the presence m the prepositional phrase of a possessive which disagrees in person with the possible head noun precludes a PARTOF relation (as, for example, in the construction ·a fish with my fmgers}:

HJ- for checking for a P ARTOF relationship between a head and a "with" complement:

I. if

a. the head is a noun, and

b. the complement is qualified by a possessive, and

c. this possessive doesn't agree in person with the head,

• then the P ARTOF relation probably doesn't hold (LF = -0.9),
• else this heuristic doesn't give any indication (LF = 0).

H3 will be applied in parallel with H2. Most of the time, the result will be the neutral value zero, which does not affect the results of other rules. When the syntactic cue is present, the rule will de­ crease strongly the resulting likelihood factor for the PARTOF in­ terpretation. Generally speaking, the rule structure offers a choice between sequentiality and parallelism. Tests which should be per­ formed sequentially will be included as successive clauses in a rule. Tests which should reinforce each other will be implemented as separate rules.

The condition of a clause may define subgoals, which will be evaluated by applymg other rules. lbus the attempt to use taxonomic or synonymic relations to connect two terms (such as "fish" and "vertebrate· in sentence (2) is defined as a separate sub­ goal, which will be invoked by the second clause of H2 (this can be seen in the formal implementation of the rule, given in Figure 10 below). Different rules may be applied to this subgoal, one checking for a direct taxonomic link, l!.nother for a synonymic link, a third if the two terms have a common parent. The evaluation of the subgoal will also yield a likelihood factor which, if positive, will be multiplied by the one expressed in the action part of the rule, thereby decreasing it.

The choice of likelihood factors rests mainly on intuition. Some choices are easy; some inferences, for example, are obviously weaker than others. In other cases the values have to be adjusted by trial and error, by processing many examples. It is interesting to note that, as our corpus of examples increases, the likelihood factors are converging toward apparently stable values.

The resulting likelihood factor of an interpretation must also be inversely tied to the length of the semantic path corresponding to that interpretation. This is basically accomplished by designing the rules so that a given rule will search only for one link in a path, the other links being identified by subgoals called by that rule. The longer the path, the longer the reasoning chain, and the lower the final likelihood factor.

The rules are written in the PLNLP language (Heidorn 1975), which we shall not describe here. We shall only give below, as an illustration, the formal version of rule II2:

H2(CONTROLER*PTR,COMPLEMENT*PTR, <SEGTYPE(CONTROLER).NE. 'NOUN', <-LF<' PARTOF',) "-1. 0">>, <SUBGOAL2<'PREF' ... CONTROLER ... ENTRIES<COMPLEMENT,'PARTOF'> ... SEGTYPE(CONTROLER) ... 2>, <-LF<'PARTOF' ,]"0.8">>, <-LF<'PARTOF' ,]"-0.3">)

Our prototype system includes currently twenty rules and is able to handle the prepositions "with", "by", "after· and ~m.· It has been tested on about 50 examples so far.

VI. LEARNING USEFUL FACTS

Re-parsing all the defmitions of a word every time that word is en­ countered will soon lead in practice to unsurmountable efficiency problems. Human beings do not look up repetitively the same word in the dictionary. Eventually, they will learn something about its meaning.

We have included in our system a simple but helpful form of learning which consists of remembering useful information extracted from dictionary defmitions. Each time the pattern-matching mech­ anism identifies semantic relations, they are stored in a ·memory ftle" where they will remain available for processing further input. If the same word occurs again later on, the system will check to see if the remembered relations are useful before attempting to parse the definitions. Figure II below shows some of the information re­ membered for sentences (I) and (2) .

(PUT 'FORK (PUT 'FORK (PUT 'BONE (PUT 'BONE 'PARTOF 'NONE) 'INSTRUMENT '(TAKE PITCH DIG)) 'PARTOF '(SKELETON VERTEBRATE)) 'INSTRUMENT '(STIFFEN))

The remembering mechanism offers two significant advantages. First, it can speed up significantly the disambiguation process. Sec­ ond, it provides an interesting tool for fmding out what information is useful and how to store it. Obviously, however, there is still room for considerable improvement in this learning process. In particular, it does not attempt to infer new information, induce new concepts, or even to structure the information in more useful ways. In the long term, this line of research could ·lead to the automatic building of formal knowledge bases from natural language sources.

VII. CONCLUSIONS

We have shown that it is possible to consult automatically a stand­ ard machine-readable dictionary as a knowledge base, in order to resolve ambiguities in the computational parsing of natural language text. Only prepositional phrase attachment ambiguities have been studied so far, but the techniques described here should be extendi­ ble to ambiguities that involve all other classes of phrases and clauses. · Furthermore, there is no need to stop with dictionaries: encyclopedias and other online written works are available, valuable sources of information.

All types of information present and available in dictionary en­ tries should eventually be used to help in the disambiguation proc­ ess: examples, synonyms, and usage notes, as well as the definitions themselves. Other important areas for future development include the development of new heuristics; the adjustment and improve­ ment of the likelihood factors; the analysis of relationships that are signaled by prepositions, conjunctions, and other function words; and also the addition of information on phrasal verbs (verb-particle pairs, verb-preposition pairs), and an investigation of how these will help in the parsing process.

This line of research highlights several principles of computer cognition:

• Knowledge is represented in natural language.
• Natural language text can be accessed by a syntactic parser and a reasoning module (in this case, heuristic reasoning).
• Heuristics can be used to help the program reach new levels of understanding.

The work should benefit all areas of natural language processing ·· from text analysis to machine translation to data base query ·· by opening up the prospect of a genuinely broad-coverage approach to mf.'aning and understanding.

ACKNOWLEDGMENTS

Thanks are due to George Heidorn for the many useful discussions that we had with him during this research and for helpful comments on a previous draft of this paper.