16.5.2 Unification-Based Parsing

A more radical approach to using unification in parsing can be motivated by looking at an alternative way of denoting our augmented grammar rules. Consider the following S rule that we have been using throughout this chapter.

$$ \begin{aligned}&S\rightarrow NPVP\\&\langle NP\ HEAD\ AGREEMENT\rangle=\langle VP\ HEAD\ AGREEMENT\rangle\\&\langle S\ HEAD\rangle=\langle VP\ HEAD\rangle\\ \end{aligned} $$

An interesting way to alter the context-free part of this rule is to change the way its grammatical categories are specified. In particular, we can place the categorical information about the parts of the rule inside the feature structure, rather than inside the context-free part of the rule. A typical instantiation of this approach would give us the following rule (Shieber, 1986).

$$ \begin{aligned}&X_{0}\rightarrow X_{1}X_{2}\\ &\left\langle X_{0}CAT\right\rangle=S\\ &\left\langle X_{1}CAT\right\rangle=NP\\ &\left\langle X_{2}CAT\right\rangle=VP\\ &\left\langle X_{1}HEAD AGREEMENT\right\rangle=\left\langle X_{2}HEAD AGREEMENT\right\rangle\\ &\left\langle X_{0}HEAD\right\rangle=\left\langle X_{2}HEAD\right\rangle\\ \end{aligned} $$

Focusing solely on the context-free component of the rule, this rule now simply states that the $ X_0 $ constituent consists of two components, and that the $ X_1 $ constituent is immediately to the left of the $ X_2 $ constituent. The information about the actual categories of these components is placed inside the rule's feature structure; in this case, indicating that $ X_0 $ is an S, $ X_1 $ is an NP, and $ X_2 $ is a VP. Altering the Earley algorithm to deal with this notational change is trivial. Instead of seeking the categories of constituents in the context-free components of the rule, it simply needs to look at the CAT feature in the DAG associated with a rule.

Of course, since it is the case that these two rules contain precisely the same information, it isn't clear that there is any benefit to this change. To see the potential benefit of this change, consider the following rules.

$$ \begin{aligned}X_{0}&\rightarrow X_{1}X_{2}\\&\left\langle X_{0}CAT\right\rangle=\left\langle X_{1}CAT\right\rangle\\&\left\langle X_{2}CAT\right\rangle=PP\end{aligned} $$

$$ X_{0}\to X_{1}{~a n d~}X_{2} $$

$$ \left\langle X_{1}CAT\right\rangle=\left\langle X_{2}CAT\right\rangle $$

$$ \left\langle X_{0}CAT\right\rangle=\left\langle X_{1}CAT\right\rangle $$

The first rule is an attempt to generalize over various rules that we have already seen, such as $ NP \rightarrow NP $ PP and $ VP \rightarrow VP $ PP. It simply states that any category can be followed by a prepositional phrase, and that the resulting constituent has the same category as the original. Similarly, the second rule is an attempt to generalize over rules such as $ S \rightarrow S $ and $ S, NP \rightarrow NP $ and NP, and so on. $ ^{1} $ It states that any constituent can be conjoined with a constituent of the same category to yield a new category of the same kind. What these rules have in common is their use of phrase structure rules that contain constituents with constrained, but unspecified categories, something that can not be accomplished with our old rule format.

Of course, since these rules rely on the use the CAT feature, their effect could be approximated in the old format by simply enumerating all the various instantiations of the rule. A more compelling case for the new approach is motivated by the existence of grammatical rules, or constructions, that contain constituents that are not easily characterized using any existing syntactic category.

Consider the following examples of the English How-MANY construction from the WSJ (Jurafsky, 1992).

(16.23) How early does it open?

(16.24) How deep is her Greenness?

(16.25) How papery are your profits?

(16.26) How quickly we forget.

(16.27) How many of you can name three famous sporting Blanchards?

As is illustrated in these examples, the HOW-MANY construction has two components: the lexical item how, and a lexical item or phrase that is rather hard to characterize syntactically. It is this second element that is of interest to us here. As these examples show, it can be an adjective, adverb, or some kind of quantified phrase (although not all members of these categories yield grammatical results). Clearly, a better way to describe this second element is as a scalar concept, a constraint can be captured using feature structures, as in the following rule.

$$ X_{0}\to X_{1}X_{2} $$

$$ \langle X_{1}ORTH\rangle=\langle how\rangle $$

$$ \left\langle X_{2}SEM\right\rangle=\left\langle SCALAR\right\rangle $$

A complete account of rules like this involves semantics and will therefore have to wait for Ch. 17. The key point here is that by using feature structures a grammatical rule can place constraints on its constituents in a manner that does not make any use of the notion of a syntactic category.

Of course, dealing this kind of rule requires some changes to our parsing scheme. All of the parsing approaches we have considered thus far are driven by the syntactic category of the various constituents in the input. More specifically, they are based on simple atomic matches between the categories that have been predicted, and categories that have been found. Consider, for example, the operation of the COMPLETER function shown in Figure 16.11. This function searches the chart for states that can be advanced by a newly completed state. It accomplishes this by matching the category of the newly completed state against the category of the constituent following the • in the existing state. Clearly this approach will run into trouble when there are no such categories to consult.

The remedy for this problem with COMPLETER is to search the chart for states whose DAGs unify with the DAG of the newly completed state. This eliminates any requirement that states or rules have a category. The PREDICTOR can be changed in a similar fashion by having it add states to the chart states whose $ X_0 $ DAG component can unify with the constituent following the $ \bullet $ of the predicting state. Exercise 16.6 asks you to make the necessary changes to the pseudo-code in Figure 16.11 to effect this style of parsing. Exercise 16.7 asks you to consider some of the implications of these alterations, particularly with respect to prediction.

16.6 TYPES AND INHERITANCE

I am surprised that ancient and modern writers have not attributed greater importance to the laws of inheritance...

Alexis de Tocqueville, Democracy in America, 1840

The basic feature structures we have presented so far have two problems that have led to extensions to the formalism. The first problem is that there is no way to place a constraint on what can be the value of a feature. For example, we have implicitly assumed that the NUMBER attribute can take only sg and pl as values. But in our current system, there is nothing, for example, to stop NUMBER from have the value 3rd or feminine as values:

NUMBER FEMININE

This problem has caused many unification-based grammatical theories to add various mechanisms to try to constrain the possible values of a feature. Formalisms like Functional Unification Grammar (FUG) (Kay, 1979, 1984, 1985) and Lexical Functional Grammar (LFG) (Bresnan, 1982), for example, focused on ways to keep intransitive verb like sneeze from unifying with a direct object (Marin sneezed Toby). This was addressed in FUG by adding a special atom none which is not allowed to unify with anything, and in LFG by adding coherence condi

tions which specified when a feature should not be filled. The Generalized Phrase Structure Grammar (GPSG) (Gazdar et al., 1985, 1988) added a class of feature co-occurrence restrictions, to prevent, for example, nouns from having some verbal properties.

The second problem with simple feature structures is that there is no way to capture generalizations across them. For example, the many types of English verb phrases described in the Subcategorization section on page 16 share many features, as do the many kinds of subcategorization frames for verbs. Syntacticians were looking for ways to express these generalities.

A general solution to both of these problems is the use of types. Type systems for unification grammars have the following characteristics:

1. Each feature structure is labeled by a type.

2. Conversely, each type has appropriateness conditions expressing which features are appropriate for it and what types of values then can take.

3. The types are organized into a type hierarchy, in which more specific types inherit properties of more abstract ones.

4. The unification operation is modified to unify the types of feature structures in addition to unifying the attributes and values.

In such typed feature structure systems, types are a new class of objects, just like attributes and values were for standard feature structures. Types come in two kinds: simple types (also called atomic types), and complex types. Let's begin with simple types. A simple type is an atomic symbol like sg or pl (we will use boldface for all types), and replaces the simple atomic values used in standard feature structures. All types are organized into a multiple-inheritance type hierarchy (a kind of partial order called a lattice). Fig. 16.12 shows the type hierarchy for the new type agreement, which will be the type of the kind of atomic object that can be the value of an AGREE feature.

In the hierarchy in Fig. 16.12, 3rd is a subtype of agr, and 3-sg is a subtype of both 3rd and sg. Types can be unified in the type hierarchy; the unification of any two types is the most-general type that is more specific than the two input types. Thus:

3rd ⊥ sg = 3sg

1st ⊆ pl = 1pl

1st ⊥ agr = 1st

3rd □ 1st = undefined

The unification of two types which do not have a defined unifier is undefined, although it is also possible to explicitly represent this fail type using the symbol ⊥ (Ait-Kaci, 1984).

The second kind of types are complex types, which specify:

• a set of features that are appropriate for that type

• restrictions on the values of those features (expressed in terms of types)

equality constraints between the values

Consider a simplified representation of the complex type $ \text{verb} $, which just represents agreement and verbal morphology information. A definition of $ \text{verb} $ would define the two appropriate features, AGREE and VFORM, and would also define the type of the values of the two features. Let's suppose that the AGREE feature takes values of type $ \text{agr} $ defined in Fig. 16.12 above, and the VFORM feature takes values of type $ \text{vform} $ where $ \text{vform} $ subsumes the seven subtypes $ \text{finite} $, $ \text{infinitive} $, $ \text{gerund} $, $ \text{base} $, $ \text{present-participle} $, $ \text{past-participle} $, and $ \text{passive-participle} $. Thus $ \text{verb} $ would be defined as follows (where the convention is to indicate the type either at the top of the AVM or just to the lower left of the left bracket):

$ \begin{bmatrix} \text{verb} \\ \text{AGREE} & \text{agr} \\ \text{VFORM} & \text{vform} \end{bmatrix} $

By contrast, the type noun might be defined with the AGREE feature, but without the VFORM feature:

$$ \begin{bmatrix} \text{noun} \\ \text{AGREE} & \text{agr} \end{bmatrix} $$

The unification operation is augmented for typed feature structures just by requiring that the types of the two structures unify in addition to the values of the component features unifying.

$$ \begin{aligned}&\begin{bmatrix}verb\\AGREE&1st\\ VFORM&gerund\end{bmatrix}\sqcup\begin{bmatrix}verb\\AGREE&sg\\ VFORM&gerund\end{bmatrix}=\begin{bmatrix}verb\\AGREE&1-sg\\ VFORM&gerund\end{bmatrix}\\ \end{aligned} $$

Complex types are also part of the type hierarchy. Subtypes of complex types inherit all the features of their parents, together with the constraints on their values. Sanfilippo (1993), for example, uses a type hierarchy to encode the hierarchical structure of the lexicon. Fig. 16.13 shows a small part of this hierarchy, the part that models the various subcategories of verbs which take sentential complements; these are divided into the transitive ones (which take direct objects: (ask yourself whether you have become better informed) and the intransitive ones (Monsieur asked whether I wanted to ride). The type trans-comp-cat would introduce the required direct object, constraining it to be of type noun-phrase, while types like sbase-comp-cat would introduce the baseform (bare stem) complement and constrain its vform to be the baseform.