Segment-Based Hidden Markov Models for Information Extraction

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 481–488, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Segment-based Hidden Markov Models for Information Extraction Zhenmei Gu David R. Cheriton School of Computer Science University of Waterloo Waterloo, Ontario, Canada N2l 3G1 z2gu@uwaterloo.ca Nick Cercone Faculty of Computer Science Dalhousie University Halifax, Nova Scotia, Canada B3H 1W5 nick@cs.dal.ca Abstract Hidden Markov models (HMMs) are pow- erful statistical models that have found successful applications in Information Ex- traction (IE). In current approaches to ap- plying HMMs to IE, an HMM is used to model text at the document level. This modelling might cause undesired redun- dancy in extraction in the sense that more than one filler is identified and extracted. We propose to use HMMs to model text at the segment level, in which the extrac- tion process consists of two steps: a seg- ment retrieval step followed by an extrac- tion step. In order to retrieve extraction- relevant segments from documents, we in- troduce a method to use HMMs to model and retrieve segments. Our experimen- tal results show that the resulting segment HMM IE system not only achieves near zero extraction redundancy, but also has better overall extraction performance than traditional document HMM IE systems. 1 Introduction A Hidden Markov Model (HMM) is a finite state automaton with stochastic state transitions and symbol emissions (Rabiner, 1989). The automa- ton models a random process that can produce a sequence of symbols by starting from some state, transferring from one state to another state with a symbol being emitted at each state, un- til a final state is reached. Formally, a hidden Markov model (HMM) is specified by a five-tuple (S, K, Π, A, B), where S is a set of states; K is the alphabet of observation symbols; Π is the initial state distribution; A is the probability distribution of state transitions; and B is the probability distri- bution of symbol emissions. When the structure of an HMM is determined, the complete model para- meters can be represented as λ = (A, B, Π). HMMs are particularly useful in modelling se- quential data. They have been applied in several areas within natural language processing (NLP), with one of the most successful efforts in speech recognition. HMMs have also been applied in information extraction. An early work of using HMMs for IE is (Leek, 1997) in which HMMs are trained to extract gene name-location facts from a collection of scientific abstracts. Another related work is (Bikel et al., 1997) which used HMMs as part of its modelling for the name finding problem in information extraction. A more recent work on applying HMMs to IE is (Freitag and McCallum, 1999), in which a sep- arate HMM is built for extracting fillers for each slot. To train an HMM for extracting fillers for a specific slot, maximum likelihood estimation is used to determine the probabilities (i.e., the ini- tial state probabilities, the state transition proba- …

Content truncated to 500 words