Learning Word Meanings From Examples

ABSTRi\Cf

This paper describes work in progress on a computer program that uses syntactic constraints to derive the meanings of verbs from an analys is of simple English example stories.* The central idea is an extension of Winston's (Winston 1975) program that learned the structural desc riptions of blocks world scenes. In the new research, English verbs take the place of blocks world objects like ARCH and TOWER, with framc·based descriptions of causal relationships serving as the structural descriptions. Syntac tic constraints derived from the parsing of story plots arc used to drive an analogical matching procedure. Analogical matching gives a way to compare descriptions of known words to unknown words. The "meaning" of a new verb is learned by matching pan of the causal network description of a story precis cont aining the unknown word to a set of such descriptions deri ved from similar stories that contain only known words. The best match forges an assignment between objects and relations such that the unknown verb is matched to a known verb. with the as~ignmcnt being guided by syntactic constraints. The causal netwo:·k surrounding the unknown item is then used as a scaffolding to construct a network representing the usc of the novel word in a particular context. Words (and their associated stories) that arc "best matches" arc grouped together into a similarity network, acconling to the match score.

I WORD i\CQUISITION i\ND DEFINITIONS

ll1is paper describes an analogical matching system that attempt,; to learn the causal descriptions of new words. The end result is that there arc no "definitions" in the sense of necessary and sufficient conditions determining word meanings; rather, what is output is an in tcrconncctcd set of descriptions of the actual use of words in context (under a particular theory of "context" , namely, causal network structure). The use of analogical matching here should not be viewed as a necessary ingredient of the learning system. but rather one way w represent a program's knowledge about the world. In other \\·ords, story plots serve as a proxy for systematic understanding of how the world works, and by matching stories the program can determine that a novel situation will work like an old one.

The word learning program is also embedded into a larger system that can acquire new syntactic rules for English, as described in (Berwick 1979 1980 1982). The word learning component uses the larger system's determination of the syntactic category of a new word and its prcdicatc·argumcnt structure (if a verb). These last

· This paper repol1s work done at the Artificial Intelligence l .aboratory of the Massachusetts Institute of Technology. Support for the Laboratory's artificial intetl igencc research is suppotted in part by the Advanced Hc\Carch Projects Agency of the Depanment of Defense under OITJce of Naval Reseaarch contract 1'00 14-80·C ·0505.

LEARNING WORD tv1Fi\i'IINGS FROM I·:XAMI'LES

Robert C. Berwick

MIT Artificial Intelligence l.aboratory, Room 820 545 Technology Sq., Cambridge, MA 02139

two abilities arc hased on the X ·har iheory of (Jackcndufr 1977) and a theory of syntax that assumes a strong principle of lexical transparency (roughl y, that the semantic argumen t structure of a verb appea rs at all levels of representation). The l'VCrall system thus provides a worki11g example of how syntac tic and semantic constraints can interact to aid in the learning of language.

Conceptually, the underlying assumption is that the meaning of a word is determined by the role it pl ays in a causal network descript ion of an event, and that similar words arc those that play similar roles in the description of similar events. To take an example that will be discussed in detai l in Section 2, consider the following scenario:

Suppose we arc given two versions of the story of Macbeth, one reporting that "Macbeth murders Duncan" and the other that "Macbeth assass inates Duncan". Further suppose that "murder" but not "assassinate" is a known word. We should conclude tJ1at "assassinate" is must like "murder" , since, compari ng stories, it seems w us that "assassinate" plays tJ1c same role that "murder" docs in the Macbeth plot. We should also conclude that "assassinate" h:ts political overtones, since we note tJ1at tJ1c Macbeth story includes such relations as "Macbeth wants to be king" and "Macbeth becomes king". Probing fu rther, later stories should inform us that the uses of "assassinate" and "murder" are slightly different. since "murder" needn't carry that political connotations that :·assassinate" docs. We should also be able to usc the story of Hamlet to deduce the same kind of relationship between "murder" and "assassinate".

This scenario illustrates the kind of learning to be modeled by tJ1e program. The actual retrieval and matching of candidate stories is considerably more complex than that described in (Winston 1980). Two separate levels of filtering, geared to linguistic and "script·like" constraints, are invoked before causal network matching is even attempted (largely on account of the computational cost of the rnatching:procedure).

II f1 SCENARIO SHOWS THE PROGRi\M IN ACTION

Perhaps the best way to gain some feel for the details of the acquisition procedure is to run through an example. Here is the actual input for the Macbeth story:

Mt\ is a story about Macbeth l..ady·macbeth Duncan and Macduff. Macbeth is an evil noble. Lady·macbcth is a greedy ambitious woman. Duncan is a king. Macduff is a noble. l..ady·macbeth persuades Macbeth to want to be king because she is greedy. lvlacbeth is evil because Latl)- lvl<icbcth is able to innucncc him and because Lady-Macbeth is greedy. She is able to in nucncc him because he is married to her :md because he is wc:tk. ivbcbcth assassitwcs l)uncan with a knife. fvlJcbcth assassinates Duncan because Macbeth wants to be king and because Macbeth is evil. Lady-macbeth kills herse lf. Macduff is angry. Macduff kills Macbeth because !'vlacbrth murdered Duncan and because Macduff is loyal to Duncan.

Usi ng the techniques described in (Winston 1980) and (Katz and Winston 1982). the system builds a "causal netwo rk description" of the story, as shown below. This network is basically an object-oriented semantic network, with objects, agents, and qualities (and sometimes propositional attitudes like beliefs or desires) serving as tl1c nodes in tl1e network and verbs serving as the links between nodes. The network is directed. It is dubbed "causal" because a major component is tl1e addition of directed CAUSE links indicating that an object or relation at the link tail causally contributes to tl1~ relation or action at its head. (There arc some other special link labels. The "HQ" link label denotes a two-place relation between nodes that is to be read as "X has quality Y"; AKO X = a-kind-of X. Some relations arc added by one-step inference demons, described below; for example, "murder"--> adds "JIQ dead", "HQ ev il" as appropriate. For reasons of clarity, some links in tl1c description arc omitted in the diagram below. There arc also several·evident weaknesses of tl1e representation that wi ll not be dealt with here. Most notably, aside from the implicit ordering imposed by causal relationships, there is no notion of temporality.)

Now suppose that a number of other stories have been prcviou~ l y analyt.cd and stored in causal network form, e.g., Macbeth. Hamlet, Julius Caesar. and the laming of the Shrew, as discussed in (Winston 1980). and that none of these previous plot summaries used the word "assassinate."

The first job of the program is to successfully parse the input story containing the unknown word. Here, tl1e new story differs in just two ways from the old story since the new word is used twice.

The techniques described in (llcrwick 1982) (based on the Marcus parser (Marcus 1980) arc used to syntxtically analyze the input:

(I) Consider the sentence, "Macbeth assassinates Duncan". Since all S's arc assumed to be of the form NP-YP, the parser predicts the existence of an NP Subject.

(2) With UlC NP disposed of, the parser now predicts that an lnOcctional clement and a Verb Phrase (VP) will be found. Now the constraint (sec (.Jackcndoff 1977)) that English Verb Phrases are headed by Verbs forces "assassinate" to be a Verb.

(3) Finally. "])uncan" is parsed as an NP and noted as an Object of the unknown verb. Since arguments arc assumed obligatory until proven otherwise by positive examples (sec (Berwick 1982) for a discussion of this lcarnability constraint), this NP is presumed to be a required argument of "assassinate".

With the analysis of the novel sentences in band, the remainder of tl1e story anal ysis proceeds as before. A causal network representation can he built that is nearly identical to the network built previously, hut with some key differences that flow from the lack of understanding of "assassinate." Most importantly, since tl1crc arc no one-step inference demons attached to "assassinate," tl1c HQ relations of Duncan being dead and Macbctl1 being evil cannm be deduced. Still, tl1c proper syntactic analysis pcnnits the entire network to be built save for these two relations, since the connections between objects and actions are actually syntactic.

When tl1c plot-unit portion of tl1e system is complete, then the next step will be to output a a high-level description of tl1e story in tl1c style suggested by the work of (Lehnert 1981). Note that the plot summary is intended to be a computational aid to story retrieval, and is not tl1e central thrust of this work. Roughly, plot unit tl1cory is grounded on a "chemical" model of representation. It assumes that the causal relationships in a story can be summarized by extracting out the "molecular structu re" of the causal network. ·111is is done by imposing a theory of plot molecular structure onto the more basic causal network. While there is no space to give the details of this procedure here, we simply note that given a network description, we can try to form a corresponding description in terms of "atomic" plot abstraction units like "loss" or "gain" (an agent experiences something negative or positive). This exercise is far from easy, however, and tl1c rules for carrying out this translation arc still under development. ·

Since the plot-unit step is sti ll under development, it will not be further described here. Instead, what is currently done is to simply retrieve descriptions of all stories in tl1c Shakespeare precis database. In our running example, these arc the stories of Macbeth, Hamlet, Julius Caesar. and the Taming of the Shrew.

What next? The learn ing procedure !Jikcs tl1e the causal network descriptions of each of the candidate stories and run tl1c analogy matching program, pairing objects and relations in the new Macbeth story against objects and relations in each of the candidates until the best match is obtained. /\s mentioned, we restrict our attention to just tl1at portion of the network tlutt is immediately connected to the causal links emanating from "assassinate". This means that distantly related events and relations arc not brought in for matching at all. (This metric of locality could of course be modified, but seems a reasonable first stab at a way to fix local context.) The matching program as designed can be primed to consider only matches that keep intact the objects on citJ1cr end of tl1e unknown "assassinate" link (this means tlwt the match of "Macbeth" in Macbeth story #2 against "Duncan" in Macbeth story # l is not even attempted, since tl1is would be incompatible with the direction of the "murder" and "assassinate" links).

TI1c match scores obtained are as follows. MA-2 is the new Macbeth-story.

MA HAM JUL SHR

MA-2 22 15 12 2

Not surprisingly, MA gets the highest match score, with the algorithm mating "assassinate" in MA-2 to "murder" in MA But the algorithm also pairs "assassinate" in MA-2 with "kill" in Hamlet and Julius Cac:>ar, demonstrating that it would not be necessary to have an absolutely identical story in order to extract a useful word meaning. The algorithm weds "assassinate" to "love" in the raming of the Shrew, but this receives a low match score.

Next we modify the causal network description associated with "assassinate" according to the !;Jest match story. Any relations that locally associated with "murder" in the MA-l network arc added to the MA-2 description. In our example. this means that the "IJunc<m HQ dead" and "Macbeth HQ evil" links will be added to the MA-2 network. This modification corresponds to the a'isurnption that since "assassinate" has been deduced as most similar to "murder". the inferences f(>llowing from "murder" will also be ttue of "assassinate." (This of course is only approximately so, and later story examples where the target of assassination survives -- if explicitly indicated in the story -- would modify this link.}

Finally, the "meaning" of the novel verb is stored by associating with the word entry (i) a pointer to its causal network description; and (ii) a list of "nearest neighbor" words, according to the results of the matd1ing algorithm. The similarity metric is normalized by the value obtained from matching an identical story against itself. In the case of multiple word matches (as with "kill", the best match word in both Hamlet and Julius Caesa r), the highest scoring value is used. In the example above. the new entry for "assassinate" incl udes the related words of "murder" (score .88); "kill" (.60}, and "low" (.08). (The :;core f!1r MA is not 1 becau~c the "HQ dead" and "IIQ evil" relations associated with "murder" arc not present in the initial MA-2 desc ription.) The program also adds difference poin t e r~ indicating why the stored causal network description is diffc r~nt from each of the network descriptions .associated with these tJH..:e words. In tl1e case at hand, tJ1erc arc no such difkrenccs. but if the ·best match story was. say, about a general homicide, tJ1cn the "AKO" links wolild indicate that tJ1e characters in tJ1e "assassinate" story were all a-kind-of political figures, whereas those in the general homicide story need not be. Difference pointers could then be used to encode some of the distinctions between "murder" and "assassinate."

III OPEN PROBLEMS

In this short paper, many important topics currently under investigation could not be covered. These include:

-- Jlettcr generalization schemes arc required. Currently, all details about a related story arc kept. The only possible generalization is via the "AKO" hierarchy that drives the formation of di ffcrence pointers between word networks. This means that the choice of AKO vocabulary is crucial, since if the category "noble" is not known then no generalizations about the category "noble" is possible. A better way of creating generalized categories out of old ones is needed. perhaps based on the work of (Kcil 1979) on the development of semantic categories.

-- Plot unit summarizat ion must be :~ddcd to reduce the computational burden of matching against all known stories.

--The use of causal network descriptions of stories to summarize world knowledge must be carefully examined.