Elamur Research⌕
☰
home / papers / 2005 / Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling

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

Summary

HMMs, CMMs and CRFs, among other sequence models, depend on the Markov property to keep Viterbi decoding exact and inexpensive. The cost is that they ignore long-range regularities. For example, the same name should get the same label wherever it appears in a document. The authors replace Viterbi with Gibbs sampling combined with simulated annealing. This approximate decoder only needs each label's conditional distribution given the rest of the sequence, so extra non-local factors can be multiplied in at test time. They first show that, on a plain CRF, the annealed sampler matches Viterbi accuracy. They then add two kinds of constraint models on top of an already-trained CRF:

  • label consistency for repeated entities in the CoNLL 2003 NER data;
  • template consistency for fields in the CMU Seminar Announcements data.

This reduces errors by up to 9% relative to state-of-the-art systems, with gains significant at over 95% confidence. The approach matters because it is simple, probabilistically principled, and attachable to any existing sequence model. Its price is much slower inference.

Key points

  • With 10 randomly initialized runs, each using a linear annealing schedule of 1000 full passes over the sequence, Gibbs decoding of a basic CRF matched Viterbi:
    • CoNLL: 85.51 per-entity F1 for both.
    • CMU Seminars: 91.85 per-token F1 for both.
  • CMU Seminar Announcements setup:
    • 485 emails annotated with four fields (speaker, location, start time, end time).
    • 5-fold cross-validation using Sutton and McCallum's splits.
    • Evaluation uses class-averaged per-token F1.
  • The non-local models cut errors by up to 9%. Results across trials were stable:
    • Standard deviations were 0.083% (CoNLL) and 0.007% (Seminars).
    • Minimum F-scores were 86.72 (CoNLL) and 92.28 (Seminars).
  • Drawing 100 samples made testing much slower:
    • CoNLL: from 55 to 1738 seconds.
    • Seminars: from 189 to 6436 seconds.
  • The CRF was trained with a quadratic prior and quasi-Newton optimization. The non-local constraints are applied only at inference, so no retraining is needed.

Interesting ideas

  • I1. Swap the decoder, not the model. Annealed Gibbs sampling can replace exact dynamic-programming decoding. Any scoring term then becomes usable, however non-local, provided you can compute a label's conditional score given the others. This is handy for adding document-level knowledge to an existing tagger.
  • I2. Annealing as a temperature knob. The sampler raises each conditional distribution to a power that grows over time, then renormalizes. This gradually turns random sampling into hill-climbing, giving a generic way to approximately maximize hard, non-convex objectives in structured prediction.
  • I3. Sanity-check the approximation first. Before adding new constraints, the authors confirmed that the approximate decoder reproduces exact Viterbi results on the unchanged model. This cleanly separates gains from the new constraints from artifacts of the inference method, which is a good evaluation habit for any approximate method.
  • I4. Constraints keyed on labels, not surface form. Prior skip-chain and RMN approaches link tokens that look alike. Here a penalty can fire whenever two spans share a label but disagree, for example two inconsistent start times. This suits template filling and other tasks where related items look nothing alike.
  • I5. Layer constraints over pretrained models. The consistency model sits on top of a trained sequence model in a factored setup. Standard, well-tuned training pipelines therefore remain untouched, which lowers the cost of trying new global constraints on any HMM, CMM, CRF or even heuristic tagger.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Information extraction

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/1219840.1219885

@inproceedings{finkel2005incorporating,
  title = {{Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling}},
  author = {Finkel, Jenny Rose and Grenager, Trond and Manning, Christopher},
  booktitle = {Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)},
  year = {2005},
  doi = {10.3115/1219840.1219885},
  url = {https://doi.org/10.3115/1219840.1219885}
}

References

22 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. S. Abney. 1997. Stochastic attribute-value grammars. Computational Linguistics, 23:597–618. find
  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. find
  3. A. Borthwick. 1999. A Maximum Entropy Approach to Named Entity Recognition. Ph.D. thesis, New York University. find
  4. R. Bunescu and R. J. Mooney. 2004. Collective information extraction with relational Markov networks. In Proceedings of the 42nd ACL, pages 439–446. find
  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. find
  6. R. G. Cowell, A. Philip Dawid, S. L. Lauritzen, and D. J. Spiegelhalter. 1999. Probabilistic Networks and Expert Systems. Springer-Verlag, New York. find
  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. find
  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. find
  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. find
  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. find
  11. D. Freitag. 1998. Machine learning for information extraction in informal domains. Ph.D. thesis, Carnegie Mellon University. find
  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. find
  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. find
  14. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by simulated annealing. Science, 220:671–680. find
  15. P. J. Van Laarhoven and E. H. L. Arts. 1987. Simulated Annealing: Theory and Applications. Reidel Publishers. find
  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. find
  17. T. R. Leek. 1997. Information extraction using hidden Markov models. Master’s thesis, U.C. San Diego. find
  18. R. Malouf. 2002. Markov models for language-independent named entity recognition. In Proceedings of the 6th CoNLL, pages 187–190. find
  19. A. Mikheev, M. Moens, and C. Grover. 1999. Named entity recognition without gazetteers. In Proceedings of the 9th EACL, pages 1–8. find
  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. find
  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. find
  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. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/finkel-2005-incorporating-non-local-information-into/