Conditional random field


Conditional random fields are a class of statistical modeling method often applied in pattern recognition and machine learning and used for structured prediction. Whereas a classifier predicts a label for a single sample without considering "neighboring" samples, a CRF can take context into account. To do so, the prediction is modeled as a graphical model, which implements dependencies between the predictions. What kind of graph is used depends on the application. For example, in natural language processing, linear chain CRFs are popular, which implement sequential dependencies in the predictions. In image processing the graph typically connects locations to nearby and/or similar locations to enforce that they receive similar predictions.
Other examples where CRFs are used are: labeling or parsing of sequential data for natural language processing or biological sequences, POS tagging, shallow parsing, named entity recognition, gene finding, peptide critical functional region finding, and object recognition and image segmentation in computer vision.

Description

CRFs are a type of discriminative undirected probabilistic graphical model.
Lafferty, McCallum and Pereira define a CRF on observations and random variables as follows:
Let be a graph such that
so that is indexed by the vertices of.
Then is a conditional random field when the random variables, conditioned on, obey the Markov property with
respect to the graph:, where means
that and are neighbors in.

What this means is that a CRF is an undirected graphical model whose nodes can be divided into exactly two disjoint sets and, the observed and output variables, respectively; the conditional distribution is then modeled.

Inference

For general graphs, the problem of exact inference in CRFs is intractable. The inference problem for a CRF is basically the same as for an MRF and the same arguments hold.
However, there exist special cases for which exact inference is feasible:
If exact inference is impossible, several algorithms can be used to obtain approximate solutions. These include:
Learning the parameters is usually done by maximum likelihood learning for. If all nodes have exponential family distributions and all nodes are observed during training, this optimization is convex. It can be solved for example using gradient descent algorithms, or Quasi-Newton methods such as the L-BFGS algorithm. On the other hand, if some variables are unobserved, the inference problem has to be solved for these variables. Exact inference is intractable in general graphs, so approximations have to be used.

Examples

In sequence modeling, the graph of interest is usually a chain graph. An input sequence of observed variables represents a sequence of observations and represents a hidden state variable that needs to be inferred given the observations. The are structured to form a chain, with an edge between each and. As well as having a simple interpretation of the as "labels" for each element in the input sequence, this layout admits efficient algorithms for:
The conditional dependency of each on is defined through a fixed set of feature functions of the form, which can be thought of as measurements on the input sequence that partially determine the likelihood of each possible value for. The model assigns each feature a numerical weight and combines them to determine the probability of a certain value for.
Linear-chain CRFs have many of the same applications as conceptually simpler hidden Markov models, but relax certain assumptions about the input and output sequence distributions. An HMM can loosely be understood as a CRF with very specific feature functions that use constant probabilities to model state transitions and emissions. Conversely, a CRF can loosely be understood as a generalization of an HMM that makes the constant transition probabilities into arbitrary functions that vary across the positions in the sequence of hidden states, depending on the input sequence.
Notably, in contrast to HMMs, CRFs can contain any number of feature functions, the feature functions can inspect the entire input sequence at any point during inference, and the range of the feature functions need not have a probabilistic interpretation.

Variants

Higher-order CRFs and semi-Markov CRFs

CRFs can be extended into higher order models by making each dependent on a fixed number of previous variables. In conventional formulations of higher order CRFs, training and inference are only practical for small values of , since their computational cost increases exponentially with.
However, another recent advance has managed to ameliorate these issues by leveraging concepts and tools from the field of Bayesian nonparametrics. Specifically, the CRF-infinity approach constitutes a CRF-type model that is capable of learning infinitely-long temporal dynamics in a scalable fashion. This is effected by introducing a novel potential function for CRFs that is based on the Sequence Memoizer, a nonparametric Bayesian model for learning infinitely-long dynamics in sequential observations. To render such a model computationally tractable, CRF-infinity employs a mean-field approximation of the postulated novel potential functions. This allows for devising efficient approximate training and inference algorithms for the model, without undermining its capability to capture and model temporal dependencies of arbitrary length.
There exists another generalization of CRFs, the semi-Markov conditional random field , which models variable-length segmentations of the label sequence. This provides much of the power of higher-order CRFs to model long-range dependencies of the, at a reasonable computational cost.
Finally, large-margin models for structured prediction, such as the structured Support Vector Machine can be seen as an alternative training procedure to CRFs.

Latent-dynamic conditional random field

Latent-dynamic conditional random fields or discriminative probabilistic latent variable models are a type of CRFs for sequence tagging tasks. They are latent variable models that are trained discriminatively.
In an LDCRF, like in any sequence tagging task, given a sequence of observations x =, the main problem the model must solve is how to assign a sequence of labels y = from one finite set of labels. Instead of directly modeling as an ordinary linear-chain CRF would do, a set of latent variables h is "inserted" between x and y using the chain rule of probability:
This allows capturing latent structure between the observations and labels. While LDCRFs can be trained using quasi-Newton methods, a specialized version of the perceptron algorithm called the latent-variable perceptron has been developed for them as well, based on Collins' structured perceptron algorithm. These models find applications in computer vision, specifically gesture recognition from video streams and shallow parsing.

Software

This is a partial list of software that implement generic CRF tools.
This is a partial list of software that implement CRF related tools.