当前位置:首页 >> 少儿英语 >>

A conceptual reasoning approach to textual ellipsis

ically narrowed regions in a knowledge base, likely to make the algorithm e ciently executable even on larger knowledge bases. The ellipsis handler has been implemented in Smalltalk as part of a comprehensive text parser for German, which is interfaced to the LOOM system 15]. Besides the information technology domain (this knowledge base currently contains approximately 800 concept/role speci cations), experiments with our parser have also been successfully run on medical domain texts (the corresponding medical domain knowledge base currently contains approximately 500 concept/role speci cations). These results indicate that the heuristics we have been developing are not bound to a particular domain.

Acknowledgments. We would like to thank our colleagues in the CLIF group for fruitful discussions. M. Strube's contribution has been funded by LGFG Baden-Wurttemberg, while K. Markert is supported by a grant from DFG within the Freiburg University Graduate Program on \Human and Arti cial Intelligence". We also gratefully acknowledge the provision of the LOOM system from USC/ISI.


15] Robert MacGregor and Raymond Bates. The LOOM Knowledge Representation Language. (ISI/RS-87-18) USC/ISI, 1987. 16] Peter Norvig, `Marker passing as a weak method for inferencing', Cognitive Science, 13(4), 569{620, (1989). 17] Martha S. Palmer, Deborah A. Dahl, Rebecca J. Schi man, and Lynette Hirschman, `Recovering implicit information', in Proc. of ACL-86, pp. 10{19, (1986). 18] Phil Resnik, `Using information content to evaluate semantic similarity in a taxonomy', in Proc. of IJCAI-95, volume 1, pp. 448{453, (1995). 19] Michael Strube and Udo Hahn, `ParseTalk about sentence- and text-level anaphora', in Proc. of EACL95, pp. 237{244, (1995). 20] Michael Strube and Udo Hahn, `Functional centering', in Proc. of ACL-96, (1996). 21] Hajime Wada, `A treatment of functional de nite descriptions', in Proc. of COLING-94, volume 2, pp. 789{ 795, (1994). 22] Morton Winston, Roger Cha n, and Douglas Herrmann, `A taxonomy of part-whole-relations', Cognitive Science, 11, 417{444, (1987). 23] William A. Woods and James G. Schmolze, `The KLONE family', Computers & Mathematics with Applications, 23(2-5), 133{177, (1992).

1] Roger Cha n, `The concept of a semantic relation', in Frames, Fields and Contrasts, eds., A. Lehrer and E.F. Kittay, 253{288, Hillsdale, N.J.: Lawrence Erlbaum, (1992). 2] Eugene Charniak, `A neat theory of marker passing', in Proc. of AAAI-86, volume 1, pp. 584{588, (1986). 3] Herbert H. Clark, `Bridging', in Proc. of the Conference on Theoretical Issues in Natural Language Processing, Cambridge, MA, pp. 169{174, (1975). 4] Frantisek Danes, `Functional sentence perspective and the organization of the text', in Papers on Functional Sentence Perspective, ed., F. Danes, 106{128, Prague: Academia, (1974). 5] Dan C. Fass, `met : A method for discriminating metonymy and metaphor by computer', Computational Linguistics, 17(1), 49{90, (1991). 6] Barbara J. Grosz, Aravind K. Joshi, and Scott Weinstein, `Centering: A framework for modeling the local coherence of discourse', Computational Linguistics, 21(2), 203{225, (1995). 7] Udo Hahn, `Making understanders out of parsers: Semantically driven parsing as a key concept for realistic text understanding applications', International Journal of Intelligent Systems, 4(3), 345{393, (1989). 8] Udo Hahn, Susanne Schacht, and Norbert Broker, `Concurrent, object-oriented dependency parsing: The ParseTalk model.', International Journal of HumanComputer Studies, 41(1/2), 179{222, (1994). 9] Udo Hahn, Michael Strube, and Katja Markert, `Bridging textual ellipses', in Proc. of COLING-96, (1996). 10] Graeme Hirst, Semantic Interpretation and the Resolution of Ambiguity, Cambridge, UK: Cambridge University Press, 1987. 11] Jerry R. Hobbs, Mark E. Stickel, Douglas E. Appelt, and Paul Martin, `Interpretation as abduction', Arti cial Intelligence, 63, 69{142, (1993). 12] Michael N. Huhns and Larry M. Stephens, `Plausible inferencing using extended composition', in Proc. of IJCAI-89, volume 2, pp. 1420{1425, (1989). 13] Hans Kamp and Uwe Reyle, From Discourse to Logic, Dordrecht: Kluwer, 1993. 14] George Lako , Women, Fire, and Dangerous Things. What Categories Reveal about the Mind, Chicago University Press, Chicago, IL, 1987.

Natural Language Processing


U. Hahn, K. Markert and M. Strube

related to Charge-Time via a plausible path (viz. chargetime-of). As plausible paths are the strongest type of conceptual paths, none of the items following in the centering list can be preferred as the antecedent of \Ladezeit" (charge time) over \Akku" (accumulator) (cf. the constraint from Table 7). Hence, the remaining concepts in the Cf list (viz. Time-UnitPair and Power) need no longer be considered as potential antecedents. An appropriate update links the corresponding instances via the role charge-time-of and, thus, local coherence is established at the conceptual level of the text knowledge base. A fully worked out parsing example together with a discussion of a medium-sized performance evaluation of the criteria considered for ellipsis resolution is given in 9]. Searching links in a taxonomic hierarchy is a problem which has often been tackled by spreading activation or marker passing approaches. The paradigm of path nding and evaluating they propose has obvious parallels to our approach. The criteria used in spreading activation models for nding and evaluating paths, however, are mostly based on numerical restrictions, e.g., on weights 2] or path lengths 10]. This is problematic, as the foundation and derivation of these numbers is usually not made explicit. The abduction-based approach to inferencing underlying the TACITUS system 11] also refers to weights and costs and, thus, shares some similarity with marker passing proposals 11, p. 122]. The crucial problem, however, still unsolved in this logically very principled framework concerns a proper choice methodology for xing appropriate costs for speci c assumptions on which, among other factors, textual ellipsis resolution is primarily based. A pattern-based approach to inferencing (including textual ellipsis resolution) has also been put forward by Norvig 16]. Unlike Norvig's proposal to de ne path patterns solely in terms of \formal" link criteria in a knowledge base whose patterns are simply matched against the links being passed, our de nitions of path patterns take the semantic hierarchy of relations and their compositional properties (like transitivity) into account. This allows for a semantically motivated preference ranking of the paths by treating the phenomena of granularity (corresponding to plausible paths) and metonymy (corresponding to metonymic paths) in a uni ed search algorithm. Although Norvig makes a strong point concerning his use of path patterns (instead of marker energy) to guide the search in a knowledge base, the de nitions of path patterns he gives are not restrictive enough. Additional numerical rules for coping with combinatorial search problems (e.g., an antipromiscuity rule) still have to be supplied, whereas our path patterns are complemented by structural formal criteria which do not rely upon numerical restrictions in any way. The cyclicity criterion, e.g., leads to path length (and thus granularity) independence and the inclusion criterion further abstracts from node counting. As far as text-level processing is concerned, the framework of DRT 13], at rst sight, constitutes a particularly strong alternative to our approach. The machinery of DRT, however, might work well for (pro)nominal anaphora, but faces problems when elliptical text phenomena are to be interpreted (though 21] has recently made an attempt to deal with restricted forms of textual ellipsis in the DRT context). This

6 Comparison with Related Approaches

shortcoming is simply due to the fact that DRT is basically a semantic theory, not a full- edged model for text understanding. In particular, it lacks any systematic connection to well-developed reasoning systems accounting for conceptual domain knowledge. Actually, the sort of constraints we consider seem much more rooted in encyclopedic knowledge than are they of a primarily semantic nature anyway. Unlike DRT, the centering model 6] to which we adhere is not considered a semantic theory but rather a discourse processing model which lends itself to an easy integration into a text understanding framework. Still, it does not provide for well-developed methods for textual ellipsis resolution. Grosz et al. rather sketchily point to the di erence between the relations directly realizes and realizes whose precise de nition they suggest depends on the semantic theory one adopts 6, p.209]. We have shown, however, that there are a lot of constraints at the conceptual level which cannot reasonably be accounted for by semantic theories. Only few NLP systems exist which deal with textual ellipsis in a dedicated way. For example, the PUNDIT system 17] provides a fairly restricted solution in that only direct conceptual links between the concept denoted by the antecedent and the elliptical expression are considered (\plausible" paths of length 1, in our terminology). The approach reported in this paper also extends our own previous work on textual ellipses 7] by the incorporation of an elaborated model of functional preferences on Cf elements which constrains the set of possible antecedents according to information structure criteria. In this paper, we have outlined a model of textual ellipsis resolution. It considers conceptual criteria to be of primary importance and provides conceptual well-formedness and strength criteria for role chains in a terminological knowledge base in order to assess the plausibility of various possible antecedents as proper bridges 3] to elliptical expressions. Functional constraints based on the utterances' information structure contribute further restrictions on proper elliptical antecedents and require a basic revision of the centering model. The two principled di culties inherent in every networkbased symbolic knowledge representation approach are its dependency on hand-crafted and often domain-speci c knowledge and the exorbitant costs for unconstrained search (often limiting the scalability of the approach). We cope with the rst of these problems by postulating two formal criteria, viz. the non-cyclicity and the inclusion condition, which only depend on features present in almost any knowledge representation language, i.e., isa links, domains and ranges of relations and inverse relations. No reference to a speci c network structure or a speci c domain is made. The de nition of patterns relies mainly on structural properties of semantic relations, which are entirely domain-independent. However, this heuristic criterion is only e ective when the underlying knowledge base is built on top of a clear taxonomy of relations (although this taxonomy and the corresponding path patterns can be speci ed in ways di ering from ours). The expensiveness of the search has already been reduced significantly by testing the non-cyclicity of the paths during the search. We are currently experimenting with an additional search constraint, which limits the search to certain dynam-

7 Conclusions

Natural Language Processing


U. Hahn, K. Markert and M. Strube

The main di erence between Grosz et al.'s seminal work 6] and our proposal (see 20]) concerns the criteria for ranking the forward-looking centers. While Grosz et al. assume that grammatical roles are the major determinant for the ranking on the Cf , we claim that for languages with relatively free word order (such as German), it is the functional information structure (IS) of the utterance in terms of the context-boundedness or unboundedness of its discourse elements. The centering data structures and the notion of context-boundedness can be used to rede ne Danes' 4] trichotomy between given information, theme and new information (which he considers equivalent to rheme). The Cb (Un ), the most highly ranked element of Cf (Un?1 ) realized in Un , corresponds to the element which represents the given information. The theme of Un is represented by the preferred center Cp (Un ), the most highly ranked element of Cf (Un ). The theme/rheme hierarchy of Un is determined by the Cf (Un?1 ): the rhematic elements of Un are the ones not contained in Cf (Un?1 ) (unbound discourse elements) { they express the new information in Un . The ones contained in Cf (Un?1 ) and Cf (Un ) (bound discourse elements) are thematic, with the theme/rheme hierarchy corresponding to the ranking in the Cf s.

if their conceptual strength is equal, whose strength of preference under the IS relation is higher than that of y. \>IS " de nes (cf. 20] for an in-depth treatment) a strict order on the conceptual/semantic items of Cf re ecting the functional information structure of the utterance Un in which their linguistic counterparts, viz. z and y, occur.
Table 7.

Preferred Conceptual Bridge for an Elliptical Expression

PreferredConceptualBridge (y, x, n) :, isPotentialEllipticAntecedent (y, x, n) ^ :9 z : isPotentialEllipticAntecedent (z, x, n) ^ (isStrongerThan (CPx:c;z:c , CPx:c;y:c ) _ (equallyStrongAs (CPx:c;z:c , CPx:c;y:c ) ^ z

> IS


The grammar formalism we use (cf. 8] for a survey) is based on dependency relations between lexical heads and modiers. The dependency speci cations allow a tight integration of linguistic (grammar) and conceptual knowledge (domain model), thus making powerful terminological reasoning facilities directly available for the parsing process3 . The resolution of textual ellipses is based on two major criteria, a conceptual and a structural one. The conceptual strength criterion for role chains is already speci ed in Table 5. The structural condition is embodied in the predicate isPotentialEllipticAntecedent (cf. Table 6). The elliptical phrase which occurs in the n-th utterance is restricted to be a de nite NP and the antecedent must be one of the forward-looking centers of the preceding utterance (note that Cf s contain only conceptual referents of nouns and pronouns).
Table 6.

4 Grammatical Predicates for Textual Ellipsis

Potential Elliptical Antecedent

isPotentialEllipticAntecedent (y, x, n) :, y C Nominal ^ x C Noun ^ 9 z: (x z ^ z C DetDe nite) ^ x 2 n ^ y.r 2 f ( n?1 )
isa head isa U U C

The resolution of textual ellipses depends on the results of the foregoing resolution of nominal anaphors 19] and the termination of the semantic interpretation of the current utterance. It will only be triggered at the occurrence of the de nite noun phrase NP when NP is not a nominal anaphor and (the conceptual referent of the) NP is only connected via certain types of relations (e.g., has-property, has-physical-part)4 to referents denoted in the current utterance at the conceptual level. We will illustrate our approach to text ellipsis resolution, referring to the already introduced text fragment (1) { (3). (3) contains the de nite noun phrase \die Ladezeit". At the conceptual level, \Ladezeit" (charge time) does not subsume any element of the forward-looking centers of the previous utterance (Cf (U2 ) = 316LT, Accumulator, Time-Unit-Pair, Power]). Thus, the anaphora test fails; the conceptual referent of \die Ladezeit" has also not been integrated in terms of a signi cant relation into the conceptual representation of the utterance as a result of its semantic interpretation. Consequently, the search for an antecedent of the textual ellipsis is triggered. The forward-looking centers of the previous sentence are tested for the predicate PreferredConceptualBridge. In this case, the instance 316LT (the conceptual referent of the nominal anaphor \der Rechner" (the computer), which has already been properly resolved) is related to Charge-Time (the concept denoting \Ladezeit") via a metonymic path, viz. (chargetime-of accumulator-of). This path corresponds to a wholefor-part metonymy, as charge time is a direct property of an accumulator and therefore only a mediated property of a computer as a whole. In contrast, the concept Accumulator is
4 The distinction between roles and their inverses becomes cru-

5 Text Ellipsis Resolution

The predicate PreferredConceptualBridge (cf. Table 7) combines both criteria. A lexical item y is determined as the proper antecedent of the elliptic expression x i it is a potential antecedent and if there exists no alternative antecedent z whose conceptual strength relative to x exceeds that of y or, 3 We assume the following conventions to hold: C = fWord, Nominal, Noun, PronPersonal,...g denotes the set of word classes, and C = f(Nominal, Word), (Noun, Nominal), (PronPersonal, Nominal),...g C C denotes the subclass relation which yields a

hierarchical ordering among these classes. Furthermore, object.r refers to the instance in the text knowledge base denoted by the linguistic item object and object.c refers to the corresponding concept class c. Head denotes a structural relation within dependency trees, viz. x being the head of modi er y.

cial for already established relations like has-property (subsuming charge-time, etc.) or has-physical-part (subsuming has-accumulator, etc.). The instantiation of these relations does not block the triggering of the resolution procedure for textual ellipsis (e.g., Accumulator { charge-time { Charge-Time), whereas instantiations of their inverses, we here refer to as POF-type relations, e.g., property-of (subsuming charge-time-of, etc.) or physicalpart-of (subsuming accumulator-of, etc.), do (e.g., Charge-Time { charge-time-of { Accumulator). This is simply due to the fact that the semantic interpretation of a phrase like \the charge time of the accumulator" already leads to the creation of the POF-type relation the resolution mechanism for textual ellipsis is supposed to determine. This is opposed to the interpretation of its ellipti ed counterpart \the charge time" in sentence (3), where the genitive object \ of the accumulator]" is elided and, thus, the role charge-time-of remains uninstantiated.

Natural Language Processing


U. Hahn, K. Markert and M. Strube

express one of the metonymic relations MS = fhas-part, partof, produced-byg, depending on the speci c metonymy to be handled2 . For a producer-for-product metonymy, e.g., j = n and rn = produced-by must hold. For a part-for-whole or whole-for-part metonymy, j < n may be possible as all paths in T and T ?1 (e.g., (has-physical-part )) also express a single has-part or part-of relation (see the explanations of plausible paths above). For notational convenience, we now consider the paths in T and T ?1 as a single relation so that we may write (has-physical-part ) isaR has-part or (event-feature ) 2 MS . Thus, we may restrict the above cases of well-formed metonymic paths to the pattern in Table 3. Special path patterns for speci c metonymies and metonymic chains can be derived from this general pattern by either instantiating speci c metonymic relations or by a recursive application of the predicate. Table 3. Metonymic Path Patterns
Metonymic-Path (( 1 n )) :, ( 1 n) 2 P ^ (( 1 ^ ( 1 2 n?1 ) 2 P ^ n 2 MS ) _( 1^( 2 3 n ) 2 P ^ 1 2 MS ?1 ))
r :::r r :::r = n > r ;r ;:::;r r n > r ;r ;:::;r r

usually have to compare pairs of path lists CPx;y and CPx;z , where x, y, z 2 F (y 6= z ). Fortunately, the same criteria can be applied to path lists as those we used for evaluating paths linking single concepts. As all paths in CPx;y and CPx;z were computed by the path nder, they already ful ll the connectivity and non-cyclicity condition. The inclusion criterion (see Table 2) cannot be applied to any path p1 2 CPx;y and p2 2 CPx;z , as p1 and p2 have di erent end points, by de nition. However, the criterion which ranks conceptual paths according to their associated path markers is applicable, as all paths in a single CP list have the same marker. A function, PathMarker(CPi;j ), yields as its value either \plausible", \metonymic" or \implausible" depending on the type of paths it contains. We may now apply the same ordering of path markers as in Table 4 in order to compare two CP lists (cf. Table 5).
Table 5.

Path Lists Compared by Conceptual Strength

The markers \plausible", \metonymic" and \implausible" are nally ranked (cf. Table 4) according to their inherent level of conceptual strength denoted by the relation \>str " (conceptually stronger than).
Table 4.

isStrongerThan (CPx;y , CPx;z ) :, PathMarker(CPx;y ) str PathMarker(CPx;z ) equallyStrongAs (CPx;y , CPx;z ) :, PathMarker(CPx;y ) = PathMarker(CPx;z)

Path Markers Ordered by Conceptual Strength
> >

\plausible" str \metonymic" str \implausible"

As a consequence of this ordering, metonymic paths will be excluded from a path list i plausible paths already exist, while implausible paths will be excluded i plausible or metonymic paths already exist. At the end of this selection process, only paths of the strongest type are retained in the path list. To evaluate our approach we selected 80 concept pairs at random from the underlying knowledge base (composed of 459 concepts and 334 relations). We submitted these pairs to the path nder/evaluator and compared the automatically generated conceptual paths with introspective judgments about the kinds of relations linking each pair. The overall error rate was below 5%. The average number of connected paths between two concepts (41.8) was further reduced by the non-cyclicity criterion to 10.4 well-formed paths and by the inclusion criterion (see Table 2) to 2.4. The criterion in Table 4 leads to a nal reduction to merely 1.8 paths. Hence, the criteria realize the desired discrimination. We plan a broader evaluation of our approach by running the algorithm on larger-sized knowledge bases in order to test its domain-independence and scaling performance. All paths which meet the above criteria for two concepts, x and y , are contained in a list denoted by CPx;y . As, in the case of textual ellipsis, we have to deal with paths leading from the conceptual referent of the elliptical expression to the conceptual referents of several possible antecedents, we

2 If the direction of search is reversed (searching from C3 to C1 ) the

corresponding inverse relations must be considered. We refer to these inverse relations as MS ?1 = fpart-of, has-part, producesg. This list of metonymic relations is, of course, incomplete and can be augmented on demand.

Conceptual criteria are of tremendous importance, but they are not su cient for proper ellipsis resolution. Additional criteria have to be supplied in the case of equal strength of CP lists for alternative antecedents. We therefore incorporate into our model criteria which relate to the functional information structure of utterances using the methodological framework of the well-known centering model 6]. The theory of centering is intended to model the local coherence of discourse, i.e., coherence among the utterances in a particular discourse segment (say, a paragraph of a text). Each utterance Ui in a discourse segment is assigned a set of forward-looking centers, Cf (Ui ), and a unique backwardlooking center, Cb (Ui ). The elements of Cf (Ui ) are partially ordered to re ect relative prominence in Ui . The most highly ranked element of Cf (Ui ) that is realized in Ui+1 (i.e., is associated with an expression that has a valid semantic interpretation) is the Cb (Ui+1 ). The ranking imposed on the elements of the Cf re ects the assumption that the most highly ranked element of Cf (Ui ) is the most preferred antecedent of an anaphoric expression in Ui+1 , while the remaining elements are partially ordered according to decreasing preference for establishing referential links. The theory of centering, in addition, de nes several transition relations across pairs of adjacent utterances (e.g., continuation, retention, smooth and rough shift), which di er from each other according to the degree by which successive backward-looking centers are con rmed or rejected, and, if they are con rmed, whether they correspond to the most highly ranked element of the current forward-looking centers or not. The theory claims that to the extent a discourse adheres to all these centering constraints (e.g., realization constraints on pronouns, preferences among types of center transitions), its local coherence will increase and the inference load placed upon the hearer will decrease. Therefore, the tremendous importance of eshing out the relevant and most restrictive, though still general centering constraints.

3 Functional Constraints on Centers

Natural Language Processing


U. Hahn, K. Markert and M. Strube

Apart from being connective, we require a well-formed path to be non-cyclic (cf. Table 1; r?1 denotes the inverse of relation r).
Table 1.

book to Price; we regard p1 as being conceptually weaker than p2 given the constraint from Table 2.

Cyclic Path Criterion
i j

Cyclic (( 1 n )) :, 9 i, j 2 f1, . .. , ng: 6= ^?1 s 2 R: 9 (ri R s) ^ (rj R s )
r :::r isa isa

This criterion favors a unidirectional search in the knowledge base. A cyclic connected conceptual path lacks specicity, as it often only expresses that the end point and the starting point of the search are of a similar, though not necessarily of a semantically related type (for this distinction see, e.g., 18]). For instance, the path (accumulator-of has-printer) will be excluded from the search for a path from Accumulator to Printer as accumulator-of isaR physical-part-of and has-printer isaR has-physical-part holds. Thus, the example path carries the information that both, accumulator and printer, are types of hardware, but it does not elucidate any special relationship between these two that an elliptical expression could refer to. A warranted side e ect of the exclusion of cyclic patterns is that, as longer paths usually tend to get cyclic, the search terminates without the need to take refuge to ad hoc path length restrictions. Given the set of well-formed, i.e., connected and non-cyclic paths, the remaining items of the path list are interpreted by the path evaluator. Two criteria are considered in order to select the strongest paths among the elements of the path list. One considers the formal inclusion property between well-formed paths, the other introduces semantically plausible path patterns. Path Inclusion. The introduction of a relative path length condition is aimed at constraining the overly simplistic counting of nodes in role chains. A well-formed path p1 = (r1 ... rn ) is conceptually longer than another well-formed path p2 = (s1 ... sm ) i p1 properly includes p2 (see Table 2). The path p1 will then be regarded as being conceptually weaker than p2 and thus be discarded from the path list.
Table 2.

Path Inclusion Criterion

Includes (p1 , p2 ) :, 9 i, j 2 f1, . . ., ng: i j ^ (i 6= 1 _ j 6= n) ^ ((ri . . .rj ) = (s1 .. . sm )) ^ ((domain (r1 ) F domain (s1 )) _ (domain (s1 ) F domain (r1))) ^ ((range (rn) F range (sm )) _ (range (sm ) F range (rn )))
isa isa isa isa

Accordingly, path length considerations cannot be applied to the paths p1 = (has-central-unit has-motherboard has-cpu) and p2 = (has-central-unit has-motherboard) { both being well-formed conceptual paths from Notebook to Product. Although p2 is shorter than p1 in the absolute sense (counting role chains or concept nodes), it is not shorter in the relative sense speci ed above and, thus, not presumed to express a stronger conceptual link (range (has-cpu) = CPU and range (has-motherboard) = Motherboard; hence, the last constraint in Table 2 is violated). In contrast, the inclusion criterion is applicable to the paths p1 = (has-accumulator pricedm-pair) and p2 = (price-dm-pair) both leading from Note-

empirical criterion which marks certain paths as being preferred over others in terms of commonsense semantic plausibility. Based on introspective analyses of approximately 60 product reviews from the information technology domain we performed, and evidences reported from several (psycho)linguistic studies (e.g., 1]) , we stipulate certain predened path patterns. From those general path patterns and by virtue of the hierarchical organization of conceptual relations, concrete conceptual role chains can be derived by a simple pattern matching algorithm. These path patterns are used to distinguish between a subset P of all types of well-formed paths, which is labeled \plausible", another subset M which is labeled \metonymic", and all remaining paths which are labeled \implausible". Plausible Paths. An important assessment criterion for characterizing relation chains as plausible ones (forming the set P ) is that a plausible role chain can always be treated as a single relation. Thus, plausible paths provide a handle for coping with the notorious problem of granularity in knowledge bases. All paths of unit length 1 are included in P , as they are \plausible", by de nition (they refer to the conceptual roles directly associated with a concept de nition). In addition, we incorporate empirical observations about the transitivity of relations, part-whole relations in particular, made by Cha n 1] and Winston et al. 22]. In these studies several subtypes of part-whole relations are distinguished, e.g., integral object-component (corresponding to what we call has-physical-part), collection-member, mass-portion, processphase, event-feature and area-place. The claim is made that any of these subrelations are transitive, while the most general part-whole relation usually is not. In other words, a relation chain containing only relations of one of the abovementioned subtypes is again a relation of the same subtype, whereas a relation chain containing several di erent types of part-whole relations is, in general, not reasonable any more. Following this argument, we have included the path patterns (has-physical-part ), (collection-member ), (massportion ), (process-phase ), (event-feature ), (area-place ) and the corresponding inverses like (physical-part-of ) in P . We will refer to the rst six of these patterns as transitive part-whole patterns, in short T , and to the inverse patterns as T ?1 . Apart from the transitive part-whole relations we have included (spatial containment ) and (connnection ) inP (cf. 12]). Metonymic Paths. Following established classi cations of metonymies (cf. 14, 5]), we have included the analysis of whole-for-part, part-for-whole, and producer-for-product metonymies in the system. In order to determine path patterns corresponding to these types of metonymies consider the conceptual link between an instance of the concept C1 and an instance of the concept C3 , which characterizes a metonymy and thus stands for another instance of a concept C2 . A corresponding well-formed conceptual path p = (r1 : : : rn ) with n 2 IN , n > 1, and ri 2 R (i = 1,...,n) must, rst, link C1 to C2 via p1 = (r1 : : : rj?1 ) for some j 2 f2,...,ng. C2 is then linked to C3 via p2 = (rj : : : rn ). We restrict the rst link p1 to plausible paths in order to provide reasonable metonymic chains only. The second link p2 must

Conceptual Path Patterns. Finally, we introduce a purely

Natural Language Processing


U. Hahn, K. Markert and M. Strube

A Conceptual Reasoning Approach to Textual Ellipsis
Udo Hahn, Katja Markert and Michael Strube1
Abstract. We present a hybrid text understanding methodology for the resolution of textual ellipsis. It integrates conceptual criteria (based on the well-formedness and conceptual strength of role chains in a terminological knowledge base) and functional constraints re ecting the utterances' information structure (based on the distinction between context-bound and unbound discourse elements). The methodological framework for text ellipsis resolution is the centering model that has been adapted to these constraints.

1 Introduction

1. Der 316LT wird mit einem Nickel-Metall-Hydride-Akku bestuckt. (The 316LT is { with a nickel-metal-hydride accumulator { equipped.) 2. Der Rechner wird durch diesen neuartigen Akku fur 4 Stunden mit Strom versorgt. (The computer is { because of this new type of accumulator { for 4 hours { with power { provided.) 3. Daruberhinaus ist die Ladezeit mit 1,5 Stunden sehr kurz. (Also { is { the charge time of 1.5 hours quite short.)

Textual forms of ellipsis and anaphora are a challenging issue for the design of parsers for text understanding systems, since lacking recognition facilities either result in referentially incoherent or invalid text knowledge representations. At the conceptual level, textual ellipsis (also called functional or partial anaphora) relates a quasi-anaphoric expression to its extrasentential antecedent by conceptual attributes (or roles) associated with that antecedent (see, e.g., the relation between \Ladezeit" (charge time) and \Akku" (accumulator) in (3) and (2)). Thus, it complements the phenomenon of nominal anaphora, where an anaphoric expression is related to its antecedent in terms of conceptual generalization (as, e.g., \Rechner" (computer) refers to \316LT", a particular notebook, in (2) and (1)). The resolution of text-level nominal (and pronominal) anaphora contributes to the construction of referentially valid text knowledge bases, while the resolution of textual ellipsis yields referentially coherent text knowledge bases. Both phenomena tend to interact, as evidenced by the example below. \Akku" (accumulator) in (2) is a nominal anaphor referring to \Nickel-Metall-Hydride-Akku" (nickelmetal-hydride accumulator) in (1), which, when resolved, provides the proper referent for relating \Ladezeit" (charge time) in (3) to it.

can only be made explicit if conceptual knowledge about the domain, viz. the relation charge-time-of between the concepts Charge-Time and Accumulator, is available. The solution we propose is embedded within the centering model 6], in which textual ellipsis has only been given an insu cient treatment so far. Our approach combines domain and discourse knowledge as well as results from the functional interpretation of the utterances. On the one hand, language-independent conceptual criteria are based on the well-formedness and conceptual strength of role chains in a terminological knowledge base. On the other hand, we incorporate language-dependent information structure constraints re ecting the context-boundedness or unboundedness of discourse elements within the considered utterances. In this section, we will introduce formal and heuristic criteria to determine conceptual links, thus clarifying the notions of well-formedness and strength of conceptual chains underlying the resolution of textual ellipses. We assume the following conventions to hold in our knowledge base: The concept hierarchy consists of a set of concept names F = fComputer-System, Notebook, Accumulator,...g and a subclass relation isaF = f(Notebook, Computer-System), (Nimh-Accumulator, Accumulator),...g F F . The set of relation names R = fhas-physical-part, has-accumulator, charge-time-of,...g contains the labels of all possible conceptual roles. The roles are organized into a hierarchy by the relation isaR = f(has-accumulator, has-physical-part), (chargetime-of, property-of),...g R R. Throughout the paper, we assume a terminological knowledge representation and reasoning framework (cf. 23] for a survey). For the identi cation and evaluation of suitable conceptual links, the ellipsis resolution mechanism is supplied with a path nder, which performs an extensive search in the domain knowledge base looking for \well-formed" paths between two concepts, and a path evaluator, which selects the \strongests" of the ensuing paths. The path nder applies two basic criteria: Given two concepts x; y 2 F , a series of conceptual relations ri 2 R (i = 1,...,n) and concepts cj 2 F (j = 0,...,n) (n 2 I ) N is admitted as a conceptual path from x to y i the following connectivity condition holds: ri is a (possibly inherited) conceptual role of ci?1 with range(ri ) = ci for all i = (1,...,n); denotes cn ), where isaF y _ y isaF c0 = x ^ ( cn isaF the re exive and transitive closure of isaF . Note that no conceptual specialization is allowed at any step of the search except of the end point, thus reducing the complexity of the search. In the following, a connected conceptual path like the one above will be denoted by (r1 : : : rn ).

2 Constraints on Conceptual Linkage

1 Freiburg University, CLIF { Computational Linguis-

In the case of textual ellipsis, the missing conceptual link between two discourse elements occurring in adjacent utterances must be inferred in order to establish the local coherence of the discourse (for an early statement of that idea, cf. 3]). In sentence (3), e.g., \Ladezeit" (charge time) must be linked up with \Akku" (accumulator) from sentence (2). This relation

tics Lab, Europaplatz 1, D-79085 Freiburg, Germany http://www.coling.uni-freiburg.de]


Computational Linguistics Research Group Albert-Ludwigs-Universitat Freiburg Werthmannplatz 1 79085 Freiburg, Germany


We present a hybrid text understanding methodology for the resolution of textual ellipsis. It integrates conceptual criteria (based on the well-formedness and conceptual strength of role chains in a terminological knowledge base) and functional constraints re ecting the utterances' information structure (based on the distinction between context-bound and unbound discourse elements). The methodological framework for text ellipsis resolution is the centering model that has been adapted to these constraints.


Appeared in:
Proc. of the 12th European Conference on Arti cial Intelligence (ECAI-96). Budapest, Hungary, August 1996, pp. 572-576


Computational Linguistics Research Group

Albert-Ludwigs-Universitat Freiburg im Breisgau Germany


April 1996

REPORT 10/96

...A{{/B}} To understand the marketing concept, it ...
{{B}}TEXT A{{/B}} To understand the marketing concept, it is only ...This eye-on-the-consumer approach is known as the marketing concept, which...
text,they approach the concept from different ... substitution,ellipsis,conjunction and lexical ...conceptual connectivity,including(1)logical relations...