We use Viterbi algorithm to find the best tag sequence Y hat for a given input X.
Like the HMM, the linear chain CRF depends at each time step on only one previous output token y.i-1.

State University of New York at Stony Brook

$Yˆ = argmax_{Y∈y} P(Y|X)$
However, the CRF does not compute a probability for each tag at each time step. Instead, at each time step the CRF computes log-linear functions over a set of relevant features, and these local features are aggregated and normalized to produce a global probability for the whole sequence.
In a CRF, the function F maps an entire input sequence X and an entire output sequence Y to a feature vector. Let’s assume we have K features, with a weight wk for each feature $F_{k}$:
$p(Y|X) = \frac{exp(\sum_{k=1}^K w_{k}F_{k}(X,Y))}{\sum_{Y'∈y} exp(\sum_{k=1}^Kw_{k}F_{k}(X,Y'))}$
We’ll call these K functions $F_{k}(X,Y)$ global features, since each one is a property of the entire input sequence X and output sequence Y. We compute them by decomposing into a sum of local features for each position i in Y:
$F_{k}(X,Y) =\sum_{i=1}^n f_{k}(y_{i−1}, y_{i},X,i) $
This constraint to only depend on the current and previous output tokens $y_{i}$ and $y_{i−1}$ are what characterizes a linear chain CRF.  A general CRF allows a feature to make use of any output token, and are thus necessary for tasks in which the decision depend on distant output tokens. General CRFs require more complex inference, and are less commonly used for language processing.

Conditional Random Fields (CRFs)

An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Speech and Language Processing (3rd ed. draft) 

the specific features are automatically populated by using feature templates. Here are some templates that only use information from $y_{i−1}$, $y_{i}$ ,X,i):
$<y_{i}, x_{i}>, <y_{i}, y_{i−1}>, <y_{i}, x_{i−1}, x_{i+2}>$
These templates automatically populate the set of features from every instance in the training and test set. 
Word shape features represent the abstract letter pattern of the word by mapping lower-case letters to ‘x’, upper-case to ‘X’, numbers to ’d’, and retaining punctuation. 
In summary, here are some sample feature templates that help with unknown words (the graph).
The known-word templates are computed for every word seen in the training set; the unknown word features can also be computed for all words in training, or only on training words whose frequency is below some threshold. The result of the known-word templates and word-signature features is a very large set of features. Generally a feature cutoff is used in which features are thrown out if they have count < 5 in the training set.
For CRF training and inference there is always a fixed set of K features with K weights, even though the length of each sentence is different.


Features in a CRF POS Tagger

A CRF for NER makes use of very similar features to a POS tagger.
Gazetteer feature is useful for locations, which is a list of place names, often providing millions of entries for locations with detailed geographical and political information. This can be implemented as a binary feature indicating a phrase appears in the list.


Learn Before

Related