Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling

Jenny Rose FinkelTrond GrenagerChristopher D. Manning

article2005ACL3,463 citations

Proposes using Gibbs sampling with simulated annealing during inference to incorporate long-range consistency constraints into conditional random fields, boosting information extraction accuracy on standard benchmarks without requiring structural retraining.

Listen

Statistical models for natural language processing tasks such as information extraction have long been limited to local features because these permit efficient exact inference through dynamic programming. This constraint prevents them from capturing the long-distance regularities common in text, such as consistent labeling of repeated entity names across a document. The work addresses this gap by demonstrating a practical way to relax the locality requirement while retaining usable inference procedures.

The authors set out to evaluate whether Gibbs sampling combined with simulated annealing could serve as a drop-in replacement for Viterbi decoding in existing sequence models, thereby allowing non-local consistency constraints to be added without making inference intractable. They started from trained conditional random field models and augmented them with simple penalty-based models that discourage inconsistent entity labels or mismatched template fields. Inference was performed by running a Markov chain that repeatedly resamples individual positions conditioned on the rest of the sequence and the non-local penalties; a linear cooling schedule gradually sharpened the distribution toward high-probability assignments.

On the CoNLL 2003 named-entity recognition task the non-local model raised per-entity F1 from 85.51 to 86.86, an absolute gain of 1.35 points that corresponds to roughly a 9 percent relative error reduction. On the CMU Seminar Announcements template-filling task the same approach produced a smaller but still statistically significant improvement, moving overall token F1 from 91.85 to 92.29. Both gains were obtained against already competitive baselines and were stable across repeated runs. The method also proved flexible: the same sampling machinery worked on top of the original CRF without retraining and could enforce constraints that are difficult to encode in skip-chain or relational Markov network alternatives.

These results indicate that modest, linguistically motivated non-local constraints can measurably improve extraction accuracy on standard benchmarks without requiring entirely new model architectures. The computational price is a roughly thirty-fold increase in test-time cost, which may be acceptable when accuracy matters more than throughput. Because the technique is model-agnostic, it can be layered onto hidden Markov models, conditional Markov models, or other sequence taggers already in production.

The main limitations are the task-specific design of the penalty terms and the lack of a systematic exploration of cooling schedules or sampling budgets. Readers should therefore treat the reported gains as evidence of feasibility rather than as guaranteed improvements for every new domain. Further work to reduce sampling cost or to learn the non-local penalties automatically would strengthen the practical case for wider adoption.

Stanford University annealing approximate inference gibbs sampling information extraction Gibbs sampling non-local information

stanfordnlp/CoreNLP Finkel et al (2005).pdf

Paper: Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data, J. Lafferty et al. (2001). This foundational paper introduces Conditional Random Fields, the sequence modeling framework that the source paper augments with Gibbs sampling.

Paper: Bidirectional LSTM-CRF Models for Sequence Tagging, Zhiheng Huang et al. (2015). This paper extends sequence tagging by replacing traditional graphical models like CRFs with bidirectional LSTM-neural architectures.

Cover for Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling

Abstract

Most current statistical natural language processing models use only local features so as to permit dynamic programming in inference, but this makes them unable to fully account for the long distance structure that is prevalent in language use. We show how to solve this dilemma with Gibbs sampling, a simple Monte Carlo method used to perform approximate inference in factored probabilistic models. By using simulated annealing in place of Viterbi decoding in sequence models such as HMMs, CMMs, and CRFs, it is possible to incorporate non-local structure while preserving tractable inference. We use this technique to augment an existing CRF-based information extraction system with long-distance dependency models, enforcing label consistency and extraction template consistency constraints. This technique results in an error reduction of up to 9% over state-of-the-art systems on two established information extraction tasks.

1 Introduction
2 Gibbs Sampling for Inference in Sequence Models
3 A Conditional Random Field Model
4 Datasets and Evaluation
4.1 The CoNLL NER Task
4.2 The CMU Seminar Announcements Task
5 Models of Non-local Structure
5.1 CoNLL Consistency Model
5.2 CMU Seminar Announcements Consistency Model
6 Combining Sequence Models
7 Results and Discussion
8 Related Work
9 Conclusions
Acknowledgements
References

Knowls

Knowl 1 — Factored Sequence Model Combining Local CRFs with Non-Local Constraints
model/method
To incorporate non-local document-level constraints into sequence labeling without requiring exact global dynamic programming or heuristic multi-stage pipelines, a factored sequence model combines a locally factored sequence model $P_M(\mathbf{s} \mid \mathbf{o})$ (such as a linear-chain Conditional Random Field) with a non-local constraint model $P_L(\mathbf{s} \mid \mathbf{o})$ :

$P_F(\mathbf{s} \mid \mathbf{o}) \propto P_M(\mathbf{s} \mid \mathbf{o}) P_L(\mathbf{s} \mid \mathbf{o})$

where $\mathbf{o} = (o_1, \dots, o_N)$ is an observed sequence of $N$ tokens, $\mathbf{s} = (s_1, \dots, s_N)$ is the corresponding sequence of hidden state labels, $M$ is the local model, $L$ is the non-local constraint model, and $F$ is the joint factored model.

During inference, computing the full sequence normalizer across all $|\mathcal{S}|^N$ assignments is intractable. However, Gibbs sampling requires only the conditional distribution of a single state $s_i$ given all other states $\mathbf{s}_{-i} = (s_1, \dots, s_{i-1}, s_{i+1}, \dots, s_N)$ and the observations $\mathbf{o}$ :

$P_F(s_i \mid \mathbf{s}_{-i}, \mathbf{o}) \propto P_M(s_i \mid \mathbf{s}_{-i}, \mathbf{o}) P_L(s_i \mid \mathbf{s}_{-i}, \mathbf{o})$

For a first-order linear-chain CRF defined by clique potentials $\phi_i(s_{i-1}, s_i)$ on adjacent state transitions, the Markov blanket of position $i$ consists only of its immediate neighbors $s_{i-1}$ and $s_{i+1}$ . Thus, the local conditional distribution simplifies to:

$P_M(s_i \mid \mathbf{s}_{-i}, \mathbf{o}) \propto \phi_i(s_{i-1}, s_i) \phi_{i+1}(s_i, s_{i+1})$
Knowl 2 — Simulated Annealing Gibbs Sampling for Non-Local Sequence Decoding
algorithm
Exact maximum a posteriori (MAP) decoding with non-local constraints is intractable via dynamic programming because long-distance dependencies violate the Markov property. An approximate inference procedure employs Gibbs sampling combined with simulated annealing over the space of state sequences.
Input: Observation sequence $\mathbf{o} = (o_1, \dots, o_N)$ , label set $\mathcal{S}$ , local clique potentials $\phi$ , non-local penalty model $P_L$ , cooling schedule $c = (c_0, c_1, \dots, c_T)$ with $c_0 = 1.0$ and $c_T \to 0$ .
Output: Sequence assignment $\mathbf{s}$ .
Initialize sequence $\mathbf{s}^{(0)} = (s_1^{(0)}, \dots, s_N^{(0)})$ randomly from $\mathcal{S}^N$
for $t \leftarrow 1$ to $T$ do
     $\mathbf{s}^{(t)} \leftarrow \mathbf{s}^{(t-1)}$
    for $i \leftarrow 1$ to $N$ do
        for each candidate label $s \in \mathcal{S}$ do
            Construct candidate sequence $\mathbf{s}' = (s_1^{(t)}, \dots, s_{i-1}^{(t)}, s, s_{i+1}^{(t-1)}, \dots, s_N^{(t-1)})$
            Compute local factor $P_M(s \mid \mathbf{s}_{-i}^{(t)}, \mathbf{o}) \leftarrow \phi_i(s_{i-1}^{(t)}, s) \cdot \phi_{i+1}(s, s_{i+1}^{(t-1)})$
            Compute non-local factor $P_L(s \mid \mathbf{s}_{-i}^{(t)}, \mathbf{o}) \leftarrow P_L(\mathbf{s}' \mid \mathbf{o})$
            Compute product $p(s) \leftarrow P_M(s \mid \mathbf{s}_{-i}^{(t)}, \mathbf{o}) \cdot P_L(s \mid \mathbf{s}_{-i}^{(t)}, \mathbf{o})$
            Compute annealed score $w(s) \leftarrow (p(s))^{1 / c_t}$
        Sample new state $s_i^{(t)}$ from $\mathcal{S}$ with probability $\frac{w(s)}{\sum_{s' \in \mathcal{S}} w(s')}$
return $\mathbf{s}^{(T)}$
The sampler iterates through positions $i \in \{1, \dots, N\}$ and resamples each state $s_i$ from the annealed conditional distribution:

$P_A(s_i^{(t)} \mid \mathbf{s}_{-i}^{(t-1)}, \mathbf{o}) = \frac{P_F(s_i^{(t)} \mid \mathbf{s}_{-i}^{(t-1)}, \mathbf{o})^{1/c_t}}{\sum_{s' \in \mathcal{S}} P_F(s' \mid \mathbf{s}_{-i}^{(t-1)}, \mathbf{o})^{1/c_t}}$

As the temperature parameter $c_t$ decreases toward 0 according to a linear cooling schedule, the conditional distribution sharpens around the argmax, guiding the Markov chain toward the global maximum of the factored sequence probability space.
Knowl 3 — Exponential Penalty Formulation for Non-Local Constraints
equation
Non-local constraints across an entire document are formulated as an unnormalized sequence probability model that penalizes specific types of structural or consistency violations:

$P_L(\mathbf{s} \mid \mathbf{o}) \propto \prod_{\lambda \in \Lambda} \theta_\lambda^{\#(\lambda, \mathbf{s}, \mathbf{o})}$

where $\Lambda$ is a finite set of predefined violation types, $\theta_\lambda \in (0, 1]$ is a penalty parameter associated with violation type $\lambda$ , and $\#(\lambda, \mathbf{s}, \mathbf{o}) \in \mathbb{N}_0$ is the count of how many times violation $\lambda$ occurs in the state sequence $\mathbf{s}$ with respect to observation sequence $\mathbf{o}$ .

Sequences containing more consistency violations receive lower probability weights. Because the model is queried only for single-site conditional distributions during Gibbs sampling, evaluation requires computing relative violation counts when modifying state $s_i$ , which is accelerated via memoized index structures mapping token spans to their current label assignments.
Knowl 4 — Empirical Bayes Non-Local Consistency Penalties for Named Entity Recognition
model/method
In named entity recognition (NER), identical or overlapping phrases within a single document tend to have identical entity types. The non-local constraint model for NER defines penalty parameters using Empirical Bayes estimates computed from document-level co-occurrence statistics in training data:
1. Exact Match Consistency: For identical token sequences appearing multiple times within a document, pairs assigned conflicting entity types $(c_1, c_2)$ are penalized. The pairwise penalty parameter is defined as the geometric mean of conditional probabilities derived from smoothed training counts:
$\theta_{\text{pair}}(c_1, c_2) = \sqrt{\hat{P}(c_2 \mid c_1) \cdot \hat{P}(c_1 \mid c_2)}$

where $\hat{P}(c_2 \mid c_1) = \frac{\text{Count}(c_1, c_2) + 1}{\sum_{c'} \text{Count}(c_1, c') + |\mathcal{C}|}$ uses Laplace add-one smoothing.
1. Subsequence Consistency: When an entity is a token subsequence of another entity elsewhere in the document (such as "Woods" and "Geoff Woods"), an asymmetric subsequence penalty $\hat{P}(c_{\text{sub}} \mid c_{\text{full}})$ is computed from training subsequence co-occurrences.
2. Length Multiplier: To encourage inconsistent entity spans to shrink rather than expand, the combined penalty term is applied multiplicatively $k$ times, where $k$ is the token length of the offending entity phrase.
Knowl 5 — Extraction Template Consistency Constraints for Seminar Announcements
model/method
For template extraction tasks such as seminar announcements, non-local structure is enforced via task-specific field consistency constraints parameterized by a fixed penalty weight $\theta = \exp(-4.0)$ :
1. Start Time Consistency: All text segments tagged as start times are normalized (e.g., standardizing 12-hour and 24-hour time expressions). If multiple distinct normalized start times are extracted within the same announcement document, a penalty of $\theta^k$ is applied, where $k$ is the number of tokens in the inconsistent entity.
2. End Time Consistency: All text segments tagged as end times are normalized. Inconsistent normalized end times receive a penalty of $\theta^k$ proportional to token length $k$ .
3. Speaker Consistency: For any phrase tagged as a seminar speaker, its final token is extracted as the speaker's surname. Every occurrence of that surname in the document that is not tagged as a speaker incurs a single penalty factor of $\theta$ .

Knowl 6 — Equivalence of Annealed Gibbs Sampling to Viterbi Inference in Linear-Chain CRFs

data/table

When applied to a standard first-order linear-chain CRF without non-local constraint factors, simulated annealing Gibbs sampling achieves decoding performance statistically identical to exact Viterbi dynamic programming across multiple trials initialized from random state assignments.

Inference	CoNLL (Entity $F_1$ )	Seminars (Token $F_1$ )
Viterbi	85.51	91.85
Gibbs Sampling	85.54	91.85
	85.51	91.85
	85.49	91.85
	85.51	91.85
	85.51	91.85
	85.51	91.85
	85.51	91.85
	85.51	91.85
	85.51	91.86
Mean	85.51	91.85
Std. Dev.	0.01	0.004

The experiments used a linear cooling schedule with 1,000 sequence sweeps over the test sets. The mean $F_1$ score across 10 random initializations matches Viterbi decoding exactly to two decimal places on both the CoNLL 2003 named entity recognition test set ( $85.51\%$ entity $F_1$ ) and the CMU Seminar Announcements information extraction task ( $91.85\%$ token $F_1$ ), confirming the reliability of stochastic simulated annealing for sequence optimization.

Knowl 7 — Named Entity Recognition Performance on CoNLL 2003 Dataset

data/table

Incorporating document-level label and subsequence consistency models via Gibbs sampling improves named entity recognition performance on the CoNLL 2003 English benchmark (testb set of 231 documents, 46,000 tokens) across all entity classes (Location, Organization, Miscellaneous, Person).

Approach	LOC	ORG	MISC	PER	ALL ( $F_1$ )
BM LT-RMN	–	–	–	–	80.09
BM GLT-RMN	–	–	–	–	82.30
Local + Viterbi	88.16	80.83	78.51	90.36	85.51
NonLoc + Gibbs	88.51	81.72	80.43	92.29	86.86

Evaluation is measured using entity-level $F_1$ without partial credit. The non-local Gibbs model (NonLoc + Gibbs) achieves an overall $F_1$ score of $86.86\%$ , yielding an absolute gain of $+1.35\%$ (an error reduction of approximately $9.3\%$ ) over the local CRF baseline (Local + Viterbi, $85.51\%$ ) and substantially outperforming Relational Markov Network baselines (Bunescu and Mooney, 2004). The improvement over the baseline is statistically significant at $p < 0.05$ with a trial standard deviation of $0.083\%$ .

Knowl 8 — Information Extraction Performance on CMU Seminar Announcements

data/table

Evaluating template consistency constraints with Gibbs sampling on the CMU Seminar Announcements corpus (485 emails, 5-fold cross-validation) improves field-level extraction performance across start time (STIME), end time (ETIME), speaker (SPEAK), and location (LOC).

Approach	STIME	ETIME	SPEAK	LOC	ALL ( $F_1$ )
SM CRF	97.5	97.5	88.3	77.3	90.2
SM Skip-CRF	96.7	97.2	88.1	80.4	90.6
Local + Viterbi	96.67	97.36	83.39	89.98	91.85
NonLoc + Gibbs	97.11	97.89	84.16	90.00	92.29

Evaluation is measured as per-token $F_1$ averaged across the four target fields. The non-local Gibbs inference method achieves an overall average $F_1$ of $92.29\%$ , outperforming the local CRF baseline ( $91.85\%$ ) with greater than $95\%$ confidence ( $p < 0.05$ ) and surpassing the Skip-Chain CRF model of Sutton and McCallum ( $90.6\%$ ).

Knowl 9 — Computational Overhead and Decoding Latency of Gibbs Sampling
limitation
The primary drawback of simulated annealing Gibbs sampling relative to Viterbi dynamic programming is a substantial increase in inference time. Drawing 100 to 200 sequence sweeps per document increases evaluation time by more than an order of magnitude:
- On the CoNLL 2003 English test set (231 documents), average evaluation runtime across 3 runs increases from 55 seconds using Viterbi decoding to 1,738 seconds using Gibbs sampling (a 31.6-fold increase in latency).
- On the CMU Seminar Announcements corpus (485 documents), average evaluation runtime across 3 runs increases from 189 seconds using Viterbi decoding to 6,436 seconds using Gibbs sampling (a 34.1-fold increase in latency).

Coverage note — None was omitted; all contributed models, equations, algorithms, experimental tables, and limitations are fully covered.

References

1.S. Abney. 1997. Stochastic attribute-value grammars. Computational Linguistics, 23:597–618.
2.C. Andrieu, N. de Freitas, A. Doucet, and M. I. Jordan. 2003. An introduction to MCMC for machine learning. Machine Learning, 50:5–43.
3.A. Borthwick. 1999. A Maximum Entropy Approach to Named Entity Recognition. Ph.D. thesis, New York University.
4.R. Bunescu and R. J. Mooney. 2004. Collective information extraction with relational Markov networks. In Proceedings of the 42nd ACL, pages 439–446.
5.H. L. Chieu and H. T. Ng. 2002. Named entity recognition: a maximum entropy approach using global information. In Proceedings of the 19th Coling, pages 190–196.
6.R. G. Cowell, A. Philip Dawid, S. L. Lauritzen, and D. J. Spiegelhalter. 1999. Probabilistic Networks and Expert Systems. Springer-Verlag, New York.
7.J. R. Curran and S. Clark. 2003. Language independent NER using a maximum entropy tagger. In Proceedings of the 7th CoNLL, pages 164–167.
8.S. Della Pietra, V. Della Pietra, and J. Lafferty. 1997. Inducing features of random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19:380–393.
9.J. Finkel, S. Dingare, H. Nguyen, M. Nissim, and C. D. Manning. 2004. Exploiting context for biomedical entity recognition: from syntax to the web. In Joint Workshop on Natural Language Processing in Biomedicine and Its Applications at Coling 2004.
10.D. Freitag and A. McCallum. 1999. Information extraction with HMMs and shrinkage. In Proceedings of the AAAI-99 Workshop on Machine Learning for Information Extraction.
11.D. Freitag. 1998. Machine learning for information extraction in informal domains. Ph.D. thesis, Carnegie Mellon University.
12.S. Geman and D. Geman. 1984. Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Transitions on Pattern Analysis and Machine Intelligence, 6:721–741.
13.M. Kim, Y. S. Han, and K. Choi. 1995. Collocation map for overcoming data sparseness. In Proceedings of the 7th EACL, pages 53–59.
14.S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by simulated annealing. Science, 220:671–680.
15.P. J. Van Laarhoven and E. H. L. Arts. 1987. Simulated Annealing: Theory and Applications. Reidel Publishers.
16.J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional Random Fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the 18th ICML, pages 282–289. Morgan Kaufmann, San Francisco, CA.
17.T. R. Leek. 1997. Information extraction using hidden Markov models. Master's thesis, U.C. San Diego.
18.R. Malouf. 2002. Markov models for language-independent named entity recognition. In Proceedings of the 6th CoNLL, pages 187–190.
19.A. Mikheev, M. Moens, and C. Grover. 1999. Named entity recognition without gazetteers. In Proceedings of the 9th EACL, pages 1–8.
20.L. R. Rabiner. 1989. A tutorial on Hidden Markov Models and selected applications in speech recognition. Proceedings of the IEEE, 77(2):257–286.
21.C. Sutton and A. McCallum. 2004. Collective segmentation and labeling of distant entities in information extraction. In ICML Workshop on Statistical Relational Learning and Its connections to Other Fields.
22.B. Taskar, P. Abbeel, and D. Koller. 2002. Discriminative probabilistic models for relational data. In Proceedings of the 18th Conference on Uncertianty in Artificial Intelligence (UAI-02), pages 485–494, Edmonton, Canada.

Citation

MLA

Finkel, J. R., et al. “Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling”. Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), 2005, pp. 363–70, https://doi.org/10.3115/1219840.1219885.

APA

Finkel, J. R., Grenager, T., & Manning, C. D. (2005). Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling. Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), 363–370. https://doi.org/10.3115/1219840.1219885

Chicago

Finkel, J. R., T. Grenager, and C. D. Manning. 2005. “Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling”. Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), 363–70. https://doi.org/10.3115/1219840.1219885.

Harvard

Finkel, J.R., Grenager, T. and Manning, C.D. (2005) “Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling”, Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05). Association for Computational Linguistics, pp. 363–370. Available at: https://doi.org/10.3115/1219840.1219885.

Vancouver

1. Finkel JR, Grenager T, Manning CD (2005) Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling. In: Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05). Association for Computational Linguistics, pp 363–370

BibTeX

@inproceedings{finkel-etal-2005-incorporating,
    title = "Incorporating Non-local Information into Information Extraction Systems by {G}ibbs Sampling",
    author = "Finkel, Jenny Rose  and
      Grenager, Trond  and
      Manning, Christopher",
    editor = "Knight, Kevin  and
      Ng, Hwee Tou  and
      Oflazer, Kemal",
    booktitle = "Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics ({ACL}{'}05)",
    month = jun,
    year = "2005",
    address = "Ann Arbor, Michigan",
    publisher = "Association for Computational Linguistics",
    url = "https://aclanthology.org/P05-1045/",
    doi = "10.3115/1219840.1219885",
    pages = "363--370"
}

Metadata:ACL Anthology

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by-nc-sa/4.0/

Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Factored Sequence Model Combining Local CRFs with Non-Local Constraints

Knowl 2 — Simulated Annealing Gibbs Sampling for Non-Local Sequence Decoding

Knowl 3 — Exponential Penalty Formulation for Non-Local Constraints

Knowl 4 — Empirical Bayes Non-Local Consistency Penalties for Named Entity Recognition

Knowl 5 — Extraction Template Consistency Constraints for Seminar Announcements

Knowl 6 — Equivalence of Annealed Gibbs Sampling to Viterbi Inference in Linear-Chain CRFs

Knowl 7 — Named Entity Recognition Performance on CoNLL 2003 Dataset

Knowl 8 — Information Extraction Performance on CMU Seminar Announcements

Knowl 9 — Computational Overhead and Decoding Latency of Gibbs Sampling

References

Citation

BibTeX

Source Code

Access the Paper