Skip to content
Last Dictionary
Plane
Machine LearningMathematics & Statistics

conditional random field

nounAlso: CRF, CRFs, linear-chain CRF

In plain wordsA statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time.

  1. A discriminativediscriminative model, n.: A model that learns only to tell things apart — spam or not spam, cat or dog — without learning how to produce new examples of those things. undirected probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together. that defines the conditional probability of a whole label structure y given an observed input x, rather than the joint probability of both. In the common linear-chain form, a label sequence is scored by a weighted sum of feature functions over adjacent label pairs and the entire input; the score is exponentiated and normalized by a partition function Z(x) taken over all possible label sequences. Because normalization is global rather than per position, CRFs avoid the label bias problem of maximum-entropy Markov models, and unlike hidden Markov modelshidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds. they can use rich, overlapping features of the input. Training maximizes conditional log-likelihood; the forward–backward algorithm gives marginals and the Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination. the best sequence. CRFs were a leading approach to named-entity recognitionnamed-entity recognition, n.: Software that spots names and similar expressions in text and labels each by type: in 'Maria flew from Lagos to Paris on Monday', it marks a person, two cities and a date., shallow parsing and part-of-speech taggingpart-of-speech tagging, n.: Labeling each word in a sentence with its grammatical role — noun, verb, adjective and so on — as in 'Time (noun) flies (verb) like (preposition) an arrow'. in the 2000s and survive as the output layer of neural taggers such as the BiLSTM-CRF.

    Adding a CRF layer on top of the BiLSTM stopped the tagger from predicting an I-PER tag straight after an O.

p(y∣x)=1Z(x)exp⁡(∑t=1T∑kλkfk(yt−1,yt,x,t))p(\mathbf{y} \mid \mathbf{x}) = \frac{1}{Z(\mathbf{x})} \exp\Big( \sum_{t=1}^{T} \sum_{k} \lambda_k f_k(y_{t-1}, y_t, \mathbf{x}, t) \Big)

Origin

Introduced by John Lafferty, Andrew McCallum and Fernando Pereira at ICML 2001 as a remedy for the label bias of maximum-entropy Markov models. Fei Sha and Pereira's 2003 shallow-parsing results helped make CRFs the standard sequence labeler of the decade; Zhiheng Huang, Wei Xu and Kai Yu (2015) and Guillaume Lample and colleagues (2016) paired them with recurrent neural encoders.

Usage note

A CRF is a Markov random fieldMarkov random field, n.: A model of many linked uncertain quantities, such as neighboring pixels in a photo, in which each one depends directly only on its neighbors, with no notion of which one causes which. conditioned on the input. Logistic regressionlogistic regression, n.: A simple, widely used method for yes-or-no predictions that outputs a probability — say, a 70% chance a customer cancels — by passing a weighted sum of inputs through an S-shaped curve. is the single-position special case. A linear-chain CRF is to a hidden Markov model what logistic regression is to naive Bayes: the discriminative counterpart of a generative model with the same structure.

Related

See also
  • hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds.
  • Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination.
  • Markov random fieldMarkov random field, n.: A model of many linked uncertain quantities, such as neighboring pixels in a photo, in which each one depends directly only on its neighbors, with no notion of which one causes which.
  • probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together.
  • named-entity recognitionnamed-entity recognition, n.: Software that spots names and similar expressions in text and labels each by type: in 'Maria flew from Lagos to Paris on Monday', it marks a person, two cities and a date.
  • part-of-speech taggingpart-of-speech tagging, n.: Labeling each word in a sentence with its grammatical role — noun, verb, adjective and so on — as in 'Time (noun) flies (verb) like (preposition) an arrow'.
  • logistic regressionlogistic regression, n.: A simple, widely used method for yes-or-no predictions that outputs a probability — say, a 70% chance a customer cancels — by passing a weighted sum of inputs through an S-shaped curve.
Contrast with
  • hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds.
  • generative modelgenerative model, n.: A model that learns what a kind of data looks like — faces, sentences, songs — well enough to produce new examples that resemble the originals without copying them.

Sources

  1. Lafferty, J., McCallum, A. & Pereira, F. (2001). Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data. Proc. ICML 2001.
  2. Sutton, C. & McCallum, A. (2012). An Introduction to Conditional Random Fields. Foundations and Trends in Machine Learning 4(4).

Mentioned in

hidden Markov modelhidden Markov model, n.: A model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds., probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together., Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination., Markov random fieldMarkov random field, n.: A model of many linked uncertain quantities, such as neighboring pixels in a photo, in which each one depends directly only on its neighbors, with no notion of which one causes which.