Allen 1995: Chapter 4 - Features and Augmented Grammars Allen 1995 : Natural Language Understanding Contents Preface Introduction previous Part I Part II Part III - Context / World next chapter chapter Knowledge Syntactic Processing Semantic Interpretation Appendices Bibliography Index Summaries Further Readings Exercises Chapter 4: Features and Augmented Grammars 4.1 Feature Systems and Augmented Grammars 4.2 Some Basic Feature Systems for English 4.3 Morphological Analysis and the Lexicon 4.4 A Simple Grammar Using Features 4.5 Parsing with Features o 4.6 Augmented Transition Networks o 4.7 Definite Clause Grammars o 4.8 Generalized Feature Systems and Unification Grammars Summary Related Work and Further Readings Exercises for Chapter 4 [Allen 1995 : Chapter 4 - Features and Augmented Grammars 83] http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (1 / 57) [2002-2-26 21:23:16] Allen 1995: Chapter 4 - Features and Augmented Grammars Context-free grammars provide the basis for most of the computational parsing mechanisms developed to date, but as they have been described so far, they would be very inconvenient for capturing natural languages. This chapter de-scribes an extension to the basic context-free mechanism that defines constituents by a set of features. This extension allows aspects of natural language such as agreement and subcategorization to be handled in an intuitive and concise way. Section 4.1 introduces the notion of feature systems and the generalization of context-free grammars to allow features. Section 4.2 then describes some useful feature systems for English that are typical of those in use in various grammars. Section 4.3 explores some issues in defining the lexicon and shows how using features makes the task considerably simpler. Section 4.4 describes a sample context-free grammar using features and introduces some conventions that simplify the process. Section 4.5 describes how to extend a chart parser to handle a grammar with features. The remaining sections, which are optional, describe how features are used in other grammatical formalisms and explore some more advanced material. Section 4.6 introduces augmented transition networks, which are a generalization of recursive transition networks with features, and Section 4.7 describes definite clause grammars based on PROLOG. Section 4.8 describes generalized feature systems and unification grammars. >> back 4.1 Feature Systems and Augmented Grammars In natural languages there are often agreement restrictions between words and phrases. For example, the NP "a men" is not correct English because the article a indicates a single object while the noun "men" indicates a plural object; the nounphrase does not satisfy the number agreement restriction of English. There are many other forms of agreement, including subject-verb agreement, gender agree-ment for pronouns, restrictions between the head of a phrase and the form of its complement, and so on. To handle such phenomena conveniently, the grammati-cal formalism is extended to allow constituents to have features. For example, we might define a feature NUMBER that may take a value of either s (for sin-gular) or p (for plural), and we then might write an augmented CFG rule such as NP -> ART N only when NUMBER agrees with NUMBER 1 2 This rule says that a legal noun phrase consists of an article followed by a noun, but only when the number feature of the first word agrees with the number feature of the second. This one rule is equivalent to two CFG rules that would use different terminal symbols for encoding singular and plural forms of all noun phrases, such as http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (2 / 57) [2002-2-26 21:23:16] Allen 1995: Chapter 4 - Features and Augmented Grammars NP-SING -> ART-SING N-SING NP-PLURAL -> ART-PLURAL N-PLURAL While the two approaches seem similar in ease-of-use in this one example, consider that all rules in the grammar that use an NP on the right-hand side would [Allen 1995 : Chapter 4 - Features and Augmented Grammars 84] now need to be duplicated to include a rule for NP-SING and a rule for NP--PLURAL, effectively doubling the size of the grammar. And handling additional features, such as person agreement, would double the size of the grammar again and again. Using features, the size of the augmented grammar remains the same as the original one yet accounts for agreement constraints. To accomplish this, a constituent is defined as a feature structure - a mapping from features to values that defines the relevant properties of the constituent. In the examples in this book, feature names in formulas will be written in boldface. For example, a feature structure for a constituent ART1 that represents a particular use of the word a might be written as follows: ART1: (CAT ART ROOT a NUMBER s) This says it is a constituent in the category ART that has as its root the word a and is singular. Usually an abbreviation is used that gives the CAT value more prominence and provides an intuitive tie back to simple context-free grammars. In this abbreviated form, constituent ART1 would be written as ART1: (ART ROOT a NUMBER s) Feature structures can be used to represent larger constituents as well. To do this, feature structures themselves http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (3 / 57) [2002-2-26 21:23:16] Allen 1995: Chapter 4 - Features and Augmented Grammars can occur as values. Special features based on the integers - 1, 2, 3, and so on - will stand for the first subconstituent, second subconstituent, and so on, as needed. With this, the representation of the NP constituent for the phrase "a fish" could be NP1:(NP NUMBERs 1 (ART ROOT a NUMBER s) 2 (N ROOT fish NUMBER s)) Note that this can also be viewed as a representation of a parse tree shown in Figure 4.1, where the subconstituent features 1 and 2 correspond to the subconstituent links in the tree. The rules in an augmented grammar are stated in terms of feature structures rather than simple categories. Variables are allowed as feature values so that a rule can apply to a wide range of situations. For example, a rule for simple noun phrases would be as follows: (NP NUMBER ?n) - (ART NUMBER ?n) (N NUMBER ?n) This says that an NP constituent can consist of two subconstituents, the first being an ART and the second being an N, in which the NUMBER feature in all three constituents is identical. According to this rule, constituent NP1 given previously is a legal constituent. On the other hand, the constituent [Allen 1995 : Chapter 4 - Features and Augmented Grammars 85] http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (4 / 57) [2002-2-26 21:23:16] Allen 1995: Chapter 4 - Features and Augmented Grammars Figure 4.1 Viewing a feature structure as an extended parse tree * (NP 1 (ART NUMBER s) 2 (N NUMBER s)) is not allowed by this rule because there is no NUMBER feature in the NP, and the constituent *(NP NUMBER s 1 (ART NUMBER s) 2 (N NUMBER p)) is not allowed because the NUMBER feature of the N constituent is not identical to the other two NUMBER features. Variables are also useful in specifying ambiguity in a constituent. For instance, the word fish is ambiguous between a singular and a plural reading. Thus the word might have two entries in the lexicon that differ only by the value of the NUMBER feature. Alternatively, we could define a single entry that uses a variable as the value of the NUMBER feature, that is, (N ROOT fish NUMBER ?n) This works because any value of the NUMBER feature is allowed for the word fish. In many cases, however, not just any value would work, but a range of values is possible.. To handle these cases, we introduce http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (5 / 57) [2002-2-26 21:23:16] Allen 1995: Chapter 4 - Features and Augmented Grammars constrained variables, which are variables that can only take a value out of a specified list. For example, the variable ?n{s p} would be a variable that can take the value s or the value p. Typically. when we write such variables, we will drop the variable name alto-gether and just list the possible values. Given this, the word fish might be represented by the constituent (N ROOT fish NUMBER ?n{sp}) or more simply as (N ROOT fish NUMBER {s p}) [Allen 1995 : Chapter 4 - Features and Augmented Grammars 86] BOX 4.1 http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (6 / 57) [2002-2-26 21:23:16] Allen 1995: Chapter 4 - Features and Augmented Grammars There is an interesting issue of whether an augmented context-free grammar can describe languages that cannot be described by a simple context-free grammar. The answer depends on the constraints on what can be a feature value. If the set of feature values is finite, then it would always be possible to create new constituent categories for every combination of features. Thus it is expressively equivalent to a context-free grammar. If the set of feature values is unconstrained, however, then such grammars have arbitrary computational power. In practice, even when the set of values is not explicitly restricted, this power is not used, and the standard parsing algorithms can be used on grammars that include features. >> back 4.2 Some Basic Feature Systems for English This section describes some basic feature systems that are commonly used in grammars of English and develops the particular set of features used throughout this book. Specifically, it considers number and person agreement, verb form features, and features required to handle subcategorization constraints. You should read this to become familiar with the features in general and then refer back to it later when you need a detailed specification of a particular feature. [Allen 1995 : Chapter 4 - Features and Augmented Grammars 87] Person and Number Features In the previous section, you saw the number system in English: Words may be classified as to whether they can describe a single object or multiple objects. While number agreement restrictions occur in several different places in English, jhey are most importantly found in subject-verb agreement. But subjects and verbs must also agree on another dimension, namely with respect to the person. The possible values of this dimension are First Person (1): The noun phrase refers to the speaker, or a group of people including the speaker (for example, I, we, you, and 0. Second Person (2): The noun phrase refers to the listener, or a group including the listener but not including the speaker (for example, you, all of you). http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (7 / 57) [2002-2-26 21:23:16] Allen 1995: Chapter 4 - Features and Augmented Grammars Third Person (3): The noun phrase refers to one or more objects, not including the speaker or hearer. Since number and person features always co-occur, it is convenient to combine the two into a single feature, AGR, that has six possible values: first person singular (is), second person singular (2s), third person singular (3s), and first, second and third person plural (ip, 2p, and 3p, respectively). For example, an instance of the word is can agree only with a third person singular subject, so its AGR feature would be 3s. An instance of the word are, however, may agree with second person singular or any of the plural forms, so its AGR feature would be a variable ranging over the values {2s 1p 2p 3p}. Verb-Form Features and Verb Subcategorization Another very important feature system in English involves the form of the verb. This feature is used in many situations, such as the analysis of auxiliaries and generally in the subcategorization restrictions of many head words. As described in Chapter 2, there are five basic forms of verbs. The feature system for verb forms will be slightly more complicated in order to conveniently capture certain phenomena. In particular, we will use the following feature values for the feature VFORM: base - base form (for example, go, be, say, decide) pres - simple present tense (for example, go, goes, am, is, say, says, decide) past - simple past tense (for example, went, was, said, decided) fin - finite (that is, a tensed form, equivalent to {pres past}) ing - present participle (for example, going, being, saying, deciding) pastprt - past participle (for example, gone, been, said, decided) inf - a special feature value that is used for infinitive forms with the word to [Allen 1995 : Chapter 4 - Features and Augmented Grammars 88] http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (8 / 57) [2002-2-26 21:23:16] Allen 1995: Chapter 4 - Features and Augmented Grammars Figure 4.2 The SUBCAT values for NPNP combinations To handle the interactions between words and their complements, an addi -tional feature, SUBCAT, is used. Chapter 2 described some common verb sub-categorization possibilities. Each one will correspond to a different value of the SUBCAT feature. Figure 4.2 shows some SUBCAT values for complements consisting of combinations of NPs and VPs. To help you remember the meaning of the feature values, they are formed by listing the main category of each part of the complement. If the category is restricted by a feature value, then the feature value follows the constituent separated by a colon. Thus the value npvp:inf will be used to indicate a complement that consists of an NP followed by a VP with VFORM value inf. Of course, this naming is just a convention to help the reader; you could give these values any arbitrary name, since their significance is determined solely by the grammar rules that involve the feature. For instance, the rule for verbs with a SUBCAT value of _np_vp:inf would be (VP) -> (V SUBCAT _np_vp:inf) (NP) (VP VFORM inf) This says that a VP can consist of a V with SUBCAT value _np_vp:inf, followed by an NP, followed by a VP with VFORM value inf. Clearly, this rule could be rewritten using any other unique symbol instead of _np_vp:inf, as long as the lexicon is changed to use this new value. Many verbs have complement structures that require a prepositional phrase with a particular preposition, or one that plays a particular role. For example, the verb give allows a complement consisting of an NP followed by a PP using the preposition to, as in "Jack gave the money to the bank". Qther verbs, such as "put", require a prepositional phrase that describes a location, using prepositions such as "in", "inside", "on", and "by". To http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (9 / 57) [2002-2-26 21:23:16] Allen 1995: Chapter 4 - Features and Augmented Grammars express this within the feature system, we introduce a feature PFORM on prepositional phrases. A prepositional phrase with a PFORM value such as TO must have the preposition to as its head, and so on. A prepositional phrase with a PFORM value LOC must describe a location. Another useful PFORM value is MOT, used with verbs such as walk, which may take a [Allen 1995 : Chapter 4 - Features and Augmented Grammars 89] Figure 4.3 Some values of the PFORM feature for prepositional phrases http://www.uni-giessen.de/~g91062/Seminare/gk-cl/Allen95/al199504.htm (10 / 57) [2002-2-26 21:23:16]