Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

Inside the paper

The problem

Labeling a sequence requires decisions that fit together across positions. Locally normalized sequence models can favor states with few possible successors, even when later observations should favor another path.

The idea

Define a conditional probability over the entire label sequence given the observations, using a shared normalization over possible sequences. This lets evidence at different positions compete across whole paths.

How it works

• Features can describe a label transition or a label at a position, and can depend on overlapping parts of the observed sequence.
• A weighted sum of these features gives each complete labeling a score, which is normalized over possible label sequences.
• For a chain of labels, forward and backward recurrences compute the quantities needed for training and inference efficiently.
• The paper describes iterative scaling procedures that adjust feature weights using expectations under the model and the training data.

What it showed

On synthetic examples the conditional random field avoids the severe label bias seen in the locally normalized comparison. In part-of-speech tagging, it also achieves lower error than the compared models, especially when spelling features are included.

Read it for

Read the label-bias example in Section 2 and the definition in Section 3, then inspect Figure 4 and Section 5.3. The iterative scaling equations in Section 4 can wait.

Written in our own words from the paper itself. A draft the editors have not yet reviewed.