Conditional Random Fields (2001) › The Structured Prediction Problem

To understand why CRFs represented such an important advance, it helps to examine the nature of structured prediction problems more closely. Imagine we are building a system to analyze the grammatical structure of English sentences. Given the sentence "The cat sat on the mat," we want our system to recognize that "The" is a determiner, "cat" is a noun, "sat" is a verb, "on" is a preposition, and so on. In linguistic notation, we might represent this as the sequence DT NN VB IN DT NN.

The challenge is that the grammatical role of each word depends significantly on context. The word "sat," for instance, could theoretically be a noun in some contexts, but when it appears after a noun like "cat," it is almost certainly functioning as a verb. Similarly, after we predict that "on" is a preposition, we should expect that the following article "the" will be followed by a noun, because that is how English prepositional phrases work.

Earlier approaches to this problem treated each decision independently. They would look at "cat," consider its features in isolation, perhaps note that it is a common noun form, and assign it the label "noun." Then they would move to the next word and repeat the process. This independence assumption made the mathematics tractable and the computation efficient, but it discarded dependencies between labels. The system had no way to prefer sequences of labels that formed grammatically coherent patterns over those that did not.

CRFs addressed this limitation head-on. Instead of making separate independent predictions for each word, a CRF models the probability of the entire label sequence given the entire input sequence. This allows the model to capture regularities like "determiners are usually followed by nouns" or "verbs rarely appear before determiners" directly in its structure. The model learns not just which labels fit which words, but which sequences of labels fit together coherently.