Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
ScholarlyCommons (University of Pennsylvania)Published 28 June 2001Open access
John Lafferty, Andrew McCallum, Fernando C. N. Pereira
Citations12,978
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work presents iterative parameter estimation algorithms for conditional random fields and compares the performance of the resulting models to HMMs and MEMMs on synthetic and natural-language data.
Abstract
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.
Keywords
Computer Science
Journal of Computer and System SciencesA Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
20,320 Citations1997Yoav Freund, Robert E. Schapire
Foundations of statistical natural language processing
9,996 Citations1999Christopher D. Manning, Hinrich Schütze
Biological sequence analysis probabilistic models of proteins and nucleic acids
3,654 Citations2010Richard Durbin
Computational LinguisticsA maximum entropy approach to natural language processing
3,120 Citations1996Adam Berger, Vincent J. Della Pietra +1 more
A maximum-likelihood approach for automatically constructing maximum entropy models is presented and how to implement this approach efficiently is described, using as examples several problems in natural language processing.
Transformation-based error-driven learning and natural language processing: a case study in part-of-speech tagging
1,531 Citations1995Eric Brill
This paper describes a simple rule-based approach to automated learning of linguistic knowledge that has been shown for a number of tasks to capture information in a clearer and more direct fashion without a compromise in performance.
Maximum Entropy Markov Models for Information Extraction and Segmentation
1,333 Citations2000Andrew McCallum, Dayne Freitag +1 more
A new Markovian sequence model is presented that allows observations to be represented as arbitrary overlapping features (such as word, capitalization, formatting, part-of-speech), and defines the conditional probability of state sequences given observation sequences.
Maximum Entropy Model for Part-Of-Speech Tagging
1,276 Citations1996Adwait Ratnaparkhi
A statistical model which trains from a corpus annotated with Part Of Speech tags and assigns them to previously unseen text with state of the art accuracy and discusses the corpus consistency problems discovered during the implementation of these features.
The Annals of Mathematical StatisticsGeneralized Iterative Scaling for Log-Linear Models
1,203 Citations1972J. N. Darroch, D. Ratcliff
IEEE Transactions on Pattern Analysis and Machine IntelligenceInducing features of random fields
1,044 Citations1997S. Della Pietra, V. Della Pietra +1 more
The random field models and techniques introduced in this paper differ from those common to much of the computer vision literature in that the underlying random fields are non-Markovian and have a large number of parameters that must be estimated.
Finite-state transducers in language and speech processing
919 Citations1997Mehryar Mohri
Machine LearningLogistic Regression, AdaBoost and Bregman Distances
689 Citations2002Michael Collins, Robert E. Schapire +1 more
A unified account of boosting and logistic regression in which each learning problem is cast in terms of optimization of Bregman distances, and a parameterized family of algorithms that includes both a sequential- and a parallel-update algorithm as special cases are described, thus showing how the sequential and parallel approaches can themselves be unified.
Discriminative Reranking for Natural Language Parsing
443 Citations2000Michael J. Collins
Information Extraction with HMM Structures Learned by Stochastic Optimization
286 Citations2000Dayne Freitag, Andrew McCallum
This paper demonstrates that extraction accuracy strongly depends on the selection of structure, and presents an algorithm for automatically finding good structures by stochastic optimization, which finds HMM models that almost always out-perform a fixed model, and have superior average performance across tasks.
arXiv (Cornell University)Learning to Resolve Natural Language Ambiguities: A Unified Approach
175 Citations1998Dan Roth
An extensive experimental comparison of the approach with other methods on several well studied lexical disambiguation tasks such as context-sensitive spelling correction, prepositional phrase attachment and part of speech tagging shows that it outperforms other methods tried for these tasks or performs comparably to the best.
A comparison of several approximate algorithms for finding multiple (N-best) sentence hypotheses
144 Citations1991Richard Schwartz, S. Austin
The authors introduce a new, more efficient algorithm, the word-dependent N-best algorithm, for finding multiple sentence hypotheses, based on the assumption that the beginning time of a word depends only on the preceding word.
Theoretical Computer ScienceMinimization algorithms for sequential transducers
133 Citations2000Mehryar Mohri
Algorithms for minimizing sequential finite-state transducers that output strings or numbers are presented and are shown to be efficient since in the case of acyclic transducers and for output strings.
Boosting Applied to Tagging and PP Attachment
116 Citations1999Steven Abney, Robert E. Schapire +1 more
This paper applies boosting, a machine learning algorithm that is not well known in computational linguistics, to part-of-speech tagging and prepositional phrase attachment to improve data quality and identify annotation errors.
Boltzmann Chains and Hidden Markov Models
67 Citations1994Lawrence K. Saul, Michael I. Jordan
A statistical mechanical framework for the modeling of discrete time series is proposed, and maximum likelihood estimation is done via Boltzmann learning in one-dimensional networks with tied weights, which motivates new architectures that address particular shortcomings of HMMs.
A whole sentence maximum entropy language model
57 Citations2002Roni Rosenfeld
A new kind of language model, which models whole sentences or utterances directly using the maximum entropy (ME) paradigm, which is conceptually simpler, and more naturally suited to modeling whole-sentence phenomena, than the conditional ME models proposed to date.
Neural ComputationEquivalence of Linear Boltzmann Chains and Hidden Markov Models
18 Citations1996David Mackay
It is demonstrated that under the simple condition that the state sequence has a mandatory end state, the probability distribution assign by a strictly linear Boltzmann chain is identical to that assigned by a hidden Markov model.