21.6.2 A Centering Algorithm for Anaphora Resolution
The Hobbs algorithm does not use an explicit representation of a discourse model. By contrast Centering theory, (Grosz et al., 1995b, henceforth GJW) is a family of models which has an explicit representation of a discourse model, and incorporates an additional claim: that there is a single entity being “centered” on at any given point in the discourse which is to be distinguished from all other entities that have been evoked. Centering theory has been applied to many problems in discourse, such as the computation of entity-based coherence; in this section we see its application to anaphora resolution.
There are two main representations tracked in the Centering theory discourse model. In what follows, take $ U_{n} $ and $ U_{n+1} $ to be two adjacent utterances. The backward looking center of $ U_{n} $, denoted as $ C_{b}(U_{n}) $, represents the entity currently being focused on in the discourse after $ U_{n} $ is interpreted. The forward looking centers of $ U_{n} $, denoted as $ C_{f}(U_{n}) $, form an ordered list containing the entities mentioned in $ U_{n} $, all of which could serve as the $ C_{b} $ of the following utterance. In fact, $ C_{b}(U_{n+1}) $ is by definition the most highly ranked element of $ C_{f}(U_{n}) $ mentioned in $ U_{n+1} $. (The $ C_{b} $ of the first utterance in a discourse is undefined.) As for how the entities in the $ C_{f}(U_{n}) $ are ordered, for simplicity's sake we can use the grammatical role hierarchy below. $ ^{3} $
subject > existential predicate nominal > object > indirect object or oblique > demarcated adverbial PP
As a shorthand, we will call the highest-ranked forward-looking center $ C_{p} $ (for “preferred center”).
We describe a centering-based algorithm for pronoun interpretation due to Brennan et al. (1987, henceforth BFP). (See also Walker et al. (1994) and the end of the chapter for other centering algorithms). In this algorithm, preferred referents of pronouns are computed from relations that hold between the forward and backward looking centers in adjacent sentences. Four intersentential relationships between a pair of utterances $ U_{n} $ and $ U_{n+1} $ are defined which depend on the relationship between $ C_{b}(U_{n+1}) $, $ C_{b}(U_{n}) $, and $ C_{p}(U_{n+1}) $; these are shown in Figure 21.7.
| | $ C_b(U_{n+1}) = C_b(U_n) $\nor undefined $ C_b(U_n) $ | $ C_b(U_{n+1}) \neq C_b(U_n) $ |
| --- | --- | --- |
| $ C_b(U_{n+1}) = C_p(U_{n+1}) $ | Continue | Smooth-Shift |
| $ C_b(U_{n+1}) \neq C_p(U_{n+1}) $ | Retain | Rough-Shift |
The following rules are used by the algorithm:
Rule 1: If any element of $ C_f(U_n) $ is realized by a pronoun in utterance $ U_{n+1} $, then $ C_b(U_{n+1}) $ must be realized as a pronoun also.
- Rule 2: Transition states are ordered. Continue is preferred to Retain is preferred to Smooth-Shift is preferred to Rough-Shift.
Having defined these concepts and rules, the algorithm is defined as follows.
1. Generate possible $ C_b - C_f $ combinations for each possible set of reference assignments.
2. Filter by constraints, e.g., syntactic coreference constraints, selectional restrictions, centering rules and constraints.
3. Rank by transition orderings.
The pronominal referents that get assigned are those which yield the most preferred relation in Rule 2, assuming that Rule 1 and other coreference constraints (gender, number, syntactic, selectional restrictions) are not violated.
Let us step through passage (21.66) to illustrate the algorithm.
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}) $
Using the grammatical role hierarchy to order the $ C_{f} $, for sentence $ U_{1} $ we get:
$ C_{f}(U_{1}) $: {John, Ford, dealership}
$ C_{p}(U_{1}) $: John
$ C_{b}(U_{1}) $: undefined
Sentence $ U_{2} $ contains two pronouns: he, which is compatible with John, and it, which is compatible with the Ford or the dealership. John is by definition $ C_{b}(U_{2}) $, because he is the highest ranked member of $ C_{f}(U_{1}) $ mentioned in $ U_{2} $ (since he is the only possible referent for he). We compare the resulting transitions for each possible referent of it. If we assume it refers to the Falcon, the assignments would be:
$ C_f(U_2) $: {John, Ford, Bob}
$ C_{p}(U_{2}) $: John
$ C_{b}(U_{2}) $: John
Result: Continue $ (C_{p}(U_{2})=C_{b}(U_{2});C_{b}(U_{1}) $ undefined)
If we assume it refers to the dealership, the assignments would be:
$ C_{f}(U_{2}) $: {John, dealership, Bob}
$ C_{p}(U_{2}) $: John
$ C_{b}(U_{2}) $: John
Result: Continue $ (C_{p}(U_{2})=C_{b}(U_{2});C_{b}(U_{1}) $ undefined)
Since both possibilities result in a Continue transition, the algorithm does not say which to accept. For the sake of illustration, we will assume that ties are broken in terms of the ordering on the previous $ C_f $ list. Thus, we will take it to refer to the Falcon instead of the dealership, leaving the current discourse model as represented in the first possibility above.
In sentence $U_{3}$, he is compatible with either John or Bob, whereas it is compatible with the Ford. If we assume he refers to John, then John is $C_{b}(U_{3})$ and the assignments would be:
$$ C_{f}(U_{3})\colon\{\mathrm{J o h n},\mathrm{F o r d}\} $$
$ C_{p}(U_{3}) $: John
$ C_{b}(U_{3}) $: John
$$ Result:Continue\quad(C_{p}(U_{3})=C_{b}(U_{3})=C_{b}(U_{2})) $$
If we assume he refers to Bob, then Bob is $ C_{b}(U_{3}) $ and the assignments would be:
$$ C_{f}(U_{3}):\{Bob,Ford\} $$
$ C_{p}(U_{3}) $: Bob
$$ C_{b}(U_{3})\colon\mathrm{B o b} $$
$$ Result:Smooth-Shift\quad(C_{p}(U_{3})=C_{b}(U_{3});C_{b}(U_{3})\neq C_{b}(U_{2})) $$
Since a Continue is preferred to a Smooth-Shift per Rule 2, John is correctly taken to be the referent.
The main salience factors that the centering algorithm implicitly incorporates include the grammatical role, recency, and repeated mention preferences. The manner in which the grammatical role hierarchy affects salience is indirect, since it is the resulting transition type that determines the final reference assignments. In particular, a referent in a low-ranked grammatical role will be preferred to one in a more highly ranked role if the former leads to a more highly ranked transition. Thus, the centering algorithm may incorrectly resolve a pronoun to a low salience referent. For instance, in example (21.67),
Bob opened up a new dealership last week. John took a look at the Fords in his lot. He ended up buying one.
the centering algorithm will assign Bob as the referent of the subject pronoun he in the third sentence – since Bob is $ C_b(U_2) $, this assignment results in a Continue relation whereas assigning John results in a Smooth-Shift relation. On the other hand, the Hobbs algorithm will correctly assign John as the referent.
Like the Hobbs algorithm, the centering algorithm requires a full syntactic parse as well as morphological detectors for gender.
Centering theory is also a model of entity coherence, and hence has implications for other discourse applications like summarization; see the end of the chapter for pointers.