HMM and CRF: the label bias problem and I-equivalence

Question

I have a question about the label bias problem in HMM and CRF.

I understand that HMM and MEMM suffer from the label bias problem, which is a preference for states with fewer transitions. The problem is due to the fact that in HMM and MEMM use local probabilities (each probability has to sum to 1), and thus, states with fewer transitions have a larger probability for its transitions. CRF alleviates this problem by global normalization, so that local potentials don't have to sum to 1.

What I am confused about is its relationship to I-equivalence between HMM/MEMM and CRF. Consider the following graphical models over variables $Y_{1:T}$ (where $X$ can be viewed as always given):

• Directed graph $D$: $$Y_1\rightarrow Y_2\rightarrow\cdots\rightarrow Y_T $$
• Undirected graph $G$: $$Y_1 - Y_2 - \cdots - Y_T $$

It's obvious that $D$ and $G$ have the same I-map, thus being I-equivalent.

In both cases, the inference objective is to find $$Y_{1:T}^*=\operatorname{argmax}_{Y_{1:T}} p(Y_1,\cdots, Y_T)$$ However, $D$ suffers from the label bias problem, whereas $G$ doesn't.

I am wondering if $G$ has a stronger power of modeling joint probabilities than $D$ (i.e., $D$'s hypothesis class is a subset of $G$) despite their I-equivalence.

I would appreciate any insight. Thanks.

Answer 1

Expanding on my comment: the answer is clearer when you realize that you can't ignore the observed variables. They affect each model differently. As it turns out, the MEMM is not I-equivalent to the linear-chain CRF and HMM.

As a recap, the HMM looks like this:

y1 -> y2 -> y3 -> ... -> yn
 |     |     |            |
 v     v     v            v
x1    x2    x3           xn

The MEMM looks like this:

y1 -> y2 -> y3 -> ... -> yn
 ʌ     ʌ     ʌ            ʌ
 |     |     |            |
x1    x2    x3           xn

While the skeleton is the same, this has different immoralities than the HMM. (Note the v-structure at each $y_i$ for $i>1$; the HMM doesn't have immoralities.) That means that the MEMM's I-map is different from the HMM's I-map.

Finally, the linear-chain CRF.

y1 —— y2 —— y3 —— ... —— yn
 |     |     |            |
 |     |     |            |
x1    x2    x3           xn

This is I-equivalent to the HMM, but not to the MEMM. (Try moralizing both if you are not convinced.)

---

This website explains in depth why HMMs don't suffer from label bias, but MEMMs do. The MEMM always has one unit of probability mass to mete out among the choices for the next state (“conservation of score mass”; Bottou, 1991). In the HMM, the observation modulates how much mass there is to distribute. And, of course, the CRF is globally normalized; there's no constraint on the mass.