Introduction

Every sentence is a sequence of words, and understanding language often means sticking a label on each one: this is a Person, that is an Organization, and the rest are Other. The task is called sequence labeling, and it sits at the heart of named-entity recognition, part-of-speech tagging, and dozens of other language problems.

The naive approach labels each word independently — look at the word, maybe its neighbors, and pick the most likely tag. But language rarely works that way. "Washington" is a person, a city, or a state depending entirely on what surrounds it. A model that ignores those dependencies will make avoidable mistakes.

Conditional Random Fields (CRFs), introduced by Lafferty, McCallum and Pereira in 2001, solve this by scoring the entire label sequence jointly. Instead of asking "what is the best label for word ii?", a CRF asks "what is the best sequence of labels for the whole sentence?" That global view lets it enforce consistency across positions — if the model commits to B-ORG here, it will naturally prefer I-ORG next rather than an incoherent jump.

CRFs are a solved model: training by maximum-likelihood gradient descent and decoding by the Viterbi algorithm (dynamic programming in O(n⋅k2)O(n \cdot k^2) time, where nn is the sequence length and kk is the number of labels) are both well understood and efficient.

Try It

Below is a short sentence with a hidden gold annotation. Click any word to cycle its label through O (Other), B-PER (person start), I-PER (person continuation), B-ORG (organization start), and I-ORG (organization continuation). The score panel shows how well your labeling agrees with typical CRF transition and emission features.

<!-- CRF Sequence Labeling demo — click each word to cycle its BIO tag -->
<p class="hint">Click any word to cycle its label: O, B-PER, I-PER, B-ORG, I-ORG. The score rewards correct labels (+10) and valid BIO transitions (+3). Red borders mark illegal transitions.</p>
<div id="sentence" class="sentence" role="group" aria-label="Labeled sentence — click words to change their tags"></div>
<div class="score-panel">
  <div class="score-row">
    <span class="score-label">Score:</span>
    <span id="score-value" class="score-value">0</span>
    <span class="score-bar-wrap"><span id="score-bar" class="score-bar"></span></span>
  </div>
  <div id="violations" class="violations"></div>
</div>
<div class="btns">
  <button id="btn-reset" type="button" class="ghost">Reset</button>
  <button id="btn-reveal" type="button">Show gold labels</button>
</div>
<div id="legend" class="legend">
  <span class="tag-O">O</span> Other
  &nbsp;&nbsp;
  <span class="tag-B-PER">B-PER</span> <span class="tag-I-PER">I-PER</span> Person
  &nbsp;&nbsp;
  <span class="tag-B-ORG">B-ORG</span> <span class="tag-I-ORG">I-ORG</span> Organization
</div>

/* CRF demo styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px 4px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.sentence { display: flex; flex-wrap: wrap; gap: 6px; margin-bottom: .8rem; }
.token { display: inline-flex; flex-direction: column; align-items: center; cursor: pointer;
         border-radius: 8px; padding: 6px 10px 5px; border: 2px solid #cdd9e3;
         background: #f0f4f8; transition: all .12s; user-select: none; }
.token:hover { border-color: #5a87c0; }
.token .word { font: 700 15px ui-monospace, monospace; }
.token .tag { font-size: .7rem; font-weight: 600; margin-top: 3px; padding: 1px 5px;
              border-radius: 4px; letter-spacing: .03em; }
/* Tag color coding */
.token[data-tag="O"] .tag { background: #e8eef3; color: #5a7088; }
.token[data-tag="B-PER"] .tag, .token[data-tag="I-PER"] .tag { background: #d4f0e0; color: #1a6e3c; }
.token[data-tag="B-ORG"] .tag, .token[data-tag="I-ORG"] .tag { background: #dde7fb; color: #1d3a8a; }
.token.violation { border-color: #e63946; }
.score-panel { display: flex; flex-direction: column; gap: 4px; margin-bottom: .7rem; }
.score-row { display: flex; align-items: center; gap: 8px; }
.score-label { font-size: .85rem; color: #555; min-width: 80px; }
.score-value { font: 700 15px system-ui; min-width: 28px; text-align: right; }
.score-bar-wrap { flex: 1; height: 10px; background: #e0e7ef; border-radius: 5px; overflow: hidden; }
.score-bar { height: 100%; background: #1d8a4e; border-radius: 5px; width: 0; transition: width .3s; }
.violations { font-size: .8rem; color: #c0392b; min-height: 1.2em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.legend { font-size: .78rem; color: #555; display: flex; flex-wrap: wrap; align-items: center; gap: 4px; }
.legend .tag-O { background: #e8eef3; color: #5a7088; padding: 1px 6px; border-radius: 4px; font-weight: 600; }
.legend .tag-B-PER, .legend .tag-I-PER { background: #d4f0e0; color: #1a6e3c; padding: 1px 6px; border-radius: 4px; font-weight: 600; }
.legend .tag-B-ORG, .legend .tag-I-ORG { background: #dde7fb; color: #1d8a4e; padding: 1px 6px; border-radius: 4px; font-weight: 600; }
.tag-I-PER { background: #d4f0e0; color: #1a6e3c; }
.tag-B-ORG { background: #dde7fb; color: #1d3a8a; }
.tag-I-ORG { background: #dde7fb; color: #1d3a8a; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// The input sentence (tokens)
const WORDS = ['Marie', 'Curie', 'worked', 'at', 'the', 'University', 'of', 'Paris'];
// Gold (reference) BIO labels for this sentence
const GOLD  = ['B-PER', 'I-PER', 'O', 'O', 'O', 'B-ORG', 'I-ORG', 'I-ORG'];
const LABELS = ['O', 'B-PER', 'I-PER', 'B-ORG', 'I-ORG'];
// Current user labeling, starts all-O
let current = WORDS.map(() => 'O');

// Allowed BIO transitions (valid CRF label pairs)
// I-X after O is illegal; I-X after B-Y or I-Y where X!=Y is also illegal
const ALLOWED_TRANS = new Set([
  'O->O', 'O->B-PER', 'O->B-ORG',
  'B-PER->I-PER', 'B-PER->O', 'B-PER->B-ORG', 'B-PER->B-PER',
  'I-PER->I-PER', 'I-PER->O', 'I-PER->B-ORG', 'I-PER->B-PER',
  'B-ORG->I-ORG', 'B-ORG->O', 'B-ORG->B-PER', 'B-ORG->B-ORG',
  'I-ORG->I-ORG', 'I-ORG->O', 'I-ORG->B-PER', 'I-ORG->B-ORG'
]);

// Compute score and collect BIO violations
function computeScore() {
  let score = 0;
  const violations = [];
  // Emission score: +10 for each token matching the gold label
  current.forEach((tag, i) => { if (tag === GOLD[i]) score += 10; });
  // Transition score: +3 for each consecutive valid BIO pair
  for (let i = 0; i < current.length - 1; i++) {
    const trans = current[i] + '->' + current[i + 1];
    if (ALLOWED_TRANS.has(trans)) score += 3;
    else violations.push(i18nFmt('%a% then %b% is not a valid BIO transition.', { a: current[i], b: current[i + 1] }));
  }
  return { score, violations };
}

function render() {
  const container = document.getElementById('sentence');
  container.innerHTML = '';
  WORDS.forEach((word, i) => {
    const tok = document.createElement('span');
    tok.className = 'token';
    tok.dataset.tag = current[i];
    tok.title = 'Click to change label';
    tok.innerHTML = '<span class="word">' + word + '</span><span class="tag">' + current[i] + '</span>';
    tok.addEventListener('click', () => {
      const idx = LABELS.indexOf(current[i]);
      current[i] = LABELS[(idx + 1) % LABELS.length];
      updateAll();
    });
    container.appendChild(tok);
  });
  updateScore();
}

function updateScore() {
  const { score, violations } = computeScore();
  const maxScore = WORDS.length * 10 + (WORDS.length - 1) * 3;
  document.getElementById('score-value').textContent = score;
  document.getElementById('score-bar').style.width = Math.round((score / maxScore) * 100) + '%';
  const vEl = document.getElementById('violations');
  if (violations.length) {
    vEl.textContent = i18nFmt('%n% invalid transition(s):', { n: violations.length }) + ' ' + violations[0];
  } else {
    vEl.textContent = score >= maxScore * 0.85 ? 'Great labeling — all transitions valid!' : 'Keep adjusting to improve the score.';
  }
  // Highlight tokens whose outgoing transition is illegal
  document.querySelectorAll('.token').forEach((tok, i) => {
    const trans = i < current.length - 1 ? current[i] + '->' + current[i + 1] : null;
    tok.classList.toggle('violation', trans !== null && !ALLOWED_TRANS.has(trans));
  });
}

function updateAll() {
  document.querySelectorAll('.token').forEach((tok, i) => {
    tok.dataset.tag = current[i];
    tok.querySelector('.tag').textContent = current[i];
  });
  updateScore();
}

document.getElementById('btn-reset').addEventListener('click', () => {
  current = WORDS.map(() => 'O');
  render();
});
document.getElementById('btn-reveal').addEventListener('click', () => {
  current = [...GOLD];
  updateAll();
});
render();
Result
Console

Notice that some transitions feel "wrong" even before checking the score — I-ORG right after O is a red flag, because the BIO convention says a continuation tag must follow a matching begin tag. A CRF learns exactly these cross-position constraints from data, encoding them as transition features in the model's log-linear score.

The Real Complexity

Unlike many learning problems that hide NP-hard inference inside them, CRFs are remarkably tractable:

  • Decoding (finding the best label sequence given the model) runs in O(n⋅k2)O(n \cdot k^2) time via the Viterbi algorithm — dynamic programming that sweeps left to right, keeping only the best partial path to each state. With nn words and kk labels, you fill a table of size n×kn \times k in time proportional to k2k^2 per step.
  • Training optimizes a convex log-likelihood objective. Gradient descent with L-BFGS converges to the global optimum; there are no local minima to worry about.
  • Marginals (the probability of each label at each position, summed over all consistent sequences) come from the forward–backward algorithm, also O(n⋅k2)O(n \cdot k^2), and are needed for the gradient.

The real difficulty is not computational but representational: the model is only as good as its features. Traditional CRFs rely on handcrafted indicator functions — is the current word capitalized? Does it end in -ing? What is the previous predicted label? Getting these right is an art.

Modern systems layer a CRF on top of a deep neural network (a BiLSTM-CRF or Transformer-CRF) that learns features automatically, combining the expressive power of neural representations with the global consistency guarantee of the CRF output layer. This combination — tractable exact decoding on top of learned representations — is why CRFs remain relevant in the era of large language models. Compare this to the unconstrained sampling in Bayesian inference, where exact inference is often intractable.

Where It Matters

Sequence labeling appears wherever meaning is distributed across positions, and CRFs have been deployed across a wide range:

  • Named-entity recognition (NER): tagging people, places, organizations, and dates in news articles, contracts, and medical records — the classic CRF application since Lafferty et al. (2001).
  • Part-of-speech tagging: assigning grammatical roles (noun, verb, adjective, …) to every token; the context-sensitive transitions give CRFs an edge over per-word classifiers.
  • Chunking and shallow parsing: identifying noun phrases, verb phrases, and other syntactic chunks without building a full parse tree.
  • Biomedical NLP: finding gene names, protein mentions, and clinical entities in scientific literature, where domain-specific capitalization and compound words make feature design critical.
  • OCR post-correction: fixing errors in scanned text by treating the sequence of recognized characters as a sequence-labeling problem with spelling constraints as features.
  • Computer vision: CRFs model spatial label dependencies in image segmentation and scene labeling, extending the sequential model to two-dimensional grids.

The common thread: whenever the correct label at position ii depends on what comes before and after, a model that scores the full sequence will outperform one that labels positions independently. Related ideas appear in pattern matching, where finding structure in sequences is also the central challenge.

Conclusion

Conditional Random Fields occupy a special place in machine learning: they are one of the few models where you can score an exponential number of possible outputs — all knk^n label sequences — and still find the best one exactly, in polynomial time, via Viterbi. That is not obvious, and it is not free; it relies on the chain structure of the model.

The lesson generalizes. Whenever a problem has sequential structure and you need globally consistent predictions, the right tool is a model that scores sequences, not positions. CRFs made that lesson concrete for language, and their influence echoes in every modern neural sequence model that terminates with a structured output layer.

Whether you are tagging entities in a legal brief or segmenting proteins in a genome, you are solving the same problem Lafferty, McCallum and Pereira formalized in 2001: given a sequence of observations, find the label sequence that is most consistent with everything you know — not just locally, but globally.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/crf-sequence-labeling/Content licensed under CC BY-NC 4.0.