Approximating Maximum-Entropy Ratings for Evidential Parsing and Semantic Interpretation

1 Introduction

It bas been generally accepted for some time that some lin­ guistic constructs can only be properly disambiguated and in­ terpreted by combining lexicosyntactic factors with semantic and conceptual knowledge. A prime example is the nom­ inal compound construction, examples of which are coast road, weekend guest, high-speed bus, and rubber baby buggy bumper. To parse the latter correctly as [rubber [[baby buggy] bumper]] requires lexicosyntactic knowledge of the conven­ tional collocation baby buggy, as well as conceptual knowl­ edge that bumpers are typically constructed of rubber, but not buggies. Moreover, such constraints are not absolute, but soft and defeasible suggesting a numerical treatment (Wu 1990).

*Preparation of this paper was partially supported by the Nat­ ural Sciences and Engineering Research Council of Canada while the author was a postdoctoral fellow at the University of Toronto. Much of this research was done at the Computer Science Division, University of California at Berkeley and was sponsored in part by the Defense Advanced Research Projects Agency (DoD), monitored by the Space and Naval Warfare Systems Command under N0003988-C-0292, the Office of Naval Research under N00014-89-J-3205, the Sloan Foundation under grant 86-10-3, and the National Science Foundation under CDA-8722788.

Probabilistic methods for language interpretation have re­ cently come to the fore, spurred by developments in uncertain reasoning and statistical linguistics. Previous methods for combining these factors relied largely on ad hoc schemes re­ quiring painstaking number tweaking, whereas to realize any hope of scalability, the calculus must be consistent in principle with some statistical sampling process. However, probabilis­ tic methods are computationally expensive in domains with complex dependencies-like natural language--so efficient approximate techniques must be sought.

The following are the objectives behind the proposed method:

1. Integration of syntactic, semantic, and conceptual fac­ tors.
2. Consistent and statistically grounded evidence combina­ tion.
3. Flexible policy on hypothesis and constraint selection.

The latter is the most important feature distinguishing the proposed method from others. It means that the approxi­ mation technique does not impose strong restrictions on the probabilistic event space, with the following rationale. To keep computational expense reasonable, the rating procedure should not employ the full knowledge base, nor consider all possible interpretations. Instead, language analysis should employ various heuristics for hypothesizing good candidate interpretations and for retrieving pertinent constraints from the knowledge base. Thus the rating method should be capa­ ble of handling these arbitrary subpartitions of the hypothesis and constraint space.

The schema of this paper is as follows. The next section discusses related approaches. In section 3 we discuss why maximum-entropy ratings are difficult to obtain for natural language interpretation. Section 4 introduces an approxima­ tion technique to overcome this difficulty. Illustrative exam­ ples are given in section 5, followed by additional discussion in section 6.

2 Related Work

Related probabilistic interpretation methods fall into two main categories with respect to the type of concession made for computational feasibility. On one hand are methods that sac­ rifice the expressiveness of the language in which constraints are represented. On the other band are methods that restrict the precedence ordering of dependencies between constraints.

Methods of the first category employ simple representa­ tion languages that do not permit expressing compositional constraints. Examples of this approach are n-gram models, hidden Markov models, and stochastic context -free grammars. These methods do not yield full conceptual representations, but can be used to rate alternative parses. For example, Fu­ jisaki et at. (1991) rate potential bracketings of nominal com­ pounds using a stochastic CFG. It is also possible to view microfeature-based PDP models that have probabilistic inter­ pretations as members of this category.

Methods of the second category allow compositional con­ straints about roles and fillers to be predicated, but restrict the precedence of such constraints. The members of this group most relevant here (Goldman & Charniak 1990a, 1990b; Cbar­ niak & Goldman 1988, 1989; Burger & Connolly 1992) are based on Bayesian belief networks (Pearl 1988). Difficul­ ties that arise with this group are discussed in a companion paper (Wu 1993a). Briefly, the precedence of dependencies is dictated by the topology of the net, according to the rule that any two nodes are conditionally independent given the instantiated values of all intervening nodes. Although nodes are permitted to express hypotheses about the binding of one variable to another, the state of a binding hypothesis elim­ inates many others. For example, if a role r is bound to some filler, no other hypothesis that binds r can hold. Under the conditional independence rule, either (1) all such interde­ pendent hypotheses must be connected, creating loops which are expensive to evaluate, or (2) they must be clustered into single nodes as compound variables, with equivalent compu­ tational cost. The usual solution is to use a priori knowledge to generate as few binding hypotheses as possible, and to give some binding_ hypotheses precedence over others by appro­ priate choice of instance variables. However, as argued in the rest of this paper, the awkwardness of such a framework may be unnecessary.

3 Why the "Correct" Solution is Hard

Before proceeding to describe .the proposed method, let us consider what it is about the natural language domain that makes getting the theoretically "correct" maximum-entropy solution different from other domains where statistical and uncertain reasoning techniques have proven so apt. (Maxi­ mum entropy (Jaynes 1979) is a principle for assigning prob­ abilities to a partially constrained distribution without adding information.) First we ask what forms of information are needed to interpret nominal compounds, taking coast road as an example. 1 We conducted an informal survey that yielded as the most common interpretation a road in or along the coastal area. We also found that longtime residents of California automatically concretized this to Highway 1. Another inter­ pretation that was volunteered, though less preferred, was a road amenable to coasting. In addition, all informants agreed that in a context like Since the earthquake damaged the only Interstate to the coast, old Highway 17 will temporarily serve as the main coast road, the interpretation of a road leading to the coast would be perfectly natural. To account for these pref­ erences, some of the types of knowledge constraints needed are:

1 From the Brown corpus (Kucera & Francis 1967). For more discussion of nominal compounds, see Wu (1990) and the linguistics literature (e.g., Lees 1963, 1970; Downing 1977; Levi 1978; Warren 1978; McDonald 1982; Leonard 1984).

1. Specific conceptual schemas: The Highway 1 concept is a specialization of coastal road that is often used when residing on the West Coast. 2
2. Intermediate conceptual schemas: Usually when think­ ing about roads in the context of seacoasts, one thinks specifically of roads running along the coast (the subcat­ egory we abbreviate as coastal road).
3. Semantic schemas: In our example we have a one-dimensional entity road and an elongated two­ dimensional space coast . Prototypical abstract spatial relationships for this combination include aligned con­ tainment and linear order locative (i.e., destination).
4. Specific constructions: 3 By convention, the noun coast means a seacoast substantially more frequently than an unpowered movement.
5. Intermediate constructions: The construction coast N re­ lates to a seacoast more often than unpowered movement, as in coast artillery, coast guard, coastland, coastline, and coast redwood. (In contrast, coaster tends to desig­ nate unpowered movement, as in coaster wagon, coaster brake, and roller coaster.)
6. Abstract constructions: Nominal compounds frequently express containment relationships, and somewhat less frequently, linear order locative relationships.

These factors involve a mix of feature constraints and role binding constraints and are conveniently notated using con­ ventional frames or feature-structures, as shown in figures 1 (a) and (b). (Details of our representation and ontology are given in Wu (1992, 1993b.) To see why role bindings make maximum-entropy estimation difficult, we may compare the structure of concept spaces with and without binding. In both cases, there is an implicit abstraction hierarchy governing the set of all tokens in the concept space. This can be made ex­ plicit by the device of abstractive relations. Without bindings, as in the simple binary feature example of figure 2(a), abstrac­ tive relations such as A and B indicate that the tokens 001 and 011 share a common abstract ancestral type Ox 1. (Note the distinction between the token 001 and its parent type 00 1.) Here any input evidence about a particular feature's value, say that the leftmost bit is 1, corresponds to conditioning by an internal node such as 1xx. Marginal probabilities on internal nodes may or may not be known; for example we might have P(Oxx) = 0.6 and P(1xx) = 0.4. The maximum-entropy distribution over the set of tokens { q1 , ... , qc } is computed by maximizing

2 We use coastal road to designate a conceptual category, as op­ posed to the novel lexical construct "coast road".

3 In the philosophy of Fillmore's (1988) Construction Grammar, a construction is a lexicosyntactic pattern paired with the seman­ tic/conceptual representation it signifies (de Saussure 1966). Cone structions come at various levels of specificity and an inheritance hierarchy is a convenient storage technique; see Wu (1992).

ABBRV: C:coast:seacoast l

subject to the marginal constraints, where P; ~r P(q;)­ When the implicit abstraction hierarchy is a regular lat­ tice such as this, it is easy to predicate conditional inde­ pendence relationships between features that are deemed to be uncorrelated given the value of other chosen features, by omitting all information at a particular depth, say for P(OOO), P(OOl), ... , P(lll). This means certain marginal distributions are mutually orthogonal, and in this special case the maximum-entropy distribution can be computed sim­ ply by multiplying marginal probabilities. For example, if the only other things we know are P(OxO) # P(lxO) and P(OOx) # P(lOx), then the middle and rightmost features are conditionally independent given the value of the leftmost feature, so P(OOO) = P(OxO)P(OOx ). In effect, efficient methods for probabilistic uncertain reasoning such as belief networks take advantage of this underlying assumption about the concept space.

Now consider the case with role bindings. In the abstraction hierarchy we must provide for specialization of the features that describe role types, in addition to specialization of con­ cept features as in the no-bindings case. Moreover, we must allow for the commonality between feature-structures with two roles that are either bound or not, as performed in fig­ ure 2(b) by abstractive relations C and D. (For perspicuity feature-structures are depicted using directed graph notation.) The resulting abstraction hierarchy is a semilattice because any two feature-structure nodes have a unique least upper bound, but not necessarily a unique greatest lower bound. As before, the input evidence corresponds to conditioning on an internal type, having a form such as figure l(c) which says the input phrase is coast road. Also, we may know marginal probabilities on some internal types, and the joint distribution is obtained by maximizing entropy. However, the distortion introduced into the abstraction lattice by the role bindings rules out orthogonal marginal distributions, except for extreme coincidences; there is no longer a single depth at which all information can be omitted to yield conditional independence. Thus we can no longer exploit conditional in­ dependence assumptions to make evaluation efficient. To the best of our knowledge, the application of maximum entropy in its general form (other than conditional independence) to this type of compositional "binding-distorted" semilattice has not previously been suggested.

4 An Approximate Maximum-Entropy Technique

In section 2 we discussed two approaches that have been taken to feasible approximation. We propose a third approach, which is to relax the requirement of getting a strict condi­ tional distribution. This proceeds from the assumption that language, though ambiguous, contains sufficiently many dis­ criminating cues so that getting precise probabilistic ratings is computational overkill. Rather, it suffices to (1) gener­ ate hypothesized interpretations heuristically, (2) retrieve po­ tentially relevant constraints from the knowledge base, and (3) compute an approximation to the conditional distribution (the first two steps can be done by a chart parser, marker passing, and/or other standard methods). The method pre­ sented here approaches the theoretical probabilistic solution as more hypotheses and constraints are given to it, but also becomes too expensive then. However, the method is quite practical given a reasonable number of heuristically generated hypotheses and constraints.

The essence of the method, called AME for Approximate Maximum Entropy, is to concentrate on rating only the hy­ potheses, and no other tokens; in contrast full-fledged max­ imum entropy assigns probabilities to all tokens. The ap­ proximation is accomplished by discarding the details of the abstraction lattice (or event space) outside the immediate hy­ pothesis space. Instead, a minimum number of "dummy" to­ kens (or events) are introduced to cover the space, one for each marginal constraint. Each dummy event represents all the to­ kens that are consistent with the corresponding constraint, but not with the conditional space (the space subsumed by the input conditioning event type). In addition, a single null dummy event represents all remaining events. Dummy events are treated as tokens, even though each one takes the place of many real tokens. The standard maximum-entropy criterion is then applied to the new coarse space comprising the dummy tokens together with the hypothesis tokens. This problem is feasible since the space is much smaller; the only detailed structure lies within the hypothesis space. Discrepancies in the approximation arise from the fact that dummy events are treated as if they are disjoint, although in fact they represent event subspaces that may overlap.

More formally, suppose Q is the set of token f-structures and 9 is the set of type f-structures, and :F ~f 9 U Q. Let1i = {ht , ··· ,h;, .. . ,hn} c Q be the candidate out­ put structures produced by the hypothesis generator, and let M = { m 1, ... , mi, . .. , mM} C 9 be the pertinent abstract classes with associated marginal probabilities Pmi = P(mi) from the constraint generator. Denote by c the partial or­ dering induced on 1i u M by the subsumption semilattice on f-structure space.

We defineD= { d1 , ... , di, .. . , dM} as thesetofdummy · def events. Let :F = 1i U M u V be the approximate event space, and let if. d,g 1i U V be the approximate hypoth~sis space. Define the approximate ordering relation[: over :F as follows:

Let Pmi be the marginal. probability constraints on :F and use Pmi as estimators for Pmi.

Then we wish to assign Ph, and Pd, such that

while maximizing the entropy

subject to the marginal constraints

which can be solved by an iterative method given in the com­ panion paper (Wu 1993a).

This formulation has several advantages over a number of other probabilistic approaches including belief nets. First, it eliminates explicit features (or hypothesis nodes) for variable bindings. Instead, the similarity between feature-structures with similar binding patterns is expressed implicitly in the subsumption lattice. Thus the framework does not promote questionable precedence ordering judgements for binding hy­ potheses.

Second, the method robustly accepts arbitrary subsets of hypotheses and marginal probabilities, and does not require strictly consistent conditional probabilities. Aside from re­ ducing the event space to a feasible size, dummy events serve a second purpose: they guarantee consistency of the marginal probabilities even when an "improper" subset of marginal constraints has been retrieved from the knowledge base. An example of this will be noted in the next section.

5 Examples

A better feel for the behavior of AME can be had from the following exercise. Figure 3(a) shows a simple example where the two dummy events are incorrectly related. Since coast and coastal road is subsumed by road, every token of the former type should be counted in the marginal probability for road as well, as shown in figure 3(b). The probabilities, shown both as joint and conditional (parenthesized) distributions, change substantially with proper subsumption.

It is also important to include the most specific applica­ ble marginal constraints available from the knowledge base. The strong preference for road leading to coastal area in fig­ ure 3(b) arises because the hypothesis is left "floating" with no other marginal to constrain its probability. Another large correction occurs in figure 3(c) when a specific marginal on coast and road is included, which restricts the total amount of probability assignable to the hypotheses. This causes much of the probability weight to be shifted to the dummy events and switches the preferred hypotheses. Another simple example of this phenomenon is shown in figure 4 demonstrating the sensitivity of the coasting road hypothesis (a road amenable to coasting) to the presence of a constraining marginal on coasting accomplishment (coast in the unpowered movement sense).

Now consider again the range of knowledge needed to in­ terpret coast road. We suppose that the subset of constraints and hypotheses deemed pertinent are as shown in figure 5. The constraints correspond to the types of knowledge con­ straints enumerated in section 3. Knowledge constraint 1 is encoded by the relative magnitudes of ?(coastal road) and ?(Highway 1). Similarly, constraint 2 is encoded by P(coast and road) and P(coast and coastal road); con­ straint 4 is encoded by P(L:coast), P( C:coast:seacoast), and P( C:coast:coasting accomplishment); and constraint 6 is encoded by P(C:NN:linearorder locative) and P( C:NN:containment), which says that a noun-noun con­ struction is used to signify containment twice as often as linear order locatives. Constraints 3 and 5, as well as other in­ termediate lexicosyntactic signification patterns, are omitted for the sake of brevity.

In the basic case, AME yields the conditional distribution shown in the uppermost row labelled "0:". The hypotheses road in coastal area and road along coastline are the winners with the highest probability, as might be expected. (The probabilities for these two hypotheses will always be the same here as we have omitted their distinguishing features.)

The next run is labelled "1:". Suppose constraint4 weren't true, and "coast" were actually used more often to mean unpowered movement than a seacoast. To model this, the marginals on "coast" signifying seacoast and coasting ac­ complishment are switched as shown by the alternate mar­ ginals labelled "1:". In the resulting conditional distribution, coasting road now dominates the hypotheses.

The marginals labelled "2:" model another alternate case where constraint 6 is reversed such that noun-noun construc­ tions signify linear order locatives more often than contain­ ment. In this case the preferred interpretation switches to road leading to coastal area.

In "3:" we relax constraint 2 so that one does not think specifically of roads running along the seacoast quite as frequently (when thinking about roads in the context of sea­ coasts). Again, the result is that the preferred interpretation switches to road leading to coastal area.

Lastly, in "4:" we model constraint 1 for West Coast resi­ dents by increasing the magnitude of the ?(Highway 1) mar­ ginal, resulting in a corresponding change in the dominating hypotheses. All examples were computed using a C imple­ mentation of AME.

The preceding section mentioned that dummy events also serve to guarantee consistency of marginal probabilities. When only a subpartition of the knowledge base is consid­ ered, the marginals may be inconsistent due to the omission of some of the probability weight. For instance, in figure 5,

P(coast and coastal road)+ ?(Highway 1) < ?(coastal road)

when they should be equal. The dummy events provide nonzero subspaces to absorb the remaining probability for coastal road that goes to other subcategories that have been neglected in the approximation.

6 Discussion

In practice it will be difficult to obtain the marginal probabil­ ities on many frames. However, note that our guiding principie is that the method accepts whatever statistics are available and improves upon the interpreter's discrimatory power to the extent possible. Pragmatic, if theoretically unsatisfactory, probability estimation methods may well suffice for interim applications. Lexical frequency counts over the Brown corpus and others are available (Francis & Kucera 1982) and parsed corpora will soon facilitate frequency counts for syntactic pat­ terns as well. These counts may be used as estimators for the marginals of lexicosyntactic structures. The analogous proce­ dure is impractical for semantic or conceptual structures, since fully interpreted corpora are not available. Warren (1978) gives frequency counts on manually-analyzed, coarse seman­ tic relation categories in her study of nominal compounds, but these must be massaged to fit more realistic AI ontologies.

Another potential use of large-corpora techniques has been suggested by Hearst (1991), who proposes an automated method for "coarse" disambiguation of noun homographs that could be used as a front-end hypothesis generator. Such a method, based on orthographic, lexical, and syntactic cues near the noun, may improve the relevance and accuracy rate of hypotheses.

Performance will depend to a large degree on which frames the investigator chooses to place marginal constraints on; this model is as susceptible to the ontology problem as any other.

In effect, the investigator decides the degree of generalization, because what maximum entropy does is to generalize the par­ tial distributional constraints in the knowledge base to the rest of the event space. Choosing the frames is a kind of concept formation, which this work does not aim to address, although toward this direction Wu (1991) proposes a discrete kernel estimation model of generalization from samples. Choosing a set of marginal constraints can then be seen as a matter of best fit to the theoretical kernel distribution.

Finally, it is worth noting that although we developed AME specifically to address our language interpretation problem, we believe the method is of sufficient generality as to find applications in other uncertain domains where the constraints are highly interconnected.

7 Conclusion

The high degree of interconnectedness between lexicosyn­ tactic, semantic, and conceptual factors in natural language interpretation suggests quantitative integration of constraints. Evaluating hypotheses on a probabilistic basis rather than an ad hoc weighting scheme yields a model that will more plau­ sibly scale up to interestingly large domains. The proposed technique has several advantages compared with other proba­ bilistic methods. First, it evaluates structured hypotheses sub­ ject to compositional constraints, without additional binding precedence assumptions. It is also robust and highly flexible in that arbitrary heuristically-generated subsets of hypothe­ ses and constraints are accepted. These two properties make the method straightforward to incorporate as a filtering/rating stage within existing theories and architectures.

Acknowledgements

I am indebted to Robert Wilensky, Jerome Feldman, and the members of the BAIR and La groups for many valuable dis­ cussions, as well as Graeme Hirst, Geoff Hinton, and their respective groups.