Sentence-Incremental Neural Coreference Resolution (2022)

Abstract: We propose a sentence-incremental neural coreference resolution system which incrementally builds clusters after marking mention boundaries in a shift-reduce method. The system is aimed at bridging two recent approaches at coreference resolution: (1) state-of-the-art non-incremental models that incur quadratic complexity in document length with high computational cost, and (2) memory network-based models which operate incrementally but do not generalize beyond pronouns. For comparison, we simulate an incremental setting by constraining non-incremental systems to form partial coreference chains before observing new sentences. In this setting, our system outperforms comparable state-of-the-art methods by 2 F1 on OntoNotes and 6.8 F1 on the CODI-CRAC 2021 corpus. In a conventional coreference setup, our system achieves 76.3 F1 on OntoNotes and 45.5 F1 on CODI-CRAC 2021, which is comparable to state-of-the-art baselines. We also analyze variations of our system and show that the degree of incrementality in the encoder has a surprisingly large effect on the resulting performance.

## introduction coreference resolution (cr) is a task in which a system detects and resolves linguistic expressions that refer to the same entity. it is typically performed in two steps: in mention detection, the model predicts which expressions are referential, and in mention clustering, the model computes each mention's antecedent. many recently proposed systems follow a mention-pair formulation from @xcite , in which all possible spans are ranked and then scored against each other. in particular, methods that augment this approach with large, pre-trained language models achieve state-of-the-art results @xcite . in 2004, on the waterfront promenade originally constructed for viewing only the scenery of hong kong island and victoria harbor, the hong kong tourism board also constructed the avenue of stars, memorializing hong kong's 100-year film history . figure 1 : an example from the ontonotes dataset which highlights the need for incremental systems to identify spans rather than tokens as mentions. the mentions cannot be resolved solely from the prefix 'hong kong', and the clustering decision should be delayed until the full mention is observed. despite impressive performance, these methods are computationally demanding. for a text with n tokens, they will score up to o(n 2 ) spans, followed by up to o(n 4 ) span comparisons. they also process documents non-incrementally, requiring access to the entire document before processing can begin. these properties present challenges when insufficient computational resources are available, or when the task setup is incremental, such as in dialogue (e.g. @xcite . from a cognitive perspective, these methods are also unappealing because research on "garden-path" effects show that humans resolve referring expressions incrementally @xcite . these drawbacks have led to renewed interest in incremental coreference resolution systems, in which document tokens are processed sequentially. some recent approaches use memory networks to track entities in differentiable memory cells @xcite . these models demonstrate proficiency at proper name and pronoun resolution @xcite . however, they seem unlikely to generalize to more complicated coreference tasks due to a strict interpretation of incrementality. both @xcite and @xcite resolve mentions wordby-word, making coreference decisions possibly before the full noun phrase has been observed. the approach is adequate for proper names and pronouns, but it may fail to distinguish entities who share the same phrase prefix. for example, in figure 1 , three mentions all begin with 'hong kong', though all belong to separate entities. in this case, it is difficult to see how a system using word-level predictions would resolve these mentions to different entities. motivated by this recent work, we propose a new system that processes a document incrementally at the sentence-level, creating and updating coreference clusters after each sentence is observed. the system addresses deficiencies in memory networkbased approaches by delaying mention clustering decisions until the full mention has been observed. these goals are achieved through a novel mention detector based on shift-reduce parsing, which identifies mentions by marking left and right mention boundaries. identified mention candidates are then passed to an online mention clustering model similar to @xcite and @xcite . the model proposes a linear number of spans per sentence, reducing computational requirements and maintaining more cognitive plausibility compared to non-incremental methods. in order to compare non-incremental and incremental systems on equal footing, we propose a new sentence-incremental evaluation setting. in this setting, systems receive sentences incrementally and must form partial coreference chains before observing the next sentence. this setting mimics human coreference processing more closely, and is a more suitable evaluation setting for downstream tasks in which full document access is generally not available (e.g. for dialogue @xcite ). using the sentence-incremental setting, we demonstrate that our model outperforms comparable systems adapted from partly incremental methods @xcite across two corpora, the ontonotes dataset @xcite and the recently released codi-crac 2021 corpus @xcite . moreover, we show that in a conventional evaluation setting, where the model can access the entire document, our system retains close to state-of-the-art performance. however, the sentence-incremental setting is substantially outperformed by non-sentence-incremental systems. analyzing the difference between these two settings reveals that the encoder is heavily dependent on how many sentences it can observe at a time. the analysis suggests better representations of the entities and their context may improve performance in the sentence-incremental setting. nevertheless, our results provides new state-of-the-art baselines for sentence-incremental evaluation. ## related work non-incremental mention-pair models have dominated the field in recent years, with many following the formulation presented by @xcite . several extensions have led to performance improvements, such as adding higher-order inference @xcite , and replacing the encoder with bert and spanbert @xcite . extensions to this approach have looked at reformulating the problem as question-answering @xcite , simplifying span representations @xcite , and incorporating coherence signals from centering theory @xcite . although our work is orthogonal to this line of research, we compare our system against this type of non-incremental model. @xcite and xia et al. (2020) adapt the non-incremental system of @xcite so that mention clustering is performed incrementally. their resulting models achieve similar performance to the original non-incremental one. however, in their formulation, document encoding, mention detection and certain clustering decisions still fully depend on @xcite . the resulting model still requires access to the full document in order to compute coreference chains. @xcite similarly present an incremental mention clustering approach where mention detection is performed non-incrementally as @xcite . memory network-based approaches identify coreferring expressions by writing and updating entities into cells within a fixed-length memory @xcite . these models demonstrate how fully incremental coreference systems can be achieved. however, the formulation operates on token-level predictions, and does not easily extend to either nested mentions or certain multi-token mentions (e.g. in figure 1 ). cross-document coreference resolution (cdcr) requires systems to compute coreference chains across documents, raising scalability challenges as the number of documents increases. given these challenges, incremental cdcr systems are crucial @xcite due to lower memory requirements. however, these works are not directly comparable to ours since they assume gold mentions are provided as input. other, earlier, incremental coreference systems also often ignore or diminish the role of mention detection. for example, @xcite use an external parser for mention detection, requiring an additional model. @xcite assume gold mentions as input. recently, @xcite propose a coreference resolution system based a seq2seq formulation using hidden variables. although their focus is on adding structure to seq2seq models, their system can also be viewed as transition-based like ours. our incremental mention detector bears similarities to certain models for nested named-entity recognition (ner). in particular, @xcite present an incremental neural model for nested ner based on a shift-reduce algorithm. their deduction rules differ greatly from ours as they model mention spans using complete binary trees, and are aimed at ner rather than mention detection. recent work has also explored incremental transformer architectures @xcite , and adapting these architectures to nlu tasks (though not coreference resolution) @xcite . in this work, we focus on the simpler sentence-incremental setting, believing it to be sufficient for downstream tasks. ## method given a document, the goal is to output a set of clusters @xmath0, . . . , c k }, where mentions within each cluster are co-referring. we assume mentions may be nested but otherwise do not overlap. this assumption allows us to model mentions using a method analogous to shift-reduce, where shifting corresponds to either incrementing the buffer index or marking a left mention boundary, and reducing corresponds to marking a right boundary and resolving the mention to an entity cluster. ## analysis the dramatic performance gap between the sent-inc and part-inc settings may be surprising. since coreference resolution is primarily processed incrementally by humans, why does access to future tokens affect the sent-inc model so heavily? to investigate this issue deeper, we design additional k-sentence-incremental settings. in each setting, the system accesses k sentences (s 1 , . . . , s k ) at a time as active input, and 512 -k @xmath1. in each setting, the model observes the same number of tokens (512), but varies the amount of active input vs. memory. the mention detection and mention clustering steps remain the same and are still incremental; the only change is in the encoder. varying k in this way allows us to the test the effect of more or less incrementality on the system. when @xmath2, we recover the original sent-inc model. when k is large enough (in practice, 24), we get the part-inc model. for each @xmath3, 4, 8, 12, 16, 20, 24}, we fully train the corresponding model on ontonotes as described in section 4, and evaluate on the dev set. the results are shown in figure 5 . there are a few notable characteristics. the first is that as k increases, we see a much more dramatic lift when k is small (e.g. moving from 1 to 4 sentences) compared to when k is large. this effect corresponds to the intuition that coreferring expressions are usually close to their antecedent. the more coreference chains the model can observe simultaneously, the better it is at resolving them. the second noteworthy trend is that increasing k improves recall (9.7%) far more than precision (3.8%). although not shown here, we observe this trend across all three metrics within the conll score (muc, b 3 and ceaf φ 4 ). the result means that finding and resolving true coreference links (i.e. reducing false negatives) is a far more serious obstacle for the sent-inc model than for part-inc. since the only difference in these models is how many embeddings are cached, the result suggests caching or not caching embeddings plays a large role in finding and correctly resolving mentions. ## future work a major goal would be to elevate incremental coreference resolvers to the same level as non-incremental ones. as we showed in section 6, a large part of the performance difference occurs because the xlnet encoder does not effectively handle incremental input. a simple strategy therefore may be to swap out that encoder for a more powerful one. however, few pre-trained language models targeted at nlu tasks are naturally incremental. one candidate is gpt-j @xcite but its size is prohibitively large. other ways to bridge this gap may come from improving the mention detection component. a similar task is nested named entity recognition, where the system must identify named entity boundaries and coarsely classify them. recent nested ner systems such as @xcite or yu et al. (2020a) may provide directions for improving mention detection in our incremental formulation. ## conclusion we propose a sentence-incremental coreference resolution model using a shift-reduce formulation. the model delays mention clustering until the full span has been observed, alleviating a key flaw with previous incremental systems. it efficiently processes text, and avoids scoring a quadratic number of spans during mention detection. in a sentence-incremental setting, our method outperforms strong baselines adapted from stateof-the-art systems. when access to the full document is allowed, the proposed system achieves similar performance to state-of-the-art methods while maintaining a higher level of incrementality. we investigate why this relaxation has such a dramatic effect, finding that the document encoder does not make effective use of its memory cache. our sentence-incremental results suggest an important point: non-incremental methods are not effective tools when they must be used incrementally. creating new, incremental coreference resolvers that perform at the same level as non-incremental ones is a challenging but meaningful goal. achieving this result would make a significant impact in downstream applications where text is received incrementally, such as dialogue systems or conversational question answering (e.g. @xcite . our proposal demonstrates an important step towards highly effective, incremental coreference resolution systems.