Conditional random field

Last updated December 17, 2024

Conditional random fields (CRFs) are a class of statistical modeling methods 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 "neighbouring" samples, a CRF can take context into account. To do so, the predictions are modelled as a graphical model, which represents the presence of dependencies between the predictions. The kind of graph used depends on the application. For example, in natural language processing, "linear chain" CRFs are popular, for which each prediction is dependent only on its immediate neighbours. 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,^[1] part-of-speech tagging, shallow parsing,^[2] named entity recognition,^[3] gene finding, peptide critical functional region finding,^[4] and object recognition ^[5] and image segmentation in computer vision.^[6]

Description

CRFs are a type of discriminative undirected probabilistic graphical model.

Lafferty, McCallum and Pereira^[1] define a CRF on observations ${\boldsymbol {X}}$ and random variables ${\boldsymbol {Y}}$ as follows:

Let $G=(V,E)$ be a graph such that ${\boldsymbol {Y}}=({\boldsymbol {Y}}_{v})_{v\in V}$ , so that ${\boldsymbol {Y}}$ is indexed by the vertices of $G$ .
Then $({\boldsymbol {X}},{\boldsymbol {Y}})$ is a conditional random field when each random variable ${\boldsymbol {Y}}_{v}$ , conditioned on ${\boldsymbol {X}}$ , obeys the Markov property with respect to the graph; that is, its probability is dependent only on its neighbours in G:
$P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\neq v\})=P({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},\{{\boldsymbol {Y}}_{w}:w\sim v\})$ , where ${\mathit {w}}\sim v$ means that $w$ and $v$ are neighbors in $G$ .

What this means is that a CRF is an undirected graphical model whose nodes can be divided into exactly two disjoint sets ${\boldsymbol {X}}$ and ${\boldsymbol {Y}}$ , the observed and output variables, respectively; the conditional distribution $p({\boldsymbol {Y}}|{\boldsymbol {X}})$ 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.^[7] However, there exist special cases for which exact inference is feasible:

If the graph is a chain or a tree, message passing algorithms yield exact solutions. The algorithms used in these cases are analogous to the forward-backward and Viterbi algorithm for the case of HMMs.
If the CRF only contains pair-wise potentials and the energy is submodular, combinatorial min cut/max flow algorithms yield exact solutions.

If exact inference is impossible, several algorithms can be used to obtain approximate solutions. These include:

Loopy belief propagation
Alpha expansion
Mean field inference
Linear programming relaxations

Parameter Learning

Learning the parameters $\theta$ is usually done by maximum likelihood learning for $p(Y_{i}|X_{i};\theta )$ . If all nodes have exponential family distributions and all nodes are observed during training, this optimization is convex.^[7] 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 $X$ represents a sequence of observations and $Y$ represents a hidden (or unknown) state variable that needs to be inferred given the observations. The $Y_{i}$ are structured to form a chain, with an edge between each $Y_{i-1}$ and $Y_{i}$ . As well as having a simple interpretation of the $Y_{i}$ as "labels" for each element in the input sequence, this layout admits efficient algorithms for:

model training, learning the conditional distributions between the $Y_{i}$ and feature functions from some corpus of training data.
decoding, determining the probability of a given label sequence $Y$ given $X$ .
inference, determining the most likely label sequence $Y$ given $X$ .

The conditional dependency of each $Y_{i}$ on $X$ is defined through a fixed set of feature functions of the form $f(i,Y_{i-1},Y_{i},X)$ , which can be thought of as measurements on the input sequence that partially determine the likelihood of each possible value for $Y_{i}$ . The model assigns each feature a numerical weight and combines them to determine the probability of a certain value for $Y_{i}$ .

Linear-chain CRFs have many of the same applications as conceptually simpler hidden Markov models (HMMs), 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 $X$ 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 $Y_{i}$ dependent on a fixed number $k$ of previous variables $Y_{i-k},...,Y_{i-1}$ . In conventional formulations of higher order CRFs, training and inference are only practical for small values of $k$ (such as k ≤ 5),^[8] since their computational cost increases exponentially with $k$ .

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^[9] 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 (SM), a nonparametric Bayesian model for learning infinitely-long dynamics in sequential observations.^[10] To render such a model computationally tractable, CRF-infinity employs a mean-field approximation ^[11] of the postulated novel potential functions (which are driven by an SM). 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 (semi-CRF), which models variable-length segmentations of the label sequence $Y$ .^[12] This provides much of the power of higher-order CRFs to model long-range dependencies of the $Y_{i}$ , 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 (LDCRF) or discriminative probabilistic latent variable models (DPLVM) 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 = $x_{1},\dots ,x_{n}$ , the main problem the model must solve is how to assign a sequence of labels y = $y_{1},\dots ,y_{n}$ from one finite set of labels $Y$ . Instead of directly modeling $P$ (y|x) 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:^[13]

P(\mathbf {y} |\mathbf {x} )=\sum _{\mathbf {h} }P(\mathbf {y} |\mathbf {h} ,\mathbf {x} )P(\mathbf {h} |\mathbf {x} )

This allows capturing latent structure between the observations and labels.^[14] 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.^[13] These models find applications in computer vision, specifically gesture recognition from video streams^[14] and shallow parsing.^[13]

Related Research Articles

A hidden Markov model (HMM) is a Markov model in which the observations are dependent on a latent Markov process. An HMM requires that there be an observable process $whose outcomes depend on the outcomes of in a known way. Since cannot be observed directly, the goal is to learn about state of by observing . By definition of being a Markov model, an HMM has an additional requirement that the outcome of at time must be "influenced" exclusively by the outcome of at and that the outcomes of and at must be conditionally independent of at given at time . Estimation of the parameters in an HMM can be performed using maximum likelihood estimation. For linear chain HMMs, the Baum-Welch algorithm can be used to estimate parameters.$

Pattern recognition is the task of assigning a class to an observation based on patterns extracted from data. While similar, pattern recognition (PR) is not to be confused with pattern machines (PM) which may possess (PR) capabilities but their primary function is to distinguish and create emergent patterns. PR has applications in statistical data analysis, signal processing, image analysis, information retrieval, bioinformatics, data compression, computer graphics and machine learning. Pattern recognition has its origins in statistics and engineering; some modern approaches to pattern recognition include the use of machine learning, due to the increased availability of big data and a new abundance of processing power.

In machine learning, the perceptron is an algorithm for supervised learning of binary classifiers. A binary classifier is a function which can decide whether or not an input, represented by a vector of numbers, belongs to some specific class. It is a type of linear classifier, i.e. a classification algorithm that makes its predictions based on a linear predictor function combining a set of weights with the feature vector.

A Bayesian network is a probabilistic graphical model that represents a set of variables and their conditional dependencies via a directed acyclic graph (DAG). While it is one of several forms of causal notation, causal networks are special cases of Bayesian networks. Bayesian networks are ideal for taking an event that occurred and predicting the likelihood that any one of several possible known causes was the contributing factor. For example, a Bayesian network could represent the probabilistic relationships between diseases and symptoms. Given symptoms, the network can be used to compute the probabilities of the presence of various diseases.

A graphical model or probabilistic graphical model (PGM) or structured probabilistic model is a probabilistic model for which a graph expresses the conditional dependence structure between random variables. They are commonly used in probability theory, statistics—particularly Bayesian statistics—and machine learning.

In statistics, an expectation–maximization (EM) algorithm is an iterative method to find (local) maximum likelihood or maximum a posteriori (MAP) estimates of parameters in statistical models, where the model depends on unobserved latent variables. The EM iteration alternates between performing an expectation (E) step, which creates a function for the expectation of the log-likelihood evaluated using the current estimate for the parameters, and a maximization (M) step, which computes parameters maximizing the expected log-likelihood found on the E step. These parameter-estimates are then used to determine the distribution of the latent variables in the next E step. It can be used, for example, to estimate a mixture of gaussians, or to solve the multiple linear regression problem.

In statistics, Gibbs sampling or a Gibbs sampler is a Markov chain Monte Carlo (MCMC) algorithm for sampling from a specified multivariate probability distribution when direct sampling from the joint distribution is difficult, but sampling from the conditional distribution is more practical. This sequence can be used to approximate the joint distribution ; to approximate the marginal distribution of one of the variables, or some subset of the variables ; or to compute an integral. Typically, some of the variables correspond to observations whose values are known, and hence do not need to be sampled.

In electrical engineering, statistical computing and bioinformatics, the Baum–Welch algorithm is a special case of the expectation–maximization algorithm used to find the unknown parameters of a hidden Markov model (HMM). It makes use of the forward-backward algorithm to compute the statistics for the expectation step. The Baum–Welch algorithm, the primary method for inference in hidden Markov models, is numerically unstable due to its recursive calculation of joint probabilities. As the number of variables grows, these joint probabilities become increasingly small, leading to the forward recursions rapidly approaching values below machine precision.

The forward algorithm, in the context of a hidden Markov model (HMM), is used to calculate a 'belief state': the probability of a state at a certain time, given the history of evidence. The process is also known as filtering. The forward algorithm is closely related to, but distinct from, the Viterbi algorithm.

<span class="mw-page-title-main">Markov random field</span> Set of random variables

In the domain of physics and probability, a Markov random field (MRF), Markov network or undirected graphical model is a set of random variables having a Markov property described by an undirected graph. In other words, a random field is said to be a Markov random field if it satisfies Markov properties. The concept originates from the Sherrington–Kirkpatrick model.

In statistics, multinomial logistic regression is a classification method that generalizes logistic regression to multiclass problems, i.e. with more than two possible discrete outcomes. That is, it is a model that is used to predict the probabilities of the different possible outcomes of a categorically distributed dependent variable, given a set of independent variables.

In statistics, binomial regression is a regression analysis technique in which the response has a binomial distribution: it is the number of successes in a series of ⁠ $⁠$ independent Bernoulli trials, where each trial has probability of success ⁠ $⁠$ . In binomial regression, the probability of a success is related to explanatory variables: the corresponding concept in ordinary regression is to relate the mean value of the unobserved response to explanatory variables.

Structured prediction or structured output learning is an umbrella term for supervised machine learning techniques that involves predicting structured objects, rather than discrete or real values.

Graphical models have become powerful frameworks for protein structure prediction, protein–protein interaction, and free energy calculations for protein structures. Using a graphical model to represent the protein structure allows the solution of many problems including secondary structure prediction, protein-protein interactions, protein-drug interaction, and free energy calculations.

In statistics, a maximum-entropy Markov model (MEMM), or conditional Markov model (CMM), is a graphical model for sequence labeling that combines features of hidden Markov models (HMMs) and maximum entropy (MaxEnt) models. An MEMM is a discriminative model that extends a standard maximum entropy classifier by assuming that the unknown values to be learnt are connected in a Markov chain rather than being conditionally independent of each other. MEMMs find applications in natural language processing, specifically in part-of-speech tagging and information extraction.

In statistics and in machine learning, a linear predictor function is a linear function of a set of coefficients and explanatory variables, whose value is used to predict the outcome of a dependent variable. This sort of function usually comes in linear regression, where the coefficients are called regression coefficients. However, they also occur in various types of linear classifiers, as well as in various other models, such as principal component analysis and factor analysis. In many of these models, the coefficients are referred to as "weights".

In machine learning, the kernel embedding of distributions comprises a class of nonparametric methods in which a probability distribution is represented as an element of a reproducing kernel Hilbert space (RKHS). A generalization of the individual data-point feature mapping done in classical kernel methods, the embedding of distributions into infinite-dimensional feature spaces can preserve all of the statistical features of arbitrary distributions, while allowing one to compare and manipulate distributions using Hilbert space operations such as inner products, distances, projections, linear transformations, and spectral analysis. This learning framework is very general and can be applied to distributions over any space $on which a sensible kernel function may be defined. For example, various kernels have been proposed for learning from data which are: vectors in, discrete classes/categories, strings, graphs/networks, images, time series, manifolds, dynamical systems, and other structured objects. The theory behind kernel embeddings of distributions has been primarily developed by Alex Smola, Le Song, Arthur Gretton, and Bernhard Schölkopf. A review of recent works on kernel embedding of distributions can be found in.$

The following outline is provided as an overview of, and topical guide to, machine learning:

Dependency networks (DNs) are graphical models, similar to Markov networks, wherein each vertex (node) corresponds to a random variable and each edge captures dependencies among variables. Unlike Bayesian networks, DNs may contain cycles. Each node is associated to a conditional probability table, which determines the realization of the random variable given its parents.

In network theory, collective classification is the simultaneous prediction of the labels for multiple objects, where each label is predicted using information about the object's observed features, the observed features and labels of its neighbors, and the unobserved labels of its neighbors. Collective classification problems are defined in terms of networks of random variables, where the network structure determines the relationship between the random variables. Inference is performed on multiple random variables simultaneously, typically by propagating information between nodes in the network to perform approximate inference. Approaches that use collective classification can make use of relational information when performing inference. Examples of collective classification include predicting attributes of individuals in a social network, classifying webpages in the World Wide Web, and inferring the research area of a paper in a scientific publication dataset.

References

1 2 Lafferty, J.; McCallum, A.; Pereira, F. (2001). "Conditional random fields: Probabilistic models for segmenting and labeling sequence data". Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. pp. 282–289.
↑ Sha, F.; Pereira, F. (2003). shallow parsing with conditional random fields.
↑ Settles, B. (2004). "Biomedical named entity recognition using conditional random fields and rich feature sets" (PDF). Proceedings of the International Joint Workshop on Natural Language Processing in Biomedicine and its Applications. pp. 104–107.
↑ Chang KY; Lin T-p; Shih L-Y; Wang C-K (2015). "Analysis and Prediction of the Critical Regions of Antimicrobial Peptides Based on Conditional Random Fields". PLOS ONE. 10 (3): e0119490. Bibcode:2015PLoSO..1019490C. doi: 10.1371/journal.pone.0119490 . PMC 4372350 . PMID 25803302.
↑ J.R. Ruiz-Sarmiento; C. Galindo; J. Gonzalez-Jimenez (2015). "UPGMpp: a Software Library for Contextual Object Recognition.". 3rd. Workshop on Recognition and Action for Scene Understanding (REACTS).
↑ He, X.; Zemel, R.S.; Carreira-Perpinñán, M.A. (2004). "Multiscale conditional random fields for image labeling". IEEE Computer Society. CiteSeerX 10.1.1.3.7826 .
1 2 Sutton, Charles; McCallum, Andrew (2010). "An Introduction to Conditional Random Fields". arXiv: 1011.4088v1 [stat.ML].
↑ Lavergne, Thomas; Yvon, François (September 7, 2017). "Learning the Structure of Variable-Order CRFs: a Finite-State Perspective". Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. Copenhagen, Denmark: Association for Computational Linguistics. p. 433.
↑ Chatzis, Sotirios; Demiris, Yiannis (2013). "The Infinite-Order Conditional Random Field Model for Sequential Data Modeling". IEEE Transactions on Pattern Analysis and Machine Intelligence. 35 (6): 1523–1534. doi:10.1109/tpami.2012.208. hdl: 10044/1/12614 . PMID 23599063. S2CID 690627.
↑ Gasthaus, Jan; Teh, Yee Whye (2010). "Improvements to the Sequence Memoizer" (PDF). Proc. NIPS.
↑ Celeux, G.; Forbes, F.; Peyrard, N. (2003). "EM Procedures Using Mean Field-Like Approximations for Markov Model-Based Image Segmentation". Pattern Recognition. 36 (1): 131–144. Bibcode:2003PatRe..36..131C. CiteSeerX 10.1.1.6.9064 . doi:10.1016/s0031-3203(02)00027-4.
↑ Sarawagi, Sunita; Cohen, William W. (2005). "Semi-Markov conditional random fields for information extraction". In Lawrence K. Saul; Yair Weiss; Léon Bottou (eds.). Advances in Neural Information Processing Systems 17. Cambridge, MA: MIT Press. pp. 1185–1192. Archived from the original (PDF) on 2019-11-30. Retrieved 2015-11-12.
1 2 3 Xu Sun; Takuya Matsuzaki; Daisuke Okanohara; Jun'ichi Tsujii (2009). Latent Variable Perceptron Algorithm for Structured Classification. IJCAI. pp. 1236–1242. Archived from the original on 2018-12-06. Retrieved 2018-12-06.
1 2 Morency, L. P.; Quattoni, A.; Darrell, T. (2007). "Latent-Dynamic Discriminative Models for Continuous Gesture Recognition" (PDF). 2007 IEEE Conference on Computer Vision and Pattern Recognition. p. 1. CiteSeerX 10.1.1.420.6836 . doi:10.1109/CVPR.2007.383299. ISBN 978-1-4244-1179-5. S2CID 7117722.