文档介绍：Maximum Entropy Markov Models
for Information Extraction and Segmentation
Andrew McCallum, Dayne Freitag, and Fernando Pereira
17th International Conf. on Machine Learning, 2000
Presentation by Gyozo Gidofalvi
Computer Science and Engineering Department
University of California, San Diego
******@
May 7, 2002
1
Outline
• Modeling sequential data with HMMs
• Problems with previous methods: motivation
• Maximum entropy Markov model (MEMM)
• Segmentation of FAQs: experiments and results
• Conclusions
2
Background
• A large amount of text is available on the
– We need algorithms to process and analyze this text
• Hidden Markov models (HMMs), a “powerful tool
for representing sequential data,” have been
essfully applied to:
– Part-of-speech tagging:
<PRP>He</PRP> <VB>books</VB> <NNS>tickets</NNS>
– Text segmentation and event tracking:
tracking non-rigid motion in video sequences
– Named entity recognition:
<ORG>Mips</ORG> Vice President <PRS>John Hime</PRS>
– Information extraction:
<TIME>After lunch</TIME> meet <LOC>under the oak tree</LOC>
3
Brief overview of HMMs
• An HMM is a finite state automaton with
stochastic state transitions and observations.
• Formally: An HMM is
Dependency graph
– a finite set of states S
– a finite set of observations O evidence
– two conditional probability distributions: cause
• for s given s’: P(s|s’) s’ s
• for o given s: P(o|s)
o
– the initial state distribution P0(s)
4
The “three classical problems” of HMMs
• Evaluation problem: Given an HMM, determine the probability of a
=
given observation sequence oo 1 ,, ! o T :
Po()= ∑ Po ( | s )() Ps
s
• Decoding problem: Given a model and an observation sequence,
determine the most likely states that led to the observation sequence
ss= ,,! s:
1 T arg maxPo ( | s )
s
• Learning problem: Suppose we are given the structure of a model
(S, O) only. Given a set of observation sequenc