2 Error analysis by mention type

We begin with an error analysis, inspired by and building on a number of previous analyses of errors in various coreference systems. For example, Stoyanov et al. (Reference Stoyanov, Gilbert, Cardie and Riloff2009) analyzed the performance of an early coreference resolution system by resolution classes. They found that proper nouns were easier to resolve than common nouns, that third person ungendered pronouns (it and they) were the most difficult to resolve, and that the accuracy of mention detection played a huge role in system performance.

The difficulty of pronouns has been confirmed by a number of previous analyses. Kummerfeld and Klein (Reference Kummerfeld and Klein2013) analyzed missing or extra mentions and mis-clustered entities, showing, e.g., the important role of pleonastic pronouns (you, it) in errors. Martschat and Strube (2014, 2015) propose a framework for comparing coreference errors, and evaluate such errors for entity-pair systems, finding that pronouns, and especially third-person genderless pronouns (it, they) are a particularly large sources of errors. Wiseman et al. (Reference Wiseman, Rush, Shieber and Weston2015) also found that pleonastic pronoun mentions constitute a particularly large source of errors.

Other error analyses have pointed to large number of errors in common nouns. Recasens et al. (Reference Recasens, Can and Jurafsky2013) showed that a particularly large source of error is caused by trying to link common noun mentions that do not have overlapping head words, e.g., app and software, a finding replicated also by Wiseman et al. (Reference Wiseman, Rush, Shieber and Weston2015).

In this section, we categorize errors by mention type, following these previous models, but focusing on a state-of-the-art sieve approach, and using an oracle method to investigate which words and situations are most problematic for each type of mention. An analysis by type has a particular advantage in our work because, unlike for most of the other systems previously analyzed, it aligns directly with our system components; e.g., many errors coming from resolving second person pronouns would suggest improvements in the pronoun–resolution component.

We investigate the following types of errors (examples in Table 1):

• • Mention detection: Errors in detecting correct mention spans or referentiality, including false positives that are singletons (whether non-referential or just mentioned once in the document), and false negatives (missed mentions) that are mention recall errors.

• • Proper–Proper: Errors when both mention and correct antecedent are proper nouns.

• • Common–Common: Errors between two common-noun mentions.

• • Proper–Common: Errors between a proper-noun antecedent and common-noun mention.

• • List–List: Missing or incorrect links between mentions in lists or enumerations.

• • AnyType–Pronoun: Pronoun resolution errors, with any type of antecedent. This includes errors in detecting generic pronouns.

Table 1.

Examples of coreference resolution errors, by type

Prior error analyses have generally drawn conclusions by studying the frequency of errors of different types. But in many coreference systems, and especially in entity-based systems like ours, errors influence each other; fixing one type of error could thus change the proportions of other errors. We, therefore, propose to directly study the impact of different errors on final system performance by using a partial oracle system. The partial oracle maintains the same sieves as the actual system, except the component being analyzed, which is replaced with perfect decisions.

We compare the best rule-based system (Lee et al. Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013), which serves as the starting point of our proposal, against these partial oracle systems. For example, to analyze proper–common errors, this oracle replaces system decisions with gold (perfect) decisions when resolving a common-noun mention with a proper-noun antecedent. This comparison lets us quantify ‘missed opportunities’ from each component, and, consequently, the upper limit of coreference performance if the component had been perfect.Footnote ¹

We perform this error analysis on the development partition of the CoNLL 2012 Shared Task dataset (Pradhan et al. Reference Pradhan, Moschitti, Xue, Uryupina and Zhang2012). This data is a combination of newswire, broadcast news, weblog, telephone conversation, etc. The number of tokens in the development dataset is 160 K (222 documents).

Table 2 lists the result of this experiment, from which we draw the following observations:

1. (1) The most significant errors come from mention detection, followed by pronoun and common–common errors, consistent with previous error analyses. We discuss each below.

2. (2) The mention detection oracle has a considerably higher score than the current system, consistent with the results of Stoyanov et al. (Reference Stoyanov, Gilbert, Cardie and Riloff2009) and others. This is because the mention detection oracle solves two difficult tasks: (a) identifying correct mention spans (requiring perfect parses), and (b) determining referentiality of mentions. To understand the distribution of these errors, we conducted two further oracle experiments. In the mention recall experiment, we added all mentions missed by the system (this fixes error type (a) above). In the singleton detection experiment, we used gold data to mark a mention as singleton or not, since singleton mentions are not coreferent with any other mentions in the corresponding document (this fixes error type (b)). We found significantly more errors for error type (b), highlighting the difficulty of detecting referentiality; indeed, this is actually a good part of the coreference resolution problem itself, and previous error analyses have emphasized its importance (Wiseman et al. Reference Wiseman, Rush, Shieber and Weston2015). Mention recall errors are largely caused by parsing errors (Kummerfeld and Klein Reference Kummerfeld and Klein2013). The fact that the performance improvement for this oracle is low indicates that parsing is already robust enough for this task. All in all, this clearly shows that mention detection is not a trivial task, and there is clear room for improvement.

3. (3) As mentioned, pronominal resolution errors are the dominant error in coreference linking. The need for improvements in pronominal resolution has been reported for earlier systems and is a consistent theme in other analyses. The dominant pronominal error are the third person it and they mentions. The it errors are mainly due to failures of detecting pleonastic it pronouns, suggesting that the pleonastic pronoun detection in the deterministic system— a set of syntactic and lexical patterns drawing on earlier sets of patterns for pleonastic detection like Lappin and Leass (Reference Lappin and Leass1994)—has insufficient accuracy. The they errors are caused by the ambiguity in gender and animacy of the pronoun they, which can corefer with most plural nouns, or (singular or plural) organizations.

4. (4) Common–common errors are the third most dominant error type. This is due to the high frequency of the common–common coreferential links. But these errors are important also because these links likely require semantics for correct resolution, to understand, e.g., that victim and casualty are synonyms (Recasens, Can and Jurafsky Reference Recasens, Can and Jurafsky2013).

5. (5) While there are fewer errors involving proper-nouns than those involving common-nouns, consistent with all previous research, there are still enough that need to be addressed.

6. (6) A few rule-based sieves—such as the speaker-based sieve, which focuses on first- and second-person pronouns that appear in dialogue—work very well. For example, we generally solve first- and second-person pronouns within one F1 point of the oracle system. This highlights that rule-based methods are not to be ignored: they perform very well when they need to manage few features and when the context can be modeled deterministically (e.g., speaker turns in dialogue).

Table 2.

Error analysis of the rule-based system showing performance increase of the partial oracle

The score difference indicates the upper limit of improvement we can achieve by fixing the corresponding error type. The → indicates a subclass of the error type listed immediately above. The last rows containing pronoun types include all wordform variants with the same lemma, including accusative and reflexive pronouns. For example, the I row includes also my, me and myself.

In summary, the analysis suggests that while rule-based sieves perform well in certain situations, they have strong limitations when they need to manage a large lexical feature space, which is required for a better mention detection or pronominal resolution. This larger message hints toward a hybrid solution, which combines ML for scenarios that require many features with rule-based components for scenarios that may be complex but can be unambiguously modeled by a domain expert.

In the next section, we describe such a hybrid approach, implemented in the same sieve architecture, which offers the right balance of simplicity (sieves can be independently constructed by different researchers), and power (incrementally building entity clusters allows the extraction of complex, global features patterns).

3 The hybrid architecture

The architecture of our model draws on the sieve architecture of Lee et al. (Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013), with the goal of maintaining the elements that made that architecture successful, while incorporating ML to address the problems identified in the error analysis above.

Like the Lee et al. (Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013) model, we apply a series of resolution models sequentially, ordering the models so as to keep the precision in the earlier sieves as high as possible. while injecting the maximum amount of information on entities as early as possible. This strategy allows this model to incrementally gather reliable information about the entities in text and use it to guide future decisions.Footnote ²

Our hybrid architecture consists of a series of seven sieves. Drawing on the insights of Chen and Ng (Reference Chen and Ng2012), we combined both rule-based and statistical sieves. Our final system combines two rule-based sieves and five statistical sieves trained by supervised ML, as shown in Figure 1. This architecture is simpler than the one proposed by Lee et al. (Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013) (it has seven sieves, whereas Lee et al.’s has ten), yet, as we show later, it performs considerably better.

Fig. 1.

Proposed hybrid architecture combining deterministic and statistical sieves.

The five statistical sieves are each designed around a particular mention type: proper nouns, common nouns, mixes of the two, lists, and pronouns. Thus, the proper-proper sieve is dedicated to resolving links from proper-noun mentions to proper-noun antecedents. The idea for this modular architecture comes from Ratinov and Roth (Reference Ratinov and Roth2012), who, drawing on the earlier work of Denis and Baldridge (Reference Denis and Baldridge2008), suggested that re-organizing sieves according to mention type allows them to differently weight features that may behave very differently for each type. Our results support Ratinov and Roth’s finding; as we will see, lexical semantic features like word vectors are important for common nouns, while grammatical structure and morphological attributes are more important for pronouns.

Although our work thus draws heavily on the Ratinov and Roth (Reference Ratinov and Roth2012) statistical sieve models and other early work, we do explore some new architectural elements.

One is the classifiers themselves. Our approach is a hybrid one, combining rule-based and ML-based sieves, whereas the Ratinov and Roth model, for example, focuses on ML models alone. As we show below in our ablation study, combining rule- and ML-based components yields the best overall performance. We also used random forests for all the statistical classifiers, unlike earlier models, which tend to use linear classifiers. Previous research has suggested that successful ML coreference resolution is particularly dependent on feature conjunction: individual features don’t give strong signals for coreference (Wiseman et al. Reference Wiseman, Rush, Shieber and Weston2015); this may explain the strong performance of deterministic systems, in which rule-writers can build rules that explicitly conjoin large numbers of features. Random forests, like all classifiers built on decision trees, very naturally model very larger numbers of conjoined features. Our experiments validate this observation the approach that relies on random forests outperforms considerably the approach where the statistical classifiers are implemented using linear classifiers.

Our model incorporates a different decision model than that of Ratinov and Roth (Reference Ratinov and Roth2012). Similar to Lee et al. (Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013), our model commits to decisions at the end of sieves, while Ratinov and Roth allow early decisions to be overridden by following sieves. Our model is thus less powerful, but has the advantage of less complicated book-keeping. As we show, our approach achieves state-of-the-art performance despite the simpler model. Similar to Ratinov and Roth (Reference Ratinov and Roth2012), our hybrid model creates training data for a given sieve from the output of the previous sieves. This approach thus allows each sieve to be individually optimized on the appropriate examples in the context in which they appear in an actual disambiguation scenario. Similar to previous work, we found that this paradigm yields better performance.

Finally, we augmented the mention detection component of the new system, since we found that mention detection is one of the biggest sources of errors. We introduce a novel hybrid mention detector, which uses a rule-based component to propose mention candidates, and a ML component to disambiguate between multiple spans that share the same headword.

We note that our strategy that focuses on decomposing the task into simpler subtasks and using decision trees or deterministic models to address them differs considerably from recent trends in using neural networks for coreference resolution. For example, Wiseman et al. (Reference Wiseman, Rush and Shieber2016) use recurrent neural networks to capture global representations of entity clusters directly from their mentions. Clark and Manning (Reference Clark and Manning2016) use a deep reinforcement learning approach to directly optimize a neural mention-ranking model for coreference resolution. Clark and Manning (Reference Clark and Manning2016) currently obtain the best performance on the English and Chinese portions of the CoNLL 2012 dataset. However, while neural-network approaches tend to perform well, they produce models that are hard to interpret, which increases their long-term maintenance cost (Sculley et al. Reference Sculley, Holt, Golovin, Davydov, Phillips, Ebner, Chaudhary and Young2014). Our approach mitigates this cost by producing a series of simpler models that are easier to interpret, as they rely either on deterministic approaches, or on decision trees that can be analyzed by human domain experts.

In the following subsections, we describe our mention detection strategy, followed by details of our proposed sieves.

3.1 Mention detection

As we have shown in Section 2, mention detection is the most significant source of errors in the rule-based system. Mention detection is complicated by the following two issues:

First, identifying singleton mentions improves the system’s performance considerably, as shown in Table 2. However, in practice, few coreference resolution approaches identify singleton mentions ahead of time, because this is a complex task that is nearly identical to the complete coreference resolution problem, i.e., it requires the exploration of all possible antecedents, just not the selection of one. Following previous work, we also defer this decision to the subsequent sieves (see below).

Second, identifying correct mention spans is complicated by the imperfect syntax produced by existing parsers. For example, in the text the car was stopped by [[a security guard] at the intersection of the road towards Disney], the parser incorrectly attached the PP at the intersection of the road towards Disney to the NP a security guard, instead of the verb. The mention detection component thus had difficulty deciding the end boundary for the mention headed by guard (see the two closing brackets). Choosing the wrong boundary is a considerable error, because it generates both a false positive (the longer mention) and a false negative (the shorter mention).

We propose a hybrid approach for mention detection that addresses the above issues with a combination of deterministic rules (driven by syntax) and statistical decisions to handle ambiguities. Our approach starts by marking most noun phrase (NP) constituents, named entities, and pronouns as mention candidates. We filter these candidates using a minimal set of exclusion rules: (a) following the OntoNotes annotation guidelines (BBN Technologies 2006; Pradhan et al. Reference Pradhan, Hovy, Marcus, Palmer, Ramshaw and Weischedel2007), we discard adjectival forms of nations or nationality acronyms (e.g., American, U.S., U.K.); and (b) we remove the following stop words: there, etc., ltd., ’s, hmm, mm, ahem, um.

The second component of our mention detection algorithm deploys a statistical classifier to identify correct mention boundaries when there are multiple mention candidates sharing the same headword, e.g., as in the security guard example above. In this situation, a binary classifier is deployed to select a single mention from all candidates sharing the same head word. Table 3 lists the features used by this classifier.

Table 3.

Features used by mention span classifier

Our mention candidate list is by design over-inclusive. We let the following coreference resolution sieves handle the incorrect mentions in this candidate list by eventually marking them as singletons (i.e., by not linking them with any other mentions), which are removed from the output in a post-processing step.

3.3 Statistical sieves

Motivated by the sieve architecture of Ratinov and Roth (Reference Ratinov and Roth2012) and our error analysis, we introduce five statistical sieves. Each error class from Section 2 corresponds to a distinct statistical sieve (or pass) in Figure 1. As Ratinov and Roth (Reference Ratinov and Roth2012) and Denis and Baldridge (Reference Denis and Baldridge2008) propose, designing sieves by mention class allows us to incorporate different knowledge into each sieve that is specifically useful for resolving mentions of that types. For example, linking common nouns requires synonym information that is computable from word vectors, whereas finding the antecedent of a pronoun requires information on attributes like animacy. We detail next the resolution algorithm, i.e., deciding if two given mentions belong to the same cluster or not at prediction time, followed by the training process for the statistical sieves, and the features used.

3.3.1 Resolution

Figure 2 illustrates the resolution algorithm that is used for all statistical sieves. When resolving a mention, (e.g., his in the example in the figure), the sieve attempts to link the mention to all possible antecedents within a certain sentence range. The sentence range may be different between sieves (d_i indicates the sentence–distance range for the ith pass). Antecedents that are out of range are not considered. The antecedent candidate that yields a coreference link generated with the highest confidence (the president in the second sentence in Figure 2) is selected as the antecedent. We control for link over-generation by imposing a minimal confidence threshold, that, again, is specific to each sieve (t_i : merging threshold for ith pass). If no confidence value is larger than t_i , then no coreferent antecedent is selected for the corresponding mention, i.e., the mention is currently considered a singleton (this state may change in the subsequent sieves). All d_i and t_i hyper-parameters are tuned on the OntoNotes development set. Importantly, we use both mention-pair and cluster-pair features for all statistical sieves (see Section 3.4).

Fig. 2.

Resolution in a statistical sieve, with mention subscript indices (and different colors) indicating current mention clusters. The example—the resolution of his in line 3—shows the classification of potential antecedent The question. The system ultimately chooses the higher confidence answer (the president).

3.3.2 Training

Each statistical sieve trains on the output produced by the previous sequence of sieves on the training data. Thus, at each pass, a sieve is exposed to a list of mentions and a set of (partial) clusters that group the mentions according to decisions of the previous sieves. From this data, for each mention, we extract at most one positive (coreferent) and possibly multiple negative (non-coreferent) training data points consisting of the pair of the corresponding mention and one antecedent, where the antecedent must appear within the sentence range for this sieve.

For the coreference resolution task, the number of negative training examples is considerably larger than the number of positive examples (the former is quadratic in the number of mentions in a document, whereas the latter is linear). To mitigate excessive training times and to guarantee that the task fits in memory, we implemented a subsampling process for negative examples. We deploy this subsampling component for the sieves where the number of negative examples is excessive (currently the proper–proper and common–common sieves). The subsampling process is the following:

1. (1) We start by training a classifier for the relevant sieve using all positive examples gathered for all mentions in the training dataset, and a random subsample of twenty per cent of the negative examples.

2. (2) We then inspect the classifier confidence values (estimated probabilities) for all the negative examples, and keep only the top twenty per cent most-ambiguous negative examples, i.e., whose confidence values for belonging to the positive class is high. We train the final classifier using these more informative negative examples and all positive examples.

   This method is conceptually similar to methods that favor training examples near the class boundaries (Burges Reference Burges1998).

All classifiers are implemented using random forests (Breiman Reference Breiman2001). The only hyper-parameters tuned were the percentage of features to be used for each split point, and the number of individual decision trees.Footnote ⁴

3.4 Features

We list in Table 4 the features used by all statistical sieves. As the table shows, features may exploit information that is local to the mention (M), or that is global, from the currently available cluster of mentions pointing to the same entity (E). For example, one feature aggregates gender information from all the mentions in the antecedent’s cluster.

Table 4.

Features (using entity (E) or mention (M) information) that compare an anaphor mention with a candidate antecedent; showing in the second column sample features extracted between Kostunica and him in the given example document

We incorporated all the features used by the rules in Lee et al. (Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013)’s system, plus part-of-speech and lexical features from Durrett and Klein (Reference Durrett and Klein2013)’s system and word-embedding features from Mikolov et al. (Reference Mikolov, Sutskever, Chen, Corrado and Dean2013) to model semantic similarity. The vectors were generated with the skip-gram model using 200 dimensions over the English Gigaword dataset (LDC2011T07). The features that use these vectors include the Euclidean distance between the vector representations of headwords, first and last words in mention/antecedent, immediately preceding and following words, and average distances of all words in both mentions.

Importantly, each statistical sieve uses a selected subset of this feature space, only retaining features that occur at least twenty times in the training data and have a pointwise mutual information (between feature and corresponding class) over 0.0001 (chosen by coarse tuning on the development dataset). As we show in the next section, the sieves adapt to their corresponding tasks by choosing very different features.

3.5 Coreference resolution using dependency-based syntax

The proposed coreference system (similar to most others) uses a constituent parser for several purposes. These include extracting NP for mention detection, finding headwords that are required by various sieves, and finding syntactic relations such as apposition, which are used in the precise syntactic constructions sieve.

Our analysis of the run time of the end-to-end coreference resolution system revealed that the syntactic parser dominates the execution time: on average, eighty-one per cent of the run time is spent on constituent parsing. This is because the constituent-based syntactic parser used in our system (Klein and Manning Reference Klein and Manning2003) relies on probabilistic context free grammars (PCFG), which are applied using a chart-based dynamic programming algorithm with a runtime complexity of O(N ³), where N is the number of words per sentence. By contrast, the actual coreference resolution algorithm has a theoretical runtime complexity of O(M ²), where M is the number of mentions in a document, because a mention could be linked to any other mention in the document. Furthermore, in practice, this is O(M), because we constrain the search for antecedents to a small number of preceding sentences.

While there are more efficient algorithms for constituent parsing (Petrov and Klein Reference Petrov and Klein2007; Roark and Hollingshead Reference Roark and Hollingshead2008; Yi et al. Reference Yi, Lai, Petrov and Keutzer2011), in general, dependency parsing is faster (Cer et al. Reference Cer, Marneffe, Jurafsky and Manning2010). Unlike the constituent-based representation, the dependency-based representation is flat, i.e., each node (or word) is connected to other nodes by a directed grammatical relation such as nominal subject. An example contrasting the two syntactic representations is shown in Figure 3. Because of this simpler representation, dependency parsers using the shift-reduce algorithm achieve state-of-the-art performance at a run time linear in the sentence length (Chen and Manning Reference Chen and Manning2014). Previous work has shown that, despite their simplicity, these dependency parsers perform similarly with constituent parsers for more complex language processing tasks such as discourse parsing (Surdeanu, Hicks and Valenzuela-Escárcega Reference Surdeanu, Hicks and Valenzuela-Escárcega2015).

Fig. 3.

Parse trees for the sentence ‘The Constitution does not expressly give the president such power.’ (a) Constituency tree. (b) Dependency tree, using Stanford dependencies.

3.5.1 Using a dependency parser instead of a constituency parser

While the above analysis of run times is good motivation for switching to dependency-based syntax, this implies several non-trivial changes throughout the coreference resolution system. We discuss them below. We chose the Stanford dependency representation (de Marneffe and Manning Reference de Marneffe and Manning2008) as our new syntactic representation. We generate it in two different ways. For the runtime analysis, we generate Stanford dependencies directly by replacing our original constituent parser (Klein and Manning Reference Klein and Manning2003) with the dependency parser of Chen and Manning (Reference Chen and Manning2014). For the qualitative comparison against other systems that evaluated on the CoNLL 2012 shared task data (Pradhan et al. Reference Pradhan, Moschitti, Xue, Uryupina and Zhang2012), we start with the constituent parse trees that are included in the dataset and were used by all previous work, and convert them to Stanford dependencies using software included in the CoreNLP toolkit (Manning et al. Reference Manning, Surdeanu, Bauer, Finkel, Bethard and McClosky2014).

Mention detection: One of the main reason the constituent syntax is widely used for coreference resolution is due to mention detection. Our coreference resolution system (similarly to most others) considers NPs, named entities, and pronouns as mentions to resolve. Out of these, NPs require parsing to be identified. As shown in Figure 3, NPs can be trivially extracted from constituent trees, but they are not explicitly marked in dependency trees.

To identify NPs in dependency trees, we implemented the following algorithm. For all nodes, whose part-of-speech in the dependency tree is N*, PRP*, or DT*, we take the subtree of the node (i.e., all nodes syntactically dominated by this node) as a mention, as long as the node does not serve as a determiner (det) or noun modifier (nn) for another node. If the subtree contains a copular relation (cop), we remove all words dominated by this dependency up to the governor of the copular relation. For example, in Figure 3, there are three nouns Constitution, president, and power. The corresponding NPs are created simply by taking the subtree governed by these three nouns in the dependency tree, yielding the following three NPs: The Constitution, the president, and such power.

We show an additional, more complex example in Figure 4 (showing the constituency tree above the text, and the dependency tree below). In this tree, there are two DTs: This and the, and three nouns (N*): reason, price, and instability. Below we show the system decisions for each of these mentions (and other non-mentions) as follows:

1. (1) Mention: This—its part-of-speech is DT, and it is not in a determiner relation with another word.

2. (2) Not Mention: The—its part-of-speech is DT, but it serves as modifier in a determiner (det) relation with another word (reason).

3. (3) Mention: Price instability — this is a phrase covered by the subtree of the node instability, which has an N* part-of-speech.

4. (4) Not Mention: Price—this has a N* part-of-speech, but it is in a noun modifier (nn) relation with another word (instability).

5. (5) Not Mention: This is the reason for price instability—this is a phrase covered by a subtree of the node reason, which has an N* part-of-speech. However, one of its child has the copular relation is - cop - reason.

6. (6) Mention: The reason for price instability—this is a phrase covered by the subtree of the node reason, after removing all words up to the word in the copular relation (i.e., is).

Fig. 4.

An example of mention detection based on constituency tree or dependency tree.

Headword detection: Headword information is crucial in coreference resolution. For example, headword agreement is the most important feature in the resolution of proper- and common-noun anaphors.

For constituency syntax, there are a number of widely used linguistic heuristics for discovering headwords of constituent phrases (Collins Reference Collins1999). For dependency syntax, by contrast, the extraction is much simpler, because dependency relations are directed from governor (or headword) to modifier. Exploiting this information, the headword of a sequence becomes the only word whose own head is outside of the sequence. For example, in Figure 3, The cannot be the headword of the phrase The Constitution, because its own headword (Constitution) is included in the sequence. On the other hand, the governor of Constitution (give) is outside of the phrase. Thus, Constitution becomes the headword for the entire sequence. Below are the headwords of all other mentions identified for the text in Figure 3 by this algorithm:

• headword (the president) = president

• headword (such power) = power

• headword (This) = This

• headword (price instability) = instability

• headword (the reason for price instability) = reason

Syntactic relation detection: Particular syntactic structures like appositions or copular relations give very strong clues for coreference (Lee et al. Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013). When we use a constituency tree for coreference, these structures are discovered using regular expression patterns over constituent trees (Levy and Andrew Reference Levy and Andrew2006). In contrast, the dependency tree labels these relations explicitly as cop and appos dependencies, so they are trivial to extract. For example, in Figure 4, reason and This are in a copular relation. As a result, the precise patterns sieve links the mentions the reason for price instability and This.

4 Evaluation

We evaluate our system on the English portion of the CoNLL 2012 Shared Task dataset (Pradhan et al. Reference Pradhan, Moschitti, Xue, Uryupina and Zhang2012). This dataset is a combination of newswire, broadcast news, weblog, telephone conversation, etc., and contains 1.6M words and 2,384 documents. Similar to the shared task, we calculate five coreference metrics: MUC (Vilain et al. Reference Vilain, Burger, Aberdeen, Connolly and Hirschman1995), B ³ (Bagga and Baldwin Reference Bagga and Baldwin1998), CEAF_m , CEAF_e (Luo Reference Luo2005), and CoNLL F1 (average of MUC, B ³, and CEAF_e ), using the CoNLL 2012 scorer version 8.

4.1 Results

Table 5 compares the performance of our system under various configurations against previous work.Footnote ⁵ The table includes three configurations of the random forest classifiers (for 100 and 1,000 decision trees trained on training set, and 1,000 trees trained on train+dev dataset), three ablation experiments, where we remove important components of our system, and two artificial configurations that analyze the impact of the scaffolding architecture. The hyper-parameters for all sieves were coarsely tuned to optimize the CoNLL F1 score on the development set. In particular, we used a threshold of 0.2 for merging two mention clusters for the pronoun sieve, and a threshold of 0.3 for all the other sieves (these apply over the merging probability as produced by the RF). For the limit in sentence distance between two mentions we used: five sentences for the pronoun sieve, no limit for the proper–proper sieve, and 15 for all other sieves. The feature subset size that the RF uses is fifty features for the proper–proper sieve and thirty for all other sieves. All sieves used unpruned trees.

Table 5.

Performance of our approach compared to previous work

Similarly to previous work, we used the syntactic parse trees and named entities included in the CoNLL corpus. ‘# trees’ is the number of individual decision trees used by the random forest classifiers. Row 10 shows score of the model trained on both train and development dataset. Rows 11–13 show three ablation experiments: ‘ − Rule-based sieves’: removing the first two rule-based sieves, ‘ − MD classifier’: removing the statistical component of the mention detection module described in Section 3.1, and ‘ − Entity features’: removing the entity level features (E) in Table 4. Rows 14, 15, and 16 show three different configurations. ‘Single pass’: using a single statistical model with all features from Table 4 and no rule-based sieves, and ‘Reverse ordering’: all sieves, both rule-based and statistical, but called in reverse order to the one in Figure 1. ‘Dependency tree’: using dependency syntax instead of constituency. The dependency trees are generated by converting the constituency tree provided with the dataset to Stanford dependencies using CoreNLP software. All hyper-parameters for rows 11–16 are identical to the configuration in row 8. We repeated the comparison experiments (rows 8 and 11–16) ten times and averaged the scores. A non-parametric permutation test indicates row 8 is statistically significantly better than rows 11–16 (p < 0.01). Row 17 shows the performance of the best sieve architecture (row 10) but replacing each RF classifier with a linear, logistic regression classifier. We used the CoNLL 2012 scorer version 8 for all reported scores.

4.2 Discussion

The table shows that our best configuration (rows 9 or 10) gives comparable performance with a current state-of-the-art system (Wiseman et al. Reference Wiseman, Rush, Shieber and Weston2015), and outperforms by nearly eight CoNLL F1 points the rule-based system of Lee et al. (Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013), which served as the starting point of this work. This demonstrates that it is possible to achieve roughly state-of-the-art performance while maintaining the modularity and most of the simplicity of the original sieve architecture.

The experiments summarized in Table 5 allow us to answer several additional questions.

Are the rule-based sieves still important? The ablation experiment in row 11 shows that the rule-based sieves contribute 1.26 F1 points to the overall performance (row 8). This comes on top of statistical sieves that contain features that capture the same information as the rules (e.g., our ‘narrator’ feature in Table 4 captures, if the current mention refers to the speaker, the same information used by the speaker detection sieve). In the statistical sieves, these features are drowned out by many other features, which is avoided by the deterministic process in the rule-based sieves. This result illustrates the benefit of hybrid architectures.

How important is the scaffolding architecture? The scaffolding architecture improves two aspects of the singular classifier approach: (a) it captures (some of) the jointness of the task by incrementally constructing mention clusters, which are then available for the extraction of global features ((E) in Table 4), and (b) it reduces the error rate by keeping the antecedent search space small in each sieve (e.g., only proper nouns in the proper–proper sieve). We verified the importance of these two issues in rows 13 and 14, respectively. Row 13 shows that global (entity-based) features contribute 0.96 F1 points, whereas solving all mentions jointly in a single classifier drops performance by 1.43 F1 points (as mentioned in the table caption, rows 13 and 14 are compared against row 8). This demonstrates that, while joint information is indeed useful, the biggest benefit of the sieve architecture comes from the scaffolding of components. We cannot be sure, however, what portion, if any, of this improvement is due to the fact that having separate classifiers means we have more hyper-parameters to tune (see Section 4.1). Row 17 shows the performance of the linear classifier system with the same sieve architecture and features.

What is the impact of sieve ordering? Lee et al. (Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013) show the importance of precise-first ordering of sieves. To verify this for our hybrid approach, in row 15, we show the performance of an experiment where all seven sieves are called in reverse order (from pronoun to speaker id). The performance drop of 0.24 F1 points indicates that sieve ordering is not crucial, even though it is statistically significant.

What is the impact of the statistical component in mention detection? The ablation experiment in row 12 removes the statistical component of mention detection, which disambiguates between multiple mentions with the same head word, showing this component accounts for a statistically significant improvement of 0.3 F1 points. This is not a considerable contribution, but, to the best of our knowledge, our work is the first to show that this type of mention disambiguation is beneficial to the overall task.

Is there a performance penalty when switching to dependency syntax? When we switched from the constituent to the dependency parser, we measured a 1.11 CoNLL F1 points decrease (row 16 compared to row 8). The performance difference is caused mainly by a weaker mention detection component and less robust syntactic coreference patterns (e.g., appositives) when relying on dependency syntax. On the other hand, Table 6 shows that the runtime of this configuration decreased by more than five-fold compared to the original system that used the Stanford parser (Klein and Manning Reference Klein and Manning2003). All in all, we believe that, for most real-world applications, a one F1 point drop is an acceptable compromise for a speedup of fivefold.

Table 6.

Overall runtimes, i.e., starting from raw text, on the entire CoNLL shared task 2012 test dataset, in seconds

We ran the two configurations on a single machine with two Intel Xeon CPUs E5-2660 @ 2.20 GHz (sixteen cores and thrity-two hyperthreading) and 128 GB of RAM. The first CoNLL F1 reported (first column) is provided for reference from the previous table: it was measured when the system used the CoNLL-provided preprocessing (parser, NER, part-of-speech tagging). For the rest of the columns, we used Stanford CoreNLP version 3.5.1 for all preprocessing. We used the CoNLL scorer version 8 for all scores.

What is the impact of the forest size? Table 5 shows minimal performance differences with different numbers of trees (rows 8 and 9), indicating that it is possible to build good performing models with a relatively small memory footprint. Table 6 shows that we can run this end-to-end coreference model with 3 GB of RAM.

Are random forests better than linear classifiers? We chose random forests because of their ability to handle complex feature interactions; Wiseman et al. (Reference Wiseman, Rush, Shieber and Weston2015) and others have shown that individual features aren’t sufficiently informative for coreference. To validate this observation, we compared our best RF-based sieve model (row 10) against a similar model, where each classifier was replaced with a linear, logistic regression one (row 17). This comparison shows that, indeed, the LR-based model performs over four F1 points worse than the corresponding RF-based model. This confirms that modeling the non-linearity of the feature space for coreference resolution is important.

What are the random forests learning? Analyzing the trees learned by the RF classifiers, we found that the model was indeed making use of very large conjunctions of features. Figure 5 shows decision paths (from the root of one decision tree to the leaf) from the common–common sieve and the pronoun sieve. The depth of these decisions are 174 and 121, meaning that the tree considers the interaction of a vast number of features, far greater than easily possible in most other types of classifiers. Features in the first path include the similarity of head words, definiteness, mention length, textual overlap, distance, semantic similarity (from word vectors), etc. We observed similarly complex paths in other sieves, focusing on different features. For example, the pronominal resolution sieve focuses on animacy and number agreement and context words.

Fig. 5.

Part of the decision path in the common–common sieve for linking mention The industry with antecedent The oil industry’s and the part of decision path in the pronominal sieve for linking the pronoun its with the antecedent The company; (T) and (F) represent deciding True or False.

Table 7 shows the top eight features for each statistical sieve. The table shows that the feature space covers lexical, syntactic, and semantic features, and, crucially, that the important features differ between sieves. For example, while proper and common nouns both rely on headword agreement among all the mentions in the cluster, common nouns (and lists) further rely on word vector features. Pronominal anaphora resolution relies most on agreement of attributes like person and number. This is a further argument for a modular approach for coreference resolution.

Table 7.

Eight most important features of each sieve, sorted in descending order of the permutation feature importance (Wt) assigned by the model

The permutation importance of a feature is calculated by mean decrease in accuracy when the feature is randomly permuted (Breiman Reference Breiman2001).

4.3 Error analysis

To understand the improvements that our hybrid system has over the baseline rule-based system of Lee et al. (Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013), we repeated the partial-oracle analysis described in Section 2 for the proposed hybrid system.

The results, summarized in Table 8, show improvements for both mention detection and anaphora resolution. The performance gap in mention detection between our hybrid system and the oracle mention detection system (10.61) is smaller than that of the rule-based system (18.5). This demonstrates that our new mention detection algorithm, together with better coreference resolution, significantly reduces the performance drop due to incorrect mention detection.

Table 8.

Performance increase of the partial oracle system on the development dataset

The score difference is the max improvement achievable by fixing the corresponding error type. The → indicates a subclass of the preceding error type. Similar to Table 2, the last rows containing pronoun types include all wordform variants with the same lemma.

The gap between our system and the oracle pronominal resolution system also decreased (from 14.25 to 11.32), showing that our system successfully captures and combines the various weak signals for pronoun resolution. For example, the oracle error for it pronouns decreases from 3.28 to 2.85. Our conjecture is that since our model employs as a binary feature the deterministic pleonastic detection from Lee et al. (Reference Lee, Chang, Peirsman, Chambers, Surdeanu and Jurafsky2013), some of the improvements seen come from feature weighting and composition operations that include this feature. Nonetheless, the high remaining error rate for this class of pronouns highlights the need for more sophisticated models of pleonastic pronoun detection (Boyd, Gegg-Harrison and Byron Reference Boyd, Gegg-Harrison and Byron2005; Müller Reference Müller2006; Wiseman et al. Reference Wiseman, Rush, Shieber and Weston2015; Wiseman, Rush and Shieber Reference Wiseman, Rush and Shieber2016).