21.6.4 Features
Some commonly used features for pronominal anaphora resolution between a pronoun $ Pro_{i} $ and a potential referent $ NP_{j} $ include:
1. strict gender [true or false]. True if there is a strict match in gender (e.g. male pronoun $ Pro_{i} $ with male antecedent $ NP_{j} $).
2. compatible gender [true or false]. True if $ Pro_i $ and $ NP_j $ are merely compatible (e.g. male pronoun $ Pro_i $ with antecedent $ NP_j $ of unknown gender).
3. strict number [true or false] True if there is a strict match in number (e.g. singular pronoun with singular antecedent)
4. compatible number [true or false]. True if $ Pro_i $ and $ NP_j $ are merely compatible (e.g. singular pronoun $ Pro_i $ with antecedent $ NP_j $ of unknown number).
5. sentence distance [0, 1, 2, 3,...]. The number of sentences between pronoun and potential antecedent.
6. Hobbs distance [0, 1, 2, 3,...]. The number of noun groups that the Hobbs algorithm has to skip, starting backwards from the pronoun Pro_{i}, before the potential antecedent NP_{j} is found.
7. grammatical role [subject, object, PP]. Whether the potential antecedent is a syntactic subject, direct object, or is embedded in a PP.
8. linguistic form [proper, definite, indefinite, pronoun]. Whether the potential antecedent $ NP_j $ is a proper name, definite description, indefinite NP, or a pronoun.
Fig. 21.8 shows some sample feature values for potential antecedents for the final He in $ U_{3} $:
John saw a beautiful 1961 Ford Falcon at the used car dealership. $ (U_{1}) $
He showed it to Bob. $ (U_{2}) $
He bought it. $ (U_{3}) $
The classifier will learn weights indicating which of these features are more likely to be good predictors of a successful antecedent (e.g. being nearby the pronoun, in
| | He $ U_2 $ | it $ U_2 $ | Bob $ U_2 $ | John $ U_1 $ |
| --- | --- | --- | --- | --- |
| strict number | 1 | 1 | 1 | 1 |
| compatible number | 1 | 1 | 1 | 1 |
| strict gender | 1 | 0 | 1 | 1 |
| compatible gender | 1 | 0 | 1 | 1 |
| sentence distance | 1 | 1 | 1 | 2 |
| Hobbs distance | 2 | 1 | 0 | 3 |
| grammatical role | subject | object | PP | subject |
| linguistic form | pronoun | pronoun | proper | proper |
subject position, agreeing in gender and number). Thus where the Hobbs and Centering algorithms rely on hand-built heuristics for antecedent selection, the machine learning classifiers learn the importance of these different features based on their co-occurrence in the training set.
21.7 COREFERENCE RESOLUTION
In the previous few sections, we concentrated on interpreting a particular subclass of the reference phenomena that we outlined in Sec. 21.4: the personal pronouns such as he, she, and it. But for the general coreference task we'll need to decide whether any pair of noun phrases corefer. This means we'll need to deal with the other types of referring expressions from Sec. 21.4, the most common of which are definite noun phrases and names. Let's return to our coreference example, repeated below:
Victoria Chen, Chief Financial Officer of Megabucks Banking Corp since 2004, saw her pay jump 20%, to 1.3 million, as $ \underline{\text{the 37-year-old}} $ also became $ \underline{\text{the Denver-based financial-services company's president}} $. It has been ten years since $ \underline{\text{she}} $ came to Megabucks from rival Lotsabucks.
Recall that we need to extract four coreference chains from this data:
1. { Victoria Chen, Chief Financial Officer of Megabucks Banking Corp since 1994, her, the 37-year-old, the Denver-based financial-services company's president, She}
2. { Megabucks Banking Corp, the Denver-based financial-services company, Megabucks }
3. { her pay }
4. { Lotsabucks }
As before, we have to deal with pronominal anaphora (figuring out that her refers to Victoria Chen). And we still need to filter out non-referential pronouns like the pleonastic It in It has been ten years), as we did for pronominal anaphora.
But for full NP coreference we'll also need to deal with definite noun phrases, to figure out that the 37-year-old is coreferent with Victoria Chen, and the Denver-based financial-services company is the same as Megabucks. And we'll need to deal with names, to realize that Megabucks is the same as Megabucks Banking Corp.
An algorithm for coreference resolution can use the same log-linear classifier architecture we saw for pronominal anaphora. Thus we'll build a binary classifier which is given an anaphor and a potential antecedent and returns true (the two are coreferential) or false (the two are not coreferential). We'll use this classifier in the resolution algorithm as follows. We process a document from left to right. For each $ NP_{j} $ we encounter, we'll search backwards through the document examining each previous NP. For each such potential antecedent $ NP_{i} $, we'll run our classifier, and if it returns true, we successfully coindex $ NP_{i} $ and $ NP_{j} $. The process for each $ NP_{j} $ terminates when we either find a successful antecedent $ NP_{i} $ or reach the beginning of the document. We then move on to the next anaphor $ NP_{j} $.
In order to train our binary coreference classifier, just as for pronoun resolution, we’ll need a labeled training set in which each anaphor $ NP_i $ has been linked by hand with the correct antecedent. In order to build a classifier, we’ll need both positive and negative training examples of coreference relations. A positive examples for $ NP_i $ is the noun phrase $ NP_j $ which is marked as coindexed. We get negative examples by pairing the anaphor $ NP_j $ with the intervening NPs $ NP_{i+1} $, $ NP_{i+2} $ which occur between the true antecedent $ NP_i $ and the anaphor $ NP_i $.
Next features are extracted for each training observation, and a classifier is trained to predict whether an $ (NP_j, NP_i) $ pair corefer or not. Which features should we use in the binary coreference classifier? We can use all the features we used for anaphora resolution; number, gender, syntactic position, and so on. But we will also need to add new features to deal with phenomena that are specific to names and definite noun phrases. For example, we'll want a feature representing the fact that Megabucks and Megabucks Banking Corp share the word Megabucks, or that Megabucks Banking Corp and the Denver-based financial-services company both end in words (Corp and company) indicating a corporate organization.
Here are some commonly used features for coreference between an anaphor $ NP_{i} $ and a potential antecedent $ NP_{j} $ (in addition to the features for pronominal anaphora resolution listed on page 29):
1. anaphor edit distance [0,1,2,...,]. The character minimum edit distance from the potential antecedent to the anaphor. Recall from Ch. 3 that the character minimum edit distance is the minimum number of character editing operations (insertions, substitutions, deletions) necessary to turn one string into another. More formally,
$$ 100\times\frac{m-(s+i+d)}{m} $$
given the antecedent length $m$, and the number of substitutions $s$, insertions $i$, and deletions $d$.
2. antecedent edit distance [0,1,2,...,]. The minimum edit distance from the anaphor to the antecedent. Given the anaphor length n:
$$ 100\times\frac{n-\left(s+i+d\right)}{n} $$
3. alias [true or false]: A multi-part feature proposed by Soon et al. (2001) which requires a named entity tagger. Returns true if $ NP_i $ and $ NP_j $ are both named
entities of the same type, and $ NP_{i} $ is an alias of $ NP_{j} $. The meaning of alias depends on the types; two dates are aliases of each other if they refer to the same date. For type PERSON, prefixes like Dr. or Chairman are stripped off and then the NPs are checked to see if they are identical. For type ORGANIZATION, the alias function checks for acronyms (e.g., IBM for International Business Machines Corp).
4. appositive [true or false]: True if the anaphor is in the syntactic apposition relation to the antecedent. For example the NP Chief Financial Officer of Megabucks Banking Corp is in apposition to the NP Victoria Chen. These can be detected using a parser, or more shallowly by looking for commas and requiring that neither NP have a verb and one of them be a name.
5. linguistic form [proper, definite, indefinite, pronoun]. Whether the potential anaphor $ NP_{j} $ is a proper name, definite description, indefinite NP or a pronoun.
21.8 EVALUATING COREFERENCE RESOLUTION
One standard way of evaluating coreference is the Model-Theoretic coreference scoring scheme (Vilain et al., 1995), originally proposed for the MUC-6 and MUC-7 information extraction evaluation (Sundheim, 1995).
The evaluation is based on a human-labeled gold standard for coreference between referring expressions. We can represent this gold information as a set of identity links between referring expressions. For example, the fact that referring expression A and referring expression B are coreferent could be represented as a link A-B. If A, B, and C are coreferent, this can be represented as the two links A-B, B-C (or alternatively as A-C, B-C). We can call this set of correct links the reference or key set of links. Similarly, the hypothesis or response from a coreference algorithm can be viewed as a set of links.
What we'd like to do is compute the precision and recall of the response links against the key links. But recall that if entities A, B, and C are coreferent in the key, this can be represented either via (A-B, B-C) or via (A-C, B-C). As long as our coreference system correctly figures out that A, B, and C are coreferent, we don't want to penalize it for representing this fact in a different set of links than happen to be in the key.
For example, suppose that A, B, C, and D are coreferent, and this happens to be represented in the key by links (A-B, B-C, C-D). Suppose further that a particular coreference algorithm returns (A-B, C-D). What score should be given to this response? Intuitively the precision should be 1 (since both links correctly join referring expressions that indeed corefer). The recall should be 2/3, since intuitively it takes three links to correctly indicate that 4 expressions are coreferent, and the algorithm returned two of these three links. The details of this intuition are fleshed out in the Vilain et al. (1995) algorithm, which is based on computing the number of equivalence classes of expressions generated by the key.
21.9 ADVANCED: INFERENCE-BASED COHERENCE RESOLUTION
The algorithms we have seen in this chapter for the resolution of coherence and coreference have relied solely on shallow information like cue phrases and other lexical and simple syntactic cues. But many problems in resolution seem to require much more sophisticated kinds of knowledge. Consider the following example of coreference, adapted from Winograd (1972):
(21.70) The city council denied the demonstrators a permit because
a. they feared violence.
b. they advocated violence.
Determining the correct antecedent for the pronoun they requires understanding first that the second clause is intended as an Explanation of the first clause, and also that city councils are perhaps more likely than demonstrators to fear violence, and demonstrators might be more likely to advocate violence. A more advanced method for coherence resolution might assign this Explanation relation and in doing so help us figure out the referents of both pronouns.
We might perform this kind of more sophisticated coherence resolution by relying on the semantic constraints that are associated with each coherence relation, assuming a parser that could assign a reasonable semantics to each clause.
Applying these constraints requires a method for performing inference. Perhaps the most familiar type of inference is \textit{deduction}; recall from Sec. \ref{sec:thecentralrule} of \textit{deduction} is \textit{modus ponens}:
An example of modus ponens is the following:
All Falcons are fast.
John's car is an Falcon.
John's car is fast.
SOUND INFERENCE
Deduction is a form of sound inference: if the premises are true, then the conclusion must be true.
However, much of language understanding is based on inferences that are not sound. While the ability to draw unsound inferences allows for a greater range of inferences to be made, it can also lead to false interpretations and misunderstandings. A method for such inference is logical abduction (Peirce, 1955). The central rule of abductive inference is:
$$ \begin{array}{r} \alpha \Rightarrow \beta \\ \hline \beta \end{array} $$
Whereas deduction runs an implication relation forward, abduction runs it backward, reasoning from an effect to a potential cause. An example of abduction is the following:
All Falcons are fast.
John's car is fast.
John's car is an Falcon.
Obviously, this may be an incorrect inference: John's car may be made by another manufacturer yet still be fast.
In general, a given effect $ \beta $ may have many potential causes $ \alpha_i $. We generally will not want to merely reason from a fact to a possible explanation of it, we want to identify the best explanation of it. To do this, we need a method for comparing the quality of alternative abductive proofs. This can be done with probabilistic models (Charniak and Goldman, 1988; Charniak and Shimony, 1990), or with heuristic strategies (Charniak and McDermott, 1985; Chapter 10), such as preferring the explanation with the smallest number of assumptions, or the most specific explanation. We will illustrate a third approach to abductive interpretation, due to Hobbs et al. (1993), which applies a more general cost-based strategy that combines features of the probabilistic and heuristic approaches. To simplify the discussion, however, we will largely ignore the cost component of the system, keeping in mind that one is nonetheless necessary.
Hobbs et al. (1993) apply their method to a broad range of problems in language interpretation; here we focus on its use in establishing discourse coherence, in which world and domain knowledge are used to determine the most plausible coherence relation holding between utterances. Let us step through the analysis that leads to establishing the coherence of passage (21.4). First, we need axioms about coherence relations themselves. Axiom (21.71) states that a possible coherence relation is the Explanation relation; other relations would have analogous axioms.
$$ \forall e_{i},e_{j}{~E x p l a n a t i o n}(e_{i},e_{j})\;\Rightarrow\;{C o h e r e n c e R e l}(e_{i},e_{j}) $$
The variables $ e_{i} $ and $ e_{j} $ represent the events (or states) denoted by the two utterances being related. In this axiom and those given below, quantifiers always scope over everything to their right. This axiom tells us that, given that we need to establish a coherence relation between two events, one possibility is to abductively assume that the relation is Explanation.
The Explanation relation requires that the second utterance express the cause of the effect that the first sentence expresses. We can state this as axiom (21.72).
$$ \forall e_{i},e_{j}{~c a u s e}(e_{j},e_{i})\;\Rightarrow\;{E x p l a n a t i o n}(e_{i},e_{j}) $$
In addition to axioms about coherence relations, we also need axioms representing general knowledge about the world. The first axiom we use says that if someone is drunk, then others will not want that person to drive, and that the former causes the latter (for convenience, the state of not wanting is denoted by the diswant predicate).
$$ \begin{array}{c}\forall x,y,e_{i}\ drunk(e_{i},x)\ \Rightarrow\\ \exists e_{j},e_{k}\ diswant(e_{j},y,e_{k})\land drive(e_{k},x)\land cause(e_{i},e_{j})\end{array} $$
Before we move on, a few notes are in order concerning this axiom and the others we will present. First, axiom (21.73) is stated using universal quantifiers to bind several of the variables, which essentially says that in all cases in which someone is drunk, all people do not want that person to drive. Although we might hope that this is generally the case, such a statement is nonetheless too strong. The way in which this is handled in the Hobbs et al. system is by including an additional relation, called an etc predicate, in the antecedent of such axioms. An etc predicate represents all the other properties that must be true for the axiom to apply, but which are too vague to state explicitly. These predicates therefore cannot be proven, they can only be assumed at a corresponding cost. Because rules with high assumption costs will be dispreferred to ones with low costs, the likelihood that the rule applies can be encoded in terms of this cost. Since we have chosen to simplify our discussion by ignoring costs, we will similarly ignore the use of etc predicates.
Second, each predicate has what may look like an “extra” variable in the first argument position; for instance, the drive predicate has two arguments instead of one. This variable is used to reify the relationship denoted by the predicate so that it can be referred to from argument places in other predicates. For instance, reifying the drive predicate with the variable $ e_k $ allows us to express the idea of not wanting someone to drive by referring to it in the final argument of the diswant predicate.
Picking up where we left off, the second world knowledge axiom we use says that if someone does not want someone else to drive, then they do not want this person to have his car keys, since car keys enable someone to drive.
$$ \begin{array}{c}\forall x,y,e_{j},e_{k}\ diswant(e_{j},y,e_{k})\land drive(e_{k},x)\Rightarrow\\\exists z,e_{l},e_{m}\ diswant(e_{l},y,e_{m})\land have(e_{m},x,z)\\\land carkeys(z,x)\land cause(e_{j},e_{l})\end{array} $$
The third axiom says that if someone doesn't want someone else to have something, he might hide it from him.
$$ \forall x,y,z,e_{l},e_{m}\ d i s w a n t(e_{l},y,e_{m})\land h a v e(e_{m},x,z) \Rightarrow \exists e_{n}\ h i d e(e_{n},y,x,z)\land c a u s e(e_{l},e_{n}) $$
The final axiom says simply that causality is transitive, that is, if $ e_i $ causes $ e_j $ and $ e_j $ causes $ e_k $, then $ e_i $ causes $ e_k $.
$$ \forall e_{i},e_{j},e_{k}{~c a u s e}(e_{i},e_{j})\land{c a u s e}(e_{j},e_{k})\;\Rightarrow\;{c a u s e}(e_{i},e_{k}) $$
Finally, we have the content of the utterances themselves, that is, that John hid Bill's car keys (from Bill),
(21.77) hide(e_{1}, John, Bill, ck) \land carkeys(ck, Bill)
and that someone described using the pronoun “he” was drunk; we will represent the pronoun with the free variable he.
(21.78) drunk( $ e_{2} $, he)
We can now see how reasoning with the content of the utterances along with the aforementioned axioms allows the coherence of passage (21.4) to be established under the Explanation relation. The derivation is summarized in Figure 21.9; the sentence interpretations are shown in boxes. We start by assuming there is a coherence relation, and using axiom (21.71) hypothesize that this relation is Explanation,
(21.79) Explanation $ (e_{1}, e_{2}) $
which, by axiom (21.72), means we hypothesize that
(21.80) \quad cause(e_{2}, e_{1}) $
holds. By axiom (21.76), we can hypothesize that there is an intermediate cause $ e_{3} $,
(21.81) $ cause(e_2, e_3) \land cause(e_3, e_1) $
and we can repeat this again by expanding the first conjunct of (21.81) to have an intermediate cause $ e_4 $.
(21.82) \quad \textit{cause}(e_{2}, e_{4}) \land \textit{cause}(e_{4}, e_{3})
We can take the hide predicate from the interpretation of the first sentence in (21.77) and the second cause predicate in (21.81), and, using axiom (21.75), hypothesize that John did not want Bill to have his car keys:
(21.83) diswant( $ e_{3} $, John, $ e_{5} $) $ \land $ have( $ e_{5} $, Bill, ck)
From this, the carkeys predicate from (21.77), and the second cause predicate from (21.82), we can use axiom (21.74) to hypothesize that John does not want Bill to drive:
(21.84) \quad \text{diswant}(e_{4}, \text{John}, e_{6}) \land \text{drive}(e_{6}, \text{Bill}) \)
From this, axiom (21.73), and the second cause predicate from (21.82), we can hypothesize that Bill was drunk:
(21.85) drunk(e2, Bill)
But now we find that we can “prove” this fact from the interpretation of the second sentence if we simply assume that the free variable he is bound to Bill. Thus, the establishment of coherence has gone through, as we have identified a chain of reasoning between the sentence interpretations – one that includes unprovable assumptions about axiom choice and pronoun assignment – that results in $ cause(e_2, e_1) $, as required for establishing the Explanation relationship.
This derivation illustrates a powerful property of coherence establishment, namely its ability to cause the hearer to infer information about the situation described by the discourse that the speaker has left unsaid. In this case, the derivation required the assumption that John hid Bill's keys because he did not want him to drive (presumably out of fear of him having an accident, or getting stopped by the police), as opposed to some other explanation, such as playing a practical joke on him. This cause is not stated anywhere in passage (21.4); it arises only from the inference process triggered
by the need to establish coherence. In this sense, the meaning of a discourse is greater than the sum of the meanings of its parts. That is, a discourse typically communicates far more information than is contained in the interpretations of the individual sentences that comprise it.
We now return to passage (21.5), repeated below as (21.87), which was notable in that it lacks the coherence displayed by passage (21.4), repeated below as (21.86).
John hid Bill's car keys. He was drunk.
37) ?? John hid Bill's car keys. He likes spinach.
We can now see why this is: there is no analogous chain of inference capable of linking the two utterance representations, in particular, there is no causal axiom analogous to (21.73) that says that liking spinach might cause someone to not want you to drive. Without additional information that can support such a chain of inference (such as the aforementioned scenario in which someone promised John spinach in exchange for hiding Bill's car keys), the coherence of the passage cannot be established.
Because abduction is a form of unsound inference, it must be possible to subsequently retract the assumptions made during abductive reasoning, that is, abductive inferences are defeasible. For instance, if passage (21.86) was followed by sentence (21.88),
Bill's car isn't here anyway; John was just playing a practical joke on him.
the system would have to retract the original chain of inference connecting the two clauses in (21.86), and replace it with one utilizing the fact that the hiding event was part of a practical joke.
In a more general knowledge base designed to support a broad range of inferences, one would want axioms that are more general than those we used to establish the coherence of passage (21.86). For instance, consider axiom (21.74), which says that if you do not want someone to drive, then you do not want them to have their car keys. A more general form of the axiom would say that if you do not want someone to perform an action, and an object enables them to perform that action, then you do not want them to have the object. The fact that car keys enable someone to drive would then be
encoded separately, along with many other similar facts. Likewise, axiom (21.73) says that if someone is drunk, you don't want them to drive. We might replace this with an axiom that says that if someone does not want something to happen, then they don't want something that will likely cause it to happen. Again, the facts that people typically don't want other people to get into car accidents, and that drunk driving causes accidents, would be encoded separately.
While it is important to have computational models that shed light on the coherence establishment problem, large barriers remain for employing this and similar methods on a wide-coverage basis. In particular, the large number of axioms that would be required to encode all of the necessary facts about the world, and the lack of a robust mechanism for constraining inference with such a large set of axioms, makes these methods largely impractical in practice. Nonetheless, approximations to these kinds of knowledge and inferential rules can already play an important role in natural language understanding systems.
21.10 PSYCHOLINGUISTIC STUDIES OF REFERENCE AND COHERENCE
To what extent do the techniques described in this chapter model human discourse comprehension? We summarize here a few selected results from the substantial body of psycholinguistic research; for reasons of space we focus here solely on anaphora resolution.
A significant amount of work has been concerned with the extent to which people use the preferences described in Section 21.5 to interpret pronouns, the results of which are often contradictory. Clark and Sengal (1979) studied the effects that sentence recency plays in pronoun interpretation using a set of reading time experiments. After receiving and acknowledging a three sentence context to read, human subjects were given a target sentence containing a pronoun. The subjects pressed a button when they felt that they understood the target sentence. Clark and Sengal found that the reading time was significantly faster when the referent for the pronoun was evoked from the most recent clause in the context than when it was evoked from two or three clauses back. On the other hand, there was no significant difference between referents evoked from two clauses and three clauses back, leading them to claim that “the last clause processed grants the entities it mentions a privileged place in working memory”.
Crawley et al. (1990) compared the grammatical role parallelism preference with a grammatical role preference, in particular, a preference for referents evoked from the subject position of the previous sentence over those evoked from object position. Unlike previous studies which conflated these preferences by considering only subject-to-subject reference effects, Crawley et al. studied pronouns in object position to see if they tended to be assigned to the subject or object of the last sentence. They found that in two task environments – a question answering task which revealed how the human subjects interpreted the pronoun, and a referent naming task in which the subjects identified the referent of the pronoun directly – the human subjects resolved pronouns to the subject of the previous sentence more often than the object.
However, Smyth (1994) criticized the adequacy of Crawley et al.'s data for evaluating the role of parallelism. Using data that met more stringent requirements for assessing parallelism, Smyth found that subjects overwhelmingly followed the parallelism preference in a referent naming task. The experiment supplied weaker support for the preference for subject referents over object referents, which he posited as a default strategy when the sentences in question are not sufficiently parallel.
Caramazza et al. (1977) studied the effect of the “implicit causality” of verbs on pronoun resolution. Verbs were categorized in terms of having subject bias or object bias using a sentence completion task. Subjects were given sentence fragments such as (21.89).
John telephoned Bill because he
The subjects provided completions to the sentences, which identified to the experimenters what referent for the pronoun they favored. Verbs for which a large percentage of human subjects indicated a grammatical subject or object preference were categorized as having that bias. A sentence pair was then constructed for each biased verb: a “congruent” sentence in which the semantics supported the pronoun assignment suggested by the verb’s bias, and an “incongruent” sentence in which the semantics supported the opposite prediction. For example, sentence (21.90) is congruent for the subject-bias verb “telephoned”, since the semantics of the second clause supports assigning the subject John as the antecedent of he, whereas sentence (21.91) is incongruent since the semantics supports assigning the object Bill.
(21.90) John telephoned Bill because he wanted some information.
(21.91) John telephoned Bill because he withheld some information.
In a referent naming task, Caramazza et al. found that naming times were faster for the congruent sentences than for the incongruent ones. Perhaps surprisingly, this was even true for cases in which the two people mentioned in the first clause were of different genders, thus rendering the reference unambiguous.
Matthews and Chodorow (1988) analyzed the problem of intrasentential reference and the predictions of syntactically-based search strategies. In a question answering task, they found that subjects exhibited slower comprehension times for sentences in which a pronoun antecedent occupied an early, syntactically deep position than for sentences in which the antecedent occupied a late, syntactically shallow position. This result is consistent with the search process used in Hobbs's tree search algorithm.
There has also been psycholinguistic work concerned with testing the principles of centering theory. In a set of reading time experiments, Gordon et al. (1993) found that reading times were slower when the current backward-looking center was referred to using a full noun phrase instead of a pronoun, even though the pronouns were ambiguous and the proper names were not. This effect – which they called a repeated name penalty – was found only for referents in subject position, suggesting that the $ C_b $ is preferentially realized as a subject. Brennan (1995) analyzed how choice of linguistic form correlates with centering principles. She ran a set of experiments in which a human subject watched a basketball game and had to describe it to a second person. She found that the human subjects tended to refer to an entity using a full noun phrase in subject position before subsequently pronominalizing it, even if the referent had already been introduced in object position.
21.11 SUMMARY
In this chapter, we saw that many of the problems that natural language processing systems face operate between sentences, that is, at the discourse level. Here is a summary of some of the main points we discussed:
- Discourses, like sentences, have hierarchical structure. In the simplest kind of structure detection, we assume a simpler linear structure, and segment a discourse on topic or other boundaries. The main cues for this are lexical cohesion as well as discourse markers/cue phrases.
Discourses are not arbitrary collections of sentences; they must be coherent. Among the factors that make a discourse coherent are coherence relations between the sentences and entity-based coherence.
- Various sets of coherence relations and rhetorical relations have been proposed. Algorithms for detecting these coherence relations can use surface-based cues (cue phrases, syntactic information).
- Discourse interpretation requires that one build an evolving representation of discourse state, called a discourse model, that contains representations of the entities that have been referred to and the relationships in which they participate.
- Natural languages offer many ways to refer to entities. Each form of reference sends its own signals to the hearer about how it should be processed with respect to her discourse model and set of beliefs about the world.
- Pronominal reference can be used for referents that have an adequate degree of salience in the discourse model. There are a variety of lexical, syntactic, semantic, and discourse factors that appear to affect salience.
- The Hobbs, Centering, and Log-linear models for pronominal anaphora offer different ways of drawing on and combining various of these constraints.
- The full NP coreference task also has to deal with names and definite NPs. String edit distance is a useful feature for these.
- Advanced algorithms for establishing coherence apply constraints imposed by one or more coherence relations, often leads to the inference of additional information left unsaid by the speaker. The unsound rule of logical abduction can be used for performing such inference.
BIBLIOGRAPHICAL AND HISTORICAL NOTES
Building on the foundations set by early systems for natural language understanding (Woods et al., 1972; Winograd, 1972; Woods, 1978), much of the fundamental work in computational approaches to discourse was performed in the late 70's. Webber's (1978, 1983) work provided fundamental insights into how entities are represented in the discourse model and the ways in which they can license subsequent reference. Many of the examples she provided continue to challenge theories of reference to this day. Grosz (1977) addressed the focus of attention that conversational participants
maintain as the discourse unfolds. She defined two levels of focus; entities relevant to the entire discourse were said to be in global focus, whereas entities that are locally in focus (i.e., most central to a particular utterance) were said to be in immediate focus. Sidner (1979, 1983) described a method for tracking (immediate) discourse foci and their use in resolving pronouns and demonstrative noun phrases. She made a distinction between the current discourse focus and potential foci, which are the predecessors to the backward and forward looking centers of centering theory respectively.
The roots of the centering approach originate from papers by Joshi and Kuhn (1979) and Joshi and Weinstein (1981), who addressed the relationship between immediate focus and the inferences required to integrate the current utterance into the discourse model. Grosz et al. (1983) integrated this work with the prior work of Sidner and Grosz. This led to a manuscript on centering which, while widely circulated since 1986, remained unpublished until Grosz et al. (1995b). A series of papers on centering based on this manuscript/paper were subsequently published (Kameyama, 1986; Brennan et al., 1987; Di Eugenio, 1990; Walker et al., 1994; Di Eugenio, 1996; Strube and Hahn, 1996; Kehler, 1997a, inter alia). A collection of later centering papers appears in Walker et al. (1998), and see Poesio et al. (2004) for more recent work. We have focused in this chapter on Centering and anaphora resolution; Sse Karamanis (2003, 2007), Barzilay and Lapata (2007) and related papers discussed in Ch. 23 for the application of Centering to entity-based coherence.
There is a long history in linguistics of studies of information status (Chafe, 1976; Prince, 1981; Ariel, 1990; Prince, 1992; Gundel et al., 1993; Lambrecht, 1994, inter alia).
Beginning with Hobbs's (1978) tree-search algorithm, researchers have pursued syntax-based methods for identifying reference robustly in naturally occurring text. An early system for a weighted combination of different syntactic and other features was Lappin and Leass (1994), which we described in detail in our first edition. Kennedy and Boguraev (1996) describe a similar system that does not rely on a full syntactic parser, but merely a mechanism for identifying noun phrases and labeling their grammatical roles. Both approaches use Alshawi's (1987) framework for integrating salience factors. An algorithm that uses this framework for resolving references in a multimodal (i.e., speech and gesture) human-computer interface is described in Huls et al. (1995). A discussion of a variety of approaches to reference in operational systems can be found in Mitkov and Boguraev (1997).
Methods for reference resolution based on supervised learning were proposed quite early (Connolly et al., 1994; Aone and Bennett, 1995; McCarthy and Lehnert, 1995; Kehler, 1997b; Ge et al., 1998, inter alia). More recently both supervised and unsupervised approaches have received a lot of research attention, focused both on anaphora resolution Kehler et al. (2004), Bergsma and Lin (2006) and full NP coreference (Cardie and Wagstaff, 1999; Ng and Cardie, 2002b; Ng, 2005). For definite NP reference, there are general algorithms (Poesio and Vieira, 1998; Vieira and Poesio, 2000), as well as specific algorithms that focus on deciding if a particular definite NP is anaphoric or not (Bean and Riloff, 1999, 2004; Ng and Cardie, 2002a; Ng, 2004).
Mitkov (2002) is an excellent comprehensive overview of anaphora resolution.
The idea of using cohesion for linear discourse segmentation was implicit in the groundbreaking work of (Halliday and Hasan, 1976), but was first explicitly imple-
mented by Morris and Hirst (1991), and quickly picked up by many other researchers, including (Kozima, 1993; Reynar, 1994; Hearst, 1994, 1997; Reynar, 1999; Kan et al., 1998; Choi, 2000; Choi et al., 2001; Brants et al., 2002; Bestgen, 2006). Power et al. (2003) studies discourse structure, while Filippova and Strube (2006), Sporleder and Lapata (2004, 2006) focus on paragraph segmentation.
The use of cue phrases in segmentation has been widely studied, including work on many textual genres as well as speech (Passonneau and Litman, 1993; Hirschberg and Litman, 1993; Manning, 1998; Kawahara et al., 2004)
Many researchers have posited sets of coherence relations that can hold between utterances in a discourse (Halliday and Hasan, 1976; Hobbs, 1979; Longacre, 1983; Mann and Thompson, 1987; Polanyi, 1988; Hobbs, 1990; Sanders et al., 1992; Carlson et al., 2001, 2002; Asher and Lascarides, 2003; Baldridge et al., 2007, inter alia). A compendium of over 350 relations that have been proposed in the literature can be found in Hovy (1990).
There are a wide variety of approaches to coherence extraction. The cue-phrase based model described in Sec. 21.2.2 is due to Daniel Marcu and colleagues (Marcu, 2000b, 2000a; Carlson et al., 2001, 2002). The Linguistic Discourse Model (Polanyi, 1988; Scha and Polanyi, 1988; Polanyi et al., 2004a, 2004b) is a framework in which discourse syntax is more heavily emphasized; in this approach, a discourse parse tree is built on a clause-by-clause basis in direct analogy with how a sentence parse tree is built on a constituent-by-constituent basis. Corston-Oliver (1998) also explores explores syntactic and parser-based features. A more recent line of work has applied a version of the tree-adjoining grammar formalism to discourse parsing (Webber et al., 1999; Webber, 2004). This model has also been used to annotate the Penn Discourse Treebank (Miltsakaki et al., 2004b, 2004a). See Asher and Lascarides (2003) and Baldridge et al. (2007) on Segmented Discourse Representation Structure (SDRT). Wolf and Gibson (2005) argue that coherence structure includes crossed bracketsing which make it impossible to represent as a tree, and propose a graph representation instead.
In addition to determining discourse structure and meaning, theories of discourse coherence have been used in algorithms for interpreting discourse-level linguistic phenomena, including pronoun resolution (Hobbs, 1979; Kehler, 2000), verb phrase ellipsis and gapping (Prüst, 1992; Asher, 1993; Kehler, 1993, 1994a), and tense interpretation (Lascarides and Asher, 1993; Kehler, 1994b, 2000). An extensive investigation into the relationship between coherence relations and discourse connectives can be found in Knott and Dale (1994).
EXERCISES
21.1 Early work in syntactic theory attempted to characterize rules for pronominalization through purely syntactic means. A rule was proposed in which a pronoun was interpreted by deleting it from the syntactic structure of the sentence that contains it, and replacing it with the syntactic representation of the antecedent noun phrase.
Explain why the following sentences (called “Bach-Peters” sentences) are problematic for such an analysis:
(21.92) The man who deserves it gets the prize he wants.
(21.93) The pilot who shot at it hit the MIG that chased him.
What other types of reference discussed on pages 18–21 are problematic for this type of analysis?
21.2 Draw syntactic trees for example (21.66) on page 27 and apply Hobbs's tree search algorithm to it, showing each step in the search.
21.3 Hobbs (1977) cites the following examples from his corpus as being problematic for his tree-search algorithm:
(21.94) The positions of pillars in one hall were marked by river boulders and a shaped convex cushion of bronze that had served as $ \underline{\text{their}} $ footings.
(21.95) They were at once assigned an important place among the scanty remains which record the physical developments of the human race from the time of $ \underline{\text{its}} $ first appearance in Asia.
(21.96) Sites at which the coarse grey pottery of the Shang period has been discovered do not extend far beyond the southernmost reach of the Yellow river, or westward beyond $ \underline{\text{its}} $ junction with the Wei.
(21.97) The thin, hard, black-burnished pottery, made in shapes of angular profile, which archaeologists consider as the clearest hallmark of the Lung Shan culture, developed in the east. The site from which $ \underline{\text{it}} $ takes its name is in Shantung. $ \underline{\text{It}} $ is traced to the north-east as far as Liao-ning province.
(21.98) He had the duty of performing the national sacrifices to heaven and earth: his role as source of honours and material rewards for services rendered by feudal lords and ministers is commemorated in thousands of inscriptions made by the recipients on bronze vessels which were eventually deposited in $ \underline{\text{their}} $ graves.
In each case, identify the correct referent of the underlined pronoun and the one that the algorithm will identify incorrectly. Discuss any factors that come into play in determining the correct referent in each case, and what types of information might be necessary to account for them.
21.4 Implement the Hobbs algorithm. Test it on a sample of the Penn TreeBank. You will need to modify the algorithm to deal with differences between the Hobbs and TreeBank grammars.