Questions: Sequence Labeling and CRFs

Question 1

An HMM and a CRF are trained on the same part-of-speech tagging dataset. The CRF achieves significantly higher accuracy. What is the most likely reason?

• A. The CRF uses a more powerful inference algorithm than Viterbi, finding globally optimal label sequences that HMMs cannot
• B. The CRF can incorporate arbitrary features of the input — capitalization, word suffixes, neighboring words — without the HMM's independence constraint that observation probability depends only on the current tag
• C. The CRF captures longer-range label-to-label dependencies, whereas HMMs only model adjacent tag pairs
• D. The CRF uses a larger tag vocabulary, distinguishing more fine-grained parts of speech

Answer: (B)

The CRF's key advantage is discriminative modeling: it learns P(tags|words) directly, allowing feature functions that examine any part of the input sequence. An HMM must model P(words, tags) jointly, which means the probability of each word must be modeled given only its tag — it cannot easily use features like 'ends in -ing' or 'the previous word is a determiner' without dramatically expanding the state space. Both models use Viterbi for inference and both model adjacent-tag dependencies; the feature richness is the decisive difference.

Question 2

A student argues that CRFs outperform HMMs because CRFs model dependencies between consecutive labels, whereas HMMs treat each label independently. What is wrong with this claim?

• A. The student is correct — HMMs assume all labels are independent and cannot model transitions
• B. HMMs also model label-to-label dependencies through transition probabilities; the actual CRF advantage is discriminative modeling that allows arbitrary input features without requiring a generative model of observations
• C. CRFs cannot model label dependencies — they score each label position independently and then pick the best combination
• D. Both models are equivalent in practice; performance differences come only from training data size

Answer: (B)

HMMs explicitly model P(tag_t | tag_{t-1}) as transition probabilities — label dependencies are central to HMM design. CRFs also capture label-to-label interactions through pairwise feature functions on adjacent labels. The real difference is the generative vs. discriminative distinction: HMMs model how observations are generated (P(word|tag)), forcing a strong independence assumption; CRFs model the conditional distribution directly (P(tags|words)), freeing them to use any observable feature of the input sequence.

Question 3

Both Hidden Markov Models and linear-chain CRFs use the Viterbi algorithm to find the most probable label sequence at inference time.

• T. True
• F. False

Answer: True

The Viterbi algorithm is a dynamic programming approach that efficiently finds the most probable path through a sequence of states or labels — it applies to any model where the score of a label sequence decomposes into local scores at each position and at each adjacent pair. Both HMMs and linear-chain CRFs have this factorization structure, so Viterbi works for both. The partition function (for training) is computed with the forward algorithm in both cases. The algorithms are shared; the difference is what is being computed — joint probability in HMMs, conditional probability in CRFs.

Question 4

A CRF's main advantage over an HMM is that it captures label-to-label dependencies that HMMs fundamentally cannot model.

• T. True
• F. False

Answer: False

HMMs do model label dependencies — they are the core of the HMM design, encoded as transition probabilities P(tag_t | tag_{t-1}). The CRF's actual advantage is discriminative modeling: it directly models P(labels|observations) without requiring a generative story for how observations arise. This allows arbitrary feature functions on the input, such as 'does the current word end in -tion?' or 'is the next word capitalized?' — features that would be awkward or impossible for an HMM to use without expanding its state space enormously.

Question 5

Explain why a CRF can incorporate features like 'the word ends in -ing' or 'the previous word is a title' more effectively than an HMM, even though both models capture dependencies between adjacent labels.

Model answer: An HMM models the joint probability P(words, tags) by factoring it into emission probabilities P(word|tag) and transition probabilities P(tag|prev_tag). To use a feature like 'ends in -ing', the HMM must model the probability of observing a word ending in -ing given a particular tag — it must generate the feature, treating it as part of the observation model. This requires estimating many parameters and assumes the feature's distribution is independent of other features given the tag. A CRF models P(tags|words) directly, so features can be arbitrary functions of the entire observation sequence — it doesn't need to model how features are generated, only how they correlate with labels. This makes CRFs naturally suited to rich, overlapping feature sets.

The generative vs. discriminative distinction is fundamental: generative models (HMMs) must model the full data distribution P(x,y), which constrains what they can condition on. Discriminative models (CRFs) only model P(y|x), which means any observable property of x can be a feature for free. This is why feature engineering dominated NLP before deep learning: CRFs could absorb any handcrafted feature, while HMMs struggled with feature-rich inputs.