Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

We present Conditional Random Fields, a framework
\nfor building probabilistic models to segment
\nand label sequence data. Conditional random
\nfields offer several advantages over hidden
\nMarkov models and stochastic grammars
\nfor such tasks, including the ability to relax
\nstrong independence assumptions made in those
\nmodels. Conditional random fields also avoid
\na fundamental limitation of maximum entropy
\nMarkov models (MEMMs) and other discriminative
\nMarkov models based on directed graphical
\nmodels, which can be biased towards states
\nwith few successor states. We present iterative
\nparameter estimation algorithms for conditional
\nrandom fields and compare the performance of
\nthe resulting models to HMMs and MEMMs on
\nsynthetic and natural-language data.