21.6.1 Pronominal Anaphora Baseline: The Hobbs Algorithm
The first of the three algorithms we present for pronominal anaphora resolution is the Hobbs algorithm. The Hobbs algorithm (the simpler of two algorithms presented originally in Hobbs (1978)) depends only on a syntactic parser plus a morphological gender and number checker. For this reason it is often used as a baseline when evaluating new pronominal anaphora resolution algorithms.
The input to the Hobbs algorithm is a pronoun to be resolved, together with a syntactic parse of the sentences up to and including the current sentence. The algorithm searches for an antecedent noun phrase in these trees. The intuition of the algorithm is to start with the target pronoun and walk up the parse tree to the root S. For each NP or S node that it finds, it does a breadth-first left-to-right search of the node's children to the left of the target. As each candidate noun phrase is proposed, it is checked for gender, number, and person agreement with the pronoun. If no referent is found, the algorithm performs the same breadth-first search on preceding sentences.
The Hobbs algorithm does not capture all the constraints and preferences on pronominalization described above. It does, however, approximate the binding theory, recency, and grammatical role preferences by the order in which the search is performed, and the gender, person, and number constraints by a final check.
An algorithm that searches parse trees must also specify a grammar, since the assumptions regarding the structure of syntactic trees will affect the results. A fragment for English that the algorithm uses is given in Figure 21.6. The steps of the Hobbs algorithm are as follows:
1. Begin at the noun phrase (NP) node immediately dominating the pronoun.
2. Go up the tree to the first NP or sentence (S) node encountered. Call this node X, and call the path used to reach it p.
S $ \rightarrow $ NP VP
NP $ \rightarrow $ $ \left\{
\begin{array}{l}
(Det) \text{ Nominal} \left( \left\{ PP \right\} \right)^{*} \\
\text{pronoun}
\end{array}
\right. $
Det $ \rightarrow $ $ \left\{
\begin{array}{l}
\text{determiner} \\
NP's
\end{array}
\right\} $
PP $ \rightarrow $ preposition NP
Nominal $ \rightarrow $ noun (PP) $ ^{*} $
Rel $ \rightarrow $ wh-word S
VP $ \rightarrow $ verb NP (PP) $ ^{*} $
Figure 21.6 A grammar fragment for the Tree Search algorithm.
3. Traverse all branches below node X to the left of path p in a left-to-right, breadth-first fashion. Propose as the antecedent any NP node that is encountered which has an NP or S node between it and X.
4. If node X is the highest S node in the sentence, traverse the surface parse trees of previous sentences in the text in order of recency, the most recent first; each tree is traversed in a left-to-right, breadth-first manner, and when an NP node is encountered, it is proposed as antecedent. If X is not the highest S node in the sentence, continue to step 5.
5. From node X, go up the tree to the first NP or S node encountered. Call this new node X, and call the path traversed to reach it p.
6. If X is an NP node and if the path p to X did not pass through the Nominal node that X immediately dominates, propose X as the antecedent.
7. Traverse all branches below node X to the left of path p in a left-to-right, breadth-first manner. Propose any NP node encountered as the antecedent.
8. If X is an S node, traverse all branches of node X to the right of path p in a left-to-right, breadth-first manner, but do not go below any NP or S node encountered. Propose any NP node encountered as the antecedent.
9. Go to Step 4.
Demonstrating that this algorithm yields the correct coreference assignments for an example sentence is left as Exercise 21.2.
Most parsers return number information (singular or plural), and person information is easily encoded by rule for the first and second person pronouns. But parsers for English rarely return gender information for common or proper nouns. Thus the only additional requirement to implementing the Hobbs algorithm, besides a parser, is an algorithm for determining gender for each antecedent noun phrase.
One common way to assign gender to a noun phrase is to extract the head noun, and then use WordNet (Ch. 19) to look at the hypernyns of the head noun. Ancestors like person or living thing indicate an animate noun. Ancestors like female indicate a female noun. A list of personal names associated with genders, or patterns like Mr. can also be used (Cardie and Wagstaff, 1999).
More complex algorithms exist, such as that of Bergsma and Lin (2006); Bergsma and Lin also make freely available a large list of nouns and their (automatically extracted) genders.