Control of Inference: Role of Some Aspects of Discourse Structure-Centering

1. INTRODUCTION

Although there is considerable research in the development of suitable representations for differ­ en t pieces of knowledge so that the necessary in­ ferences can be drawn (e.g., for comprehending a discourse), very little is known about how the in­ fe rential processes are controlled (some exceptions are (1], (2], and [4], for example) i.e., how the more appropriate inferences are drawn and how the irrelevant (yet valid) inferences are prevented from being drawn, or at least drawn with greater diff iculty; alternatively, how the various pieces of knowledge and their organization impose ordering on the set of inferences so that this ordering re­ flects the relative ease ~or difficulty) associated

with these inferences.

The purpose of this communication is to exam­ ine one particular aspect of discourse structure, name l y , a discourse construct called center of a sentence in discourse and its relation to the lar­ ger issue of control of inference. First we will describe very briefly the notion of center(s) of a sen tence in discourse and then discuss (again very briefly) how the centering phenomenon might be in­ co rporated in a formal model of inference and whether such a model might shed light on the intri~ sic complexity of certain inferences.

+This work is partially supported by a grant from the National Science Foundation, MCS79-08401, and by a grant to the University of Delaware by the Air Force Office of Scientific Research, Air Force Sys tems Command, USAF, AFOSR-80-0190.

CONTROL OF INFERENCE: ROLE OF SOME ASPECTS OF DISCOURSE STRUCTURE - CENTERING+

Aravind K. Joshi

Department of Computer

and Information Science

University of Pennsylvania, Philadelphia, PA 19104

and Scott Weinstein Department of Philosophy

(Dedicated to the memory of William A. Martin)

In a natural language sentence in discourse (in sharp contrast to sentences of a formal lan­ guage) one or more entities (arguments of the main predicate) are singled out. We call these the centers*. Centered entities may be syntactically marked but this need not be the case.

Let Si be the current utterance (sentence) and let Di-1 be the preceding discourse (at times only the preceding sentence Si-r). We assume that as the discourse is unfolding a discourse "model" is being created. By "model", for the purpose of our present discussion, we mean simply a data structure in terms of a set of entities and relations among them. We are not claiming here that this is all there is to a discourse "model", however, for our immediate purpose this representation would be ade­ quate. In addition to constructing the discourse model, we will assume that we keep track of those entities which are centered so far. Our main goal is that in terms of the discourse model together with the associated set of centers, and the cen­ ter(s) of the current sentence, we should be able to give some account of the appropriateness (or in­ appropriateness) of the current sentence Si in the discourse context Di-1· The notion of center is relevant to the determination of how the current utterance is integrated in the discourse "model" constructed so far and how the succeeding discourse is to be integrated in the preceding discourse of

which the current utterance is now a part.

For each utterance (sentence), Si, in dis­ course, we will associate two centers, Cb(Si): the backward looking center, and Cf(Si): the forward looking center(s)**· Cb(Si) determines how Si is going to be incorporated in the preceding discourse Di-1 and thus incrementally augment the current discourse model. Cf(Si) determines how Si will get linked up to the succeeding discourse. We will assume that Cb(Si) is always a singleton, i.e. each sentence has only one backward looking center;

however, Cf(S 1 ) could be a set. Further, it is not necessary that Cb(Si) and Cf(Si) are disjoint. In an obvious way we can define Cf(Di-1) which would be the set of all forward looking centers associated with the preceding discourse Di-1· (We have defined Cf(Di-1) as a set without any further structure on it. This is clearly not adequate. Some structure on this set is necessary to account for the relative ease (or difficulty) of accessing elements of this set. See examples in Section 2. Stack organization by itself is not adequate. We will not discuss this issue here due to restriction on allowed space for the paper.)

*--------

This notion is relat ed to the AI notion of (local) focus (3] and the notions of topic and focus in lin­ i uistics, but it is not identical to any of these .

**we are not concerned he r e about the determina­ tion of centers. Svntactic structure, stress, and discourse context a~e some of the determining fac­ tors. For our present purpose it is enough to

assume that a sentence in discourse has centers.

We will now define "appropriateness" of Si in the discourse context Di-1· Si is "appropriate" in the discourse context Di-1 if Cb(Si) i Cf(Di-1), i.e. the backward looking center is identical to one of the forward looking centers, or Cb(Si) is a proword for some element in Cf(Di-1), or Cb(Si) is functionally dependent on some element of Cf(Di-1). Cf(Di) the set of forward looking centers for Di cannot be represented by just the union of Cf(Di-1) and Cf(Si). (See the remark at the end of the previous paragraph.) We do not drop centers but allow for some of them to be temporarily placed

in the background.

The intuitive notion of appropriateness is that if the condition is satisfied the resultant discourse Di = Di-1 Si will be judged to be more coherent, better "well-fanned," less awkward than the case when the condition is not satisfied. Thus it is not the case that if the condition is not satisfied, Si cannot follow Di-1· but rather if it does, the resultant discourse Di = Di-1 Si will be more difficult to comprehend i.e., there would be more processing involved in integrating Si into the discourse model constructed so far (more as com­ pared to the case when the condition is fulfilled). Our mathematical treatment so far has attempted to characterize this increased processing in terms of some complexity measures associated with certain

inference schemes.

2. EXAMPLES

1. Si: John hit Bill. Cb(Si) (John, Bill).

This example shows that Cb(Si) corresponds roughly to the notion of topic of a sentence. Cf(Si) cor responds roughly to the linguistic notion of focus or the AI notion of (local) focus [3). Cb(Si) and Cf(Si) are not necessarily disjoint.

1. Si: Bill was hit by John. Cb(Si) = Bill; Cf(Si) = (John, Bill)
2. Si: It was John who hit Bill. Cb(Si) Cf(Si) = John Bill;

John is the focus; hence it is Cf(Si). Bill is the Cb(Si) which corresponds to the topic. Note that Bill is not in Cf(Si). In this respect (3) above is different from (2). The it-cleft const­ ruction has the effect of temporarily putting Bill in the background thereby making it difficult to access Bill from the set of previously centered en­ tities, i.e., Bill can be made the center in the succeeding discourse only hy explicitly reintroduc­ ing it. For this reason, discourse (3a 3b) is less awkward than discourse (3a' 3h').

fa ~b pa· ~b' s 1 : Bill was hit by John. Si+l: He (=Bill) was taken to the has­ pi tal. Si: lt was John who hit Bill. Si+l: He (= Bill) was taken to the has­ pita 1.

Cb(Si) can be a pro-word for some element in Cf(Si-1), or Cb(Si) can be functionally dependent

on some element in Cf(Si_1). For example,

• la Si: John walked up to the house. Cf(Si) = {John, house} lb Si+l: The door was locked. { door}

Cb(Si+l) =door is not in Cf(Si), however, it is functionally dependent on house (i.e. the door of the house), hence (la lb) is appropriate. Such dependen;ies could be nested . It is important t o note that whenever we have such functional depen­ dencies, we have an effect which is similar to that in it-cleft sentences, i.e., in lb Si+l: the door was locked, Cb(Si+l) = door; hous~ in Cf(Si) is temporarily put in the background, i.e., it can be brought into the succeeding discourse only by explicit reintroduction. Hence (2a2b2c2d) is more awkward than (2a'2b'2c'2d'). (The contrast can be made sharper by allowing for further nested functional dependencies.)

a John walked up to the house.

2b The door was locked.

• U c 2d But the handle was broken. It (= the house) looked unoccupied for a long time.

a' John walked up to the house.

b' The door was locked.

c ' But the handle was broken.

U d' The house looked unoccupied for a long time.

3. COMPLEXITY OF INFERENCING

We will now briefly describe our formal in­ vestigations in complexity of inferencing with respect to the notion of centering. Centering contributes to the difficulty of inferencing (i.e. of incorporating Si into the discourse model con­ structed up to Di-1), in various ways: 1) violation of centering con­ straints, 2) size of the forward looking centers of Di-l· the large r this set the more difficult~ in incorporating Si, 3) the total number of ent1ties centered in the discourse. In a formal model of inference incorporating the notion of center, each of these aspects of discourses rele­ vant to their ease of comprehension may be natu­ rally translated into measures of complexity on

the deductions which can be formalized in the model . Thus each of these measures would impose a complexity ordering on the formal deductions of the mode l. An inference (i.e. pair of premises and conclusion) which could be derived in the model mi ght then be assigned as its intrinsic complexity a long one of these measures the minimum complexity of the deductions which derive that inference. By combining the different measures we might arrive at a useful partial ordering of the complexity of in­ f e rences. It would be particularly interesting to s how that the inferences which fell below a gi ven l evel of complexity in such an ordering are sim­ pl er than those falling above that level in a computational sense. Thus a first question to con­ s ider would be: are the collections of inferences which fall below a given level of complexity along each of the measures considered above decidable se ts. If so, are the decision procedures for the collections at higher levels more complex (compu­ t a tionallv) than the decision procedures for lower levels.

In order to investigate these questions in any de t ai l we must choose a formal model of inference and a means of incorporating the notion of center i nto that model. In the studies we have completed thus far, the model of inference we have chosen is t he system of natural deduction as formulated by Prawitz and our means of introducing the notion of center has been to require the centering of para­ meters which are used as the proper parameters of quantifi e r introduction and elimination rules. By us ing Prawitz's normalization theorem, we have been abl e t o answer the decidability question broached above f or the third measure of complexity indicated above (that in terms of total number of centered entities). In particular, if 1T is a deduction in Prawitz's system C' let c("tT) = the number of di s tinct parameters which occur in formulas in TT. Le t Tn = {A I A is a parameter free formula of C' and 3TT ( iT is a deduction of A from the empty set of assumptions and c( 1T ) = n}.

• Pr oposition: 1) For every n, Tn is primitive recursive.
• For every. n, Tn+l - Tn ~ ¢

At present we are studying other formal models of inf erence in order to determine whether a more na tural introduction of the notion of center can be achieved than in the case of natural deduction. In particular, it seems that centering, if it plays a genuine role in inferential complexity at all , ought to be relevant to the complexity of inferen­ ces in the propositional as well as in the full pr edicate calculus. Our natural deduction model does no t exhibit this feature. Indeed, it is vasy to s~:e that all the purely propositional in­ fe rences comprehended in the model described above occur in 1' 0 · Hence, our model dne s not discrimi­ nat e at a ll among propositional inferences of diff e ring complexity. We are currently studying way s in which the propositional cnmplexity of in­ fe r ences might be accommodated within our model, a study which seems essential if the centering phenomenon is to have bearing on the computational complexity of infe rencing procedures.

In addition, it may be that measures of com­ plexity based on the notion of centering provide a ni ce structure only on a proper subcollec tion of all valid inferences in the propositional or pre­ dicate calculus. This seems particularly plausib~ in view of the fact that such measures were de­ rived from phenomena which arise in natural dis­ course and the consideration that not all valid inferences may be derivable by deductions which constitute natural discourses. The question whether there are proper fragments of the predi­ cate calculus to which the complexity mea sures considered here more naturally apply is currently under study.

Acknowledgement

We would like to acknowledge the he lpful comments of bill Martin who was a referee for this paper. We wish to express our deep sadness at his untimely death.

We also would like to thank Don Norman for

his valuable comments.