For an Incremental Computation of Intrasentential Coreference

1 Introduction

Intrasentential coreference is the grammatical phe­ nomenon of two nominal expressions, which occur in the same sentence, referring to the same entity in the dis­ course. Thus, in example (1)a John and him can be, but might also not be, coreferent, while in example (1)b John and himself must be coreferent.

1. a . John's mother likes him

b. John likes himself

A set of algorithms is presented to compute coref­ erence, according to Binding theory, as presented in [Chomsky, 1986]. The novelty of the computational so­ lution is two-fold: it is incremental and it computes both possible and impossible antecedents (such as John above) dynamically. By incrementality we mean that the algorithms are applied while building the syntactic repre­ sentation for the input string. Other proposals ([Latecki, 1991; Giorgi et al ., 1990]) require that the entire tree be built, before the coreference algorithms can apply. In our proposal, we interleave the computation of corefer­ ence at every structure-building step of the parser, which is the interactive parser described in [Wehrli, 1992).1

Incrementality is crucial for the efficiency of a sys­ tem, because the search space of possible analyses for a correct input sentence can be pruned earlier, and possi­ ble sources of ungrammaticality for incorrect input are discovered early in the parse. 2 Secondly, consider, for example, the sentence in (2) .

1 [Wehrli, 1992] is essentially a licensing parser, in the sense of [Abney, 1989], to which this algorithm is also applicable.

1. They thought that [ Bill liked them ]

For sentences such as (2), Binding theory, and algorithms that implement it directly, [Giorgi et al. , 1990], check that them, a pronoun, is not coreferent with a noun phrase in its local domain, here indicated by the brack­ ets: as Bill and them cannot be coreferent, the sentence is accepted. For practical applications, however, beside checking grammaticality, it is also important to be able to recover the possible antecedents of a pronominal ex­ pression, in (2) they is a possible antecedent of them. Thus we associate each noun phrase with two sets: one of possible and one of impossible antecedents, following [Ingria and Stallard, 1989]. The update of the two lists is incremental, as it is based on the structure-building algorithm, and it has wider empirical coverage than pre­ vious proposals, because the local domain of coreference is computed dynamically. More specifically, our algo­ rithm can handle cases of coreference inside NPs cor­ rectly (cases 6 and 7 below), while [Ingria and Stallard, 1989] could not .

The paper is structured as follows: first, we present all the definitions that constitute the core of binding theory and related concepts, then we introduce the linguistic examples, and finally we present and discuss the algo­ rithms.

2 C-command and Binding

According to binding theory, two notions are crucial to define the distribution of coreferring elements in a sen­ tence: a topological relation between the two coreferring phrases in the tree (c-command), and a notion of do­ main, which determines how far away from each other the elements can be (Complete Functional Complex). The two algorithms that we propose deal with these two aspects of the computation.

[Latecki, 1991] defines a general P-command relation.

2 We refer to [Fong, 1991] for experimental results on ef­ ficiency gains in parsing systems when filtering operations, such as computation of coreference, are applied as early as possible.

Definition 1 a P-commands f3 iff the first node with property P that properly dominates a also dominates {3 .

In this definition, the first node that dominates a means the parent of a. 3 Given the general P-command relation in Definition 1, Barker and Pullum 1990 also ar­ gue that the notion of c-command can be expressed as a special instance of it (Def.3), where property P is the property of being a branching node, i.e. having more than one child (Def.2).

Definition 2 M, the mother relation, is given by M ={(a, b)la >D b 1\ -,:J:z:[a >D x >D b] }

The notation a >D b means that a dominates b.

Definition 3 C-command is the (P-)command relation with property P1 , where P1 is given by P1 = {a l:lx, y[x :f. y A aMx A aMy]}

We now proceed to define other notions used for Bind­ ing theory.

Definition 4 a and f3 are coindeud iff a has index i and f3 has index j, and i=j.

Definition 5 a binds f3 iff a c-commands f3 and a and {3 are coindeud.

The indexing I and the pair (a, /3), a a node and f3 a: subtree, are compatible with respect to binding the­ ory (BT -compatible) if a satisfies the binding theory in the local domain f3 under the indexing I. The following definitions are adapted from [Chomsky, 1986]:171-72. 4

Definition 6 I is BT-compatible with (a, f3) if

A a is an anaphor and a is bound in f3 under I.

• B a is a pronominal and a is not bound in f3 under I.

Definition 6 states that the antecedent of an anaphor a must be inside a certain domain f3 (to be defined), while the antecedent (if any) of a a pronominal must be outside {3. The complementary distribution of anaphors and pronominals is thus captured.

Definition 7 Licensing condition for a category a by a lexical governing category -y in the expression E with indexing I:

For some f3 I is BT-compatible with (a, /3), for a an anaphor or pronominal, and f3 the mini­ mal Complete Functional Complex containing -y for which there is an indexing J, BT-compatible with (a, {3).

3 [Latecki, 1991] shows that Definition 1 is equivalent to the definition of P-command in [Barker and Pullum, 1990], but it is an improvement from a computational point of view, u, according to this definition, only one node beside the currently processed node needs to be checked to determine whether the P-command relation holds between a and j3, while in [Barker and Pullum, 1990] all nodes dominating a need to be checked.

4 For the moment, we can assume that anaphor11 and pronominal11 are give!J. by exhaustive listing. In the discussion that follows anaphors are words such as him11elj, them11elve11, each other, while pronouns are them, they, their11.

Definition 8 {Giorgi 1987) -y is a Complete Functional Complex {CFC) iff one of the following holds:

• (i) -y is the minimal domain in which all the thematic roles pertaining to a lexical head are assigned; 5
• (ii) -y is the minimal domain in which all the grammatical functions pertaining to that head are realized.

3 The Linguistic Evidence

The definitions given above correctly capture the follow­ ing cases, where a is the referring nominal expression. 6

Case 1 a is inside a VP and the local domain is the clause dominating the VP. If a is an anaphor, it can be coindexed with a c-commanding element, while if a is a pronominal it must be free.

1. a. I told them; about each other;.

b. * I told them; about them;. c. * They; thought that Bill liked each other;.

1. They; thought that Bill liked them;,;.
2. Case 2 a is the subject of a tensed clause. The local domain is the minimal clause containing a, since tensed inflection governs the subject position (as shown by Nominative Case (they) .) If a is an anaphor the sentence will be bad, as there is no possible c-commanding antecedent in the minimal domain, while if a is a pronoun it will be free, or coindexed with an element in a dominating clause.
3. a.*They; expected that(rpeach other; would win] b. They; expected that [rP they; would win J
4. Case 3 a is the subject of a tenseless clause. The local domain is the clause dominating the clause contain­ ing a. This result descends from the licensing condi­ tion, which requires that the local domain contains a lexical govenor for a. The subject of a tenseless clause is governed either by the verb or by the com­ plementizer (for) of the dominating clause, as shown by accusative Case (them).
5. a. They; expected (rP each other; to win ] b. * They; expected [rP them; to win ]

Case 4 a is inside an NP, the NP has a subject and a is in complement position. The local domain is the NP itself, the minimal CFC.

(6) a. They heard [NP my; stories about ourselves;] b. *They; heard [NP my stories about each other;] c. * They heard [NP John's; stories about him; ] d. Bill; heard [NP John's stories about him; J

Case 5 a is inside an NP, a is in complement position, but the NP has no subject. The local domain is the CFC containing the NP, namely the complete clause. 7

5 The relations between a lexical head, such as a noun or a verb, and its satellites are called thematic roles, for instance a transitive verb assigns the thematic relations of agent and patient to its arguments.

6 We use the symbol IP, for Inflection Phrase, to define a clause in the bracketed representation.

(8) a. They; heard [NP stories about each other; J b. * They; told [NP stories about him; ]

So far, all the cases have shown a complementary distribution of anaphors and pronouns, but in some cases pronouns and anaphors can occur in the same context, as shown by cases 6 and 7.

• Case 6 In this instance, a is the subject of an NP, and a is pronominal. The local domain is the NP.
• The children; like [NP their; friends]
• Case 7 a is the subject of the NP and a is anaphoric. The local domain is the clause containing the NP, because there is no BT-compatible indexation inside the NP itself.
• The children; like [NP each other's; friends]

4 The Algorithms

Other algorithms for the computational treatment of coreference have been proposed. We present a set of algorithms which capitalizes on previous work ([Giorgi et al., 1990; Ingria and Stallard, 1989; Barker and Pul­ lum, 1990; Latecki, 1991]), but it is different both in intent and practical features. Although [Ingria and Stal­ lard, 1989; Giorgi et al ., 1990] present interesting treat­ ments of co reference in the G B framework, both algo­ rithms operate on a tree which is already completely constructed. Neither algorithm then is compositional and incremental. [Fong, 1991] has shown that the point at which filtering principles of the grammar are applied can make order-of-magnitude differences in parsing time. An incremental approach is to be preferred as it supports early applications of grammatical filters, that reduce the computational space.

4.1 The C-command Algorithm

The proposal by [Latecki, 1991], to compute c-command incrementally is modified. [Latecki, 1991] claims that the proposed indexing technique can be computed while building the tree. The algorithm, however, relies on a strict preorder traversal of the tree. This restriction cannot be met easily by many parsing algorithms, thus the incrementality of the indexing technique is not suffi­ ciently general.

By using the definition of P-command relation from [Barker and Pullum, 1990], [Latecki, 1991] defines an in­ dexing procedure to encode P-command relations in a tree, and proves Theorem 1, reported below for clarity. (They correspond to Def.2.1 and Theorem 2.4 respec­ tively in [Latecki, 1991, p.53].)

7 1n this instance, an empty pronominal element can op­ tionally be inserted, thus inducing a smaller local domain, as case 5 reduces to case 4.

(7) a. They; heard [NP P ROi stories about them; ]

b. *They; heard [NP PRO; stories about them; ]

The sentence is grammatical only with the interpretation that the stories about them are not their &torie&, but &omeone el&e '& .

Definition 9 Let P be any property. The function indp: N ---+ F ( N) = { u <;; N : u is a finite subset of N} is defined recursively as follows:

• 1° indp(root(T)) ={1}, where root(T) denotes the root node.
• 2° if a immediately dominates (3, then indp(f3)= indp(a) U fp(f3)

where fp is a function fp: N---+ F(N), which fulfills the following conditions:

• 1 1 IfaCi.P, thenfp(a) = 0.
• 2 1 If aEP, then fp{a) = {r}, for some unique indez r E N, r ct U{fp(-y) : "Y E Nand -y :f. a}.

Theorem 1 Node a P-commands node (3 iff indp(a) · fp(a) <;; indp{f3).

The procedural interpretation of this definition is a two-step algorithm: one function, corresponding to fp, which assigns a new index to each node with property P, and another function which percolates these indices down the tree. This procedure requires that the mother is always built before its children. 8

We show how to interpret these definition with an in­ cremental and compositional algorithm, which is inter­ leaved in the structure~building operations of a licens­ ing parser. A licensing parser can perform the following three operations: project, attach as complement ("right and down"), attach as specifier ("left and up"). We present the pseudo-code for the algorithm, we show that it computes the function in Definition 9, (so that The­ orem 1, proved in [Latecki, 1991], also holds), and then we sketch an analysis of its complexity.

Algorithm 1 This procedure applies every time a pro­ jection is attached to the already built portion of the tree. Each node has two stores: one for the unique indezing assigned to the node (index}, the other for the set of in­ dices inherited by the parent node (index-set).

c-command-indexation(CurrentPtr:pointer) begin update-root-of-phrase(CurrentPtr) end (· Step h) update-root-of-phrase(PhrasePtr:pointer) begin if PhrasePtr.branching-flag = false then PhrasePtr.index <- get-nevindex end if PhrasePtr. branching-flag <- true

8 Latecki notices that Theorem 1 does not directly apply to c-command, as defined in [Reinhart, 1983]. This is because [Reinhart, 1983] includes two special cases: the relation be­ tween the two sentential projections CP and IP, and the case of so-called "Chomsky-adjunction" where a maximal projec­ tion is the daughter of a maximal projection of the same category. [Latecki, 1991] shows, however, that the indexins procedure can be extended. These two cases, are treated as special cases, in which the index assigned to the node by fp is not added to the indp set. This is not an unjustified solution as these two cases are indeed violation of the well-formedness conditions on phrase structure as expressed in X theory .

end

get-nevindex

(· generating function that outputs unique numerical indices ·)

(·Step 2·)

percolate-index-to-children(Root:pointer)

• (· any type of complete tree-traversal algorithm, which makes a copy of the nevindex for each traversed node, and assigns it to the indexset store, vith the exception of CP and Chomsky-adjunction

In practice, PhrasePtr can have two values in English. If the attachment is a complement attachment, it cor­ responds to the parent node of CurrentPtr, while if the attachment is as specifier, it is CurrentPtr itself. 9

This algorithm performs an indexation like the one defined in Definition 9. On inspection of the algorithm, we note that a node obtains a new index only if it has property P (since the algorithm is called only upon at­ tachment, and we are testing for property P of node a, o: a branching node, which is always true when the algo­ rithm is called.) Branching flag is an overloaded boolean variable which keeps track of wh~ther the algorithm has already applied to a given node or not . Thus Step 1 is function fp in Definition 9.

A node inherits a distinct index from all of its an­ cestors with property P, as a consequence of percolate­ indez-to-children, which is by definition a complete tree traversal of the subtree rooted at the parent of the node which has just been attached to the tree. Thus Step 2 of the algorithm is function indp in Definition 9.

Consider what happens at each type of attachment. T1 is the tree before the attachment, and N1 is the newly created projection. There are two cases.

Case 1: T1 attached as Specifier to N1

In this instance the new index of N 1 is percolated to all the nodes in T1 U N1,· as N1 becomes the root of the new tree. Hence, indp and fp hold for the attach as specifier operation. Iii = £NI

eln general, this value depends on the interaction of incre­ mental tree-building (necessarily from left to right) with the word order of the language. For example, in a language where the complement precedes its head, like German, CurrentPtr and PhrauPtr are equivalent. These cases are predictable. It is indeed not unexpected that it should be so, as inter­ leaving indexation and structure-building could not abstract from word order. ()f course, the generalisation is that the head of the phrase, for instance a verb in a VP, is always the root ( Phra&ePtr).

Nl is attached as complement at the right frontier of Tl. A new index is percolated to the subtree headed by the parent of N1, the node to which N1 has become complement. Since nodes are attached one by one, a new index is assigned to all the nodes rooted in a branching node, hence indp and fp hold for the attach as complement operation. Hence, Def­ inition 9 holds, and consequently, Theorem 1 holds as well.

To calculate the complexity of this operation of index­ ation, we take into consideration the number of times that all nodes are visited by the algorithm. We observe that a new index is generated and percolated down at each attachment which gives rise to a branching node. Thus, the worst case arises if a complete binary tree is traversed, because it has the greatest number of internal nodes. The total number of internal nodes of a complete binary tree is (n- 1)/2, for n leaves. Thus, the total number of updates is (n- 1)/2 x (n- 1)/2 = O(n 2 ) in the worst case. 10

4.2 The Local Domain

The computation of coreference involves nodes in a tree for which the c-command relation holds in a certain do­ main. Antecedents of coreferring expressions are not ex­ plicitly identified. [Giorgi et al., 1989] argue that this is the correct way of interpreting the purpose of a binding algorithm.

On the other hand, [Ingria and Stallard, 1989} claim that an algorithm that computes coreference must return as output both possible and impossible antecedents, to be useful for practical purposes. Following a procedu­ ral statement of binding theory [Chomsky, 1980], they present an algorithm where each nominal node in a tree is associated to two sets: the set of internal nodes to the local binding domain and the set of nodes ezternal to it . The extension of the binding domain is computed stati­ cally: each NP with a subject and each IP define a new domain. The algorithm performs a preorder traversal of the tree and updates the two sets of possible antecedents.

This algorithm is empirically insufficient in two cases: case 7 above, where the NP with a subject is not the local domain, and case 3, where IP is not the local do­ main either. 11 Nonetheless, the idea of computing sets of internal and external nodes is interesting, as it elim­ inates the need to traverse the tree upward each time an element that requires an antecedent is encountered (differently from [Giorgi et al., 1989).)

10 This measure is not affected by the fact that some nodes cover the empty string (which is a necessary property of these trees, since we are assuming GB theory). Each lexical token ( i.e. a word in the string) can license at most k empty cat­ egories, for ( k) very small, usually 3 or 4, which are in turn preterminal nodes, hence they do not license any other nodes. Thus, empty categories can increase the number of attach­ ments by only a (small) constant factor. (See [Correa, 1991], who establishes this upper bound.)

11 [Ingria and Stallard, 1989] acknowledge case 7 and do not

We propose an extension of [Ingria and Stallard, 1989], which deals correctly with the problematic cases men­ tioned above. On observation of the actual linguistic instances, illustrated in section 2 (derived from Defs. 68) , we notice that the current sentential node (IP) is a CFC in most cases. Thus it is the domain f3 in which Def. 6 applies, with the exception of cases 3 and 7. In the former case, IP does not count because it is an infini­ tival, in the latter case the NP, contained within the IP, is the local domain. This is possible only if the corefer­ ring expression is a pronoun, which can be not bound. 12 Computationally, the extent of the binding domain is, in part, a function of values which are known only when the input is seen ( i .e. whether the verb is ± Tense or whether the NP is ±pronominal ).

However, if the computation of the local domain, and the collection of possible/impossible antecedents is per­ formed on-line, then an upward traversal of the tree is necessary. In order to avoid this traversal , we propose an "off-line" approach. In the spirit of [Ingria and Stal­ lard, 1989), all the possible cases derivable from Defs. 7 and 8 are calculated, reaching a 3-way distinction. A number of global variables is set, which keeps track of all the potential local domains. For each of these local domains, the set of possible and impossible antecedents is calculated. The relevant local domain, with related antecedents, will be chosen when the actual referring ex­ pression is seen. Coreference can be established without traversing the tree.

Algorithm 2 This algorithm applies at each attach­ ment operation, if the node that is being attached is an NP.

update-coreference (· this procedure manipulates some global variables: external-current-ip, internal-current-ip: nodes; external-higher-ip, internal-higher-ip : nodes; external-current-np, internal-current-np: nodes; np-has-subject, np-has-no-subject : boolean; ·> (· case 3 ·) if attachment=specifier and head=non-tensed-i then (· local-domain<- higher-ip ·) if np = anaphor then possible-antecedents <- internal-higher-ip impossible-antecedents <- external-higher-ip else possible-antecedents <- external-higher-ip impossible-antecedents <- internal-higher-ip

(· case 4,7 ·) else if

(attachment=complement and head=n and np-has-subject) or (attachment = specifier and head = n ) then

treat case 3.

12 This descends from Def.7: for pronouns there always is a BT-compatible indexation, because they can be free, l.e. not coindexed.

(· local-domain<- current-np ·) if np = anaphor then possible-antecedents <- internal-current-np impossible-antecedents <- external-current-np else possible-antecedents <- external-current-np impossible-antecedents <- internal-current -np (· all other cases ·) else (· local-domain<- current-ip ·) if np = anaphor then possible-antecedents <- internal-current-ip impossible-antecedents <- external-current-ip else possible-antecedents <- external-current-ip impossible-antecedents <- internal-current-ip

Finally, consider how the sets of internal and external nodes are updated.

Algorithm 3 This algorithm applies at each attache· ment of NP.

For all the global pointers of local domain do if -pointer dominates new node then add new node to set of internal nodes else add new node to external nodes

On updating the pointers, the set of internal and ex­ ternal nodes are inherited by computing dominance. 13

5 Example

In this section we show how the percolation of the indices is done, and, for each step, what is the local domain defined by the algorithm. Sentence (5) is illustrated.

For each word in the input, and also for null strings postulated by the grammar, the parser projects a node. Clearly no attachment can occur until two nodes are pro­ jected. After an NP and an IP are projected, an attach­ ment as specifier is performed. Due to the attachment, · IP becomes a branching node, hence the index 1 is per­ colated, as shown. The local domain is the current IP, according to the third clause of algorithm 2. The NP is the only internal node, and there are no external nodes.

The verb expected is encountered, projected to a VP, and attached to the IP. No new indices are percolated, as IP was already a branching node. (This is computed by branching flag.) No changes occur to the local domain, as no NP nodes have been parsed. The partially built tree is shown below.

A new NP and a new inflectional, non-tensed node are parsed, projected to the maximal projection, and at­ tached in a specifier configuration. Percolation of indices is performed as in the first step. This configuration is shown here.

The two-node configuration built in the preceding step is attached as complement, and indices are percolated, since now VP is a branching node. The value of the local domain is the higher IP. They is an internal node, and there are no external nodes. The indexed tree is shown below.

Finally, the verb win is projected and attached, no new indices are generated. Binding of each other is possible by the higher they, since principle A of the binding the­ ory applies, and the binding is within the local domain, i.e. the anaphor is bound in the higher IP.

Conclusion In this paper we have illustrated two al­ gorithms to compute c-command and binding. We have shown that they work incrementally and can handle a few cases that previous proposals could not treat. Fu­ ture work is going to extend the algorithms beyond the core cases presented here, such as split antecedents and backward anaphora.