|
A conditional random field (CRF) is a type of discriminative probabilistic model most often used for the labeling or parsing of sequential data, such as natural language text or biological sequences.
Description Much like a Markov random field, a CRF is an undirected graphical model in which each vertex represents a random variable whose distribution is to be inferred, and each edge represents a dependency between two random variables. In a CRF, the distribution of each discrete random variable in the graph is conditioned on an input sequence . In principle, the layout of the graph of random variables can be arbitrary; most often, however, 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 model training, learning the conditional distributions between the and feature functions from some corpus of training data, inference, determining the probability of a given label sequence given , and decoding, determining the most likely label sequence given . The conditional dependency of each on is defined through a fixed set of feature functions of the form , which can informally 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 . Relationship to hidden Markov models 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 at any point during inference, and the range of the feature functions need not have a probabilistic interpretation. The well-known forward-backward and Viterbi algorithms for HMMs have direct analogues for CRFs, with the same asymptotic running times. The training step, which determines a weight for each feature function, is somewhat more complex; generally, there is no closed-form solution for the optimal assignment of weights, so it must be found using a numerical optimization algorithm. 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 . Training and inference are only practical for small values of (such as ), since their computational cost increase exponentially with . There exists another generalization of CRFs, the semi-Markov conditional random field (semi-CRF), which model 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. | ||||||||
|
| |||||||||
 |
|
| |