21.2.2 Automatic Coherence Assignment

Given a sequence of sentences, how can we automatically determine the coherence relations between them? Whether we use RST, Hobbs, or one of the many other sets of relations (see the end of the chapter), we call this task coherence relation assignment. If we extend this task from assigning a relation between two sentences to the larger goal of extracting a tree or graph representing an entire discourse, the term discourse parsing is often used.

Both of these tasks are quite difficult, and remain unsolved open research problems. Nonetheless, a variety of methods have been proposed, and in this section we describe shallow algorithms based on cue phrases. In the following section we sketch a more sophisticated but less robust algorithm based on abduction.

A shallow cue-phrase-based algorithm for coherence extraction has three stages:

1. Identify the cue phrases in a text

2. Segment the text into discourse segments, using cue phrases

3. Classify the relationship between each consecutive discourse segment, using cue phrases.

We said earlier that a cue phrase (or discourse marker or cue word) is a word or phrase that functions to signal discourse structure, especially by linking together discourse segments. In Sec. 21.1 we mentioned cue phrases or features like joining us now is $ \langle PERSON\rangle $ (for broadcast news segmentation) or following word is the name of a neighborhood (for real estate ad segmentation). For extracting coherence relations, we rely on cue phrases called \textit{connectives}, which are often conjunctions or adverbs, and which give us a 'cue' to the coherence relations that hold between segments. For example, the connective because strongly suggests the EXPLANATION relation in passage (21.24).

(21.24) John hid Bill's car keys $ \underline{\text{because}} $ he was drunk.

Other such cue phrases include although, but, for example, yet, with, and and. Discourse markers can be quite ambiguous between these discourse uses and non-discourse related sentential uses. For example, the word with can be used as a cue phrase as in (21.25), or in a sentential use as in (21.26) $ ^{1} $:

With its distant orbit, Mars exhibits frigid weather conditions

We can see Mars with an ordinary telescope.

Some simple disambiguation of the discourse versus sentential use of a cue phrase can be done with simple regular expressions, once we have sentence boundaries. For example, if the words With or Yet are capitalized and sentence-initial, they tend to be discourse markers. The words because or where tend to be discourse markers if preceded by a comma. More complete disambiguation requires the WSD techniques of Ch. 20 using many other features. If speech is available, for example, discourse markers often bear different kinds of pitch accent than sentential uses (Hirschberg and Litman, 1993).

The second step in determining the correct coherence relation is to segment the text into discourse segments. Discourse segments generally correspond to clauses or sentences, although sometimes they are smaller than clauses. Many algorithms approximate segmentation by using entire sentences, employing the sentence segmentation algorithm of Fig. ?? (page ??), or the algorithm of Sec. ??.

Often, however, a clause or clause-like unit is a more appropriate size for a discourse segment, as we see in the following examples from Sporleder and Lapata (2004):

(21.28) [The ability to operate at these temperature is advantageous], [because the devices need less thermal insulation] (EXPLANATION)

One way to segment these clause-like units is to use hand-written segmentation rules based on individual cue phrases. For example, if the cue-phrase Because occurs sentence-initially and is eventually followed by a comma (as in (21.29)), it may begin a segment (terminated by the comma) that relates to the clause after the comma. If because occurs sentence-medially, it may divide the sentence into a previous and following discourse segment (as in (21.30)). These cases can be distinguished by handwritten rules based on punctuation and sentence boundaries.

(21.29) $ \underline{\text{Because}} $ of the low atmospheric pressure,] [any liquid water would evaporate instantly]

(21.30) [Any liquid water would evaporate instantly] $ \underline{\text{because}} $ of the low atmospheric pressure.]

If a syntactic parser is available, we can write more complex segmentation rules making use of syntactic phrases.

The third step in coherence extraction is to automatically classify the relation between each pair of neighboring segments. We can again write rules for each discourse marker, just as we did for determining discourse segment boundaries. Thus a rule could specify that a segmenting beginning with sentence-initial Because is a satellite in a CAUSE relationship with a nucleus segment that follows the comma.

In general, the rule-based approach to coherence extraction does not achieve extremely high accuracy. Partly this is because cue phrases are ambiguous; because, for example, can indicate both CAUSE and EVIDENCE, but can indicate CONTRAST, AN-TITHESIS, and CONCESSION, and so on. We need additional features than just the cue phrases themselves. But a deeper problem with the rule-based method is that many coherence relations are not signaled by cue phrases at all. In the RST corpus of Carlson et al. (2001), for example, Marcu and Echihabi (2002) found that only 61 of the 238 CONTRAST relations, and only 79 of the 307 EXPLANATION-EVIDENCE relations, were indicated by explicit cue phrases. Instead, many coherence relations are signalled by more implicit cues. For example, the following two sentences are in the CONTRAST relation, but there is no explicit in contrast or but connective beginning the second sentence:

(21.31) The $6 billion that some 40 companies are looking to raise in the year ending March 31 compares with only $2.7 billion raised on the capital market in the previous fiscal year

(21.32) In fiscal 1984 before Mr. Gandhi came to power, only $810 million was raised.

How can we extract coherence relations between discourse segments if no cue phrases exist? There are certainly many implicit cues that we could use. Consider the following two discourse segments:

(21.33) [I don't want a truck;] [I'd prefer a convertible.]

The CONTRAST relation between these segments is signalled by their syntactic parallelism, by the use of negation in the first segment, and by the lexical coordinate relation between convertible and truck. But many of these features are quite lexical,

requiring a large number of parameters which couldn't be trained on the small amount of labeled coherence relation data that currently exists.

This suggests the use of bootstrapping to automatically label a larger corpus with coherence relations that could then be used to train these more expensive features. We can do this by relying on discourse markers that are very strong unambiguous cues for particular relations. For example consequently is an unambiguous signal for RESULT, in other words for SUMMARY, for example for ELABORATION, and secondly for CONTINUATION. We write regular expressions to extract pairs of discourse segments surrounding these cue phrases, and then remove the cue phrases themselves. The resulting sentence pairs, without the cue phrases, are used as a supervised training set for these coherence relations.

Given this labeled training set, any supervised machine learning method may be used. Marcu and Echihabi (2002), for example, use a naive Bayes classifier based only on word-pair features $ (w_1, w_2) $, where the first word $ w_1 $ occurs in the first discourse segment, and the second $ w_2 $ occurs in the following segment. This feature captures lexical relations like convertible/truck above. Sporleder and Lascarides (2005) include other features, including individual words, parts of speech, or stemmed words in the left and right discourse segment. They found, for example, that words like other, still, and not were chosen by feature selection as good cues for CONTRAST. Words like so, indeed, and undoubtedly were chosen as cues for RESULT.

21.3 REFERENCE RESOLUTION

and even Stigand, the patriotic archbishop of Canterbury, found it advisable—

'Found WHAT?' said the Duck.

'Found IT,' the Mouse replied rather crossly: 'of course you know what "it" means.'

'I know what "it" means well enough, when I find a thing,' said the Duck: 'it's generally a frog or a worm. The question is, what did the archbishop find?

Lewis Carroll, Alice in Wonderland

In order to interpret the sentences of any discourse, we need to know who or what entity is being talked about. Consider the following passage:

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.

In this passage, each of the underlined phrases is used by the speaker to denote one person named Victoria Chen. We refer to this use of linguistic expressions like her or Victoria Chen to denote an entity or individual as reference. In the next few sections of this chapter we study the problem of reference resolution. Reference resolution is the task of determining what entities are referred to by which linguistic expressions.

We first define some terminology. A natural language expression used to perform reference is called a referring expression, and the entity that is referred to is called the referent. Thus, Victoria Chen and she in passage (21.34) are referring expressions, and Victoria Chen is their referent. (To distinguish between referring expressions and

their referents, we italicize the former.) As a convenient shorthand, we will sometimes speak of a referring expression referring to a referent, e.g., we might say that she refers to Victoria Chen. However, the reader should keep in mind that what we really mean is that the speaker is performing the act of referring to Victoria Chen by uttering she. Two referring expressions that are used to refer to the same entity are said to corefer; thus Victoria Chen and she corefer in passage (21.34). There is also a term for a referring expression that licenses the use of another, in the way that the mention of John allows John to be subsequently referred to using he. We call John the antecedent of he. Reference to an entity that has been previously introduced into the discourse is called anaphora, and the referring expression used is said to be anaphoric. In passage (21.34), the pronouns she and her, and the definite NP the 37-year-old are therefore anaphoric.

Natural languages provide speakers with a variety of ways to refer to entities. Say that your friend has a 1961 Ford Falcon automobile and you want to refer to it. Depending on the operative discourse context, you might say it, this, that, this car, that car, the car, the Ford, the Falcon, or my friend's car, among many other possibilities. However, you are not free to choose between any of these alternatives in any context. For instance, you cannot simply say it or the Falcon if the hearer has no prior knowledge of your friend's car, it has not been mentioned before, and it is not in the immediate surroundings of the discourse participants (i.e., the situational context of the discourse).

The reason for this is that each type of referring expression encodes different signals about the place that the speaker believes the referent occupies within the hearer's set of beliefs. A subset of these beliefs that has a special status form the hearer's mental model of the ongoing discourse, which we call a discourse model (Webber, 1978). The discourse model contains representations of the entities that have been referred to in the discourse and the relationships in which they participate. Thus, there are two components required by a system to successfully interpret (or produce) referring expressions: a method for constructing a discourse model that evolves with the dynamically-changing discourse it represents, and a method for mapping between the signals that various referring expressions encode and the hearer's set of beliefs, the latter of which includes this discourse model.

We will speak in terms of two fundamental operations to the discourse model. When a referent is first mentioned in a discourse, we say that a representation for it is evoked into the model. Upon subsequent mention, this representation is accessed from the model. The operations and relationships are illustrated in Figure 21.5. As we will see in Sec. 21.8, the discourse model plays an important role in how coreference algorithms are evaluated.

We are now ready to introduce two reference resolution tasks: coreference resolution and pronominal anaphora resolution. Coreference resolution is the task of finding referring expressions in a text that refer to the same entity, i.e. finding expressions that corefer. We call the set of coreferring expressions a coreference chain. For example, in processing (21.34), a coreference resolution algorithm would need to find four coreference chains:

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. { herpay }

4. { Lotsabucks }

Coreference resolution thus requires finding all referring expressions in a discourse, and grouping them into coreference chains. By contrast, pronominal anaphora resolution is the task of finding the antecedent for a single pronoun; for example, given the pronoun her, our task is to decide that the antecedent of her is Victoria Chen. Thus pronominal anaphora resolution can be viewed as a subtask of coreference resolution. $ ^{2} $

In the next section we introduce different kinds of reference phenomena. We then give various algorithms for reference resolution. Pronominal anaphora has received a lot of attention in speech and language processing, and so we will introduce three algorithms for pronoun processing: the Hobbs algorithm, a Centering algorithm, and a log-linear (MaxEnt) algorithm. We then give an algorithm for the more general coreference resolution task.

We will see that each of these algorithms focuses on resolving reference to entities or individuals. It is important to note, however, that discourses do include reference to many other types of referents than entities. Consider the possibilities in example (21.35), adapted from Webber (1991).

(21.35) According to Doug, Sue just bought a 1961 Ford Falcon.

a. But that turned out to be a lie.

b. But that was false.

c. That struck me as a funny way to describe the situation.

d. That caused a financial problem for Sue.

The referent of that is a speech act (see Ch. 24) in (21.35a), a proposition in (21.35b), a manner of description in (21.35c), and an event in (21.35d). The field awaits the development of robust methods for interpreting these types of reference.

21.4 REFERENCE PHENOMENA

The set of referential phenomena that natural languages provide is quite rich indeed. In this section, we provide a brief description of several basic reference phenomena, surveying five types of referring expression: indefinite noun phrases, definite noun phrases, pronouns, demonstratives, and names. We then summarize the way these referring expressions are used to encode given and new information, along the way introducing two types of referents that complicate the reference resolution problem: inferrables and generics.