Source-linked AI summary
Neural Segmental Hypergraphs for Overlapping Mention Recognition
Bailin Wang, Wei Lu
TL;DR
Overlapping entity mentions challenge methods built on non-overlapping spans and can affect downstream extraction. The paper introduces a neural segmental hypergraph with efficient inference and a one-to-one encoding of mention combinations, achieving state-of-the-art results on three benchmark datasets.
Problem
Existing mention-recognition approaches can assume non-overlapping spans or suffer structural ambiguity, despite overlapping mentions occurring in practical datasets.
Method
The paper combines a segmental hypergraph representation for overlapping mentions with neural networks for word- and span-level feature learning.
Results
The model achieves state-of-the-art performance on three standard datasets for recognizing overlapping mentions.
Takeaways & Limitations
The representation is general and robust for recognizing both overlapping and non-overlapping mentions, with linear-time processing noted as attractive for large-scale data.
Takeaways & Limitations
ACE2005 comparisons use a split different from one prior study, although the paper follows the Lu and Roth (2015) split.
Abstract
from arXiv · showhide
In this work, we propose a novel segmental hypergraph representation to model overlapping entity mentions that are prevalent in many practical datasets. We show that our model built on top of such a new representation is able to capture features and interactions that cannot be captured by previous models while maintaining a low time complexity for inference. We also present a theoretical analysis to formally assess how our representation is better than alternative representations reported in the literature in terms of representational power. Coupled with neural networks for feature learning, our model achieves the state-of-the-art performance in three benchmark datasets annotated with overlapping mentions.
1 Introduction
Mention recognition supports downstream language understanding tasks, but common sequence-labeling assumptions exclude overlapping spans. The paper proposes a segmental hypergraph model that represents arbitrary overlapping mentions efficiently and reports state-of-the-art performance.
- Motivation: Overlapping mentions can be necessary for downstream relation extraction, such as extracting LOCATEDIN between “the Seattle zoo” and “Seattle.”Sequence-labeling approaches typically assume mentions are non-overlapping, so they may miss relations requiring both overlapping mentions.
- Contributions: The proposed segmental hypergraph models arbitrary combinations of potentially overlapping mentions with O(cmn) inference time.Here, m is the number of mention types, n is sentence length, and c is the maximum mention length.
- Contributions: The representation is designed to capture features unavailable to existing approaches and avoid their stated limitations through theoretical analysis.The paper specifically frames the new representation as addressing limitations of recent overlapping-mention models.
- Contributions: Neural feature learning combined with the new representation achieves state-of-the-art performance on three benchmark datasets with overlapping mentions.The paper also describes the model as general and robust, including evaluation on data without overlapping annotations.
2 Related Work
Prior work uses rules, cascaded or stacked sequence models, parsing, local span classifiers, and hypergraphs to recognize overlapping mentions. These approaches trade off overlap coverage, scalability, span interactions, or structural unambiguity.
- Sequence and rule-based approaches: Rule-based, cascaded, and multilayer approaches recognize overlapping segments but can fail when overlapping mentions share the same type.The cascaded CRF approach specifically cannot model same-type overlap, a limitation also noted for related sequential strategies.
- Parsing approaches: Parsing-based recognition models nesting assumptions but incurs cubic time complexity, limiting scalability for long sentences.A transition-based constituency-forest variant was proposed to improve scalability while retaining the same general parsing perspective.
- Span and layered approaches: Local span classifiers cannot capture interactions between spans, while sequentially stacked flat layers process mentions from inner to outer spans.These methods represent alternative decompositions of overlapping mention recognition rather than a single global span-interaction structure.
- Hypergraph approaches: Mention hypergraph and separator models are fast and effective but suffer from structural ambiguity during inference.The paper positions its new representation as removing this limitation.
- Neural approaches: Recent neural approaches have demonstrated strong mention-recognition performance without handcrafted features.This motivates combining neural feature learning with a representation specifically designed for overlapping mentions.
3 Segmental Hypergraph
The segmental hypergraph compactly represents all possible combinations of potentially overlapping mentions through typed nodes and hyperedges. Its hyperpaths correspond one-to-one with mention combinations, eliminating structural ambiguity.
- Representation: A segmental hypergraph represents all possible combinations of potentially overlapping mentions in a sentence using directed hypergraph nodes and hyperedges.Each hyperedge has one parent node and an ordered list of child nodes.
- Representation: Node types encode mentions by start position, mention type, covered words, and termination, while X marks the end of a mention.Ai and Ei organize mentions by whether they start at or after a position; Tk_i and Ik_i,j encode type and span coverage.
- Hyperedges: The hyperedges enumerate whether mentions start at a position, which types they have, and whether spans continue, end, or do both.This compactly encodes the complete search space, including overlapping mentions.
- Hyperpaths: A hyperpath combines node sequences to encode a specific overlapping mention set, such as the three mentions illustrated in Figure 3.The example includes mentions that share boundaries or overlap within the same sentence.
- Structural ambiguity: The representation has a one-to-one correspondence between hyperpaths and possible mention combinations, so each combination receives a unique encoding.The proof sketch characterizes both hyperpaths and mention combinations through hyperedges involving X nodes.
- Structural ambiguity: Unlike earlier mention hypergraph and separator representations, the segmental hypergraph has no structural ambiguity during inference.Earlier models can assign multiple interpretations to the same local beginning-and-end decisions.
4 Learning
The model assigns scores to hyperedges using neural word- and span-level representations, with softmax-margin training emphasizing false negatives. Its segmental hypergraph supports span features and interactions that prior representations cannot capture.
- 4 Learning: The log-linear model assigns each mention combination a score through its corresponding hyperpath and decomposes that score over hyperedges.The score function is defined for an input sentence and output mention combination, which uniquely corresponds to a hyperpath.
- 4 Learning: The segmental hypergraph defines features over word-level and span-level nodes, including interactions between partial mentions.Span-level features are extracted from nodes representing particular spans, while hyperedges between I nodes capture interactions between partial mentions.
- 4 Learning: Softmax-margin training assigns more penalty to false negatives than false positives by setting β ≥1 in the cost function.The cost compares predicted hyperedges with the gold mention combination and uses β to weight the error margin.
- 4 Learning: Two bidirectional LSTMs learn word-level and span-level features, while dynamic programming computes all possible span embeddings in O(cn) time.Word embeddings and optional POS embeddings form word representations before contextual and span-level processing.
- 4 Learning: Scores for two-node hyperedges use a linear layer, with parameter matrices shaped by word features, span features, and mention types.The model defines scores only for the latter two hyperedge types because the first two contribute constant factors to the loss.
5 Inference
Inference uses inside-outside message passing for partition-function computation and max-product-style MAP decoding over the complete hypergraph. The resulting algorithm has O(cmn) time complexity, matching a zero-th order semi-Markov CRF.
- 5 Inference: The inside algorithm computes the partition function by passing messages from leaf nodes to the root, and the outside pass is defined analogously.The message-passing procedure converges after one forward and one backward pass.
- 5 Inference: MAP decoding finds the most probable hyperpath using a max-product-style message-passing procedure over the complete hypergraph.Decoding uses the feature function when constructing messages.
- 5 Inference: Inference runs in O(cmn) time because each node participates in at most three hyperedges, matching a zero-th order semi-Markov CRF.Here c is the maximum mention length, m the number of mention types, and n the number of sentence words.
6 Experiments
The experiments evaluate segmental hypergraph models on ACE-2004, ACE-2005, and GENIA against neural, non-neural, and overlapping-mention baselines. The evaluation also includes ablations and character-level variants.
- Datasets: The experiments cover ACE-2004, ACE-2005, and GENIA, where overlapping mentions frequently occur, including over 46% of ACE-2004 mentions.
- Baseline Approaches: The baselines include linear-chain and cascaded CRFs, semi-CRF, prior neural models, and the non-neural SH model.
- Baseline Approaches: Table 3 compares SH and baseline models using precision, recall, and F1 across ACE-2004, ACE-2005, and GENIA.
- Model Variants: Character-level representations are evaluated as additional variants of the segmental hypergraph model.
6.3 Training
Training experiments compare unrestricted and restricted segmental hypergraph models, feature variants, and decoding settings. Results emphasize strong benchmark performance, benefits from longer span coverage, and a speed–performance tradeoff controlled by the length bound.
- Main Results: SH gains around 1-2% F1 over the mention hypergraph and mention separator, indicating the value of eliminating structural ambiguity.
- Main Results: SH (c=n) + char achieves the best results on all datasets compared with other recent neural models.
- Main Results: SH (c=n) achieves the best results among previous models on ACE datasets, while neural SH models improve over non-neural SH on GENIA with fewer parameters.
- Length Restriction: Increasing the maximum mention length c consistently improves F1, making c a tradeoff between time complexity and performance.
- Global versus Local Modeling: The global approach outperforms FOFE, whose unrestricted performance suffers from more negative training instances.
6.5 Additional Analyses
Additional analyses examine how the model behaves under different experimental conditions.
- Additional Analyses: The analyses investigate model behavior through further experiments beyond the main benchmark evaluation.
Ablation study
Ablation and overlap-focused analyses assess which training components matter and how SH performs on sentences with different mention structures. The results support contributions from dropout, pre-trained embeddings, softmax-margin training, and overlap handling.
- Ablation study: Dropout, pre-trained embeddings, and softmax-margin training each significantly improve model performance across the evaluated datasets.
- Overlap Analysis: On ACE-05, SH significantly improves over two state-of-the-art models on both sentences with and without overlapping mentions, especially in the overlapping portion.
- Overlap Analysis: The larger ACE improvement is associated with its higher frequency of overlapping mentions, while unrestricted SH mainly benefits from recalling more overlapping mentions.
Running time
The model is evaluated for decoding speed against other linear-time approaches and for robustness on data containing only non-overlapping mentions.
- The length bound c=6 is reported to make the model much faster than compared models on ACE-05.
- On CoNLL 2003, the model is evaluated as a general mention extraction system using only word and character embeddings.
- The model achieves competitive results against neural models that use no external features, although most comparators handle only non-overlapping mentions.
- The segmental hypergraph captures interactions between neighboring spans sharing the same type and left boundary.
7 Conclusion and Future Work
The paper concludes that its neural segmental hypergraph model is effective for overlapping mentions and remains robust across overlapping and non-overlapping settings. It also points to applications involving other overlapping structures, including discontinuous biomedical entities.
- The model achieves state-of-the-art results on three standard datasets for recognizing overlapping mentions.
- The model is described as general and robust for both overlapping and non-overlapping mentions.
- Complete results for the evaluation are provided in supplementary material.
- The authors suggest applying the model to overlapping and discontinuous entities, which frequently occur in biomedical data.