nlp
Label every word
It is 2001 at Carnegie Mellon, and the pipeline systems of statistical NLP keep tripping over their own independence assumptions: tag each word in a sentence with its role, and the right label for one word depends on the labels of its neighbors, which depend on theirs. Generative sequence models force you to model the words themselves, wasting capacity on what is already observed; greedy classifiers commit early errors that cascade to the end of the sentence. Do structured prediction properly: model the whole label sequence conditionally, with global normalization, arbitrary overlapping features, and exact inference over the chain. Every parser, entity extractor, and information pipeline downstream inherits these tags; a principled percentage point here compounds through the entire stack of language technology.
Who this problem belongs to
The two figures whose methods fit it best, out of 57 in contention.
Lafferty, with McCallum and Pereira, invented conditional random fields at exactly this moment, in 2001, while Lafferty was at Carnegie Mellon, to solve precisely this problem: escape the label-bias problem of maximum-entropy Markov models and the conditional-independence assumptions of generative HMMs by modeling the whole label sequence conditionally, with global normalization over the partition function and arbitrary overlapping features drawn from anywhere in the input. This is not an analogy or an adjacent toolkit applied loosely -- it is the actual paper the problem describes, down to the venue, the institution, and the year. No other carrier in this entire batch can claim to have built the specific mathematical object the problem asks for; this is as close to a perfect historical match as the game format allows.
Viterbi's 1967 dynamic-programming algorithm for decoding convolutional codes is, essentially unmodified in its logic, exactly the exact-inference machinery a linear-chain CRF needs at both training and test time -- finding the highest-scoring label sequence, or summing over all possible sequences, by propagating scores forward through the chain and backtracking through pointers. Every statistical sequence-tagging system built since, CRFs included, runs his algorithm or a close variant as its inference engine, making this arguably the single most directly reusable piece of mathematics in the entire problem. What he lacks is the CRF's own distinctive contribution: the discriminative, globally normalized conditional model with arbitrary overlapping features, developed three decades after his information-theory work and outside his own field of communications engineering. But the inference engine at the literal center of the problem is his invention, repurposed.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
57 figures are scored on this problem. Draw it in a battle to see where you land.