Abstract
Most recent improvements in NLP come from changes to the neural network architectures modeling the text input. Yet, state-of-the-art models often rely on simple approaches to model the label space, e.g. bigram Conditional Random Fields (CRFs) in sequence tagging. More expressive graphical models are rarely used due to their prohibitive computational cost. In this work, we present an approach for efficiently training and decoding hybrids of graphical models and neural networks based on Gibbs sampling. Our approach is the natural adaptation of SampleRank (Wick et al., 2011) to neural models, and is widely applicable to tasks beyond sequence tagging. We apply our approach to named entity recognition and present a neural skip-chain CRF model, for which exact inference is impractical. The skip-chain model improves over a strong baseline on three languages from CoNLL-02/03. We obtain new state-of-the-art results on Dutch.
Introduction
In sequence tagging tasks like Named Entity Recognition (NER), the relationships between labels are as critical as the individual word representations. For instance, an "I-PER" tag should logically follow a "B-PER" tag. Traditionally, researchers have favored Linear-Chain Conditional Random Fields (CRFs) because they allow for exact inference via dynamic programming (e.g., the Viterbi algorithm). However, these models are limited to local dependencies, typically only looking at immediate neighbors.
While Skip-Chain CRFs can model long-range dependencies—such as ensuring a word like "Apple" is labeled consistently as an Organization throughout a document—they render exact inference computationally intractable. Consequently, modern NLP often relies on deep neural networks (like BiLSTMs or Transformers) to capture context, while keeping the label space model simple. This paper introduces Neural SampleRank (NSR), a framework that enables the use of expressive, non-linear graphical models with deep neural features by leveraging Gibbs sampling.
Methods
Neural SampleRank (NSR) adapts the classical SampleRank algorithm for compatibility with backpropagation. The architecture decomposes the scoring function into two components: a heavy neural network (BiLSTM) for input representations and a lightweight graphical model (CRF) for label scoring.
The training process utilizes Gibbs sampling, a Markov Chain Monte Carlo (MCMC) method, to navigate the label space. Instead of calculating all possible label combinations, the model samples high-scoring sequences. Training is driven by a max-margin loss that includes both "pairwise" and "gold" components. The pairwise loss is particularly crucial as it provides a smooth gradient by comparing two sampled sequences, guiding the sampler toward the ground truth.
A key implementation is the Skip-Chain CRF, which adds connections between identical capitalized words across a document. This structure forces global consistency but is typically difficult to train. NSR makes this feasible by running the expensive BiLSTM once per sentence and performing efficient MCMC steps on the label space.
Results
The authors evaluated NSR on standard NER benchmarks including CoNLL-2003 (English and German) and CoNLL-2002 (Dutch), using both standard embeddings (GloVe/FastText) and contextualized embeddings (Flair).
- State-of-the-Art in Dutch: The model achieved a new SOTA F1 score of 91.44 on the Dutch NER task.
- Performance Gains: On English and German, the Neural Skip-Chain CRF significantly outperformed standard BiLSTM-CRF baselines when using non-contextualized embeddings (+0.67 F1 on English).
- Contextualized Embeddings: While gains were smaller when paired with Flair—which already captures significant context—the skip-chain model still provided improvements in Dutch.
- Efficiency: Despite the complexity of skip-chains, the NSR implementation stabilized at approximately 2,000 tokens per second, making it practical for research.
Discussion and Insights
The primary advantage of the skip-chain model is its ability to perform disambiguation via consistency. By linking occurrences of the same word, the model can resolve ambiguous tokens based on clearer context elsewhere in the document.
As shown in the figure above, the skip-connection helps the model realize that "Such" is a surname rather than a common word. The efficiency of this approach stems from the sparsity of Gibbs sampling; since only one label changes at a time, only a small fraction of CRF factors need recalculation at each step.
Limitations and Future Work
The skip-chain model requires document boundaries to link tokens, which may not be available in all real-world scenarios. Additionally, the marginal benefit of explicit graphical modeling decreases as "black-box" neural embeddings become more powerful. However, the authors suggest that Neural SampleRank could be transformative for tasks with even more complex structures, such as coreference resolution and relation extraction, where exact inference remains a significant barrier.
Summary updated