Interpretation as Exception Minimization

1 Introduction

Ambiguity is a notorious problem for Natural Language Pro­ cessing (NLP). Schmitz and Quantz have shown that the same general strategy can be used for the resolution of referen­ tial, lexical, and structural ambiguities [Schmitz and Quantz, 93]. The basic idea is that contextual information is used tore­ solve the local ambiguities (see also [Kameyama et al, 91] and [Eberle et al, 92]). In most cases, this information cannot be formalized as hard constraints but only as defaults, i.e. as rules which allow for exceptions. Each possible interpretation of an ambiguous expression satisfies some of the defaults while violating others. The idea of interpretation as exception min­ imization is to choose the interpretation which contains the fewest exceptions according to a relevance ordering on the defaults.

A fundamental assumption of this approach towards disam­ biguation is that contextual information of quite heterogenous nature, such as syntactic, semantic, conceptual, or domain specific information is used in the disambiguation process. Consequently, the strictly sequential architecture of interpre­ tation used in most existing NL systems, e.g. [AIIgayer et al.,

89], [Stock, 91], [Schmitz et al, 91], in which syntactic, se­ mantic, and conceptual information is represented on different levels and in different formalisms, seems to be inadequate.

I see Head-Driven Phrase Structure Grammar (HPSG) as an attempt to provide a homogenous formalism for integrating syntactic and semantic information [Pollard and Sag, 87] . In this paper I try to combine the ideas of HPSG and Terminolog­ ical Logics (TL), which are widely used in NL systems for the representation of conceptual and domain specific knowledge (e.g., the systems cited above and [Bateman, 92]). The aim of this paper is twofold:

• I will show how the syntactic principles of HPSG can be represented in TL;
• I will show how interpretation can be achieved by min­ imizing the exceptions to contextual defaults and how this can be formalized in terms of TL entailment.

This paper is a formal elaboration of the technical aspects sketched in [Schmitz and Quantz, 93]. I will therefore reduce the linguistic motivation to a minimum and refer the inter­ ested reader to the examples presented in that paper. I will also contend myself with a very superficial treatment of HPSG and rather aim at presenting the general formal structure of interpretation as exception minimization in a iL framework. Of course, the general idea of exception minimization could be combined with other formalisms as well.

One final remark: the task of interpretation or disambigua­ tion can be seen as a special case of model-based diagnosis, where the phonological realization is the observed symptom, the grammar and the conceptual knowledge are the under­ lying model, and the chosen interpretation is the diagnosis. The approach of interpretation as exception minimization is therefore of relevance not only for NLP but for diagnosis tasks in general.

2 Terminological Logics and Typed Feature Structures

The similarity between Terminological Logics (TL) and Typed Feature Structures (TFs), which provide the formal paradigm of Unification Grammars as HPSG, has been mentioned in a number of papers (e.g., [Nebel and Smolka, 87], [Backofen et al, 90], and [Carpenter, 92]). The basic constructs of TFS are feature structures, i.e. sets of feature value pairs, where features are partial functions from feature structures into val­ ues. The corresponding entities in TL are concepts. Like feature structures, concepts can be seen as sets of role value pairs with the difference that roles are partial relations and not necessarily functions. Both formalisms allow (limited) forms of disjunction or negation in addition to conjunction.

Note that in 11.. there is a strict distinction between types and instances, i.e., between concepts and objects. Consequently, there are two kinds of formulae in n.: c, ~ c2 means that the concept c1 is subsumed by c2 (i.e., c1 is more specific than c2); o :: c means that the object o is an instance of c. The feature formalisms, on the other hand, do not make this distinction. In a sense, they lack the level of objects and only comprise types. Thus, the fillers of features are not objects, but feature structures, i.e. types. Instead of distinguishing between objects and types they distinguish between atomic and complex types: atomic types are values like sing or ace, whereas complex types have an internal structure like per:3 etc. Note that there is no strict correspondance between atomic values and 11.. objects. Though each atomic value can be encoded as a 11.. object, the converse is not true. 11.. objects are structured because they can be described by structured concepts.

As a consequence of this difference between TL and TFS, we need to introduce additional TL objects to encode complex feature structures. Thus the feature structure in (1) will be encoded by the 11.. formulae in (2).

(1) [f, [h v]]

Thus we explicitly introduce names for the objects which are described by the feature structures (and by the internally nested feature structures).

The following syntax contains only the TL operators used in this paper. For a formal description of the language imple­ mented in the 11.. system BACK see [Hoppe eta/, 93], which also contains illustrating examples for domain modeling with 11.. Note the following notational conventions: t stands for terms in general, i.e. for concepts or roles; en and r n stand for atomic names.

For this language a modeltheoretic semantics can be given where a model M of a setofTL-formulae 1 is a pair (D, [·f). [·f maps concepts into subsets of D, roles into subsets of D x D, and objects injectively into D, in accordance with the following equations (I user( d) to denote { e : (d, e) E ,. } ):

Note that features are treated as special roles: whereas roles in general are interpreted as partial relations, features are interpreted as partial functions.

Satisfaction of formulae is then defined as follows:

A structure M is a model of a formula 1 iff M F= 1; it is a model of a set of formulae 1 iff it is a model of every formula in 1. A formula 1 is entailed by a set of formulae 1 (written 1 F= 1) iff every structure which is a model of 1 is also a model or,.

Note that the following abbreviations are frequently used in this paper:

In addition to this core TL, I assume in this paper the integra­ tion of test! compute facilities, of epistemic operators, and of defaults. I will need these constructs for the modeling of the grammar, for the definition of explicit interpretations, and for the specification of preferences guiding the disambiguation. I will briefly sketch the basic ideas of these extensions but refer the interested reader to the literature for more detailed infor­ mation. I will not address the issue of decidability or tractabil­ ity for the resulting 11... Even without these extensions, the core TL needed for representing linguistic information is prob­ ably undecidable (see [Donini eta/, 91] for complexity results ofn.).

The test/compute construct allows the attachement of ex­ ternal procedures into a 11.. system. The formal integra­ tion of the compute construct into the 11.. system BACK is described in [KortUm, 93]. The basic idea is that compute(r,pred(arg,, ... ,argn)) can be used to determine the role-filler(s) for a role r by calling the external predicate pred with the arguments arg;. These arguments will typically be the values of other roles.

The integration of epistemic operators into 11.. has been proposed in [Donini eta/, 92] . The K operator can be used to distinguish cases in which an object is known to be a filler for role r, from cases in which just the type of the role-filler is known. Thus 1 r describes all objects which are known to have exactly one filler for r, but I Kr describes only those objects for which this filler is explicitly known.

Finally, I need a default extension ofn. as the one developed in [Quantz and Royer, 92] . The idea is to model defaults as rules c, "-> c2 that allow for exceptions. Each object which is a c1 is assumed to be a c2 unless this leads to inconsistencies. A priority ordering on defaults stemming from the specificity of the premises wrt the subsumption hierarchy is used to resolve conflicts between defaults.

Given such a TL I will now show how interpretation can be defined formally in terms of 11.. entailment, how syntactic principles from HPSG can be modeled as 11.. formulae, and how defaults can be used to guide disambiguation by realizing interpretation as exception minimization . .

3 Interpretation and Disambiguation

Consider the following example taken from [Schmitz and Quantz, 93]:

1. Die Hersteller produzieren Schaltkreise.
2. (The manufacturers produce integrated circuits.)
3. e :: phon:"Die Hersteller produzieren Schaltkreise" n phrase n 4 atom n atom: (w1 n w2 n WJ n W4)

w1 :: word n pos:1 n phon:"Die" w2 :: word n pos:2 n phon:"Hersteller" w3 : : word n pos:3 n phon:"produzieren" w4 : : word n pos:4 n phon:"Schaltkreise"

I see (5) as representing the information explicitly given by sentence (3). Since it contains mainly phonological informa­ tion I use ne to denote this set of n. formulae.

The task of interpretation consists in computing the infor­ mation implicitly given in (5). Let us assume that another set ofn. formulae r contains grammatical information (examples will be given in the next section). The deductive approach to interpretation (see [Pereira and Warren, 80]) can then be for­ malized as follows: 1

Definition 1 Let e be any NL expression. If r U lle is in­ consistent, e has no interpretation. Otherwise, the deductive interpretation of e is defined as the rrwst specific concept id such that r u ne I= e :: id.

Due to the (semi-)free word order of German, both Schaltkreise and Die Hersteller can be the subject of sen­ tence (3) (thus the English sentence (4) is the translation of the preferred interpretation in which Die Hersteller is subject). Given an adequate formalization of German grammar as r we obtain the following deductive interpretation

where P1 is the phrase Die Hersteller and PJ is the phrase Schaltkreise.

I do not think that this matches our intuition, how­ ever: I'd rather say that e has two interpretations and that subject: (p1 u p3) is too unspecific to count as an intepretation. It thus seems that further restrictions on interpretations are re­ quired. The general idea is that the values of certain features have to be determined and that disjunctive information about them is not enough.

This can be formalized by using epistemic operators as proposed in [Donini et al, 92]. The requirement that a value for a feature f must be known is expressible as the concept 1 Kf. We say that this concept is explicit wrt f and give the following general definition of explicitness.

Definition 2 A concept c is explicit wrt a role r and a set of n.- formulae r ifJT I= c!;;;; K~ n r only ijr I= c!;;;; ~ n Kr. A concept c is explicit wrt a set of roles p iff it is explicit wrt each role in p.

Note that explicitness is a relative notion which is only mean­ ingful wrt a given set of roles. But this is exactly what is needed for a variable depth of analysis. We can stipulate that an interpretation has to be explicit wrt a set of relevant roles.

1 In all the definitions in this paper I assume that r is a set of 1L formulae modeling the grammar, that ne is a set of 1L formulae modeling the phonological realization of an NL expression e, and that~ is a set of 1L defaults.

Thus, the depth of analysis can be controled via the set of relevant roles. 2

Given the notion of explicitness we can formalize an ab­ ductive approach to interpretation (see [Hobbs et al, 93]). In general, abduction is the inference of a formula A from the formulae A -+ Band B. To give an intuition for this infer­ ence, which clearly is not deductively v~id, consider B an observed fact and A an explanation for B given that A --+ B.

Definition 3 Let e be any NL expression and p a set of roles relevant for interpretation. If r u ne is inconsistent. e has no interpretation. Otherwise, the abductive interpretations of e are the least specific concepts ia. explicit wrt p, such that r u { e :: ia} is consistent and r u { e :: ia} I= ne.

Note that the requirements of generality and explicitness con­ trol the depth of analysis: on the one hand, an abductive interpretation must be specific enought to be explicit wrt a set of relevant roles; on the other hand, it is only as specific as necessary to explain the phonological information, i.e. as general as possible.

Note further that in cases of ambiguity, we obtain several abductive interpretations and the task of disambiguation con· sists in determining the preferred one. I will address this issue in Section 5.

4 Linguistic Information and Ambiguity

Having sketched the general framework of interpretation, I will now turn my attention towards the formalization of HPSG principles as 1L formulae. In HPSG two types of signs, namely words and phrases are distinguished. In the lexicon, feature structures are assigned to the words of a language. Lexical rules can be used to model the general principles underlying the lexical inventory of a language. First, the wordforms of a Iexeme have a lot of information in common and only some information is specific to the single wordforms. Second, there are general rules governing the derivation of wordforms from the stem of a lexeme. These general rules allow for exceptions, however, which are known as irregular forms (see [Krieger and Nerbonne, 91]). ·

Lexical information can be used to illustrate the differ­ ence between the deductive and the abductive approach to · interpretation. In the previous section I took the phonological information associated with an expression as the starting point for interpretation. Thus given the information e :: phon:"is' we would like to infer e :: v n per:3 n plu:- n lexeme:be. To get this inference in the the deductive framework, we would need rules like

phon:"is" -+ lexeme:be n per:3 n plu:- lexeme:be -+ v n stem:"be"

This representation has two disadvantages, however: for one thing it does not capture the general derivation rules; further­ more, for ambiguous wordforms we have to model disjunctive information in the righthand side of the rules.

It seems more natural to choose a representation like the following:

2 1 would like to thank Christa Hauenschild for pointing out to me the importance of a variable depth of analysis for Machine Transla­ tion. The basic idea is that ambiguous expressions do not have to be disambiguated if the same ambiguity is expressible in the target language.

lexeme:give v n per:3 n plu:- lexeme:be n per:3 n plu:- -+ v n stem:"give" n ... '"'-'"' compute(phon concat(lexeme.stem,"s")) -+ phon:"is"

Such a modeling yields the desired inferences within the ab­ ductive approach. Thus e :: phon:"is" can be explained by assuming that e :: lexeme:be n per:3 n plu:-.

Note that in HPSG this modeling is used with a deductive approach together with a closure of grammatical information. Thus, for example, the lexemes mentioned in the lexicon are taken to be alllexemes of the language:

word -+ lexeme:h u ... u lexeme:ln

I think that this approach is not cognitively adequate, since it does not allow the interpretation of wordforms for which no lexeme exists in the lexicon. But clearly, human speakers are able to interpret expressions containing such forms and usually form a hypothesis what the stem of the 'missing' lexeme would be like.

For the purpose of this paper it suffices to see a general equivalence between the deductive and the abductive ap­ proach: the abductive approach can be simulated deductively by adding the closure

C -+ C1 U ... U Cn for a list of rules

In the remainder of this section I will present some of the syn­ tactic principles of HPSG and show how they can be modeled inn..

Whereas words form the atomic elements of a natural lan­ guage- at least with respect to the task of interpretation­ phrases are complex entities arising from the combination of signs. In addition to the lexicon, a grammar has thus to specify the principles underlying this combination. In HPSG there are a number of such principles, in this paper I will concentrate on the most important ones only. In general, these principles constrain the set of valid feature structure, i.e., they filter out some feature structures as ill-formed.

The internal structure of a phrase is represented in HPSG by the daughters ( dtrs) feature, which further divides into the features head-dtr and comp-dtrs. Representing this in TL I will model dtrs as a role with a sub-feature head-dtr and a sub-role comp-dtrs.

The head-dtr is assigned special treatment for two reasons. First, some feature values of the head-dtr determine the cor­ responding feature values of the overall phrase. This is the content of the Head Feature Principle (HFP), which can be formalized as follows:

phrase -+ plu=head-dtr.plu n cas=head-dtr.cas n ...

The features constrained in the HFP are usually called head features.

Second, the head-dtr acts like a functor in that it takes the comp-dtrs as arguments to produce the overall phrase. This perspective, which owes a lot to the ideas underlying Cate­ gorial Grammar, is reflected in the subcat feature in which number and types of the arguments of a functor are speci­ fied. I will model subcat as a TI.-role with sub-features arg1, ... , arg4. Thus, the following lexicon entry expresses that produzieren expects two arguments, one being in nominative case, the other in accusative:

lexeme:produzieren -+ 2 subcat n the(arg1 ,np n cas:nom) n the(arg2,np n cas:acc)

The functional application is controlled by the Subcategoriza­ tion Principle (SP), which basically requires that the subcat value of a phrase contains those arguments of head-dtr, which are not members of comp-dtrs:

phrase -+ compute(subcat, subtract(head-dtr.subcat,comp-dtrs))

Whereas HFP and SP express general constraints on the combi­ nation of signs, Immediate Dominance (ID) Schemata are used to single out those combinations that actually are phrases of a language. The ID Principle states that each phrase must be an instance of one of the ID Schemata. We thus get:

phrase -+ id1 u id2 id1 phrase n 0 subcat n the(head-dtr,lex:-) n 1 comp-dtrs id2 phrase n 1 subcat n the(head-dtr,lex:+)

The purpose of this section was to show that the syntactic information modeled in HPSG can be in principle represented in TL. I will give no examples for tile modeling of semantic, conceptual, or encyclopedic information in n., since this has been already exemplified in a number of existing systems, e.g. [Allgayer et al. , 89], [Stock, 91], [Schmitz et al, 91], [Bateman, 92]. In the following I will therefore assume that r contains information of quite heterogeneous nature mod­ eled homogeneously as TL formulae. It remains to be shown how defaults can be integrated into the formal framework of interpretation presented so far.

5 Disambiguation as Exception Minimization

The abductive approach to interpretation can be refined to handle ambiguities. Note that multiple abductions result from the existence of several explanations, i.e. formulae Ai -+ B. The idea of weighted abduction, as proposed in [Hobbs et al, 93] , is to assign costs and factors to the Ai. Then the preferred abduction is the cheapest one, i.e. the one containing the least expensive explanations.

Instead of pursuing the approach of weighted abduction, however, I will use defaults to model preferences between interpretations. The main reason for doing so is that the approach of weighted abduction cannot deal with the de­ fault information we need in order to model the contextual constraints. 3

In [Schmitz and Quantz, 93] it is explained in detail how defaults can be seen as a means to model preference rule systems as proposed in [Jackendoff, 83]. Thus the default c,

3 Hobbs pointed out to me, however, that their "etcetera" predi­ cations can be used to model uncertain information.

...__.. c2 says that a situation in which a Ct is also a c2 is more likely (and hence a preferred interpretation) than a situation in which it is not a c2.

Quantz and Royer have developed a default extension for TL in which a priority ordering between defaults can be specified [Quantz and Royer, 92]. The basic idea of their preference semantics is to prefer models with fewer exceptions. If two defaults are in conflict and stand in a priority relation, then the exception to the less prior default is tolerated.

Consider again the examples from [Schmitz and Quantz, 93] :

1. Die Harstallar produziaran Schaltkreisa.
2. Schaltkreisa produzieran die Harstallar.

We might introduce two defaults to deal with the ambiguity of these examples:

8,: top:+

...__.. cas:nom

82: lexama:produce ...__.. the(agent,company)

The first default says that a topicalized expression is usually nominative, i.e. the unmarked word order in German is the one where the subject is topicalized. The second default says that the filler of the agent role for the lexeme produce is usually a company, i.e. it specifies a selection restriction. In exam­ ple (6) the interpretation in which Die Herstallar is subject satisfies both defaults, whereas in example (7) it violates the first one. This might be taken as evidence for assigning 62 more relevance than 6t .

As shown in [Schmitz et at, 91] and [Schmitz and Quantz, 93] most interpretations will generally violate more than one default. In order to choose between such interpretations, we thus need a priority ordering not only between single defaults but rather between sets of defaults. Following [Quantz and Royer, 92] we can define the exceptions to defaults in a model Mas:

i.e. as pairs of defaults and domain elements which are mem­ bers of their premise (8p) but not of their conclusion (8c). Let us now assign a natural number p6 to each default represent­ ing the price of violating it: the more relevant a default, the higher its price. Given these prices we can redefine exception preference [Quantz and Royer, 92, Def. 5] as follows:

Definition 4 Let r be any set ofTL1ormulae, Mt and M2 any models of r, and ~ any set of defaults. M2 is exception­ preferred to Mt wrt rand~ (written Mt CE M2) ijf"f.(E t) > "f.(E2) . where "f.(E;) is the result of summing up the prices of the defaults in E;. (Note that the price of a default has to be added for each occurrence in E;, i.e., if (8, d) E E; and (6, e) E E; the price of 8 will be added twice.)

Having thus modified exception preference, we obtain a ~­ entailment (r f=6 o :: c, see [Quantz and Royer, 92, Def. 8]), which takes into account a relevance ordering between mul­ tisets of defaults. Based on this ~-entailment we can define preferred deductive interpretations:

Definition 5 Let a be any NL expression. If r U fle is in­ consistent, e has no interpretation. Otherwise, the preferred deductive interpretation of e is defined as the most specific concept ip such that r U fla F6 a :: ip.

Thus given the two defaults above together with P6, < P6 2 and a formalization of German grammar we would obtain

where e6 is example (6), a7 example (7), p, the phrase Die Herstallar in example (6), and P3 the phrase die harsteller in example (7).

Of course, preferred deductive interpretations suffer from the same shortcomings as deductive interpretations in general: though defaults will resolve most ambiguities, some expres­ sions might be ambiguous even when defaults are taken into account. Thus we might obtain a preferred deductive inter· pretation which is disjunctive and not explicit wrt a relevant role. But even worse, the depth of analysis is not variable in the deductive framework and we will therefore perform disambiguations which might not be necessary. In order to overcome these shortcomings I will now integrate defaults into the abductive approach to interpretation.

In order to take contextual defaults into account we have to redefine abductive interpretations:

Definition 6 Let a be any NL expression and p a set of roles relevant for interpretation. If r U fla is inconsistent, a has no interpretation. Otherwise, the abductive interpretations of e are the least specific concepts ia, explicit wrt p, such that r u {a :: ia} is consistent and r u {a :: ia} F6 na .

For ambiguous expressions we nevertheless obtain several abductive interpretations. In order to choose between them we need to compare them with respect to the defaults they violate. I thus define

Note that these are not exceptions relative to a model, but rather exceptions induced by a set of TL formulae r. Hence, the second elements of the exception pairs are objects and not the entities of the domain D of a model.

Definition 7 Let it and i2 be abductive interpretations of an NL expression e. it is preferred to i2 (written i2 C it) ijf"f.(Et) > "f.(E2) (seeDefinition4), where E; ~ E(fU {a :: i;}.~).

An abductive interpretation it of a is preferred iff there is no abductive interpretation i2 of e such that it C i2.

Note that expressions which are ambiguous even when taking into account default information have more than one preferred abductive interpretation. Furthermore, since abductive inter­ pretations have to be explicit only for a speciti"ed set of relevant roles, we obtain a variable depth of analysis.

6 Conclusion

I have shown that Terminological Logics (TL) can be used to model grammatical as well as conceptual knowledge in a ho­ mogeneous manner. Furthermore, I have presented a deduc­ tive and an abductive formalization of interpretation in terms of TL entailment. In case of ambiguous expressions, contex­ tual constraints modeled as defaults can be used to determine the preferred interpretation. The basic idea is to choose the interpretation yielding a set of exceptions to defaults which is minimal wrt a relevance ordering on the defaults.

To formalize this, I slightly modified the default extension of TL as proposed in [Quantz and Royer, 92]. Instead of a precedence relation between defaults, a precedence relation between multisets of defaults is needed. Moreover, epistemic operators can be used to define the notion of interpretations being explicit wrt a given set of roles. This set of relevant roles can be used to control the granularity of interpretation and thus provides the basis for a variable depth of analysis. The resulting approach to interpretation is very similar to the approach of weighted abduction described in [Hobbs et al, 93] . A detailed evaluation of both approaches is needed to compare their respective advantages and disadvantages.

I see the logical framework presented here as a formal foun­ dation for developing NL systems. To obtain efficient perfor­ mance, however, heuristics have to be integrated to choose the preferred interpretation. Thus instead of evaluating all possi­ ble interpretations by comparing the exceptions they induce, heuristics are needed to test as few interpretation as possible. This should probably be done outside the TL system. Related to this issue is the general topic of integrating abductive rea­ soning into TL. There is currently some research aiming at this integration for configuration tasks [Buchheit eta/, 93].

Another issue concerns the representation of ambiguous information. Variable depth of analysis means that not all ambiguities have to be resolved but only the ones relevant for the specific purpose of interpretation (e.g., to select the appropriate transfer rules in Machine Translation). Thus an efficient representation of ambiguities is needed to avoid ex­ ponential computation of disjunctive normal forms. This topic is currently discussed in the literature on feature formalisms [Kasper, 87], [Trost and Backofen, 92].

Acknowledgements

I would like to thank Bob Carpenter, Christa Hauenschild, Jerry Hobbs, Bob Kasper, Werner Null, Susanne PreuB, Birte Schmitz, and Carla Umbach for providing valuable informa­ tion and/or thoroughly discussing the ideas underlying this paper.