Language Acquisition: Learning a Hierarchy of Phrases

1. INTRODUCTION

All language-related knowledge required by a linguistic model resides in its lexicon. Traditionally, the lexicon has been viewed as a flat list of lexical entries [Bresnan82]. Recently, however [Jacobs85, Langacker86], hierarchy has emerged as a method for organizing lexical information. Through the hierarchical representation, linguistic knowledge ranging form general grammar rules, to specific lexical entries can be covered uniformly. A significant ad­ vantage of this approach is the ability to cope with incom­ plete knowledge-a problem faced by any running linguistic model, as well as by humans.

Here, due to the context provided by the user, RINA forms an initial hypothesis. However, based on a single example, the hypothesis is not general enough (doing a job on behalf of a second person is not the essence of the meaning).

(3) A Similar Entry Exists, and a Context is Given: Nc;xt, RINA hears a similar phrase, to boss around.

User:

RINA:

Mary was hired on the same day as John, but she knew the manager. Therefore, she used to boss around her colleague, John.

Mary forced him to act.

At this point, RINA could identify the similarities between the two situations. Basically, RINA detected a common sur­ face feature (the word around), and common semantic features (one person uses his power to impose his will on a second person). She constructs a generalization regarding the association between these features, and accordingly, she conveys a more general hypothesis to the user. This hy­ pothesis may help the learner predict the behavior of other phrases involving the word around. However, since there are phrases involving around which do not have this meaning (e.g., stick around, get around to it, etc.), the acquired general­ ized phrase must carry discriminating conditions.

(4) No Context is Given, but a General Entry Exists: Next, RINA hears a third related phrase, to order around:

User: Doug, Linda's younger brother,

told her to stop ordering him around.

RINA: Doug asked Linda to stop forcing him to act?

Like the first scenario, neither: (a), the phrase order somebody around is encoded explicitly in the lexicon, nor (b), any ex­ planatory context is provided by the user. However, in ab­ sence of specific knowledge for parsing the new phrase, RINA applies here the general phrase acquired previously. RINA's hypothesis is not guaranteed to be correct, yet it enables the formation of a hypothesis regarding the unk­ nown phrase.

Notice how learning improved the performance of the pro­ gram.

• Before learning, RINA was not able to parse push around (without an explanatory context).
• After learning, even in conditions of minimal context, RINA could parse sentences which include, not only the phrase itself, but an entire set of similar phrases.

1.2 The Issues

Five issues must be addressed in acquiring such a hierarchi­ cal lexicon.

Determining Scope and Variability: The syntactic pattern of a new phrase is extracted initially from a single sentence.

Frank used to push Corinne around.

From that sentence, the program must determine scope and the variability of the pattern. However, the unknown pattern could take on many forms.

Frank pushed Corinne

X:person push:verb Y:person

X:person push:verb Y:person around

X:person use:verb to push:verb Y:person around

Which one of the forms above is appropriate as the phrase pattern?

Forming the Meaning: The meaning of the phrase is ex­ tracted form the context. However, the context includes many concepts, some appropriate, and some inappropriate for meaning formation. Thus, based on the given context of Frank and Corinne, what is the meaning of push around?

Generalization: From the first example, RINA extracted a narrow meaning:

RINA: Frank made Corinne carry out a job on his behalf.

By hearing a second example, RINA was able to generalize the meaning:

RINA: Mary forced John to act against his will.

This meaning pertains to general interpersonal relationships (power, authority) and can cover more situations in which the phrase may appear. ( 1) How can a generalization be formed across two apparently distinct situations (family feud vs. problems at the working place)? (2) How far should generalization be pursued without causing overgen­ eralizing (e.g., here is an overgeneralization: Frank did some­ thing negative to Corinne)?

Specialization: A new phrase order around is encountered without an explanatory context. Yet, although a specific lex­ ical entry for that phrase does not exist, the phrase can be analyzed by a generalized phrase. How is generalized knowledge applied in coping with gaps in specific knowledge?

Phrase Disambiguation: Even when all the necessary in­ formation exists in the lexicon, parsing is not without prob­ lems. Consider the following pair of texts:

• Mary and John were ice skating in circles. He was pushing her around.
• John acted bossy with Mary. He was always pushing her around.

Since two phrases exist for push around, the program must select the appropriate one in each case. Individual lexical entries must provide the sufficient conditions for phrase discrimination.

1.3 The Approach

The phrasal lexicon [Becker75, Wilensky81, Fillmore87] contains not only single words (e.g., around), rather it con­ tains entire phrasal entries (e.g., to get around to it, to stick around, around the clock, around Spm). The phrasal approach has proved effective in parsing [Wilks75] and in generation [Jacobs85]. Yet the basic dilemma regarding inclusion of phrases in the lexicon is unresolved. Which linguistic ele­ ments belong in the phrasal lexicon, and which elements do not? On the one hand, productive phrases such as John gave Mary the spoon, or Mary went to school, should not reside in the lexicon, lest the lexicon will get oversized. On the other hand, rum-productive phrases such as the big apple, or to throw the book; at somebody must reside in the lexicon. Their mean­ ings cannot be derived from their constituents. However, there is a gray area which includes phrases such as stick around, hang around, and sit around, for whom the inclusion question is unclear. These phrases are non-productive, since their meanings cannot be simply derived from the single words. Thus, they must be included. However, they all share semantic and syntactic features, thus they should not all be included as separate entries. Therefore in our model, such groups of phrases are clustered into generalized phrases, which represent their shared features. Such general­ ized phrases serve in predicting meanings of similar combi­ nations even before they have been encountered.

The hierarchical representation facilitates learning as a con­ tinuous process of knowledge refinement. Two approaches have been integrated in our model. Using Mitchell's method [Mitchell82] we view the lexicon as a version space of rules. Since phrases are organized in a hierarchy by general­ ization, then both parsing and learning require determining location of phrases in that hierarchy. Kolodner [Ko­ lodner84], on the other hand, has shown how learning is ac­ complished by organizing episodes in a dynamic memory. In our model, the lexical hierarchy itself is dynamic and nodes at all levels of generality are updated by receiving in­ stance episodes at the bottom of the hierarchy.

2. REPRESENTING THE CONTEXT

The context is represented as a goal-plan situation at two levels: specific planning, and abstract planning.

Specific Planning Knowledge: Planning knowledge in each domain consists of goals-and acts which implement those goals. For example, consider the text:

Frank needed to clean up his room; Corinne made his bed for him.

The events underlying the sentence are given in the follow­ ing plan box [Schank77].

Making the bed (G1), wiping the floor (G2), clearing the desk (G3), are all subgoals for cleaning one's room (GO). In this case, although GO is a goal of Frank, Act Al which im­ plements G 1 is executed by Corinne.

Abstract Planning Knowledge: Many specific plan boxes are required in covering planning situations across domains. In contrast, a relatively small set of abstract planning struc­ tures [Wilensky83] (e.g., goal-conflict, goal-competition, goal-concordance, plan agency, etc.), and relations (authori­ ty, power, friendship) can cover situations across all domains. In our example, due to the power relationship between characters X and Y, X causes Y execute an act A on X's behalf. This is shown in figure 2 below.

Corinne serves as a plan agent in executing a plan for Frank. Her motivation is neither (a) an authority relation­ ship (Frank is not an authority for Corinne), nor (b) a friendship with Frank, but (c) the power relationship (due to his Frank's age). The abstract planning elements are used here to explain the planning situation. Planning knowledge at these two levels provide the semantics for lexical representation.

3. THE LEXICON

The phrasal lexicon [Zemik87a] is specified in two ways: by the contents of single lexical entries, and by the struc­ ture of the entire lexicon.

Single-Phrase Representation: A lexical entry, or a phrase, is a triple associating a linguistic pattern with its concept and a presupposition. For example compare the following sentences: ·

1. John sat three days working on his thesis.
2. John sat around three days working on his thesis.

What is the difference between their meanings, and what is the value added by the modifier around? The phrase to sit around is represented as a triple:

.

Sentence (2), then, is parsed in three steps using the lexical phrase:

1. The pattern is matched successfully against the text. Consequently, X is bound to the person called John.

1. The presupposition is unified with the current context In this case the variable P is taken by the context as the Ph.D work.
2. Since both (1) and (2) are successful, then the pattern itself is instantiated, adding to the con­ text: working on the PhD wasted John's time (which disabled execution of other acts by John).

Generalized Phrases: However, the representation given above for hang around is not satisfactory when considering two other similar phrases:

John used to stick around for hours. John bung around, waiting for his girlfriend.

The lexicon cannot simply enumerate all word combina­ tions. There must be a more general entry to account for all the phrases of the from "verb around" which convey this particular sense.

pattern:

X:person V:act around

presupposition: V is an act of staying in location L

for a period of time

concept:

staying in L disables execution of other acts by X

This entry captures an entire set of such phrases. The presupposition part is used to discriminate phrases such as hang around, and stick around from phrases such as push some­ body around and boss somebody around, by detecting necessary conditions in the context.

The Global Hierarchy: A hierarchy is defined, to accom­ modate for phrases at all levels of generality.

(The names of the nodes in this scheme are for reference only.) Phrases in this hierarchy are· all given uniformly as pattern-concept-presupposition triples. For example, P13 (sit) is the phrase for sit around, and P6 ("idle") is the phrase encompassing a set of V around phrases. Specific phrases, traditionally called "lexical rules", reside near the bottom. General phrase, or "grammar rules", reside at the top. P2 (around), for example, maintains general knowledge about the behavior of that modifier.

4 THE ALGORITHM

The learning algorithm accepts as input a sequence of ep­ isodes, from which it generates a subtree of phrases. The hierarchy before arid after learning is given schematically below, where subtree T4 is the element added to the lexicon by learning.

The process itself is shown schematically through a se­ quence of snapshots.

1. Initially, the subtree includes only a the general node P2 (which stands for the modifier around).
2. Node P8 is extracted from episode El.
3. Node P9 is extracted from episode E2. Howev­ er, P7 is generalized by detecting the similarities between El and E2,
4. E3 is not informative enough for extraction of a node. However, node P10 can be specialized from the general node P7.

Thus, a subtree is added under P2. The specifications of the algorithm are given below. The given information is:

1. An initial hierarchy. This hierarchy is not sufficiently developed, so parsing of certain sen­ tences might fail.
2. A sequence of episodes. An episode is a para­ graph embedding a new phrase in an explanato­ ry context.
3. The semantics of the context. Semantic knowledge is given in terms of planning knowledge.

The objective is to refine the initial hierarchy. By adding on additional nodes, or by specializing and generalizing ex­ isting nodes, the new hierarchy should facilitate parsing of sentences on which the initial hierarchy has failed. The three basic steps of the algorithm are explained in regard to the sequence of scenarios in section 1.1.

4.1 Extracting a Phrase from a Single Example

Two simultaneous actions are involved in acquiring an unk­ nown phrase from a training example (Frank pushed his younger sister around).

1. The pattern is extracted from the input sentence.
2. The meaning (both concept and presupposition) is extracted from the given context.

(1) Forming the Pattern

Two problems arise in pattern formation: determining the scope and determining the variability of the new pattern.

Determining the scope: Since the input sentence includes not only the bare phrase itself, but some additional cle­ ments, it is necessary to determine which elements in the sentence should be included in the pattern and which ones should be excluded. For example, the sentence under con­ sideration contains two modifiers:

Throughout their cbildbood, Frank used to push Corinne arOUDCI.

While throughout their childhood is excluded, around is taken as a part of the new phrase. The reason is that throughout their childhood can be interpreted successfully by the parser in any context. It docs not cause a parsing failure. However, around does cause a parsing failure: "Frank moved Corinne around something"? Thus, the pattern is scoped as follows:

X:person push Y:person around

Determining variability: In converting an instance sentence into a general pattern, each element in the new pattern ei­ ther becomes a variable, or it remains as a literal. In the conversion above, both Frank and Corinne were taken as gen­ eralized references to persons, X andY. Accordingly, it ap­ pears that the rule was:

References to persons and to objects are converted into variables.

However, this rule is refuted by examples such as:

1. Admiral Neilson went to Davey Joaes' locker.
2. He kicked the bucket in Trafalg.-.

In these idioms, the marked references are taken as literals and not as variables, in violation of the rule above. Thus, the rule must be refined:

References which can be resolved in the context are converted into variables. References which cannot be resolved in the context are kept as literals.

Further strategies for pattern formation are described else­ where [Zernik87b].

(1) Forming the Meaning

Initially, the program focuses at the level of specific plans.

• 0 (cleaning the room) is goal of X (Frank).

P (making the bed) is a plan for G.

P is cried out by Y (Corinne).

The meaning captured at this level is: X carried out a job on Y's behalf. Consequently, the acquired phrase is:

pattera:

X:person <push around> Y:person

presuppositioa: P is a plan for 0

coacept:

Y is a plan agent in executing plan P for X

P8: The Specific Phrase for push around

However, many situations in which push around may be ap­ plied, are not included in P8's definition. Thus, P8 must be generalized.

4.1 Generalizing from Two Examples

The second scenario, Mary bossed her colleague around, does not · share the specific features with the first example. Syntacti· cally: the verb is boss and not push. Semantically: John did not carry out a job in Mary's behalf. Thus both the pattern and the meaning must be generalized.

The pattern is generalized as the verb becomes a variable. The meaning is generalized when specific planning elements are replaced by abstract planning structures which are shared by both episodes: Mary used her power (and not an authority), and Frank used his power to make Corinne act against her will. Therefore, the resulting phrases is:

pattena:

X:penon <V:act around> Y:person

presuppositioa: X presents a power for Y

coacept:

X causes Y to act against X's will

P7: The Generalized Phrase for "dominating"

Notice that although the general phrase P7 was generated, the specific phrases P8 and P9 have not been eliminated. Specific information is maintained even though it is sub­ sumed by more general information.

4.3 Specializing a General Phrase

A specific phrase does not exist for order around in the fourth scenario. However, the sentence is parsed by using the gen­ eralized phrase P7. P7 is matched successfully in the ep­ isode E3, since:

1. The syntactic pattern of P7 matches the input sentence (the form is x Verbed Y around).
2. The semantic presupposition matches the input context (X presents a power to Y).

The specific phrase PlO (for order around) is added on to the lexicon, although it is subsumed by P7. For one thing, specific phrases enrich the program's vocabulary. In text generation they en:1ble production of sentences which in­ clude specific variants of generalized phrases.

5 PREVIOUS WORK IN LANGUAGE ACQUISITION

Two previous models of language acquisition are related to our work. Granger's program FOUL-UP [Granger77], which acquired word meanings, and Pinker's model [Pinker84] which acquired language syntax.

FOUL-UP was devised as a mechanism for extending SAM's [Cullingford78] lexicon while performing conceptual analysis. SAM constructed meanings for English sentences by a two-step cycle: (a) select a script, and (b) instantiate the script For example the following text:

John's baby caught a cold. He called up his doctor, and made an appointment for the next morning. The nurse took his tern­ perature, and it was 106 degrees. She realized immediately that he needed to be ragled.

involves the $clinic script, which stands for a chain of events associated with a visit to the family doctor. Thus, the combination of child-being-sick followed by call-up-a­ doctor causes the selection of $clinic. Once this script is selected, references and events can be readily resolved. Made an appointment for example is taken as a standard $clinic event. The nurse is bound to a designated role-holder in the script, and take his temperature also matches an anticipated ac­ tion while in the clinic. The reference his (in his temperature) is bound to John's baby (and not to John) since the baby holds the role of the patient in $clinic. FOUL-UP is ac­ tivated by SAM at the point that the word raggled is encoun­ tered, a word which does not appear in SAM's lexicon. By knowing the rest of the possible events and the possible outcomes of $clinic, FOUL-UP can predict that to be raggled means to taken to the hospital. FOUL-UP learned lexical entries assuming that the new single word appeared in the context of a script, and that the meaning of the word could be drawn from that script. FOUL-UP did not handle syntax acquisition, nor multi-word phrases.

Pinker [Pinker84] modeled child language acquisition, cov­ ering phenomena ranging from basic phrase structure identification to mastering phrase interaction-the issue being addressed here. Phrase interaction, or complementation, is restricted by two substantive constraints:

• (a) The argument which might be missing in the com­ plement is always the subject (e.g. : in John persuaded Mary to leave, the subject of the verb leave is not ex­ plicit in the text).
• (b) The missing argument is equated with either one of:
• an object of the controlling verb (persuade in the example above), if an object exists (which is the case in the example),
• The subject of the controlling verb if ¢e object does not exist (as in John asked to go).

This pattern of behavior holds for virtually all complem~t­ taking English verbs. Nonetheless there are some exc:ptions such as promise in John promised Mary to go, or make m John made Mary a fine husband. Such exceptions, although small in number, are significant since they could be used for testing the power of language-learning theories. If such exceptions did not exist, the learning of verb complementation would be trivial. Indeed this behavior (of promise) accounts for er­ rors in children's language, as recorded by Carol Chomsky [Chomsky69] (as in Jenny's father promised her to go to Disney­ land meaning he promised her that she would go there). At this point, an example in context (in which it is clear that the fa­ ther is supposed to go) can correct such a hypothesis.

RINA draws from both these approaches. RINA's acquisi­ tion of lexical items concerns the mapping between syntac­ tic patterns and their semantic concepts. However, Granger's model was restricted to single words and simple script-like contexts. RINA also addresses issues such as control and complementation. However, in our view, behavior of verbs reflects their semantics, and it is not just an arbitrary parameter which needs to be acquired to distin­ guish promise from persuade. Concepts representing such verbs must account for two facts. The verb means that (1) one party conveyed fact to a second party, and (2) each in­ dividual verb denotes a different speech act performed by conveying that fact. Thus learning the special syntax of promise is a by-product of understanding what promise means.

Pinker presupposes the existence of certain innate learning procedures. In his model, each language feature is account­ ed for by a custom-tailored procedure. For example, in learning the control aspect of complement-taking verbs, Pinker assumes this preexisting rule (Rule C3):

Add to the lexical entry of the complement-taking predicate the equation X-COMP's SUBJ · (FUNCTION) where (FUNC­ TION) is the grammatical function annotated to the matrix ar­ gument .that is coindexed with the missing complement subject in the contextually inferred semantic representation. ( [Pink­ er84] pp. 213).

Pinker has chosen Lexical-Functional Grammar (LFG) [Bresnan82] as his linguistic framework. While LFG intends to denote a variety of linguistic phenomena, the rule C3 talks about LFG notation, but it certainly is not expounded in LFG terms. Moreover, if a language-learning program re­ quires such a specific procedural rule for each language feature, then the purpose of modeling learning in the first place is defeated. Learning must be handled by a general declarative mechanism. In fact, the same unification mechanism which accounts for parsing and generation, should account also for learning.

6 CONCLUSIONS

Although the lexicon includes both specific and general phrases, the algorithm which constructs the hierarchy must require as input only specific episodes. This reflects human learning behavior. When communicating, people do not ex­ . change syntax and semantics in form of rules, rather they communicate in terms of specific examples in context.

Accordingly we have shown a learning algorithm which augments a hierarchical lexicon as follows: