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

Proceedings of the 43rd Annual Meeting of the ACL, pages 363–370, Ann Arbor, June 2005. c⃝2005 Association for Computational Linguistics Incorporating Non-local Information into Information Extraction Systems by Gibbs Sampling Jenny Rose Finkel, Trond Grenager, and Christopher Manning Computer Science Department Stanford University Stanford, CA 94305 {jrfinkel, grenager, mannning}@cs.stanford.edu Abstract Most current statistical natural language process- ing 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 sam- pling, a simple Monte Carlo method used to per- form approximate inference in factored probabilis- tic models. By using simulated annealing in place of Viterbi decoding in sequence models such as HMMs, CMMs, and CRFs, it is possible to incorpo- rate 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 consis- tency 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 Most statistical models currently used in natural lan- guage processing represent only local structure. Al- though this constraint is critical in enabling tractable model inference, it is a key limitation in many tasks, since natural language contains a great deal of non- local structure. A general method for solving this problem is to relax the requirement of exact infer- ence, substituting approximate inference algorithms instead, thereby permitting tractable inference in models with non-local structure. One such algo- rithm is Gibbs sampling, a simple Monte Carlo algo- rithm that is appropriate for inference in any factored probabilistic model, including sequence models and probabilistic context free grammars (Geman and Ge- man, 1984). Although Gibbs sampling is widely used elsewhere, there has been extremely little use of it in natural language processing.1 Here, we use it to add non-local dependencies to sequence models for information extraction. Statistical hidden state sequence models, such as Hidden Markov Models (HMMs) (Leek, 1997; Freitag and McCallum, 1999), Conditional Markov Models (CMMs) (Borthwick, 1999), and Condi- tional Random Fields (CRFs) (Lafferty et al., 2001) are a prominent recent approach to information ex- traction tasks. These models all encode the Markov property: decisions about the state at a particular po- sition in the sequence can depend only on a small lo- cal window. It is this property which allows tractable computation: the Viterbi, Forward Backward, and Clique Calibration algorithms all become intractable without it. However, information extraction tasks can benefit from modeling non-local structure. As an example, several authors (see Section 8) mention the value of enforcing label consistency in named entity recogni- tion (NER) tasks. In the example given in Figure 1, the second occurrence of the token Tanjug is mis- labeled by our CRF-based statistical NER system, because by looking only at local evidence it is un- clear whether it is a person or …

Content truncated to 500 words